Hey hackers, Recently I improved a dynamic SQL compiler (an ORM-like layer) using a pattern that seems to generalize to the Postgres planner. I taught the layer to emit an EXISTS subquery when the target relation only served to filter, rather than fanning out a join whose extra rows were discarded.
That led me into the join elimination machinery, and to the attached draft
patch. It adds convert_joins_to_semijoins(), which recognizes an inner
join that only restricts which rows survive and adds a JOIN_SEMI
SpecialJoinInfo for the filtering relation. Two conditions must hold: the
query must discard duplicates, and nothing outside the join clauses may
reference the relation.
The patch works, but only by being narrowed to the point where most of the
idea goes uncaptured.
Results: enable_semijoin_conversion off versus on, same data, serial
plans, work_mem 4MB, median of 5 runs. 100,000 posts and 10,000 authors;
fanout is the number of matching righthand rows per driver row, so it is
exactly the number of duplicate rows the join produces and the dedup step
removes. Fanout =1 is the control.
query fanout =1 =2 =8 =32
--------------------------------------------------------------
DISTINCT over a to-many join 0.98x 1.14x 4.64x 9.42x
count(DISTINCT) over a to-many 0.98x 0.93x 2.75x 11.06x
GROUP BY with max() 1.01x 1.17x 2.33x 6.99x
DISTINCT, driver also filtered 0.92x 1.19x 1.33x 6.87x
The patch lifts one relation at a time. The righthand side must be a single
relation;
a chain is declined outright. (I discovered that LHS selectivity trumps row
multiplicativity when there is no index to probe). This forced me to bind the
RHS
and forgo most of the upside.
>From the same run, at fanout 32:
SELECT a.id, a.name, a.country FROM author a
WHERE EXISTS (SELECT 1
FROM post p JOIN comment c ON c.post_id = p.id
WHERE p.author_id = a.id AND c.spam
);
Master 4527ms
hand-written EXISTS 104ms 43.6x
Which brings me to the layering question. The neighboring machinery here
increases
planner freedom: join elimination removes a relation the query can't observe,
self-join
elimination removes a redundant one; etc. My patch (currently) decreases it.
My intent now is to follow the eager aggregation work and build at a lower
layer.
Rather than replacing joins, offer the planner an alternative to choose on
cost. Concretely,
a parallel "distinct relation", holding rows made distinct on the columns the
query can
observe, carried through the join search, competing on cost, with no
SpecialJoinInfo
and no order constraint.
One caveat: Reaching the ceiling will certainly require existence semantics and
an
index-driven exit. So a distinct relation would have to be able to source a
semijoin path
(not just a pre-deduplicated one). And I wonder whether that can be expressed
without
reintroducing the join-order/selectivity constraint?
Patch attached; it applies to master today.
Thanks,
Will
0002-semijoin-v1-patch-b.patch
Description: 0002-semijoin-v1-patch-b.patch
0003-semijoin-v1-patch-c.patch
Description: 0003-semijoin-v1-patch-c.patch
0004-semijoin-v1-patch-d.patch
Description: 0004-semijoin-v1-patch-d.patch
0001-semijoin-v1-patch-a.patch
Description: 0001-semijoin-v1-patch-a.patch
