-- A scan under an ORDER BY or a window emits its groups in the order the parent sorts by, so that no Sort is put above it: the distinct values of each key are
-- sorted once with the comparator of the pathkey (its sort operator, collation and nulls order) and the groups by the ranks. The rows are the normal plan's in the same
-- order (the key columns, row by row), for text, numeric, date, float and jsonb keys, DESC, NULLS FIRST and LAST, a prefix of the group keys, and with workers.
CREATE EXTENSION pg_sift;
SET seq_page_cost = 10000;
SET sift.agg_preagg = off;
SET parallel_setup_cost = 0;
SET parallel_tuple_cost = 0;
SET min_parallel_table_scan_size = 0;
SET min_parallel_index_scan_size = 0;
SET extra_float_digits = 0;
CREATE TABLE o (id int, a text, b numeric(8,2), c date, e int, f float8, x float8) WITH (fillfactor = 20, autovacuum_enabled = false);
INSERT INTO o
SELECT i, CASE WHEN i % 17 = 0 THEN NULL ELSE 'k' || (i * 7 % 301) END, (i % 40) / 4.0, DATE '2024-01-01' + (i % 30), CASE WHEN i % 11 = 0 THEN NULL ELSE i % 6 END,
       CASE i % 9 WHEN 0 THEN 0.0 WHEN 1 THEN -0.0 WHEN 2 THEN 'NaN' WHEN 3 THEN NULL WHEN 4 THEN 'Infinity' WHEN 5 THEN '-Infinity' ELSE i % 5 - 2.5 END, i * 0.1
FROM generate_series(1, 30000) i;
CREATE INDEX o_col ON o USING sift_col (id, a, b, c, e, f, x);
NOTICE:  sift_col index "o_col": 1 automatic choice (rollup_columns), 1 advice (track_changes)
DETAIL:  advice: track_changes = the table has no one-column primary key; rollup_columns = c, e
HINT:  Reasons, costs and how to turn each off: SELECT * FROM sift.index_choices('o_col');
VACUUM ANALYZE o;
-- jsonb keys (a dimension built from columns): many distinct values, so the ranks come from the byte keys (gorder.c) and the check of the comparator; numbers that are one double
-- (9007199254740992 and 9007199254740993), integers and fractions, strings of both cases, with accents and empty, true, false and null elements, nested arrays and objects
CREATE TABLE oj (id int, a int, b text, c numeric, d bool, e int) WITH (fillfactor = 20, autovacuum_enabled = false);
INSERT INTO oj
SELECT i, CASE WHEN i % 23 = 0 THEN NULL ELSE i % 19 - 9 END,
       (ARRAY['a', 'A', 'b', 'B', 'é', 'e', '', 'z', 'Z', '10', '9', '_', 'ab', 'aB', 'Ab'])[1 + i % 15],
       (ARRAY[9007199254740992, 9007199254740993, 9007199254740994, 0, -1.5, 2.25, 1e20, -1e20, 0.1, 0.5])[1 + i % 10]::numeric,
       CASE i % 3 WHEN 0 THEN true WHEN 1 THEN false END, i % 3
FROM generate_series(1, 30000) i;
CREATE INDEX oj_col ON oj USING sift_col (id, a, b, c, d, e);
NOTICE:  sift_col index "oj_col": 1 automatic choice (rollup_columns), 1 advice (track_changes)
DETAIL:  advice: track_changes = the table has no one-column primary key; rollup_columns = d, e
HINT:  Reasons, costs and how to turn each off: SELECT * FROM sift.index_choices('oj_col');
VACUUM ANALYZE oj;
-- five keys of about 12,000 values each: their ranks take more than 64 bits together, so the groups are sorted by the tuple of ranks and not by one packed integer
CREATE TABLE ow (id int, k1 int, k2 int, k3 int, k4 int, k5 int) WITH (fillfactor = 20, autovacuum_enabled = false);
INSERT INTO ow SELECT i, (i * 3) % 12007, (i * 5) % 12011, CASE WHEN i % 29 = 0 THEN NULL ELSE (i * 7) % 12013 END, (i * 11) % 12037, (i * 13) % 12041 FROM generate_series(1, 12000) i;
CREATE INDEX ow_col ON ow USING sift_col (id, k1, k2, k3, k4, k5);
NOTICE:  sift_col index "ow_col": 1 advice (track_changes)
DETAIL:  advice: track_changes = the table has no one-column primary key
HINT:  Reasons, costs and how to turn each off: SELECT * FROM sift.index_choices('ow_col');
VACUUM ANALYZE ow;
-- the key columns (the first k of the select list) of the statement, in the order it gives them, as a checksum
CREATE FUNCTION o_keys(q text, k int, push bool, workers int) RETURNS text LANGUAGE plpgsql AS $$
DECLARE r text;
BEGIN
	PERFORM set_config('sift.enable_agg', push::text, true);
	PERFORM set_config('max_parallel_workers_per_gather', workers::text, true);
	EXECUTE format('SELECT md5(string_agg(row(%s)::text, E''\n'')) FROM (%s) q', CASE WHEN k = 0 THEN 'q.*' ELSE (SELECT string_agg('q.c' || i, ', ') FROM generate_series(1, k) i) END, q) INTO r;
	RETURN r;
