-- order_layout = compact: the order of a leaf of many rows keeps the heap address of each row and its key rounded to a bucket; the exact keys are read from the
-- rows of the heap. Every ordered read answers what the table does (a copy without an index is the oracle): each column type, ASC and DESC, NULLs, LIMIT and OFFSET, bounds at the ends, in the middle and
-- in a bracket, a write buffer, dead rows, updates that change a key, HOT updates, aborted writes, reused addresses, VACUUM, a merge, a rewrite and REINDEX.
-- The chunks of the first and last 2 * sift.test_col_gorder_ends entries are whole (128 here, 8,192 otherwise).
CREATE EXTENSION pg_sift;
CREATE EXTENSION pg_sift_helpers;
SET client_min_messages = warning;
SET sift.async_maintenance = off;
-- plain chunks: the column format minors below tell the layouts apart (col_gorder_seek covers the seekable ones)
SET sift.test_limits = 'gord_seek_pct=0';
SET sift.test_col_gorder_ends = 64;
SET max_parallel_workers_per_gather = 0;
SELECT setseed(0.42);
 setseed 
---------
 
(1 row)

CREATE TABLE t (id int, ts timestamp, tz timestamptz, d date, s smallint, b bigint, dup int, pad int, tie bigint);
INSERT INTO t SELECT i, TIMESTAMP '2026-01-01' + random() * 300 * INTERVAL '1 day', TIMESTAMPTZ '2026-01-01 00:00:00+00' + random() * 300 * INTERVAL '1 day', DATE '2026-01-01' + (random() * 300)::int,
	CASE WHEN i % 11 = 0 THEN NULL ELSE (random() * 30000)::int - 15000 END, CASE WHEN i % 7 = 0 THEN NULL ELSE (random() * 1000000000000)::bigint - 500000000000 END, (random() * 20)::int, 0, (random() * 2000)::int * 1000000000::bigint
FROM generate_series(1, 6000) i;
CREATE INDEX t_ix ON t USING sift_col (id, ts, tz, d, s, b, dup, pad, tie) WITH (order_columns = 'ts, tz, d, s, b, dup, tie', order_array_columns = 'ts, tz, d, s, b, dup, tie', write_buffer_limit = 64, order_layout = 'compact');
INSERT INTO t SELECT 6000 + i, TIMESTAMP '2026-01-01' + random() * 300 * INTERVAL '1 day', TIMESTAMPTZ '2026-01-01 00:00:00+00' + random() * 300 * INTERVAL '1 day', DATE '2026-01-01' + (random() * 300)::int,
	(random() * 30000)::int - 15000, (random() * 1000000000000)::bigint - 500000000000, (random() * 20)::int, 0, (random() * 2000)::int * 1000000000::bigint FROM generate_series(1, 1500) i;
SELECT sift.col_promote('t_ix') >= 0 AS promoted;
 promoted 
----------
 t
(1 row)

SELECT format, count(*) AS segments, sum(rows) AS rows FROM sift.col_segments('t_ix') WHERE kind = 'immutable' GROUP BY format ORDER BY format;
 format | segments | rows 
--------+----------+------
     38 |        1 |  339
     41 |        2 | 7161
(2 rows)

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

-- rows that stay in the write buffer: the order reads them from memory
INSERT INTO t SELECT 8000 + i, TIMESTAMP '2026-01-01' + random() * 300 * INTERVAL '1 day', TIMESTAMPTZ '2026-01-01 00:00:00+00' + random() * 300 * INTERVAL '1 day', DATE '2026-01-01' + (random() * 300)::int,
	(random() * 30000)::int - 15000, (random() * 1000000000000)::bigint - 500000000000, (random() * 20)::int, 0, (random() * 2000)::int * 1000000000::bigint FROM generate_series(1, 100) i;
CREATE TABLE p AS SELECT * FROM t;
ANALYZE t;
ANALYZE p;
CREATE FUNCTION global_order(q text) RETURNS boolean LANGUAGE sql AS $$ SELECT sift_helpers.plan_reads_global_order(q) $$;
CREATE FUNCTION same(q text) RETURNS boolean LANGUAGE sql AS $$ SELECT sift_helpers.same_keys_in_t_and_p(q) $$;
-- the quantiles of each column, as literals of its type: the bounds of the shapes
CREATE FUNCTION quant(col text, ty text, f float8) RETURNS text LANGUAGE plpgsql AS $$
DECLARE r text;
BEGIN
	EXECUTE format('SELECT quote_literal(percentile_disc(%s) WITHIN GROUP (ORDER BY %I))||''::%s'' FROM p', f, col, ty) INTO r;
	RETURN r;
END $$;
CREATE TABLE shapes AS
SELECT col, ty, dir, nl, lim, off, lo, hi, quant(col, ty, 0.5) AS mid
FROM (VALUES ('ts', 'timestamp'), ('tz', 'timestamptz'), ('d', 'date'), ('s', 'smallint'), ('b', 'bigint'), ('dup', 'int'), ('tie', 'bigint')) c(col, ty),
	 (VALUES ('ASC'), ('DESC')) d(dir),
	 (VALUES ('NULLS FIRST'), ('NULLS LAST')) n(nl),
	 (VALUES (1), (20), (100)) l(lim),
	 (VALUES (0), (30), (700), (3000)) o(off),
	 (VALUES (NULL::float8), (0.01), (0.5), (0.98)) b1(lo),
	 (VALUES (NULL::float8), (0.02), (0.5), (0.99)) b2(hi)
