Re: hashjoins vs. Bloom filters (yet again)

Hi,

Here's a v8, with a bunch of changes on top of v7 from last week. The
changes are related mostly to generating the build join relids, so
hopefully it's not too disruptive w.r.t. your work on selecting filter
combinations, building paths etc.

The 0001-0012 parts are from v7, the changes are in 0013-0020. I kept
them unsquashed, to make it easier to review/understand etc.

v8-0013-Consider-foreign-keys-when-estimating-filter-sele.patch
v8-0014-Rework-bloom_build_side_join_ratio.patch
-----

The main change is in 0013 and 0014. While reviewing the TPC-H results
from last week, Q9 kept puzzling me (even with all the fixes from v7).
The new plan was ~10x faster (good), but the filter estimates were
considerably off. Which is surprising, because without the filters the
estimates are fairly accurate.

Turns out, the filter estimates were completely ignoring FK constrains.
For most queries that's fine, but Q9 has joins on a multi-column FK, and
in that case ignoring the FK can results in under-estimate. It just
happens to pick the right plan, but that's mostly luck.

0013 attempted to fix that, but I realized bloom_build_side_join_ratio
calculates the join cardinality (which is then used to calculate the
filter selectivity) for given relids "from scratch". It does consider
the FK between the target rel and the build relids, but not for the
joins in the build relids. And doing that "from scratch" is hard,
because we'd need to reverse-engineer a way to build the relids.

I think this means we have to calculate the join sizes while creating
the build relids, just like during the regular planning, and 0014 is a
step in that direction.

I'm not claiming this is perfect, though.

The trouble is the relevant functions (for generating clauses from ECs,
calculating join rel size, ...) take RelOptInfo for the join relations.
But we don't have those, except for the baserels. The intent is to keep
this first phase as cheap as possible, and building "proper" RelOptInfos
somewhat contradicts that.

The v7 built just the relids, and re-implemented a bunch of stuff (e.g.
a lot of find_interesting_bloom_filters was about generating the clauses
from EC, etc. But now we need to track e.g. join cardinality, etc.

v8 introduces a SimpleRelOptInfo, with only the minimal subset of fields
required for the first phase. That does the trick, but it also means we
have to "copy" a bunch of functions accepting RelOptInfo:

- calc_joinrel_size_estimate
- set_joinrel_size_estimates
- generate_join_implied_equalities
- build_joinrel_restrictlist
- subbuild_joinrel_joinlist
- build_joinrel_joinlist

It's rather annoying, because now we have literally a 100% copy, with
the only change being s/RelOptInfo/SimpleRelOptInfo/ in the function
signature. There's still a bunch of functions copies accepting Relids
(like simple_join_is_legal), those should probably accept the new struct
too. But I'm not sure having this "simple" variant is a good idea, the
code duplication is annoying, so I haven't done that.

Maybe it'd be possible to build "fake" RelOptInfo, with just the fields
needed for calculating the join result size initialized. We'd still not
generate the various paths (which seems like the most expensive part).

But it seems pretty fragile. It might easily happen that this RelOptInfo
gets passed to a place expecting some of the other field, etc.

OTOH, building SimpleRelOptInfo first, and then also RelOptInfo (which
gets to recalculate a bunch of fields) is also not free. Even without
the annoying code duplication.

But I'm also not sure what to do about this :-( All I know is that this
makes the filter selectivity estimates. Maybe it'd be possible to build
RelOptInfo in phases, or something.

v8-0015-Sort-filters-pushed-down-to-a-scan-by-selectivity.patch
-----
It seems reasonable to sort the filters pushed down to a scan node so
that the most selective filters are evaluated first. There's probably a
more elaborate costing, considering cost of probing each filter (some
filters may have many more hash functions etc.). I haven't done that.

In fact, the primary motivation for this change was plan stability. A
surprising consequence of pushing down a filter is that all it makes the
order of those joins "irrelevant". The cardinality gets reduced at the
scan level - the joins "provide" the filters, but do not affect the
cardinality.

So if F joins to D1 and D2, with a filter for each dimension, it then
does not matter if D1 joins before D2 or vice versa. This makes the plan
"unstable" because a small change in statistics can flip the order, even
if the filters discard very different fractions of tuples.

This change stabilizes at least the order of filters, but we probably
need to think about stabilizing the plans in some way.

It probably needs to consider things like false positive rate for the
filters, etc.

v8-0017-Show-expected-filter-selectivity-in-EXPLAIN.patch
-----
It seems useful to know what's the expected selectivity of the filter,
so that it can be compared to the fraction of discarded tuples. It's
only shown for VERBOSE and/or ANALYZE runs, not for plain EXPLAIN.

I just realized it the semantics of this new field is somewhat opposite
to the "rejected" fraction, it should probably be unified.

v8-0016-Add-basic-regression-tests-for-filter-pushdown.patch
v8-0018-Add-a-multi-column-FK-join-to-the-simple-test.patch
v8-0019-Test-a-starjoin-with-multi-column-FK-join-clauses.patch
v8-0020-Test-a-snowflake-join-with-multi-column-FK-join-c.patch
-----
The remaining patches add a couple regression tests focused on the
filter pushdown. The patches do affect plans in various regression
suites, of course. But sometimes it's hard to determine if the plan
change for a complex query is desirable/expected.

These new tests add a bunch of starjoin/snowflake joins, where we know
the expected behavior. The tests are too expensive to be committable,
but for development that's not an issue.

regards

--
Tomas Vondra