PostgreSQL Query Planner overestimating Row Count leads to slow Hash Join

Question

I have a table with two columns and about 10M rows. About half the records are NULL in the first field, and about half the records are NULL in the second field, although there are a few hundred records that have a non-NULL value in both fields.

When I want to query all records that have both values set, the PostgreSQL query planner assumes that both columns are statistically independent, so it expects that the query will return 2.5M rows (50% of 50% of 10M total rows), while it actually returns a mere 1000 rows.

This overestimation of rows causes bad optimization decisions later on in the query planning process, because if I want to join the table to another table with many rows, it chooses a hash join, while a nested loop join would be multiple orders of magnitude quicker.

Below is a simplified definition of the tables that I am talking about:

CREATE TABLE a (
    id serial PRIMARY KEY,
    num1 integer,
    num2 integer
);

-- partial index for finding rows with both values set
CREATE INDEX a_num1_num2_idx ON a (num1, num2)
WHERE num1 IS NOT NULL AND num2 IS NOT NULL;

CREATE TABLE b (
    id serial PRIMARY KEY,
    a_id integer REFERENCES a (id)
);

-- foreign key index
CREATE INDEX b_a_id_idx ON b (a_id);

-- 5M records with NULL in first column
INSERT INTO a (num1, num2)
SELECT NULL, random() * 1000000
FROM generate_series(1, 5000000);

-- 5M records with NULL in second column
INSERT INTO a (num1, num2)
SELECT random() * 1000000, NULL
FROM generate_series(1, 5000000);

-- 1000 records with both values set
UPDATE a SET
    num1 = random() * 1000000,
    num2 = random() * 1000000
WHERE random() < 0.0001;

-- add some records in other table to join to
INSERT INTO b (a_id)
SELECT id
FROM a;

The rather simple query below takes 8000ms with hash and merge joins enabled, and 50ms with only nested loop joins left enabled.

SELECT count(*) FROM a JOIN b ON a.id = b.a_id WHERE num1 IS NOT NULL AND num2 IS NOT NULL;

postgres=*# SET LOCAL random_page_cost = 1.0;
SET
postgres=*# SET LOCAL max_parallel_workers_per_gather = 0;
SET
postgres=*# EXPLAIN ANALYZE SELECT count(*) FROM a JOIN b ON a.id = b.a_id WHERE num1 IS NOT NULL AND num2 IS NOT NULL;
                                                                    QUERY PLAN
--------------------------------------------------------------------------------------------------------------------------------------------------
 Aggregate  (cost=384740.28..384740.29 rows=1 width=8) (actual time=7201.943..7201.950 rows=1 loops=1)
   ->  Hash Join  (cost=120100.63..378490.35 rows=2499971 width=0) (actual time=2119.769..7201.733 rows=1034 loops=1)
         Hash Cond: (b.a_id = a.id)
         ->  Seq Scan on b  (cost=0.00..144247.77 rows=9999977 width=4) (actual time=8.768..2035.219 rows=10000000 loops=1)
         ->  Hash  (cost=79084.92..79084.92 rows=2499977 width=4) (actual time=2.002..2.005 rows=1034 loops=1)
               Buckets: 262144  Batches: 32  Memory Usage: 2050kB
               ->  Index Scan using a_num1_num2_idx on a  (cost=0.28..79084.92 rows=2499977 width=4) (actual time=0.064..0.781 rows=1034 loops=1)
 Planning Time: 0.474 ms
 JIT:
   Functions: 11
   Options: Inlining false, Optimization false, Expressions true, Deforming true
   Timing: Generation 1.797 ms, Inlining 0.000 ms, Optimization 0.538 ms, Emission 7.842 ms, Total 10.176 ms
 Execution Time: 7203.964 ms
(13 rows)

postgres=*# SET LOCAL enable_hashjoin = off;
SET
postgres=*# SET LOCAL enable_mergejoin = off;
SET
postgres=*# EXPLAIN ANALYZE SELECT count(*) FROM a JOIN b ON a.id = b.a_id WHERE num1 IS NOT NULL AND num2 IS NOT NULL;
                                                                 QUERY PLAN
--------------------------------------------------------------------------------------------------------------------------------------------
 Aggregate  (cost=1268992.21..1268992.22 rows=1 width=8) (actual time=50.841..50.844 rows=1 loops=1)
   ->  Nested Loop  (cost=0.71..1262742.28 rows=2499971 width=0) (actual time=42.603..50.681 rows=1034 loops=1)
         ->  Index Scan using a_num1_num2_idx on a  (cost=0.28..79084.92 rows=2499977 width=4) (actual time=0.035..0.915 rows=1034 loops=1)
         ->  Index Only Scan using b_a_id_idx on b  (cost=0.43..0.46 rows=1 width=4) (actual time=0.006..0.006 rows=1 loops=1034)
               Index Cond: (a_id = a.id)
               Heap Fetches: 0
 Planning Time: 0.269 ms
 JIT:
   Functions: 5
   Options: Inlining true, Optimization true, Expressions true, Deforming true
   Timing: Generation 0.911 ms, Inlining 9.734 ms, Optimization 18.465 ms, Emission 13.940 ms, Total 43.051 ms
 Execution Time: 51.936 ms
(12 rows)

How can I properly fix this behavior, i.e. without setting enable_hashjoin and enable_mergejoin to off? I already tried adding more statistics, but without success so far.

Answer 1

First, try to gather accurate statistics:

ANALYZE a;

If that doesn't help, you can choose the ugly solution of rewriting the query so that you force a nested loop join:

SELECT count(*)
FROM a
CROSS JOIN LATERAL (SELECT FROM b
                    WHERE a.id = b.a_id
                    OFFSET 0)
WHERE a.num1 IS NOT NULL
  AND a.num2 IS NOT NULL;