Changing location of ORDER BY has large effect on performance, but not results...

I have two queries that return the same results, but one is 6 times
slower than the other one, can anyone enlighten me as to why?

My initial guess is that it is not able to utilize the index on
foo.tracktitle to sort the result set after foo has been joined with
other tables. This seems kind of broken to me. I am running 8.0.4 on
Gentoo Linux.

Thanks,
Jason

--- First Query ---

select
foo.*,
genre.genrename,
album.albumtitle,
(select performer.performername from performer as p, trackperformers as tp
where p.performerid = tp.performerid
and tp.trackid = foo.trackid
limit 1) AS performername,

(SELECT coverartid
FROM trackcoverart
WHERE trackcoverart.trackid = foo.trackid
LIMIT 1) as trackcoverart,

(SELECT albumcoverart.coverartid
FROM albumcoverart, track
WHERE foo.trackid = trackid
AND albumcoverart.albumid = foo.albumid
LIMIT 1) as albumcoverart

FROM (select * from track order by tracktitle) as foo, album, genre

where foo.albumid = album.albumid
and foo.genreid = genre.genreid

offset 2000
limit 20;

--- First Explain Analyze ---

Limit (cost=20915.07..21123.71 rows=20 width=338) (actual
time=184.997..186.417 rows=20 loops=1)
-> Hash Join (cost=50.81..131860.75 rows=12635 width=338) (actual
time=5.085..185.202 rows=2020 loops=1)
Hash Cond: ("outer".albumid = "inner".albumid)
-> Hash Join (cost=13.07..938.94 rows=12635 width=318)
(actual time=1.317..34.143 rows=2020 loops=1)
Hash Cond: ("outer".genreid = "inner".genreid)
-> Subquery Scan foo (cost=0.00..736.34 rows=12635
width=288) (actual time=0.021..16.317 rows=2020 loops=1)
-> Index Scan using track_tracktitle on track
(cost=0.00..609.99 rows=12635 width=332) (actual time=0.012..4.266
rows=2020 loops=1)
-> Hash (cost=11.66..11.66 rows=566 width=34) (actual
time=1.267..1.267 rows=0 loops=1)
-> Seq Scan on genre (cost=0.00..11.66 rows=566
width=34) (actual time=0.004..0.737 rows=566 loops=1)
-> Hash (cost=33.59..33.59 rows=1659 width=24) (actual
time=3.646..3.646 rows=0 loops=1)
-> Seq Scan on album (cost=0.00..33.59 rows=1659
width=24) (actual time=0.012..2.194 rows=1659 loops=1)
SubPlan
-> Limit (cost=0.00..7.53 rows=1 width=4) (actual
time=0.021..0.021 rows=1 loops=2020)
-> Nested Loop (cost=0.00..7.53 rows=1 width=4)
(actual time=0.019..0.019 rows=1 loops=2020)
-> Index Scan using albumcoverart_albumid on
albumcoverart (cost=0.00..3.01 rows=1 width=4) (actual
time=0.007..0.007 rows=1 loops=2020)
Index Cond: (albumid = $1)
-> Index Scan using track_pkey on track
(cost=0.00..4.51 rows=1 width=0) (actual time=0.007..0.007 rows=1
loops=2020)
Index Cond: ($0 = trackid)
-> Limit (cost=0.00..2.78 rows=1 width=4) (actual
time=0.006..0.006 rows=0 loops=2020)
-> Index Scan using trackcoverart_trackid on
trackcoverart (cost=0.00..27.80 rows=10 width=4) (actual
time=0.004..0.004 rows=0 loops=2020)
Index Cond: (trackid = $0)
-> Limit (cost=0.00..0.03 rows=1 width=17) (actual
time=0.028..0.028 rows=1 loops=2020)
-> Nested Loop (cost=0.00..64.89 rows=2142 width=17)
(actual time=0.025..0.025 rows=1 loops=2020)
-> Nested Loop (cost=0.00..6.05 rows=2
width=0) (actual time=0.019..0.019 rows=1 loops=2020)
-> Index Scan using
trackperformers_trackid on trackperformers tp (cost=0.00..3.01 rows=1
width=4) (actual time=0.007..0.007 rows=1 loops=2020)
Index Cond: (trackid = $0)
-> Index Scan using performer_pkey on
performer p (cost=0.00..3.02 rows=1 width=4) (actual
time=0.007..0.007 rows=1 loops=2020)
Index Cond: (p.performerid =
"outer".performerid)
-> Seq Scan on performer (cost=0.00..18.71
rows=1071 width=17) (actual time=0.002..0.002 rows=1 loops=2020)
Total runtime: 186.706 ms

