1

We are sometimes getting poor performance (~14s) when using the following query (PostgreSQL 9.6) to fetch rows from the table items whose ID is present in the table items_categories:

SELECT items.*
FROM items 
WHERE EXISTS (
    SELECT item_id 
    FROM items_categories 
    WHERE item_id = items.id  AND category_id = 626 
) 
AND items.active = TRUE
-- possibly some others "AND" here to use more filters on "items", but not considered for this question
ORDER BY modified_at DESC 
LIMIT 10

Relevant parts of our schema:

                              Table "public.items"
           Column      |       Type        |                     Modifiers
-----------------------+-------------------+----------------------------------------------------
 id                    | integer           | not null default nextval('items_id_seq'::regclass)
 active                | boolean           | default true
 modified_at           | timestamp without time zone | default now()
Indexes:
    "items_pkey" PRIMARY KEY, btree (id)
    "active_idx" btree (active)
    "aggregate_idx" btree (id)
    "items_modified_at_idx" btree (modified_at)


  Table "public.items_categories"
   Column    |  Type   | Modifiers
-------------+---------+-----------
 item_id     | integer | not null
 category_id | integer | not null
Indexes:
    "unique_cat_item_assoc" UNIQUE CONSTRAINT, btree (item_id, category_id)
    "items_categories_1_idx" btree (category_id)
    "items_categories_2_idx" btree (item_id)
Foreign-key constraints:
    "items_categories_category_id_fkey" FOREIGN KEY (category_id) REFERENCES categories(id)
    "items_categories_item_id_fkey" FOREIGN KEY (item_id) REFERENCES items(id)

The table items contains ~2 M rows, and the table items_categories contains ~4 M rows

When we ask for 10 items (i.e. LIMIT 10 at the end of the above query) and 10 or more rows match in items_categories, the performance is good (~10ms), but when we ask for 10 items and less than 10 rows match in items_categories, then the query takes ~14s because it’s doing an index scan on items.modified_at to look at each 2 M rows.

Query plan when less than 10 rows match in items_categories (poor performance):

Limit  (cost=0.86..11696.68 rows=10 width=1797) (actual time=168.376..14484.854 rows=7 loops=1)
  ->  Nested Loop Semi Join  (cost=0.86..2746178.23 rows=2348 width=1797) (actual time=168.376..14484.836 rows=7 loops=1)
        ->  Index Scan Backward using items_modified_at_idx on items  (cost=0.43..1680609.95 rows=2243424 width=1797) (actual time=0.054..7611.300 rows=2251395 loops=1)
              Filter: active
              Rows Removed by Filter: 2467
        ->  Index Only Scan using unique_cat_item_assoc on items_categories  (cost=0.43..0.47 rows=1 width=4) (actual time=0.003..0.003 rows=0 loops=2251395)
              Index Cond: ((item_id = items.id) AND (category_id = 626))
              Heap Fetches: 7
Planning time: 3.082 ms
Execution time: 14485.057 ms

Query plan when more than 10 rows match in items_categories (good performance):

Limit  (cost=0.86..24.07 rows=10 width=1857) (actual time=3.575..3.757 rows=10 loops=1)
  ->  Nested Loop Semi Join  (cost=0.86..2763459.56 rows=1190819 width=1857) (actual time=3.574..3.752 rows=10 loops=1)
        ->  Index Scan Backward using items_modified_at_idx on items  (cost=0.43..1684408.22 rows=2246967 width=1857) (actual time=0.013..2.205 rows=751 loops=1)
              Filter: active
        ->  Index Only Scan using unique_cat_item_assoc on items_categories  (cost=0.43..0.47 rows=1 width=4) (actual time=0.002..0.002 rows=0 loops=751)
              Index Cond: ((item_id = items.id) AND (category_id = 20))
              Heap Fetches: 10
Planning time: 1.650 ms
Execution time: 3.868 ms

How can we tune this query to handle both situations? (i.e. good performances no matter how many rows of items_categories match).

I have a POC working where I first count the number of matching rows in items_categories (separate query) then if the number is low I use a CTE to work on a subset of items instead of all its rows, but it’s really a dirty temporary hack IMO… If the number is high, the CTE takes too long and it's more efficient to NOT use this CTE in this case (i.e. the above query performs better).

Thank you!

