Re: hashjoins vs. Bloom filters (yet again)

Hi,

I spent a bit of time profiling this myself today, using a very simple
starjoin schema (attached), with filters on each dimension, so that each
dimension qualifies as a filter source.

And with

set bloom_filter_pushdown_max = 10;

planning that "simple" join query takes ~500ms (compared to 30ms with
filters disabled). That's a lot, and most of this seems to be due to
processing the new paths during joins, because after setting

set join_collapse_limit = 1;

the plan times drop to ~40ms and 10ms. So it's still much more than
without filters, but much less than before.

I'm also attaching a perf profile for this. There's two things that
caught my eye:

1) expected_filters_equal seems to be damn expensive

It does a deep comparison. I wonder if we could come up with some
cheaper way to compare filters. I have a couple ideas.

For example, we can compare pathkeys directly (by comparing pointers),
and maybe we could try something like that here? generate_filtered_paths
creates unique instances of a filter, and then attaches it to many
paths. compute_join_expected_filters does not construct new filters either.

It might be an issue if we start comparing filters constructed for
different baserels (e.g. between join inputs). Then we'd either need to
do the expensive comparison, or do something more complicated.

Alternatively, maybe we could calculate a "hash" - if different hash
value would mean "certainly different", that'd be sufficient for most
places in add_path(). A matching hash would still need deep comparison,
but if it's rare enough, that should be OK.

However, now that I think about this. Do we actually need the deep
comparison? Isn't it enough to compare just the "build relids" for each
filter? Or maybe a union of relids first, and then relids for filters?

Of course, this won't eliminate the overhead. If there's 100x more
paths, it'll add overhead.

Maybe we'll need to rethink how add_path() handles these paths. Maybe we
could keep them aside and/or grouped by the expected filters?

2) It's interesting most of the time is spent in try_nestloop_path (and
try_hashjoin_path), while try_mergejoin_path remains cheap. I suppose
that's because it only looks at total cheapest paths, etc.

3) I think we'll need to do something like the 'heuristic 4', which just
creates paths with all 'candidate' filters, not for combinations. I was
a bit afraid that'll restrict the planner too much when picking join
algorithms, but maybe that's OK.

4) I suspect compute_join_expected_filters is not quite right when
comparing the build relids - probably did work for singleton rels on the
build side, but with joins it might "keep" bogus filters. See the
attached fix. It does not affect the planning for the example, though.

FWIW I'm running some tests on TPC-H, to see which queries would benefit
from this, how much, if there are issues, etc. Should have some numbers
later this week.

regards

--
Tomas Vondra