-- The lists of dead rows that an OFFSET over the global order asks for (the rows a segment lost to VACUUM, by unit) are kept by the backend for the next scan: the second query finds them
-- (sift._test_col_gdead_stats), and a query after more rows were cleared (DELETE and VACUUM, an UPDATE, a promotion, a merge, new rows at the freed addresses) makes them again. Every answer is the
-- table's without the index (p takes the same writes and is the oracle), between two queries of the same backend, and through a script of random writes.
CREATE EXTENSION pg_sift_test CASCADE;
NOTICE:  installing required extension "pg_sift"
SET client_min_messages = warning;
SET max_parallel_workers_per_gather = 0;
SET sift.async_maintenance = off;
SET max_parallel_maintenance_workers = 0;
SELECT setseed(0.42);
 setseed 
---------
 
(1 row)

CREATE TABLE t (id int PRIMARY KEY, k int, u int, pad text DEFAULT repeat('x', 100));
ALTER TABLE t ALTER COLUMN pad SET STORAGE PLAIN;
INSERT INTO t (id, k, u) SELECT i, (hashint4(i) & 16777215) % 2000, (hashint4(i + 5) & 16777215) % 1000003 FROM generate_series(1, 30000) i;
CREATE INDEX t_ix ON t USING sift_col (id, k, u) WITH (order_columns = 'k, u', order_array_columns = 'k, u', write_buffer_limit = 64);
CREATE TABLE p AS TABLE t;
ANALYZE t;
ANALYZE p;
SET sift.agg_force = on;
CREATE FUNCTION same(q text) RETURNS boolean LANGUAGE plpgsql AS $$
DECLARE a text; b text;
BEGIN
	EXECUTE format('SELECT string_agg(r::text, '','') FROM (%s) r', replace(q, '@', 't')) INTO a;
	EXECUTE format('SELECT string_agg(r::text, '','') FROM (%s) r', replace(q, '@', 'p')) INTO b;
	RETURN a IS NOT DISTINCT FROM b;
END $$;
-- ties (k has 2,000 values: the group the offset ends in is fetched, the groups before it are counted), a key with no repeats, descending, a filtered and a deep one
CREATE FUNCTION allq() RETURNS boolean LANGUAGE sql AS $$
	SELECT same('SELECT id, k FROM @ ORDER BY k, id LIMIT 20 OFFSET 4000') AND same('SELECT id, u FROM @ ORDER BY u, id LIMIT 20 OFFSET 6000')
	   AND same('SELECT id, k FROM @ ORDER BY k DESC, id LIMIT 20 OFFSET 12000') AND same('SELECT id, u FROM @ WHERE k < 1000 ORDER BY u DESC, id LIMIT 20 OFFSET 3000')
	   AND same('SELECT id, k FROM @ ORDER BY k, id LIMIT 20 OFFSET 20000') $$;
CREATE TABLE res (step text, equal boolean, hits int8, builds int8);
CREATE FUNCTION step(name text) RETURNS void LANGUAGE plpgsql AS $$
DECLARE h0 int8; b0 int8; h1 int8; b1 int8; ok boolean;
BEGIN
	SELECT hits, builds INTO h0, b0 FROM sift._test_col_gdead_stats();
	ok := allq();
	SELECT hits, builds INTO h1, b1 FROM sift._test_col_gdead_stats();
	INSERT INTO res VALUES (name, ok, h1 - h0, b1 - b0);
END $$;
SELECT step('clean');
 step 
------
 
(1 row)

-- the first query after rows were cleared makes the lists (builds), the second finds them (hits)
DELETE FROM t WHERE id % 37 = 0;
DELETE FROM p WHERE id % 37 = 0;
VACUUM t;
SELECT step('delete, vacuum');
 step 
------
 
(1 row)

SELECT step('again');
 step 
------
 
(1 row)

UPDATE t SET k = k + 1 WHERE id % 41 = 0;
UPDATE p SET k = k + 1 WHERE id % 41 = 0;
SELECT step('update, no vacuum');
 step 