WHERE (lo IS NULL OR hi IS NULL OR lo < hi) AND (off = 0 OR lim = 20);
SELECT count(*) AS shapes FROM shapes;
 shapes 
--------
   2016
(1 row)

CREATE FUNCTION shape_sql(s shapes) RETURNS text LANGUAGE sql AS $$
	SELECT format('SELECT %1$s AS k FROM @ WHERE %2$s ORDER BY %1$s %3$s %4$s LIMIT %5$s OFFSET %6$s', s.col,
		concat_ws(' AND ', CASE WHEN s.lo IS NOT NULL THEN format('%s >= %s', s.col, quant(s.col, s.ty, s.lo)) END,
						   CASE WHEN s.hi IS NOT NULL THEN format('%s <= %s', s.col, quant(s.col, s.ty, s.hi)) END, 'true'),
		s.dir, s.nl, s.lim, s.off)
$$;
-- a sweep checks the shapes whose hash with the stage falls in a 1 / per share: each stage another share
CREATE FUNCTION sweep(stage int, per int) RETURNS TABLE (same bigint, shapes bigint) LANGUAGE sql AS
$$ SELECT count(*) FILTER (WHERE same(shape_sql(s))), count(*) FROM shapes s WHERE hashtext(s::text || stage) % per = 0 $$;
SELECT * FROM sweep(1, 4);
 same | shapes 
------+--------
  516 |    516
(1 row)

SELECT count(*) FILTER (WHERE same(format('SELECT %1$s AS k FROM @ WHERE %1$s >= %2$s AND %1$s <= %3$s ORDER BY %1$s', s.col, quant(s.col, s.ty, s.lo), quant(s.col, s.ty, s.hi)))) AS ranges_whole, count(*) AS n
FROM shapes s WHERE lo IS NOT NULL AND hi IS NOT NULL AND dir = 'ASC' AND nl = 'NULLS LAST' AND lim = 1 AND off = 0;
 ranges_whole | n  
--------------+----
           35 | 35
(1 row)

-- a range or count across the middle is answered by the order, and a bound inside a bracket is the same row as the table's
SELECT global_order('SELECT ts AS k FROM t WHERE ts >= TIMESTAMP ''2026-04-01'' ORDER BY ts DESC LIMIT 20') AS a_range_at_the_end;
 a_range_at_the_end 
--------------------
 t
(1 row)

SELECT same('SELECT ts AS k FROM @ WHERE ts BETWEEN TIMESTAMP ''2026-04-01'' AND TIMESTAMP ''2026-04-03'' ORDER BY ts') AS a_range_in_the_middle;
 a_range_in_the_middle 
-----------------------
 t
(1 row)

SELECT (SELECT count(*) FROM t WHERE ts BETWEEN TIMESTAMP '2026-04-01' AND TIMESTAMP '2026-05-01') = (SELECT count(*) FROM p WHERE ts BETWEEN TIMESTAMP '2026-04-01' AND TIMESTAMP '2026-05-01') AS count_same;
 count_same 
------------
 t
(1 row)

SELECT same('SELECT dup AS k FROM @ ORDER BY dup LIMIT 700') AS ties_asc, same('SELECT dup AS k FROM @ ORDER BY dup DESC LIMIT 700') AS ties_desc;
 ties_asc | ties_desc 
----------+-----------
 t        | t
(1 row)

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

-- the pages are all-visible after a VACUUM: an OFFSET takes the entries it throws away off the front of the order without reading their keys (sift_gord_skip), where the buckets say they come first
VACUUM t;
SELECT * FROM sweep(2, 10);
 same | shapes 
------+--------
  209 |    209
(1 row)

-- an update that changes a key is not a HOT update (the column is in the index): the old version stays in the segment and the new one is in the write buffer
UPDATE t SET ts = ts + INTERVAL '3 days', s = s + 1 WHERE id % 13 = 0;
-- one that does not (pad is not in the order, still covered): the chain keeps the key
UPDATE t SET pad = 1 WHERE id % 5 = 0;
-- an aborted update and an aborted insert leave versions nobody sees
BEGIN;
UPDATE t SET ts = ts + INTERVAL '1 year' WHERE id % 3 = 0;
INSERT INTO t SELECT 20000 + i, TIMESTAMP '2026-01-01', TIMESTAMPTZ '2026-01-01', DATE '2026-01-01', 1, 1, 1, 0, 1000000000 FROM generate_series(1, 200) i;
ROLLBACK;
DROP TABLE p;
CREATE TABLE p AS SELECT * FROM t;
SELECT * FROM sweep(3, 10);
 same | shapes 
------+--------
  199 |    199
(1 row)