--- Second Query ---

select
foo.*,
genre.genrename,
album.albumtitle,
(select performer.performername from performer as p, trackperformers as tp
where p.performerid = tp.performerid
and tp.trackid = foo.trackid
limit 1) AS performername,

(SELECT coverartid
FROM trackcoverart
WHERE trackcoverart.trackid = foo.trackid
LIMIT 1) as trackcoverart,

(SELECT albumcoverart.coverartid
FROM albumcoverart, track
WHERE foo.trackid = trackid
AND albumcoverart.albumid = foo.albumid
LIMIT 1) as albumcoverart

FROM track as foo, album, genre

where foo.albumid = album.albumid
and foo.genreid = genre.genreid

order by foo.tracktitle

offset 2000
limit 20;

--- Second Explain Analyze ---

Limit (cost=134126.42..134126.47 rows=20 width=382) (actual
time=1068.650..1068.698 rows=20 loops=1)
-> Sort (cost=134121.42..134153.01 rows=12635 width=382) (actual
time=1064.642..1067.106 rows=2020 loops=1)
Sort Key: foo.tracktitle
-> Hash Join (cost=50.81..131602.77 rows=12635 width=382)
(actual time=5.242..956.526 rows=12635 loops=1)
Hash Cond: ("outer".albumid = "inner".albumid)
-> Hash Join (cost=13.07..680.95 rows=12635 width=362)
(actual time=1.332..119.681 rows=12635 loops=1)
Hash Cond: ("outer".genreid = "inner".genreid)
-> Seq Scan on track foo (cost=0.00..478.35
rows=12635 width=332) (actual time=0.003..19.214 rows=12635 loops=1)
-> Hash (cost=11.66..11.66 rows=566 width=34)
(actual time=1.297..1.297 rows=0 loops=1)
-> Seq Scan on genre (cost=0.00..11.66
rows=566 width=34) (actual time=0.004..0.760 rows=566 loops=1)
-> Hash (cost=33.59..33.59 rows=1659 width=24) (actual
time=3.801..3.801 rows=0 loops=1)
-> Seq Scan on album (cost=0.00..33.59 rows=1659
width=24) (actual time=0.012..2.246 rows=1659 loops=1)
SubPlan
-> Limit (cost=0.00..7.53 rows=1 width=4) (actual
time=0.018..0.019 rows=1 loops=12635)
-> Nested Loop (cost=0.00..7.53 rows=1
width=4) (actual time=0.016..0.016 rows=1 loops=12635)
-> Index Scan using albumcoverart_albumid
on albumcoverart (cost=0.00..3.01 rows=1 width=4) (actual
time=0.006..0.006 rows=1 loops=12635)
Index Cond: (albumid = $1)
-> Index Scan using track_pkey on track
(cost=0.00..4.51 rows=1 width=0) (actual time=0.005..0.005 rows=1
loops=12635)
Index Cond: ($0 = trackid)
-> Limit (cost=0.00..2.78 rows=1 width=4) (actual
time=0.005..0.005 rows=0 loops=12635)
-> Index Scan using trackcoverart_trackid on
trackcoverart (cost=0.00..27.80 rows=10 width=4) (actual
time=0.003..0.003 rows=0 loops=12635)
Index Cond: (trackid = $0)
-> Limit (cost=0.00..0.03 rows=1 width=17) (actual
time=0.024..0.025 rows=1 loops=12635)
-> Nested Loop (cost=0.00..64.89 rows=2142
width=17) (actual time=0.022..0.022 rows=1 loops=12635)
-> Nested Loop (cost=0.00..6.05 rows=2
width=0) (actual time=0.016..0.016 rows=1 loops=12635)
-> Index Scan using
trackperformers_trackid on trackperformers tp (cost=0.00..3.01 rows=1
width=4) (actual time=0.006..0.006 rows=1 loops=12635)
Index Cond: (trackid = $0)
-> Index Scan using performer_pkey
on performer p (cost=0.00..3.02 rows=1 width=4) (actual
time=0.005..0.005 rows=1 loops=12635)
Index Cond: (p.performerid =
"outer".performerid)
-> Seq Scan on performer
(cost=0.00..18.71 rows=1071 width=17) (actual time=0.002..0.002 rows=1
loops=12635)
Total runtime: 1072.935 ms

--
http://emptycrate.com Games, Programming, Travel & other stuff