-- The plan of the statements the b-tree plan answers faster. A list of 20 to 1,000 rows of one entity (ORDER BY .. LIMIT over WHERE entity = k) read the rows from
-- the heap in the order of the key, and the b-tree on (entity, key) reads the same pages without the sorted runs: measured, the top-N scan took 1.9 to 2.4 times its
-- instructions and 2.0 to 2.5 times its cycles (pgbench -c 4: 8,300 against 15,500 statements a second), while the cost model priced the fetch at half a page
-- (a fifth of the b-tree plan's cost with sorted runs); where a b-tree gives the first key of the order the price now has the pages of its plan as a floor.
-- `plan` is where the rows come from: the b-tree ("native") or the extension ("sift"). The lists a b-tree cannot give in order (another key, a filter on a column it does not hold, the whole table) stay with the extension: they take 4 to 80 times fewer instructions.
CREATE EXTENSION pg_sift;
SET max_parallel_workers_per_gather = 0;
SET client_min_messages = warning;
SET sift.async_maintenance = off;
CREATE TABLE events (id int PRIMARY KEY, entity int NOT NULL, d date NOT NULL, kind int NOT NULL, amount int NOT NULL) WITH (autovacuum_enabled = false);
-- 500 entities of 160 to 20,000 rows: the number of an entity is the cube of a uniform value
INSERT INTO events SELECT g, 1 + (500 * power((hashint4(g) & 2147483647) / 2147483648.0, 3))::int, date '2020-01-01' + (hashint4(g + 1) & 2147483647) % 2000, (hashint4(g + 2) & 2147483647) % 20, g % 1000
FROM generate_series(1, 200000) g;
CREATE INDEX events_entity_d ON events (entity, d);
CREATE INDEX events_col ON events USING sift_col (id, entity, d, kind, amount) WITH (key_columns = 'entity', key_order = 'entity, d');
VACUUM (FREEZE, ANALYZE) events;
CREATE FUNCTION plan(q text) RETURNS text LANGUAGE plpgsql AS $$
DECLARE line text;
BEGIN
	FOR line IN EXECUTE 'EXPLAIN (COSTS OFF) ' || q LOOP
		IF line ~ 'Custom Scan \(SiftAgg\)' THEN RETURN 'sift'; END IF;
	END LOOP;
	RETURN 'native';
END $$;
SELECT entity, size, lim, plan(format('SELECT id, d, amount FROM events WHERE entity = %s ORDER BY d DESC, id LIMIT %s', entity, lim)) AS plan
FROM (SELECT entity, count(*) AS size FROM events WHERE entity IN (1, 2, 10, 40, 120, 300) GROUP BY entity) e, (VALUES (20), (200), (1000)) l(lim)
ORDER BY entity, lim;
 entity | size  | lim  |  plan  
--------+-------+------+--------
      1 | 19998 |   20 | native
      1 | 19998 |  200 | native
      1 | 19998 | 1000 | native
      2 |  8770 |   20 | native
      2 |  8770 |  200 | native
      2 |  8770 | 1000 | native
     10 |  1959 |   20 | native
     10 |  1959 |  200 | native
     10 |  1959 | 1000 | native
     40 |   727 |   20 | native
     40 |   727 |  200 | native
     40 |   727 | 1000 | native
    120 |   354 |   20 | native
    120 |   354 |  200 | native
    120 |   354 | 1000 | native
    300 |   163 |   20 | native
    300 |   163 |  200 | native
    300 |   163 | 1000 | native
(18 rows)

SELECT q, plan(q) AS plan FROM (VALUES
	('SELECT id, d, amount FROM events ORDER BY amount DESC, id LIMIT 10'),
	('SELECT id, d, amount FROM events ORDER BY d DESC, id LIMIT 200'),
	('SELECT id, d, amount FROM events WHERE kind = 3 ORDER BY amount DESC, id LIMIT 50'),
	('SELECT id, d, amount FROM events WHERE entity < 50 ORDER BY amount DESC, id LIMIT 100'),
	('SELECT id, d, amount FROM events ORDER BY amount DESC, id LIMIT 100 OFFSET 5000')) s(q);
                                           q                                           | plan 
---------------------------------------------------------------------------------------+------
 SELECT id, d, amount FROM events ORDER BY amount DESC, id LIMIT 10                    | sift
 SELECT id, d, amount FROM events ORDER BY d DESC, id LIMIT 200                        | sift
 SELECT id, d, amount FROM events WHERE kind = 3 ORDER BY amount DESC, id LIMIT 50     | sift
 SELECT id, d, amount FROM events WHERE entity < 50 ORDER BY amount DESC, id LIMIT 100 | sift
 SELECT id, d, amount FROM events ORDER BY amount DESC, id LIMIT 100 OFFSET 5000       | sift
(5 rows)

DROP FUNCTION plan(text);
DROP TABLE events;
DROP EXTENSION pg_sift;