------
 
(1 row)

VACUUM t;
SELECT step('update, vacuum');
 step 
------
 
(1 row)

SELECT step('again');
 step 
------
 
(1 row)

-- new rows take the freed addresses
INSERT INTO t (id, k, u) SELECT 40000 + i, (hashint4(i + 9) & 16777215) % 2000, (hashint4(i + 13) & 16777215) % 1000003 FROM generate_series(1, 3000) i;
INSERT INTO p SELECT * FROM t WHERE id >= 40000;
SELECT step('insert');
 step 
------
 
(1 row)

SELECT sift.col_promote('t_ix') >= 0 AS promoted;
 promoted 
----------
 t
(1 row)

SELECT step('promotion');
 step 
------
 
(1 row)

DELETE FROM t WHERE id % 43 = 0;
DELETE FROM p WHERE id % 43 = 0;
VACUUM t;
SELECT step('delete, vacuum');
 step 
------
 
(1 row)

SELECT step('again');
 step 
------
 
(1 row)

SELECT sift.col_merge('t_ix', true) >= 0 AS merged;
 merged 
--------
 t
(1 row)

SELECT step('merge');
 step 
------
 
(1 row)

DELETE FROM t WHERE id % 47 = 0;
DELETE FROM p WHERE id % 47 = 0;
VACUUM t;
SELECT step('delete, vacuum');
 step 
------
 
(1 row)

SELECT step('again');
 step 
------
 
(1 row)

SELECT step, equal, hits > 0 AS found, builds > 0 AS made FROM res ORDER BY ctid;
       step        | equal | found | made 
-------------------+-------+-------+------
 clean             | t     | f     | f
 delete, vacuum    | t     | t     | t
 again             | t     | t     | f
 update, no vacuum | t     | t     | f
 update, vacuum    | t     | t     | t
 again             | t     | t     | f
 insert            | t     | t     | f
 promotion         | t     | t     | f
 delete, vacuum    | t     | t     | t
 again             | t     | t     | f
 merge             | t     | f     | f
 delete, vacuum    | t     | t     | t
 again             | t     | t     | f
(13 rows)

-- a script of random writes, each followed by the queries (a statement of its own: VACUUM cannot share a transaction)
CREATE TABLE script (n serial, stmt text);
CREATE TABLE randres (n int, equal boolean);
INSERT INTO script (stmt)
SELECT stmt FROM (
	SELECT i, o, stmt FROM (
		SELECT i, CASE (random() * 5)::int
			WHEN 0 THEN ARRAY[format('DELETE FROM t WHERE id %% %s = %s', m, r), format('DELETE FROM p WHERE id %% %s = %s', m, r)]
			WHEN 1 THEN ARRAY[format('UPDATE t SET k = (hashint4(id + %s) & 16777215) %% 2000 WHERE id %% %s = %s', i, m, r), format('UPDATE p SET k = (hashint4(id + %s) & 16777215) %% 2000 WHERE id %% %s = %s', i, m, r)]
			WHEN 2 THEN ARRAY[format('INSERT INTO t (id, k, u) SELECT %s + g, (hashint4(g + %s) & 16777215) %% 2000, (hashint4(g + %s) & 16777215) %% 1000003 FROM generate_series(1, %s) g', 100000 + i * 5000, i, i + 3, 200 + m * 20),
						   format('INSERT INTO p SELECT * FROM t WHERE id > %s AND id <= %s', 100000 + i * 5000, 100000 + i * 5000 + 200 + m * 20)]
			WHEN 3 THEN ARRAY['SELECT sift.col_promote(''t_ix'') >= 0']
			ELSE ARRAY['VACUUM t'] END AS stmts
		FROM (SELECT i, 31 + (random() * 20)::int AS m, (random() * 10)::int AS r FROM generate_series(1, 36) i) s
	) a, unnest(a.stmts) WITH ORDINALITY u(stmt, o)
	UNION ALL SELECT i, 9, format('INSERT INTO randres SELECT %s, allq()', i) FROM generate_series(1, 36) i
) w ORDER BY i, o;
SELECT stmt FROM script ORDER BY n \gexec
VACUUM t
INSERT INTO randres SELECT 1, allq()
UPDATE t SET k = (hashint4(id + 2) & 16777215) % 2000 WHERE id % 32 = 1
UPDATE p SET k = (hashint4(id + 2) & 16777215) % 2000 WHERE id % 32 = 1
INSERT INTO randres SELECT 2, allq()
SELECT sift.col_promote('t_ix') >= 0
 ?column? 
