4

My app is making the following psql query, and it is running extremely slow:

SELECT COUNT(*) 
FROM (
  SELECT 1 AS one 
  FROM "large_table" 
  WHERE "large_table"."user_id" = 123 
  ORDER BY "large_table"."id" desc 
  LIMIT 1 OFFSET 30
) subquery_for_count;

When I change the ORDER BY to ASC, it runs like 100x quicker. I have the default primary key index on id, and I've experimented with adding an additional index for the id in desc order, however it didn't seem to make a difference.

When I run Explain Analyze, I see that it is using an index scan backwards on the slow query (desc). I tried manually disabling index scans for my session, and found that the query ran in 40seconds instead of 2 minutes, which is a noticeable improvement.

Any idea on what I can do to try and improve the speed of this query when sorting by DESC? I've read that for b-tree indices, it should generally give you the same performance irregardless of sort order, but that does not seem to be the case.

7
  • 3
    When you change to ASC, I bet it is actually using an index on user_id. Can you check? – Stu Oct 3 '20 at 3:37
  • Which version of Postgres are you on? Please tag. You're limited to 5 tags; remove the database-design tag as your question isn't about that. – Colin 't Hart Oct 3 '20 at 6:54
  • Add an index on (user_id, id) – ypercubeᵀᴹ Oct 3 '20 at 14:38
  • Do you have an index on user_id? If not, what I believe is happening is that for user id 123 the corresponding IDs are small, so when scanning backwards they are encountered towards the end of the scan. Otherwise scanning forward or backward should indeed make no difference. Performance-wise the best option would be to create a composite index: CREATE INDEX compositeindex ON large_table (user_id, id) – dbilid Oct 3 '20 at 14:38
  • Since you only return a count, why bother specifying an order at all? – jjanes Oct 3 '20 at 15:08
4

Your query must be using an index on "id" to scan the index in the implied order, and then filtering out everything where "user_id" does not equal 123, stopping after it finds 31 rows which survive the filter. Going in one direction it quickly finds 31 such rows, going in the other direction needs to filter out a large number of rows before 31 survive (because none/few of the rows starting at that end have user_id=123).

You could readily confirm this theory by doing an EXPLAIN (ANALYZE, BUFFERS) of the queries.

This is not fundamentally about the order of the index scan. If you picked a value for 123 which had the opposite property (they all occurred at the logical end of the index rather than the logical beginning) then the situation would be reversed. Specifying DESC would fix the problem, rather than causing it.

Any idea on what I can do to try and improve the speed of this query when sorting by DESC?

Your query seems pointless. Counting is not an order-dependent activity. This is probably not your real query. So who knows if our suggestions would transfer over to your real query? The most straighforward fix for this query would be to build a multicolumn index on (user_id, id). Then no rows would get filtered out one by one, as they would be removed in wholesale through the operation of the index.

1

There is a discussion about this in the documentation (https://www.postgresql.org/docs/current/indexes-ordering.html):

By default, B-tree indexes store their entries in ascending order with nulls last. This means that a forward scan of an index on a column x produces output satisfying ORDER BY x (or more verbosely, ORDER BY x ASC NULLS LAST). The index can also be scanned backward, producing output satisfying ORDER BY x DESC (or more verbosely, ORDER BY x DESC NULLS FIRST, since NULLS FIRST is the default for ORDER BY DESC).

You can adjust the ordering of a B-tree index by including the options ASC, DESC, NULLS FIRST, and/or NULLS LAST when creating the index

...snip...

You might wonder why bother providing all four options, when two options together with the possibility of backward scan would cover all the variants of ORDER BY. In single-column indexes the options are indeed redundant, but in multicolumn indexes they can be useful.

If the query planner has picked a multi column index, you may be in the situation described by the documentation. If it is using a single column index, then your observed performance is unusual.

I recommend you create a descending index and see if that improves performance:

CREATE INDEX test3_desc_index ON test3 (id DESC NULLS LAST);
2
  • I doubt this applies to him. Since the first column is constrained by equality and is not sorted upon, it could still use the index regardless of the declared ordering. – jjanes Oct 3 '20 at 15:11
  • True, but not knowing what indexes are defined the query planner might have picked one. The documentation specifically mentions that defining the order may help with some queries. It's a cheap experiment to run – Jim D Oct 4 '20 at 0:17

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.