2

I'm currently using Postgres 12. A few years ago, I set up the following model: a lot table with a one-to-many relationship to a line table. My idea was to mutualize data that are common for multiple rows of the line table, into the lot table.
The lot table contains metadata stored as in a JSONB column, it felt right at the time not to duplicate the data, since a lot could contain 1 to 10 lines.

Users can ask for lines through an API in a paginated manner, using seek pagination on a sort_index column in the line table. Users can also filter on multiple columns. I'm currently having issues to scale. I have ~40M rows in the line table for ~8M rows in the lot table.

Here is a simplified view of the model:

\d+ public.lot
                                                   Table "public.lot"
     Column      |           Type           | Collation | Nullable | Default | Storage  | Stats target | Description
-----------------+--------------------------+-----------+----------+---------+----------+--------------+-------------
 id              | uuid                     |           | not null |         | plain    |              |
 metadata        | jsonb                    |           | not null |         | extended |              |
 discriminant_id | bigint                   |           | not null |         | plain    |              |
 date_created    | timestamp with time zone |           | not null |         | plain    |              |
 last_updated    | timestamp with time zone |           | not null |         | plain    |              |
Indexes:
    "lot_pkey" PRIMARY KEY, btree (id)
    "idx_lot_discriminant_id" btree (discriminant_id)
Foreign-key constraints:
    "fk_lot_discriminant" FOREIGN KEY (discriminant_id) REFERENCES public.discriminant(id)
Referenced by:
    TABLE "public.line" CONSTRAINT "fk_line_lot" FOREIGN KEY (lot_id) REFERENCES public.lot(id)
Access method: heap
Options: autovacuum_enabled=true, toast.autovacuum_enabled=true
\d+ public.line
                                       Table "public.line"
   Column   |  Type  | Collation | Nullable | Default | Storage  | Stats target | Description
------------+--------+-----------+----------+---------+----------+--------------+-------------
 id         | uuid   |           | not null |         | plain    |              |
 type       | text   |           | not null |         | extended |              |
 sort_index | bigint |           | not null |         | plain    |              |
 lot_id     | uuid   |           | not null |         | plain    |              |
Indexes:
    "line_pkey" PRIMARY KEY, btree (id)
    "idx_line_lot" btree (lot_id)
    "idx_line_sort_index" btree (sort_index)
    "idx_line_type" btree (type)
Foreign-key constraints:
    "fk_line_lot" FOREIGN KEY (lot_id) REFERENCES public.lot(id)
Access method: heap

and a simplified query that I've problem with:

EXPLAIN ANALYZE
SELECT *
FROM public.lot lot
         JOIN public.line line ON lot.id = line.lot_id
WHERE lot.discriminant_id = $discriminant_id
ORDER BY line.sort_index DESC
LIMIT 10;

From what I understand of how the planer should behave, it should choose between:

  • Plan 1: Scanning the index idx_line_sort_index to retrieve lines sorted correctly, then filter rows on the condition discriminant_id = $discriminant_id
  • Plan 2: Scanning the index idx_lot_discriminant_id to filter on lots with a discriminant_id = $discriminant_id, then sort the matching lines

From what I know, the planner should choose between the two plans based on statistics:

  • Plan 1 will be chosen for slightly selective $discriminant_id values, since it's better to sort first, then filter.
  • Plan 2 will be chosen for highly selective $discriminant_id values, since it's better to filter, then sort.

However, I got always the same plan: For $discriminant_id=2003, a filter not selective matching ~30% of the total lot table:

                                                                           QUERY PLAN
----------------------------------------------------------------------------------------------------------------------------------------------------------------
 Limit  (cost=1.00..19.96 rows=10 width=923) (actual time=189.045..189.397 rows=10 loops=1)
   ->  Nested Loop  (cost=1.00..25037693.73 rows=13206387 width=923) (actual time=189.042..189.393 rows=10 loops=1)
         ->  Index Scan Backward using idx_line_sort_index on line  (cost=0.56..2881081.84 rows=40287948 width=56) (actual time=0.139..8.513 rows=2500 loops=1)
         ->  Index Scan using lot_pkey on lot  (cost=0.43..0.55 rows=1 width=859) (actual time=0.072..0.072 rows=0 loops=2500)
               Index Cond: (id = line.lot_id)
               Filter: (discriminant_id = 2003)
               Rows Removed by Filter: 1
 Planning Time: 8.149 ms
 Execution Time: 189.787 ms
(9 rows)

For $discriminant_id=2173, a filter very selective matching only a few rows in the lot table, I have the same plan, and very bad performances:

                                                                                      QUERY PLAN
