Re: hashjoins vs. Bloom filters (yet again)

Hi,

Here is a v6 with an experimental version of building the filters on
joins, and a couple more improvements. I did not include your v5 changes
in selecting interesting filters - sorry about that. I ran out of time,
and I assume you may have a newer version of those changes? Your changes
seem largely orthogonal to the changes I did, so it should not be very
hard to adjust.

v6-0001-PoC-hashjoin-bloom-filter-pushdown.patch
----
In v6 I merged the 0001 and 0002 patches, so this completely abandons
the initial v1 approach of filter pushdown at createplan time. It now
happens during the bottom-up path construction, as introduced in v3.

v6-0002-Check-expected-filters-even-for-partial-paths.patch
v6-0003-Skip-paths-with-filters-in-get_cheapest_path_for_.patch
----
0002 and 0003 fix two gaps, where we failed to consider filters - when
planning joins on partial paths, and when evaluating cheapest paths with
specific pathkeys.

The join planning with partial paths may be a bit surprising, but the
thing we missed is that partial paths can join with non-partial ones
(when the join is not parallel, and happens in the worker). So we need
to be careful about this, and just do the same check as elsewhere.

The "cheapest path with pathkeys" is a clear omission. In a couple
places we simply ask for "cheapest path with pathkeys" not considering
the filters at all, and in that case we better get a path with no
filters by default.

There probably are cases where we could consider the expected filters,
and get cheapest path with some specific filters. I'm speficically
thinking about merge joins (which now AFAIK mostly discard the filters),
aggregations and so on. But I haven't done anything about this.

v6-0004-Make-sure-Gather-nodes-don-t-have-filters.patch
----
This is more or a paranoia/safety, to make sure we're not passing
filters through Gather nodes. Which seems like a possible improvement,
but it's not supported by this version (and I'm not sure how hard would
it be).

v6-0005-Add-tests-for-CustomScan-filter-pushdown.patch
v6-0006-Allow-a-CustomScan-to-consume-a-pushed-down-hashj.patch
----
These are the original CustomScan patches, no change to thse.

v6-0007-Properly-plan-filters-built-on-joins.patch
v6-0008-Add-GUCs-for-limiting-join-enumaration.patch
v6-0009-Allow-filters-built-for-queries-with-LATERAL-join.patch
----

This is the new stuff, related to building (and estimting) filters on
joins. It's split into 3 smaller parts, but it really is one change.

I already explained the issue in [1], and how the paper deals with that
by running the join planning in two phases. First a simpler phase to
identify interesting filter candidates, and then the regular join search.

This implements roughly that, with a couple simplifications. The core is
in enumerate_bloom_filter_build_relids, which enumerates relids of
possible join relations, similarly to what standard_join_search would.
It operates only on relids (no RelOptInfo, no path construction, ...).

In [1] I speculated about using DPccp to enumerate the joins, and maybe
we could do that. But I don't think it'd be any faster, as most of the
time is spent in checking join legality, etc.

There is a bunch of other limits intended to limit the overhead:

1) The relids are generated only once per query, cached in PlannerInfo.

2) We don't generate relids for joins of more than 3 rels (which limits
e.g. how many dimensions can be used to derive a filter).

3) We don't generate more than 100 relids.

Of course, (2) and (3) limits are somewhat arbitrary, and I think we can
use much higher values in practice. In the comments I speculate we could
"prune" the join search space quite a bit by deducing which relations
are interesting filter targets (e.g. not tiny ones), and leveraging the
join graph structure.

I also suspect this is related to the "join hardness" thread, which is
exactly about limiting the number of valid join relations in a query. So
maybe there's something we could use here.

I think one worthwhile task would be inspecting the plan changes due to
this patch series. In fact, that's how I ended up with 0002 and 0003
patches, by looking for weird plans changes in tests. There probably are
a couple more cases to investigate.

A bunch of plans changed because "Join Filter" lists clauses a bit
differently, but I think that's correct / expected. The patches have to
deduce clauses from ECs, and that may cache a slightly different variant
of the clause. It's annoying but harmless.

I'll have to put this on the backburner for a couple days, but then I
plan to add some more test coverage, with schemas/queries designed
specifically to leverage filters. And look for places in the planner
that might/should consider filters.

regards

[1] https://postgr.es/m/68389077-45fa-4b7b-89d3-89fdffde1283@vondra.me

--
Tomas Vondra