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]

Reply via email to