---------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------
 Limit  (cost=1001.02..31878.16 rows=10 width=923) (actual time=178184.893..178185.317 rows=10 loops=1)
   ->  Gather Merge  (cost=1001.02..11879434.51 rows=3847 width=923) (actual time=178184.890..178185.312 rows=10 loops=1)
         Workers Planned: 2
         Workers Launched: 2
         ->  Nested Loop  (cost=1.00..11877990.44 rows=1603 width=923) (actual time=73048.846..73050.343 rows=7 loops=3)
               ->  Parallel Index Scan Backward using idx_line_sort_index on line  (cost=0.56..2646068.81 rows=16786645 width=56) (actual time=0.121..26016.348 rows=13428898 loops=3)
               ->  Index Scan using lot_pkey on lot  (cost=0.43..0.55 rows=1 width=859) (actual time=0.003..0.003 rows=0 loops=40286694)
                     Index Cond: (id = line.lot_id)
                     Filter: (discriminant_id = 2173)
                     Rows Removed by Filter: 1
 Planning Time: 0.904 ms
 Execution Time: 178185.392 ms
(12 rows) 

At first, I thought it was a statistic problem, so I check the pg_stats table:

SELECT *
FROM pg_stats
WHERE tablename = 'lot' AND attname = 'discriminant_id';
-[ RECORD 1 ]----------+-----------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------
schemaname             | pub
tablename              | lot
attname                | discriminant_id
inherited              | f
null_frac              | 0
avg_width              | 8
n_distinct             | 204
most_common_vals       | {2003,2349,2063,2199,2256,2002,2104,2215,2060,2042,2113,2004,2066,2101,2006,2049,2058,2156,2177,2007,2052,2043,2046,2064,2100,2050,2367,2165,2055,2164,2213,2216,2260,2200,2154,2190,2191,2158,2044,2001,2179,2201,2189,2105,2174,2187,2205,2161,2162,2309,2196,2108,2183,2312,2188,2194,2182,2197,2198,2008,2263,2181,2267,2048,2195,2062,2379,2180,2059,2112,2163,2171,2271,2106,2057,2206,2348,2381,2061,2120,2212,2005,2053,2259,2274,2115,2313,2121,2193,2251,2264,2099,2184,2262,2398,2419,2207,2409,2413,2422}
most_common_freqs      | {0.3278,0.1092,0.029466666,0.029466666,0.0294,0.0278,0.026333334,0.026333334,0.0224,0.020533333,0.0203,0.0194,0.018033333,0.0156,0.014733333,0.010433333,0.0093,0.0091,0.0091,0.008466667,0.0079666665,0.0073,0.0069333334,0.0068,0.0067,0.0064333333,0.0064333333,0.006366667,0.0062666666,0.005866667,0.0058,0.005433333,0.0047,0.0046666665,0.0046,0.0042333333,0.0042333333,0.0040666666,0.0039333333,0.0039,0.0037333334,0.0037,0.0032666668,0.0032,0.0031666667,0.0028,0.0028,0.0027,0.0026666666,0.0026333334,0.0024,0.0023333333,0.0022666666,0.0022666666,0.0021666666,0.0021,0.0020333333,0.0019666667,0.0019666667,0.0019,0.0019,0.0018,0.0018,0.0017,0.0017,0.0016,0.0016,0.0015333333,0.0014666667,0.0014333334,0.0014,0.0013666666,0.0013333333,0.0013,0.0012666667,0.0012666667,0.0012333334,0.0012,0.0010333334,0.00093333336,0.00093333336,0.0009,0.0009,0.00086666667,0.0008,0.00073333335,0.00073333335,0.0007,0.0007,0.0007,0.0007,0.0006,0.0006,0.00056666665,0.00053333334,0.0005,0.00046666668,0.00046666668,0.00046666668,0.00043333333}
histogram_bounds       | {2041,2047,2047,2054,2056,2056,2065,2065,2103,2103,2109,2109,2109,2114,2117,2119,2160,2160,2160,2168,2170,2175,2178,2178,2202,2202,2202,2203,2204,2211,2211,2250,2250,2252,2252,2253,2254,2254,2254,2255,2258,2258,2266,2266,2266,2268,2268,2269,2272,2273,2273,2359,2362,2362,2363,2366,2370,2370,2377,2378,2380,2383,2390,2390,2392,2397,2400,2402,2405,2426}
correlation            | 0.17503545
most_common_elems      |
most_common_elem_freqs |
elem_count_histogram   |

Everything looks fine to me, but I could not understand the plan chosen by the planer. So I tried to bump stats sampling for the column discriminant_id:

ALTER TABLE public.lot ALTER COLUMN discriminant_id SET STATISTICS 500;
ANALYZE public.lot;

I got more sampling in the pg_stats table:

-[ RECORD 1 ]----------+-------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------
schemaname             | pub
tablename              | lot
attname                | discriminant_id
inherited              | f
null_frac              | 0
avg_width              | 8
n_distinct             | 204
most_common_vals       | {2003,2349,2256,2002,2199,2063,2104,2215,2060,2042,2113,2004,2066,2101,2006,2049,2058,2177,2007,2156,2052,2046,2064,2043,2050,2055,2100,2213,2367,2260,2165,2191,2154,2200,2164,2216,2190,2158,2179,2044,2001,2105,2205,2201,2189,2174,2161,2162,2187,2188,2196,2267,2309,2183,2194,2312,2263,2198,2181,2182,2163,2197,2379,2108,2057,2195,2106,2381,2062,2048,2059,2112,2348,2271,2180,2274,2008,2120,2005,2171,2061,2212,2206,2259,2313,2053,2121,2115,2099,2054,2184,2193,2251,2419,2264,2258,2422,2262,2254,2160,2398,2397,2409,2103,2065,2250,2252,2413,2362,2366,2268,2056,2380,2202,2109,2170,2204,2370,2207,2047,2114,2266,2211,2178,2390,2116,2118,2377,2272,2363,2217,2175,2176,2255,2400,2408,2378,2394,2405,2373,2384,2402,2155,2392,2117,2385,2275}
most_common_freqs      | {0.32298,0.108333334,0.029793333,0.029746667,0.0289,0.02848,0.02712,0.02536,0.02328,0.020573333,0.02038,0.019706666,0.018566666,0.01624,0.015613333,0.011046667,0.00908,0.009073333,0.008833333,0.008486667,0.007833334,0.0072333333,0.00708,0.00702,0.006853333,0.006726667,0.0063866666,0.0062066666,0.0061533335,0.0057666665,0.00576,0.004833333,0.0047533335,0.0047533335,0.0046066665,0.004526667,0.0042933333,0.00394,0.0038466668,0.0038066667,0.00356,0.0034933332,0.00344,0.00336,0.0031733334,0.00304,0.00276,0.00276,0.00276,0.0026333334,0.0025066666,0.0024533332,0.0022866668,0.00224,0.0021333334,0.0020933333,0.0020333333,0.0019933332,0.0019066667,0.00188,0.0018666667,0.0018133334,0.00178,0.0017533334,0.0017266667,0.0016066667,0.00158,0.0015333333,0.0015266667,0.0014866666,0.0014866666,0.0014333334,0.0013333333,0.00132,0.00124,0.00124,0.0011133334,0.0010666667,0.0010533333,0.0010533333,0.00098,0.00098,0.0009733333,0.00088,0.00086,0.00082666666,0.00077333336,0.00076666666,0.0007533333,0.0006466667,0.00064,0.00060666667,0.00056666665,0.00052666664,0.00047333332,0.00046666668,0.00045333334,0.00044,0.00041333333,0.0004,0.0004,0.00038666668,0.00038666668,0.00038,0.00033333333,0.00031333332,0.00031333332,0.00031333332,0.0003,0.0003,0.00029333335,0.00028666668,0.00028,0.00027333334,0.00025333333,0.00025333333,0.00025333333,0.00024,0.00023333334,0.00022,0.00022,0.00022,0.00020666666,0.0002,0.0002,0.00018666667,0.00018666667,0.00018,0.00017333333,0.00017333333,0.00015333333,0.00013333333,0.00012666667,0.00012666667,0.00012,0.000113333335,0.00010666667,0.00010666667,0.00010666667,0.0001,0.0001,0.0001,9.3333336e-05,9.3333336e-05,8.666667e-05,8.666667e-05,8e-05}
histogram_bounds       | {2041,2051,2051,2119,2157,2167,2168,2168,2169,2192,2208,2253,2253,2269,2270,2273,2273,2310,2311,2314,2357,2358,2359,2359,2361,2361,2361,2364,2365,2369,2369,2371,2383,2395,2395,2399,2401,2401,2407,2415,2418,2426,2432,2432}
correlation            | 0.17252338
most_common_elems      |
most_common_elem_freqs |
elem_count_histogram   |

Still, the value 2173 is still not in the common_vals array. At this point, I wouldn't be surprised to see the same execution plan.

However, for $discriminant_id=2173, and after the stats inflation, my query planned changed for the best:

                                                                     QUERY PLAN
