Repository navigation
Description
Describe the bug
UNION (distinct) recursive CTEs can silently drop rows when two distinct rows in a batch have the same hash and the deduplication uses GroupValuesColumn.
DistinctDeduplicator::deduplicate (datafusion/physical-plan/src/recursive_query.rs) keeps a row only if its group id is greater than all ids kept before it in the batch (new_groups_mask), i.e., it assumes new group ids are assigned in row order. GroupValuesColumn::vectorized_intern does not do that: rows whose hash matches an existing group but whose values differ are only interned in scalarized_intern_remaining, after all other new rows have received ids.
For example, in VALUES ('x', 'a', 'b'), ('x', 'b', 'a'), ('x', 'c', 'd'), the first two rows have the same hash: combine_hashes has a hash collision for the first two rows. The interned ids are [0, 2, 1]:
- 0:
('x', 'a', 'b') - 2:
('x', 'b', 'a'), which collides with row 0 and gets its id in the scalar pass - 1:
('x', 'c', 'd'), which has a different hash and gets its id in the vectorized pass
After keeping id 2, the mask drops id 1, so ('x', 'c', 'd') is treated as a duplicate.
This matters for graph-like workloads, e.g., computing the transitive closure of edges (friends of friends of friends ...).
To Reproduce
query TTT rowsort
WITH RECURSIVE t AS (
SELECT arrow_cast(g, 'Utf8') AS g, arrow_cast(s, 'Utf8') AS s, arrow_cast(o, 'Utf8') AS o
FROM (VALUES ('x', 'a', 'b'), ('x', 'b', 'a'), ('x', 'c', 'd')) edges(g, s, o)
UNION
SELECT * FROM t WHERE false
)
SELECT * FROM t
----
x a b
x b a
🌩️ <--- x c d is missing even though it's distinct from the other 2
Expected behavior
query TTT rowsort
WITH RECURSIVE t AS (
SELECT arrow_cast(g, 'Utf8') AS g, arrow_cast(s, 'Utf8') AS s, arrow_cast(o, 'Utf8') AS o
FROM (VALUES ('x', 'a', 'b'), ('x', 'b', 'a'), ('x', 'c', 'd')) edges(g, s, o)
UNION
SELECT * FROM t WHERE false
)
SELECT * FROM t
----
x a b
x b a
x c d
Additional context
#23523 could make this issue worse as more data types are affected
The GroupValues docs say that new rows get "the next available group id", which can be read as a promise of row order, but GroupValuesColumn breaks it on purpose to keep the vectorized path fast.
Two possible fixes:
- Make
GroupValuesColumnassign ids to new groups in row order. This may affects the hot aggregation path. - Do more book keeping in
DistinctDeduplicatorofRecursiveQueryto address this
Willingness to contribute
I can file a fix for option 2). I think Option 1) is a bit more involved.
Activity