sql: foreign key checks should only scan the primary column family of a row

[nvanbenschoten]

We currently scan all column families in the destination row when performing a foreign key check. We should limit this to the primary column family, which we know will never be missing as long as the row exists.

This has implications on transaction contention. For instance, see #30624.

cc. @knz for triage.

[knz]

@nvanbenschoten can you double check the issue description? Is this optimization also valid if the FK references a non-primary (unique) index?

[nvanbenschoten]

If we supported multiple column families in secondary indexes then it would be. I forget if we do or if secondary indexes are encoded in such a way that we could in the future. The only requirement is that we need to verify that the row exists, and that can be performed looking only at the primary column family of whatever index we need to look at. Scanning any other column families in the destination row is a waste.

[andy-kimball]

Ping @RaduBerinde. Would be good to keep this in mind when doing FK work.

[RaduBerinde]

@jordanlewis this will come down to optimizing the scans performed by lookup semi/anti joins.

[jordanlewis]

Yep - we'll make sure this gets done. Thanks!

[jordanlewis]

In conjunction with planning foreign key checks via the optimizer, this work was materially finished by @rohany in #38301. Assigning to @RaduBerinde to close once opt-driven fks are in.

[nvanbenschoten]

I just confirmed that this is still a blocker for #30624. This is true with and without sql.defaults.experimental_optimizer_foreign_keys.enabled enabled at the moment.

With a tpcc dataset initialized from that PR with 1 warehouse:

# In terminal 1
root@localhost:26257/tpcc> show create table district;
  table_name |                                         create_statement
+------------+--------------------------------------------------------------------------------------------------+
  district   | CREATE TABLE district (
             |     d_id INT8 NOT NULL,
             |     d_w_id INT8 NOT NULL,
             |     d_name VARCHAR(10) NULL,
             |     d_street_1 VARCHAR(20) NULL,
             |     d_street_2 VARCHAR(20) NULL,
             |     d_city VARCHAR(20) NULL,
             |     d_state CHAR(2) NULL,
             |     d_zip CHAR(9) NULL,
             |     d_tax DECIMAL(4,4) NULL,
             |     d_ytd DECIMAL(12,2) NULL,
             |     d_next_o_id INT8 NULL,
             |     CONSTRAINT "primary" PRIMARY KEY (d_w_id ASC, d_id ASC),
             |     CONSTRAINT fk_d_w_id_ref_warehouse FOREIGN KEY (d_w_id) REFERENCES warehouse(w_id),
             |     FAMILY static (d_id, d_w_id, d_name, d_street_1, d_street_2, d_city, d_state, d_zip, d_tax),
             |     FAMILY dynamic_1 (d_ytd),
             |     FAMILY dynamic_2 (d_next_o_id)
             | )

root@localhost:26257/tpcc> show create table history;
  table_name |                                                      create_statement
+------------+-----------------------------------------------------------------------------------------------------------------------------+
  history    | CREATE TABLE history (
             |     rowid UUID NOT NULL DEFAULT gen_random_uuid(),
             |     h_c_id INT8 NOT NULL,
             |     h_c_d_id INT8 NOT NULL,
             |     h_c_w_id INT8 NOT NULL,
             |     h_d_id INT8 NOT NULL,
             |     h_w_id INT8 NOT NULL,
             |     h_date TIMESTAMP NULL,
             |     h_amount DECIMAL(6,2) NULL,
             |     h_data VARCHAR(24) NULL,
             |     CONSTRAINT "primary" PRIMARY KEY (h_w_id ASC, rowid ASC),
             |     CONSTRAINT fk_h_c_w_id_ref_customer FOREIGN KEY (h_c_w_id, h_c_d_id, h_c_id) REFERENCES customer(c_w_id, c_d_id, c_id),
             |     CONSTRAINT fk_h_w_id_ref_district FOREIGN KEY (h_w_id, h_d_id) REFERENCES district(d_w_id, d_id),
             |     INDEX history_customer_fk_idx (h_c_w_id ASC, h_c_d_id ASC, h_c_id ASC),
             |     INDEX history_district_fk_idx (h_w_id ASC, h_d_id ASC),
             |     FAMILY "primary" (rowid, h_c_id, h_c_d_id, h_c_w_id, h_d_id, h_w_id, h_date, h_amount, h_data)
             | )

root@localhost:26257/tpcc> BEGIN;
BEGIN

root@localhost:26257/tpcc  OPEN> UPDATE district
SET d_next_o_id = d_next_o_id + 1
WHERE d_w_id = 0 AND d_id = 1
RETURNING d_tax, d_next_o_id;
  d_tax  | d_next_o_id