----------
 t
(1 row)

INSERT INTO randres SELECT 3, allq()
VACUUM t
INSERT INTO randres SELECT 4, allq()
UPDATE t SET k = (hashint4(id + 5) & 16777215) % 2000 WHERE id % 48 = 8
UPDATE p SET k = (hashint4(id + 5) & 16777215) % 2000 WHERE id % 48 = 8
INSERT INTO randres SELECT 5, allq()
VACUUM t
INSERT INTO randres SELECT 6, allq()
INSERT INTO t (id, k, u) SELECT 135000 + g, (hashint4(g + 7) & 16777215) % 2000, (hashint4(g + 10) & 16777215) % 1000003 FROM generate_series(1, 860) g
INSERT INTO p SELECT * FROM t WHERE id > 135000 AND id <= 135860
INSERT INTO randres SELECT 7, allq()
INSERT INTO t (id, k, u) SELECT 140000 + g, (hashint4(g + 8) & 16777215) % 2000, (hashint4(g + 11) & 16777215) % 1000003 FROM generate_series(1, 940) g
INSERT INTO p SELECT * FROM t WHERE id > 140000 AND id <= 140940
INSERT INTO randres SELECT 8, allq()
VACUUM t
INSERT INTO randres SELECT 9, allq()
SELECT sift.col_promote('t_ix') >= 0
 ?column? 
----------
 t
(1 row)

INSERT INTO randres SELECT 10, allq()
UPDATE t SET k = (hashint4(id + 11) & 16777215) % 2000 WHERE id % 35 = 6
UPDATE p SET k = (hashint4(id + 11) & 16777215) % 2000 WHERE id % 35 = 6
INSERT INTO randres SELECT 11, allq()
UPDATE t SET k = (hashint4(id + 12) & 16777215) % 2000 WHERE id % 39 = 3
UPDATE p SET k = (hashint4(id + 12) & 16777215) % 2000 WHERE id % 39 = 3
INSERT INTO randres SELECT 12, allq()
VACUUM t
INSERT INTO randres SELECT 13, allq()
DELETE FROM t WHERE id % 35 = 8
DELETE FROM p WHERE id % 35 = 8
INSERT INTO randres SELECT 14, allq()
VACUUM t
INSERT INTO randres SELECT 15, allq()
UPDATE t SET k = (hashint4(id + 16) & 16777215) % 2000 WHERE id % 31 = 1
UPDATE p SET k = (hashint4(id + 16) & 16777215) % 2000 WHERE id % 31 = 1
INSERT INTO randres SELECT 16, allq()
UPDATE t SET k = (hashint4(id + 17) & 16777215) % 2000 WHERE id % 37 = 2
UPDATE p SET k = (hashint4(id + 17) & 16777215) % 2000 WHERE id % 37 = 2
INSERT INTO randres SELECT 17, allq()
INSERT INTO t (id, k, u) SELECT 190000 + g, (hashint4(g + 18) & 16777215) % 2000, (hashint4(g + 21) & 16777215) % 1000003 FROM generate_series(1, 1200) g
INSERT INTO p SELECT * FROM t WHERE id > 190000 AND id <= 191200
INSERT INTO randres SELECT 18, allq()
DELETE FROM t WHERE id % 44 = 2
DELETE FROM p WHERE id % 44 = 2
INSERT INTO randres SELECT 19, allq()
VACUUM t
INSERT INTO randres SELECT 20, allq()
DELETE FROM t WHERE id % 40 = 3
DELETE FROM p WHERE id % 40 = 3
INSERT INTO randres SELECT 21, allq()
INSERT INTO t (id, k, u) SELECT 210000 + g, (hashint4(g + 22) & 16777215) % 2000, (hashint4(g + 25) & 16777215) % 1000003 FROM generate_series(1, 1180) g
INSERT INTO p SELECT * FROM t WHERE id > 210000 AND id <= 211180
INSERT INTO randres SELECT 22, allq()
VACUUM t
INSERT INTO randres SELECT 23, allq()
INSERT INTO t (id, k, u) SELECT 220000 + g, (hashint4(g + 24) & 16777215) % 2000, (hashint4(g + 27) & 16777215) % 1000003 FROM generate_series(1, 860) g
INSERT INTO p SELECT * FROM t WHERE id > 220000 AND id <= 220860
INSERT INTO randres SELECT 24, allq()
INSERT INTO t (id, k, u) SELECT 225000 + g, (hashint4(g + 25) & 16777215) % 2000, (hashint4(g + 28) & 16777215) % 1000003 FROM generate_series(1, 1200) g
INSERT INTO p SELECT * FROM t WHERE id > 225000 AND id <= 226200
INSERT INTO randres SELECT 25, allq()
UPDATE t SET k = (hashint4(id + 26) & 16777215) % 2000 WHERE id % 38 = 3
UPDATE p SET k = (hashint4(id + 26) & 16777215) % 2000 WHERE id % 38 = 3
INSERT INTO randres SELECT 26, allq()
VACUUM t
INSERT INTO randres SELECT 27, allq()
SELECT sift.col_promote('t_ix') >= 0
 ?column? 
