How to avoid the SORT operation in SQL query that contains ORDER_BY condition?

Question

I am optimising a PostgreSQL query which involves three tables and a ORDER_BY condition. It seems that PostgreSQL prefer to arrange a SORT operation to perform the ORDER_BY condition, rather than using the index.

The raw SQL looks like this:

SELECT activity.provider, activity.provider_id, activity.crawled_at, activity.raw, activity.account_provider_id, activity.created_at
FROM activity 
JOIN friendship ON (activity.provider, activity.account_provider_id) = (friendship.provider, friendship.friend_provider_id) 
JOIN token ON (token.provider, token.account_provider_id) = (friendship.provider, friendship.provider_id) 
WHERE token.uid = 1 
ORDER BY created_at desc NULLS LAST
LIMIT 10 OFFSET 10000;

I have already created an index provider, account_provider_id, created_by on the activity table.

CREATE INDEX activity_provider_account_provider_id_created_at_idx
  ON activity
  USING btree
  (provider COLLATE pg_catalog."default", account_provider_id COLLATE pg_catalog."default", created_at DESC NULLS LAST);

However, the query plan returned by PostgreSQL requires an expensive SORT operation.

This query would take more than 10 seconds to finish. I also tried set enable_sort = false, but it didn't work. How should I optimise this query?

EDIT: I have added the execution time graph. The SORT operation is the most expensive part of the query. Without the ORDER_BY, the query returns pretty fast.

Answer 1

ORDER BY is not that expensive by itself. The problem here is that it is used together with OFFSET. So postgresql does sorting of all data before it can take needed 10 rows.

You are probably implementing paging using ORDER BY + OFFSET. This is a known postgresql limitation and there is postgresql way to handle this.

Answer 2

It turns out that I have made a mistake in explaining the problem. The SORT operation is not the most expensive part in this query, as shown in the second figure. The most expensive part is the second nested loop, which is responsible to materialise and join the activity table. The database engine need to fetch all the columns from the activity table. The query can be optimised by deferring the loading of extra columns:

SELECT * FROM activity WHERE (activity.provider, activity.account_provider_id, activity.created_at) IN (
  SELECT activity.provider, activity.account_provider_id, activity.created_at
  FROM activity 
  JOIN friendship ON (activity.provider, activity.account_provider_id) = (friendship.provider, friendship.friend_provider_id) 
  JOIN token ON (token.provider, token.account_provider_id) = (friendship.provider, friendship.provider_id) 
  WHERE token.uid = 2
  ORDER BY created_at desc NULLS LAST
  LIMIT 10 OFFSET 100
)

This can reduce the query time to ~100ms.

Both comment from @FuzzyTree and answer from @Roman Konoval are correct in the sense of the posed question.