How to speed up ORDER BY sorting when using GIN index in PostgreSQL?

Question

I have a table like this:

CREATE TABLE products (
  id serial PRIMARY KEY, 
  category_ids integer[],
  published boolean NOT NULL,
  score integer NOT NULL,
  title varchar NOT NULL);

A product can belong to multiple categories. category_ids column holds a list of ids of all product's categories.

Typical query looks like this (always searching for single category):

SELECT * FROM products WHERE published
  AND category_ids @> ARRAY[23465]
ORDER BY score DESC, title
LIMIT 20 OFFSET 8000;

To speed it up I use the following index:

CREATE INDEX idx_test1 ON products
  USING GIN (category_ids gin__int_ops) WHERE published;

This one helps a lot unless there are too many products in one category. It quickly filters out products that belong to that category but then there is a sort operation that has to be done the hard way (without index).

A have installed btree_gin extension allowing me to build multi-column GIN index like this:

CREATE INDEX idx_test2 ON products USING GIN (
  category_ids gin__int_ops, score, title) WHERE published;

But Postgres does not want to use that for sorting. Even when I remove DESC specifier in the query.

Any alternative approaches to optimize the task are very welcome.

---

Additional information:

• PostgreSQL 9.4, with intarray extension
• total number of products currently is 260k but expected to grow significantly (upto 10M, this is multi-tenant e-commerce platform)
• products per category 1..10000 (can grow up to 100k), average is below 100 but those categories with large number of products tend to attract many more requests

The following query plan was obtained from smaller test system (4680 products in selected category, 200k products total in the table):

Limit  (cost=948.99..948.99 rows=1 width=72) (actual time=82.330..82.341 rows=20 loops=1)
  ->  Sort  (cost=948.37..948.99 rows=245 width=72) (actual time=80.231..81.337 rows=4020 loops=1)
        Sort Key: score, title
        Sort Method: quicksort  Memory: 928kB
        ->  Bitmap Heap Scan on products  (cost=13.90..938.65 rows=245 width=72) (actual time=1.919..16.044 rows=4680 loops=1)
              Recheck Cond: ((category_ids @> '{292844}'::integer[]) AND published)
              Heap Blocks: exact=3441
              ->  Bitmap Index Scan on idx_test2  (cost=0.00..13.84 rows=245 width=0) (actual time=1.185..1.185 rows=4680 loops=1)
                    Index Cond: (category_ids @> '{292844}'::integer[])
Planning time: 0.202 ms
Execution time: 82.404 ms

Note #1: 82 ms might not look that scary but that is because sort buffer fits into memory. Once I select all columns from products table (SELECT * FROM ... and in real life there are about 60 columns) it goes to Sort Method: external merge Disk: 5696kB doubling execution time. And that is only for 4680 products.

Action point #1 (comes from Note #1): In order to reduce memory footprint of sort operation and therefore speed it up a little it would be wise to fetch, sort and limit product ids first, then fetch full records:

SELECT * FROM products WHERE id IN (
  SELECT id FROM products WHERE published AND category_ids @> ARRAY[23465]
  ORDER BY score DESC, title LIMIT 20 OFFSET 8000
) ORDER BY score DESC, title;

This brings us back to Sort Method: quicksort Memory: 903kB and ~80 ms for 4680 products. Still can be slow when number of products grows to 100k.

Answer 1

I've done a lot of experimenting and here are my findings.

GIN and sorting

GIN index currently (as of version 9.4) can not assist ordering.

Of the index types currently supported by PostgreSQL, only B-tree can produce sorted output — the other index types return matching rows in an unspecified, implementation-dependent order.

work_mem

Thanks Chris for pointing out to this configuration parameter. It defaults to 4MB, and in case your recordset is larger, increasing work_mem to proper value (can be found from EXPLAIN ANALYSE) can significantly speed up sort operations.

ALTER SYSTEM SET work_mem TO '32MB';

Restart the server for change to take effect, then double check:

SHOW work_mem;

Original query

