-- The histogram of an ordered-set aggregate whose values are nearly all distinct is an array of pairs, not a hash (agg/osa.c): the percentiles agree with the
-- normal plan when the values are distinct, when they repeat from some row on, with NULLs, a FILTER and a mode() on the same argument (which keeps the hash),
-- and the array that outgrows work_mem moves to the sort.
-- (percentiles that are not a multiple of 1/4 are left out of percentile_cont: the server's own interpolation may be built with fused multiply-adds, which this library is not)
CREATE EXTENSION pg_sift;
CREATE EXTENSION pg_sift_helpers;
SET max_parallel_workers_per_gather = 0;
SET work_mem = '64MB';
SET sift.agg_force = on;
CREATE TABLE f (id int, g int, x float8, b bigint, r float8, mix float8, nx float8) WITH (fillfactor = 20, autovacuum_enabled = false);
INSERT INTO f SELECT i, i % 7,
	(i * 7919 % 100003) / 8.0,
	(i::bigint * 104729 % 1000003) - 500000,
	(i % 9)::float8,
	CASE WHEN i <= 12000 THEN (i * 31 % 100003)::float8 ELSE (i % 50)::float8 END,
	CASE WHEN i % 13 = 0 THEN NULL ELSE (i * 17 % 100019) / 3.0 END
FROM generate_series(1, 70000) i;
CREATE INDEX f_col ON f USING sift_col (id, g, x, b, r, mix, nx);
NOTICE:  sift_col index "f_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('f_col');
VACUUM ANALYZE f;
CREATE FUNCTION fl_rows(q text, push bool) RETURNS jsonb[] LANGUAGE sql AS $$ SELECT sift_helpers.rows_agg_as_jsonb_array(q, push) $$;
CREATE FUNCTION fl_same(q text) RETURNS text LANGUAGE plpgsql AS $$
DECLARE a jsonb[]; b jsonb[];
BEGIN
	a := fl_rows(q, true);
	b := fl_rows(q, false);
	RETURN CASE WHEN a IS NOT DISTINCT FROM b THEN 'same ' || coalesce(cardinality(a), 0) ELSE 'differs: ' || a::text || ' vs ' || b::text END;
END $$;
-- the plan's lines of the aggregate: whether the ordered sets were flat or spilled
CREATE FUNCTION fl_plan(q text) RETURNS text LANGUAGE plpgsql AS $$
DECLARE l text; r text := '';
BEGIN
	PERFORM set_config('sift.enable_agg', 'true', true);
	FOR l IN EXECUTE 'EXPLAIN (ANALYZE, COSTS off, TIMING off, BUFFERS off) ' || q LOOP
		IF l LIKE '%Custom Scan (SiftAgg)%' THEN r := r || 'scan '; END IF;
		IF l ~ 'ordered sets of distinct values' THEN r := r || 'flat '; END IF;
		IF l ~ 'ordered sets spilled' THEN r := r || 'spilled '; END IF;
	END LOOP;
	RETURN trim(r);
END $$;
CREATE TABLE fl_q (n int, q text);
INSERT INTO fl_q VALUES
	(1, 'SELECT g AS k, percentile_cont(0.5) WITHIN GROUP (ORDER BY x) AS a, percentile_disc(0.9) WITHIN GROUP (ORDER BY x) AS b FROM f GROUP BY g'),
	(2, 'SELECT g AS k, percentile_cont(ARRAY[0.25, 0.5, 0.75]) WITHIN GROUP (ORDER BY x) AS a, percentile_disc(ARRAY[0.25, 0.75]) WITHIN GROUP (ORDER BY x DESC) AS b FROM f GROUP BY g'),
	(3, 'SELECT g AS k, percentile_disc(0.5) WITHIN GROUP (ORDER BY b) AS a, percentile_cont(0.25) WITHIN GROUP (ORDER BY b::float8) AS c FROM f GROUP BY g'),
	(4, 'SELECT g AS k, percentile_cont(0.5) WITHIN GROUP (ORDER BY r) AS a, percentile_disc(0.7) WITHIN GROUP (ORDER BY r) AS b FROM f GROUP BY g'),
	(5, 'SELECT g AS k, percentile_cont(0.5) WITHIN GROUP (ORDER BY mix) AS a, percentile_disc(0.95) WITHIN GROUP (ORDER BY mix) AS b FROM f GROUP BY g'),
	(6, 'SELECT g AS k, percentile_cont(0.5) WITHIN GROUP (ORDER BY nx) AS a, percentile_disc(0.1) WITHIN GROUP (ORDER BY nx) AS b FROM f GROUP BY g'),
	(7, 'SELECT g AS k, percentile_cont(0.5) WITHIN GROUP (ORDER BY x) FILTER (WHERE id % 3 <> 0) AS a, percentile_disc(0.5) WITHIN GROUP (ORDER BY x) FILTER (WHERE id > 50000) AS b FROM f GROUP BY g'),
	(8, 'SELECT g AS k, mode() WITHIN GROUP (ORDER BY mix) AS a, percentile_disc(0.5) WITHIN GROUP (ORDER BY mix) AS b, percentile_cont(0.5) WITHIN GROUP (ORDER BY mix) AS c FROM f GROUP BY g'),
	(9, 'SELECT 1 AS k, percentile_cont(0.5) WITHIN GROUP (ORDER BY x) AS a, percentile_cont(0.75) WITHIN GROUP (ORDER BY x) AS b FROM f'),
	(10, 'SELECT id % 500 AS k, percentile_cont(0.5) WITHIN GROUP (ORDER BY x) AS a, percentile_disc(0.5) WITHIN GROUP (ORDER BY x) AS b FROM f GROUP BY id % 500'),
	(11, 'SELECT g AS k, percentile_cont(0.5) WITHIN GROUP (ORDER BY x) AS a, percentile_disc(0.25) WITHIN GROUP (ORDER BY x) AS b FROM f WHERE id <= 8300 GROUP BY g');
SELECT n, fl_plan(q) AS plan, fl_same(q) AS same FROM fl_q ORDER BY n;
 n  |   plan    |   same   
----+-----------+----------
  1 | scan flat | same 7
  2 | scan flat | same 7
  3 | scan flat | same 7
  4 | scan      | same 7
  5 | scan flat | same 7
  6 | scan flat | same 7
  7 | scan flat | same 7
  8 | scan      | same 7
  9 | scan flat | same 1
 10 | scan flat | same 500
 11 | scan flat | same 7
(11 rows)

-- the array outgrows work_mem: the values move to the sort and the rows are the same (256kB: the hash does, before it could turn into an array)
SET work_mem = '256kB';
SELECT n, fl_plan(q) AS plan, fl_same(q) AS same FROM fl_q WHERE n IN (1, 3, 6, 9) ORDER BY n;
 n |     plan     |  same  
---+--------------+--------
 1 | scan spilled | same 7
 3 | scan spilled | same 7
 6 | scan spilled | same 7
 9 | scan spilled | same 1
(4 rows)

SET work_mem = '1MB';
SELECT n, fl_plan(q) AS plan, fl_same(q) AS same FROM fl_q WHERE n IN (1, 3, 5, 6) ORDER BY n;
 n |       plan        |  same  
---+-------------------+--------
 1 | scan flat spilled | same 7
 3 | scan flat spilled | same 7
 5 | scan flat spilled | same 7
 6 | scan flat         | same 7
(4 rows)

-- the 70000 pairs of the array are past the 65536 that 1MB holds
SELECT n, fl_plan(q) AS plan, fl_same(q) AS same FROM fl_q WHERE n = 9;
 n |       plan        |  same  
---+-------------------+--------
 9 | scan flat spilled | same 1
(1 row)

DROP TABLE fl_q;
DROP FUNCTION fl_rows(text, bool), fl_same(text), fl_plan(text);
DROP TABLE f;
DROP EXTENSION pg_sift_helpers;
DROP EXTENSION pg_sift;