Plan an inner join as a semijoin under eager deduplication

Hi hackers,

This patch teaches the planner to remove provably unnecessary
multiplicity before joining, and gives the planner more opportunities
to choose a semijoin on cost. These changes improve the performance
of some ordinary queries by large factors.

It follows an earlier attempt, now superseded, and takes up both Tom's
objection and the concern I raised myself.

https://www.postgresql.org/message-id/PH0PR18MB444307FAC570FFD7F2457D4DA6AE2%40PH0PR18MB4443.namprd18.prod.outlook.com

It builds directly on Richard Guo's eager aggregation (8e11859102f,
originally proposed by Antonin Houska): the grouped relation, the pushdown,
and the judgement of where in the join tree it is worth doing all come from
that work. This widens what may be pushed down, and offers semijoin
as a way to build it.

Eager deduplication pushes duplicate removal past a join so that the
join sees fewer input rows. Eager aggregation pushes a partial
aggregate below a join; eager deduplication pushes a plain grouping
with no aggregate.

Three cases become interesting. A query with DISTINCT or GROUP BY and
no aggregates groups on its own keys. A query with no grouping clause
of its own, whose every aggregate carries DISTINCT, groups on the
aggregates' arguments, since agg(DISTINCT x) discards duplicate x
before aggregating. A query that does write grouping keys, and whose
aggregates cannot observe how often a row arrives, groups on those keys
and computes the aggregates above the deduplication. In the latter two
cases the aggregates are computed above the join as before, but from
deduplicated rows, so no partial aggregation is pushed down.

An aggregate ignores how often a row arrives if it carries DISTINCT, or
if pg_aggregate.aggsortop is set for it, as it is for min and max. Its
arguments must read only the relations that the query groups by, so the
deduplication displaces only a partial aggregate that would have grouped
on the same keys.

Because the deduplicated rows of a join input are reached by a grouping
rather than an aggregate, a relation that only decides which rows
survive (contributing nothing to the target list or the HAVING qual)
need not be joined at all. Such a relation may be reached via a
semijoin. Usefully, a semijoin terminates the search at the first
matching row instead of producing wasteful matches to be subsequently
discarded. Joins containing a filtering relation are also considered with
parameterization, so the probe can drive an index scan on it.

The SpecialJoinInfo describing that semijoin is local to those paths and
is never added to root->join_info_list, so join order enumeration is
unaffected and no ordering constraint is imposed. Costing an
inner join's clauses under semijoin semantics does collide with the two
selectivity slots a RestrictInfo caches, so those are set aside and
restored around it.

A deduplication is judged useful by its own threshold,
min_eager_distinct_group_size, which defaults to 2 against eager
aggregation's 8, since deduplicated rows carry no transition states.

When the pushed-down grouping is on exactly the query's own grouping
keys, the aggregate above repeats it, so the pushdown is dropped along
with any projection between the two.

The restrictions on eager aggregation carry over, including the
prohibition on pushing below the nullable side of an outer join. A
grouping key whose equality does not imply binary equality, as with a
non-deterministic collation, is not usable, since a deduplication would
decide which of two distinguishable values survives. Grouping sets and
set-returning functions in the target list are not handled.

If a deduplicated relation is built for the topmost join relation, its
paths are finalized and compete with paths from regular planning.

Nothing here decides in advance which shape a query gets. The
deduplication, the semijoin probe, and the ordinary join are all
offered for the same relation, and the planner chooses on cost.

---- Plan change ----

Two-hop chain, DISTINCT, at fanout 32:

SELECT DISTINCT a.id, a.name, a.country
FROM author a
JOIN post p ON p.author_id = a.id
JOIN comment c ON c.post_id = p.id
WHERE c.spam;

-- master
HashAggregate
Group Key: a.id, a.name, a.country
-> Hash Join
Hash Cond: (p.author_id = a.id)
-> Hash Join
Hash Cond: (c.post_id = p.id)
-> Seq Scan on comment c
Filter: spam
-> Hash
-> Seq Scan on post p
-> Hash
-> Seq Scan on author a

