opt: rewrite const OP ANY(subquery) as EXISTS(subquery WHERE ... OP const)

[justinj]

These two queries are equivalent:

[email protected]:58515/defaultdb> explain select exists(select * from y where b = 3);
       tree      |    field     |             description
+----------------+--------------+--------------------------------------+
  root           |              |
   ├── values    |              |
   │             | size         | 1 column, 1 row
   └── subquery  |              |
        │        | id           | @S1
        │        | original sql | EXISTS (SELECT * FROM y WHERE b = 3)
        │        | exec mode    | exists
        └── scan |              |
                 | table        | y@primary
                 | spans        | /3-/3/#
(10 rows)

Time: 1.24ms

[email protected]:58515/defaultdb> explain (opt) select 3 = any(select b from y);
           text
+-------------------------+
  values
   └── tuple
        └── any: eq
             ├── scan y
             └── const: 3
(5 rows)

Time: 597µs

However, the first is significantly better since it can generate spans.

It might be the case that it's better to address this by instead hoisting the subquery, which would be a more general solution, but wouldn't generate spans at plan time which might be valuable (and is also blocked in the common case by #37240).

Jira issue: CRDB-4443

[justinj]

Perhaps the cleaner way to do this would be to hoist the subquery and then add a rule that simplifies that kind of join with a VALUES clause into a Select,

[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!

[knz]

still exists in 21.1

[mgartner]

Unfortunately, i = ANY (SELECT a FROM t) is not equivalent to EXISTS (SELECT * FROM t WHERE a = i in all cases. ANY has some unexpected behavior in the presence of NULL either on the LHS of the comparison, or within the results on the RHS:

The Postgres docs explain this:

... The result is “false” if no true result is found (including the case where the array has zero elements)...

... If the left-hand expression yields null, the result of ANY is ordinarily null (though a non-strict comparison operator could possibly yield a different result). Also, if the right-hand array contains any null elements and no true comparison result is obtained, the result of ANY will be null, not false (again, assuming a strict comparison operator). This is in accordance with SQL's normal rules for Boolean combinations of null values.

Here's how this plays out in practice:

CREATE TABLE t_without_null (a INT);
INSERT INTO t_without_null VALUES (1);

CREATE TABLE t_with_null (a INT);
INSERT INTO t_with_null VALUES (NULL), (1);

CREATE TABLE t_empty (a INT);

SELECT
  i,
  i = ANY (SELECT a FROM t_without_null) AS "any - t_without_null",
  EXISTS (SELECT a FROM t_without_null WHERE a = i) AS "exists - t_without_null",
  i = ANY (SELECT a FROM t_with_null) AS "any - t_with_null",
  EXISTS (SELECT a FROM t_with_null WHERE a = i) AS "exists - t_with_null",
  i = ANY (SELECT a FROM t_empty) AS "any - t_empty",
  EXISTS (SELECT a FROM t_empty WHERE a = i) AS "exists - t_empty"
FROM (VALUES (1), (2), (NULL)) v(i);

  i   | any - t_without_null | exists - t_without_null | any - t_with_null | exists - t_with_null | any - t_empty | exists - t_empty
------+----------------------+-------------------------+-------------------+----------------------+---------------+------------------
    1 | t                    | t                       | t                 | t                    | f             | f
    2 | f                    | f                       | NULL              | f                    | f             | f
 NULL | NULL                 | f                       | NULL              | f                    | f             | f
(3 rows)

I'm motivated to make a rewrite like this work - it'll vastly simplify the optimizer and execution engine if we can get rid of bespoke support for ANY entirely. But it's proving to be difficult.

One of the most difficult hurdles to overcome is supporting this bizarre behavior (which I've extracted from the results above):

CREATE TABLE t_empty (a INT);

SELECT NULL = ANY (SELECT * FROM t_empty);

 ?column?
---------
 f
(1 row)

If the contents of the ANY are empty, the result is false even if the LHS of the comparison is NULL.

[mgartner]

I think the following is a valid rewrite:

i = ANY (SELECT a FROM t)
=>
(SELECT count(*) > 0 AND
  (bool_or(a = i)  OR (
    CASE
    WHEN bool_or(a IS NULL) THEN NULL
    ELSE (CASE WHEN i IS NULL THEN NULL ELSE false END)
    END
  ))
FROM t)

Here's some tests showing its equivalence (in Postgres): https://gist.github.com/mgartner/9dac0b802c087329a8e2ee4ff0204bbd

[mgartner]

I used this transformation in #98375. I don't think we should use it yet universally, though, because it can lead to plans with slow apply-joins.

Also, it doesn't provide the benefit originally described in this issue - it won't allow constrained scans to be performed. If columns can be prove to be non-NULL then a simpler transformation may be possible. For now I'm going to close this issue.