Pulling up more complicated subqueries

Hi,

I spent some time staring at TPC-DS benchmark's query 6. It contains a
somewhat complicated subquery, and most of the time spent on that query
is currently spent on executing the subquery again and again. The
essence of the query boils down to this:

CREATE TABLE foo (i int4, j int4);
CREATE TABLE bar (i int4, j int4);

INSERT INTO foo SELECT g%10, g FROM generate_series(1, 10000) g;
INSERT INTO bar SELECT g%10, g FROM generate_series(1, 10000) g;

SELECT * FROM foo
WHERE foo.j >= 1.2 *
(SELECT avg(bar.j) FROM bar WHERE foo.i = bar.i);

The planner can pull up simpler subqueries, converting them to joins,
but unfortunately this case is beyond its capabilities. If it was smart
enough, it could be transformed into something like this:

SELECT * FROM foo
LEFT JOIN (SELECT avg(bar.j) as avg, bar.i FROM bar GROUP BY bar.i) as
avg_bar ON foo.i = avg_bar.i
WHERE foo.j >= 1.2 * avg_bar.avg

There was some brief discussion on doing this kind of transformation
back in 2011, at
https://www.postgresql.org/message-id/4E2F163B.6060105%40gmail.com. I
think we're in a better position to do that now than back then, thanks
to all the other planner work that's been done since.

So how do we get there? I've identified a number of smaller steps that,
when all put together, can handle this, as well as many other queries of
course.

0. This simple case is already handled:

SELECT * FROM foo
WHERE foo.j IN (select bar.j from bar)

It's turned into a semi-join. The next steps will extend this basic
capability, to handle more complicated cases.

postgres=# explain SELECT * FROM foo WHERE foo.j IN (select bar.j from bar);
QUERY PLAN
-------------------------------------------------------------------------
Hash Join (cost=42.75..93.85 rows=1130 width=8)
Hash Cond: (foo.j = bar.j)
-> Seq Scan on foo (cost=0.00..32.60 rows=2260 width=8)
-> Hash (cost=40.25..40.25 rows=200 width=4)
-> HashAggregate (cost=38.25..40.25 rows=200 width=4)
Group Key: bar.j
-> Seq Scan on bar (cost=0.00..32.60 rows=2260 width=4)
(7 rows)

1. Currently, the IN/EXISTS pullup is only done when the IN/EXISTS is a
top-level qual. For example, this isn't currently pulled-up:

SELECT * FROM foo
WHERE foo.j IN (select bar.j from bar) OR foo.j < 10;

That's not a straight semi-join, but we could still turn it into a new
kind of LEFT-SEMI join. A left-semi join is like a left join, in that it
returns all rows from the left side, and NULLs for any non-matches. And
like a semi-join, it returns only one matching row from the right-side,
if there are duplicates. In the qual, replace the SubLink with an IS NOT
NULL test. So logically, the above would be converted into:

SELECT * FROM foo
/* SEMI- */ LEFT JOIN (select bar.j from bar) ON foo.j = bar.j
WHERE bar.j IS NOT NULL OR foo.j < 10

This transformation can be applied to IN/EXIST type SubPlan references
anywhere in the query, not only those in the WHERE clause.

2. Using a similar trick, we can transform subqueries that are not of
the IN/EXISTS kind. (This isn't useful on its own, because this example
would be handled as an InitPlan, which performs well. But it's a
stepping stone in explaining this.)

For example:

SELECT * FROM foo
WHERE foo.j > (select avg(bar.j) from bar)

This can be implemented using yet another new join type, a LEFT-UNIQUE
join. It's like a LEFT JOIN, but it must check that there are no
duplicates in the right-hand-side, and throw an error if there are
(ERROR: more than one row returned by a subquery used as an expression).

SELECT * FROM foo
/* unique-checking */ LEFT JOIN (select avg(bar.j) as min_j from bar) as
subq ON TRUE
WHERE foo.j > subq.min_j

3. All the previous examples are uncorrelated subqueries, but all these
transformations can also be performed on correlated subqueries. The
difference is that the subquery that's pulled up to the range table must
be marked as LATERAL. For example:

SELECT * FROM foo
WHERE foo.j > (select avg(bar.j) from bar where bar.i = foo.i)

->

SELECT * FROM foo
/* UNIQUE-CHECKING */ LEFT JOIN LATERAL (select avg(bar.j) from bar
where bar.i = foo.i) AS subq(j) ON true
WHERE foo.j > subq.j

4. The previous transformation isn't very interesting on its own,
because the only way to implement a LATERAL join is a nested loop join,
which is essentially the same as executing the subplan the naive way.
But we can potentially de-correlate it, by pulling up the correlation qual:

SELECT * FROM foo
/* UNIQUE-CHECKING */ LEFT JOIN LATERAL (select bar.j, bar.i from bar
WHERE bar.i = foo.i) AS subq(j, i) ON true
WHERE foo.j > subq.j

->

SELECT * FROM foo
/* UNIQUE-CHECKING */ LEFT JOIN (select bar.j, bar.i from bar) AS
subq(j, i) ON subq.i = foo.i
WHERE foo.j > subq.j

This will get inlined into the parent query, getting rid of the subquery
altogether. But even if that cannot be done, this is potentially much
better. (I think we already do such de-correlation, at least in simple
cases, actually).

5. If the subquery contains aggregation, we can still perform the
previous transformations, by adding the correlation vars to the GROUP
BY. Like this:

SELECT * FROM foo
/* UNIQUE-CHECKING */ LEFT JOIN LATERAL (select AVG(bar.j) from bar
WHERE bar.i = foo.i) AS subq(j) ON true
WHERE foo.j > subq.j

->

SELECT * FROM foo
/* UNIQUE-CHECKING */ LEFT JOIN (select AVG(bar.j), bar.i from bar GROUP
BY bar.i) AS subq(j, i) ON foo.i = subq.i
WHERE foo.j > subq.j

6. De-correlating the subquery is not necessary a win. Consider the
previous query, if 'foo' is very small, and 'bar' is a huge. The
parameterized plan we generate for a correlated LATERAL subquery, with a
nested loop join, is actually better in that case.

If we teach the planner to consider parameterized nested loop plans for
non-lateral subqueries, by pushing down join quals back to the subquery.
There's a comment on this in set_subquery_pathlist:

* We don't currently support generating parameterized paths for subqueries
* by pushing join clauses down into them; it seems too expensive to
re-plan
* the subquery multiple times to consider different alternatives.
* (XXX that could stand to be reconsidered, now that we use Paths.)

In the old thread from 2011 that I mentioned above, Tom said:

> This leads me to think that we need to represent both cases as the same
> sort of query and make a cost-based decision as to which way to go.
> Thinking of it as a pull-up or push-down transformation is the wrong
> approach because those sorts of transformations are done too early to
> be able to use cost comparisons.

This last step, to push down join quals to a subquery, allows the
planner to make a cost-based decision. A nested-loop, with the join qual
pushed back down to the subquery, isn't exactly the same as the SubPlan,
but it should be comparable in performance.

Thoughts? I'm planning to work on this in the next release cycle,
although I'm not too familiar with the planner, and I don't know if I'll
be distracted with something more shiny, so no promises on any results.

As a final note, I found an interesting paper called "Unnesting
Arbitrary Queries", by Thomas Neumann and Alfons Kemper
(http://www.btw-2015.de/res/proceedings/Hauptband/Wiss/Neumann-Unnesting_Arbitrary_Querie.pdf).
It describes a series of transformations that can be applied to
de-correlate (de-lateralize?) any lateral subquery join. The trick is to
build a temporary relation that contains all the distinct outer values
of the join, and pass that relation down to the subquery. So instead of
"executing" the subquery for every outer row, passing the outer values
as parameters (using PostgreSQL terminology), you collect a list of all
the outer values first, and then execute the subquery only once. In the
subquery, you perform a join with the temporary relation. And then the
paper describes a bunch of rules and optimizations, that can optimize
away the temporary relation in many cases. That might be one way to
implement the de-lateralization steps in PostgreSQL.

- Heikki