sql: lazy evaluation of subqueries during comparisons

[jordanlewis]

Subqueries on the right side of IN/ANY/SOME/ALL comparisons are fully executed and their results buffered into memory before the comparisons begin.

This is undesirable in the case of large subqueries. Take a look at the following contrived scenario:

SELECT 1 IN (SELECT * FROM generate_series(1,1000000));

This query takes 700ms to return on my machine, since it has to buffer up the result of the inner subquery into a tuple Datum before starting the comparison. In this case, it would be ideal to perform the execution of the subquery plan lazily, because the comparison would quickly be able to short-circuit. I think all of the tuple comparison operators could be converted to use this lazy plan evaluation for subqueries.

This could be exposed with a special Tuple datum that hides an internal subquery and has a Next method. There are probably other ways of doing it too.

Jira issue: CRDB-5935

[jordanlewis]

cc @knz @justinj for thoughts

[petermattis]

Should this be tackled at query planning time? Your sample query can be transformed to:

SELECT * FROM (SELECT * FROM generate_series(1,1000000)) AS a(x) WHERE x = 1

And from there we could possibly push the x = 1 filter down onto the generate_series and make the query take constant time. Interestingly, even that initial transform is much faster as it avoids buffering the subquery:

root@:26257/> SELECT 1 IN (SELECT * FROM generate_series(1,1000000));
+--------------------------------+
| 1 IN (SELECT * FROM generate_series(1, 1000000)) |
+--------------------------------+
| true                           |
+--------------------------------+
(1 row)

Time: 416.859735ms

vs

root@:26257/> SELECT * FROM (SELECT * FROM generate_series(1,1000000)) AS a(x) WHERE x = 1;
+---+
| x |
+---+
| 1 |
+---+
(1 row)

Time: 162.897092ms

The example is a bit artificial, though. Do you have a practical query to play with? Perhaps such transformations are not amenable in a real query.

[jordanlewis]

Yeah, it's possible that we could always get something to be done at planning time. I'm not sure though. In general, any subquery that returns a large number of rows will be subject to this problem. I'm sure we can think of something, right? Surely there are realistic queries with subqueries that always have to return a lot of rows.

[knz]

I'm siding with Peter on this. We shouldn't invest to optimize the infrastructure around subqueries at this time, given how much we will change logical planning in the coming few months.

[knz]

I do agree something needs to be done though, but I believe we'll reap 80% of the performance gains with a plan transformation, instead of "lazy evaluation".

[justinj]

In addition I think there's some additional complexity here in the interaction with the [...] insert/update syntax, in which we can't really do things lazily:

> create table t (x int);
> select 1 in (select * from [insert into t (select * from generate_series(1,100)) returning x]);

[jordanlewis]

Seems somewhat reasonable.

I believe that this optimization will be a lot simpler than the kind of transformations you're proposing. If we had a good reason to try to optimize large subqueries, I would vote for doing this as a first cut before some more fancy transformation that might not even work in all cases. However, it's not clear that there's a need for this work yet.

Also I'm not sure why you're putting lazy evaluation in quotes - is there a more accurate term that I'm missing? ISTM we eagerly iterate the entire plan and put the results into a datum. I'm proposing we iterate the plan only when prompted by the above layer, volcano style, the way we do with every other kind of plan.

