Originally posted: https://stackoverflow.com/questions/11173717/expensive-query-on-select-distinct-with-multiple-inner-join-in-postgres

The songs table has only about 4k rows, posts and stations have less. Running the query without the DISTINCT ON fixes it.

Running Postgres on Mac OS X Lion.

Song Load (7358.2ms)

EXPLAIN (426.2ms)

SELECT  DISTINCT ON (songs.rank, songs.shared_id) songs.*, 
        posts.url as post_url, 
        posts.excerpt as post_excerpt, 
        stations.title as station_title, 
        stations.slug as station_slug 
FROM "songs" 
    INNER JOIN "posts" ON "posts"."id" = "songs"."post_id" 
    inner join stations on stations.blog_id = songs.blog_id 
WHERE "songs"."processed" = 't' 
  AND "songs"."working" = 't' 
ORDER BY songs.rank desc 

                                           QUERY PLAN
 Limit  (cost=546147.28..546159.16 rows=24 width=2525)
   ->  Unique  (cost=546147.28..547360.75 rows=2452 width=2525)
         ->  Sort  (cost=546147.28..546551.77 rows=161796 width=2525)
               Sort Key: songs.rank, songs.shared_id
               ->  Hash Join  (cost=466.50..2906.84 rows=161796 width=2525)
                     Hash Cond: (songs.blog_id = stations.blog_id)
                     ->  Hash Join  (cost=249.41..587.52 rows=2452 width=2499)
                           Hash Cond: (songs.post_id = posts.id)
                           ->  Seq Scan on songs  (cost=0.00..304.39 rows=2452 width=2223)
                                 Filter: (processed AND working)
                           ->  Hash  (cost=230.85..230.85 rows=1485 width=280)
                                 ->  Seq Scan on posts  (cost=0.00..230.85 rows=1485 width=280)
                     ->  Hash  (cost=140.93..140.93 rows=6093 width=30)
                           ->  Seq Scan on stations  (cost=0.00..140.93 rows=6093 width=30)

I tried a few things... first index on (rank, shared_id). Then removed that and added an index on rank and shared_id separately, as well as combinations of the three... no luck.

Are the indexes not being used for some reason? Or do I need to do anything after adding an index to ensure they work?

  • 1
    Have you tried indexing (processed, working, rank, shared_id) ? – ypercubeᵀᴹ Jun 24 '12 at 0:44

Because the WHERE condition of the query involves only equality checks:

WHERE "songs"."processed" = 't' 
  AND "songs"."working" = 't'

and then you have:

SELECT  DISTINCT ON (songs.rank, songs.shared_id) ...

which is similar to GROUP BY songs.rank, songs.shared_id

I would first try adding a compound index on (first the columns in WHERE, then the columns in DISTINCT ON):

(processed, working, rank, shared_id)

The ordering: ORDER BY rank DESC may be better optimized if you have the index as:

(processed, working, rank DESC, shared_id)

Not really sure if this would contribute to efficiency but you can test.

Addition by @Erwin

As per request in comment

In principal (default) b-tree indexes can be scanned forward and backward at the same speed. But sorting can make a difference in multi-column indexes where you combine the sort order of multiple columns. The query starts with:

SELECT  DISTINCT ON (songs.rank, songs.shared_id)

In combination with ORDER BY rank DESC this dictates that the result be ordered by rank DESC, shared_id effectively. After the (simplified) WHERE clause WHERE processed AND working has been applied and before LIMIT can be applied.
I have my doubts if the DISTINCT clause is actually useful. But while it is there, the optimal index for the query should be (just as @ypercube suspected):

CREATE INDEX songs_special_idx
ON songs (processed, working, rank DESC, shared_id);

Looks like one of the rare cases where explicit ordering of index columns would benefit the query. There is an excellent explanation in the chapter Indexes and ORDER BY of the manual.

If the WHERE condition is stable (always WHERE processed AND working), a partial multi-column index would be smaller and faster, yet:

CREATE INDEX songs_special_idx
ON songs (rank DESC, shared_id)
WHERE processed AND working;
  • 2
    I'm getting picky here, because @ErwinBrandstetter is fundamentally right, and the fine point I'm about to raise will probably only be noticed in rare cases on highly contended workloads using deep, volatile indexes; but due to locking techniques a reverse index scan can't follow a sibling pointer without visiting the parent level. Unless there is blocking during the attempt, the difference is not likely to be significant. Just something to keep in mind in an environment like I just described. – kgrittn Jun 24 '12 at 16:11
  • @kgrittn: Indeed, B-tree indices work best when they are traversed in one (the forward) direction by all concurrent queries/statements/procedures. Otherwise complications may occur. – ypercubeᵀᴹ Jun 25 '12 at 7:27
  • @ypercube: "Complications may occur" sounds a little more dramatic than I think is merited. "There may be additional blocking in some workloads" is the reality. I guess you could call that "complications" -- but to me that word has connotations of something a bit more ominous and serious. I went through the PostgreSQL btree code pretty closely a couple years ago, and the only real asymmetry I saw was that on a forward scan you can follow a sibling page pointer without visiting the parent page, and on a reverse scan you needed to visit the parent. – kgrittn Jun 25 '12 at 10:31
  • @kgrittn: Yes, you are right of course.I was trying to be more general, I know almost nothing about Postgres implementation. With complications I meant "locking, blocking, deadlocks, etc..." – ypercubeᵀᴹ Jun 25 '12 at 12:09
  • 1
    You're right. Brief locks are needed on page images, of course, and those are optimized for forward traversal. It's just that in PostgreSQL B-trees are almost as good when reading backwards. There has been some discussion of adjusting the costing factor for reverse scans versus forward scans, but nobody could come up with a principled way to arrive at a multiplier, since the difference is usually too small to reliably measure. – kgrittn Jun 25 '12 at 14:33

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.