END $$;
-- the plan has the node and no Sort above it; the plan is serial (the ordered groups are offered to a serial scan, and a parallel scan under a Sort can cost less on a few thousand groups, which depends on the workers the server allows)
CREATE FUNCTION o_plan(q text) RETURNS text LANGUAGE plpgsql AS $$
DECLARE l text; scan bool := false; srt bool := false;
BEGIN
	PERFORM set_config('sift.enable_agg', 'true', true);
	PERFORM set_config('max_parallel_workers_per_gather', '0', true);
	FOR l IN EXECUTE 'EXPLAIN (COSTS OFF) ' || q LOOP
		scan := scan OR l LIKE '%Custom Scan (SiftAgg)%';
		srt := srt OR l LIKE '%Sort%';
	END LOOP;
	RETURN CASE WHEN NOT scan THEN 'no scan' WHEN srt THEN 'sorted above' ELSE 'ordered' END;
END $$;
CREATE FUNCTION o_ordered(q text) RETURNS bool LANGUAGE plpgsql AS $$
DECLARE l text; r bool := false;
BEGIN
	PERFORM set_config('sift.enable_agg', 'true', true);
	PERFORM set_config('max_parallel_workers_per_gather', '0', true);
	FOR l IN EXECUTE 'EXPLAIN (ANALYZE, COSTS OFF, TIMING OFF, SUMMARY OFF, BUFFERS OFF) ' || q LOOP
		r := r OR l LIKE '%order keys)%';
	END LOOP;
	RETURN r;