I've populated my database with 650k products with some categories holding up to 40k products. I've simplified query a bit by removing published clause:

SELECT * FROM products WHERE category_ids @> ARRAY [248688]
ORDER BY score DESC, title LIMIT 10 OFFSET 30000;

Limit  (cost=2435.62..2435.62 rows=1 width=1390) (actual time=1141.254..1141.256 rows=10 loops=1)
  ->  Sort  (cost=2434.00..2435.62 rows=646 width=1390) (actual time=1115.706..1140.513 rows=30010 loops=1)
        Sort Key: score, title
        Sort Method: external merge  Disk: 29656kB
        ->  Bitmap Heap Scan on products  (cost=17.01..2403.85 rows=646 width=1390) (actual time=11.831..25.646 rows=41666 loops=1)
              Recheck Cond: (category_ids @> '{248688}'::integer[])
              Heap Blocks: exact=6471
              ->  Bitmap Index Scan on idx_products_category_ids_gin  (cost=0.00..16.85 rows=646 width=0) (actual time=10.140..10.140 rows=41666 loops=1)
                    Index Cond: (category_ids @> '{248688}'::integer[])
Planning time: 0.288 ms
Execution time: 1146.322 ms

As we can see work_mem was not enough so we had Sort Method: external merge Disk: 29656kB (the number here is approximate, it needs slightly more than 32MB for in-memory quicksort).

Reduce memory footprint

Don't select full records for sorting, use ids, apply sort, offset and limit, then load just 10 records we need:

SELECT * FROM products WHERE id in (
  SELECT id FROM products WHERE category_ids @> ARRAY[248688]
  ORDER BY score DESC, title LIMIT 10 OFFSET 30000
) ORDER BY score DESC, title;

Sort  (cost=2444.10..2444.11 rows=1 width=1390) (actual time=707.861..707.862 rows=10 loops=1)
  Sort Key: products.score, products.title
  Sort Method: quicksort  Memory: 35kB
  ->  Nested Loop  (cost=2436.05..2444.09 rows=1 width=1390) (actual time=707.764..707.803 rows=10 loops=1)
        ->  HashAggregate  (cost=2435.63..2435.64 rows=1 width=4) (actual time=707.744..707.746 rows=10 loops=1)
              Group Key: products_1.id
              ->  Limit  (cost=2435.62..2435.62 rows=1 width=72) (actual time=707.732..707.734 rows=10 loops=1)
                    ->  Sort  (cost=2434.00..2435.62 rows=646 width=72) (actual time=704.163..706.955 rows=30010 loops=1)
                          Sort Key: products_1.score, products_1.title
                          Sort Method: quicksort  Memory: 7396kB
                          ->  Bitmap Heap Scan on products products_1  (cost=17.01..2403.85 rows=646 width=72) (actual time=11.587..35.076 rows=41666 loops=1)
                                Recheck Cond: (category_ids @> '{248688}'::integer[])
                                Heap Blocks: exact=6471
                                ->  Bitmap Index Scan on idx_products_category_ids_gin  (cost=0.00..16.85 rows=646 width=0) (actual time=9.883..9.883 rows=41666 loops=1)
                                      Index Cond: (category_ids @> '{248688}'::integer[])
        ->  Index Scan using products_pkey on products  (cost=0.42..8.45 rows=1 width=1390) (actual time=0.004..0.004 rows=1 loops=10)
              Index Cond: (id = products_1.id)
Planning time: 0.682 ms
Execution time: 707.973 ms

Note Sort Method: quicksort Memory: 7396kB. Result is much better.

JOIN and additional B-tree index

As Chris advised I've created additional index:

CREATE INDEX idx_test7 ON products (score DESC, title);

First I tried joining like this:

SELECT * FROM products NATURAL JOIN
  (SELECT id FROM products WHERE category_ids @> ARRAY[248688]
  ORDER BY score DESC, title LIMIT 10 OFFSET 30000) c
ORDER BY score DESC, title;

Query plan differs slightly but result is the same:

