Message-ID: <b860c71a-7cab-4d88-ad87-8c1f2eea9ae8@dalibo.com>
Date: Fri, 22 Nov 2024 16:53:39 +0100
MIME-Version: 1.0
User-Agent: Mozilla Thunderbird
From: =?UTF-8?Q?Fr=C3=A9d=C3=A9ric_Yhuel?= <frederic.yhuel@dalibo.com>
Content-Language: en-US
To: pgsql-performance@lists.postgresql.org
Cc: Christophe Courtois <christophe.courtois@dalibo.com>
Subject: Cardinality estimate of the inner relation
Autocrypt: addr=frederic.yhuel@dalibo.com; keydata=
 xjMEXn3bgxYJKwYBBAHaRw8BAQdA6tX5FT/n5ztMWIoBdl6k5avvu65fv6ryfVzIx/aH3V3N
 JEYuIFlodWVsIDxmcmVkZXJpYy55aHVlbEBkYWxpYm8uY29tPsKWBBMWCAA+FiEEi7OTyf6H
 ePS+C6n11XGWhN8zGNUFAmZDVJ8CGwMFCQtfi90FCwkIBwIGFQoJCAsCBBYCAwECHgECF4AA
 CgkQ1XGWhN8zGNV65gEA6o+UrebFjn2CIAOYwP3CiiJugiM5TMH9yJyehQua5ZoA/2ChxiVn
 8OUaAw/ErxJmQi1mSN0tNZBL/KhkUPBDUDQNzjgEXn3bgxIKKwYBBAGXVQEFAQEHQCuh5cLQ
 AtEBXHa2Fmtp0kduBu7msM7qO/gaEcdjFUdiAwEIB8J+BBgWCAAmAhsMFiEEi7OTyf6HePS+
 C6n11XGWhN8zGNUFAmZDVJ8FCQtfi90ACgkQ1XGWhN8zGNWOOAEArSqePBqfd4Kx4ulACaWO
 6fM+XSDfUlBAQXx9rU6DR4MBALwozl9g91tRysim6lKxggvBfp/PvbpTZNrxYLWB2fYP
Content-Type: text/plain; charset=UTF-8; format=flowed
Content-Transfer-Encoding: 7bit
Archived-At: 
 <https://www.postgresql.org/message-id/b860c71a-7cab-4d88-ad87-8c1f2eea9ae8%40dalibo.com>
Precedence: bulk

My colleague Christophe Courtois and I have been trying to fix a bad 
plan for one of Dalibo's clients. It is a (probably well-known) problem 
with skewed data and a parameterized Nested Loop with an underestimation 
of the cardinality of the inner relation.

Here is a test case (the script to create and populate the two tables is 
at the end):

EXPLAIN (ANALYZE, SETTINGS)
   SELECT name, sum(quantity)
   FROM products p
   JOIN orders o ON (p.id = o.product_id)
   WHERE p.name = 'babar'        /*    28% of orders    */
   GROUP BY name;
  
QUERY PLAN 

--------------------------------------------------------------------------------------------------------------------------------------------------
  GroupAggregate  (cost=5.50..1022.27 rows=1 width=40) (actual 
time=66.213..66.215 rows=1 loops=1)
    ->  Nested Loop  (cost=5.50..1019.29 rows=1189 width=36) (actual 
time=0.083..56.991 rows=320000 loops=1)
          ->  Bitmap Heap Scan on products p  (cost=5.08..250.17 rows=85 
width=40) (actual time=0.058..0.153 rows=80 loops=1)
                Recheck Cond: (name = 'babar'::text)
                Heap Blocks: exact=80
                ->  Bitmap Index Scan on products_name_idx 
(cost=0.00..5.06 rows=85 width=0) (actual time=0.030..0.031 rows=80 loops=1)
                      Index Cond: (name = 'babar'::text)
          ->  Index Scan using orders_product_id_idx on orders o 
(cost=0.43..8.79 rows=26 width=12) (actual time=0.006..0.440 rows=4000 
loops=80)
                Index Cond: (product_id = p.id)
  Planning Time: 0.560 ms
  Execution Time: 66.268 ms

The cardinaly estimate on 'orders' is wrong (26 rows against 4000), 
hence the Nested Loop.
Any other value for product.name gives less rows and a good plan (i.e. 
NL makes more sense).

If I'm not wrong, the row count estimate for the inner table is computed 
as follow:

SELECT n_distinct AS product_id_n_distinct FROM pg_stats
   WHERE tablename = 'orders' AND attname = 'product_id' \gset

SELECT reltuples AS orders_tuples FROM pg_class
   WHERE relname = 'orders' \gset

SELECT :orders_tuples / :product_id_n_distinct AS inner_estimation;
   inner_estimation
---------------------
  26.4049450290190157

I have two questions:

1) Is there a known workaround for this problem (besides unatural 
partitioning of the inner table)?

2) Would it be possible to add cross-table statistics to fix this? Has 
this been discussed?


Here is the script to create and populate the two tables:

  SELECT 80000 AS nbp \gset

DROP TABLE IF EXISTS orders;
DROP TABLE IF EXISTS products;

CREATE UNLOGGED TABLE products(
         id bigint PRIMARY KEY,
         name TEXT,
         price INT
);

CREATE UNLOGGED TABLE orders(
         id bigint generated always as identity,
         product_id BIGINT, -- REFERENCES products(id),
         quantity INT
);

INSERT INTO products (id, name, price)
   SELECT
     i,
     CASE WHEN i % 1000 = 0 THEN 'babar' ELSE md5(i::text) END,
     random() * 1000
   FROM generate_series(1, :nbp) AS T(i);

INSERT INTO orders (product_id, quantity)
   SELECT product_id, quantity FROM (
     SELECT
       id AS product_id,
       random() * 10 AS quantity,
       name
     FROM products,
     LATERAL (SELECT * FROM generate_series (1, CASE WHEN name = 'babar' 
THEN 4000 ELSE 10 END)) T) U;

CREATE INDEX ON orders (product_id);
VACUUM ANALYZE products, orders;

ALTER TABLE orders ADD FOREIGN KEY (product_id) REFERENCES products(id);

CREATE INDEX ON products (name);