END $$;
CREATE TABLE o_q (n int, k int, q text, want text);
INSERT INTO o_q VALUES
	(1, 2, 'SELECT a AS c1, c AS c2, count(*) AS n FROM o GROUP BY a, c ORDER BY a DESC NULLS LAST, c', 'ordered'),
	(2, 2, 'SELECT c AS c1, a AS c2, count(*) AS n FROM o GROUP BY a, c ORDER BY c DESC, a NULLS FIRST', 'ordered'),
	(3, 1, 'SELECT b AS c1, e AS c2, count(*) AS n FROM o GROUP BY b, e ORDER BY b DESC', 'ordered'),
	(4, 3, 'SELECT b AS c1, e AS c2, c AS c3, round(sum(x)::numeric, 2) AS s FROM o GROUP BY b, e, c ORDER BY b, e DESC NULLS LAST, c DESC', 'ordered'),
	(5, 1, 'SELECT f AS c1, count(*) AS n FROM o GROUP BY f ORDER BY f', 'ordered'),
	(6, 1, 'SELECT f AS c1, count(*) AS n FROM o GROUP BY f ORDER BY f DESC NULLS FIRST', 'ordered'),
	(7, 1, 'SELECT a COLLATE "C" AS c1, count(*) AS n FROM o GROUP BY a ORDER BY a COLLATE "C" DESC', 'ordered'),
	(8, 0, 'SELECT a AS c1, c AS c2, count(*) AS n, lag(count(*)) OVER (PARTITION BY a ORDER BY c DESC) AS l FROM o GROUP BY a, c', 'ordered'),
	(9, 2, 'SELECT e AS c1, b AS c2, count(*) AS n FROM o GROUP BY e, b ORDER BY e, b, count(*)', 'sorted above'),
	-- the window is in the query level that reads the groups (an inlined CTE, a sub-select), the keys in another order than the GROUP BY
	(11, 0, 'WITH g AS (SELECT a AS c1, c AS c2, e AS c3, count(*) AS n FROM o GROUP BY a, c, e) SELECT c1, c3, c2, n, lag(n) OVER (PARTITION BY c1, c3 ORDER BY c2 DESC) AS l FROM g', 'ordered'),
	(12, 0, 'SELECT * FROM (SELECT b AS c1, c AS c2, count(*) AS n FROM o GROUP BY b, c) q ORDER BY c1 DESC NULLS FIRST, c2', 'ordered'),
	-- a column of the sub-select that is a constant, a COALESCE of a key (the NULL group sorts as the constant), keys in the window's order
	(14, 0, 'WITH g AS (SELECT COALESCE(a, ''zz'') AS c1, NULL::date AS c2, e AS c3, c AS c4, count(*) AS n FROM o GROUP BY a, e, c) SELECT c1, c2, c3, c4, n, count(*) OVER (PARTITION BY c2, c3 ORDER BY c1 DESC, c4) AS w FROM g', 'ordered'),
	-- a group key that is itself a COALESCE (of two columns, of a column and a constant, of three columns): ordered by the whole key, NULL groups and DESC NULLS FIRST included
	(40, 0, 'WITH g AS (SELECT COALESCE(a, c::text) AS c1, e AS c2, count(*) AS n FROM o GROUP BY COALESCE(a, c::text), e) SELECT c1, c2, n, lag(n) OVER (PARTITION BY c1 ORDER BY c2 DESC NULLS FIRST) AS l FROM g', 'ordered'),
	(41, 0, 'SELECT * FROM (SELECT COALESCE(b, e) AS c1, a AS c2, count(*) AS n FROM o GROUP BY COALESCE(b, e), a) q ORDER BY c1 DESC NULLS FIRST, c2', 'ordered'),
	(42, 0, 'SELECT * FROM (SELECT COALESCE(a, ''zz'') AS c1, e AS c2, count(*) AS n FROM o GROUP BY COALESCE(a, ''zz''), e) q ORDER BY c1 COLLATE "C" DESC, c2 NULLS FIRST', 'ordered'),
	(43, 0, 'SELECT * FROM (SELECT COALESCE(a, c::text, ''x'') AS c1, COALESCE(e, 7) AS c2, COALESCE(b, 0) AS c3, count(*) AS n FROM o GROUP BY COALESCE(a, c::text, ''x''), COALESCE(e, 7), COALESCE(b, 0)) q ORDER BY c1, c2 DESC, c3', 'ordered'),
	(44, 0, 'WITH g AS (SELECT COALESCE(a, c::text) AS c1, COALESCE(NULLIF(e, 3), b::int) AS c2, c AS c3, count(*) AS n FROM o GROUP BY 1, 2, 3) SELECT c1, c2, c3, n, row_number() OVER (PARTITION BY c1, c2 ORDER BY c3 DESC) AS r FROM g', 'ordered'),
	-- the parent groups with an aggregate of its own that sorts (its ORDER BY or DISTINCT): PostgreSQL sorts for it and can not hash, the scan gives that order
	(45, 0, 'WITH g AS (SELECT a AS c1, c AS c2, e AS c3, count(*) AS n FROM o GROUP BY a, c, e) SELECT c1, string_agg(c3::text || ''/'' || n, '','' ORDER BY c2 DESC, c3 NULLS FIRST) AS s FROM g GROUP BY c1', 'ordered'),
	(46, 0, 'SELECT c1, count(DISTINCT c3) AS d, array_agg(c2 ORDER BY c2) AS arr FROM (SELECT b AS c1, c AS c2, e AS c3, count(*) AS n FROM o GROUP BY b, c, e) q GROUP BY c1', 'ordered'),
	(47, 0, 'SELECT string_agg(c1 || ''/'' || c2::text, '','' ORDER BY c1 DESC NULLS LAST, c2) AS s FROM (SELECT a AS c1, c AS c2, count(*) AS n FROM o GROUP BY a, c) q', 'ordered'),
	-- many groups (30,000) with a key of as many distinct values: the values of an integer or date key are sorted by the value with no call for a compare and the groups by a radix
	-- sort, which is much less than the Sort they replace: the scan is ordered where the cost said the Sort was cheaper
	(50, 2, 'SELECT id AS c1, a AS c2, count(*) AS n FROM o GROUP BY id, a ORDER BY a, id DESC', 'ordered'),
	(51, 0, 'WITH g AS (SELECT a AS c1, id AS c2, count(*) AS n FROM o GROUP BY a, id) SELECT c1, c2, n, lag(n) OVER (PARTITION BY c1 ORDER BY c2 DESC) AS l FROM g', 'ordered'),
	(52, 3, 'SELECT c AS c1, id AS c2, a AS c3, count(*) AS n FROM o GROUP BY c, id, a ORDER BY c DESC NULLS LAST, id, a', 'ordered'),
	-- grouping sets: a key a set leaves out is NULL in its groups, and sorts as NULL (a window in the query that reads them, an ORDER BY of the parent, a COALESCE of a key)
	(20, 0, 'WITH g AS (SELECT b AS c1, c AS c2, count(*) AS n FROM o GROUP BY GROUPING SETS ((b, c), (b))) SELECT c1, c2, n, lag(n) OVER (PARTITION BY c1 ORDER BY c2 DESC) AS l FROM g', 'ordered'),
	(21, 0, 'SELECT * FROM (SELECT b AS c1, c AS c2, count(*) AS n FROM o GROUP BY ROLLUP (b, c)) q ORDER BY c1 DESC NULLS FIRST, c2', 'ordered'),
	(22, 0, 'SELECT * FROM (SELECT COALESCE(b, -1) AS c1, c AS c2, count(*) AS n FROM o GROUP BY GROUPING SETS ((b, c), (c), (b))) q ORDER BY c2 NULLS LAST, c1 DESC', 'ordered'),
	-- the ORDER BY of the query that groups by sets: the keys a set leaves out are NULL, in the position the sort puts NULL
	(24, 2, 'SELECT b AS c1, c AS c2, count(*) AS n FROM o GROUP BY ROLLUP (b, c) ORDER BY b NULLS FIRST, c NULLS FIRST', 'ordered'),
	(25, 2, 'SELECT a AS c1, e AS c2, count(*) AS n FROM o GROUP BY GROUPING SETS ((a, e), (a), (e), ()) ORDER BY a DESC NULLS LAST, e NULLS FIRST', 'ordered'),
	(26, 1, 'SELECT c AS c1, b AS c2, count(*) AS n FROM o GROUP BY GROUPING SETS ((c, b), (c), (b)) ORDER BY c DESC NULLS FIRST', 'ordered'),
	(27, 0, 'SELECT b AS c1, c AS c2, count(*) AS n, lag(count(*)) OVER (PARTITION BY b ORDER BY c DESC) AS l FROM o GROUP BY GROUPING SETS ((b, c), (b))', 'ordered'),
	-- the NULL group and the grand total tie in the ORDER BY: the check reads the key column only (the order of the two rows is the executor's, and changed in PostgreSQL 19)
	(28, 1, 'SELECT a AS c1, count(*) AS n FROM o GROUP BY ROLLUP (a) ORDER BY a NULLS FIRST', 'ordered'),
	(23, 0, 'WITH g AS (SELECT b AS c1, c AS c2, a AS c3, count(*) AS n FROM o WHERE a IS NOT NULL GROUP BY GROUPING SETS ((b, c, a), (b, c))) SELECT c1, c2, c3, n, rank() OVER (PARTITION BY c1 ORDER BY c2, c3 NULLS FIRST) AS r FROM g', 'ordered'),
	-- jsonb keys: the rank of the 3,000 distinct values, ascending, descending, nulls first, with a window on top
	(30, 0, 'SELECT jsonb_build_array(a, b, c, d) AS c1, count(*) AS n FROM oj GROUP BY jsonb_build_array(a, b, c, d) ORDER BY 1', 'ordered'),
	(31, 0, 'SELECT jsonb_build_array(a, b, c, d) AS c1, count(*) AS n FROM oj GROUP BY jsonb_build_array(a, b, c, d) ORDER BY 1 DESC', 'ordered'),
	(32, 0, 'SELECT jsonb_build_array(jsonb_build_object(''k'', c), jsonb_build_array(b, d)) AS c1, e AS c2, count(*) AS n FROM oj GROUP BY 1, 2 ORDER BY c1 DESC NULLS FIRST, c2', 'ordered'),
	(33, 0, 'WITH g AS (SELECT to_jsonb(b) AS c1, to_jsonb(c) AS c2, jsonb_build_object(''a'', a, ''d'', d) AS c3, count(*) AS n FROM oj GROUP BY to_jsonb(b), to_jsonb(c), jsonb_build_object(''a'', a, ''d'', d)) SELECT c1, c2, c3, n, lag(n) OVER (PARTITION BY c3 ORDER BY c1 DESC, c2) AS l FROM g', 'ordered'),
	-- keys whose ranks do not fit 64 bits together
	(60, 5, 'SELECT k1 AS c1, k2 AS c2, k3 AS c3, k4 AS c4, k5 AS c5, count(*) AS n FROM ow GROUP BY k1, k2, k3, k4, k5 ORDER BY k1, k2 DESC, k3 NULLS FIRST, k4, k5 DESC', 'ordered'),
	(61, 5, 'SELECT k1 AS c1, k2 AS c2, k3 AS c3, k4 AS c4, k5 AS c5, count(*) AS n FROM ow GROUP BY k1, k2, k3, k4, k5 ORDER BY k5, k4 DESC, k3, k2, k1 DESC NULLS LAST', 'ordered'),
	-- a CTE read twice or materialized is a scan of its own: the Sort stays
	(13, 0, 'WITH g AS MATERIALIZED (SELECT a AS c1, c AS c2, count(*) AS n FROM o GROUP BY a, c) SELECT c1, c2, n, lag(n) OVER (PARTITION BY c1 ORDER BY c2) AS l FROM g', 'sorted above'),
	-- an order the keys do not decide (an Incremental Sort on the prefix, or a Sort): a Sort stays above
	(10, 1, 'SELECT a AS c1, count(*) AS n FROM o GROUP BY a ORDER BY count(*) DESC, a', 'sorted above');
SELECT n, o_plan(q) = want AS plan FROM o_q ORDER BY n;
 n  | plan 
----+------
  1 | t
  2 | t
  3 | t
  4 | t
  5 | t
  6 | t
  7 | t
  8 | t
  9 | t
 10 | t
 11 | t
 12 | t
 13 | t
 14 | t
 20 | t
 21 | t
 22 | t
 23 | t
 24 | t
 25 | t
 26 | t
 27 | t
 28 | t
 30 | t
 31 | t
 32 | t
 33 | t
 40 | t
 41 | t
 42 | t
 43 | t
 44 | t
 45 | t
 46 | t
 47 | t
 50 | t
 51 | t
 52 | t
 60 | t
 61 | t
(40 rows)

-- the scan emits its groups in an order where a Sort above it was asked for; a parent that hashes (no sorting aggregate) gets them unordered
SELECT n, o_ordered(q) AS group_order FROM o_q WHERE n IN (1, 40, 45, 46, 47) ORDER BY n;
 n  | group_order 
----+-------------
  1 | t
 40 | t
 45 | t
 46 | t
 47 | t
(5 rows)

-- rows in the normal plan's order (key columns), with no worker and with three
SELECT n, o_keys(q, k, true, 0) = o_keys(q, k, false, 0) AS serial, o_keys(q, k, true, 3) = o_keys(q, k, false, 0) AS workers FROM o_q WHERE want = 'ordered' ORDER BY n;
 n  | serial | workers 
----+--------+---------
  1 | t      | t
  2 | t      | t
  3 | t      | t
  4 | t      | t
  5 | t      | t
  6 | t      | t
  7 | t      | t
  8 | t      | t
 11 | t      | t
 12 | t      | t
 14 | t      | t
 20 | t      | t
 21 | t      | t
 22 | t      | t
 23 | t      | t
 24 | t      | t
 25 | t      | t
 26 | t      | t
 27 | t      | t
 28 | t      | t
 30 | t      | t
 31 | t      | t
 32 | t      | t
 33 | t      | t
 40 | t      | t
 41 | t      | t
 42 | t      | t
 43 | t      | t
 44 | t      | t
 45 | t      | t
 46 | t      | t
 47 | t      | t
 50 | t      | t
 51 | t      | t
 52 | t      | t
 60 | t      | t
 61 | t      | t
(37 rows)

-- the groups are the same rows
CREATE FUNCTION o_rows(q text, push bool) RETURNS text LANGUAGE plpgsql AS $$
DECLARE r text;
BEGIN
	PERFORM set_config('sift.enable_agg', push::text, true);
	PERFORM set_config('max_parallel_workers_per_gather', '0', true);
	EXECUTE format('SELECT md5(string_agg(q::text, E''\n'' ORDER BY q::text)) FROM (%s) q', q) INTO r;
	RETURN r;
END $$;
SELECT n, o_rows(q, true) = o_rows(q, false) AS rows FROM o_q ORDER BY n;
 n  | rows 
----+------
  1 | t
  2 | t
  3 | t
  4 | t
  5 | t
  6 | t
  7 | t
  8 | t
  9 | t
 10 | t
 11 | t
 12 | t
 13 | t
 14 | t
 20 | t
 21 | t
 22 | t
 23 | t
 24 | t
 25 | t
 26 | t
 27 | t
 28 | t
 30 | t
 31 | t
 32 | t
 33 | t
 40 | t
 41 | t
 42 | t
 43 | t
 44 | t
 45 | t
 46 | t
 47 | t
 50 | t
 51 | t
 52 | t
 60 | t
 61 | t
(40 rows)

-- a parent that hashes gets the groups unordered, and the same rows
SELECT o_ordered('SELECT c1, sum(n) AS s FROM (SELECT a AS c1, c AS c2, count(*) AS n FROM o GROUP BY a, c) q GROUP BY c1') AS hashing_parent_ordered,
       o_rows('SELECT c1, sum(n) AS s FROM (SELECT a AS c1, c AS c2, count(*) AS n FROM o GROUP BY a, c) q GROUP BY c1', true) = o_rows('SELECT c1, sum(n) AS s FROM (SELECT a AS c1, c AS c2, count(*) AS n FROM o GROUP BY a, c) q GROUP BY c1', false) AS rows;
 hashing_parent_ordered | rows 
------------------------+------
 f                      | t
(1 row)

-- adversarial keys: strings that sort differently by collation (case, accents, punctuation, digits, the empty string), numeric with NaN, floats with -0, NaN and infinities,
-- dates and timestamps with infinity, booleans, negative bigints, NULLs everywhere; every key, both directions, both nulls orders, alone and with a second key that breaks the ties
CREATE TABLE o2 (id int, s text, n numeric, f float8, d date, t timestamptz, b bool, i8 bigint, g int) WITH (fillfactor = 20, autovacuum_enabled = false);
INSERT INTO o2
SELECT i, (ARRAY['a', 'A', 'b', 'B', 'a1', 'a10', 'a2', '_x', ' ', '', 'é', 'e', 'z', 'Z', '1', '10', '2'])[1 + i % 17] || CASE WHEN i % 5 = 0 THEN '' ELSE '' END,
       (ARRAY['0', '-1', '1.5', '1e20', 'NaN', '-0.001', '100', '7', '-1e10'])[1 + i % 9]::numeric,
       (ARRAY[0.0, -0.0, 1.5, -2.5, 'NaN', 'Infinity', '-Infinity', 3.0, 1e300, -1e300])[1 + i % 10],
       (ARRAY[DATE '2024-01-01', DATE '2023-12-31', 'infinity', '-infinity', DATE '1999-06-15', DATE '2024-02-29'])[1 + i % 6],
       (ARRAY[TIMESTAMPTZ '2024-01-01 00:00:00+00', 'infinity', '-infinity', TIMESTAMPTZ '2000-03-04 05:06:07+00', TIMESTAMPTZ '1970-01-01 00:00:00+00'])[1 + i % 5],
       (ARRAY[true, false])[1 + i % 2],
       (ARRAY[0, -1, 9223372036854775807, -9223372036854775807, 42, -42, 1000000007])[1 + i % 7]::bigint,
       i % 4
FROM generate_series(1, 30000) i;
UPDATE o2 SET s = NULL WHERE id % 31 = 0;
UPDATE o2 SET n = NULL WHERE id % 29 = 0;
UPDATE o2 SET f = NULL WHERE id % 23 = 0;
UPDATE o2 SET d = NULL WHERE id % 19 = 0;
UPDATE o2 SET t = NULL WHERE id % 37 = 0;
UPDATE o2 SET b = NULL WHERE id % 41 = 0;
UPDATE o2 SET i8 = NULL WHERE id % 43 = 0;
-- no dead version is left for the index build (a session of another test with an older snapshot makes the planner leave the index out: indcheckxmin)
CREATE TEMP TABLE o2_rows AS SELECT * FROM o2 ORDER BY ctid;
TRUNCATE o2;
INSERT INTO o2 SELECT * FROM o2_rows;
DROP TABLE o2_rows;
CREATE INDEX o2_col ON o2 USING sift_col (id, s, n, f, d, t, b, i8, g);
NOTICE:  sift_col index "o2_col": 1 automatic choice (rollup_columns), 1 advice (track_changes)
DETAIL:  advice: track_changes = the table has no one-column primary key; rollup_columns = b, g
HINT:  Reasons, costs and how to turn each off: SELECT * FROM sift.index_choices('o2_col');
VACUUM ANALYZE o2;
-- a collation that is not the byte order, when the server has one
SELECT coalesce((SELECT collname FROM pg_collation WHERE collname IN ('en_US.utf8', 'und-x-icu') ORDER BY collname LIMIT 1), 'C') AS coll \gset
CREATE FUNCTION o2_check(col text, second text, dir text, nulls text, coll text) RETURNS TABLE (plan text, order_same bool, rows_same bool) LANGUAGE plpgsql AS $$
DECLARE q text; a text; b text;
BEGIN
	q := format('SELECT %1$s %5$s AS c1, %2$s AS c2, count(*) AS cnt FROM o2 GROUP BY %1$s, %2$s ORDER BY %1$s %5$s %3$s NULLS %4$s, %2$s DESC NULLS FIRST',
				col, second, dir, nulls, CASE WHEN coll = '' THEN '' ELSE 'COLLATE "' || coll || '"' END);
	plan := o_plan(q);
	order_same := o_keys(q, 2, true, 0) = o_keys(q, 2, false, 0) AND o_keys(q, 2, true, 3) = o_keys(q, 2, false, 0);
	rows_same := o_rows(q, true) = o_rows(q, false);
	RETURN NEXT;
END $$;
SELECT col, second, dir, nulls, (o2_check(col, second, dir, nulls, '')).*
FROM unnest(ARRAY['s', 'n', 'f', 'd', 't', 'b', 'i8']) col, unnest(ARRAY['g', 'b']) second, unnest(ARRAY['ASC', 'DESC']) dir, unnest(ARRAY['FIRST', 'LAST']) nulls
WHERE col <> second ORDER BY 1, 2, 3, 4;
 col | second | dir  | nulls |  plan   | order_same | rows_same 
-----+--------+------+-------+---------+------------+-----------
 b   | g      | ASC  | FIRST | ordered | t          | t
 b   | g      | ASC  | LAST  | ordered | t          | t
 b   | g      | DESC | FIRST | ordered | t          | t
 b   | g      | DESC | LAST  | ordered | t          | t
 d   | b      | ASC  | FIRST | ordered | t          | t
 d   | b      | ASC  | LAST  | ordered | t          | t
 d   | b      | DESC | FIRST | ordered | t          | t
 d   | b      | DESC | LAST  | ordered | t          | t
 d   | g      | ASC  | FIRST | ordered | t          | t
 d   | g      | ASC  | LAST  | ordered | t          | t
 d   | g      | DESC | FIRST | ordered | t          | t
 d   | g      | DESC | LAST  | ordered | t          | t
 f   | b      | ASC  | FIRST | ordered | t          | t
 f   | b      | ASC  | LAST  | ordered | t          | t
 f   | b      | DESC | FIRST | ordered | t          | t
 f   | b      | DESC | LAST  | ordered | t          | t
 f   | g      | ASC  | FIRST | ordered | t          | t
 f   | g      | ASC  | LAST  | ordered | t          | t
 f   | g      | DESC | FIRST | ordered | t          | t
 f   | g      | DESC | LAST  | ordered | t          | t
 i8  | b      | ASC  | FIRST | ordered | t          | t
 i8  | b      | ASC  | LAST  | ordered | t          | t
 i8  | b      | DESC | FIRST | ordered | t          | t
 i8  | b      | DESC | LAST  | ordered | t          | t
 i8  | g      | ASC  | FIRST | ordered | t          | t
 i8  | g      | ASC  | LAST  | ordered | t          | t
 i8  | g      | DESC | FIRST | ordered | t          | t
 i8  | g      | DESC | LAST  | ordered | t          | t
 n   | b      | ASC  | FIRST | ordered | t          | t
 n   | b      | ASC  | LAST  | ordered | t          | t
 n   | b      | DESC | FIRST | ordered | t          | t
 n   | b      | DESC | LAST  | ordered | t          | t
 n   | g      | ASC  | FIRST | ordered | t          | t
 n   | g      | ASC  | LAST  | ordered | t          | t
 n   | g      | DESC | FIRST | ordered | t          | t
 n   | g      | DESC | LAST  | ordered | t          | t
 s   | b      | ASC  | FIRST | ordered | t          | t
 s   | b      | ASC  | LAST  | ordered | t          | t
 s   | b      | DESC | FIRST | ordered | t          | t
 s   | b      | DESC | LAST  | ordered | t          | t
 s   | g      | ASC  | FIRST | ordered | t          | t
 s   | g      | ASC  | LAST  | ordered | t          | t
 s   | g      | DESC | FIRST | ordered | t          | t
 s   | g      | DESC | LAST  | ordered | t          | t
 t   | b      | ASC  | FIRST | ordered | t          | t
 t   | b      | ASC  | LAST  | ordered | t          | t
 t   | b      | DESC | FIRST | ordered | t          | t
 t   | b      | DESC | LAST  | ordered | t          | t
 t   | g      | ASC  | FIRST | ordered | t          | t
 t   | g      | ASC  | LAST  | ordered | t          | t
 t   | g      | DESC | FIRST | ordered | t          | t
 t   | g      | DESC | LAST  | ordered | t          | t
(52 rows)

-- text under the server's non-byte collation, and under C, a prefix of the keys (ties left to the second key's order only when it is in the ORDER BY)
SELECT dir, nulls, (o2_check('s', 'g', dir, nulls, :'coll')).*, (o2_check('s', 'g', dir, nulls, 'C')).rows_same AS c_rows
FROM unnest(ARRAY['ASC', 'DESC']) dir, unnest(ARRAY['FIRST', 'LAST']) nulls ORDER BY 1, 2;
 dir  | nulls |  plan   | order_same | rows_same | c_rows 
