opt/distsql: fix CTE semantics

[justinj]

The purpose of this issue is to summarize the expected semantics of CTEs and also document a proposed solution.

Today, we simply inline all CTEs. This is incorrect in the case where a CTE contains side effects. The heuristic planner partially solves this problem by introducting a Spool operator on top of any inlined CTE. This is still incorrect in the presence of CTEs which are never referenced in a query at all. Today, we error in such a case. This also prohibits referencing a given CTE's results more than once. In the short-term the optimizer will mimic this behaviour and simply insert a spool node (possibly eliminating the spool if no side effects are possible).

The desired semantics of CTEs are this:

• Every top-level CTE executes exactly once.
• Every non-top level CTE executes at most once.

The proposed end-state is this:

opt and exec both introduce a With operator which has two inputs: a variable input and an actual input input. It also contains a variable reference ref. The semantics of With are that the variable input is guaranteed to be run to completion before the input input begins running, and its results stored in some other place, referenced by ref. input can then refer to those results as a table referenced by ref (ref would be referenced in input by some other new operator WithRef).

As an optimization, we can track the number of references to a given CTE, and if it has no side effects and exactly one reference we can inline it.

cc @andy-kimball @knz @jordanlewis

[justinj]

Clarifying from a conversation with @andy-kimball that it's important that the With operator doesn't use the existing spoolNode, since it must only evaluate its input if it ever get evaluated itself, it's not correct if, say, it's part of a CASE branch that doesn't get evaluated and it does get evaluated.

[knz]

it's not correct if, say, it's part of a CASE branch that doesn't get evaluated and it does get evaluated.

I think something got lost in translation:

1. the spool operator must only be used when the operand is a mutation -- a "WITH a AS SELECT ..." does not need a spool, and for the purpose of point 2 below we can specify that only mutation CTEs use a spool

2. as has also been discussed before: it's not valid SQL to have a mutation CTE inside CASE -- mutations CTEs are only allowed at the top level

Assuming the semantic check for point 2 is done properly, then as long as we only introduce spools for mutations then we don't have to care about CASE whatsoever.

[justinj]

I think @andy-kimball's contention is that side-effecting (even without mutation) CTEs should be spooled.

[knz]

that's arbitrary and will hurt performance

postgres does not do it

[justinj]

hm, I don't think I realized that Postgres didn't do that:

d=# with y as (select 1/a from x) select * from y limit 0;
 ?column?
----------
(0 rows)

[knz]

I want to clarify my proposition here:

• it is allowed to spool select clauses, for example to avoid the same results being computed multiple times as an optimization for certain queries

• however there is no guarantee that things will be spooled or not

• also, I saw in several places in postgres docs mentions that "side effects" (never called with this term in pg docs, but they do refer to e.g. sequence increments) are not guaranteed to happen or not in SELECT

[andy-kimball]

What about the case where a CTE is referenced multiple times?

WITH cte AS (SELECT nextval('lastval_test') FROM a) SELECT * FROM cte, cte AS cte2;

In Postgres, this returns:

 nextval | nextval
---------+---------
       1 |       1

Which suggests the CTE is only executed once, meaning it spools.

Are you absolutely sure that PG makes no guarantees about whether a CTE would spool? When I wrote the side-effect policy, you asked me to add CTE semantics to it, and so I added this:

//   3. A common table expression (CTE) with side effects will only be evaluated
//      one time. This will typically prevent inlining of the CTE into the query
//      body. For example:
//
//        WITH a AS (INSERT ... RETURNING ...) SELECT * FROM a, a
//
//      Although the "a" CTE is referenced twice, it must be evaluated only one
//      time (and its results cached to satisfy the second reference).

If I understand your position, you're saying that that rule should only apply to mutations, but not to other kinds of side effects.

[knz]

As I wrote above in PG the spool is possible but not guaranteed, it can be introduced for optimisations but apps can't rely on it. -- Sent from my Android device with K-9 Mail. Please excuse my brevity.

[andy-kimball]

Our side effect semantics are still tangled up. Say this is the query, and y=0 for one of the rows in a:

SELECT *
FROM a
WHERE
  CASE
  WHEN x=1234 THEN
    EXISTS(WITH a AS (SELECT 1/y) SELECT * FROM a, a AS a2)
  END

Here, if we attempt to use a Spool to handle multiple CTE references, we'll indirectly violate the CASE guarantee by raising a division by zero, even if the CASE branch is never taken. This is because we hoist Spool up to the top of the query, regardless of its context.

PG in this scenario does not trigger an error. If/when we support multiple CTE refs, we'll have to figure out how to handle this case, perhaps by using the With operator that Justin describes above.