-----------------------------------------------------------------------------------------------------------------------------------------------------
 Limit  (cost=26989.83..26989.86 rows=10 width=923) (actual time=21.925..21.930 rows=10 loops=1)
   ->  Sort  (cost=26989.83..26992.10 rows=908 width=923) (actual time=21.920..21.922 rows=10 loops=1)
         Sort Key: line.sort_index DESC
         Sort Method: quicksort  Memory: 65kB
         ->  Nested Loop  (cost=1.00..26970.21 rows=908 width=923) (actual time=13.881..21.228 rows=20 loops=1)
               ->  Index Scan using idx_lot_discriminant_id on lot  (cost=0.43..718.59 rows=183 width=859) (actual time=9.429..9.688 rows=4 loops=1)
                     Index Cond: (discriminant_id = 2173)
               ->  Index Scan using idx_line_lot on line  (cost=0.56..143.10 rows=35 width=56) (actual time=2.159..2.865 rows=5 loops=4)
                     Index Cond: (lot_id = lot.id)
 Planning Time: 3.137 ms
 Execution Time: 22.082 ms
(11 rows)

For $discriminant_id=2003, after the stats inflation, the planer still choose to pass through the idx_line_sort_index (which is indeed the most accurate plan):

                                                                           QUERY PLAN
----------------------------------------------------------------------------------------------------------------------------------------------------------------
 Limit  (cost=1.00..20.24 rows=10 width=923) (actual time=20.670..20.711 rows=10 loops=1)
   ->  Nested Loop  (cost=1.00..25037693.73 rows=13012200 width=923) (actual time=20.665..20.704 rows=10 loops=1)
         ->  Index Scan Backward using idx_line_sort_index on line  (cost=0.56..2881081.84 rows=40287948 width=56) (actual time=0.039..3.832 rows=2500 loops=1)
         ->  Index Scan using lot_pkey on lot  (cost=0.43..0.55 rows=1 width=859) (actual time=0.006..0.006 rows=0 loops=2500)
               Index Cond: (id = line.lot_id)
               Filter: (discriminant_id = 2003)
               Rows Removed by Filter: 1
 Planning Time: 0.888 ms
 Execution Time: 20.807 ms
(9 rows)

I don't why, but it seems that altering the stats sampling helps the planer to choose the plans I was waiting for, according to the selectivity of the discriminant_id column. Even if the pg_stats did not really change for the specific values 2003, and 2173.

I ran some tests, and it seems my problems did not end here: For $discriminant_id=2191, matching ~0.5% of the lot table, before the stat inflation:

                                                                               QUERY PLAN
------------------------------------------------------------------------------------------------------------------------------------------------------------------------
 Limit  (cost=1.00..1060.32 rows=10 width=921) (actual time=7011.736..42354.274 rows=10 loops=1)
   ->  Nested Loop  (cost=1.00..25037693.73 rows=236355 width=921) (actual time=7011.720..42354.255 rows=10 loops=1)
         ->  Index Scan Backward using idx_line_sort_index on line  (cost=0.56..2881081.84 rows=40287948 width=56) (actual time=0.273..16201.866 rows=10036046 loops=1)
         ->  Index Scan using lot_pkey on lot  (cost=0.43..0.55 rows=1 width=857) (actual time=0.002..0.002 rows=0 loops=10036046)
               Index Cond: (id = line.lot_id)
               Filter: (discriminant_id = 2191)
               Rows Removed by Filter: 1
 Planning Time: 12.324 ms
 Execution Time: 42354.448 ms
(9 rows)

After the stats inflation:

                                                                               QUERY PLAN
------------------------------------------------------------------------------------------------------------------------------------------------------------------------
 Limit  (cost=1.00..1392.35 rows=10 width=924) (actual time=5870.174..40331.055 rows=10 loops=1)
   ->  Nested Loop  (cost=1.00..25037693.73 rows=179952 width=924) (actual time=5870.166..40331.044 rows=10 loops=1)
         ->  Index Scan Backward using idx_line_sort_index on line  (cost=0.56..2881081.84 rows=40287948 width=56) (actual time=0.583..15596.227 rows=10036046 loops=1)
         ->  Index Scan using lot_pkey on lot  (cost=0.43..0.55 rows=1 width=860) (actual time=0.002..0.002 rows=0 loops=10036046)
               Index Cond: (id = line.lot_id)
               Filter: (discriminant_id = 2191)
               Rows Removed by Filter: 1
 Planning Time: 3.152 ms
 Execution Time: 40331.218 ms
(9 rows)

The plans are slightly different, but the idea is the same: the query seems too slow to me. Bumping the stats to the maximum (10000) does not solve this issue, the query is still slow.

