Description:
INTERSECT ALL returns too few rows when its left operand is larger than
set_operations_buffer_size (default 256 KiB), so that the hash set operation
spills to chunk files. Every duplicate counted into the in-memory hash map
before the spill collapses to a single row. Duplicates that arrive after the
spill are counted correctly.
With 6000 rows per side, one third of them a repeated value, at stock settings:
INTERSECT ALL 1389 rows expected 2000 WRONG
INTERSECT DISTINCT 1 row expected 1 correct
The same query is correct if either the spill or the hash algorithm is taken
out of play:
set_operations_buffer_size = 33554432 (32 MiB) 2000 correct
optimizer_switch = 'hash_set_operations=off' 2000 correct
set_operations_buffer_size = DEFAULT (256 KiB) 1389 WRONG
Deterministic: 5 of 5 identical runs, and identical results on 8.4.11, 9.7.2
and 26.7.0.
EXCEPT ALL is affected by the same defect. It is visible whenever the right
operand has fewer copies of a value than the left: with 500 copies of 'dup'
plus 6000 unique rows on the left and a single 'dup' on the right, EXCEPT ALL
should return 6499 rows but returns 6000, because the left's 500 copies had
already collapsed to 1. INTERSECT DISTINCT and EXCEPT DISTINCT are unaffected,
since only the ALL forms carry per-row duplicate counts.
THE TRIGGER IS SMALL. At the shipped 256 KiB buffer, with 150-byte rows:
rows per side 500 1000 1500 2000 3000 4000 6000
returned 166 333 500 55 389 722 1389
expected 166 333 500 666 1000 1333 2000
So roughly 300 KB of left operand is enough. That is an ordinary size for an
analytics query, and nothing in the query or schema hints at it.
LOSS IS NOT MONOTONIC in the buffer size, which makes it easy to miss in
testing. It peaks just below the size at which the spill stops happening
(6000 rows/side, 2000 repeats, expected 2000):
buffer 16K 32K 64K 128K 256K* 512K 1M 32M
returned 2000 2000 1845 1689 1389 755 2000 2000
(* = shipped default)
Identical on 9.7.2 and 26.7.0. A very small buffer is correct here because the
spill happens early enough that most duplicates arrive through the IF chunk
path, which counts them properly.
MECHANISM (empirical). Controlled test at the default buffer: the left operand
carries k copies of 'dup' either before or after the 6000 unique rows that
force the spill, and the right operand is k copies of 'dup':
k = 500 result expected
copies read BEFORE the spill 1 500
copies read AFTER the spill 500 500
Every count accumulated in memory before the spill is lost. In
sql/iterators/composite_iterators.cc, handle_hash_map_full() spreads the
deduplicated map to the HF chunk files (spread_hash_map_to_HF_chunk_files).
The design comment states that HF rows "already have counters" and are re-read
through the shorter load_HF_row_into_hash_map path. The observed behaviour is
that those counters do not survive that round trip: they come back as 1, as if
reset by the left-pass "counter := 1" logic.
VERSION BOUNDARY. 8.0.46 is correct (returns 2000). It supports INTERSECT ALL
but has neither set_operations_buffer_size nor hash_set_operations ("Unknown
system variable"), so it uses the temporary-table algorithm. This defect
therefore arrived with hash set operations and is present in every release
that has them.
How to repeat:
-- No tables are needed; the recursive CTE builds both operands. Run against a
-- stock server, e.g.: mysql -uroot -p test < this.sql
-- 'dup' occurs 2000 times on each side and every other value is unique to its
-- side, so INTERSECT ALL must return exactly 2000 rows.
SET SESSION cte_max_recursion_depth = 1000000;
-- 1. Shipped default (set_operations_buffer_size = 256 KiB): WRONG
SET SESSION set_operations_buffer_size = DEFAULT;
WITH RECURSIVE s(n) AS (SELECT 1 UNION ALL SELECT n + 1 FROM s WHERE n < 6000),
l AS (SELECT IF(n % 3 = 0, 'dup', concat('L', n, repeat('x', 150))) AS h FROM s),
r AS (SELECT IF(n % 3 = 0, 'dup', concat('R', n, repeat('y', 150))) AS h FROM s)
SELECT 'default 256K' AS arm, count(*) AS got, 2000 AS expected
FROM (SELECT h FROM l INTERSECT ALL SELECT h FROM r) x;
-- got 1389, expected 2000
-- 2. Same data, buffer large enough that no spill occurs: correct
SET SESSION set_operations_buffer_size = 33554432;
WITH RECURSIVE s(n) AS (SELECT 1 UNION ALL SELECT n + 1 FROM s WHERE n < 6000),
l AS (SELECT IF(n % 3 = 0, 'dup', concat('L', n, repeat('x', 150))) AS h FROM s),
r AS (SELECT IF(n % 3 = 0, 'dup', concat('R', n, repeat('y', 150))) AS h FROM s)
SELECT '32M' AS arm, count(*) AS got, 2000 AS expected
FROM (SELECT h FROM l INTERSECT ALL SELECT h FROM r) x;
-- got 2000
-- 3. Same data, hash set operations disabled: correct
SET SESSION set_operations_buffer_size = DEFAULT;
SET SESSION optimizer_switch = 'hash_set_operations=off';
WITH RECURSIVE s(n) AS (SELECT 1 UNION ALL SELECT n + 1 FROM s WHERE n < 6000),
l AS (SELECT IF(n % 3 = 0, 'dup', concat('L', n, repeat('x', 150))) AS h FROM s),
r AS (SELECT IF(n % 3 = 0, 'dup', concat('R', n, repeat('y', 150))) AS h FROM s)
SELECT 'hash off' AS arm, count(*) AS got, 2000 AS expected
FROM (SELECT h FROM l INTERSECT ALL SELECT h FROM r) x;
-- got 2000
SET SESSION optimizer_switch = 'hash_set_operations=on';
-- 4. The before/after-spill demonstration of the mechanism:
SET SESSION set_operations_buffer_size = DEFAULT;
-- 500 copies of 'dup' BEFORE the rows that force the spill -> returns 1
WITH RECURSIVE s(n) AS (SELECT 1 UNION ALL SELECT n+1 FROM s WHERE n < 6000),
k(n) AS (SELECT 1 UNION ALL SELECT n+1 FROM k WHERE n < 500),
l AS (SELECT 'dup' AS h FROM k UNION ALL SELECT concat('L',n,repeat('x',150)) FROM s),
r AS (SELECT 'dup' AS h FROM k)
SELECT 'dups before spill' AS arm, count(*) AS got, 500 AS expected
FROM (SELECT h FROM l INTERSECT ALL SELECT h FROM r) x;
-- got 1, expected 500
-- the same 500 copies AFTER those rows -> correct
WITH RECURSIVE s(n) AS (SELECT 1 UNION ALL SELECT n+1 FROM s WHERE n < 6000),
k(n) AS (SELECT 1 UNION ALL SELECT n+1 FROM k WHERE n < 500),
l AS (SELECT concat('L',n,repeat('x',150)) AS h FROM s UNION ALL SELECT 'dup' FROM k),
r AS (SELECT 'dup' AS h FROM k)
SELECT 'dups after spill' AS arm, count(*) AS got, 500 AS expected
FROM (SELECT h FROM l INTERSECT ALL SELECT h FROM r) x;
-- got 500
-- EXCEPT ALL, same shape: left keeps 500 'dup', right removes one
WITH RECURSIVE s(n) AS (SELECT 1 UNION ALL SELECT n+1 FROM s WHERE n < 6000),
k(n) AS (SELECT 1 UNION ALL SELECT n+1 FROM k WHERE n < 500),
l AS (SELECT 'dup' AS h FROM k UNION ALL SELECT concat('L',n,repeat('x',150)) FROM s),
r AS (SELECT 'dup' AS h)
SELECT 'EXCEPT ALL' AS arm, count(*) AS got, 6499 AS expected
FROM (SELECT h FROM l EXCEPT ALL SELECT h FROM r) x;
-- got 6000, expected 6499
-- 5. A plain-table form behaves the same, including with NULL as the repeated value:
CREATE TABLE sl (h VARCHAR(255)); CREATE TABLE sr (h VARCHAR(255));
INSERT INTO sl WITH RECURSIVE s(n) AS (SELECT 1 UNION ALL SELECT n + 1 FROM s WHERE n < 6000)
SELECT IF(n % 3 = 0, NULL, concat('L', n, repeat('x', 150))) FROM s;
INSERT INTO sr WITH RECURSIVE s(n) AS (SELECT 1 UNION ALL SELECT n + 1 FROM s WHERE n < 6000)
SELECT IF(n % 3 = 0, NULL, concat('R', n, repeat('y', 150))) FROM s;
SET SESSION set_operations_buffer_size = DEFAULT;
SELECT count(*) FROM (SELECT h FROM sl INTERSECT ALL SELECT h FROM sr) x;
-- got 1406
SELECT sum(least(l.n, r.n)) FROM
(SELECT h, count(*) n FROM sl GROUP BY h) l
JOIN (SELECT h, count(*) n FROM sr GROUP BY h) r ON l.h <=> r.h;
-- ground truth 2000
-- Reproduced in the official Docker images, e.g.:
-- docker run -d --name my -e MYSQL_ROOT_PASSWORD=root -e MYSQL_DATABASE=t mysql:26.7
-- docker exec -i my mysql -uroot -proot t < repro.sql
Suggested fix:
Preserve the per-row duplicate counter when a hash-map row is written to, and
re-read from, the HF chunk files. Either carry set_counter through
spread_hash_map_to_HF_chunk_files / load_HF_row_into_hash_map explicitly, or,
if HF rows are meant to re-enter the map through the left-pass path, make that
path add the stored counter rather than assigning 1.
A regression test would need a left operand larger than
set_operations_buffer_size containing repeated values in the portion read
before the spill. The existing set-operation tests appear to stay under the
buffer, since the defect is invisible below it.
Description: INTERSECT ALL returns too few rows when its left operand is larger than set_operations_buffer_size (default 256 KiB), so that the hash set operation spills to chunk files. Every duplicate counted into the in-memory hash map before the spill collapses to a single row. Duplicates that arrive after the spill are counted correctly. With 6000 rows per side, one third of them a repeated value, at stock settings: INTERSECT ALL 1389 rows expected 2000 WRONG INTERSECT DISTINCT 1 row expected 1 correct The same query is correct if either the spill or the hash algorithm is taken out of play: set_operations_buffer_size = 33554432 (32 MiB) 2000 correct optimizer_switch = 'hash_set_operations=off' 2000 correct set_operations_buffer_size = DEFAULT (256 KiB) 1389 WRONG Deterministic: 5 of 5 identical runs, and identical results on 8.4.11, 9.7.2 and 26.7.0. EXCEPT ALL is affected by the same defect. It is visible whenever the right operand has fewer copies of a value than the left: with 500 copies of 'dup' plus 6000 unique rows on the left and a single 'dup' on the right, EXCEPT ALL should return 6499 rows but returns 6000, because the left's 500 copies had already collapsed to 1. INTERSECT DISTINCT and EXCEPT DISTINCT are unaffected, since only the ALL forms carry per-row duplicate counts. THE TRIGGER IS SMALL. At the shipped 256 KiB buffer, with 150-byte rows: rows per side 500 1000 1500 2000 3000 4000 6000 returned 166 333 500 55 389 722 1389 expected 166 333 500 666 1000 1333 2000 So roughly 300 KB of left operand is enough. That is an ordinary size for an analytics query, and nothing in the query or schema hints at it. LOSS IS NOT MONOTONIC in the buffer size, which makes it easy to miss in testing. It peaks just below the size at which the spill stops happening (6000 rows/side, 2000 repeats, expected 2000): buffer 16K 32K 64K 128K 256K* 512K 1M 32M returned 2000 2000 1845 1689 1389 755 2000 2000 (* = shipped default) Identical on 9.7.2 and 26.7.0. A very small buffer is correct here because the spill happens early enough that most duplicates arrive through the IF chunk path, which counts them properly. MECHANISM (empirical). Controlled test at the default buffer: the left operand carries k copies of 'dup' either before or after the 6000 unique rows that force the spill, and the right operand is k copies of 'dup': k = 500 result expected copies read BEFORE the spill 1 500 copies read AFTER the spill 500 500 Every count accumulated in memory before the spill is lost. In sql/iterators/composite_iterators.cc, handle_hash_map_full() spreads the deduplicated map to the HF chunk files (spread_hash_map_to_HF_chunk_files). The design comment states that HF rows "already have counters" and are re-read through the shorter load_HF_row_into_hash_map path. The observed behaviour is that those counters do not survive that round trip: they come back as 1, as if reset by the left-pass "counter := 1" logic. VERSION BOUNDARY. 8.0.46 is correct (returns 2000). It supports INTERSECT ALL but has neither set_operations_buffer_size nor hash_set_operations ("Unknown system variable"), so it uses the temporary-table algorithm. This defect therefore arrived with hash set operations and is present in every release that has them. How to repeat: -- No tables are needed; the recursive CTE builds both operands. Run against a -- stock server, e.g.: mysql -uroot -p test < this.sql -- 'dup' occurs 2000 times on each side and every other value is unique to its -- side, so INTERSECT ALL must return exactly 2000 rows. SET SESSION cte_max_recursion_depth = 1000000; -- 1. Shipped default (set_operations_buffer_size = 256 KiB): WRONG SET SESSION set_operations_buffer_size = DEFAULT; WITH RECURSIVE s(n) AS (SELECT 1 UNION ALL SELECT n + 1 FROM s WHERE n < 6000), l AS (SELECT IF(n % 3 = 0, 'dup', concat('L', n, repeat('x', 150))) AS h FROM s), r AS (SELECT IF(n % 3 = 0, 'dup', concat('R', n, repeat('y', 150))) AS h FROM s) SELECT 'default 256K' AS arm, count(*) AS got, 2000 AS expected FROM (SELECT h FROM l INTERSECT ALL SELECT h FROM r) x; -- got 1389, expected 2000 -- 2. Same data, buffer large enough that no spill occurs: correct SET SESSION set_operations_buffer_size = 33554432; WITH RECURSIVE s(n) AS (SELECT 1 UNION ALL SELECT n + 1 FROM s WHERE n < 6000), l AS (SELECT IF(n % 3 = 0, 'dup', concat('L', n, repeat('x', 150))) AS h FROM s), r AS (SELECT IF(n % 3 = 0, 'dup', concat('R', n, repeat('y', 150))) AS h FROM s) SELECT '32M' AS arm, count(*) AS got, 2000 AS expected FROM (SELECT h FROM l INTERSECT ALL SELECT h FROM r) x; -- got 2000 -- 3. Same data, hash set operations disabled: correct SET SESSION set_operations_buffer_size = DEFAULT; SET SESSION optimizer_switch = 'hash_set_operations=off'; WITH RECURSIVE s(n) AS (SELECT 1 UNION ALL SELECT n + 1 FROM s WHERE n < 6000), l AS (SELECT IF(n % 3 = 0, 'dup', concat('L', n, repeat('x', 150))) AS h FROM s), r AS (SELECT IF(n % 3 = 0, 'dup', concat('R', n, repeat('y', 150))) AS h FROM s) SELECT 'hash off' AS arm, count(*) AS got, 2000 AS expected FROM (SELECT h FROM l INTERSECT ALL SELECT h FROM r) x; -- got 2000 SET SESSION optimizer_switch = 'hash_set_operations=on'; -- 4. The before/after-spill demonstration of the mechanism: SET SESSION set_operations_buffer_size = DEFAULT; -- 500 copies of 'dup' BEFORE the rows that force the spill -> returns 1 WITH RECURSIVE s(n) AS (SELECT 1 UNION ALL SELECT n+1 FROM s WHERE n < 6000), k(n) AS (SELECT 1 UNION ALL SELECT n+1 FROM k WHERE n < 500), l AS (SELECT 'dup' AS h FROM k UNION ALL SELECT concat('L',n,repeat('x',150)) FROM s), r AS (SELECT 'dup' AS h FROM k) SELECT 'dups before spill' AS arm, count(*) AS got, 500 AS expected FROM (SELECT h FROM l INTERSECT ALL SELECT h FROM r) x; -- got 1, expected 500 -- the same 500 copies AFTER those rows -> correct WITH RECURSIVE s(n) AS (SELECT 1 UNION ALL SELECT n+1 FROM s WHERE n < 6000), k(n) AS (SELECT 1 UNION ALL SELECT n+1 FROM k WHERE n < 500), l AS (SELECT concat('L',n,repeat('x',150)) AS h FROM s UNION ALL SELECT 'dup' FROM k), r AS (SELECT 'dup' AS h FROM k) SELECT 'dups after spill' AS arm, count(*) AS got, 500 AS expected FROM (SELECT h FROM l INTERSECT ALL SELECT h FROM r) x; -- got 500 -- EXCEPT ALL, same shape: left keeps 500 'dup', right removes one WITH RECURSIVE s(n) AS (SELECT 1 UNION ALL SELECT n+1 FROM s WHERE n < 6000), k(n) AS (SELECT 1 UNION ALL SELECT n+1 FROM k WHERE n < 500), l AS (SELECT 'dup' AS h FROM k UNION ALL SELECT concat('L',n,repeat('x',150)) FROM s), r AS (SELECT 'dup' AS h) SELECT 'EXCEPT ALL' AS arm, count(*) AS got, 6499 AS expected FROM (SELECT h FROM l EXCEPT ALL SELECT h FROM r) x; -- got 6000, expected 6499 -- 5. A plain-table form behaves the same, including with NULL as the repeated value: CREATE TABLE sl (h VARCHAR(255)); CREATE TABLE sr (h VARCHAR(255)); INSERT INTO sl WITH RECURSIVE s(n) AS (SELECT 1 UNION ALL SELECT n + 1 FROM s WHERE n < 6000) SELECT IF(n % 3 = 0, NULL, concat('L', n, repeat('x', 150))) FROM s; INSERT INTO sr WITH RECURSIVE s(n) AS (SELECT 1 UNION ALL SELECT n + 1 FROM s WHERE n < 6000) SELECT IF(n % 3 = 0, NULL, concat('R', n, repeat('y', 150))) FROM s; SET SESSION set_operations_buffer_size = DEFAULT; SELECT count(*) FROM (SELECT h FROM sl INTERSECT ALL SELECT h FROM sr) x; -- got 1406 SELECT sum(least(l.n, r.n)) FROM (SELECT h, count(*) n FROM sl GROUP BY h) l JOIN (SELECT h, count(*) n FROM sr GROUP BY h) r ON l.h <=> r.h; -- ground truth 2000 -- Reproduced in the official Docker images, e.g.: -- docker run -d --name my -e MYSQL_ROOT_PASSWORD=root -e MYSQL_DATABASE=t mysql:26.7 -- docker exec -i my mysql -uroot -proot t < repro.sql Suggested fix: Preserve the per-row duplicate counter when a hash-map row is written to, and re-read from, the HF chunk files. Either carry set_counter through spread_hash_map_to_HF_chunk_files / load_HF_row_into_hash_map explicitly, or, if HF rows are meant to re-enter the map through the left-pass path, make that path add the stored counter rather than assigning 1. A regression test would need a left operand larger than set_operations_buffer_size containing repeated values in the portion read before the spill. The existing set-operation tests appear to stay under the buffer, since the defect is invisible below it.