----------
 t
(1 row)

INSERT INTO randres SELECT 28, allq()
SELECT sift.col_promote('t_ix') >= 0
 ?column? 
----------
 t
(1 row)

INSERT INTO randres SELECT 29, allq()
INSERT INTO t (id, k, u) SELECT 250000 + g, (hashint4(g + 30) & 16777215) % 2000, (hashint4(g + 33) & 16777215) % 1000003 FROM generate_series(1, 1080) g
INSERT INTO p SELECT * FROM t WHERE id > 250000 AND id <= 251080
INSERT INTO randres SELECT 30, allq()
DELETE FROM t WHERE id % 51 = 1
DELETE FROM p WHERE id % 51 = 1
INSERT INTO randres SELECT 31, allq()
VACUUM t
INSERT INTO randres SELECT 32, allq()
VACUUM t
INSERT INTO randres SELECT 33, allq()
UPDATE t SET k = (hashint4(id + 34) & 16777215) % 2000 WHERE id % 34 = 2
UPDATE p SET k = (hashint4(id + 34) & 16777215) % 2000 WHERE id % 34 = 2
INSERT INTO randres SELECT 34, allq()
UPDATE t SET k = (hashint4(id + 35) & 16777215) % 2000 WHERE id % 37 = 3
UPDATE p SET k = (hashint4(id + 35) & 16777215) % 2000 WHERE id % 37 = 3
INSERT INTO randres SELECT 35, allq()
INSERT INTO t (id, k, u) SELECT 280000 + g, (hashint4(g + 36) & 16777215) % 2000, (hashint4(g + 39) & 16777215) % 1000003 FROM generate_series(1, 1060) g
INSERT INTO p SELECT * FROM t WHERE id > 280000 AND id <= 281060
INSERT INTO randres SELECT 36, allq()
SELECT count(*) AS runs, count(*) FILTER (WHERE equal) AS equal FROM randres;
 runs | equal 
------+-------
   36 |    36
(1 row)

SELECT sift.col_verify('t_ix');
 col_verify 
------------
 
(1 row)

DROP TABLE t, p, res, script, randres;
DROP FUNCTION same(text), allq(), step(text);
DROP EXTENSION pg_sift_test;
DROP EXTENSION pg_sift;