Обсуждение: Join consolidation / Removing duplicate joins
I've been looking into improving the performance of queries that have co-related sub-queries, such as:
Where currently we produce a plan that executes the subquery as a sub plan, like:
QUERY PLAN
--------------------------------------------------------------------------------------------------------------------------
Seq Scan on t1 (cost=0.00..8456925.00 rows=1000000 width=4) (actual time=0.139..4071.598 rows=1000000 loops=1)
SubPlan 1
-> Index Scan using t2_pkey on t2 (cost=0.42..8.44 rows=1 width=4) (actual time=0.003..0.003 rows=1 loops=1000000)
Index Cond: (id = t1.id)
Planning time: 0.169 ms
Execution time: 4107.809 ms
Though, if the subquery could be proved only to ever return 1 record, then this could be re-written to become:
QUERY PLAN
--------------------------------------------------------------------------------------------------------------------------
Hash Left Join (cost=30832.00..70728.00 rows=1000000 width=8) (actual time=384.337..1452.387 rows=1000000 loops=1)
-> Seq Scan on t1 (cost=0.00..14425.00 rows=1000000 width=4) (actual time=0.015..199.716 rows=1000000 loops=1)
-> Hash (cost=14425.00..14425.00 rows=1000000 width=8) (actual time=382.387..382.387 rows=1000000 loops=1)
Buckets: 131072 Batches: 16 Memory Usage: 2463kB
-> Seq Scan on t2 (cost=0.00..14425.00 rows=1000000 width=8) (actual time=0.010..179.911 rows=1000000 loops=1)
Planning time: 0.396 ms
Execution time: 1473.392 ms
(8 rows)
(notice performance increase)
Of course, you might ask, why not just write the 2nd query in the first place? Well, good idea, but it's not always that simple, take the following update statement:
explain update t1
We end up with a quite a few extra sub queries where probably 1 join would have done the trick. We could have probably written this using the UPDATE/FROM syntax, but if you like to write standard SQL then that might not fly.
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, but as for the case in the UPDATE statement above, I didn't really want the code to create a new join for each subplan that it pulls into the outer query, it would be nice if the code could detect if there's a suitable join there already, and make use of it.
I started to think what an efficient way to do this might be, and thought maybe that it would be good if on RelOptInfo or so, if we could add a bool flag named something like uniquejoin, where this would be set to True, if we could detect that a unique index existed on the relation that was a subset of the join condition, (similar to the requirement of LEFT JOIN removals), we could have a function that tried to pullup all these subplans into the outer query, when it could detect that at most 1 subplan row could exist for each outer plan row, the code could then convert these to a LEFT OUTER JOIN on the outer query.
A bit later in planning, once all the subqueries are planned or pulled up, a "join consolidation" function could be run that merges all of these duplicate joins into 1 join for each relation, it could do this by just looking at relations that have this uniquejoin flag set to true, and then dig deeper to ensure that the join conditions also match. If we also went to the trouble of setting this flag for outer rels and not just the ones we add from this pullup operation, then we could also merge duplicate INNER JOINS too.
Another example of where removing these duplicated joins could be useful is when 2 views get joined that share a non-empty intersection of their relations, where the join conditions are the same.
I kind of thought that perhaps that all of this extra processing to look for unique indexes might just be more processing than it's worth, as success cases of join consolidation might be small, but then I started looking at the executor code around merge and hash join. It seems that there might also be some performance gains in here too. I see with SEMI joins we move to the next outer row once we've found 1 matching inner row. I believe that with these uniquejoin relations that we could also skip to the next outer row the same as with semi joins. I did some quick hacks in the merge join code to test if there was much performance to gain to be had here and found that on a join conditions involving 2 varchar fields of about 16 chars, that I could get the query to run in 97% of the time (saving 1 comparison on the join condition for each row). So perhaps that's promising enough to make it worth the extra planning cycles of setting this uniquejoin flag.
Does anyone have any thoughts on this?
Regards
David Rowley
On Wed, Sep 17, 2014 at 2:00 PM, David Rowley <dgrowleyml@gmail.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=1111width=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)Executiontime: 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.00rows=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
byFilter: 7000Execution time: 4.591 ms
Regards,
Marti