@justinj true - that isn't evaluated as a subquery though, I don't think. I'm putting the [] syntax aside because people don't really know it exists yet. Also, FWIW, other databases (well I'm just thinking of pg to be fair) use CTEs in lieu of the [] syntax. CTEs allow all preparable statements as named expressions.

[knz]

It sounds like lazy evaluation except it wouldn't be lazy in all cases - when planning for distributed execution, we'd need to evaluate them all upfront so the evaluation would then be strict.

What I'd like to recommend is to start by applying the "leaf data" pattern to subqueries as a first step, then perhaps consider indeed delaying the evaluation until either distsql physical planning, or actual evaluation in local execution, whichever occurs.

[andy-kimball]

I actually didn't know that in case of IN/ANY/ALL we buffer up the right side. I had assumed we'd only buffer the result (a single boolean value), since we know we only need to evaluate the subquery once to obtain that result.

Unless we plan to fix this in the execution engine, we should change the optimizer to hoist the subquery out of the projection in this case. Currently, it only hoists correlated subqueries, but we could easily change it to hoist uncorrelated subqueries like this as well.

[knz]

We can't evaluate the boolean / comparison when the subquery is executed because the LHS of the comparison may be row-dependent, i.e. select v = any (select ...) from .... This query may not be correlated (and thus may be executed just once) but the comparison is correlated and needs be executed again for every row of the from clause.

[andy-kimball]

The optimizer already hoists the case where the ANY is row-dependent. Ideally, the exec engine would not cache the subquery in the non row-dependent case, and only cache the final boolean result.

[github-actions]

We have marked this issue as stale because it has been inactive for
18 months. If this issue is still relevant, removing the stale label
or adding a comment will keep it active. Otherwise, we'll close it in
5 days to keep the issue queue tidy. Thank you for your contribution
to CockroachDB!

[mgartner]

An additional motivator for lazy evaluation of subqueries is to improve the performance of queries in the form SELECT COALESCE(<fast_subquery>, <slow_subquery>), or equivalent CASE or IF expression. Ideally, queries like this would have a latency about equal to the latency of <fast_subquery> when it produces a non-null value. Because we evaluate all subqueries eagerly, the latency is greater than or equal to the latency of <slow_query>.

For example, in CRDB, notice that the latency of both of the queries below are about the same:

defaultdb> select max(x) from generate_series(1, 10000000) as x;
    max
------------
  10000000
(1 row)

Time: 1.388s total (execution 1.387s / network 0.001s)


defaultdb> select coalesce((select 1), (select max(x) from generate_series(1, 10000000) as x));
  coalesce
------------
         1
(1 row)

Time: 1.449s total (execution 1.449s / network 0.000s)

Postgres lazy evaluates the subqueries, so the latency of the second query is much lower. The EXPLAIN output shows that the optimizer has not eliminated the generate_series from the query plan.

marcus=# select max(x) from generate_series(1, 10000000) as x;
   max
----------
 10000000
(1 row)

Time: 1727.274 ms (00:01.727)


marcus=# select coalesce((select 1), (select max(x) from generate_series(1, 10000000) as x));
 coalesce
----------
        1
(1 row)

Time: 0.370 ms


marcus=# explain select coalesce((select 1), (select max(x) from generate_series(1, 10000000) as x));
                                           QUERY PLAN
------------------------------------------------------------------------------------------------
 Result  (cost=125000.02..125000.03 rows=1 width=4)
   InitPlan 1 (returns $0)
     ->  Result  (cost=0.00..0.01 rows=1 width=4)
   InitPlan 2 (returns $1)
     ->  Aggregate  (cost=125000.00..125000.01 rows=1 width=4)
           ->  Function Scan on generate_series x  (cost=0.00..100000.00 rows=10000000 width=4)
(6 rows)

Time: 0.394 ms

Of course, this example could in theory be simplified at optimization time to remove the slow subquery entirely because the fast subquery returns a constant value. But it's not hard to imagine fast subqueries with results that cannot be known at optimization time, like select col from tab limit 1.

[mgartner]

Furthermore, Postgres docs explicitly mention:

A CASE expression does not evaluate any subexpressions that are not needed to determine the result.

I believe lazy evaluation of subqueries is required in order to match this behavior.

We even make the same claim in our documentation, which we need to correct:

Arguments to the right of the first non-null argument are not evaluated.

[knz]

Another argument is correctness: if there's an invalid expression (that would trigger a run-time error) in the non-evaluated branch, the overall query should succeed without error.

[mgartner]

Another argument is correctness: if there's an invalid expression (that would trigger a run-time error) in the non-evaluated branch, the overall query should succeed without error.

Good point. That's the behavior I would expect too. Although I believe either way could be considered correct because Postgres is not consistent—the optimizer traverses all branches searching for expressions to fold, which can cause runtime errors in branches that aren't actually followed during execution. For example:

marcus=# SELECT coalesce((SELECT 1), (SELECT 1/0));
ERROR:  22012: division by zero
LOCATION:  int4div, int.c:822

If we prevent the optimizer from folding the division expression by adding a volatile numerator, the runtime error does not occur:

marcus=# SELECT coalesce((select 1), (select random()::INT/0));
 coalesce
----------
        1
(1 row)

[mgartner]

I think we're close to solving this with some of the infrastructure we added for UDFs. Subqueries in UDFs have to be lazily evaluated because they are evaluated for each invocation of the UDF (can be multiple times in one query if the UDF is in a projection or filter) and they might depend on values of the UDF arguments that are only known at runtime.

I think the remaining hurdle to overcome is building execution infrastructure that can distribute lazily-evaluated subqueries so that we don't have to disable DistSQL for all queries with subqueries.