PostgreSQL query performance issue

Question

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!

Answer 1

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.

Answer 2

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

Answer 3

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