sql: tuple + BETWEEN generates loose spans

[danhhz]

root@:26257/d> CREATE TABLE t (a INT, b INT, PRIMARY KEY (a, b));
CREATE TABLE

Time: 4.984ms

root@:26257/d> SHOW TRACE FOR SELECT * FROM t WHERE (a, b) BETWEEN (1, 2) AND (3, 4);
+----------------------------------+---------+-------------------------------------------------------+-----------------------------------+-----------------------------------+-------+
|            timestamp             |   age   |                        message                        |              context              |             operation             | span  |
+----------------------------------+---------+-------------------------------------------------------+-----------------------------------+-----------------------------------+-------+
| 2017-12-05 20:56:58.626476+00:00 | 0s      | === SPAN START: sql txn implicit ===                  | NULL                              | sql txn implicit                  | (0,0) |
| 2017-12-05 20:56:58.627186+00:00 | 710µs   | === SPAN START: starting plan ===                     | NULL                              | starting plan                     | (0,1) |
| 2017-12-05 20:56:58.627201+00:00 | 725µs   | === SPAN START: consuming rows ===                    | NULL                              | consuming rows                    | (0,2) |
| 2017-12-05 20:56:58.627223+00:00 | 747µs   | Scan /Table/51/{1/1/2-2}                              | [client=[::1]:49903,user=root,n1] | sql txn implicit                  | (0,0) |
| 2017-12-05 20:56:58.627251+00:00 | 775µs   | querying next range at /Table/51/1/1/2                | [client=[::1]:49903,user=root,n1] | sql txn implicit                  | (0,0) |
| 2017-12-05 20:56:58.627281+00:00 | 805µs   | r19: sending batch 1 Scan to (n1,s1):1                | [client=[::1]:49903,user=root,n1] | sql txn implicit                  | (0,0) |
| 2017-12-05 20:56:58.627317+00:00 | 841µs   | sending request to local server                       | [client=[::1]:49903,user=root,n1] | sql txn implicit                  | (0,0) |
| 2017-12-05 20:56:58.627396+00:00 | 920µs   | === SPAN START: /cockroach.roachpb.Internal/Batch === | NULL                              | /cockroach.roachpb.Internal/Batch | (0,3) |
| 2017-12-05 20:56:58.627401+00:00 | 925µs   | 1 Scan                                                | [n1]                              | /cockroach.roachpb.Internal/Batch | (0,3) |
| 2017-12-05 20:56:58.627405+00:00 | 929µs   | read has no clock uncertainty                         | [n1]                              | /cockroach.roachpb.Internal/Batch | (0,3) |
| 2017-12-05 20:56:58.627411+00:00 | 935µs   | executing 1 requests                                  | [n1,s1]                           | /cockroach.roachpb.Internal/Batch | (0,3) |
| 2017-12-05 20:56:58.627421+00:00 | 945µs   | read-only path                                        | [n1,s1,r19/1:/{Table/51-Max}]     | /cockroach.roachpb.Internal/Batch | (0,3) |
| 2017-12-05 20:56:58.62743+00:00  | 954µs   | command queue                                         | [n1,s1,r19/1:/{Table/51-Max}]     | /cockroach.roachpb.Internal/Batch | (0,3) |
| 2017-12-05 20:56:58.627439+00:00 | 963µs   | waiting for read lock                                 | [n1,s1,r19/1:/{Table/51-Max}]     | /cockroach.roachpb.Internal/Batch | (0,3) |
| 2017-12-05 20:56:58.627482+00:00 | 1ms6µs  | read completed                                        | [n1,s1,r19/1:/{Table/51-Max}]     | /cockroach.roachpb.Internal/Batch | (0,3) |
| 2017-12-05 20:56:58.627518+00:00 | 1ms42µs | plan completed execution                              | [client=[::1]:49903,user=root,n1] | consuming rows                    | (0,2) |
| 2017-12-05 20:56:58.62752+00:00  | 1ms44µs | resources released, stopping trace                    | [client=[::1]:49903,user=root,n1] | consuming rows                    | (0,2) |
+----------------------------------+---------+-------------------------------------------------------+-----------------------------------+-----------------------------------+-------+
(17 rows)

