-- ORDER BY a leaf, then columns the index does not hold LIMIT n: the scan gives the rows in the order of the first keys and the Sort above puts the others in order. -- The rows that tie with the last wanted one on the first keys must all be there: the heap has room for the ties the statistics say, and a group larger than that -- starts the scan again with a heap 16 times larger, twice, then keeps every row. Every query runs twice, the plain plan as the reference (sift.enable_agg off) -- and the pushed one, and the rows are compared in order, after the build, with rows in the write buffer, after updates (a tie group the statistics do not know), deletes and VACUUM. CREATE EXTENSION pg_sift; CREATE EXTENSION pg_sift_helpers; SET sift.async_maintenance = off; -- k: 400 values over 6000 rows (15 rows tie), NULLs; t: seconds, so that a few rows share one; w: the key the index does not hold; s: strings CREATE TABLE tt (id int PRIMARY KEY, k int, k2 int, t timestamp, w bigint, x double precision, s text, pad text DEFAULT repeat('x', 600)); CREATE FUNCTION tt_rows(lo int, hi int) RETURNS void LANGUAGE sql AS $$ INSERT INTO tt (id, k, k2, t, w, x, s) SELECT i, CASE WHEN i % 41 = 0 THEN NULL ELSE i % 400 END, i % 3, timestamp '2020-01-01' + (i / 4) * interval '1 second', CASE WHEN i % 37 = 0 THEN NULL ELSE (i * 7919) % 1000 END, (i % 17) - 8.0, md5((i % 211)::text) FROM generate_series(lo, hi) i $$; SELECT tt_rows(1, 6000); tt_rows --------- (1 row) CREATE INDEX tt_col ON tt USING sift_col (id, k, k2, t); NOTICE: sift_col index "tt_col": 1 automatic choice (track_changes) DETAIL: track_changes = id HINT: Reasons, costs and how to turn each off: SELECT * FROM sift.index_choices('tt_col'); VACUUM (ANALYZE) tt; CREATE FUNCTION tt_mode(pushed bool) RETURNS void LANGUAGE sql AS $$ SELECT sift_helpers.agg_mode(pushed) $$; -- 'same' / 'DIFFERENT' (the rows and their order), '+ties' when the pushed plan is the scan under a Sort (or '+all' when it keeps every row), '+restarts N' when it started again N times, and the number of rows CREATE FUNCTION tt_check(q text) RETURNS text LANGUAGE plpgsql AS $$ DECLARE n bigint; plan text := ''; line text; BEGIN DROP TABLE IF EXISTS tt_a, tt_b; PERFORM tt_mode(true); FOR line IN EXECUTE 'EXPLAIN (ANALYZE, COSTS OFF, TIMING OFF, SUMMARY OFF, BUFFERS OFF) ' || q LOOP plan := plan || line || E'\n'; END LOOP; EXECUTE 'CREATE TEMP TABLE tt_a AS SELECT row_number() OVER () AS pos, row_to_json(tq)::text AS r FROM (' || q || ') tq'; PERFORM tt_mode(false); EXECUTE 'CREATE TEMP TABLE tt_b AS SELECT row_number() OVER () AS pos, row_to_json(tq)::text AS r FROM (' || q || ') tq'; SELECT count(*) INTO n FROM ((SELECT pos, r FROM tt_a EXCEPT ALL SELECT pos, r FROM tt_b) UNION ALL (SELECT pos, r FROM tt_b EXCEPT ALL SELECT pos, r FROM tt_a)) d; RETURN CASE WHEN n = 0 THEN 'same' ELSE 'DIFFERENT' END || CASE WHEN plan ~ ' candidates' THEN '+ties' WHEN plan ~ ' restarts' THEN '+all' ELSE '' END || coalesce((SELECT ' restarts ' || (regexp_match(plan, '(\d+) restarts'))[1]), '') || ' ' || (SELECT count(*) FROM tt_b); END $$; CREATE TABLE tt_q (n serial, q text); INSERT INTO tt_q (q) VALUES ('SELECT id, k, w FROM tt ORDER BY k, w, id LIMIT 10'), ('SELECT id, k, w FROM tt ORDER BY k DESC, w, id LIMIT 10'), ('SELECT id, k, w FROM tt ORDER BY k, w DESC, id LIMIT 10'), ('SELECT id, k, w FROM tt ORDER BY k DESC, w DESC, id DESC LIMIT 10'), ('SELECT id, k, w FROM tt ORDER BY k NULLS FIRST, w NULLS FIRST, id LIMIT 10'), ('SELECT id, k, w FROM tt ORDER BY k DESC NULLS LAST, w DESC NULLS LAST, id LIMIT 10'), ('SELECT id, k, w FROM tt ORDER BY k NULLS FIRST, w DESC NULLS LAST, id LIMIT 40'), ('SELECT id, k, w FROM tt ORDER BY k, w, id LIMIT 10 OFFSET 7'), ('SELECT id, k, w FROM tt ORDER BY k, w, id LIMIT 100 OFFSET 30'), ('SELECT id, k, w FROM tt ORDER BY k, w, id LIMIT 1'), ('SELECT id, k, w FROM tt ORDER BY k, w, id LIMIT 5000'), ('SELECT id, k, w FROM tt WHERE k2 = 1 ORDER BY k, w, id LIMIT 10'), ('SELECT id, k, w FROM tt WHERE k BETWEEN 100 AND 300 AND k2 <> 2 ORDER BY k, w, id LIMIT 25'), ('SELECT id, k, w FROM tt WHERE k > 1000 ORDER BY k, w, id LIMIT 10'), ('SELECT id, k, t, w FROM tt ORDER BY k, t, w, id LIMIT 10'), ('SELECT id, k, t, w FROM tt ORDER BY t DESC, w, id LIMIT 10'), ('SELECT id, k, t, w FROM tt ORDER BY t, w DESC NULLS FIRST, id LIMIT 30'), ('SELECT id, k, t, w FROM tt ORDER BY k2, k, w, id LIMIT 10'), ('SELECT id, k, s FROM tt ORDER BY k, s, id LIMIT 10'), ('SELECT id, k, s FROM tt ORDER BY k, s COLLATE "C" DESC, id LIMIT 10'), ('SELECT id, k, x FROM tt ORDER BY k, x, id LIMIT 10'), ('SELECT id, k, w FROM tt ORDER BY k, (w % 7), id DESC LIMIT 10'), ('SELECT id, k, w FROM tt ORDER BY k, w * k2, id LIMIT 10'), ('SELECT id, k + 1 AS a, w FROM tt ORDER BY k, w, id LIMIT 10'), ('SELECT id FROM tt ORDER BY k, w, id LIMIT 10'), ('SELECT w, s FROM tt ORDER BY k, w, id LIMIT 10'), ('SELECT id, k, w FROM tt ORDER BY k, w * 1000 + id LIMIT 10'); CREATE FUNCTION tt_all() RETURNS TABLE (n int, result text, q text) LANGUAGE sql AS $$ SELECT tt_q.n, tt_check(tt_q.q), tt_q.q FROM tt_q ORDER BY tt_q.n $$; SELECT * FROM tt_all(); NOTICE: table "tt_a" does not exist, skipping NOTICE: table "tt_b" does not exist, skipping n | result | q ----+----------------+-------------------------------------------------------------------------------------------- 1 | same+ties 10 | SELECT id, k, w FROM tt ORDER BY k, w, id LIMIT 10 2 | same+ties 10 | SELECT id, k, w FROM tt ORDER BY k DESC, w, id LIMIT 10 3 | same+ties 10 | SELECT id, k, w FROM tt ORDER BY k, w DESC, id LIMIT 10 4 | same+ties 10 | SELECT id, k, w FROM tt ORDER BY k DESC, w DESC, id DESC LIMIT 10 5 | same+ties 10 | SELECT id, k, w FROM tt ORDER BY k NULLS FIRST, w NULLS FIRST, id LIMIT 10 6 | same+ties 10 | SELECT id, k, w FROM tt ORDER BY k DESC NULLS LAST, w DESC NULLS LAST, id LIMIT 10 7 | same+ties 40 | SELECT id, k, w FROM tt ORDER BY k NULLS FIRST, w DESC NULLS LAST, id LIMIT 40 8 | same+ties 10 | SELECT id, k, w FROM tt ORDER BY k, w, id LIMIT 10 OFFSET 7 9 | same+ties 100 | SELECT id, k, w FROM tt ORDER BY k, w, id LIMIT 100 OFFSET 30 10 | same+ties 1 | SELECT id, k, w FROM tt ORDER BY k, w, id LIMIT 1 11 | same+ties 5000 | SELECT id, k, w FROM tt ORDER BY k, w, id LIMIT 5000 12 | same+ties 10 | SELECT id, k, w FROM tt WHERE k2 = 1 ORDER BY k, w, id LIMIT 10 13 | same+ties 25 | SELECT id, k, w FROM tt WHERE k BETWEEN 100 AND 300 AND k2 <> 2 ORDER BY k, w, id LIMIT 25 14 | same+ties 0 | SELECT id, k, w FROM tt WHERE k > 1000 ORDER BY k, w, id LIMIT 10 15 | same+ties 10 | SELECT id, k, t, w FROM tt ORDER BY k, t, w, id LIMIT 10 16 | same+ties 10 | SELECT id, k, t, w FROM tt ORDER BY t DESC, w, id LIMIT 10 17 | same+ties 30 | SELECT id, k, t, w FROM tt ORDER BY t, w DESC NULLS FIRST, id LIMIT 30 18 | same+ties 10 | SELECT id, k, t, w FROM tt ORDER BY k2, k, w, id LIMIT 10 19 | same+ties 10 | SELECT id, k, s FROM tt ORDER BY k, s, id LIMIT 10 20 | same+ties 10 | SELECT id, k, s FROM tt ORDER BY k, s COLLATE "C" DESC, id LIMIT 10 21 | same+ties 10 | SELECT id, k, x FROM tt ORDER BY k, x, id LIMIT 10 22 | same+ties 10 | SELECT id, k, w FROM tt ORDER BY k, (w % 7), id DESC LIMIT 10 23 | same+ties 10 | SELECT id, k, w FROM tt ORDER BY k, w * k2, id LIMIT 10 24 | same+ties 10 | SELECT id, k + 1 AS a, w FROM tt ORDER BY k, w, id LIMIT 10 25 | same+ties 10 | SELECT id FROM tt ORDER BY k, w, id LIMIT 10 26 | same+ties 10 | SELECT w, s FROM tt ORDER BY k, w, id LIMIT 10 27 | same+ties 10 | SELECT id, k, w FROM tt ORDER BY k, w * 1000 + id LIMIT 10 (27 rows) -- rows in the write buffer SELECT tt_rows(6001, 6600); tt_rows --------- (1 row) SELECT * FROM tt_all(); n | result | q ----+----------------+-------------------------------------------------------------------------------------------- 1 | same+ties 10 | SELECT id, k, w FROM tt ORDER BY k, w, id LIMIT 10 2 | same+ties 10 | SELECT id, k, w FROM tt ORDER BY k DESC, w, id LIMIT 10 3 | same+ties 10 | SELECT id, k, w FROM tt ORDER BY k, w DESC, id LIMIT 10 4 | same+ties 10 | SELECT id, k, w FROM tt ORDER BY k DESC, w DESC, id DESC LIMIT 10 5 | same+ties 10 | SELECT id, k, w FROM tt ORDER BY k NULLS FIRST, w NULLS FIRST, id LIMIT 10 6 | same+ties 10 | SELECT id, k, w FROM tt ORDER BY k DESC NULLS LAST, w DESC NULLS LAST, id LIMIT 10 7 | same+ties 40 | SELECT id, k, w FROM tt ORDER BY k NULLS FIRST, w DESC NULLS LAST, id LIMIT 40 8 | same+ties 10 | SELECT id, k, w FROM tt ORDER BY k, w, id LIMIT 10 OFFSET 7 9 | same+ties 100 | SELECT id, k, w FROM tt ORDER BY k, w, id LIMIT 100 OFFSET 30 10 | same+ties 1 | SELECT id, k, w FROM tt ORDER BY k, w, id LIMIT 1 11 | same+ties 5000 | SELECT id, k, w FROM tt ORDER BY k, w, id LIMIT 5000 12 | same+ties 10 | SELECT id, k, w FROM tt WHERE k2 = 1 ORDER BY k, w, id LIMIT 10 13 | same+ties 25 | SELECT id, k, w FROM tt WHERE k BETWEEN 100 AND 300 AND k2 <> 2 ORDER BY k, w, id LIMIT 25 14 | same+ties 0 | SELECT id, k, w FROM tt WHERE k > 1000 ORDER BY k, w, id LIMIT 10 15 | same+ties 10 | SELECT id, k, t, w FROM tt ORDER BY k, t, w, id LIMIT 10 16 | same+ties 10 | SELECT id, k, t, w FROM tt ORDER BY t DESC, w, id LIMIT 10 17 | same+ties 30 | SELECT id, k, t, w FROM tt ORDER BY t, w DESC NULLS FIRST, id LIMIT 30 18 | same+ties 10 | SELECT id, k, t, w FROM tt ORDER BY k2, k, w, id LIMIT 10 19 | same+ties 10 | SELECT id, k, s FROM tt ORDER BY k, s, id LIMIT 10 20 | same+ties 10 | SELECT id, k, s FROM tt ORDER BY k, s COLLATE "C" DESC, id LIMIT 10 21 | same+ties 10 | SELECT id, k, x FROM tt ORDER BY k, x, id LIMIT 10 22 | same+ties 10 | SELECT id, k, w FROM tt ORDER BY k, (w % 7), id DESC LIMIT 10 23 | same+ties 10 | SELECT id, k, w FROM tt ORDER BY k, w * k2, id LIMIT 10 24 | same+ties 10 | SELECT id, k + 1 AS a, w FROM tt ORDER BY k, w, id LIMIT 10 25 | same+ties 10 | SELECT id FROM tt ORDER BY k, w, id LIMIT 10 26 | same+ties 10 | SELECT w, s FROM tt ORDER BY k, w, id LIMIT 10 27 | same+ties 10 | SELECT id, k, w FROM tt ORDER BY k, w * 1000 + id LIMIT 10 (27 rows) -- a tie group of 300 rows the statistics do not know: the first start's heap is too small, the second holds it UPDATE tt SET k = -5 WHERE id BETWEEN 1000 AND 1299; SELECT * FROM tt_all(); n | result | q ----+--------------------------+-------------------------------------------------------------------------------------------- 1 | same+ties restarts 1 10 | SELECT id, k, w FROM tt ORDER BY k, w, id LIMIT 10 2 | same+ties 10 | SELECT id, k, w FROM tt ORDER BY k DESC, w, id LIMIT 10 3 | same+ties restarts 1 10 | SELECT id, k, w FROM tt ORDER BY k, w DESC, id LIMIT 10 4 | same+ties 10 | SELECT id, k, w FROM tt ORDER BY k DESC, w DESC, id DESC LIMIT 10 5 | same+ties 10 | SELECT id, k, w FROM tt ORDER BY k NULLS FIRST, w NULLS FIRST, id LIMIT 10 6 | same+ties 10 | SELECT id, k, w FROM tt ORDER BY k DESC NULLS LAST, w DESC NULLS LAST, id LIMIT 10 7 | same+ties 40 | SELECT id, k, w FROM tt ORDER BY k NULLS FIRST, w DESC NULLS LAST, id LIMIT 40 8 | same+ties restarts 1 10 | SELECT id, k, w FROM tt ORDER BY k, w, id LIMIT 10 OFFSET 7 9 | same+ties restarts 1 100 | SELECT id, k, w FROM tt ORDER BY k, w, id LIMIT 100 OFFSET 30 10 | same+ties restarts 1 1 | SELECT id, k, w FROM tt ORDER BY k, w, id LIMIT 1 11 | same+ties 5000 | SELECT id, k, w FROM tt ORDER BY k, w, id LIMIT 5000 12 | same+ties restarts 1 10 | SELECT id, k, w FROM tt WHERE k2 = 1 ORDER BY k, w, id LIMIT 10 13 | same+ties 25 | SELECT id, k, w FROM tt WHERE k BETWEEN 100 AND 300 AND k2 <> 2 ORDER BY k, w, id LIMIT 25 14 | same+ties 0 | SELECT id, k, w FROM tt WHERE k > 1000 ORDER BY k, w, id LIMIT 10 15 | same+ties 10 | SELECT id, k, t, w FROM tt ORDER BY k, t, w, id LIMIT 10 16 | same+ties 10 | SELECT id, k, t, w FROM tt ORDER BY t DESC, w, id LIMIT 10 17 | same+ties 30 | SELECT id, k, t, w FROM tt ORDER BY t, w DESC NULLS FIRST, id LIMIT 30 18 | same+ties 10 | SELECT id, k, t, w FROM tt ORDER BY k2, k, w, id LIMIT 10 19 | same+ties restarts 1 10 | SELECT id, k, s FROM tt ORDER BY k, s, id LIMIT 10 20 | same+ties restarts 1 10 | SELECT id, k, s FROM tt ORDER BY k, s COLLATE "C" DESC, id LIMIT 10 21 | same+ties restarts 1 10 | SELECT id, k, x FROM tt ORDER BY k, x, id LIMIT 10 22 | same+ties restarts 1 10 | SELECT id, k, w FROM tt ORDER BY k, (w % 7), id DESC LIMIT 10 23 | same+ties restarts 1 10 | SELECT id, k, w FROM tt ORDER BY k, w * k2, id LIMIT 10 24 | same+ties restarts 1 10 | SELECT id, k + 1 AS a, w FROM tt ORDER BY k, w, id LIMIT 10 25 | same+ties restarts 1 10 | SELECT id FROM tt ORDER BY k, w, id LIMIT 10 26 | same+ties restarts 1 10 | SELECT w, s FROM tt ORDER BY k, w, id LIMIT 10 27 | same+ties restarts 1 10 | SELECT id, k, w FROM tt ORDER BY k, w * 1000 + id LIMIT 10 (27 rows) -- 1700 rows: neither start's heap holds them, the third keeps every row UPDATE tt SET k = -6 WHERE id BETWEEN 2000 AND 3699; SELECT * FROM tt_all(); n | result | q ----+--------------------------+-------------------------------------------------------------------------------------------- 1 | same+all restarts 2 10 | SELECT id, k, w FROM tt ORDER BY k, w, id LIMIT 10 2 | same+ties 10 | SELECT id, k, w FROM tt ORDER BY k DESC, w, id LIMIT 10 3 | same+all restarts 2 10 | SELECT id, k, w FROM tt ORDER BY k, w DESC, id LIMIT 10 4 | same+ties 10 | SELECT id, k, w FROM tt ORDER BY k DESC, w DESC, id DESC LIMIT 10 5 | same+ties 10 | SELECT id, k, w FROM tt ORDER BY k NULLS FIRST, w NULLS FIRST, id LIMIT 10 6 | same+ties 10 | SELECT id, k, w FROM tt ORDER BY k DESC NULLS LAST, w DESC NULLS LAST, id LIMIT 10 7 | same+ties 40 | SELECT id, k, w FROM tt ORDER BY k NULLS FIRST, w DESC NULLS LAST, id LIMIT 40 8 | same+all restarts 2 10 | SELECT id, k, w FROM tt ORDER BY k, w, id LIMIT 10 OFFSET 7 9 | same+ties restarts 1 100 | SELECT id, k, w FROM tt ORDER BY k, w, id LIMIT 100 OFFSET 30 10 | same+all restarts 2 1 | SELECT id, k, w FROM tt ORDER BY k, w, id LIMIT 1 11 | same+ties 5000 | SELECT id, k, w FROM tt ORDER BY k, w, id LIMIT 5000 12 | same+all restarts 2 10 | SELECT id, k, w FROM tt WHERE k2 = 1 ORDER BY k, w, id LIMIT 10 13 | same+ties 25 | SELECT id, k, w FROM tt WHERE k BETWEEN 100 AND 300 AND k2 <> 2 ORDER BY k, w, id LIMIT 25 14 | same+ties 0 | SELECT id, k, w FROM tt WHERE k > 1000 ORDER BY k, w, id LIMIT 10 15 | same+ties 10 | SELECT id, k, t, w FROM tt ORDER BY k, t, w, id LIMIT 10 16 | same+ties 10 | SELECT id, k, t, w FROM tt ORDER BY t DESC, w, id LIMIT 10 17 | same+ties 30 | SELECT id, k, t, w FROM tt ORDER BY t, w DESC NULLS FIRST, id LIMIT 30 18 | same+ties 10 | SELECT id, k, t, w FROM tt ORDER BY k2, k, w, id LIMIT 10 19 | same+all restarts 2 10 | SELECT id, k, s FROM tt ORDER BY k, s, id LIMIT 10 20 | same+all restarts 2 10 | SELECT id, k, s FROM tt ORDER BY k, s COLLATE "C" DESC, id LIMIT 10 21 | same+all restarts 2 10 | SELECT id, k, x FROM tt ORDER BY k, x, id LIMIT 10 22 | same+all restarts 2 10 | SELECT id, k, w FROM tt ORDER BY k, (w % 7), id DESC LIMIT 10 23 | same+all restarts 2 10 | SELECT id, k, w FROM tt ORDER BY k, w * k2, id LIMIT 10 24 | same+all restarts 2 10 | SELECT id, k + 1 AS a, w FROM tt ORDER BY k, w, id LIMIT 10 25 | same+all restarts 2 10 | SELECT id FROM tt ORDER BY k, w, id LIMIT 10 26 | same+all restarts 2 10 | SELECT w, s FROM tt ORDER BY k, w, id LIMIT 10 27 | same+all restarts 2 10 | SELECT id, k, w FROM tt ORDER BY k, w * 1000 + id LIMIT 10 (27 rows) -- deletes, then VACUUM, then new statistics DELETE FROM tt WHERE id % 5 = 0; SELECT * FROM tt_all(); n | result | q ----+--------------------------+-------------------------------------------------------------------------------------------- 1 | same+all restarts 2 10 | SELECT id, k, w FROM tt ORDER BY k, w, id LIMIT 10 2 | same+ties 10 | SELECT id, k, w FROM tt ORDER BY k DESC, w, id LIMIT 10 3 | same+all restarts 2 10 | SELECT id, k, w FROM tt ORDER BY k, w DESC, id LIMIT 10 4 | same+ties 10 | SELECT id, k, w FROM tt ORDER BY k DESC, w DESC, id DESC LIMIT 10 5 | same+ties 10 | SELECT id, k, w FROM tt ORDER BY k NULLS FIRST, w NULLS FIRST, id LIMIT 10 6 | same+ties 10 | SELECT id, k, w FROM tt ORDER BY k DESC NULLS LAST, w DESC NULLS LAST, id LIMIT 10 7 | same+ties 40 | SELECT id, k, w FROM tt ORDER BY k NULLS FIRST, w DESC NULLS LAST, id LIMIT 40 8 | same+all restarts 2 10 | SELECT id, k, w FROM tt ORDER BY k, w, id LIMIT 10 OFFSET 7 9 | same+ties restarts 1 100 | SELECT id, k, w FROM tt ORDER BY k, w, id LIMIT 100 OFFSET 30 10 | same+all restarts 2 1 | SELECT id, k, w FROM tt ORDER BY k, w, id LIMIT 1 11 | same+ties 5000 | SELECT id, k, w FROM tt ORDER BY k, w, id LIMIT 5000 12 | same+all restarts 2 10 | SELECT id, k, w FROM tt WHERE k2 = 1 ORDER BY k, w, id LIMIT 10 13 | same+ties 25 | SELECT id, k, w FROM tt WHERE k BETWEEN 100 AND 300 AND k2 <> 2 ORDER BY k, w, id LIMIT 25 14 | same+ties 0 | SELECT id, k, w FROM tt WHERE k > 1000 ORDER BY k, w, id LIMIT 10 15 | same+ties 10 | SELECT id, k, t, w FROM tt ORDER BY k, t, w, id LIMIT 10 16 | same+ties 10 | SELECT id, k, t, w FROM tt ORDER BY t DESC, w, id LIMIT 10 17 | same+ties 30 | SELECT id, k, t, w FROM tt ORDER BY t, w DESC NULLS FIRST, id LIMIT 30 18 | same+ties 10 | SELECT id, k, t, w FROM tt ORDER BY k2, k, w, id LIMIT 10 19 | same+all restarts 2 10 | SELECT id, k, s FROM tt ORDER BY k, s, id LIMIT 10 20 | same+all restarts 2 10 | SELECT id, k, s FROM tt ORDER BY k, s COLLATE "C" DESC, id LIMIT 10 21 | same+all restarts 2 10 | SELECT id, k, x FROM tt ORDER BY k, x, id LIMIT 10 22 | same+all restarts 2 10 | SELECT id, k, w FROM tt ORDER BY k, (w % 7), id DESC LIMIT 10 23 | same+all restarts 2 10 | SELECT id, k, w FROM tt ORDER BY k, w * k2, id LIMIT 10 24 | same+all restarts 2 10 | SELECT id, k + 1 AS a, w FROM tt ORDER BY k, w, id LIMIT 10 25 | same+all restarts 2 10 | SELECT id FROM tt ORDER BY k, w, id LIMIT 10 26 | same+all restarts 2 10 | SELECT w, s FROM tt ORDER BY k, w, id LIMIT 10 27 | same+all restarts 2 10 | SELECT id, k, w FROM tt ORDER BY k, w * 1000 + id LIMIT 10 (27 rows) VACUUM (ANALYZE) tt; SELECT * FROM tt_all(); n | result | q ----+--------------------------+-------------------------------------------------------------------------------------------- 1 | same+all restarts 2 10 | SELECT id, k, w FROM tt ORDER BY k, w, id LIMIT 10 2 | same+ties 10 | SELECT id, k, w FROM tt ORDER BY k DESC, w, id LIMIT 10 3 | same+all restarts 2 10 | SELECT id, k, w FROM tt ORDER BY k, w DESC, id LIMIT 10 4 | same+ties 10 | SELECT id, k, w FROM tt ORDER BY k DESC, w DESC, id DESC LIMIT 10 5 | same+ties 10 | SELECT id, k, w FROM tt ORDER BY k NULLS FIRST, w NULLS FIRST, id LIMIT 10 6 | same+ties 10 | SELECT id, k, w FROM tt ORDER BY k DESC NULLS LAST, w DESC NULLS LAST, id LIMIT 10 7 | same+ties 40 | SELECT id, k, w FROM tt ORDER BY k NULLS FIRST, w DESC NULLS LAST, id LIMIT 40 8 | same+all restarts 2 10 | SELECT id, k, w FROM tt ORDER BY k, w, id LIMIT 10 OFFSET 7 9 | same+ties restarts 1 100 | SELECT id, k, w FROM tt ORDER BY k, w, id LIMIT 100 OFFSET 30 10 | same+all restarts 2 1 | SELECT id, k, w FROM tt ORDER BY k, w, id LIMIT 1 11 | same+ties 5000 | SELECT id, k, w FROM tt ORDER BY k, w, id LIMIT 5000 12 | same+all restarts 2 10 | SELECT id, k, w FROM tt WHERE k2 = 1 ORDER BY k, w, id LIMIT 10 13 | same+ties 25 | SELECT id, k, w FROM tt WHERE k BETWEEN 100 AND 300 AND k2 <> 2 ORDER BY k, w, id LIMIT 25 14 | same+ties 0 | SELECT id, k, w FROM tt WHERE k > 1000 ORDER BY k, w, id LIMIT 10 15 | same+ties 10 | SELECT id, k, t, w FROM tt ORDER BY k, t, w, id LIMIT 10 16 | same+ties 10 | SELECT id, k, t, w FROM tt ORDER BY t DESC, w, id LIMIT 10 17 | same+ties 30 | SELECT id, k, t, w FROM tt ORDER BY t, w DESC NULLS FIRST, id LIMIT 30 18 | same+ties 10 | SELECT id, k, t, w FROM tt ORDER BY k2, k, w, id LIMIT 10 19 | same+all restarts 2 10 | SELECT id, k, s FROM tt ORDER BY k, s, id LIMIT 10 20 | same+all restarts 2 10 | SELECT id, k, s FROM tt ORDER BY k, s COLLATE "C" DESC, id LIMIT 10 21 | same+all restarts 2 10 | SELECT id, k, x FROM tt ORDER BY k, x, id LIMIT 10 22 | same+all restarts 2 10 | SELECT id, k, w FROM tt ORDER BY k, (w % 7), id DESC LIMIT 10 23 | same+all restarts 2 10 | SELECT id, k, w FROM tt ORDER BY k, w * k2, id LIMIT 10 24 | same+all restarts 2 10 | SELECT id, k + 1 AS a, w FROM tt ORDER BY k, w, id LIMIT 10 25 | same+all restarts 2 10 | SELECT id FROM tt ORDER BY k, w, id LIMIT 10 26 | same+all restarts 2 10 | SELECT w, s FROM tt ORDER BY k, w, id LIMIT 10 27 | same+all restarts 2 10 | SELECT id, k, w FROM tt ORDER BY k, w * 1000 + id LIMIT 10 (27 rows) -- limits lowered (a testing build): a heap that cannot hold the rows, or the keys, does not make a plan with the sort of every row; the keys that follow stay with the Sort above SET sift.test_limits = 'topn_rows=20'; SELECT * FROM tt_all() WHERE n IN (1, 7, 9, 15, 19); n | result | q ----+----------+-------------------------------------------------------------------------------- 1 | same 10 | SELECT id, k, w FROM tt ORDER BY k, w, id LIMIT 10 7 | same 40 | SELECT id, k, w FROM tt ORDER BY k NULLS FIRST, w DESC NULLS LAST, id LIMIT 40 9 | same 100 | SELECT id, k, w FROM tt ORDER BY k, w, id LIMIT 100 OFFSET 30 15 | same 10 | SELECT id, k, t, w FROM tt ORDER BY k, t, w, id LIMIT 10 19 | same 10 | SELECT id, k, s FROM tt ORDER BY k, s, id LIMIT 10 (5 rows) SET sift.test_limits = 'topn_keys=1'; SELECT * FROM tt_all() WHERE n IN (1, 7, 9, 15, 19); n | result | q ----+--------------------------+-------------------------------------------------------------------------------- 1 | same+all restarts 2 10 | SELECT id, k, w FROM tt ORDER BY k, w, id LIMIT 10 7 | same+ties 40 | SELECT id, k, w FROM tt ORDER BY k NULLS FIRST, w DESC NULLS LAST, id LIMIT 40 9 | same+ties restarts 1 100 | SELECT id, k, w FROM tt ORDER BY k, w, id LIMIT 100 OFFSET 30 15 | same 10 | SELECT id, k, t, w FROM tt ORDER BY k, t, w, id LIMIT 10 19 | same+all restarts 2 10 | SELECT id, k, s FROM tt ORDER BY k, s, id LIMIT 10 (5 rows) RESET sift.test_limits; -- the plan is chosen by the cost: a first key that few values share gets the scan (query 18, whose first key has three values of 2,000 rows each, takes it: 'same+ties' above), and sift.enable_topn turns it off SET sift.enable_agg = on; SET enable_seqscan = off; EXPLAIN (COSTS OFF) SELECT id, k, w FROM tt ORDER BY k, w, id LIMIT 10; QUERY PLAN ----------------------------------- Limit -> Incremental Sort Sort Key: k, w, id Presorted Key: k -> Custom Scan (SiftAgg) Index: tt_col Top-N: k (limit 10) (7 rows) RESET enable_seqscan; SET sift.enable_topn = off; EXPLAIN (COSTS OFF) SELECT id, k, w FROM tt ORDER BY k, w, id LIMIT 10; QUERY PLAN ---------------------------- Limit -> Sort Sort Key: k, w, id -> Seq Scan on tt (4 rows) RESET sift.enable_topn; -- more than 8,192 rows on a value of the first key (two values over 20,000 rows) keep the normal plan: the keys that follow are read from the heap for every row of the tie CREATE TABLE tt_big AS SELECT i AS id, i % 2 AS k, (i * 7919) % 1000 AS w FROM generate_series(1, 20000) i; CREATE INDEX tt_big_col ON tt_big USING sift_col (id, k); NOTICE: sift_col index "tt_big_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('tt_big_col'); ANALYZE tt_big; EXPLAIN (COSTS OFF) SELECT id, k, w FROM tt_big ORDER BY k, w, id LIMIT 10; QUERY PLAN -------------------------------- Limit -> Sort Sort Key: k, w, id -> Seq Scan on tt_big (4 rows) DROP TABLE tt_big; DROP TABLE tt_q; DROP FUNCTION tt_all(); DROP FUNCTION tt_check(text); DROP FUNCTION tt_mode(bool); DROP FUNCTION tt_rows(int, int); DROP TABLE tt; DROP EXTENSION pg_sift_helpers; DROP EXTENSION pg_sift;