[knz]

Check out what happens in postgres:

kena=# create table zero(x int); insert into zero(x) values (0);
CREATE TABLE
INSERT 0 1
kena=# create table a(x int);
CREATE TABLE
kena=# explain(verbose) SELECT *
FROM a
WHERE
  CASE
  WHEN x=1234 THEN
    EXISTS(WITH a AS (SELECT 1/x FROM zero) SELECT * FROM a, a AS a2)
  END;
                                 QUERY PLAN
-----------------------------------------------------------------------------
 Seq Scan on kena.a  (cost=41.90..83.77 rows=1275 width=4)
   Output: a.x
   Filter: CASE WHEN (a.x = 1234) THEN $1 ELSE NULL::boolean END
   InitPlan 2 (returns $1)
     ->  Nested Loop  (cost=41.88..130168.38 rows=6502500 width=0)
           CTE a
             ->  Seq Scan on kena.zero  (cost=0.00..41.88 rows=2550 width=4)
                   Output: (1 / zero.x)
           ->  CTE Scan on a a_1  (cost=0.00..51.00 rows=2550 width=0)
                 Output: a_1."?column?"
           ->  CTE Scan on a a2  (cost=0.00..51.00 rows=2550 width=0)
                 Output: a2."?column?"
(12 rows)

As I have explained above, postgres refuses to hoist anything inside CASE to outside of it, and this includes both subqueries and CTEs.

Independently from this observation, you can also confirm here that pg does not use a spool for the non-mutation CTE.

[knz]

Another note: I think the criteria in pg for blocking the propagation of something across CASE is not "it can produce errors" but instead "there is a subquery and its results cannot be determined reliably during planning".

[andy-kimball]

I think we're talking past each other.

I don't know what PG calls it, but it's definitely caching/spooling the results of the CTE in that query. Take a look at this simplified query:

WITH a AS (SELECT nextval('seq')) SELECT * FROM a, a AS a2;

This only increments nextval once, even though it's referenced twice. The EXPLAIN does not show an explicit Spool operator, but nevertheless it's spooling the result.

All I'm saying that we currently have no way in CockroachDB to duplicate those semantics when the CTE is nested within a CASE. If we don't use Spool, then we'll call nextval multiple times. If we do use Spool, then it gets invoked at the top-level, which in effect hoists it outside the CASE, which doesn't match PG semantics.

[andy-kimball]

Also, I think you're missing something about how the optimizer currently works. We never hoist up uncorrelated subqueries - we just leave them as-is. However, we're again unable to match PG semantics, because our subquery implementation always globalizes all subqueries, and executes them exactly once at the beginning of the query. Thus, it is SQL execution that "hoists" those queries, not the optimizer. This script shows the difference in behavior from PG, both in 2.0 and 2.1:

CREATE TABLE a (x INT PRIMARY KEY, y INT);
INSERT INTO a (x, y) VALUES (1, 0);
SELECT CASE WHEN x=1000 THEN (SELECT 1/y FROM a LIMIT 1) END FROM a;

PG correctly returns nil for this query, but CockroachDB fails with a division by zero error. I know of no way to "fix" that given the current behavior of our execution operators.

[knz]

Regarding your comment above in #31095 (comment)

As I wrote before pg will introduce a spool in some cases as an optimizations when it decides that a sub-clause can be ran just once to avoid computing results multiple times. It will not do this because it feels semantically mandated to do so.

Regarding your other comment #31095 (comment)

I agree with your assessment "our current woes come from a limitation in the execution engine". The optimizer has to contend with the feature available in the back-end. However we need to make a strong case that the SQL execution machinery must be extended, and this case must be a semantic case to be compelling (and not just an optimization).

[knz]

pg will introduce a spool in some cases as an optimizations when it decides that a sub-clause can be ran just once to avoid computing results multiple times

To clarify: this is especially true when expressions may produce errors (e.g. 1/x). It's very clear throughout the pg docs and source code that potential errors do not influence optimizations.

There may or may not be an analysis about the side effects of nextval. I don't know. I thought I found something about this but I can't find it any more.

However I suspect the SQL standard has something to say about this, given that it defines SQL sequences.

[justinj]

Moving to 19.2.

[RaduBerinde]

@justinj is there anything else we want done here for 19.2? Do we want to re-instate the single-use inlining optimization to avoid regressions?

[justinj]

Semantics here are ok now—I think the single-use optimization is probably important, I will put that on my list of things to do

[RaduBerinde]

Single-use inlining was reinstated in #40673. Moving to 20.1 to track moving up all mutation WITHs to the top.