------+-------+---------+------------+-----------+--------
 ASC  | FIRST | ordered | t          | t         | t
 ASC  | LAST  | ordered | t          | t         | t
 DESC | FIRST | ordered | t          | t         | t
 DESC | LAST  | ordered | t          | t         | t
(4 rows)

-- values that compare equal but print differently (numeric 1.0 and 1.00, float -0 and 0, text equal under a nondeterministic collation): PostgreSQL merges them in one group,
-- so must the ordered scan, in the place the sort puts them. Which of the equal spellings a group prints is arbitrary in PostgreSQL itself (its group key is the value of
-- the first row of the group that it met, and the plans meet rows in another order), so the groups are compared by a canonical form of the key and their count
DO $$ BEGIN
	CREATE COLLATION o3_ci (provider = icu, locale = 'und-u-ks-level2', deterministic = false);
EXCEPTION WHEN OTHERS THEN
	CREATE COLLATION o3_ci FROM "C";
END $$;
CREATE TABLE o3 (id int, n numeric, f float8, s text COLLATE o3_ci, g int) WITH (fillfactor = 20, autovacuum_enabled = false);
INSERT INTO o3
SELECT i, (ARRAY['1.0', '1.00', '2', '2.000', '0', '0.0', '-0.0', '3.10', '3.1'])[1 + i % 9]::numeric, (ARRAY[0.0, -0.0, 1.5, -1.5])[1 + i % 4],
       (ARRAY['a', 'A', 'b', 'B', 'á', 'Á', 'c'])[1 + i % 7], i % 3
