3

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.

3
  • I added the EXPLAIN ANALYZE output, let me know whether there is something else I could provide. @LaurenzAlbe
    – LennartF22
    Sep 2, 2023 at 19:26
  • Creating statistics on the pair of expressions (num1 is not null), (num2 is not null) should work, but does not. You can see that the stats are available, but it doesn't use them. Maybe this is s bug.
    – jjanes
    Sep 3, 2023 at 18:42
  • @jjanes Yeah, I also tried creating statistics for the expression num1 IS NOT NULL AND num2 IS NOT NULL, which didn't work either, but creating statistics for the expression coalesce(num1 IS NOT NULL AND num2 IS NOT NULL) strangely does work (if you also modify the WHERE condition in the query accordingly). I don't understand why the coalesce would make a difference though. Maybe without it, the expression was too simple?!
    – LennartF22
    Sep 3, 2023 at 23:58

1 Answer 1

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;
6
  • is TC Q somehow related to postgrespro.com/list/thread-id/2598839? We also observer some "unexpected" behaviour when using partial indexes. Sep 3, 2023 at 9:40
  • I don't know what TC Q is, and I don't see an immediate connection to what you link to. This behavior is nor really unexpected. It could be that there is a fair number of rows where either num1 or num2 is NOT NULL, but there are only very few rows where both are NOT NULL. PostgreSQL has no knowledge of such dependencies. One way that PostgreSQL could be improved is by taking the row count of a partial index for a row estimate of the query, but that isn't done. Sep 3, 2023 at 12:13
  • @LaurenzAlbe ANALYZE and CROSS JOIN LATERAL both don't seem to help, as the generated query plan is equal to the one from the original query (I guess the query planner is smart enough to recognize what we actually want to do). Instead I found that using b.a_id BETWEEN a.id AND a.id as the join condition does help, although it's not pretty and will probably have to be done like this for every additional join I might add.
    – LennartF22
    Sep 3, 2023 at 16:57
  • Thanks for the feedback. Can you try my updated query? But if you found another solution, that's cool too. Sep 3, 2023 at 19:18
  • 1
    With the added OFFSET it's working, although the same limitations as for the BETWEEN approach apply. I found a hack for making extended statistics work somewhat correctly, see the comments below the OP.
    – LennartF22
    Sep 4, 2023 at 0:00

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.