-- pruned HOT chains: the root of a chain is a redirect
VACUUM t;
SELECT * FROM sweep(4, 10);
 same | shapes 
------+--------
  184 |    184
(1 row)

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

-- the pages are all-visible but a few (a row updated in every tenth page, one deleted in every twentieth; no VACUUM has visited them): the skip of an OFFSET counts the entries of the other pages
-- and has the heap confirm those of these, whose rows it counts if the snapshot sees them; an aborted update leaves versions nobody sees on pages of its own
ALTER TABLE t SET (autovacuum_enabled = off);
UPDATE t SET pad = 3 WHERE (ctid::text::point)[0]::int % 10 = 0 AND id % 9 = 0;
DELETE FROM t WHERE (ctid::text::point)[0]::int % 20 = 3 AND id % 11 = 0;
BEGIN;
UPDATE t SET ts = ts + INTERVAL '30 days', s = s - 1 WHERE (ctid::text::point)[0]::int % 10 = 5 AND id % 13 = 0;
ROLLBACK;
DROP TABLE p;
CREATE TABLE p AS SELECT * FROM t;
SELECT * FROM sweep(5, 10);
 same | shapes 
------+--------
  158 |    158
(1 row)

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

-- dead rows: the segment has a row bulkdelete cleared, whose address is listed so that the heap is not asked for its key, and a new row may take the address of a dead one
DELETE FROM t WHERE ts < TIMESTAMP '2026-02-01' OR id % 17 = 0;
VACUUM t;
INSERT INTO t SELECT 30000 + i, TIMESTAMP '2026-01-01' + random() * 300 * INTERVAL '1 day', TIMESTAMPTZ '2026-01-01 00:00:00+00' + random() * 300 * INTERVAL '1 day', DATE '2026-01-01' + (random() * 300)::int,
	(random() * 30000)::int - 15000, (random() * 1000000000000)::bigint - 500000000000, (random() * 20)::int, 0, (random() * 2000)::int * 1000000000::bigint FROM generate_series(1, 700) i;
SELECT global_order('SELECT ts AS k FROM t ORDER BY ts LIMIT 20 OFFSET 700') AS an_offset_in_a_dirty_segment, global_order('SELECT ts AS k FROM t ORDER BY ts DESC LIMIT 20 OFFSET 3000') AS a_desc_offset_in_a_dirty_segment;
 an_offset_in_a_dirty_segment | a_desc_offset_in_a_dirty_segment 
------------------------------+----------------------------------
 t                            | t
(1 row)

DROP TABLE p;
CREATE TABLE p AS SELECT * FROM t;
SELECT * FROM sweep(6, 10);
 same | shapes 
------+--------
  209 |    209
(1 row)

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

-- a merge and a rewrite write the order again, compact again
SELECT sift.col_promote('t_ix') >= 0 AS promoted;
 promoted 
----------
 t
(1 row)

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

SELECT format, count(*) AS segments, sum(rows) AS rows FROM sift.col_segments('t_ix') WHERE kind = 'immutable' GROUP BY format ORDER BY format;
 format | segments | rows 
--------+----------+------
     41 |        1 | 7092
(1 row)

SELECT * FROM sweep(7, 10);
 same | shapes 
------+--------
  228 |    228
(1 row)

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

-- REINDEX writes it as the option says: whole again
ALTER INDEX t_ix SET (order_layout = 'whole');
REINDEX INDEX t_ix;
SELECT format, count(*) AS segments, sum(rows) AS rows FROM sift.col_segments('t_ix') WHERE kind = 'immutable' GROUP BY format ORDER BY format;
 format | segments | rows 
--------+----------+------
     38 |        1 | 7092
(1 row)

SELECT * FROM sweep(8, 10);
 same | shapes 
------+--------
  206 |    206
(1 row)

ALTER INDEX t_ix SET (order_layout = 'compact');
REINDEX INDEX t_ix;
SELECT format, count(*) AS segments, sum(rows) AS rows FROM sift.col_segments('t_ix') WHERE kind = 'immutable' GROUP BY format ORDER BY format;
 format | segments | rows 
--------+----------+------
     41 |        1 | 7092
(1 row)

SELECT * FROM sweep(9, 10);
 same | shapes 
------+--------
  191 |    191
(1 row)

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

-- auto chooses a chunk at a time: the columns of scattered keys are compact, the heavy ties (tie, dup) stay whole, and a column can be both
ALTER INDEX t_ix RESET (order_layout);
REINDEX INDEX t_ix;
SELECT format, count(*) AS segments, sum(rows) AS rows FROM sift.col_segments('t_ix') WHERE kind = 'immutable' GROUP BY format ORDER BY format;
 format | segments | rows 
--------+----------+------
     41 |        1 | 7092
(1 row)

SELECT * FROM sweep(10, 10);
 same | shapes 
------+--------
  205 |    205
(1 row)

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

DROP FUNCTION global_order(text), same(text), quant(text, text, float8), sweep(int, int), shape_sql(shapes);
DROP TABLE shapes, p, t;
DROP EXTENSION pg_sift_helpers;
DROP EXTENSION pg_sift;