From what I guess, the planer thinks it will be faster to scan the sort_index then filter, because it thinks that the values to return will be very "contiguous" on the index, and underestimates the filter to do on the discriminant.

SELECT line.sort_index FROM public.line line
JOIN public.lot lot ON line.lot_id = lot.id
WHERE lot.discriminant_id = 2191
ORDER BY line.sort_index DESC
LIMIT 10;
sort_index
------------
39224084
39224083
39224082
39224081
39223063
30288652 <---- 8934411 lines between this one and the previous, due to the filtering.
30288651
30288650
30288649
30288609
(10 rows)

We indeed see that there is a huge gap between the same query depending on the number of rows returned: In the case of limiting the rows to 5, the scanning of the idx_line_sort_index estimates 1M rows to scan

EXPLAIN ANALYSE
SELECT * FROM public.line line
JOIN public.lot lot ON line.lot_id = lot.id
WHERE lot.discriminant_id = 2191
ORDER BY line.sort_index DESC
LIMIT 5;
                                                                              QUERY PLAN
----------------------------------------------------------------------------------------------------------------------------------------------------------------------
 Limit  (cost=1.00..696.67 rows=5 width=924) (actual time=3506.308..3512.160 rows=5 loops=1)
   ->  Nested Loop  (cost=1.00..25037693.73 rows=179952 width=924) (actual time=3506.306..3512.158 rows=5 loops=1)
         ->  Index Scan Backward using idx_line_sort_index on line  (cost=0.56..2881081.84 rows=40287948 width=56) (actual time=0.159..1212.901 rows=1012824 loops=1)
         ->  Index Scan using lot_pkey on lot  (cost=0.43..0.55 rows=1 width=860) (actual time=0.002..0.002 rows=0 loops=1012824)
               Index Cond: (id = line.lot_id)
               Filter: (discriminant_id = 2191)
               Rows Removed by Filter: 1
 Planning Time: 1.565 ms
 Execution Time: 3512.199 ms
(9 rows)

In the case of limiting the rows to 6, the scanning of the idx_line_sort_index estimates 10M (x10) rows to scan

EXPLAIN ANALYSE
SELECT * FROM public.line line
JOIN public.lot lot ON line.lot_id = lot.id
WHERE lot.discriminant_id = 2191
ORDER BY line.sort_index DESC
LIMIT 6;
                                                                               QUERY PLAN
------------------------------------------------------------------------------------------------------------------------------------------------------------------------
 Limit  (cost=1.00..835.81 rows=6 width=924) (actual time=3539.010..38743.824 rows=6 loops=1)
   ->  Nested Loop  (cost=1.00..25037693.73 rows=179952 width=924) (actual time=3539.008..38743.818 rows=6 loops=1)
         ->  Index Scan Backward using idx_line_sort_index on line  (cost=0.56..2881081.84 rows=40287948 width=56) (actual time=0.107..14643.842 rows=10036002 loops=1)
         ->  Index Scan using lot_pkey on lot  (cost=0.43..0.55 rows=1 width=860) (actual time=0.002..0.002 rows=0 loops=10036002)
               Index Cond: (id = line.lot_id)
               Filter: (discriminant_id = 2191)
               Rows Removed by Filter: 1
 Planning Time: 1.077 ms
 Execution Time: 38744.039 ms
(9 rows)

Questions:

Question 1: It seems that boosting the stats cannot solve the issue for every discriminant_value. But I don't understand why it did help the planer to choose the correct query plan in some cases, for some discriminant values. Can someone explain this behaviour?

Question 2: is there a way for me to make the planer not underestimate the discriminant filter? Is there a way to boost the usage of the idx_lot_discriminant_id instead of the idx_line_sort_index when it should?

Question 3: is my model scalable ? My intuition tells me I did a bad move by splitting the model in two tables, and that I should denormalize the column discriminant_id in the table lines to create an index (discriminant_id, sort_index). But I have more filters possibles in the lot table, so it means denormalize almost everything that is index in the line table... The other thoughts I had:

  • Using a CTE (or a subquery) to filter on the lot first, but since the filters are controlled by the user API, it's not efficient when the user is filtering by nothing. There is filters possible on the line table, which makes the pagination hard to do with the CTE.
  • Using a materialized view: Since I want real time, I would use too much resource on refreshing the view.
  • Switch my data store to something more appropriate to my usage (Cassandra?, Mongo?).

I'm a bit surprised Postgres cannot handle this use case, and I have the feeling that I am missing something important here.

What are you thoughts?

0

Your Answer

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