I'd expect this scan to be [/Table/51/1/1/2,/Table/51/1/3/5). This is coming up in some upcoming partitioning tests where too many partitions are being scanned. Same things happens for WHERE (a,b) >= (1, 2) AND (a, b) <= (3, 4)

@RaduBerinde can you triage this for me please?

[RaduBerinde]

root@:26257/test> EXPLAIN (VERBOSE) SELECT * FROM t WHERE (a, b) BETWEEN (1, 2) AND (3, 4);
+-------+------+--------+-------------------------------------------+---------+----------------------------+
| Level | Type | Field  |                Description                | Columns |          Ordering          |
+-------+------+--------+-------------------------------------------+---------+----------------------------+
|     0 | scan |        |                                           | (a, b)  | a!=NULL; b!=NULL; key(a,b) |
|     0 |      | table  | t@primary                                 |         |                            |
|     0 |      | spans  | /1/2-                                     |         |                            |
|     0 |      | filter | ((a, b) >= (1, 2)) AND ((a, b) <= (3, 4)) |         |                            |
+-------+------+--------+-------------------------------------------+---------+----------------------------+

Indeed, the span doesn't look right.

Interestingly, separating each condition yields the expected spans:

root@:26257/test> EXPLAIN (VERBOSE) SELECT * FROM t WHERE (a, b) >= (1, 2);
+-------+------+--------+------------------+---------+----------------------------+
| Level | Type | Field  |   Description    | Columns |          Ordering          |
+-------+------+--------+------------------+---------+----------------------------+
|     0 | scan |        |                  | (a, b)  | a!=NULL; b!=NULL; key(a,b) |
|     0 |      | table  | t@primary        |         |                            |
|     0 |      | spans  | /1/2-            |         |                            |
|     0 |      | filter | (a, b) >= (1, 2) |         |                            |
+-------+------+--------+------------------+---------+----------------------------+

root@:26257/test> EXPLAIN (VERBOSE) SELECT * FROM t WHERE (a, b) <= (3, 4);
+-------+------+--------+------------------+---------+----------------------------+
| Level | Type | Field  |   Description    | Columns |          Ordering          |
+-------+------+--------+------------------+---------+----------------------------+
|     0 | scan |        |                  | (a, b)  | a!=NULL; b!=NULL; key(a,b) |
|     0 |      | table  | t@primary        |         |                            |
|     0 |      | spans  | /!NULL-/3/4/#    |         |                            |
|     0 |      | filter | (a, b) <= (3, 4) |         |                            |
+-------+------+--------+------------------+---------+----------------------------+
(4 rows)

[danhhz]

One tuple and one non-tuple also works

root@:26257/d> EXPLAIN (VERBOSE) SELECT * FROM t WHERE (a, b) >= (1, 2) AND a < 4;
+-------+------+--------+------------------+---------+----------------------------+
| Level | Type | Field  |   Description    | Columns |          Ordering          |
+-------+------+--------+------------------+---------+----------------------------+
|     0 | scan |        |                  | (a, b)  | a!=NULL; b!=NULL; key(a,b) |
|     0 |      | table  | t@primary        |         |                            |
|     0 |      | spans  | /1/2-/4          |         |                            |
|     0 |      | filter | (a, b) >= (1, 2) |         |                            |
+-------+------+--------+------------------+---------+----------------------------+
(4 rows)

[RaduBerinde]

The makeIndexConstraints code is a zoo when it comes to tuples. I believe the problematic line is:
https://github.com/cockroachdb/cockroach/blob/master/pkg/sql/opt_index_selection.go#L635

We are incrementing i even though we may have more andExprs to look at for this i.

This is very old code: 396d543
Not quite sure what a short term fix would be.. Longer term, this code should be rewritten from the ground up (#6346).

@danhhz How critical is this for 1.2?

[danhhz]

How critical is this for 1.2?

Good question. I've thought about this a lot more and have convinced myself that this should really be more of a 1.3 thing. From a domiciling perspective, we've got a lot more work to do anyway and for that will probably need some checks at a much lower layer

[danhhz]

Unassigning for now since there's nothing to be done immediately. Thanks for the investigation @RaduBerinde!

[RaduBerinde]

Note that #21317 adds a regression logic test for this.

[benesch]

Sweet! Thanks!