tschwarzinger opened a new issue, #27555:
URL: https://github.com/apache/datafusion/issues/27555
### 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
https://github.com/apache/datafusion/pull/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 `GroupValuesColumn` assign ids to new groups in row order. This may
affects the hot aggregation path.
- Do more book keeping in `DistinctDeduplicator` of `RecursiveQuery` to
address this
### Willingness to contribute
None
--
This is an automated message from the Apache Git Service.
To respond to the message, please log on to GitHub and use the
URL above to go to the specific comment.
To unsubscribe, e-mail: [email protected]
For queries about this service, please contact Infrastructure at:
[email protected]
---------------------------------------------------------------------
To unsubscribe, e-mail: [email protected]
For additional commands, e-mail: [email protected]