Full index scan planned for tables with small number of rows

[chriscasano]

Describe the problem

A transaction retry is being fired when two transactions, each with inserts on a table that has a FK reference for tables with a small amount of records. It seems very similar to this issue: #41701. I believe the hash join / full scan on the constraint is blocking the other insert transaction. Below are my steps to reproduce the issue:

To Reproduce

Recreation steps

-- Create two terminal session and alternate between each step of the transaction to recreate
-- The retry occurs in terminal 1 when we insert into ch (2,2).
-- The first two inserts into p work.
-- The insert into ch waits in terminal 1
-- The insert into ch completes in terminal 2 which causes the ch insert in terminal 1 to retry.

-- Do this in one terminal
create table p (id int primary key);
create table ch (id int primary key, p_id int not null references p);
create index idx_ch_p_id on ch(p_id);

begin transaction;
insert into p values (1);
insert into ch values (1,1);
commit;

-- Do this in another terminal
begin transaction;
insert into p values (2);
insert into ch values (2,2);
commit;

-- Cleanup
drop table ch;
drop table p;

Terminal 1

root@:26257/ap> create table p (id int primary key);
create table ch (id int primary key, p_id int not null references p);
create index idx_ch_p_id on ch(p_id);
CREATE TABLE

Time: 122ms total (execution 122ms / network 0ms)

CREATE TABLE

Time: 561ms total (execution 260ms / network 300ms)

CREATE INDEX

Time: 1.071s total (execution 0.092s / network 0.979s)

root@:26257/ap> explain insert into p values (1);
        tree       |    field     |   description
-------------------+--------------+------------------
                   | distribution | local
                   | vectorized   | false
  insert fast path |              |
                   | into         | p(id)
                   | auto commit  |
                   | size         | 1 column, 1 row
(6 rows)

Time: 46ms total (execution 45ms / network 0ms)

root@:26257/ap> begin transaction;
BEGIN

Time: 0ms total (execution 0ms / network 0ms)

root@:26257/ap  OPEN> insert into p values (1);
INSERT 1

Time: 2ms total (execution 2ms / network 0ms)

root@:26257/ap  OPEN> explain insert into ch values (1,1);
               tree               |        field        |   description
----------------------------------+---------------------+-------------------
                                  | distribution        | local
                                  | vectorized          | false
  root                            |                     |
   ├── insert                     |                     |
   │    │                         | into                | ch(id, p_id)
   │    └── buffer                |                     |
   │         │                    | label               | buffer 1
   │         └── values           |                     |
   │                              | size                | 2 columns, 1 row
   └── fk-check                   |                     |
        └── error if rows         |                     |
             └── hash join (anti) |                     |
                  │               | equality            | (column2) = (id)
                  │               | left cols are key   |
                  │               | right cols are key  |
                  ├── scan buffer |                     |
                  │               | label               | buffer 1
                  └── scan        |                     |
                                  | estimated row count | 1
                                  | table               | p@primary
                                  | spans               | FULL SCAN
(21 rows)

Time: 1ms total (execution 1ms / network 0ms)

root@:26257/ap  OPEN> insert into ch values (1,1);
ERROR: restart transaction: TransactionRetryWithProtoRefreshError: TransactionAbortedError(ABORT_REASON_PUSHER_ABORTED): "sql txn" meta={id=4c4921eb key=/Table/185/1/1/0 pri=0.01029214 epo=0 ts=1605217678.414709000,0 min=1605217603.103393000,0 seq=3} lock=true stat=ABORTED rts=1605217661.518035000,2 wto=false max=1605217603.603393000,0
SQLSTATE: 40001

Terminal 2

root@:26257/ap> begin transaction;
BEGIN

Time: 0ms total (execution 1ms / network 0ms)

root@:26257/ap  OPEN> insert into p values (2);
INSERT 1

Time: 1ms total (execution 1ms / network 0ms)

root@:26257/ap  OPEN> insert into ch values (2,2);
INSERT 1

Time: 98ms total (execution 98ms / network 0ms)

root@:26257/ap  OPEN>

If applicable, add screenshots to help explain your problem.

Environment:

• CockroachDB version 20.2
• Server OS: Mac OS
• Client app: cockroach cli

gz#7820

[blathers-crl]

Hello, I am Blathers. I am here to help you get the issue triaged.

Hoot - a bug! Though bugs are the bane of my existence, rest assured the wretched thing will get the best of care here.

I have CC'd a few people who may be able to assist you:

• @RaduBerinde (author of opt: hash join instead of lookup join on small tables #41701)
• @nvanbenschoten (commented on opt: hash join instead of lookup join on small tables #41701)
• @lucy-zhang (found keywords: drop table)
• @solongordon (found keywords: join)
• @rafiss (found keywords: join)
• @asubiotto (found keywords: vectorize)

If we have not gotten back to your issue within a few business days, you can try the following:

• Join our community slack channel and ask on #cockroachdb.
• Try find someone from here if you know they worked closely on the area and CC them.

_{🦉 Hoot! I am a Blathers, a bot for CockroachDB. My owner is otan.}

[RaduBerinde]

The optimizer chooses a full table scan as a better plan when the table is very small. Once the table has more than a couple of rows (and automatic table statistics ran), it should switch to point lookups. We are considering assuming (in the optimizer) that all tables are at least a certain size, and that would fix this even for empy / single row tables.

[RaduBerinde]

Related to #56615.