+--------+-------------+
  0.1692 |        3003

# Don't commit or rollback

# In terminal 2
root@localhost:26257/tpcc> insert into history values (DEFAULT, 1, 1, 0, 1, 0, '2006-01-02 15:04:05+00:00', 10, '9cdLXe0YhgLRrw');
... hangs ...

[RaduBerinde]

I tried to reproduce locally with two simple tables. A few things I found:

• make sure you restart your session(s) after changing the cluster setting
• once automatic stats run on the (almost) empty tables, the best plan for the FK check is a hash join. If I disable automatic stats I get the lookup join and the second session doesn't hang.

Can you get the EXPLAIN (VERBOSE) for the insert query?

[nvanbenschoten]

Even with those two changes, it still hangs. Here's the EXPLAIN (VERBOSE). It doesn't mention the FK lookup:

root@localhost:26257/tpcc> EXPLAIN (VERBOSE) insert into history values (DEFAULT, 1, 1, 0, 1, 0, '2006-01-02 15:04:05+00:00', 10, '9cdLXe0YhgLRrw');
          tree          |     field     |                                     description                                      |                                      columns                                       | ordering
+-----------------------+---------------+--------------------------------------------------------------------------------------+------------------------------------------------------------------------------------+----------+
                        | distributed   | false                                                                                |                                                                                    |
                        | vectorized    | false                                                                                |                                                                                    |
  count                 |               |                                                                                      | ()                                                                                 |
   └── insert           |               |                                                                                      | ()                                                                                 |
        │               | into          | history(rowid, h_c_id, h_c_d_id, h_c_w_id, h_d_id, h_w_id, h_date, h_amount, h_data) |                                                                                    |
        │               | strategy      | inserter                                                                             |                                                                                    |
        └── render      |               |                                                                                      | (column1, column2, column3, column4, column5, column6, column7, h_amount, column9) |
             │          | render 0      | column1                                                                              |                                                                                    |
             │          | render 1      | column2                                                                              |                                                                                    |
             │          | render 2      | column3                                                                              |                                                                                    |
             │          | render 3      | column4                                                                              |                                                                                    |
             │          | render 4      | column5                                                                              |                                                                                    |
             │          | render 5      | column6                                                                              |                                                                                    |
             │          | render 6      | column7                                                                              |                                                                                    |
             │          | render 7      | h_amount                                                                             |                                                                                    |
             │          | render 8      | column9                                                                              |                                                                                    |
             └── values |               |                                                                                      | (column1, column2, column3, column4, column5, column6, column7, column9, h_amount) |
                        | size          | 9 columns, 1 row                                                                     |                                                                                    |
                        | row 0, expr 0 | gen_random_uuid()                                                                    |                                                                                    |
                        | row 0, expr 1 | 1                                                                                    |                                                                                    |
                        | row 0, expr 2 | 1                                                                                    |                                                                                    |
                        | row 0, expr 3 | 0                                                                                    |                                                                                    |
                        | row 0, expr 4 | 1                                                                                    |                                                                                    |
                        | row 0, expr 5 | 0                                                                                    |                                                                                    |
                        | row 0, expr 6 | '2006-01-02 15:04:05+00:00'                                                          |                                                                                    |
                        | row 0, expr 7 | '9cdLXe0YhgLRrw'                                                                     |                                                                                    |
                        | row 0, expr 8 | 10                                                                                   |                                                                                    |

If I drop the FK, things do work, so that's where the contention is coming from.

[RaduBerinde]

If that is your explain, the new FK path is not on. Make sure you restarted the session if you changed the cluster setting, or use the session variable (set experimental_optimizer_foreign_keys = true;)

[nvanbenschoten]

Oh yes, you're right. The FK check does not conflict with the UPDATE when using the new FK path.

root@localhost:26257/tpcc> explain (verbose) insert into history values (DEFAULT, 1, 1, 0, 1, 0, '2006-01-02 15:04:05+00:00', 10, '9cdLXe0YhgLRrw');
                    tree                    |         field         |                                     description                                      |                                      columns                                       | ordering
