postgresqlindexing

Slow query when using LIMIT for pagination

I need some help to optimize my filtering/pagination system under Symfony/PostgreSQL.

I have a table "link" with ~5M rows and this query used for the pagination system with https://github.com/KnpLabs/KnpPaginatorBundle.

SELECT *
FROM   link l0_
WHERE  l0_.team_id = 21
AND    l0_.folder_id IS NULL
AND    l0_.created_at >= '2024-09-01 00:00:00'
AND    l0_.created_at < '2024-09-30 00:00:00'
AND    l0_.origin = 'API'
ORDER  BY l0_.id DESC
LIMIT  10;

This team (21) has ~2M links in this table. You can seen that the request have some filters to try to limit the number of links to show in the pagination.

The problem is that for this particular customer, this query is veryyyyyy long (>20s). While in this case, this query returns 0 result (It's normal, all his links are in folders).

I found that removing the LIMIT 10 instruction "fix" the speed. Here's the explains of both queries:

With LIMIT 10:

Limit  (cost=0.43..397.88 rows=10 width=611) (actual time=22046.648..22046.650 rows=0 loops=1)
  ->  Index Scan Backward using idx_23374_primary on link l0_  (cost=0.43..436955.10 rows=10994 width=611) (actual time=22046.646..22046.647 rows=0 loops=1)
        Filter: ((folder_id IS NULL) AND (created_at >= '2024-09-01 00:00:00+02'::timestamp with time zone) AND (created_at < '2024-09-30 00:00:00+02'::timestamp with time zone) AND (team_id = 21) AND ((origin)::text = 'API'::text))
        Rows Removed by Filter: 5759952
Planning Time: 0.182 ms
Execution Time: 22046.683 ms

Without LIMIT 10:

Sort  (cost=10741.35..10768.83 rows=10993 width=611) (actual time=0.674..0.675 rows=0 loops=1)
  Sort Key: id DESC
  Sort Method: quicksort  Memory: 25kB
  ->  Index Scan using idx_links_without_folder on link l0_  (cost=0.42..10003.48 rows=10993 width=611) (actual time=0.670..0.670 rows=0 loops=1)
        Index Cond: ((team_id = 21) AND (created_at >= '2024-09-01 00:00:00+02'::timestamp with time zone) AND (created_at < '2024-09-30 00:00:00+02'::timestamp with time zone) AND ((origin)::text = 'API'::text))
Planning Time: 0.132 ms
Execution Time: 0.691 ms

Of course I have some indexes to help:

$this->addSql('CREATE INDEX CONCURRENTLY idx_links_with_folder ON link (team_id, folder_id, created_at, origin, id) WHERE folder_id IS NOT NULL');
$this->addSql('CREATE INDEX CONCURRENTLY idx_links_without_folder ON link (team_id, created_at, origin, id) WHERE folder_id IS NULL');

But you can see that idx_links_without_folder is not used in the case of the query with LIMIT. I found that this is something possible with PostgreSQL: https://www.gojek.io/blog/the-case-s-of-postgres-not-using-index (CASE 5)

Result of:

SELECT attname,
       null_frac,
       most_common_vals,
       most_common_freqs,
       histogram_bounds
FROM pg_stats
WHERE tablename = 'link'
  AND attname IN ('team_id', 'folder_id', 'created_at', 'origin');

─[ RECORD 1 ]─────┬───────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────
attname           │ team_id
null_frac         │ 0.1018
most_common_vals  │ {10,21,13,1,2,10190,12,8,67,20,55,18,25}
most_common_freqs │ {0.50306666,0.2831,0.06306667,0.014333333,0.009266667,0.008,0.0017,0.0014666667,0.0014666667,0.00056667,0.00056667,0.0004,0.0004}
histogram_bounds  │ {9,36,54,57,61,61,71,71,71,78,82,89,89,105,125,137,145,148,180,183,184,206,215,256,281,288,295,355,400,424,476,511,548,550,580,603,667,680,705,733,783,805,826,865,935,994,1062,1096,1112,1203,1321,1348,1397,1518,1635,1735,1821,2124,2300,2559,2692,2747,2870,3188,3282,3454,3713,3913,4021,4084,4529,4818,5158,5221,5340,5896,5944,6004,6306,6583,6643,6860,7034,7263,7299,7485,7540,7796,8047,8157,8385,8995,9355,9549,9725,9925,10100,10777,10911,11177,11557}
═[ RECORD 2 ]═════╪═══════════════════════════════════════════════════════════════════════════════════════════════════════════════════════════════════════════════════════════════════════════════════════════════════════════════════════════════════════════════════════════════════════════════════════════════════════════════════════════════════════════════════════════════════════════════════════════════════════════════════════════════════════════════════════════════════════════════════════════════════════════════════════════════════════════════════════════════════════════════════════════════════════════════════════════════════════════════════════════════════════════════════════════════════════════════════════════════════════════════════════════════════════════════════════════════════════════════════════════════════════════════════════════════════════════════════════════════════════════════════════════════════════════════════════════════════════════════════════════════════════════════════════════════════════════════════════════════════════════════════════════════════════════════════════════════════════════════════════════════════════════════════════════════════════════════════════════════════════════════════════════════════════════════════════════════════════════════════════════════════════════════════════════════════════════════════════════════════════════════════════════════════════════════════════════════════════════════════════════════════════════════════════════════════════════════════════════════════════════════════════════════════════════════════════════════════════════════════════════════════════════════════════════════════════════════════════════════════════════════════════════════════════════════════════════════════════════════════════════════════════════════════════════════════════════════════════════════════════════════════════════════════════════════════════════════════════════════════════════════════════════════════════════════════════════════════════════════════════════════════════════════════════════════════════════════════════════════════════════════════════════════════════════════════════════════════════════════════════════════════════════════════════════════════════════════════════════════════════════════════════════════════════════════════════════════════════════════════════════════════════════════════════════════════════════════════════════════════════════════════════════════════════════════════════════════════════════════════════════════════════════════════════════════════════════════
attname           │ created_at
null_frac         │ 0
most_common_vals  │ {"2022-01-31 18:55:47+01"}
most_common_freqs │ {0.0002}
histogram_bounds  │ {"2019-10-31 06:44:19+01","2021-04-12 13:17:50+02","2021-07-07 18:33:12+02","2021-09-16 13:27:28+02","2021-09-26 14:48:00+02","2021-10-29 08:39:41+02","2021-11-29 16:20:19+01","2022-01-05 03:59:17+01","2022-01-21 19:06:34+01","2022-01-23 11:35:08+01","2022-01-23 11:57:47+01","2022-01-24 14:02:13+01","2022-01-25 09:51:01+01","2022-01-31 18:43:49+01","2022-02-01 08:19:52+01","2022-02-09 12:45:36+01","2022-03-01 10:58:07+01","2022-03-22 09:15:57+01","2022-04-10 08:48:39+02","2022-05-02 20:00:11+02","2022-05-22 14:16:55+02","2022-06-08 02:47:53+02","2022-06-22 17:00:27+02","2022-07-07 16:40:21+02","2022-07-25 17:07:25+02","2022-08-15 07:47:09+02","2022-09-03 09:25:57+02","2022-09-24 10:14:19+02","2022-10-13 10:43:59+02","2022-10-28 18:07:55+02","2022-11-14 14:51:57+01","2022-11-28 15:00:32+01","2022-12-14 15:29:14+01","2023-01-02 14:25:19+01","2023-01-15 16:11:27+01","2023-01-28 15:50:44+01","2023-02-10 16:42:09+01","2023-02-28 07:25:58+01","2023-03-13 22:58:09+01","2023-03-24 18:14:48+01","2023-04-11 14:36:44+02","2023-04-23 08:01:28+02","2023-05-07 12:52:49+02","2023-05-23 14:05:44+02","2023-06-07 15:10:22+02","2023-06-19 17:53:22+02","2023-07-04 21:58:35+02","2023-07-17 18:53:43+02","2023-07-30 03:17:37+02","2023-08-14 10:30:26+02","2023-08-30 17:16:39+02","2023-09-13 18:09:36+02","2023-09-27 10:01:08+02","2023-10-10 04:43:44+02","2023-10-23 18:04:42+02","2023-11-06 18:29:52+01","2023-11-20 16:22:52+01","2023-12-01 18:05:15+01","2023-12-13 10:51:49+01","2023-12-27 11:43:18+01","2024-01-11 18:11:15+01","2024-01-23 21:14:56+01","2024-02-02 18:16:39+01","2024-02-13 12:18:02+01","2024-02-26 18:05:34+01","2024-03-09 07:52:09+01","2024-03-22 05:17:58+01","2024-04-06 10:04:25+02","2024-04-16 12:25:41+02","2024-04-26 10:00:06+02","2024-05-03 15:40:21+02","2024-05-10 15:23:40+02","2024-05-17 11:01:21+02","2024-05-23 17:58:04+02","2024-05-29 11:45:00+02","2024-06-03 16:36:45+02","2024-06-08 19:45:01+02","2024-06-13 15:13:23+02","2024-06-19 11:00:08+02","2024-06-24 17:23:47+02","2024-06-29 18:19:56+02","2024-07-05 17:18:53+02","2024-07-10 14:46:22+02","2024-07-12 19:54:01+02","2024-07-17 18:03:52+02","2024-07-22 10:02:26+02","2024-07-24 18:02:06+02","2024-07-29 10:00:56+02","2024-08-03 18:00:44+02","2024-08-09 18:01:49+02","2024-08-14 19:32:17+02","2024-08-20 13:37:08+02","2024-08-25 10:00:22+02","2024-08-30 10:02:48+02","2024-09-04 13:45:01+02","2024-09-08 19:03:23+02","2024-09-12 12:55:17+02","2024-09-16 10:01:49+02","2024-09-19 10:04:14+02","2024-09-23 09:32:21+02","2024-09-26 13:55:10+02"}
═[ RECORD 3 ]═════╪═══════════════════════════════════════════════════════════════════════════════════════════════════════════════════════════════════════════════════════════════════════════════════════════════════════════════════════════════════════════════════════════════════════════════════════════════════════════════════════════════════════════════════════════════════════════════════════════════════════════════════════════════════════════════════════════════════════════════════════════════════════════════════════════════════════════════════════════════════════════════════════════════════════════════════════════════════════════════════════════════════════════════════════════════════════════════════════════════════════════════════════════════════════════════════════════════════════════════════════════════════════════════════════════════════════════════════════════════════════════════════════════════════════════════════════════════════════════════════════════════════════════════════════════════════════════════════════════════════════════════════════════════════════════════════════════════════════════════════════════════════════════════════════════════════════════════════════════════════════════════════════════════════════════════════════════════════════════════════════════════════════════════════════════════════════════════════════════════════════════════════════════════════════════════════════════════════════════════════════════════════════════════════════════════════════════════════════════════════════════════════════════════════════════════════════════════════════════════════════════════════════════════════════════════════════════════════════════════════════════════════════════════════════════════════════════════════════════════════════════════════════════════════════════════════════════════════════════════════════════════════════════════════════════════════════════════════════════════════════════════════════════════════════════════════════════════════════════════════════════════════════════════════════════════════════════════════════════════════════════════════════════════════════════════════════════════════════════════════════════════════════════════════════════════════════════════════════════════════════════════════════════════════════════════════════════════════════════════════════════════════════════════════════════════════════════════════════════════════════════════════════════════════════════════════════════════════════════════════════════════════════════════════════════════════════════════
attname           │ folder_id
null_frac         │ 0.12663333
most_common_vals  │ {58,115,67,66,6,305,68,257,70,76,79,74,69,75,63,77,298,204,73,81,72,80,82,78,44,61,65,86,177,10,329}
most_common_freqs │ {0.50303334,0.2793,0.0223,0.0149,0.008733333,0.005866667,0.0036,0.0032333334,0.0022666666,0.0021666666,0.0021666666,0.0021,0.0018666667,0.0017666667,0.0017,0.0016666667,0.0016,0.0014666667,0.0014333334,0.0014333334,0.0013666666,0.0011333333,0.0011333333,0.0010666667,0.00076667,0.0007,0.0007,0.00056667,0.00056667,0.00053333,0.00053333}
histogram_bounds  │ {55,56,83,97,103,110,110,127,157,167,167,172,180,182,188,190,193,193,193,193,207,213,213,213,251,263,349}
═[ RECORD 4 ]═════╪═══════════════════════════════════════════════════════════════════════════════════════════════════════════════════════════════════════════════════════════════════════════════════════════════════════════════════════════════════════════════════════════════════════════════════════════════════════════════════════════════════════════════════════════════════════════════════════════════════════════════════════════════════════════════════════════════════════════════════════════════════════════════════════════════════════════════════════════════════════════════════════════════════════════════════════════════════════════════════════════════════════════════════════════════════════════════════════════════════════════════════════════════════════════════════════════════════════════════════════════════════════════════════════════════════════════════════════════════════════════════════════════════════════════════════════════════════════════════════════════════════════════════════════════════════════════════════════════════════════════════════════════════════════════════════════════════════════════════════════════════════════════════════════════════════════════════════════════════════════════════════════════════════════════════════════════════════════════════════════════════════════════════════════════════════════════════════════════════════════════════════════════════════════════════════════════════════════════════════════════════════════════════════════════════════════════════════════════════════════════════════════════════════════════════════════════════════════════════════════════════════════════════════════════════════════════════════════════════════════════════════════════════════════════════════════════════════════════════════════════════════════════════════════════════════════════════════════════════════════════════════════════════════════════════════════════════════════════════════════════════════════════════════════════════════════════════════════════════════════════════════════════════════════════════════════════════════════════════════════════════════════════════════════════════════════════════════════════════════════════════════════════════════════════════════════════════════════════════════════════════════════════════════════════════════════════════════════════════════════════════════════════════════════════════════════════════════════════════════════════════════════════════════════════════════════════════════════════════════════════════════════════════════════════════════════════════
attname           │ origin
null_frac         │ 0
most_common_vals  │ {API,WEB_APP,IMPORT,MAKE}
most_common_freqs │ {0.7973,0.112333335,0.070933335,0.019433333}
histogram_bounds  │ ∅

Do you have any advice or hint to help me improve my system? Because the experience for this customer is really horrible and I don't find how to improve things for now.

I'm using PostgreSQL 15.7

Thanks in advance!

Solution

  • I've replaced:

    ORDER  BY l0_.id DESC

    by:

    ORDER  BY l0_.created_at DESC

    and i'm going from:

    Limit  (cost=0.43..387.33 rows=10 width=1189) (actual time=31416.533..31416.534 rows=0 loops=1)
  ->  Index Scan Backward using idx_23374_primary on link l0_  (cost=0.43..443342.59 rows=11459 width=1189) (actual time=31416.531..31416.532 rows=0 loops=1)
        Filter: ((folder_id IS NULL) AND (created_at >= '2024-09-01 00:00:00+02'::timestamp with time zone) AND (created_at < '2024-09-30 00:00:00+02'::timestamp with time zone) AND (team_id = 21) AND ((origin)::text = 'API'::text))
        Rows Removed by Filter: 5768584
Planning Time: 0.178 ms
Execution Time: 31417.573 ms

    to:

    Limit  (cost=0.42..9.37 rows=10 width=1189) (actual time=0.556..0.557 rows=0 loops=1)
  ->  Index Scan Backward using idx_links_without_folder on link l0_  (cost=0.42..10254.47 rows=11459 width=1189) (actual time=0.555..0.555 rows=0 loops=1)
        Index Cond: ((team_id = 21) AND ((origin)::text = 'API'::text) AND (created_at >= '2024-09-01 00:00:00+02'::timestamp with time zone) AND (created_at < '2024-09-30 00:00:00+02'::timestamp with time zone))
Planning Time: 0.221 ms
Execution Time: 0.596 ms

    So... topic fixed! Thank you very much @laurenz-albe for your help.