Skip to content

Distinct RecursiveQuery produces wrong results for rows that have hash collisions #27555

Description

@tschwarzinger

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:

  1. Make GroupValuesColumn assign ids to new groups in row order. This may affects the hot aggregation path.
  2. Do more book keeping in DistinctDeduplicator of RecursiveQuery to address this

Willingness to contribute

I can file a fix for option 2). I think Option 1) is a bit more involved.

Activity

Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment

Metadata

Metadata

Assignees

No one assigned

    Labels

    bugSomething isn't working

    Type

    Projects

    No projects

      Milestone

      No milestone

      Relationships

      None yet

      Development

      No branches or pull requests

      Issue actions

      Sponsor
      SponsoredKunjungi sekarang
      Promo