Optimizer choosing wrong plan for array contains operation with inverted index

[alistair-roacher]

Describe the problem

When optimising a 2 table join with a contains filter on an array column on one table and a sort/limit on a timestamp from the other table (no filter), the optimizer is choosing to full scan the index on the timestamp column rather than use the inverted index. This results in an execution of several seconds compared to 10ms or less.

To Reproduce

What did you do? Describe in your own words.

If possible, provide steps to reproduce the behavior:

1. Set up a CockroachDB cluster - could be a single node or even cockroach demo
2. Run the following SQL:

CREATE TABLE batches ( id UUID NOT NULL, create_request_id STRING NOT NULL, customer_id STRING NOT NULL, value_ts TIMESTAMPTZ NOT NULL, insertion_timestamp TIMESTAMPTZ NOT NULL DEFAULT now():::TIMESTAMPTZ, status INT2 NOT NULL, CONSTRAINT pk_batches PRIMARY KEY (id ASC), INDEX batches_value_ts_idx (value_ts ASC) );

CREATE TABLE instructions ( batch_id UUID NOT NULL, id UUID NOT NULL, customer_ids STRING[] NULL, customer_txn_id UUID NOT NULL, CONSTRAINT pk_instructions PRIMARY KEY (id ASC), CONSTRAINT fk_instruction_to_batch FOREIGN KEY (batch_id) REFERENCES batches(id), UNIQUE INDEX unique_instructions (batch_id ASC, customer_txn_id ASC), INVERTED INDEX instruction_customer_ids_idx (customer_ids), INDEX instruction_customer_txn_idx (customer_txn_id ASC) );

INSERT INTO batches SELECT gen_random_uuid(), gen_random_uuid(), gen_random_uuid()::STRING, now()-generate_series::INTERVAL, now(), 1 FROM generate_series(1,100000);

INSERT INTO instructions SELECT id, gen_random_uuid(), ARRAY[customer_id], gen_random_uuid() FROM batches;

3. Wait for the stats to be gathered (or force with ANALYZE on both tables)
4. Run the following with & without the EXPLAIN

EXPLAIN SELECT b.id, b.value_ts FROM batches AS b JOIN instructions i ON b.id = i.batch_id WHERE i.customer_ids @> '{caed8428-be5d-45a5-8b5b-0c68c8ff3d96}' ORDER BY b.value_ts DESC LIMIT 100;

Expected behavior The optimizer should use the instruction_customer_ids_idx INVERTED index to quickly identify the data to be selected, not perform a full scan of batches@batches_value_ts_idx

Additional data / screenshots A good plan can be forced with an index hint:

EXPLAIN SELECT b.id, b.value_ts FROM batches@pk_batches AS b JOIN instructions@instruction_customer_ids_idx i ON b.id = i.batch_id WHERE i.customer_ids @> ARRAY['caed8428-be5d-45a5-8b5b-0c68c8ff3d96'] ORDER BY b.value_ts ASC LIMIT 100;

Environment:

• CockroachDB versions: v21.2.14, v22.1.6
• Client app: cockroach sql

• Additional context Statement takes several seconds rather than a few ms

Add any other context about the problem here.

Jira issue: CRDB-19345

[DrewKimball]

This seems related to #85561 - the good plan has an index join for which the output rowcount estimate is much larger than the input estimate:

             ├── index-join instructions
             │    ├── columns: batch_id:9 customer_ids:11
             │    ├── stats: [rows=11111.11, ...]
             │    ├── cost: 26652.929
             │    └── scan instructions@instruction_customer_ids_idx [as=i]
             │         ├── columns: i.id:10
             │         ├── inverted constraint: /15/10
             │         │    └── spans: ["\x12caed8428-be5d-45a5-8b5b-0c68c8ff3d96\x00\x01", "\x12caed8428-be5d-45a5-8b5b-0c68c8ff3d96\x00\x01"]
             │         ├── flags: force-index=instruction_customer_ids_idx
             │         ├── stats: [rows=1.99982e-05, ...]
             │         ├── cost: 14.0200241
             │         └── key: (10)

However, I don't think fixing #85561 would be enough alone, since the index join is the input to a lookup join that is expected to be very expensive because it also uses the too-large rowcount. It's not obvious how to "see" the more correct, smaller estimate given by the forced-index scan for the lookup join, since it is "hidden" from the lookup join by the index join.

[DrewKimball]

Looks like the discrepancy in rowcount is because the original Select is unable to find any histograms with which to determine the selectivity of the contains filter, while the constrained scan uses one from the inverted index.

[alistair-roacher]

It's not obvious how to "see" the more correct, smaller estimate given by the forced-index scan for the lookup join, since it is "hidden" from the lookup join by the index join.

Unfortunately inverted indexes do not support storing additional columns - if they did we could store the batch_id in the inverted index and avoid the index join altogether.

[alistair-roacher]

Not sure if this is relevant, but I tried an additional test to show that the optimizer is aware of the selectivity of the contains filter. I inserted another set of 10,000 rows into instructions using a fixed value for the customer_ids array: INSERT INTO instructions SELECT id, gen_random_uuid(), ARRAY['caed8428-be5d-45a5-8b5b-0c68c8ff3d96'], gen_random_uuid() FROM batches;

Then the EXPLAIN for the index-hinted query shows that there will be a large number of rows returned from the contains filter:

• top-k │ estimated row count: 100 │ order: +value_ts │ k: 100 │ └── • lookup join │ estimated row count: 22,287 │ table: batches@pk_batches │ equality: (batch_id) = (id) │ equality cols are key │ └── • index join │ estimated row count: 22,222 │ table: instructions@pk_instructions │ └── • scan estimated row count: 96,519 (48% of the table; stats collected 4 minutes ago) table: instructions@instruction_customer_ids_idx spans: 1 span

[michae2]

Unfortunately inverted indexes do not support storing additional columns - if they did we could store the batch_id in the inverted index and avoid the index join altogether.

Filed https://github.com/cockroachdb/cockroach/issues/88278 about this.

[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 10 days to keep the issue queue tidy. Thank you for your contribution to CockroachDB!