-- The anti join over a small inner side (DESIGN.md §27, "The anti join over -- a small inner side"): -- -- SELECT count(*) FROM rows r WHERE -- AND NOT EXISTS (SELECT 1 FROM skip s WHERE s.a = r.k ... ) -- -- is the count of r's WHERE less the rows of it some row of s matches. The -- node runs s as its child, looks each distinct key of its rows up in a -- B-tree on r.k under the query's snapshot, tests every row found on r's own -- clauses and then on the join clauses, and subtracts the ones that pass - -- from the one row of a count, from each group of a GROUP BY, or from each -- cell of a count by cells. Every answer is checked against the same query -- with the pushdown off, as a multiset in both directions. \set VERBOSITY terse SET client_min_messages = warning; LOAD 'pg_lion'; CREATE EXTENSION IF NOT EXISTS pg_lion; RESET client_min_messages; -- VACUUM can only set all-visible once the commit record is on disk SET synchronous_commit = on; SET default_statistics_target = 1000; /* * lca() runs a query through the pushdown - every join method disabled, so * that core has no plan the node must beat on price - and again with the * pushdown off and sequential scans only, so that the reference reads no * lion posting set and no B-tree, and compares the two. It says whether the * node was used. */ CREATE FUNCTION lca(q text) RETURNS text LANGUAGE plpgsql AS $$ DECLARE ln text; how text := 'not pushed down'; nrows bigint; ndiff bigint; BEGIN PERFORM set_config('enable_hashjoin', 'off', true); PERFORM set_config('enable_mergejoin', 'off', true); PERFORM set_config('enable_nestloop', 'off', true); FOR ln IN EXECUTE 'EXPLAIN (COSTS OFF) ' || q LOOP IF ln LIKE '%Parallel Custom Scan (LionCount)%' THEN how := 'pushed down, parallel'; ELSIF ln LIKE '%Custom Scan (LionCount)%' AND how = 'not pushed down' THEN how := 'pushed down'; END IF; END LOOP; EXECUTE format('CREATE TEMP TABLE lca_on AS SELECT s::text AS r FROM (%s) s', q); PERFORM set_config('pg_lion.enable_count_pushdown', 'off', true); PERFORM set_config('enable_hashjoin', 'on', true); PERFORM set_config('enable_mergejoin', 'on', true); PERFORM set_config('enable_nestloop', 'on', true); PERFORM set_config('enable_bitmapscan', 'off', true); PERFORM set_config('enable_indexscan', 'off', true); PERFORM set_config('enable_indexonlyscan', 'off', true); EXECUTE format('CREATE TEMP TABLE lca_off AS SELECT s::text AS r FROM (%s) s', q); PERFORM set_config('enable_bitmapscan', 'on', true); PERFORM set_config('enable_indexscan', 'on', true); PERFORM set_config('enable_indexonlyscan', 'on', true); PERFORM set_config('pg_lion.enable_count_pushdown', 'on', true); EXECUTE 'SELECT count(*) FROM lca_off' INTO nrows; EXECUTE 'SELECT (SELECT count(*) FROM (TABLE lca_on EXCEPT ALL TABLE lca_off) a)' ' + (SELECT count(*) FROM (TABLE lca_off EXCEPT ALL TABLE lca_on) b)' INTO ndiff; EXECUTE 'DROP TABLE lca_on, lca_off'; IF ndiff <> 0 THEN RETURN format('MISMATCH: %s rows differ', ndiff); END IF; RETURN format('%s, %s rows', how, nrows); END $$; /* The answer itself, through the pushdown, joins disabled. */ CREATE FUNCTION lca_val(q text) RETURNS SETOF text LANGUAGE plpgsql AS $$ BEGIN PERFORM set_config('enable_hashjoin', 'off', true); PERFORM set_config('enable_mergejoin', 'off', true); PERFORM set_config('enable_nestloop', 'off', true); RETURN QUERY EXECUTE format('SELECT s::text FROM (%s) s', q); END $$; /* Which plan the cost model picks, with nothing disabled. */ CREATE FUNCTION lca_pick(q text) RETURNS text LANGUAGE plpgsql AS $$ DECLARE ln text; BEGIN FOR ln IN EXECUTE 'EXPLAIN (COSTS OFF) ' || q LOOP IF ln LIKE '%Custom Scan (LionCount)%' THEN RETURN 'pushed down'; END IF; END LOOP; RETURN 'not pushed down'; END $$; /* * A generic prepared plan, which keeps $n a Param, against the same with the * pushdown off. */ CREATE FUNCTION lca_prep(q text, args text) RETURNS text LANGUAGE plpgsql AS $$ DECLARE ln text; pushed boolean := false; nrows bigint; ndiff bigint; BEGIN PERFORM set_config('plan_cache_mode', 'force_generic_plan', true); PERFORM set_config('enable_hashjoin', 'off', true); PERFORM set_config('enable_mergejoin', 'off', true); PERFORM set_config('enable_nestloop', 'off', true); EXECUTE 'PREPARE lca_p_on AS ' || q; FOR ln IN EXECUTE 'EXPLAIN (COSTS OFF) EXECUTE lca_p_on(' || args || ')' LOOP IF ln LIKE '%Custom Scan (LionCount)%' THEN pushed := true; END IF; END LOOP; EXECUTE format('CREATE TEMP TABLE lca_on AS EXECUTE lca_p_on(%s)', args); PERFORM set_config('enable_hashjoin', 'on', true); PERFORM set_config('enable_mergejoin', 'on', true); PERFORM set_config('enable_nestloop', 'on', true); PERFORM set_config('pg_lion.enable_count_pushdown', 'off', true); PERFORM set_config('enable_bitmapscan', 'off', true); PERFORM set_config('enable_indexscan', 'off', true); PERFORM set_config('enable_indexonlyscan', 'off', true); EXECUTE 'PREPARE lca_p_off AS ' || q; EXECUTE format('CREATE TEMP TABLE lca_off AS EXECUTE lca_p_off(%s)', args); PERFORM set_config('enable_bitmapscan', 'on', true); PERFORM set_config('enable_indexscan', 'on', true); PERFORM set_config('enable_indexonlyscan', 'on', true); PERFORM set_config('pg_lion.enable_count_pushdown', 'on', true); EXECUTE 'DEALLOCATE lca_p_on'; EXECUTE 'DEALLOCATE lca_p_off'; EXECUTE 'SELECT count(*) FROM lca_off' INTO nrows; EXECUTE 'SELECT (SELECT count(*) FROM (TABLE lca_on EXCEPT ALL TABLE lca_off) a)' ' + (SELECT count(*) FROM (TABLE lca_off EXCEPT ALL TABLE lca_on) b)' INTO ndiff; EXECUTE 'DROP TABLE lca_on, lca_off'; IF ndiff <> 0 THEN RETURN format('MISMATCH: %s rows differ', ndiff); END IF; RETURN format('%s, %s rows', CASE WHEN pushed THEN 'pushed down' ELSE 'not pushed down' END, nrows); END $$; /* The anti join's counters in EXPLAIN ANALYZE, joins disabled. */ CREATE FUNCTION lca_counters(q text) RETURNS text LANGUAGE plpgsql AS $$ DECLARE ln text; out text := ''; BEGIN PERFORM set_config('enable_hashjoin', 'off', true); PERFORM set_config('enable_mergejoin', 'off', true); PERFORM set_config('enable_nestloop', 'off', true); FOR ln IN EXECUTE 'EXPLAIN (ANALYZE, COSTS OFF, TIMING OFF, SUMMARY OFF, BUFFERS OFF) ' || q LOOP IF btrim(split_part(ln, ':', 1)) IN ('Join Child Rows', 'Join Keys Looked Up', 'Join Rows Fetched', 'Join Rows Subtracted') THEN out := out || CASE WHEN out = '' THEN '' ELSE ', ' END || regexp_replace(btrim(ln), '^Join ', ''); END IF; END LOOP; RETURN out; END $$; /* * EXPLAIN, joins disabled, in a form every supported release prints the same * way: no "Disabled: true" lines, and no ".00" on a row count. */ CREATE FUNCTION lca_explain(q text, opts text DEFAULT 'COSTS OFF') RETURNS SETOF text LANGUAGE plpgsql AS $$ DECLARE l text; BEGIN PERFORM set_config('enable_hashjoin', 'off', true); PERFORM set_config('enable_mergejoin', 'off', true); PERFORM set_config('enable_nestloop', 'off', true); FOR l IN EXECUTE 'EXPLAIN (' || opts || ') ' || q LOOP CONTINUE WHEN l ~ '^\s*Disabled: true$'; RETURN NEXT regexp_replace(l, 'rows=(\d+)\.00 ', 'rows=\1 ', 'g'); END LOOP; END $$; /* * The table counted: 20000 rows. k has 400 values, some 50 rows each, and * NULL on every 37th row; kn is k without the NULLs, declared NOT NULL, and * kd the same as a numeric of two decimals; g has * 6 values and NULLs, y 7 and NULLs; z is 99 on exactly the rows of k = 5, * and 0..2 elsewhere; x has 10 values, for a WHERE of a tenth or a half. pad * makes the rows a few to a page. k, kn and kd have B-trees; x, g, z and (g, y) * lion indexes, and k one too, for count(k). */ CREATE TABLE lca_rows ( id int PRIMARY KEY, k int, kn int NOT NULL, kd numeric, g int, y int, z int NOT NULL, x int NOT NULL, pad text NOT NULL ) WITH (autovacuum_enabled = off); INSERT INTO lca_rows SELECT i, CASE WHEN i % 37 = 0 THEN NULL ELSE i % 400 END, i % 400, (i % 400)::numeric(6, 2), CASE WHEN i % 11 = 0 THEN NULL ELSE i % 6 END, CASE WHEN i % 13 = 0 THEN NULL ELSE i % 7 END, CASE WHEN i % 400 = 5 AND i % 37 <> 0 THEN 99 ELSE i % 3 END, (i / 400) % 10, repeat('p', 60) FROM generate_series(1, 20000) i; CREATE INDEX lca_rows_k ON lca_rows (k); CREATE INDEX lca_rows_kn ON lca_rows (kn); CREATE INDEX lca_rows_kd ON lca_rows (kd); CREATE INDEX lca_rows_x ON lca_rows USING lion (x); CREATE INDEX lca_rows_g ON lca_rows USING lion (g); CREATE INDEX lca_rows_z ON lca_rows USING lion (z); CREATE INDEX lca_rows_gy ON lca_rows USING lion (g, y); CREATE INDEX lca_rows_kl ON lca_rows USING lion (k); /* * The inner side: a few keys - two rows of key 2, a pair whose a and b * differ, NULL in a and in b, the key of the rows of z = 99, keys of no row * of lca_rows, and two rows of another f. c is a as int8. */ CREATE TABLE lca_skip (a int, b int, c int8, f int NOT NULL); INSERT INTO lca_skip VALUES (1, 1, 1, 0), (2, 2, 2, 0), (2, 2, 2, 0), (3, 4, 3, 0), (NULL, 6, NULL, 0), (6, NULL, 6, 0), (5, 5, 5, 0), (450, 450, 450, 0), (-1, -1, -1, 0), (7, 7, 7, 1), (8, 8, 8, 1); -- numeric keys, equal ones among them in other spellings CREATE TABLE lca_num (d numeric); INSERT INTO lca_num VALUES (1.0), (1.00), (1), (2.000), (2.5), (NULL); -- a second inner table, joined to the first inside the NOT EXISTS CREATE TABLE lca_tag (a int, tag text); INSERT INTO lca_tag VALUES (1, 'on'), (2, 'off'), (5, 'on'), (7, 'on'), (450, 'on'); VACUUM (FREEZE, ANALYZE) lca_rows, lca_skip, lca_num, lca_tag; -- ---------- 1. the plans ---------- SELECT * FROM lca_explain('SELECT count(*) FROM lca_rows r WHERE r.x = 3 AND NOT EXISTS (SELECT 1 FROM lca_skip s WHERE s.a = r.k AND s.f = 0)'); -- a GROUP BY, the two-clause form over one column, and an inner side that is a join SELECT * FROM lca_explain('SELECT r.g, count(*) FROM lca_rows r WHERE r.x < 5 AND NOT EXISTS (SELECT 1 FROM lca_skip s WHERE s.a = r.k AND s.b = r.k) GROUP BY r.g'); -- (the child's own plan, a join of two tables with every join method -- disabled, is whichever the release makes: only its top is shown) SELECT regexp_replace(ln, '(Nested Loop|Hash Join|Merge Join)', 'a join') AS ln FROM lca_explain('SELECT count(*) FROM lca_rows r WHERE r.x = 3 AND NOT EXISTS (SELECT 1 FROM lca_skip s JOIN lca_tag t ON t.a = s.a WHERE s.a = r.k AND t.tag = ''on'')') AS ln WHERE ln !~ '^\s{8}'; -- the counters: the child's rows, the distinct keys, the rows found, and those subtracted SELECT * FROM lca_explain('SELECT count(*) FROM lca_rows r WHERE r.x = 3 AND NOT EXISTS (SELECT 1 FROM lca_skip s WHERE s.a = r.k AND s.f = 0)', 'ANALYZE, COSTS OFF, TIMING OFF, SUMMARY OFF, BUFFERS OFF') AS ln WHERE ln ~ '(Custom Scan|Join|Seq Scan|Filter)'; -- a GUC turns it off SET pg_lion.enable_count_anti = off; SELECT lca('SELECT count(*) FROM lca_rows r WHERE r.x = 3 AND NOT EXISTS (SELECT 1 FROM lca_skip s WHERE s.a = r.k AND s.f = 0)'); RESET pg_lion.enable_count_anti; -- ---------- 2. the answers ---------- -- a WHERE of a half and of a tenth SELECT lca('SELECT count(*) FROM lca_rows r WHERE r.x < 5 AND NOT EXISTS (SELECT 1 FROM lca_skip s WHERE s.a = r.k AND s.f = 0)'); SELECT lca('SELECT count(*) FROM lca_rows r WHERE r.x = 3 AND NOT EXISTS (SELECT 1 FROM lca_skip s WHERE s.a = r.k AND s.f = 0)'); SELECT * FROM lca_val('SELECT count(*) FROM lca_rows r WHERE r.x = 3 AND NOT EXISTS (SELECT 1 FROM lca_skip s WHERE s.a = r.k AND s.f = 0)'); -- every row of the inner side, NULL keys and duplicates among them SELECT lca('SELECT count(*) FROM lca_rows r WHERE r.x < 5 AND NOT EXISTS (SELECT 1 FROM lca_skip s WHERE s.a = r.k)'); SELECT lca_counters('SELECT count(*) FROM lca_rows r WHERE r.x < 5 AND NOT EXISTS (SELECT 1 FROM lca_skip s WHERE s.a = r.k)'); -- an empty inner side subtracts nothing SELECT lca('SELECT count(*) FROM lca_rows r WHERE r.x = 3 AND NOT EXISTS (SELECT 1 FROM lca_skip s WHERE s.a = r.k AND s.f = 42)'); SELECT lca_counters('SELECT count(*) FROM lca_rows r WHERE r.x = 3 AND NOT EXISTS (SELECT 1 FROM lca_skip s WHERE s.a = r.k AND s.f = 42)'); -- inner keys of no row, or of rows the WHERE leaves out, subtract nothing SELECT lca('SELECT count(*) FROM lca_rows r WHERE r.x = 3 AND NOT EXISTS (SELECT 1 FROM lca_skip s WHERE s.a = r.k AND s.a IN (450, -1))'); SELECT lca_counters('SELECT count(*) FROM lca_rows r WHERE r.x = 3 AND r.g = 1 AND NOT EXISTS (SELECT 1 FROM lca_skip s WHERE s.a = r.k AND s.f = 0)'); -- a WHERE with no row left after the subtraction SELECT lca('SELECT count(*) FROM lca_rows r WHERE r.z = 99 AND NOT EXISTS (SELECT 1 FROM lca_skip s WHERE s.a = r.k)'); -- the two-clause form over one column: only the inner rows whose a and b agree SELECT lca('SELECT count(*) FROM lca_rows r WHERE r.x < 5 AND NOT EXISTS (SELECT 1 FROM lca_skip s WHERE s.a = r.k AND s.b = r.k)'); SELECT lca_counters('SELECT count(*) FROM lca_rows r WHERE r.x < 5 AND NOT EXISTS (SELECT 1 FROM lca_skip s WHERE s.a = r.k AND s.b = r.k)'); -- a clause of both sides beside the key, a key of an inner expression, a cross-type key SELECT lca('SELECT count(*) FROM lca_rows r WHERE r.x < 5 AND NOT EXISTS (SELECT 1 FROM lca_skip s WHERE s.a = r.k AND s.b <> r.g)'); SELECT lca('SELECT count(*) FROM lca_rows r WHERE r.x < 5 AND NOT EXISTS (SELECT 1 FROM lca_skip s WHERE r.k = s.a + 1)'); SELECT lca('SELECT count(*) FROM lca_rows r WHERE r.x < 5 AND NOT EXISTS (SELECT 1 FROM lca_skip s WHERE s.c = r.k)'); -- equal keys of other bytes are one key, looked up once: 1.0, 1.00 and 1 SELECT lca('SELECT count(*) FROM lca_rows r WHERE r.x < 5 AND NOT EXISTS (SELECT 1 FROM lca_num n WHERE n.d = r.kd)'); SELECT lca_counters('SELECT count(*) FROM lca_rows r WHERE r.x < 5 AND NOT EXISTS (SELECT 1 FROM lca_num n WHERE n.d = r.kd)'); -- a clause of the counted table alone inside the NOT EXISTS belongs to the join SELECT lca('SELECT count(*) FROM lca_rows r WHERE r.x < 5 AND NOT EXISTS (SELECT 1 FROM lca_skip s WHERE s.a = r.k AND r.g = 2)'); SELECT lca('SELECT r.g, count(*) FROM lca_rows r WHERE r.x < 5 AND NOT EXISTS (SELECT 1 FROM lca_skip s WHERE s.a = r.k AND r.g = 2) GROUP BY r.g'); -- an inner side that is a join SELECT lca('SELECT count(*) FROM lca_rows r WHERE r.x < 5 AND NOT EXISTS (SELECT 1 FROM lca_skip s JOIN lca_tag t ON t.a = s.a WHERE s.a = r.k AND t.tag = ''on'')'); -- a WHERE the residual clauses complete (DESIGN.md §10) SELECT lca('SELECT count(*) FROM lca_rows r WHERE r.x = 3 AND r.id % 3 = 0 AND NOT EXISTS (SELECT 1 FROM lca_skip s WHERE s.a = r.k)'); SELECT lca('SELECT r.g, count(*) FROM lca_rows r WHERE r.x = 3 AND r.id % 3 = 0 AND NOT EXISTS (SELECT 1 FROM lca_skip s WHERE s.a = r.k) GROUP BY r.g'); -- count(1), count of a key declared NOT NULL, count(k) of a nullable one, count(DISTINCT) of a unique column SELECT lca('SELECT count(1) FROM lca_rows r WHERE r.x < 5 AND NOT EXISTS (SELECT 1 FROM lca_skip s WHERE s.a = r.k)'); SELECT lca('SELECT count(r.kn) FROM lca_rows r WHERE r.x < 5 AND NOT EXISTS (SELECT 1 FROM lca_skip s WHERE s.a = r.kn)'); SELECT lca('SELECT count(r.k) FROM lca_rows r WHERE r.x < 5 AND NOT EXISTS (SELECT 1 FROM lca_skip s WHERE s.b = r.k)'); SELECT lca('SELECT count(DISTINCT r.id) FROM lca_rows r WHERE r.x < 5 AND NOT EXISTS (SELECT 1 FROM lca_skip s WHERE s.a = r.k)'); SELECT lca('SELECT count(*), count(r.id) FROM lca_rows r WHERE r.x = 3 AND NOT EXISTS (SELECT 1 FROM lca_skip s WHERE s.a = r.k)'); -- ---------- 3. GROUP BY ---------- SELECT lca('SELECT r.g, count(*) FROM lca_rows r WHERE r.x < 5 AND NOT EXISTS (SELECT 1 FROM lca_skip s WHERE s.a = r.k AND s.f = 0) GROUP BY r.g'); SELECT lca('SELECT r.g, r.y, count(*) FROM lca_rows r WHERE r.x < 5 AND NOT EXISTS (SELECT 1 FROM lca_skip s WHERE s.a = r.k) GROUP BY r.g, r.y'); -- the group of z = 99 is the rows of key 5: it drops to nothing and is no row SELECT lca('SELECT r.z, count(*) FROM lca_rows r WHERE r.x < 5 AND NOT EXISTS (SELECT 1 FROM lca_skip s WHERE s.a = r.k) GROUP BY r.z'); SELECT * FROM lca_val('SELECT r.z, count(*) FROM lca_rows r WHERE r.x < 5 AND NOT EXISTS (SELECT 1 FROM lca_skip s WHERE s.a = r.k) GROUP BY r.z ORDER BY r.z'); SELECT * FROM lca_val('SELECT r.z, count(*) FROM lca_rows r WHERE r.x < 5 AND NOT EXISTS (SELECT 1 FROM lca_skip s WHERE s.a = r.k AND s.a <> 5) GROUP BY r.z ORDER BY r.z'); -- ... and so is a GROUP BY the planner folds to that one group SELECT lca('SELECT r.z, count(*) FROM lca_rows r WHERE r.z = 99 AND NOT EXISTS (SELECT 1 FROM lca_skip s WHERE s.a = r.k) GROUP BY r.z'); -- the HAVING sees the counts less the rows subtracted SELECT lca('SELECT r.z, count(*) FROM lca_rows r WHERE r.x < 5 AND NOT EXISTS (SELECT 1 FROM lca_skip s WHERE s.a = r.k AND s.f = 0) GROUP BY r.z HAVING count(*) > 2650'); -- ---------- 4. the B-tree ---------- -- none on the column: core's plan SELECT lca('SELECT count(*) FROM lca_rows r WHERE r.x < 5 AND NOT EXISTS (SELECT 1 FROM lca_skip s WHERE s.a = r.y)'); -- a multicolumn B-tree with the key's column first, by one scan key and by two DROP INDEX lca_rows_k; CREATE INDEX lca_rows_ky ON lca_rows (k, y); SELECT * FROM lca_explain('SELECT count(*) FROM lca_rows r WHERE r.x < 5 AND NOT EXISTS (SELECT 1 FROM lca_skip s WHERE s.a = r.k)') AS ln WHERE ln ~ 'Lookup Index'; SELECT lca('SELECT count(*) FROM lca_rows r WHERE r.x < 5 AND NOT EXISTS (SELECT 1 FROM lca_skip s WHERE s.a = r.k)'); SELECT lca('SELECT r.g, count(*) FROM lca_rows r WHERE r.x < 5 AND NOT EXISTS (SELECT 1 FROM lca_skip s WHERE s.a = r.k AND s.b = r.y) GROUP BY r.g'); SELECT lca_counters('SELECT count(*) FROM lca_rows r WHERE r.x < 5 AND NOT EXISTS (SELECT 1 FROM lca_skip s WHERE s.a = r.k AND s.b = r.y)'); -- ... but not one whose first column no key is of DROP INDEX lca_rows_ky; CREATE INDEX lca_rows_yk ON lca_rows (y, k); SELECT lca('SELECT count(*) FROM lca_rows r WHERE r.x < 5 AND NOT EXISTS (SELECT 1 FROM lca_skip s WHERE s.a = r.k)'); DROP INDEX lca_rows_yk; -- one that names the key's column twice: a join clause is the scan key of -- the first of the two only, and stays one join clause CREATE INDEX lca_rows_kk ON lca_rows (k, k); SELECT * FROM lca_explain('SELECT count(*) FROM lca_rows r WHERE r.x < 5 AND NOT EXISTS (SELECT 1 FROM lca_skip s WHERE s.a = r.k AND s.b = r.k)') AS ln WHERE ln ~ '(Lookup Index|Join Cond)'; SELECT lca('SELECT count(*) FROM lca_rows r WHERE r.x < 5 AND NOT EXISTS (SELECT 1 FROM lca_skip s WHERE s.a = r.k)'); SELECT lca('SELECT count(*) FROM lca_rows r WHERE r.x < 5 AND NOT EXISTS (SELECT 1 FROM lca_skip s WHERE s.a = r.k AND s.b <> r.g)'); SELECT lca('SELECT r.g, count(*) FROM lca_rows r WHERE r.x < 5 AND NOT EXISTS (SELECT 1 FROM lca_skip s WHERE s.a = r.k AND s.b = r.k) GROUP BY r.g'); SELECT lca_counters('SELECT count(*) FROM lca_rows r WHERE r.x < 5 AND NOT EXISTS (SELECT 1 FROM lca_skip s WHERE s.a = r.k AND s.b = r.k)'); -- ... planned with nothing disabled, and with the pushdown off SELECT count(*) FROM lca_rows r WHERE r.x < 5 AND NOT EXISTS (SELECT 1 FROM lca_skip s WHERE s.a = r.k); SELECT r.g, count(*) FROM lca_rows r WHERE r.x < 5 AND NOT EXISTS (SELECT 1 FROM lca_skip s WHERE s.a = r.k AND s.b = r.k) GROUP BY r.g ORDER BY r.g; SET pg_lion.enable_count_pushdown = off; SELECT count(*) FROM lca_rows r WHERE r.x < 5 AND NOT EXISTS (SELECT 1 FROM lca_skip s WHERE s.a = r.k); SELECT r.g, count(*) FROM lca_rows r WHERE r.x < 5 AND NOT EXISTS (SELECT 1 FROM lca_skip s WHERE s.a = r.k AND s.b = r.k) GROUP BY r.g ORDER BY r.g; RESET pg_lion.enable_count_pushdown; -- ... and twice before a column of another key, which the search then -- stops short of: its clause is tested on the rows found DROP INDEX lca_rows_kk; CREATE INDEX lca_rows_kky ON lca_rows (k, k, y); SELECT * FROM lca_explain('SELECT count(*) FROM lca_rows r WHERE r.x < 5 AND NOT EXISTS (SELECT 1 FROM lca_skip s WHERE s.a = r.k AND s.b = r.y)') AS ln WHERE ln ~ '(Lookup Index|Join Cond)'; SELECT lca('SELECT count(*) FROM lca_rows r WHERE r.x < 5 AND NOT EXISTS (SELECT 1 FROM lca_skip s WHERE s.a = r.k AND s.b = r.y)'); SELECT lca_counters('SELECT count(*) FROM lca_rows r WHERE r.x < 5 AND NOT EXISTS (SELECT 1 FROM lca_skip s WHERE s.a = r.k AND s.b = r.y)'); DROP INDEX lca_rows_kky; CREATE INDEX lca_rows_k ON lca_rows (k); ANALYZE lca_rows; -- ---------- 5. a dirty heap: deletes and updates, before and after VACUUM ---------- DELETE FROM lca_rows WHERE k = 1 AND x < 3; UPDATE lca_rows SET k = 2 WHERE k = 3 AND x = 3; UPDATE lca_rows SET x = 3 WHERE k = 5 AND x = 4; UPDATE lca_rows SET k = NULL WHERE k = 6 AND x = 1; UPDATE lca_rows SET pad = repeat('q', 60) WHERE k = 2 AND x = 2; INSERT INTO lca_rows (id, k, kn, kd, g, y, z, x, pad) SELECT 20000 + i, 1, 1, 1, 1, 1, 1, 3, 'n' FROM generate_series(1, 7) i; UPDATE lca_skip SET a = 3 WHERE a = 6; SELECT lca('SELECT count(*) FROM lca_rows r WHERE r.x < 5 AND NOT EXISTS (SELECT 1 FROM lca_skip s WHERE s.a = r.k)'); SELECT lca('SELECT count(*) FROM lca_rows r WHERE r.x = 3 AND NOT EXISTS (SELECT 1 FROM lca_skip s WHERE s.a = r.k AND s.f = 0)'); SELECT lca('SELECT r.g, count(*) FROM lca_rows r WHERE r.x < 5 AND NOT EXISTS (SELECT 1 FROM lca_skip s WHERE s.a = r.k) GROUP BY r.g'); SELECT lca('SELECT r.z, count(*) FROM lca_rows r WHERE r.x < 5 AND NOT EXISTS (SELECT 1 FROM lca_skip s WHERE s.a = r.k) GROUP BY r.z'); -- rows deleted and updated in this very transaction BEGIN; DELETE FROM lca_rows WHERE k = 2 AND x = 0; UPDATE lca_rows SET k = 1 WHERE k = 7 AND x = 3; SELECT lca('SELECT count(*) FROM lca_rows r WHERE r.x < 5 AND NOT EXISTS (SELECT 1 FROM lca_skip s WHERE s.a = r.k)'); SELECT lca('SELECT r.g, count(*) FROM lca_rows r WHERE r.x < 5 AND NOT EXISTS (SELECT 1 FROM lca_skip s WHERE s.a = r.k) GROUP BY r.g'); ROLLBACK; VACUUM (FREEZE, ANALYZE) lca_rows, lca_skip; SELECT lca('SELECT count(*) FROM lca_rows r WHERE r.x < 5 AND NOT EXISTS (SELECT 1 FROM lca_skip s WHERE s.a = r.k)'); SELECT lca('SELECT r.g, count(*) FROM lca_rows r WHERE r.x < 5 AND NOT EXISTS (SELECT 1 FROM lca_skip s WHERE s.a = r.k) GROUP BY r.g'); -- ---------- 6. parameters: a generic plan, and a correlated rescan ---------- SELECT lca_prep('SELECT count(*) FROM lca_rows r WHERE r.x = $1 AND NOT EXISTS (SELECT 1 FROM lca_skip s WHERE s.a = r.k AND s.f = $2)', '3, 0'); SELECT lca_prep('SELECT count(*) FROM lca_rows r WHERE r.x = $1 AND NOT EXISTS (SELECT 1 FROM lca_skip s WHERE s.a = r.k AND s.f = $2)', '3, 42'); SELECT lca_prep('SELECT r.g, count(*) FROM lca_rows r WHERE r.x < $1 AND NOT EXISTS (SELECT 1 FROM lca_skip s WHERE s.a + $2 = r.k) GROUP BY r.g', '5, 1'); SELECT lca('SELECT o.v, o.w, (SELECT count(*) FROM lca_rows r WHERE r.x = o.v AND NOT EXISTS (SELECT 1 FROM lca_skip s WHERE s.a = r.k AND s.f = o.w)) FROM (VALUES (1, 0), (3, 0), (3, 1), (4, 42), (3, 0)) o(v, w)'); SELECT * FROM lca_val('SELECT o.v, o.w, (SELECT count(*) FROM lca_rows r WHERE r.x = o.v AND NOT EXISTS (SELECT 1 FROM lca_skip s WHERE s.a = r.k AND s.f = o.w)) FROM (VALUES (1, 0), (3, 0), (3, 1), (4, 42), (3, 0)) o(v, w)'); -- ---------- 7. parallel: the count divided, the subtraction made once ---------- SET max_parallel_workers_per_gather = 2; 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 pg_lion.parallel_range_keys = 1; /* * The WHERE carries a residual that every row passes. A count that reads * only its sets costs next to nothing beside the lookups, which every plan * makes once, so dividing it would save a fraction of a cost unit and the * plan would turn on rounding; one that reads its rows from the heap has * something to divide. */ SELECT * FROM lca_explain('SELECT count(*) FROM lca_rows r WHERE r.x = 3 AND length(r.pad) > 0 AND NOT EXISTS (SELECT 1 FROM lca_skip s WHERE s.a = r.k)'); SELECT lca('SELECT count(*) FROM lca_rows r WHERE r.x = 3 AND length(r.pad) > 0 AND NOT EXISTS (SELECT 1 FROM lca_skip s WHERE s.a = r.k)'); SELECT lca('SELECT count(*) FROM lca_rows r WHERE r.x = 3 AND length(r.pad) > 0 AND NOT EXISTS (SELECT 1 FROM lca_skip s WHERE s.a = r.k AND s.b = r.k)'); -- one participant ran the child and made the lookups: the serial node's counters SELECT lca_counters('SELECT count(*) FROM lca_rows r WHERE r.x = 3 AND length(r.pad) > 0 AND NOT EXISTS (SELECT 1 FROM lca_skip s WHERE s.a = r.k)'); SET max_parallel_workers_per_gather = 0; SELECT lca_counters('SELECT count(*) FROM lca_rows r WHERE r.x = 3 AND length(r.pad) > 0 AND NOT EXISTS (SELECT 1 FROM lca_skip s WHERE s.a = r.k)'); SET max_parallel_workers_per_gather = 2; -- ... rescanned under a correlated subquery SELECT lca('SELECT o.v, (SELECT count(*) FROM lca_rows r WHERE r.x = o.v AND NOT EXISTS (SELECT 1 FROM lca_skip s WHERE s.a = r.k)) FROM (VALUES (3), (1), (3)) o(v)'); -- ... and without the leader taking part: a worker subtracts, or the leader -- when none starts SET plan_cache_mode = force_generic_plan; SET enable_hashjoin = off; SET enable_mergejoin = off; SET enable_nestloop = off; PREPARE lca_par AS SELECT count(*) FROM lca_rows r WHERE r.x = 3 AND length(r.pad) > 0 AND NOT EXISTS (SELECT 1 FROM lca_skip s WHERE s.a = r.k); SELECT ln FROM lca_explain('EXECUTE lca_par') AS ln WHERE ln ~ 'Parallel'; SET parallel_leader_participation = off; CREATE TEMP TABLE lca_par_on AS EXECUTE lca_par; RESET parallel_leader_participation; DEALLOCATE lca_par; RESET plan_cache_mode; RESET enable_hashjoin; RESET enable_mergejoin; RESET enable_nestloop; SET pg_lion.enable_count_pushdown = off; SELECT (TABLE lca_par_on) = count(*) AS same_count FROM lca_rows r WHERE r.x = 3 AND length(r.pad) > 0 AND NOT EXISTS (SELECT 1 FROM lca_skip s WHERE s.a = r.k); RESET pg_lion.enable_count_pushdown; DROP TABLE lca_par_on; -- the GROUP BY stays serial SELECT lca('SELECT r.g, count(*) FROM lca_rows r WHERE r.x < 5 AND NOT EXISTS (SELECT 1 FROM lca_skip s WHERE s.a = r.k) GROUP BY r.g'); RESET max_parallel_workers_per_gather; RESET parallel_setup_cost; RESET parallel_tuple_cost; RESET min_parallel_table_scan_size; RESET min_parallel_index_scan_size; RESET pg_lion.parallel_range_keys; -- ---------- 8. what is left to core ---------- -- the cost model takes the node for a few keys of a row or so each ... SELECT lca_pick('SELECT count(*) FROM lca_rows r WHERE r.x < 5 AND NOT EXISTS (SELECT 1 FROM lca_skip s WHERE s.a = r.id)'); SELECT lca('SELECT count(*) FROM lca_rows r WHERE r.x < 5 AND NOT EXISTS (SELECT 1 FROM lca_skip s WHERE s.a = r.id)'); -- ... and not for an inner side of thousands of keys, one a row CREATE TABLE lca_many (a int NOT NULL); INSERT INTO lca_many SELECT i * 2 FROM generate_series(1, 10000) i; VACUUM (ANALYZE) lca_many; SELECT lca_pick('SELECT count(*) FROM lca_rows r WHERE r.x < 5 AND NOT EXISTS (SELECT 1 FROM lca_many m WHERE m.a = r.id)'); SELECT lca('SELECT count(*) FROM lca_rows r WHERE r.x < 5 AND NOT EXISTS (SELECT 1 FROM lca_many m WHERE m.a = r.id)'); DROP TABLE lca_many; -- ... but for a hundred and fifty: a row found is a read of a heap page the -- cache holds, not a page at random_page_cost (lion_anti_price()) CREATE TABLE lca_some (a int NOT NULL); INSERT INTO lca_some SELECT i * 2 FROM generate_series(1, 150) i; VACUUM (ANALYZE) lca_some; SELECT lca_pick('SELECT count(*) FROM lca_rows r WHERE r.x < 5 AND NOT EXISTS (SELECT 1 FROM lca_some m WHERE m.a = r.id)'); SELECT lca('SELECT count(*) FROM lca_rows r WHERE r.x < 5 AND NOT EXISTS (SELECT 1 FROM lca_some m WHERE m.a = r.id)'); DROP TABLE lca_some; -- a key of two columns that go together, k and kn: a lookup of a pair finds -- its 50 rows, which the product of the columns' n_distinct, 400 x 400 over -- 20,000 rows, makes one; CREATE STATISTICS's n_distinct of the pair says -- 400 (lion_anti_key_values()) CREATE INDEX lca_rows_kkn ON lca_rows (k, kn); CREATE TABLE lca_pairs (a int, b int); INSERT INTO lca_pairs SELECT i, i FROM generate_series(1, 100) i; VACUUM (ANALYZE) lca_pairs; SELECT lca_pick('SELECT count(*) FROM lca_rows r WHERE r.x < 5 AND NOT EXISTS (SELECT 1 FROM lca_pairs p WHERE p.a = r.k AND p.b = r.kn)'); CREATE STATISTICS lca_rows_kkn_st (ndistinct) ON k, kn FROM lca_rows; ANALYZE lca_rows; SELECT lca_pick('SELECT count(*) FROM lca_rows r WHERE r.x < 5 AND NOT EXISTS (SELECT 1 FROM lca_pairs p WHERE p.a = r.k AND p.b = r.kn)'); SELECT lca('SELECT count(*) FROM lca_rows r WHERE r.x < 5 AND NOT EXISTS (SELECT 1 FROM lca_pairs p WHERE p.a = r.k AND p.b = r.kn)'); DROP STATISTICS lca_rows_kkn_st; DROP INDEX lca_rows_kkn; DROP TABLE lca_pairs; -- a LEFT JOIN ... IS NULL, and a NOT IN over a nullable column SELECT lca('SELECT count(*) FROM lca_rows r LEFT JOIN lca_skip s ON s.a = r.k WHERE r.x = 3 AND s.a IS NULL'); SELECT lca('SELECT count(*) FROM lca_rows r WHERE r.x = 3 AND r.k NOT IN (SELECT s.a FROM lca_skip s WHERE s.f = 0 AND s.a IS NOT NULL)'); -- ... and a NOT IN whose sides are both never NULL, kn declared so and s.a -- by its filter: an anti join from PostgreSQL 19, which the node takes as it -- takes NOT EXISTS's, and a hashed SubPlan before it; core's answer either way SELECT (l LIKE 'pushed down%') = (current_setting('server_version_num')::int >= 190000) AS as_the_release_plans, regexp_replace(l, '^(not )?pushed down', 'either plan') AS answer FROM lca('SELECT count(*) FROM lca_rows r WHERE r.x = 3 AND r.kn NOT IN (SELECT s.a FROM lca_skip s WHERE s.f = 0 AND s.a IS NOT NULL)') AS l; -- a WHERE clause nothing answers: no lion index, and residual clauses off SET pg_lion.enable_count_residual = off; SELECT lca('SELECT count(*) FROM lca_rows r WHERE r.x = 3 AND r.id % 3 = 0 AND NOT EXISTS (SELECT 1 FROM lca_skip s WHERE s.a = r.k)'); RESET pg_lion.enable_count_residual; -- a NOT EXISTS beside a second table in the FROM SELECT lca('SELECT count(*) FROM lca_rows r, lca_tag t WHERE r.id = t.a AND NOT EXISTS (SELECT 1 FROM lca_skip s WHERE s.a = r.k)'); -- a correlation by no equality SELECT lca('SELECT count(*) FROM lca_rows r WHERE r.x = 3 AND NOT EXISTS (SELECT 1 FROM lca_skip s WHERE s.a < r.k)'); -- row-level security on the table counted CREATE ROLE lca_reader; GRANT SELECT ON lca_rows, lca_skip TO lca_reader; ALTER TABLE lca_rows ENABLE ROW LEVEL SECURITY; CREATE POLICY lca_rows_some ON lca_rows FOR SELECT TO lca_reader USING (g = 1); SET ROLE lca_reader; SELECT lca('SELECT count(*) FROM lca_rows r WHERE r.x < 5 AND NOT EXISTS (SELECT 1 FROM lca_skip s WHERE s.a = r.k)'); RESET ROLE; ALTER TABLE lca_rows DISABLE ROW LEVEL SECURITY; DROP POLICY lca_rows_some ON lca_rows; REVOKE ALL ON lca_rows, lca_skip FROM lca_reader; DROP ROLE lca_reader; -- a partitioned table counted CREATE TABLE lca_parts (id int NOT NULL, k int, x int NOT NULL) PARTITION BY RANGE (id); CREATE TABLE lca_parts_1 PARTITION OF lca_parts FOR VALUES FROM (0) TO (5000); CREATE TABLE lca_parts_2 PARTITION OF lca_parts FOR VALUES FROM (5000) TO (10000); INSERT INTO lca_parts SELECT i, i % 100, i % 10 FROM generate_series(0, 9999) i; CREATE INDEX lca_parts_k ON lca_parts (k); CREATE INDEX lca_parts_x ON lca_parts USING lion (x); VACUUM (ANALYZE) lca_parts; SELECT lca('SELECT count(*) FROM lca_parts p WHERE p.x = 3 AND NOT EXISTS (SELECT 1 FROM lca_skip s WHERE s.a = p.k)'); DROP TABLE lca_parts; -- ---------- 9. beside a count by cells ---------- -- A GROUP BY of expressions over predicates, and a WHERE over them, counted -- by cells (DESIGN.md §10, "Counts by cells"): each row a key finds is -- taken from its cell, its predicates evaluated on it (DESIGN.md §27, -- "Counts by cells beside the anti join"). The score reads x, g - NULL on -- every 11th row - and z, which is 99 on the rows of key 5 alone; the rows -- of one key have every x, and g and y of several values. CREATE VIEW lca_scored AS SELECT r.*, CASE WHEN r.x = 1 THEN 3 WHEN r.x IN (2, 3) THEN 2 ELSE 0 END + CASE WHEN r.g IN (2, 3) THEN 2 WHEN r.g IS NULL THEN 1 ELSE 0 END + CASE WHEN r.z = 99 THEN 5 ELSE 0 END AS score FROM lca_rows r; CREATE VIEW lca_tiered AS SELECT v.*, CASE WHEN v.score >= 5 THEN 'high' WHEN v.score >= 3 THEN 'mid' WHEN v.score >= 1 THEN 'low' ELSE 'none' END AS tier FROM lca_scored v; -- the plans: both strategies, the anti join's and the cells' SELECT * FROM lca_explain('SELECT CASE WHEN r.x = 1 THEN ''a'' WHEN r.x IN (2, 3) THEN ''b'' ELSE ''c'' END AS t, count(*) FROM lca_rows r WHERE NOT EXISTS (SELECT 1 FROM lca_skip s WHERE s.a = r.k) GROUP BY 1'); SELECT * FROM lca_explain('SELECT count(*) FROM lca_rows r WHERE CASE WHEN r.x = 1 THEN r.g = 2 ELSE r.g = 3 END AND NOT EXISTS (SELECT 1 FROM lca_skip s WHERE s.a = r.k AND s.f = 0)'); SELECT * FROM lca_explain('SELECT tier, count(*) FROM lca_tiered t WHERE t.y < 5 AND NOT EXISTS (SELECT 1 FROM lca_skip s WHERE s.a = t.k) GROUP BY tier') AS ln WHERE ln !~ 'Group Key'; -- the cost model takes the node, with nothing disabled SELECT lca_pick('SELECT tier, count(*) FROM lca_tiered t WHERE NOT EXISTS (SELECT 1 FROM lca_skip s WHERE s.a = t.k) GROUP BY tier'); SELECT lca_pick('SELECT tier, count(*) FROM lca_tiered t WHERE t.y < 5 AND NOT EXISTS (SELECT 1 FROM lca_skip s WHERE s.a = t.k AND s.f = 0) GROUP BY tier'); -- the answers: a GROUP BY of a CASE, of the tier and of the score, a WHERE -- over predicates, and both SELECT lca('SELECT CASE WHEN r.x = 1 THEN ''a'' WHEN r.x IN (2, 3) THEN ''b'' ELSE ''c'' END AS t, count(*) FROM lca_rows r WHERE NOT EXISTS (SELECT 1 FROM lca_skip s WHERE s.a = r.k) GROUP BY 1'); SELECT lca('SELECT count(*) FROM lca_rows r WHERE CASE WHEN r.x = 1 THEN r.g = 2 ELSE r.g = 3 END AND NOT EXISTS (SELECT 1 FROM lca_skip s WHERE s.a = r.k)'); SELECT lca('SELECT tier, count(*) FROM lca_tiered t WHERE NOT EXISTS (SELECT 1 FROM lca_skip s WHERE s.a = t.k) GROUP BY tier'); SELECT lca('SELECT tier, count(*) FROM lca_tiered t WHERE t.y < 5 AND NOT EXISTS (SELECT 1 FROM lca_skip s WHERE s.a = t.k AND s.f = 0) GROUP BY tier'); SELECT lca('SELECT score, count(*) FROM lca_scored v WHERE v.y < 5 AND NOT EXISTS (SELECT 1 FROM lca_skip s WHERE s.a = v.k) GROUP BY score'); SELECT lca('SELECT count(*) FROM lca_tiered t WHERE t.tier = ''high'' AND NOT EXISTS (SELECT 1 FROM lca_skip s WHERE s.a = t.k)'); SELECT lca('SELECT count(*) FROM lca_tiered t WHERE t.y < 5 AND t.tier IN (''mid'', ''low'') AND NOT EXISTS (SELECT 1 FROM lca_skip s WHERE s.a = t.k)'); SELECT lca('SELECT (t.y IS NULL) AS u, count(*) FROM lca_tiered t WHERE t.tier <> ''none'' AND NOT EXISTS (SELECT 1 FROM lca_skip s WHERE s.a = t.k) GROUP BY 1'); SELECT * FROM lca_val('SELECT tier, count(*) FROM lca_tiered t WHERE NOT EXISTS (SELECT 1 FROM lca_skip s WHERE s.a = t.k) GROUP BY tier ORDER BY tier'); -- the counters: the rows found, each taken from its cell SELECT lca_counters('SELECT tier, count(*) FROM lca_tiered t WHERE NOT EXISTS (SELECT 1 FROM lca_skip s WHERE s.a = t.k) GROUP BY tier'); -- NULL in a predicate's column: the truths of (g = 2) are true, false and -- NULL, of (y IS NULL) true and false, and the rows found are of all of them SELECT lca('SELECT (r.g = 2) AS u, (r.y IS NULL) AS v, count(*) FROM lca_rows r WHERE NOT EXISTS (SELECT 1 FROM lca_skip s WHERE s.a = r.k) GROUP BY 1, 2'); SELECT * FROM lca_val('SELECT (r.g = 2) AS u, count(*) FROM lca_rows r WHERE NOT EXISTS (SELECT 1 FROM lca_skip s WHERE s.a = r.k) GROUP BY 1 ORDER BY 1'); SELECT lca('SELECT count(*) FROM lca_rows r WHERE COALESCE(r.g = 2 OR r.y = 3, true) AND NOT EXISTS (SELECT 1 FROM lca_skip s WHERE s.a = r.k)'); -- the cell of z = 99 is the rows of key 5: it drops to nothing and is no row SELECT * FROM lca_val('SELECT (r.z = 99) AS u, count(*) FROM lca_rows r WHERE NOT EXISTS (SELECT 1 FROM lca_skip s WHERE s.a = r.k) GROUP BY 1 ORDER BY 1'); SELECT lca('SELECT (r.z = 99) AS u, count(*) FROM lca_rows r WHERE NOT EXISTS (SELECT 1 FROM lca_skip s WHERE s.a = r.k) GROUP BY 1'); SELECT lca('SELECT count(*) FROM lca_rows r WHERE CASE WHEN r.z = 99 THEN true END AND NOT EXISTS (SELECT 1 FROM lca_skip s WHERE s.a = r.k)'); -- a column of many constants, the bits of k: ten IN lists of the values -- from 1 to 1,023 with each bit set, 1,025 outcomes with another value's and -- NULL's, each row's found from its truths (lion_cells_code_of()); the -- cells of the inner side's keys come to nothing CREATE TEMP TABLE lca_bits AS SELECT format('SELECT %s, count(*) FROM lca_rows r WHERE NOT EXISTS (SELECT 1 FROM lca_skip s WHERE s.a = r.k) GROUP BY 1, 2, 3, 4, 5, 6, 7, 8, 9, 10', string_agg(format('(r.k IN (%s)) AS b%s', l, j), ', ' ORDER BY j)) AS q FROM (SELECT j, string_agg(v::text, ', ' ORDER BY v) AS l FROM generate_series(0, 9) j, generate_series(1, 1023) v WHERE v & (1 << j) <> 0 GROUP BY j) b; SELECT ln FROM lca_bits, lca_explain(q) AS ln WHERE ln ~ '^\s*(Group Strategy|Cell Columns|Cells):'; SELECT lca(q) FROM lca_bits; SELECT lca_counters(q) FROM lca_bits; DROP TABLE lca_bits; -- the correlation by two of the inner side's columns, each equal to the -- key: only the inner rows whose a and b agree SELECT * FROM lca_explain('SELECT tier, count(*) FROM lca_tiered t WHERE NOT EXISTS (SELECT 1 FROM lca_skip s WHERE s.a = t.k AND s.b = t.k) GROUP BY tier') AS ln WHERE ln ~ 'Join Cond'; SELECT lca('SELECT tier, count(*) FROM lca_tiered t WHERE NOT EXISTS (SELECT 1 FROM lca_skip s WHERE s.a = t.k AND s.b = t.k) GROUP BY tier'); SELECT lca('SELECT count(*) FROM lca_tiered t WHERE t.tier = ''high'' AND NOT EXISTS (SELECT 1 FROM lca_skip s WHERE s.a = t.k AND s.b = t.k)'); SELECT lca_counters('SELECT tier, count(*) FROM lca_tiered t WHERE NOT EXISTS (SELECT 1 FROM lca_skip s WHERE s.a = t.k AND s.b = t.k) GROUP BY tier'); -- a correlation that reads a predicate the cells evaluate: EXPLAIN shows -- the predicate as it is written, and a row's truths are evaluated for the -- clause before its cell is known SELECT * FROM lca_explain('SELECT tier, count(*) FROM lca_tiered t WHERE NOT EXISTS (SELECT 1 FROM lca_skip s WHERE s.a = t.k AND t.x = 1) GROUP BY tier') AS ln WHERE ln ~ 'Join Cond|Cell Columns'; SELECT lca('SELECT tier, count(*) FROM lca_tiered t WHERE NOT EXISTS (SELECT 1 FROM lca_skip s WHERE s.a = t.k AND t.x = 1) GROUP BY tier'); SELECT lca('SELECT tier, count(*) FROM lca_tiered t WHERE NOT EXISTS (SELECT 1 FROM lca_skip s WHERE s.a = t.k AND (t.g IN (2, 3) OR s.f = 0)) GROUP BY tier'); SELECT lca('SELECT count(*) FROM lca_tiered t WHERE t.tier = ''mid'' AND NOT EXISTS (SELECT 1 FROM lca_skip s WHERE s.a = t.k AND t.x IN (2, 3))'); -- inner keys of no row, of rows the WHERE leaves out, NULL keys and -- duplicates; an empty inner side SELECT lca('SELECT tier, count(*) FROM lca_tiered t WHERE NOT EXISTS (SELECT 1 FROM lca_skip s WHERE s.a = t.k AND s.a IN (450, -1)) GROUP BY tier'); SELECT lca_counters('SELECT tier, count(*) FROM lca_tiered t WHERE NOT EXISTS (SELECT 1 FROM lca_skip s WHERE s.a = t.k AND s.a IN (450, -1)) GROUP BY tier'); SELECT lca_counters('SELECT tier, count(*) FROM lca_tiered t WHERE t.z = 99 AND NOT EXISTS (SELECT 1 FROM lca_skip s WHERE s.a = t.k AND s.a IN (2, 3)) GROUP BY tier'); SELECT lca('SELECT tier, count(*) FROM lca_tiered t WHERE t.z = 99 AND NOT EXISTS (SELECT 1 FROM lca_skip s WHERE s.a = t.k AND s.a IN (2, 3)) GROUP BY tier'); SELECT lca('SELECT tier, count(*) FROM lca_tiered t WHERE NOT EXISTS (SELECT 1 FROM lca_skip s WHERE s.a = t.k AND s.a IS NULL) GROUP BY tier'); SELECT lca('SELECT tier, count(*) FROM lca_tiered t WHERE NOT EXISTS (SELECT 1 FROM lca_skip s WHERE s.a = t.k AND s.f = 42) GROUP BY tier'); -- a clause of both sides, a key of an inner expression, equal keys of other -- bytes, an inner side that is a join, and the HAVING SELECT lca('SELECT tier, count(*) FROM lca_tiered t WHERE NOT EXISTS (SELECT 1 FROM lca_skip s WHERE s.a = t.k AND s.b <> t.g) GROUP BY tier'); SELECT lca('SELECT tier, count(*) FROM lca_tiered t WHERE NOT EXISTS (SELECT 1 FROM lca_skip s WHERE t.k = s.a + 1) GROUP BY tier'); SELECT lca('SELECT tier, count(*) FROM lca_tiered t WHERE NOT EXISTS (SELECT 1 FROM lca_num n WHERE n.d = t.kd) GROUP BY tier'); SELECT lca('SELECT tier, count(*) FROM lca_tiered t WHERE NOT EXISTS (SELECT 1 FROM lca_skip s JOIN lca_tag g ON g.a = s.a WHERE s.a = t.k AND g.tag = ''on'') GROUP BY tier'); SELECT lca('SELECT tier, count(*), count(1) FROM lca_tiered t WHERE NOT EXISTS (SELECT 1 FROM lca_skip s WHERE s.a = t.k) GROUP BY tier HAVING count(*) > 4000'); -- a tally that goes to its file: a cell's counts come up more than once, -- and those of a cell that loses rows are added up before it does SET work_mem = '64kB'; SET hash_mem_multiplier = 1; CREATE TEMP TABLE lca_wide AS SELECT format('SELECT CASE %s END AS u, CASE WHEN r.x = 1 THEN 1 WHEN r.x = 2 THEN 2 END AS v, CASE WHEN r.g = 2 THEN 1 WHEN r.g = 4 THEN 2 END AS w, CASE WHEN r.y = 3 THEN 1 WHEN r.y = 5 THEN 2 END AS c, count(*) FROM lca_rows r WHERE NOT EXISTS (SELECT 1 FROM lca_skip s WHERE s.a = r.k) GROUP BY 1, 2, 3, 4', string_agg(format('WHEN r.k = %s THEN %s', i, i), ' ' ORDER BY i)) AS q FROM generate_series(0, 119) i; SELECT count(*) > 0 AS spilled FROM lca_wide, lca_explain(q, 'ANALYZE, COSTS OFF, TIMING OFF, SUMMARY OFF, BUFFERS OFF') AS ln WHERE ln ~ 'Tally Spills: [1-9]'; SELECT lca(q) FROM lca_wide; DROP TABLE lca_wide; RESET work_mem; RESET hash_mem_multiplier; -- no B-tree on the correlated column, and the anti join turned off: core's plan SELECT lca('SELECT tier, count(*) FROM lca_tiered t WHERE NOT EXISTS (SELECT 1 FROM lca_skip s WHERE s.a = t.y) GROUP BY tier'); SET pg_lion.enable_count_anti = off; SELECT lca('SELECT tier, count(*) FROM lca_tiered t WHERE NOT EXISTS (SELECT 1 FROM lca_skip s WHERE s.a = t.k) GROUP BY tier'); RESET pg_lion.enable_count_anti; -- a generic plan, and a rescan under a correlated subquery SELECT lca_prep('SELECT tier, count(*) FROM lca_tiered t WHERE t.y < $1 AND NOT EXISTS (SELECT 1 FROM lca_skip s WHERE s.a = t.k AND s.f = $2) GROUP BY tier', '5, 0'); SELECT lca_prep('SELECT tier, count(*) FROM lca_tiered t WHERE t.y < $1 AND NOT EXISTS (SELECT 1 FROM lca_skip s WHERE s.a = t.k AND s.f = $2) GROUP BY tier', '3, 42'); SELECT lca('SELECT o.v, o.w, (SELECT count(*) FROM lca_tiered t WHERE t.y < o.v AND t.tier = ''high'' AND NOT EXISTS (SELECT 1 FROM lca_skip s WHERE s.a = t.k AND s.f = o.w)) FROM (VALUES (5, 0), (7, 0), (5, 42), (5, 0)) o(v, w)'); -- rows deleted and updated - from one cell to another, or to no key's - -- and inserted, before VACUUM, in this very transaction, and after VACUUM DELETE FROM lca_rows WHERE k = 2 AND x = 1; UPDATE lca_rows SET x = 1 WHERE k = 3 AND x = 4; UPDATE lca_rows SET g = NULL WHERE k = 5 AND x = 6; UPDATE lca_rows SET k = 450 WHERE k = 4 AND x = 7; UPDATE lca_rows SET pad = repeat('r', 60) WHERE k = 2 AND x = 2; INSERT INTO lca_rows (id, k, kn, kd, g, y, z, x, pad) SELECT 30000 + i, 3, 3, 3, NULL, 1, 99, 1, 'n' FROM generate_series(1, 5) i; SELECT lca('SELECT tier, count(*) FROM lca_tiered t WHERE NOT EXISTS (SELECT 1 FROM lca_skip s WHERE s.a = t.k) GROUP BY tier'); SELECT lca('SELECT (r.g = 2) AS u, (r.z = 99) AS v, count(*) FROM lca_rows r WHERE r.y < 5 AND NOT EXISTS (SELECT 1 FROM lca_skip s WHERE s.a = r.k) GROUP BY 1, 2'); SELECT lca('SELECT count(*) FROM lca_tiered t WHERE t.tier = ''high'' AND NOT EXISTS (SELECT 1 FROM lca_skip s WHERE s.a = t.k)'); BEGIN; DELETE FROM lca_rows WHERE k = 1 AND x = 3; UPDATE lca_rows SET x = 2 WHERE k = 2 AND x = 0; UPDATE lca_rows SET k = 3 WHERE k = 9 AND x = 1; SELECT lca('SELECT tier, count(*) FROM lca_tiered t WHERE NOT EXISTS (SELECT 1 FROM lca_skip s WHERE s.a = t.k) GROUP BY tier'); SELECT lca('SELECT count(*) FROM lca_tiered t WHERE t.tier = ''mid'' AND NOT EXISTS (SELECT 1 FROM lca_skip s WHERE s.a = t.k)'); ROLLBACK; VACUUM (FREEZE, ANALYZE) lca_rows; SELECT lca('SELECT tier, count(*) FROM lca_tiered t WHERE NOT EXISTS (SELECT 1 FROM lca_skip s WHERE s.a = t.k) GROUP BY tier'); SELECT lca('SELECT count(*) FROM lca_tiered t WHERE t.tier = ''high'' AND NOT EXISTS (SELECT 1 FROM lca_skip s WHERE s.a = t.k)'); -- in parallel: every participant runs the child and looks the keys up, and -- takes away the rows of the ranges it counts - priced as the participants' -- runs of it all, which here outweigh their shares of the count of 20,000 -- rows: the serial node (lion_add_parallel_cells_path()) SET max_parallel_workers_per_gather = 2; 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 pg_lion.parallel_range_keys = 1; SELECT lca('SELECT tier, count(*) FROM lca_tiered t WHERE NOT EXISTS (SELECT 1 FROM lca_skip s WHERE s.a = t.k) GROUP BY tier'); -- ... and, with the pages the lookups read priced low, the parallel node SET random_page_cost = 0.1; SET seq_page_cost = 0.1; SELECT * FROM lca_explain('SELECT tier, count(*) FROM lca_tiered t WHERE NOT EXISTS (SELECT 1 FROM lca_skip s WHERE s.a = t.k) GROUP BY tier') AS ln WHERE ln !~ 'Group Key'; SELECT lca('SELECT tier, count(*) FROM lca_tiered t WHERE NOT EXISTS (SELECT 1 FROM lca_skip s WHERE s.a = t.k) GROUP BY tier'); SELECT lca('SELECT tier, count(*) FROM lca_tiered t WHERE t.y IN (1, 2, 3, 4) AND NOT EXISTS (SELECT 1 FROM lca_skip s WHERE s.a = t.k AND s.b = t.k) GROUP BY tier'); SELECT lca('SELECT (r.z = 99) AS u, count(*) FROM lca_rows r WHERE NOT EXISTS (SELECT 1 FROM lca_skip s WHERE s.a = r.k) GROUP BY 1'); SELECT lca('SELECT count(*) FROM lca_tiered t WHERE t.tier = ''high'' AND NOT EXISTS (SELECT 1 FROM lca_skip s WHERE s.a = t.k)'); -- ... the rows subtracted, every participant's, are the serial node's SELECT ln FROM lca_explain('SELECT tier, count(*) FROM lca_tiered t WHERE NOT EXISTS (SELECT 1 FROM lca_skip s WHERE s.a = t.k) GROUP BY tier', 'ANALYZE, COSTS OFF, TIMING OFF, SUMMARY OFF, BUFFERS OFF') AS ln WHERE ln ~ 'Join Rows Subtracted'; SET max_parallel_workers_per_gather = 0; SELECT lca_counters('SELECT tier, count(*) FROM lca_tiered t WHERE NOT EXISTS (SELECT 1 FROM lca_skip s WHERE s.a = t.k) GROUP BY tier'); SET max_parallel_workers_per_gather = 2; -- ... with rows the heap is asked about UPDATE lca_rows SET x = 2 WHERE k = 2 AND x = 0; SELECT lca('SELECT tier, count(*) FROM lca_tiered t WHERE NOT EXISTS (SELECT 1 FROM lca_skip s WHERE s.a = t.k) GROUP BY tier'); -- ... and without the leader taking part SET plan_cache_mode = force_generic_plan; SET enable_hashjoin = off; SET enable_mergejoin = off; SET enable_nestloop = off; PREPARE lca_par AS SELECT tier, count(*) FROM lca_tiered t WHERE NOT EXISTS (SELECT 1 FROM lca_skip s WHERE s.a = t.k) GROUP BY tier; SELECT ln FROM lca_explain('EXECUTE lca_par') AS ln WHERE ln ~ 'Parallel'; SET parallel_leader_participation = off; CREATE TEMP TABLE lca_par_on AS EXECUTE lca_par; RESET parallel_leader_participation; DEALLOCATE lca_par; RESET plan_cache_mode; RESET enable_hashjoin; RESET enable_mergejoin; RESET enable_nestloop; SET pg_lion.enable_count_pushdown = off; SELECT (SELECT count(*) FROM (TABLE lca_par_on EXCEPT ALL SELECT tier, count(*) FROM lca_tiered t WHERE NOT EXISTS (SELECT 1 FROM lca_skip s WHERE s.a = t.k) GROUP BY tier) a) + (SELECT count(*) FROM (SELECT tier, count(*) FROM lca_tiered t WHERE NOT EXISTS (SELECT 1 FROM lca_skip s WHERE s.a = t.k) GROUP BY tier EXCEPT ALL TABLE lca_par_on) b) AS rows_differ; RESET pg_lion.enable_count_pushdown; DROP TABLE lca_par_on; RESET random_page_cost; RESET seq_page_cost; RESET max_parallel_workers_per_gather; RESET parallel_setup_cost; RESET parallel_tuple_cost; RESET min_parallel_table_scan_size; RESET min_parallel_index_scan_size; RESET pg_lion.parallel_range_keys; -- ---------- 10. the order the clauses are tested in ---------- -- Each row a key finds is tested on the table's own restrictions, and only -- if it passes them on the join clauses, the scan keys' first; each list in -- the order core's plan tests it in, cheapest first. A clause core runs -- only on the rows a cheaper one keeps - a division by y after y <> 0 - is -- never run on a row that one rejects. Row 7 has y = 0, and an inner row -- a = b = 7 matches it. SELECT r.id, r.k, r.y FROM lca_rows r WHERE r.id = 7; SELECT * FROM lca_skip s WHERE s.a = 7; -- a join clause dividing by a column of the table: the WHERE keeps y = 0 out, -- planned with nothing disabled ... SELECT lca_pick('SELECT count(*) FROM lca_rows r WHERE r.y <> 0 AND NOT EXISTS (SELECT 1 FROM lca_skip s WHERE s.a = r.id AND s.b / r.y > 1)'); SELECT count(*) FROM lca_rows r WHERE r.y <> 0 AND NOT EXISTS (SELECT 1 FROM lca_skip s WHERE s.a = r.id AND s.b / r.y > 1); SET pg_lion.enable_count_pushdown = off; SELECT count(*) FROM lca_rows r WHERE r.y <> 0 AND NOT EXISTS (SELECT 1 FROM lca_skip s WHERE s.a = r.id AND s.b / r.y > 1); RESET pg_lion.enable_count_pushdown; -- ... and with joins disabled, by the key of some 50 rows, grouped, beside -- residual clauses and a count of a column SELECT lca('SELECT count(*) FROM lca_rows r WHERE r.y <> 0 AND NOT EXISTS (SELECT 1 FROM lca_skip s WHERE s.a = r.id AND s.b / r.y > 1)'); SELECT lca('SELECT count(*) FROM lca_rows r WHERE r.y <> 0 AND NOT EXISTS (SELECT 1 FROM lca_skip s WHERE s.a = r.k AND s.b / r.y > 1)'); SELECT lca('SELECT r.g, count(*) FROM lca_rows r WHERE r.y <> 0 AND NOT EXISTS (SELECT 1 FROM lca_skip s WHERE s.a = r.k AND s.b / r.y > 1) GROUP BY r.g'); SELECT lca('SELECT count(*) FROM lca_rows r WHERE r.y IN (1, 2, 3) AND r.id % 3 = 0 AND NOT EXISTS (SELECT 1 FROM lca_skip s WHERE s.a = r.k AND s.b / r.y > 1)'); SELECT lca('SELECT count(r.g) FROM lca_rows r WHERE r.y <> 0 AND NOT EXISTS (SELECT 1 FROM lca_skip s WHERE s.a = r.k AND s.b / r.y > 1)'); SELECT lca_counters('SELECT count(*) FROM lca_rows r WHERE r.y <> 0 AND NOT EXISTS (SELECT 1 FROM lca_skip s WHERE s.a = r.k AND s.b / r.y > 1)'); -- the WHERE in core's order, not as written: 10 / y after the test of y SELECT lca('SELECT count(*) FROM lca_rows r WHERE 10 / r.y > 1 AND r.y IN (1, 2, 3) AND NOT EXISTS (SELECT 1 FROM lca_skip s WHERE s.a = r.k AND s.f = 0)'); SELECT lca('SELECT r.g, count(*) FROM lca_rows r WHERE 10 / r.y > 1 AND r.y IN (1, 2, 3) AND NOT EXISTS (SELECT 1 FROM lca_skip s WHERE s.a = r.k) GROUP BY r.g'); -- the join clauses in core's order: a clause of the table alone inside the -- NOT EXISTS is the join's, and runs before the division SELECT lca('SELECT count(*) FROM lca_rows r WHERE r.x < 5 AND NOT EXISTS (SELECT 1 FROM lca_skip s WHERE s.a = r.k AND s.b / r.y > 1 AND r.y <> 0)'); SELECT * FROM lca_explain('SELECT count(*) FROM lca_rows r WHERE r.x < 5 AND NOT EXISTS (SELECT 1 FROM lca_skip s WHERE s.b / r.y > 1 AND r.y <> 0 AND s.a = r.k)') AS ln WHERE ln ~ 'Join Cond'; -- beside a count by cells, the GROUP BY and the WHERE form SELECT lca('SELECT tier, count(*) FROM lca_tiered t WHERE t.y IN (1, 2, 3) AND NOT EXISTS (SELECT 1 FROM lca_skip s WHERE s.a = t.k AND s.b / t.y > 1) GROUP BY tier'); SELECT lca('SELECT count(*) FROM lca_tiered t WHERE t.tier IN (''low'', ''none'') AND t.y IN (1, 2, 3) AND NOT EXISTS (SELECT 1 FROM lca_skip s WHERE s.a = t.k AND s.b / t.y > 1)'); -- in parallel SET max_parallel_workers_per_gather = 2; 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 pg_lion.parallel_range_keys = 1; SELECT lca('SELECT count(*) FROM lca_rows r WHERE r.y IN (1, 2, 3) AND length(r.pad) > 0 AND NOT EXISTS (SELECT 1 FROM lca_skip s WHERE s.a = r.k AND s.b / r.y > 1)'); -- ... the count by cells with the pages priced low, as in 9. SET random_page_cost = 0.1; SET seq_page_cost = 0.1; SELECT lca('SELECT tier, count(*) FROM lca_tiered t WHERE t.y IN (1, 2, 3) AND NOT EXISTS (SELECT 1 FROM lca_skip s WHERE s.a = t.k AND s.b / t.y > 1) GROUP BY tier'); RESET random_page_cost; RESET seq_page_cost; RESET max_parallel_workers_per_gather; RESET parallel_setup_cost; RESET parallel_tuple_cost; RESET min_parallel_table_scan_size; RESET min_parallel_index_scan_size; RESET pg_lion.parallel_range_keys; DROP VIEW lca_tiered; DROP VIEW lca_scored; -- ---------- 11. past work_mem ---------- -- Nothing the node keeps grows without bound in memory (DESIGN.md §27, -- "The anti join within work_mem"): the child's rows sorted by key, a key's -- inner rows, and the losses of the groups or the cells - the count's rows -- then held back beside them - and the rows taken away beside a parallel -- count by cells go to disk past work_mem or hash_mem, and the answers are -- core's. -- lca_big has 60,000 rows: k has 12,000 values of 5 rows each, the rows of -- a key all of one group of g's 6,000 and of several cells of c1 and c2, of -- 50 values each; gn is g with NULL on every 7th row, t a text of 3,000 -- values, x has 10. lca_many's keys are every value of k, beside 5,000 -- more rows of key 7 whose b differ, a hundred of them twice. CREATE TABLE lca_big ( id int PRIMARY KEY, k int NOT NULL, g int NOT NULL, gn int, t text NOT NULL, c1 int NOT NULL, c2 int NOT NULL, x int NOT NULL, pad text NOT NULL ) WITH (autovacuum_enabled = off); INSERT INTO lca_big SELECT i, i % 12000, i % 6000, CASE WHEN i % 7 = 0 THEN NULL ELSE i % 6000 END, 'v' || (i % 3000), i % 50, (i / 50) % 50, (i / 1000) % 10, repeat('p', 20) FROM generate_series(1, 60000) i; CREATE INDEX lca_big_k ON lca_big (k); CREATE INDEX lca_big_g ON lca_big USING lion (g); CREATE INDEX lca_big_gn ON lca_big USING lion (gn); CREATE INDEX lca_big_t ON lca_big USING lion (t); CREATE INDEX lca_big_c1 ON lca_big USING lion (c1); CREATE INDEX lca_big_c2 ON lca_big USING lion (c2); CREATE INDEX lca_big_x ON lca_big USING lion (x); CREATE TABLE lca_many (a int, b int); INSERT INTO lca_many SELECT i, i FROM generate_series(0, 11999) i; INSERT INTO lca_many SELECT 7, i FROM generate_series(1, 5000) i; INSERT INTO lca_many SELECT 7, i FROM generate_series(1, 100) i; VACUUM (FREEZE, ANALYZE) lca_big, lca_many; -- an inner side the planner takes for ten rows CREATE FUNCTION lca_keys(n int) RETURNS SETOF int ROWS 10 LANGUAGE plpgsql AS $$ BEGIN RETURN QUERY SELECT generate_series(0, n - 1); END $$; /* What of the anti join went to disk, from EXPLAIN ANALYZE, joins disabled. */ CREATE FUNCTION lca_spilled(q text) RETURNS text LANGUAGE plpgsql AS $$ DECLARE ln text; BEGIN PERFORM set_config('enable_hashjoin', 'off', true); PERFORM set_config('enable_mergejoin', 'off', true); PERFORM set_config('enable_nestloop', 'off', true); FOR ln IN EXECUTE 'EXPLAIN (ANALYZE, COSTS OFF, TIMING OFF, SUMMARY OFF, BUFFERS OFF) ' || q LOOP IF btrim(ln) LIKE 'Join Spilled:%' THEN RETURN btrim(substr(btrim(ln), length('Join Spilled:') + 1)); END IF; END LOOP; RETURN 'nothing'; END $$; /* * A query with an ORDER BY through the pushdown, joins disabled, in the order * it gives its rows, against core's with the pushdown off: the rows out of * their place. */ CREATE FUNCTION lca_ordered(q text) RETURNS text LANGUAGE plpgsql AS $$ DECLARE rec record; n int := 0; got text[] := '{}'; want text[] := '{}'; nbad int := 0; BEGIN PERFORM set_config('enable_hashjoin', 'off', true); PERFORM set_config('enable_mergejoin', 'off', true); PERFORM set_config('enable_nestloop', 'off', true); FOR rec IN EXECUTE q LOOP got := got || rec::text; END LOOP; PERFORM set_config('pg_lion.enable_count_pushdown', 'off', true); PERFORM set_config('enable_hashjoin', 'on', true); PERFORM set_config('enable_mergejoin', 'on', true); PERFORM set_config('enable_nestloop', 'on', true); FOR rec IN EXECUTE q LOOP want := want || rec::text; END LOOP; PERFORM set_config('pg_lion.enable_count_pushdown', 'on', true); IF cardinality(got) <> cardinality(want) THEN RETURN format('MISMATCH: %s rows, not %s', cardinality(got), cardinality(want)); END IF; FOR n IN 1 .. cardinality(want) LOOP IF got[n] IS DISTINCT FROM want[n] THEN nbad := nbad + 1; END IF; END LOOP; IF nbad <> 0 THEN RETURN format('MISMATCH: %s rows out of place', nbad); END IF; RETURN format('in order, %s rows', cardinality(want)); END $$; SET work_mem = '64kB'; SET hash_mem_multiplier = 1; -- the child's 17,100 rows sorted by key on disk SELECT * FROM lca_explain('SELECT count(*) FROM lca_big r WHERE r.x < 5 AND NOT EXISTS (SELECT 1 FROM lca_many s WHERE s.a = r.k)', 'ANALYZE, COSTS OFF, TIMING OFF, SUMMARY OFF, BUFFERS OFF') AS ln WHERE ln ~ '(Custom Scan|Join (Child|Keys|Rows|Spilled))'; SELECT lca('SELECT count(*) FROM lca_big r WHERE r.x < 5 AND NOT EXISTS (SELECT 1 FROM lca_many s WHERE s.a = r.k)'); SELECT lca('SELECT count(*) FROM lca_big r WHERE r.x < 5 AND NOT EXISTS (SELECT 1 FROM lca_many s WHERE s.a = r.k AND s.a % 3 <> 0)'); -- ... and an inner side the planner takes for ten rows, with nothing disabled SELECT lca_pick('SELECT count(*) FROM lca_big r WHERE r.x = 3 AND NOT EXISTS (SELECT 1 FROM lca_keys(12000) s(a) WHERE s.a = r.k)'); SELECT lca('SELECT count(*) FROM lca_big r WHERE r.x = 3 AND NOT EXISTS (SELECT 1 FROM lca_keys(12000) s(a) WHERE s.a = r.k)'); SELECT lca_spilled('SELECT count(*) FROM lca_big r WHERE r.x = 3 AND NOT EXISTS (SELECT 1 FROM lca_keys(12000) s(a) WHERE s.a = r.k)'); -- a key's 5,000 inner rows, those alike kept once, on disk: each row of key 7 -- tested against them in turn, b past a bound that grows with x, which -- one of them finds no row beyond SELECT lca_spilled('SELECT count(*) FROM lca_big r WHERE NOT EXISTS (SELECT 1 FROM lca_many s WHERE s.a = r.k AND s.b > r.g + r.x * 700)'); SELECT lca('SELECT count(*) FROM lca_big r WHERE NOT EXISTS (SELECT 1 FROM lca_many s WHERE s.a = r.k AND s.b > r.g + r.x * 700)'); SELECT lca('SELECT count(*) FROM lca_big r WHERE r.g = 7 AND NOT EXISTS (SELECT 1 FROM lca_many s WHERE s.a = r.k AND s.b > r.g + r.x * 700)'); SELECT lca_counters('SELECT count(*) FROM lca_big r WHERE r.g = 7 AND NOT EXISTS (SELECT 1 FROM lca_many s WHERE s.a = r.k AND s.b > r.g + r.x * 700)'); -- the losses of 6,000 groups past hash_mem, held back with the count's rows -- and merged on disk: the groups of g under 3,000 lose every row and are no -- row, those above it half of theirs SELECT lca_spilled('SELECT r.g, count(*) FROM lca_big r WHERE NOT EXISTS (SELECT 1 FROM lca_many s WHERE s.a = r.k AND s.a < 9000) GROUP BY r.g'); SELECT lca('SELECT r.g, count(*) FROM lca_big r WHERE NOT EXISTS (SELECT 1 FROM lca_many s WHERE s.a = r.k AND s.a < 9000) GROUP BY r.g'); SELECT * FROM lca_val('SELECT count(*), sum(n), min(n), max(n) FROM (SELECT r.g, count(*) AS n FROM lca_big r WHERE NOT EXISTS (SELECT 1 FROM lca_many s WHERE s.a = r.k AND s.a < 9000) GROUP BY r.g) q'); -- ... with a WHERE, by two columns, by a column with NULLs and by a text SELECT lca('SELECT r.g, count(*) FROM lca_big r WHERE r.x IN (1, 4, 6) AND NOT EXISTS (SELECT 1 FROM lca_many s WHERE s.a = r.k AND s.a < 9000) GROUP BY r.g'); SELECT lca('SELECT r.g, r.x, count(*) FROM lca_big r WHERE NOT EXISTS (SELECT 1 FROM lca_many s WHERE s.a = r.k AND s.a % 3 <> 0) GROUP BY r.g, r.x'); SELECT lca('SELECT r.gn, count(*) FROM lca_big r WHERE NOT EXISTS (SELECT 1 FROM lca_many s WHERE s.a = r.k AND s.a < 9000) GROUP BY r.gn'); SELECT lca('SELECT r.t, count(*) FROM lca_big r WHERE NOT EXISTS (SELECT 1 FROM lca_many s WHERE s.a = r.k AND s.a % 4 = 1) GROUP BY r.t'); SELECT lca_spilled('SELECT r.t, count(*) FROM lca_big r WHERE NOT EXISTS (SELECT 1 FROM lca_many s WHERE s.a = r.k AND s.a % 4 = 1) GROUP BY r.t'); -- ... the HAVING on the counts less the rows lost SELECT lca('SELECT r.g, count(*) FROM lca_big r WHERE NOT EXISTS (SELECT 1 FROM lca_many s WHERE s.a = r.k AND s.a % 3 <> 0) GROUP BY r.g HAVING count(*) > 5'); -- ... and the groups in the order the plan claims, no Sort above the node SELECT * FROM lca_explain('SELECT r.g, count(*) FROM lca_big r WHERE NOT EXISTS (SELECT 1 FROM lca_many s WHERE s.a = r.k AND s.a < 9000) GROUP BY r.g ORDER BY r.g') AS ln WHERE ln !~ '^\s{6}'; SELECT lca_ordered('SELECT r.g, count(*) FROM lca_big r WHERE NOT EXISTS (SELECT 1 FROM lca_many s WHERE s.a = r.k AND s.a < 9000) GROUP BY r.g ORDER BY r.g'); SELECT lca_ordered('SELECT r.g, count(*) FROM lca_big r WHERE NOT EXISTS (SELECT 1 FROM lca_many s WHERE s.a = r.k AND s.a % 3 <> 0) GROUP BY r.g HAVING count(*) > 5 ORDER BY r.g'); -- a rescan under a correlated subquery: each run's sorts begun again SELECT lca('SELECT o.v, (SELECT count(*) FROM lca_big r WHERE r.x = o.v AND NOT EXISTS (SELECT 1 FROM lca_many s WHERE s.a = r.k AND s.a % 3 <> 0)) FROM (VALUES (3), (1), (3)) o(v)'); SELECT lca('SELECT o.v, (SELECT count(*) FROM lca_big r WHERE r.x = o.v AND NOT EXISTS (SELECT 1 FROM lca_many s WHERE s.a = r.k AND s.a < 9000) GROUP BY r.g ORDER BY 1 DESC LIMIT 1) FROM (VALUES (3), (1), (3)) o(v)'); -- the losses of 2,500 cells past hash_mem, the tally's counts held back -- with them CREATE TEMP TABLE lca_bigcells AS SELECT format('SELECT CASE %s END AS u, CASE %s END AS v, count(*) FROM lca_big r WHERE NOT EXISTS (SELECT 1 FROM lca_many s WHERE s.a = r.k AND s.a %% 4 <> 0) GROUP BY 1, 2', string_agg(format('WHEN r.c1 = %s THEN %s', i, i), ' ' ORDER BY i), string_agg(format('WHEN r.c2 = %s THEN %s', i, i), ' ' ORDER BY i)) AS q FROM generate_series(0, 49) i; SELECT ln FROM lca_bigcells, lca_explain(q) AS ln WHERE ln ~ '^\s*(Group Strategy|Cells|Join Type):'; SELECT lca_spilled(q) FROM lca_bigcells; SELECT lca(q) FROM lca_bigcells; SELECT lca(replace(q, 'GROUP BY 1, 2', 'GROUP BY 1, 2 HAVING count(*) > 20')) FROM lca_bigcells; -- in parallel: the count divided, and the rows taken away beside a count -- by cells, every participant's, sorted by range on disk SET max_parallel_workers_per_gather = 2; 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 pg_lion.parallel_range_keys = 1; SELECT ln FROM lca_explain('SELECT count(*) FROM lca_big r WHERE r.x = 3 AND length(r.pad) > 0 AND NOT EXISTS (SELECT 1 FROM lca_many s WHERE s.a = r.k)') AS ln WHERE ln ~ 'Parallel'; SELECT lca('SELECT count(*) FROM lca_big r WHERE r.x = 3 AND length(r.pad) > 0 AND NOT EXISTS (SELECT 1 FROM lca_many s WHERE s.a = r.k)'); SELECT lca_spilled('SELECT count(*) FROM lca_big r WHERE r.x = 3 AND length(r.pad) > 0 AND NOT EXISTS (SELECT 1 FROM lca_many s WHERE s.a = r.k)'); SELECT lca('SELECT count(*) FROM lca_big r WHERE r.x IN (4, 8) AND length(r.pad) > 0 AND NOT EXISTS (SELECT 1 FROM lca_many s WHERE s.a = r.k AND s.b > r.g + r.x * 700)'); SELECT lca_spilled('SELECT count(*) FROM lca_big r WHERE r.x IN (4, 8) AND length(r.pad) > 0 AND NOT EXISTS (SELECT 1 FROM lca_many s WHERE s.a = r.k AND s.b > r.g + r.x * 700)'); -- ... and beside a count by cells, without the leader taking part: every -- participant's run of the lookups, which find every row of the table, is -- then a worker's to itself (lion_add_parallel_cells_path()) SET parallel_leader_participation = off; SELECT ln FROM lca_bigcells, lca_explain(q) AS ln WHERE ln ~ 'Parallel'; SELECT lca(q) FROM lca_bigcells; SELECT lca_spilled(q) ~ 'keys.*ranges' AS spilled FROM lca_bigcells; -- ... the rows subtracted, every participant's, are the serial node's SELECT ln FROM lca_bigcells, lca_explain(q, 'ANALYZE, COSTS OFF, TIMING OFF, SUMMARY OFF, BUFFERS OFF') AS ln WHERE ln ~ 'Join Rows Subtracted'; SET max_parallel_workers_per_gather = 0; SELECT ln FROM lca_bigcells, lca_explain(q, 'ANALYZE, COSTS OFF, TIMING OFF, SUMMARY OFF, BUFFERS OFF') AS ln WHERE ln ~ 'Join Rows Subtracted'; RESET parallel_leader_participation; RESET max_parallel_workers_per_gather; RESET parallel_setup_cost; RESET parallel_tuple_cost; RESET min_parallel_table_scan_size; RESET min_parallel_index_scan_size; RESET pg_lion.parallel_range_keys; DROP TABLE lca_bigcells; RESET work_mem; RESET hash_mem_multiplier; -- within work_mem, nothing spilled SELECT lca_spilled('SELECT r.g, count(*) FROM lca_big r WHERE NOT EXISTS (SELECT 1 FROM lca_many s WHERE s.a = r.k AND s.a < 9000) GROUP BY r.g'); DROP FUNCTION lca_keys(int); DROP FUNCTION lca_spilled(text); DROP FUNCTION lca_ordered(text); DROP TABLE lca_big, lca_many; DROP TABLE lca_rows, lca_skip, lca_num, lca_tag; DROP FUNCTION lca(text); DROP FUNCTION lca_val(text); DROP FUNCTION lca_pick(text); DROP FUNCTION lca_prep(text, text); DROP FUNCTION lca_counters(text); DROP FUNCTION lca_explain(text, text);