Incorrect row count estimate when joining parent and child tables on foreign key columns

Describe the problem When there is a foreign key constraint having predicates which are a superset of the join predicates, the row count estimate should be the same as scanning the foreign key child table. For example:

CREATE TABLE fk_parent (
  a INT NOT NULL,
  b INT NOT NULL,
  c INT NOT NULL,
  UNIQUE INDEX (b),
  UNIQUE INDEX (c),
  UNIQUE INDEX (a,b,c),
  UNIQUE INDEX (a,c),
  UNIQUE INDEX (a,b)
);

CREATE TABLE fk_child (
  a INT,
  b INT,
  c INT,
  FOREIGN KEY (a, b, c) REFERENCES fk_parent (a, b, c) ON UPDATE CASCADE
);
INSERT INTO fk_parent select g,g,g from generate_series(1,100000) g(g);
INSERT INTO fk_child select g,g,g from generate_series(1,100000) g(g);
ANALYZE fk_parent;
ANALYZE fk_child;

EXPLAIN
SELECT 1
FROM fk_child
INNER JOIN fk_parent USING (a,b);
                                             info
----------------------------------------------------------------------------------------------
  distribution: local
  vectorized: true

  • render
  │
  └── • hash join
      │ estimated row count: 1
      │ equality: (a, b) = (a, b)
      │ right cols are key
      │
      ├── • scan
      │     estimated row count: 100,000 (100% of the table; stats collected 0 seconds ago)
      │     table: fk_child@fk_child_pkey
      │     spans: FULL SCAN
      │
      └── • scan
            estimated row count: 100,000 (100% of the table; stats collected 24 minutes ago)
            table: fk_parent@fk_parent_a_b_key
            spans: FULL SCAN

Since we know every combined value of fk_child.a, fk_child.b has a matching value of fk_parent.a, fk_parent.b, the estimated row count here should be 100,000 instead of 1.

Jira issue: CRDB-21121

cockroachdb / cockroach

Incorrect row count estimate when joining parent and child tables on foreign key columns #91142