FROM generate_series(1, 20000) i;
UPDATE o3 SET n = NULL WHERE id % 13 = 0;
-- no dead version is left for the index build (a session of another test with an older snapshot makes the planner leave the index out: indcheckxmin)
CREATE TEMP TABLE o3_rows AS SELECT * FROM o3 ORDER BY ctid;
TRUNCATE o3;
INSERT INTO o3 SELECT * FROM o3_rows;
DROP TABLE o3_rows;
CREATE INDEX o3_col ON o3 USING sift_col (id, n, f, s, g);
NOTICE:  sift_col index "o3_col": 1 automatic choice (rollup_columns), 1 advice (track_changes)
DETAIL:  advice: track_changes = the table has no one-column primary key; rollup_columns = s, g
HINT:  Reasons, costs and how to turn each off: SELECT * FROM sift.index_choices('o3_col');
VACUUM ANALYZE o3;
CREATE FUNCTION o3_check(col text, canon text, dir text) RETURNS TABLE (plan text, same_groups bool) LANGUAGE plpgsql AS $$
DECLARE q text; a text; b text;
BEGIN
	q := format('SELECT %1$s AS c1, count(*) AS c2 FROM o3 GROUP BY %1$s ORDER BY %1$s %2$s', col, dir);
	plan := o_plan(q);
	same_groups := true;
	FOR w IN 0..3 LOOP
		PERFORM set_config('max_parallel_workers_per_gather', w::text, true);
		PERFORM set_config('sift.enable_agg', 'true', true);
		EXECUTE format('SELECT md5(string_agg(coalesce((%s)::text, ''null'') || '':'' || c2, '','')) FROM (%s) q', replace(canon, 'c1', 'q.c1'), q) INTO a;
		PERFORM set_config('sift.enable_agg', 'false', true);
		EXECUTE format('SELECT md5(string_agg(coalesce((%s)::text, ''null'') || '':'' || c2, '','')) FROM (%s) q', replace(canon, 'c1', 'q.c1'), q) INTO b;
		same_groups := same_groups AND a = b;
	END LOOP;
	RETURN NEXT;
END $$;
SELECT col, dir, (o3_check(col, canon, dir)).*
FROM (VALUES ('n', 'c1::float8'), ('f', 'c1 + 0'), ('s', 'translate(c1 COLLATE "C", ''ABÁ'', ''abá'')')) k(col, canon), unnest(ARRAY['ASC', 'DESC']) dir ORDER BY 1, 2;
 col | dir  |  plan   | same_groups 
-----+------+---------+-------------
 f   | ASC  | ordered | t
 f   | DESC | ordered | t
 n   | ASC  | ordered | t
 n   | DESC | ordered | t
 s   | ASC  | ordered | t
 s   | DESC | ordered | t
(6 rows)

DROP TABLE o_q, o, o2, o3, oj, ow;
DROP COLLATION o3_ci;
DROP FUNCTION o_keys(text, int, bool, int), o_plan(text), o_ordered(text), o_rows(text, bool), o2_check(text, text, text, text, text), o3_check(text, text, text);
DROP EXTENSION pg_sift;