Push down entire hash table from HashJoinExec into scans

[adriangb]

In #16445 we discussed two approaches:

• Push down min/max of the hash table. This is what DuckDB does and what we ended up implementing in Add dynamic filter (bounds) pushdown to HashJoinExec #16445
• It's also possible for us to push down the entire hash table to prune rows during scans. This is what this issue tracks.

Some questions to answer:

• Should we always push down both the hash table and bounds?
• Should we push down the entire hash table as is or should we build bloom filters, an IN LIST expression or other?

[adriangb]

cc @Dandandan

[rkrishn7]

Hello! This is quite interesting.

Should we always push down both the hash table and bounds?

Should we push down the entire hash table as is or should we build bloom filters, an IN LIST expression or other?

My initial thought is that the number of distinct values (NDV) on the build side could serve as a useful signal for which filter to push down. For example:

• If the join column has high cardinality, the values are likely fairly random, in which case pushing down an IN LIST may be more effective. I think existing pruning machinery already handles IN LIST quite well — e.g. enabling Parquet row group pruning via Bloom filters.

• On the other hand, if the column shows low variance, then min/max statistics may provide better pruning.

Curious to hear your thoughts on this approach!

[xudong963]

iirc, df stats doesn't include NDV now

[rkrishn7]

@xudong963 I was thinking we can simply derive the proportion of unique values on the left side, given that we collect the left side in memory.

If the left side has a high number of distinct values for a given column, it may be more likely that the right side follows this as well (UUIDs, for example). In which case pushing down the literal values would likely make pruning more effective.

But let me know if I'm missing something!

[rkrishn7]

I've been playing around with pushing down literal guarantees from the values on the left hand side. Some initial thoughts/observations:

As @adriangb pointed out the question is really when to push down the left column values, since there are likely diminishing returns to doing so. For example, we probably wouldn't want to push down a list of 1000 values, since:

• The effectiveness of pruning groups of data decreases as the number of distinct values increases, I imagine.
• There is likely a point where the cost of evaluating the bloom filter outweighs the cost of unnecessary data scanning.

I think the above two are directly correlated. That is, they both are influenced by the size of the literal guarantees we build.

However, with point lookup queries, for example, the effectiveness over min/max stats pruning can clearly be observed. Take the following query for example:

SELECT *
FROM customer
JOIN orders on c_custkey = o_custkey
WHERE c_name = 'Customer#000077000';

I observed around a 3x speedup on TPCH SF20 (down from ~3s to ~1s) when building the dynamic filter as an IN LIST vs. min/max bounds. Note that this required me to build the TPCH data with bloom filters included.

[adriangb]

Thank you for investigating! I really wonder what performance would be like for some of these pushing down a bounded size bloom filter. I think other systems do this (citation needed). But it does cost at build time, etc.

[adriangb]

Citation: https://15721.courses.cs.cmu.edu/spring2024/notes/09-hashjoins.pdf