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
hashjoin-bloom-test.sql
Description: application/sql
diff --git a/src/backend/optimizer/path/joinpath.c b/src/backend/optimizer/path/joinpath.c
index a3e16b5d23c..b661a5b800f 100644
--- a/src/backend/optimizer/path/joinpath.c
+++ b/src/backend/optimizer/path/joinpath.c
@@ -1051,21 +1051,21 @@ compute_join_expected_filters(PlannerInfo *root,
owner_relids = owner_in_outer ? outer_relids : inner_relids;
other_relids = owner_in_outer ? inner_relids : outer_relids;
- if (bms_is_subset(f->build_relids, owner_relids))
+ /*
+ * Build side already sits with the owner; this shouldn't
+ * normally happen (such a filter would have been resolved or
+ * discarded at a lower join).
+ */
+ Assert(!bms_is_subset(f->build_relids, owner_relids));
+
+ if (bms_overlap(f->build_relids, owner_relids))
{
/*
- * Build side already sits with the owner; this shouldn't
- * normally happen (such a filter would have been resolved at
- * a lower join), but if it does, just propagate it unchanged.
- *
- * We still must be able to reach the owner's scan from above,
- * so the owner has to be on a side this join preserves (see
- * bloom_join_side_preserved); otherwise the filter could not
- * be pushed to a recipient and this path must be rejected.
+ * We should not see a filter intersecting with the owner
+ * We need all the build relids on the other side of the join,
+ * and if the owner already has some, that can't happen.
*/
- if (!bloom_join_side_preserved(jointype, owner_in_outer))
- goto contradiction;
- result = lappend(result, f);
+ goto contradiction;
}
else if (bms_is_subset(f->build_relids, join_relids))
{
