Hi hackers, I am investigating a case where join_clause_is_movable_to() appears to be too restrictive when it is called from extract_restriction_or_clauses().
join_clause_is_movable_to() is used by several callers, including
match_join_clauses_to_index() and extract_restriction_or_clauses().
It performs some check, the 4th one is:
/*
* Clause must not use any rels with LATERAL references to this rel
*/
if (bms_overlap(baserel->lateral_referencers, rinfo->clause_relids))
return false;
I believe this check is necessary when the function is used by
match_join_clauses_to_index(): in that case the clause can be used for a
parameterized scan, and the relation containing the lateral reference cannot
simply be placed on the outer side of a NestLoop with the target relation.
However, the situation appears to be different when the function is called from
extract_restriction_or_clauses(). In that case, the clause is not being used to
construct such a parameterized path. Instead, extract_restriction_or_clauses()
is trying to derive restriction clauses from an OR-clause and push those
restrictions to the relevant base relation.
Therefore, I am wondering whether the lateral-reference check is unnecessarily
restrictive in this caller. Removing the check only for this use of
join_clause_is_movable_to() allows additional restriction
clauses to be extracted and can result in substantially better plans.
I tested this with the following example. I created:
CREATE TABLE a(a1 int, a2 int, a3 int, a4 int);
CREATE TABLE b(b1 int, b2 int, b3 int, b4 int);
Table A contains 10,000 rows and table B contains 30,000 rows, with random
integers and NULLs populated into the columns (The SQL commands I used for
populating data and the full output of 'EXPLAIN ANALYZE' commands are in the
attached file TEST.txt).
I tested with this query:
EXPLAIN ANALYZE
SELECT *
FROM A,
LATERAL (
SELECT sum(b1) x, sum(b2) y, b3, b4
FROM B
WHERE b3+b4 < a1+a2
GROUP BY b3,b4
) I
WHERE (b3<a3 and (a4=32 or a4=33))
OR (b3>a3-999 and a4=18)
OR (x-y<a3+a4 and a1-a2=a4);
With the current code, the planner does not extract a restriction for table A.
The lateral subquery is therefore executed once for each of the 10,000 rows of
table A:
-> Seq Scan on A
rows=10000
-> Subquery Scan on I
loops=10000
The execution time is "356292.545 ms"
After relaxing the 4th check when join_clause_is_movable_to() is called from
extract_restriction_or_clauses(), the planner extracts:
((a4 = 32) OR (a4 = 33) OR (a4 = 18) OR ((a1 - a2) = a4))
and the plan becomes:
-> Seq Scan on A
rows=7
-> Subquery Scan on I
loops=7
The execution time drops to "369.580 ms"
The query returned 50923 rows in both versions.
I also tested a 'LEFT JOIN LATERAL' case:
EXPLAIN ANALYZE
SELECT *
FROM a
LEFT JOIN LATERAL (
SELECT sum(b1) x,sum(b2) y,b3,b4
FROM b GROUP BY b3,b4 HAVING b3+b4<>a3+a4
) ON a1+a3>x+b3
WHERE (a1=coalesce(x,30) and a2-a4>a1+a3)
OR (a2=coalesce(y-b3,41) and a2+5=a4+a3);
With the current code, subquery is executed 10,000 times, and the execution
time is "631284.853 ms"
After the relaxation, the planner derives a restriction on table A:
Filter: (((a2 - a4) > (a1 + a3)) OR ((a2 + 5) = (a4 + a3)))
subquery is executed only 370 times, and the execution time drops to "22444.571
ms"
Again, both versions return 213 rows.
For both examples, I materialized the results produced before and after the
change and compared them using bidirectional 'EXCEPT ALL', similar to this:
(SELECT * FROM before EXCEPT ALL SELECT * FROM after)
UNION ALL
(SELECT * FROM after EXCEPT ALL SELECT * FROM before);
In both cases this returned zero rows, so I did not observe any result
difference in these test cases.
I also ran make check-world with the patch applied, all tests that were
executed passed.
The attached patch makes the lateral-reference check caller-specific: it is
retained for the existing uses where it is needed, but skipped when
join_clause_is_movable_to() is used by
extract_restriction_or_clauses().
I would especially appreciate feedback on the correctness of this
caller-specific relaxation, and in particular whether the fourth check is
required for restriction extraction for some reason that I have overlooked.
Thanks, Geng Lei
0001-Skip-LATERAL-check-in-join_clause_is_movable_to-duri.patch
Description: 0001-Skip-LATERAL-check-in-join_clause_is_movable_to-duri.patch
Table A and B are populated with data like this:
opt=# SELECT setseed(0.12345);
setseed
---------
(1 row)
opt=# INSERT INTO a (a1, a2, a3, a4)
SELECT
CASE WHEN random() < 0.1 THEN NULL ELSE floor(random() * 10000)::int END,
CASE WHEN random() < 0.04 THEN NULL ELSE floor(random() * 10000)::int END,
CASE WHEN random() < 0.021 THEN NULL ELSE floor(random() * 10000)::int END,
CASE WHEN random() < 0.01 THEN NULL ELSE floor(random() * 10000)::int END
FROM generate_series(1, 10000);
INSERT 0 10000
opt=# INSERT INTO b (b1, b2, b3, b4)
SELECT
CASE WHEN random() < 0.1 THEN NULL ELSE floor(random() * 10000)::int END,
CASE WHEN random() < 0.04 THEN NULL ELSE floor(random() * 10000)::int END,
CASE WHEN random() < 0.021 THEN NULL ELSE floor(random() * 10000)::int END,
CASE WHEN random() < 0.01 THEN NULL ELSE floor(random() * 10000)::int END
FROM generate_series(1, 30000);
INSERT 0 30000
With current join_clause_is_movable_to() implementation, run the following
queries, storing their results in materialized view MV1 and MV2,respectively:
opt=# explain analyze create materialized view MV1 as select * from a,
lateral(select sum(b1) x,sum(b2) y,b3,b4 from b where b3+b4<a1+a2 group by
b3,b4 )I where (b3<a3 and (a4=32 or a4=33)) or (b3>a3-999 and a4=18) or
(x-y<a3+a4 and a1-a2=a4);
QUERY PLAN
-----------------------------------------------------------------------------------------------------------------------------------------------------------------------
------
Nested Loop (cost=787.00..11128904.00 rows=124758 width=40) (actual
time=4069.385..356156.710 rows=50923.00 loops=1)
Buffers: shared hit=1620054
-> Seq Scan on a (cost=0.00..154.00 rows=10000 width=16) (actual
time=0.010..9.215 rows=10000.00 loops=1)
Buffers: shared hit=54
-> Subquery Scan on i (cost=787.00..1112.76 rows=12 width=24) (actual
time=35.603..35.611 rows=5.09 loops=10000)
Filter: (((i.b3 < a.a3) AND ((a.a4 = 32) OR (a.a4 = 33))) OR ((i.b3 >
(a.a3 - 999)) AND (a.a4 = 18)) OR (((i.x - i.y) < (a.a3 + a.a4)) AND ((a.a1 -
a.a2) = a.
a4)))
Rows Removed by Filter: 12487
Buffers: shared hit=1620000
-> HashAggregate (cost=787.00..855.58 rows=6858 width=24) (actual
time=21.721..28.422 rows=12492.00 loops=10000)
Group Key: b.b3, b.b4
Batches: 1 Memory Usage: 2841kB
Buffers: shared hit=1620000
-> Seq Scan on b (cost=0.00..687.00 rows=10000 width=16)
(actual time=1.161..10.169 rows=12493.69 loops=10000)
Filter: ((b3 + b4) < (a.a1 + a.a2))
Rows Removed by Filter: 17506
Buffers: shared hit=1620000
Planning Time: 0.251 ms
Execution Time: 356292.545 ms
(18 rows)
opt=# explain analyze create materialized view MV2 as select * from a left join
lateral(select sum(b1) x,sum(b2) y,b3,b4 from b group by b3,b4 having
b3+b4<>a3+a4) on a1+a3>x+b3 where (a1=coalesce(x,30) and a2-a4>a1+a3) or
(a2=coalesce(y-b3,41) and a2+5=a4+a3);
QUERY PLAN
-----------------------------------------------------------------------------------------------------------------------------------------------------------------------
--------------------------------------------------
Nested Loop Left Join (cost=985.50..13494629.00 rows=1617 width=40) (actual
time=11034.488..631277.881 rows=213.00 loops=1)
Filter: (((a.a1 = COALESCE(unnamed_subquery.x, '30'::bigint)) AND ((a.a2 -
a.a4) > (a.a1 + a.a3))) OR ((a.a2 = COALESCE((unnamed_subquery.y -
unnamed_subquery.b3),
'41'::bigint)) AND ((a.a2 + 5) = (a.a4 + a.a3))))
Rows Removed by Filter: 113918508
Buffers: shared hit=1619838 read=216
-> Seq Scan on a (cost=0.00..154.00 rows=10000 width=16) (actual
time=0.116..13.882 rows=10000.00 loops=1)
Buffers: shared read=54
-> Subquery Scan on unnamed_subquery (cost=985.50..1246.59 rows=3165
width=24) (actual time=40.443..59.584 rows=11391.74 loops=10000)
Filter: ((a.a1 + a.a3) > (unnamed_subquery.x + unnamed_subquery.b3))
Rows Removed by Filter: 16659
Buffers: shared hit=1619838 read=162
-> HashAggregate (cost=985.50..1080.44 rows=9494 width=24) (actual
time=38.196..52.896 rows=28050.80 loops=10000)
Group Key: b.b3, b.b4
Batches: 1 Memory Usage: 2841kB
Buffers: shared hit=1619838 read=162
-> Seq Scan on b (cost=0.00..687.00 rows=29850 width=16)
(actual time=0.301..11.329 rows=28053.70 loops=10000)
Filter: ((b3 + b4) <> (a.a3 + a.a4))
Rows Removed by Filter: 1946
Buffers: shared hit=1619838 read=162
Planning:
Buffers: shared hit=106 read=3
Planning Time: 0.892 ms
Execution Time: 631284.853 ms
(22 rows)
After relaxation of join_clause_is_movable_to(), run the queries again, storing
their results in materialized view MV3 and MV4, respectively:
opt=# explain analyze create materialized view MV3 as select * from a,
lateral(select sum(b1) x,sum(b2) y,b3,b4 from b where b3+b4<a1+a2 group by
b3,b4 )I where (b3<a3 and (a4=32 or a4=33)) or (b3>a3-999 and a4=18) or
(x-y<a3+a4 and a1-a2=a4);
QUERY PLAN
-----------------------------------------------------------------------------------------------------------------------------------------------------------------------
------
Nested Loop (cost=787.00..62738.38 rows=125766 width=40) (actual
time=18.017..250.829 rows=50923.00 loops=1)
Buffers: shared hit=972 read=216
-> Seq Scan on a (cost=0.00..279.00 rows=55 width=16) (actual
time=0.214..5.725 rows=7.00 loops=1)
Filter: ((a4 = 32) OR (a4 = 33) OR (a4 = 18) OR ((a1 - a2) = a4))
Rows Removed by Filter: 9993
Buffers: shared read=54
-> Subquery Scan on i (cost=787.00..1112.76 rows=2287 width=24) (actual
time=22.745..33.245 rows=7274.71 loops=7)
Filter: (((i.b3 < a.a3) AND ((a.a4 = 32) OR (a.a4 = 33))) OR ((i.b3 >
(a.a3 - 999)) AND (a.a4 = 18)) OR (((i.x - i.y) < (a.a3 + a.a4)) AND ((a.a1 -
a.a2) = a.
a4)))
Rows Removed by Filter: 4294
Buffers: shared hit=972 read=162
-> HashAggregate (cost=787.00..855.58 rows=6858 width=24) (actual
time=21.746..28.365 rows=11568.29 loops=7)
Group Key: b.b3, b.b4
Batches: 1 Memory Usage: 1817kB
Buffers: shared hit=972 read=162
-> Seq Scan on b (cost=0.00..687.00 rows=10000 width=16)
(actual time=0.016..10.581 rows=11570.14 loops=7)
Filter: ((b3 + b4) < (a.a1 + a.a2))
Rows Removed by Filter: 18430
Buffers: shared hit=972 read=162
Planning Time: 0.331 ms
Execution Time: 369.580 ms
(20 rows)
opt=# explain analyze create materialized view MV4 as select * from a left join
lateral(select sum(b1) x,sum(b2) y,b3,b4 from b group by b3,b4 having
b3+b4<>a3+a4) on a1+a3>x+b3 where (a1=coalesce(x,30) and a2-a4>a1+a3) or
(a2=coalesce(y-b3,41) and a2+5=a4+a3);
QUERY PLAN
-----------------------------------------------------------------------------------------------------------------------------------------------------------------------
--------------------------------------------------
Nested Loop Left Join (cost=985.50..4543893.73 rows=544 width=40) (actual
time=544.179..22428.814 rows=213.00 loops=1)
Filter: (((a.a1 = COALESCE(unnamed_subquery.x, '30'::bigint)) AND ((a.a2 -
a.a4) > (a.a1 + a.a3))) OR ((a.a2 = COALESCE((unnamed_subquery.y -
unnamed_subquery.b3),
'41'::bigint)) AND ((a.a2 + 5) = (a.a4 + a.a3))))
Rows Removed by Filter: 954660
Buffers: shared hit=59994
-> Seq Scan on a (cost=0.00..304.00 rows=3367 width=16) (actual
time=0.018..4.985 rows=370.00 loops=1)
Filter: (((a2 - a4) > (a1 + a3)) OR ((a2 + 5) = (a4 + a3)))
Rows Removed by Filter: 9630
Buffers: shared hit=54
-> Subquery Scan on unnamed_subquery (cost=985.50..1246.59 rows=3165
width=24) (actual time=38.590..59.817 rows=2580.74 loops=370)
Filter: ((a.a1 + a.a3) > (unnamed_subquery.x + unnamed_subquery.b3))
Rows Removed by Filter: 26431
Buffers: shared hit=59940
-> HashAggregate (cost=985.50..1080.44 rows=9494 width=24) (actual
time=38.264..53.415 rows=29011.91 loops=370)
Group Key: b.b3, b.b4
Batches: 1 Memory Usage: 2841kB
Buffers: shared hit=59940
-> Seq Scan on b (cost=0.00..687.00 rows=29850 width=16)
(actual time=0.007..11.280 rows=29014.90 loops=370)
Filter: ((b3 + b4) <> (a.a3 + a.a4))
Rows Removed by Filter: 985
Buffers: shared hit=59940
Planning:
Buffers: shared hit=74
Planning Time: 0.616 ms
Execution Time: 22444.571 ms
(24 rows)
MV1 and MV3 shall have the same cardinalities:
opt=# select count(1) from mv1;
count
-------
50923
(1 row)
opt=# select count(1) from mv3;
count
-------
50923
(1 row)
MV1 and MV3 shall be identical:
opt=# (SELECT * FROM MV1 EXCEPT ALL SELECT * FROM MV3)
UNION ALL
(SELECT * FROM MV3 EXCEPT ALL SELECT * FROM MV1);
a1 | a2 | a3 | a4 | x | y | b3 | b4
----+----+----+----+---+---+----+----
(0 rows)
MV2 and MV4 shall have the same cardinalities:
opt=# select count(1) from mv2;
count
-------
213
(1 row)
opt=# select count(1) from mv4;
count
-------
213
(1 row)
MV2 and MV4 shall be identical:
opt=# (SELECT * FROM MV2 EXCEPT ALL SELECT * FROM MV4)
UNION ALL
(SELECT * FROM MV4 EXCEPT ALL SELECT * FROM MV2);
a1 | a2 | a3 | a4 | x | y | b3 | b4
----+----+----+----+---+---+----+----
(0 rows)