-- patched
HashAggregate
Group Key: a.id, a.name, a.country
-> Nested Loop Semi Join
-> Seq Scan on author a
-> Nested Loop
-> Index Scan using post_author_id_idx on post p
Index Cond: (author_id = a.id)
-> Index Scan using comment_post_id_idx on comment c
Index Cond: (post_id = p.id)
Filter: spam

---- Performance ----

Conditions: master with the patches applied, built with cassert off at -O2,
serial plans, work_mem 4MB, shared_buffers 1GB, median of 25. Timing
is wall clock with the output discarded server side. Harness attached.

The queries are modeled after what an ORM or BI layer may produce: a
filter on a related table composed as a to-many join, with DISTINCT or
count(DISTINCT) to undo the fanout.

The corpus is synthetic: author, post, comment, reaction, with 100,000 posts
over 10,000 authors. Fanout is the number of qualifying comments per post,
so at fanout 1 there is nothing to remove. The chain shapes also carry ten
posts per author, so they have duplication to collapse in every column.

=== Delivered speedup vs master ===

query fanout =1 =2 =8 =32
--------------------------------------------------------------------
already an EXISTS (control) 0.92x* 1.02x* 1.01x* 0.99x*
DISTINCT over 1:many join 0.98x* 0.99x* 1.74x 9.62x
count(DISTINCT) over 1:many join 0.99x* 1.04x* 1.09x 6.07x
GROUP BY with max() 1.04x* 1.09x 1.50x 6.88x
DISTINCT, driver filtered 0.99x* 0.94x* 0.85x 8.17x
many to many 1.02x* 0.96x* 1.44x 2.31x
many to many, count(DISTINCT) 1.02x* 1.00x 1.49x 2.02x
two-hop chain, DISTINCT 1.37x 1.53x 14.29x 56.84x
two-hop chain, count(DISTINCT) 1.00x 1.23x 16.13x 57.58x
three-hop chain, DISTINCT 1.29x 10.70x 162.42x DNR
three-hop chain, count(DISTINCT) 0.99x 9.34x 132.77x DNR

* -> the plan did not change
DNR -> did not run (flight too large; pattern already established)

=== Which pushdown the planner chose ===

query fanout =1 =2 =8 =32
------------------------------------------------------------------
already an EXISTS (control) - - - -
DISTINCT over 1:many join - - fold semi
count(DISTINCT) over 1:many join - - fold semi
GROUP BY with max() - semi semi semi
DISTINCT, driver filtered - - fold semi
many to many - - fold fold
many to many, count(DISTINCT) - semi fold fold
two-hop chain, DISTINCT fold fold semi semi
two-hop chain, count(DISTINCT) fold fold semi semi
three-hop chain, DISTINCT fold semi semi DNR
three-hop chain, count(DISTINCT) fold semi semi DNR

fold -> deduplication folded in at join level
semi -> join input reached by semijoin probe
- -> no pushdown chosen

The first row is a query written as EXISTS, which typically receives
a near-optimal plan, and is left alone by this work. Cells where the
plan did not change span 0.92x to 1.04x, which illustrates the noise
floor in these data.

At the bottom of the range, pushdown is sometimes chosen with
unnecessary deduplication folded in. DISTINCT, driver filtered at
fanout 8 comes in at 0.85x. min_eager_distinct_group_size decides
(defaulted to 2; an educated guess). I would welcome feedback.

This threshold misses in the other direction too. It gates on row
reduction alone. The other key idea is stopping at the first matching
row. At fanout 1 the shrink factor is 1 and the gate reports nothing
to collapse, so pushdown is skipped: DISTINCT over a 1:many join
stays at 0.98x whereas the hand-written EXISTS gets 1.72x (see
bench results). No grouped relation is built, so the probe never
exists for cost to compare.

Known gaps: this mode skips create_partial_grouping_paths(), so a
deduplication never runs inside a worker. The aggsortop test is
conservative, and rejects bool_and and bit_and although they are
indifferent to duplicates.

Sixteen patches, plus the harness. Most of the line count is tests.

Thanks,
Will