opt: Optimizer using zigzag join and selecting the wrong index

[rmloveland]

Describe the problem

Working on docs for CBO index selection in the face of zone configs and lease preferences (https://github.com/cockroachdb/docs/issues/4586). As part of that, ran a query on a basically empty table (see below), which led to the wrong index being selected.

Quoth Andy Kimball:

I suspect it's due to problems with costing when stats say we have 0 rows in the table. Once that gets fixed, we should see the right index being selected

To Reproduce

What I was trying to accomplish is:

• Set up a 3-node cluster with west, central, and eastern regions.
• By default, queries against the token table should generally run on the western node, with central as a backup.
• If the query is coming from central, and the leaseholders are in central, it should prefer the central and east indexes, in that order.
• If the query is coming from east, and the leaseholders are in the east for that data, it should prefer the east and central indexes, in that order. (All of the above presumes that write traffic from e.g. the central node will cause the leaseholders for that data to be moved to that node.)

Cluster startup:

$ cockroach start   --locality=region=us-east --insecure --store=/tmp/node0 --listen-addr=localhost:26257 --http-port=8888  --join=localhost:26257,localhost:26258,localhost:26259
$ cockroach start   --locality=region=us-central --insecure --store=/tmp/node1 --listen-addr=localhost:26258 --http-port=8889  --join=localhost:26257,localhost:26258,localhost:26259
$ cockroach start   --locality=region=us-west --insecure --store=/tmp/node2 --listen-addr=localhost:26259 --http-port=8890  --join=localhost:26257,localhost:26258,localhost:26259
$ cockroach init --insecure --host=localhost --port=26257

SQL code:

SELECT version();
                                                            version                                                             
+------------------------------------------------------------------------------------------------------------------------------+
  CockroachDB CCL v19.1.0-beta.20190318-950-gb47269e069-dirty (x86_64-apple-darwin16.7.0, built 2019/04/18 18:51:49, go1.11.5)  
(1 row)

Time: 1.47ms

CREATE DATABASE if NOT EXISTS auth;
USE auth;

CREATE TABLE token (
    token_id VARCHAR(100) NULL,
    access_token VARCHAR(4000) NULL,
    refresh_token VARCHAR(4000) NULL
);

CREATE INDEX token_id_west_idx ON token (token_id) STORING (access_token, refresh_token);

CREATE INDEX token_id_central_idx ON token (token_id) STORING (access_token, refresh_token);

CREATE INDEX token_id_east_idx ON token (token_id) STORING (access_token, refresh_token);

ALTER TABLE token CONFIGURE ZONE USING
      num_replicas = 5, constraints = '{+region=us-east: 1, +region=us-central: 2, +region=us-west: 2}', lease_preferences = '[[+region=us-west], [+region=us-central]]';

-- Enter license keys to access the ALTER INDEX commands below
-- (For testing keys see https://cockroachlabs.slack.com/archives/C2C5FKPPB/p1501868500330889)

ALTER INDEX token_id_east_idx CONFIGURE ZONE USING num_replicas = 5,
      constraints = '{+region=us-east: 2, +region=us-central: 2, +region=us-west: 1}', lease_preferences = '[[+region=us-east], [+region=us-central]]';

ALTER INDEX token_id_central_idx CONFIGURE ZONE USING num_replicas = 5,
      constraints = '{+region=us-east: 2, +region=us-central: 2, +region=us-west: 1}', lease_preferences = '[[+region=us-central], [+region=us-east]]';

ALTER INDEX token_id_west_idx CONFIGURE ZONE USING num_replicas = 5,
      constraints = '{+region=us-west: 2, +region=us-central: 2, +region=us-east: 1}', lease_preferences = '[[+region=us-west], [+region=us-central]]';

SHOW ZONE CONFIGURATIONS;

-- Should result in:

--   ... snip ...

--   auth.token                      | ALTER TABLE auth.public.token CONFIGURE ZONE USING                                    
--                                   |     num_replicas = 5,                                                                 
--                                   |     constraints = '{+region=us-central: 2, +region=us-east: 1, +region=us-west: 2}',  
--                                   |     lease_preferences = '[[+region=us-west], [+region=us-central]]'                   
--   auth.token@token_id_east_idx    | ALTER INDEX auth.public.token@token_id_east_idx CONFIGURE ZONE USING                  
--                                   |     num_replicas = 5,                                                                 
--                                   |     constraints = '{+region=us-central: 2, +region=us-east: 2, +region=us-west: 1}',  
--                                   |     lease_preferences = '[[+region=us-east], [+region=us-central]]'                   
--   auth.token@token_id_central_idx | ALTER INDEX auth.public.token@token_id_central_idx CONFIGURE ZONE USING               
--                                   |     num_replicas = 5,                                                                 
--                                   |     constraints = '{+region=us-central: 2, +region=us-east: 2, +region=us-west: 1}',  
--                                   |     lease_preferences = '[[+region=us-central], [+region=us-east]]'                   
--   auth.token@token_id_west_idx    | ALTER INDEX auth.public.token@token_id_west_idx CONFIGURE ZONE USING                  
--                                   |     num_replicas = 5,                                                                 
--                                   |     constraints = '{+region=us-central: 2, +region=us-east: 1, +region=us-west: 2}',  
--                                   |     lease_preferences = '[[+region=us-west], [+region=us-central]]'                   
-- (10 rows)

-- Time: 29.718ms

-- Run the inserts below from the central node

UPSERT
INTO
    token (token_id, access_token, refresh_token)
VALUES
    (
        'DE32D09E-5C92-11E9-83EA-8E9B5FAC1A65',
        '5106F0DC-5C93-11E9-9430-508660AC1A65',
        '581E11F2-5C93-11E9-BA89-568660AC1A65'
    );

UPSERT
INTO
    token (token_id, access_token, refresh_token)
VALUES
    (
        '85748136-5C93-11E9-888B-678660AC1A65',
        '8AC3048C-5C93-11E9-90C5-6D8660AC1A65',
        '8FB28A1C-5C93-11E9-81BE-738660AC1A65'
    );

UPSERT
INTO
    token (token_id, access_token, refresh_token)
VALUES
    (
        '2E1B5BFE-6152-11E9-B9FD-A7E0F13211D9',
        '49E36152-6152-11E9-8CDC-3682F23211D9',
        '4E0E91B6-6152-11E9-BAC1-3782F23211D9'
    );

-- Run the explain from the central node.  Expectations:
-- 1. It will use the central or east indexes, in that order.
-- 2. Doing the writes from the central node means the leaseholders are on the central node

EXPLAIN
    SELECT
        access_token, refresh_token
    FROM
        token
    WHERE
        token_id = '2E1B5BFE-6152-11E9-B9FD-A7E0F13211D9';

-- Actual output shows west and central indexes used despite leaseholder prefs (?)
--
--          tree       |   field   |                 description                  
-- +------------------+-----------+---------------------------------------------+
--   render           |           |                                              
--    └── zigzag-join |           |                                              
--         │          | type      | inner                                        
--         │          | pred      | @1 = '2E1B5BFE-6152-11E9-B9FD-A7E0F13211D9'  
--         ├── scan   |           |                                              
--         │          | table     | token@token_id_west_idx                      
--         │          | fixedvals | 1 column                                     
--         └── scan   |           |                                              
--                    | table     | token@token_id_central_idx                   
--                    | fixedvals | 1 column                                     
-- (10 rows)

-- Time: 754µs

[rmloveland]

@justinj FYI

[github-actions[bot]]

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]

this has been fixed