Sort  (cost=2444.10..2444.11 rows=1 width=1390) (actual time=700.747..700.747 rows=10 loops=1)
  Sort Key: products.score, products.title
  Sort Method: quicksort  Memory: 35kB
  ->  Nested Loop  (cost=2436.05..2444.09 rows=1 width=1390) (actual time=700.651..700.690 rows=10 loops=1)
        ->  HashAggregate  (cost=2435.63..2435.64 rows=1 width=4) (actual time=700.630..700.630 rows=10 loops=1)
              Group Key: products_1.id
              ->  Limit  (cost=2435.62..2435.62 rows=1 width=72) (actual time=700.619..700.619 rows=10 loops=1)
                    ->  Sort  (cost=2434.00..2435.62 rows=646 width=72) (actual time=697.304..699.868 rows=30010 loops=1)
                          Sort Key: products_1.score, products_1.title
                          Sort Method: quicksort  Memory: 7396kB
                          ->  Bitmap Heap Scan on products products_1  (cost=17.01..2403.85 rows=646 width=72) (actual time=10.796..32.258 rows=41666 loops=1)
                                Recheck Cond: (category_ids @> '{248688}'::integer[])
                                Heap Blocks: exact=6471
                                ->  Bitmap Index Scan on idx_products_category_ids_gin  (cost=0.00..16.85 rows=646 width=0) (actual time=9.234..9.234 rows=41666 loops=1)
                                      Index Cond: (category_ids @> '{248688}'::integer[])
        ->  Index Scan using products_pkey on products  (cost=0.42..8.45 rows=1 width=1390) (actual time=0.004..0.004 rows=1 loops=10)
              Index Cond: (id = products_1.id)
Planning time: 1.015 ms
Execution time: 700.918 ms

Playing with various offsets and product counts I could not make PostgreSQL use additional B-tree index.

So I went classical way and created junction table:

CREATE TABLE prodcats AS SELECT id AS product_id, unnest(category_ids) AS category_id FROM products;
CREATE INDEX idx_prodcats_cat_prod_id ON prodcats (category_id, product_id);

SELECT p.* FROM products p JOIN prodcats c ON (p.id=c.product_id)
WHERE c.category_id=248688
ORDER BY p.score DESC, p.title LIMIT 10 OFFSET 30000;

Limit  (cost=122480.06..122480.09 rows=10 width=1390) (actual time=1290.360..1290.362 rows=10 loops=1)
  ->  Sort  (cost=122405.06..122509.00 rows=41574 width=1390) (actual time=1264.250..1289.575 rows=30010 loops=1)
        Sort Key: p.score, p.title
        Sort Method: external merge  Disk: 29656kB
        ->  Merge Join  (cost=50.46..94061.13 rows=41574 width=1390) (actual time=117.746..182.048 rows=41666 loops=1)
              Merge Cond: (p.id = c.product_id)
              ->  Index Scan using products_pkey on products p  (cost=0.42..90738.43 rows=646067 width=1390) (actual time=0.034..116.313 rows=210283 loops=1)
              ->  Index Only Scan using idx_prodcats_cat_prod_id on prodcats c  (cost=0.43..1187.98 rows=41574 width=4) (actual time=0.022..7.137 rows=41666 loops=1)
                    Index Cond: (category_id = 248688)
                    Heap Fetches: 0
Planning time: 0.873 ms
Execution time: 1294.826 ms

Still not using B-tree index, resultset did not fit work_mem, hence poor results.

But under some circumstances, having large number of products and small offset PostgreSQL now decides to use B-tree index:

SELECT p.* FROM products p JOIN prodcats c ON (p.id=c.product_id)
WHERE c.category_id=248688
ORDER BY p.score DESC, p.title LIMIT 10 OFFSET 300;

