One Weird Trick to Make PostgreSQL 15000x Faster
Genius Engineering Team
A common heuristic for indexing database tables is to index the columns you use for sorting, filtering, joining, or grouping. It’s a bit of a shotgun strategy, but it makes some sense: You look up “database index” on Wikipedia, see the words “improves the speed of data retrieval operations,” and reasonably conclude, “Hmm, speed is good, let's add a bunch of indexes!”

Even some experts endorse this strategy. Craig Kerstiens of Heroku Postgres writes, “guessing whether an index will be helpful can be a bit hard within Postgres. So the easy solution is to add indexes to everything, then just observe if they’re being used.”

One problem with the “index everything” strategy is that indexes can take up lots of disk space, and they also increase the number of writes to the database. But, as we discovered here at Rap Genius, when you have a large-scale app that’s not all that can go wrong. In our case, the consequences of having the wrong index were much more severe.

Here’s a fairly straightforward query:SELECT *
FROM annotations
WHERE
id IN (155223,155217,155252,155234,182883,155245,154824,152721,155203)
OR base_annotation_id IN (155223,155217,155252,155234,182883,155245,154824,152721,155203)
ORDER BY updated_at DESC
LIMIT 1;
This query is trying to find the most recently updated annotation from a list of 9 IDs. (It's slightly more complicated than that, because Rap Genius also has a notion of “base annotations”, so in addition to checking the 9 annotation IDs, we need to check any annotations that have one of those 9 as a base annotation.) The annotations table has millions of records, and many indexes, including single btree indexes on each of id, base_annotation_id, and updated_at. Queries like the one above were very fast for a while, but then one day, for no apparent reason, they became excruciatingly slow. So slow, in fact, that they were bringing down the site.

What was going on? The query doesn't seem all that complicated, and we have indexes on every column in play. Let's take a look at the query plan:QUERY PLAN
-----------------------------------
Limit  (cost=0.00..23986.57 rows=1 width=356)
       (actual time=29545.900..29545.900 rows=1 loops=1)
->  Index Scan Backward using index_annotations_on_updated_at
         on annotations  (cost=0.00..9282803.51 rows=387 width=356)
                         (actual time=29545.897..29545.897 rows=1 loops=1)
Filter: ((id = ANY ('{155223,155217,155252,155234,182883,155245,154824,152721,155203}'::integer[]))
      OR (base_annotation_id = ANY ('{155223,155217,155252,155234,182883,155245,154824,152721,155203}'::integer[])))
Rows Removed by Filter: 423718
Total runtime: 29545.934 ms
(5 rows)
That's odd: why does the query plan use only the index on updated_at, and not the indexes on id and base_annotation_id? In plain language, we're asking the database to find which annotation was updated most recently from a list of 9 candidates, and the database's response is, “Okay, let me get all annotations, order them by updated_at using an index, then go through that whole list of results to find the ones that match your 9 IDs.”

This is hugely inefficient, because there are millions of records in the table. It might be fast to order the whole table by updated_at, which is indexed, but then it's really slow to filter those results by ID, because the database no longer makes use of the id and base_annotation_id indexes once the results have been reordered.

The query would be much faster if we first used the indexes on id and base_annotation_id to find the records that match our WHERE conditions, and then sorted those results in memory. This latter approach would not use the index on updated_at, but that's fine: there aren't that many results from the query—a few dozen at most—so there's no need to use an index to sort.

There are a few ways we could force or “trick” the query planner into using the id and base_annotation_id indexes, but the easiest was to drop the index on updated_at entirely. It turned out this was the only query in the entire app making use of that index, and it was using the index in the worst possible way. Once we killed the index on updated_at, this was the new query plan:QUERY PLAN
-----------------------------------
Limit  (cost=805.83..805.83 rows=1 width=358)
       (actual time=1.631..1.632 rows=1 loops=1)
->  Sort  (cost=805.83..806.02 rows=393 width=358)
          (actual time=1.624..1.624 rows=1 loops=1)
Sort Key: updated_at
Sort Method: top-N heapsort  Memory: 26kB
->  Bitmap Heap Scan on annotations
    (cost=38.94..805.43 rows=393 width=358)
    (actual time=1.032..1.519 rows=9 loops=1)
Recheck Cond: ((id = ANY ('{155223,155217,155252,155234,182883,155245,154824,152721,155203}'::integer[]))
            OR (base_annotation_id = ANY ('{155223,155217,155252,155234,182883,155245,154824,152721,155203}'::integer[])))
->  BitmapOr  (cost=38.94..38.94 rows=393 width=0)
              (actual time=0.950..0.950 rows=0 loops=1)
->  Bitmap Index Scan on annotations_pkey
    (cost=0.00..18.83 rows=9 width=0)
    (actual time=0.625..0.625 rows=9 loops=1)
Index Cond: (id = ANY ('{155223,155217,155252,155234,182883,155245,154824,152721,155203}'::integer[]))
->  Bitmap Index Scan on index_annotations_on_base_annotation_id
    (cost=0.00..20.07 rows=384 width=0)
    (actual time=0.322..0.322 rows=0 loops=1)
Index Cond: (base_annotation_id = ANY ('{155223,155217,155252,155234,182883,155245,154824,152721,155203}'::integer[]))
Total runtime: 1.833 ms
(12 rows)
That's an over 15,000x speed improvement.

The old saw of “index everything you can” just isn’t true, at least not at scale. A single index can wreak tremendous havoc with PostgreSQL's query planner, which we’ve found sometimes operates unpredictably.

To avoid this pitfall, do your own analysis to make sure that your indexes match your usage patterns, and be sure to automatically monitor slow queries, which might crop up at any moment. It could turn out that you have a (very) counterproductive index.

—
Want to help us improve performance as we scale beyond 30m monthly uniques? Rap Genius is hiring for engineering and devops roles.
Write the lyrics for a misc song made in 2014, titled "One Weird Trick to Make PostgreSQL 15000x Faster", by artist "Genius Engineering Team".