8
  • What is your CTE to work on a subset of items? What if you just use that all of the time?
    – jjanes
    Jul 26 '21 at 14:42
  • Thanks @jjanes: I edited the question to mention that we can't always use this CTE because in some cases (subset of items too big) it is not performing well. It only performs better than the shown query when the subset of items is small, e.g. smaller than the requested LIMIT
    – xav
    Jul 26 '21 at 15:31
  • Have you tried adding an index on (category_id, item_id)? Sep 1 '21 at 9:47
  • @ypercubeᵀᴹ yes, it's there already
    – xav
    Sep 1 '21 at 10:59
  • I see a (unique) index on (item_id, category_id) but not on (category_id, item_id). Sep 1 '21 at 13:27
0

The query planner can't get good row estimates to adequately plan this type of query. If you can't tolerate bad plans, you will have to do two queries. There are a variety of ways you could arrange that, and it sounds like you already found one. You could create a set-returning plpgsql function which wraps up both queries into a single function call, if this makes things better for you.

1
  • Thank you. The thing is that this query is built dynamically by our code, based on the request we received (REST API), so the number and types of AND in the WHERE is dynamic. For now yes our best chance is to use 2 queries: one to check the number of matching rows in item_categories, then one to fetch the items using either the query above or another one using a CTE to handle few matches in items_categories :(
    – xav
    Jul 27 '21 at 16:51
0

Can you give this a whirl?

SELECT items.*
FROM items 
WHERE item_id in (
    SELECT item_id 
    FROM items_categories 
    where category_id = 626
    Intersect
    SELECT item_id 
    FROM items
    Where active = TRUE
) 
ORDER BY modified_at DESC 
LIMIT 10
4
  • Thanks, but sadly this takes 10s (so a tiny bit better than 14s but still too much) - the plan shows that the issue is a Seq Scan on items and then the Append. Link to plan
    – xav
    Jul 27 '21 at 11:41
  • Perhaps there are only a few inactive items, in which case you could replace the "intersect" by an "except" and "active = FALSE". Jul 27 '21 at 20:02
  • Thanks, it's a bit better indeed, and yes, most items are active. But it still takes 8s :( New plan
    – xav
    Jul 28 '21 at 11:25
  • Now this one could be quite a bit faster if you had a combined index on active+id, since it would no longer force Postgresql to read the table, the information it needs - id - would be in the index. Jul 28 '21 at 11:49
0

I think you can fix this.

You probably do not need to query ever for items that items.active = false, and every query that you run probably has to check that it's true.

  • drop your items_modified_at_idx

  • drop your active_idx.

  • drop your aggregate_idx (this does nothing anyway except slow down inserts/deletes, it's covering the pkey)

  • run CREATE INDEX ON items (modified_at DESC) WHERE active;

This will eliminate the need for the backwards scan which is taking half your time, and only removing 2467 rows. This will also shrink the size of the index on modified_at and drop one index from needing to be updated on insertion/deletion.

On the other table drop items_categories_2_idx as it will never be used anyway (it's on the left in the compound index).

When you're all done run VACUUM FULL ANALYZE on both tables, and give it a shot.

Other notes

  • Don't ever use timestamp without time zone, it's almost certainly a mistake.
  • WHERE active = true is simply WHERE active
  • upgrade to use identity columns instead of serial.
  • I would personally make unique_cat_item_assoc a primary key. Not a unique constraint. As if you only have one unique constraint on a table, that's always your primary key anyway.

Last resort

As a side note,

->  Index Only Scan using unique_cat_item_assoc on items_categories  (cost=0.43..0.47 rows=1 width=4) (actual time=0.003..0.003 rows=0 loops=2251395)
    Index Cond: ((item_id = items.id) AND (category_id = 626))

Is only returning one row. That means you can just fence it (OFFSET 0) if you absolutely must.

SELECT items.*
FROM items 
WHERE EXISTS (
    SELECT item_id 
    FROM items_categories 
    WHERE item_id = items.id  AND category_id = 626 
    OFFSET 0 -- magic dragon
)
AND items.active = TRUE
-- possibly some others "AND" here to use more filters on "items", but not considered for this question
ORDER BY modified_at DESC 
LIMIT 10
1
  • Thanks. Very, very interesting. I will give this a try and let you know! (not sure when, since we found another solution since then, but our solution was not perfect: use LIMIT to stop when there's no more items, so we need to COUNT them first)
    – xav
    Jan 6 at 11:32

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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