Limit  (cost=3986.65..4119.51 rows=10 width=1390) (actual time=264.176..264.574 rows=10 loops=1)
  ->  Nested Loop  (cost=0.98..552334.77 rows=41574 width=1390) (actual time=250.378..264.558 rows=310 loops=1)
        ->  Index Scan using idx_test7 on products p  (cost=0.55..194665.62 rows=646067 width=1390) (actual time=0.030..83.026 rows=108037 loops=1)
        ->  Index Only Scan using idx_prodcats_cat_prod_id on prodcats c  (cost=0.43..0.54 rows=1 width=4) (actual time=0.001..0.001 rows=0 loops=108037)
              Index Cond: ((category_id = 248688) AND (product_id = p.id))
              Heap Fetches: 0
Planning time: 0.585 ms
Execution time: 264.664 ms

This is in fact quite logical as B-tree index here does not produce direct result, it is only used as a guide for sequential scan.

Let's compare with GIN query:

SELECT * FROM products WHERE id in (
  SELECT id FROM products WHERE category_ids @> ARRAY[248688]
  ORDER BY score DESC, title LIMIT 10 OFFSET 300
) ORDER BY score DESC, title;

Sort  (cost=2519.53..2519.55 rows=10 width=1390) (actual time=143.809..143.809 rows=10 loops=1)
  Sort Key: products.score, products.title
  Sort Method: quicksort  Memory: 35kB
  ->  Nested Loop  (cost=2435.14..2519.36 rows=10 width=1390) (actual time=143.693..143.736 rows=10 loops=1)
        ->  HashAggregate  (cost=2434.71..2434.81 rows=10 width=4) (actual time=143.678..143.680 rows=10 loops=1)
              Group Key: products_1.id
              ->  Limit  (cost=2434.56..2434.59 rows=10 width=72) (actual time=143.668..143.670 rows=10 loops=1)
                    ->  Sort  (cost=2433.81..2435.43 rows=646 width=72) (actual time=143.642..143.653 rows=310 loops=1)
                          Sort Key: products_1.score, products_1.title
                          Sort Method: top-N heapsort  Memory: 68kB
                          ->  Bitmap Heap Scan on products products_1  (cost=17.01..2403.85 rows=646 width=72) (actual time=11.625..31.868 rows=41666 loops=1)
                                Recheck Cond: (category_ids @> '{248688}'::integer[])
                                Heap Blocks: exact=6471
                                ->  Bitmap Index Scan on idx_products_category_ids_gin  (cost=0.00..16.85 rows=646 width=0) (actual time=9.916..9.916 rows=41666 loops=1)
                                      Index Cond: (category_ids @> '{248688}'::integer[])
        ->  Index Scan using products_pkey on products  (cost=0.42..8.45 rows=1 width=1390) (actual time=0.004..0.004 rows=1 loops=10)
              Index Cond: (id = products_1.id)
Planning time: 0.630 ms
Execution time: 143.921 ms

GIN's result is much better. I checked with various combinations of number of products and offset, under no circumstances junction table approach was any better.

The power of real index

In order for PostgreSQL to fully utilize index for sorting, all query WHERE parameters as well as ORDER BY parameters must reside in single B-tree index. To do this I have copied sort fields from product to junction table:

CREATE TABLE prodcats AS SELECT id AS product_id, unnest(category_ids) AS category_id, score, title FROM products;
CREATE INDEX idx_prodcats_1 ON prodcats (category_id, score DESC, title, product_id);

SELECT * FROM products WHERE id in (SELECT product_id FROM prodcats WHERE category_id=248688 ORDER BY score DESC, title LIMIT 10 OFFSET 30000) ORDER BY score DESC, title;

Sort  (cost=2149.65..2149.67 rows=10 width=1390) (actual time=7.011..7.011 rows=10 loops=1)
  Sort Key: products.score, products.title
  Sort Method: quicksort  Memory: 35kB
  ->  Nested Loop  (cost=2065.26..2149.48 rows=10 width=1390) (actual time=6.916..6.950 rows=10 loops=1)
        ->  HashAggregate  (cost=2064.83..2064.93 rows=10 width=4) (actual time=6.902..6.904 rows=10 loops=1)
              Group Key: prodcats.product_id
              ->  Limit  (cost=2064.02..2064.71 rows=10 width=74) (actual time=6.893..6.895 rows=10 loops=1)
                    ->  Index Only Scan using idx_prodcats_1 on prodcats  (cost=0.56..2860.10 rows=41574 width=74) (actual time=0.010..6.173 rows=30010 loops=1)
                          Index Cond: (category_id = 248688)
                          Heap Fetches: 0
        ->  Index Scan using products_pkey on products  (cost=0.42..8.45 rows=1 width=1390) (actual time=0.003..0.003 rows=1 loops=10)
              Index Cond: (id = prodcats.product_id)