+-------------------------------------------+-----------------------+--------------------------------------------------------------------------------------+------------------------------------------------------------------------------------+----------+
                                            | distributed           | false                                                                                |                                                                                    |
                                            | vectorized            | false                                                                                |                                                                                    |
  root                                      |                       |                                                                                      | ()                                                                                 |
   ├── count                                |                       |                                                                                      | ()                                                                                 |
   │    └── insert                          |                       |                                                                                      | ()                                                                                 |
   │         │                              | into                  | history(rowid, h_c_id, h_c_d_id, h_c_w_id, h_d_id, h_w_id, h_date, h_amount, h_data) |                                                                                    |
   │         │                              | strategy              | inserter                                                                             |                                                                                    |
   │         └── buffer node                |                       |                                                                                      | (column1, column2, column3, column4, column5, column6, column7, h_amount, column9) |
   │              │                         | label                 | buffer 1                                                                             |                                                                                    |
   │              └── render                |                       |                                                                                      | (column1, column2, column3, column4, column5, column6, column7, h_amount, column9) |
   │                   │                    | render 0              | column1                                                                              |                                                                                    |
   │                   │                    | render 1              | column2                                                                              |                                                                                    |
   │                   │                    | render 2              | column3                                                                              |                                                                                    |
   │                   │                    | render 3              | column4                                                                              |                                                                                    |
   │                   │                    | render 4              | column5                                                                              |                                                                                    |
   │                   │                    | render 5              | column6                                                                              |                                                                                    |
   │                   │                    | render 6              | column7                                                                              |                                                                                    |
   │                   │                    | render 7              | h_amount                                                                             |                                                                                    |
   │                   │                    | render 8              | column9                                                                              |                                                                                    |
   │                   └── values           |                       |                                                                                      | (column1, column2, column3, column4, column5, column6, column7, column9, h_amount) |
   │                                        | size                  | 9 columns, 1 row                                                                     |                                                                                    |
   │                                        | row 0, expr 0         | gen_random_uuid()                                                                    |                                                                                    |
   │                                        | row 0, expr 1         | 1                                                                                    |                                                                                    |
   │                                        | row 0, expr 2         | 1                                                                                    |                                                                                    |
   │                                        | row 0, expr 3         | 0                                                                                    |                                                                                    |
   │                                        | row 0, expr 4         | 1                                                                                    |                                                                                    |
   │                                        | row 0, expr 5         | 0                                                                                    |                                                                                    |
   │                                        | row 0, expr 6         | '2006-01-02 15:04:05+00:00'                                                          |                                                                                    |
   │                                        | row 0, expr 7         | '9cdLXe0YhgLRrw'                                                                     |                                                                                    |
   │                                        | row 0, expr 8         | 10                                                                                   |                                                                                    |
   ├── postquery                            |                       |                                                                                      | ()                                                                                 |
   │    └── error if rows                   |                       |                                                                                      | ()                                                                                 |
   │         └── lookup-join                |                       |                                                                                      | (column4, column3, column2)                                                        |
   │              │                         | table                 | customer@primary                                                                     |                                                                                    |
   │              │                         | type                  | anti                                                                                 |                                                                                    |
   │              │                         | equality              | (column4, column3, column2) = (c_w_id, c_d_id, c_id)                                 |                                                                                    |
   │              │                         | equality cols are key |                                                                                      |                                                                                    |
   │              │                         | parallel              |                                                                                      |                                                                                    |
   │              └── render                |                       |                                                                                      | (column4, column3, column2)                                                        |
   │                   │                    | render 0              | column4                                                                              |                                                                                    |
   │                   │                    | render 1              | column3                                                                              |                                                                                    |
   │                   │                    | render 2              | column2                                                                              |                                                                                    |
   │                   └── scan buffer node |                       |                                                                                      | (column1, column2, column3, column4, column5, column6, column7, h_amount, column9) |
   │                                        | label                 | buffer 1                                                                             |                                                                                    |
   └── postquery                            |                       |                                                                                      | ()                                                                                 |
        └── error if rows                   |                       |                                                                                      | ()                                                                                 |
             └── lookup-join                |                       |                                                                                      | (column6, column5)                                                                 |
                  │                         | table                 | district@primary                                                                     |                                                                                    |
                  │                         | type                  | anti                                                                                 |                                                                                    |
                  │                         | equality              | (column6, column5) = (d_w_id, d_id)                                                  |                                                                                    |
                  │                         | equality cols are key |                                                                                      |                                                                                    |
                  │                         | parallel              |                                                                                      |                                                                                    |
                  └── render                |                       |                                                                                      | (column6, column5)                                                                 |
                       │                    | render 0              | column6                                                                              |                                                                                    |
                       │                    | render 1              | column5                                                                              |                                                                                    |
                       └── scan buffer node |                       |                                                                                      | (column1, column2, column3, column4, column5, column6, column7, h_amount, column9) |
                                            | label                 | buffer 1                                                                             |                                                                                    |