[RFC PATCH] Skip LATERAL check in join_clause_is_movable_to() during OR-clause restriction extraction

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