Planning time: 0.318 ms
Execution time: 7.066 ms

And this is the worst scenario with large number of products in chosen category and large offset. When offset=300 execution time is just 0.5 ms.

Unfortunately maintaining such a junction table requires extra effort. It could be accomplished via indexed materialized views, but that is only useful when your data updates rarely, cause refreshing such materialized view is quite a heavy operation.

So I am staying with GIN index so far, with increased work_mem and reduced memory footprint query.

Answer 2

Here are a few quick tips which can help improve your performance. I'll start with the easiest tip, which is almost effortless on your part, and move on to the more difficult tip after the first.

1. work_mem

So, I see right off-hand that a sort reported in your explain plan Sort Method: external merge Disk: 5696kB is consuming less that 6 MB, but is spilling to disk. You need to increase your work_mem setting in your postgresql.conf file to be great enough that the sort can fit into memory.

EDIT: Additionally, on further inspection, I see that after using the index to check for catgory_ids which fit your criteria, the bitmap index scan is forced to become "lossy" and has to recheck the condition when reading the rows from within the relevant heap pages. Refer to this post on postgresql.org for an explanation better than I have given. :P The main point is that your work_mem is way too low. If you haven't tuned the default settings on your server, it isn't going to perform well.

This fix will take you essentially no time to do. One change to postgresql.conf, and you're off! Refer to this performance tuning page for more tips.

2. Schema change

So, you've made the decision in your schema design to denormalize the category_ids into an integer array, which then forces you to use a GIN or GIST index to gain fast access. In my experience, your choice of a GIN index will be faster for reads than a GIST, so in that case you made the right choice. However, GIN is an unsorted index; think of it more like a key-value, where equality predicates are easy to check, but operations such as WHERE >, WHERE <, or ORDER BY are not facilitated by the index.

A decent approach would be to normalize your design by using a bridge table/junction table, used to specify many-to-many relationships in databases.

In this case, you have many categories and a set of corresponding integer category_ids, and you have many products and their corresponding product_ids. Instead of a column in your product table which is an integer array of category_ids, remove this array column from your schema, and create a table as

CREATE TABLE join_products_categories (product_id int, category_id int);

Then, you can generate B-tree indices on the two columns of the bridge table,

CREATE INDEX idx_products_in_join_table ON join_products_categories (product_id);
CREATE INDEX idx_products_in_join_table ON join_products_categories (category_id);

Just my humble opinion, but these changes may make a big difference for you. Try out that work_mem change first thing, at the very least.

Best of luck!

EDIT:

Build an additional index to assist sorting

So, if over time your product line expands, certain queries may return many results (thousands, tens of thousands?) but which may still only be a small subset of your total product line. In these cases, sorting may even be quite expensive if done in memory, but an appropriately designed index may be used to assist the sort.

See the official PostgreSQL documentation describing Indexes and ORDER BY.

If you create an index matching your ORDER BY reqirements

CREATE INDEX idx_product_sort ON products (score DESC, title);

then Postgres will optimize and decide if using the index or performing an explicit sort will be more cost effective. Keep in mind that there is no guarantee that Postgres will use the index; it will seek to optimize performance and choose between using the index or explicitly sorting. If you create this index, monitor it to see if it is being used enough to justify its creation, and drop it if most of your sorts are being done explicitly.

Still, at this point, your 'biggest bang for the buck' imporvement will probably be using more work_mem, but there are cases where the index could support sorting.