Re: Join consolidation / Removing duplicate joins

On Wed, Sep 17, 2014 at 2:00 PM, David Rowley <dgrowleyml(at)gmail(dot)com> wrote:
> Anyway... I've been thinking of writing some code that converts these sub
> plans into left joins where it can be proved that the subquery would only at
> most produce 1 row

> Does anyone have any thoughts on this?

+1, I've thought about this part before. There is already precedent
for inlining FROM clause subqueries into the main query, it would be
nice to do that for correlated subqueries as well. It seems we've been
adding features to the planner without fully exploiting opportunities
for normalization and consolidation of optimization techniques.

I think it's not even necessary to prove uniqueness of the subquery as
you describe. Now that 9.3 added LATERAL, a correlated subquery can be
seen as a special case of LATERAL LEFT JOIN with an additional check
to raise an error if >1 rows are returned from the inner side. And you
could optionally elide the error check if you can prove uniqueness.

Advantages:
1. Sufficiently simple lateral subqueries are already normalized into
ordinary JOINs with hash/merge support, so you would get that for free
(probably requires eliding the 1-row check).
2. We get rid of silliness like the explosion of SubPlan nodes for
each reference (see examples below).
3. Based on some naive testing, it seems that 9.5devel performs
slightly better with NestLoop LATERAL subqueries than SubPlan
correlated ones.
4. EXPLAIN output is easier to read, I find.

I suppose EXISTS/IN with correlated subqueries needs some different
treatment, as it can currently take advantage of the "hashed SubPlan"
optimization.

Can anyone see any downsides? Perhaps one day we can get rid of
SubPlan entirely, would anyone miss it?

====
Example of SubPlan explosion:

regression=# create view foo1 as select *, (select ten as ten2 from
tenk2 where tenk1.unique1=tenk2.unique1) from tenk1;

regression=# explain analyze select * from foo1 where ten2 between 1 and 3;
Seq Scan on tenk1 (cost=0.00..175782.08 rows=1111 width=244) (actual
time=0.052..49.288 rows=3000 loops=1)
Filter: (((SubPlan 2) >= 1) AND ((SubPlan 3) <= 3))
Rows Removed by Filter: 7000
SubPlan 1
-> Index Scan using tenk2_unique1 on tenk2 (cost=0.29..8.30
rows=1 width=4) (actual time=0.001..0.002 rows=1 loops=3000)
Index Cond: (tenk1.unique1 = unique1)
SubPlan 2
-> Index Scan using tenk2_unique1 on tenk2 tenk2_1
(cost=0.29..8.30 rows=1 width=4) (actual time=0.002..0.002 rows=1
loops=10000)
Index Cond: (tenk1.unique1 = unique1)
SubPlan 3
-> Index Scan using tenk2_unique1 on tenk2 tenk2_2
(cost=0.29..8.30 rows=1 width=4) (actual time=0.001..0.002 rows=1
loops=9000)
Index Cond: (tenk1.unique1 = unique1)
Execution time: 49.508 ms

====
LATERAL is a win even when using OFFSET 0 to prevent inlining:

regression=# create view foo3 as select * from tenk1 left join lateral
(select ten as ten2 from tenk2 where tenk1.unique1=tenk2.unique1
offset 0) x on true;

regression=# explain analyze select * from foo3 where ten2 between 1 and 3;
Nested Loop (cost=0.29..83733.00 rows=10000 width=248) (actual
time=0.043..28.963 rows=3000 loops=1)
-> Seq Scan on tenk1 (cost=0.00..458.00 rows=10000 width=244)
(actual time=0.008..1.177 rows=10000 loops=1)
-> Subquery Scan on x (cost=0.29..8.32 rows=1 width=4) (actual
time=0.002..0.002 rows=0 loops=10000)
Filter: ((x.ten2 >= 1) AND (x.ten2 <= 3))
Rows Removed by Filter: 1
-> Index Scan using tenk2_unique1 on tenk2 (cost=0.29..8.30
rows=1 width=4) (actual time=0.002..0.002 rows=1 loops=10000)
Index Cond: (tenk1.unique1 = unique1)
Execution time: 29.186 ms

====
And if you could prove uniqueness of the inner side and inline it,
WHERE clauses can also be pushed down trivially:

regression=# create view foo2 as select * from tenk1 left join lateral
(select ten as ten2 from tenk2 where tenk1.unique1=tenk2.unique1) x on
true;

regression=# explain analyze select * from foo2 where ten2 between 1 and 3;
Hash Join (cost=532.50..1083.00 rows=3000 width=248) (actual
time=1.848..4.480 rows=3000 loops=1)
Hash Cond: (tenk1.unique1 = tenk2.unique1)
-> Seq Scan on tenk1 (cost=0.00..458.00 rows=10000 width=244)
(actual time=0.002..0.617 rows=10000 loops=1)
-> Hash (cost=495.00..495.00 rows=3000 width=8) (actual
time=1.837..1.837 rows=3000 loops=1)
Buckets: 1024 Batches: 1 Memory Usage: 118kB
-> Seq Scan on tenk2 (cost=0.00..495.00 rows=3000 width=8)
(actual time=0.004..1.562 rows=3000 loops=1)
Filter: ((ten >= 1) AND (ten <= 3))
Rows Removed by Filter: 7000
Execution time: 4.591 ms

Regards,
Marti