LIMIT causes huge slow down

Hi people,

I'm hitting a strange behavior with our postgres servers : In some cases, using LIMIT causes slowest requests than without LIMIT :

webzine=> explain analyze SELECT id_photo, id_album, galerie_photo.etat, dimension, galerie_photo.titre, galerie_photo.dimension FROM galerie_photo JOIN galerie_album USING(id_album) WHERE galerie_album.id_webzine='18' AND id_flickr=0 AND id_picasa=0 ORDER BY id_photo DESC;
QUERY PLAN
-------------------------------------------------------------------------------------------------------------------------------------------------------------------------
Sort (cost=37527.48..37542.25 rows=5909 width=37) (actual time=19.742..21.066 rows=8247 loops=1)
Sort Key: galerie_photo.id_photo
Sort Method: quicksort Memory: 1186kB
-> Nested Loop (cost=0.84..37157.32 rows=5909 width=37) (actual time=0.044..14.104 rows=8247 loops=1)
-> Index Scan using galerie_album_picasa_flickr_idw_pos_idx on galerie_album (cost=0.42..447.58 rows=255 width=4) (actual time=0.032..0.497 rows=256 loops=1)
Index Cond: ((id_picasa = 0) AND (id_flickr = 0) AND (id_webzine = 18))
-> Index Scan using galerie_photo_id_album_idx on galerie_photo (cost=0.43..143.37 rows=59 width=37) (actual time=0.008..0.038 rows=32 loops=256)
Index Cond: (id_album = galerie_album.id_album)
Total runtime: 22.003 ms
(9 rows)

Adding LIMIT 1 modifies the query plan and slow downs...

webzine=> explain analyze SELECT id_photo, id_album, galerie_photo.etat, dimension, galerie_photo.titre, galerie_photo.dimension FROM galerie_photo JOIN galerie_album USING(id_album) WHERE galerie_album.id_webzine=18 AND id_flickr=0 AND id_picasa=0 ORDER BY id_photo DESC LIMIT 1;
QUERY PLAN
-------------------------------------------------------------------------------------------------------------------------------------------------------------------------------
Limit (cost=0.84..1523.63 rows=1 width=37) (actual time=115.787..115.787 rows=1 loops=1)
-> Nested Loop (cost=0.84..8998120.94 rows=5909 width=37) (actual time=115.787..115.787 rows=1 loops=1)
Join Filter: (galerie_photo.id_album = galerie_album.id_album)
Rows Removed by Join Filter: 374528
-> Index Scan Backward using galerie_photo_pkey on galerie_photo (cost=0.43..3056353.78 rows=1553286 width=37) (actual time=0.018..3.151 rows=1464 loops=1)
-> Materialize (cost=0.42..448.86 rows=255 width=4) (actual time=0.000..0.029 rows=256 loops=1464)
-> Index Scan using galerie_album_picasa_flickr_idw_pos_idx on galerie_album (cost=0.42..447.58 rows=255 width=4) (actual time=0.032..0.458 rows=256 loops=1)
Index Cond: ((id_picasa = 0) AND (id_flickr = 0) AND (id_webzine = 18))
Total runtime: 115.835 ms
(9 rows)

increasing the LIMIT parameter up to 8 don't change anything :

webzine=> explain analyze SELECT id_photo, id_album, galerie_photo.etat, dimension, galerie_photo.titre, galerie_photo.dimension FROM galerie_photo JOIN galerie_album USING(id_album) WHERE galerie_album.id_webzine=18 AND id_flickr=0 AND id_picasa=0 ORDER BY id_photo DESC LIMIT 8;
QUERY PLAN
-------------------------------------------------------------------------------------------------------------------------------------------------------------------------------
Limit (cost=0.84..12183.10 rows=8 width=37) (actual time=115.853..116.370 rows=8 loops=1)
-> Nested Loop (cost=0.84..8998120.94 rows=5909 width=37) (actual time=115.852..116.369 rows=8 loops=1)
Join Filter: (galerie_photo.id_album = galerie_album.id_album)
Rows Removed by Join Filter: 376313
-> Index Scan Backward using galerie_photo_pkey on galerie_photo (cost=0.43..3056353.78 rows=1553286 width=37) (actual time=0.019..3.072 rows=1471 loops=1)
-> Materialize (cost=0.42..448.86 rows=255 width=4) (actual time=0.000..0.030 rows=256 loops=1471)
-> Index Scan using galerie_album_picasa_flickr_idw_pos_idx on galerie_album (cost=0.42..447.58 rows=255 width=4) (actual time=0.032..0.525 rows=256 loops=1)
Index Cond: ((id_picasa = 0) AND (id_flickr = 0) AND (id_webzine = 18))
Total runtime: 116.420 ms
(9 rows)

But passing LIMIT 9 :

webzine=> explain analyze SELECT id_photo, id_album, galerie_photo.etat, dimension, galerie_photo.titre, galerie_photo.dimension FROM galerie_photo JOIN galerie_album USING(id_album) WHERE galerie_album.id_webzine=18 AND id_flickr=0 AND id_picasa=0 ORDER BY id_photo DESC LIMIT 9;
QUERY PLAN
-------------------------------------------------------------------------------------------------------------------------------------------------------------------------------
Limit (cost=0.84..13705.88 rows=9 width=37) (actual time=118.209..6905.990 rows=9 loops=1)
-> Nested Loop (cost=0.84..8998120.94 rows=5909 width=37) (actual time=118.207..6905.985 rows=9 loops=1)
Join Filter: (galerie_photo.id_album = galerie_album.id_album)
Rows Removed by Join Filter: 22882297
-> Index Scan Backward using galerie_photo_pkey on galerie_photo (cost=0.43..3056353.78 rows=1553286 width=37) (actual time=0.019..191.401 rows=89385 loops=1)
-> Materialize (cost=0.42..448.86 rows=255 width=4) (actual time=0.000..0.029 rows=256 loops=89385)
-> Index Scan using galerie_album_picasa_flickr_idw_pos_idx on galerie_album (cost=0.42..447.58 rows=255 width=4) (actual time=0.033..0.464 rows=256 loops=1)
Index Cond: ((id_picasa = 0) AND (id_flickr = 0) AND (id_webzine = 18))
Total runtime: 6906.050 ms
(9 rows)

Reducing the random page cost to 2.5 (I'm on SSD drives) can improve this behavior :

webzine=> explain analyze SELECT id_photo, id_album, galerie_photo.etat, dimension, galerie_photo.titre, galerie_photo.dimension FROM galerie_photo JOIN galerie_album USING(id_album) WHERE galerie_album.id_webzine='18' AND id_flickr=0 AND id_picasa=0 ORDER BY id_photo DESC ;
QUERY PLAN
-------------------------------------------------------------------------------------------------------------------------------------------------------------------------
Sort (cost=23807.38..23822.15 rows=5909 width=37) (actual time=19.163..20.660 rows=8247 loops=1)
Sort Key: galerie_photo.id_photo
Sort Method: quicksort Memory: 1186kB
-> Nested Loop (cost=0.84..23437.22 rows=5909 width=37) (actual time=0.040..13.553 rows=8247 loops=1)
-> Index Scan using galerie_album_picasa_flickr_idw_pos_idx on galerie_album (cost=0.42..283.50 rows=255 width=4) (actual time=0.030..0.433 rows=256 loops=1)
Index Cond: ((id_picasa = 0) AND (id_flickr = 0) AND (id_webzine = 18))
-> Index Scan using galerie_photo_id_album_idx on galerie_photo (cost=0.43..90.21 rows=59 width=37) (actual time=0.008..0.037 rows=32 loops=256)
Index Cond: (id_album = galerie_album.id_album)
Total runtime: 21.554 ms
(9 rows)

webzine=> explain analyze SELECT id_photo, id_album, galerie_photo.etat, dimension, galerie_photo.titre, galerie_photo.dimension FROM galerie_photo JOIN galerie_album USING(id_album) WHERE galerie_album.id_webzine='18' AND id_flickr=0 AND id_picasa=0 ORDER BY id_photo DESC LIMIT 1;
QUERY PLAN
-----------------------------------------------------------------------------------------------------------------------------------------------------------------------
Limit (cost=0.72..1284.78 rows=1 width=37) (actual time=6.356..6.356 rows=1 loops=1)
-> Nested Loop (cost=0.72..7587529.65 rows=5909 width=37) (actual time=6.356..6.356 rows=1 loops=1)
-> Index Scan Backward using galerie_photo_pkey on galerie_photo (cost=0.43..1925267.77 rows=1553286 width=37) (actual time=0.026..2.123 rows=1464 loops=1)
-> Index Scan using galerie_album_pkey on galerie_album (cost=0.29..3.64 rows=1 width=4) (actual time=0.002..0.002 rows=0 loops=1464)
Index Cond: (id_album = galerie_photo.id_album)
Filter: ((id_webzine = 18) AND (id_flickr = 0) AND (id_picasa = 0))
Rows Removed by Filter: 1
Total runtime: 6.402 ms
(8 rows)

webzine=> explain analyze SELECT id_photo, id_album, galerie_photo.etat, dimension, galerie_photo.titre, galerie_photo.dimension FROM galerie_photo JOIN galerie_album USING(id_album) WHERE galerie_album.id_webzine='18' AND id_flickr=0 AND id_picasa=0 ORDER BY id_photo DESC LIMIT 9;
QUERY PLAN
--------------------------------------------------------------------------------------------------------------------------------------------------------------------------
Limit (cost=0.72..11557.29 rows=9 width=37) (actual time=6.286..356.399 rows=9 loops=1)
-> Nested Loop (cost=0.72..7587529.65 rows=5909 width=37) (actual time=6.286..356.395 rows=9 loops=1)
-> Index Scan Backward using galerie_photo_pkey on galerie_photo (cost=0.43..1925267.77 rows=1553286 width=37) (actual time=0.020..103.572 rows=89385 loops=1)
-> Index Scan using galerie_album_pkey on galerie_album (cost=0.29..3.64 rows=1 width=4) (actual time=0.002..0.002 rows=0 loops=89385)
Index Cond: (id_album = galerie_photo.id_album)
Filter: ((id_webzine = 18) AND (id_flickr = 0) AND (id_picasa = 0))
Rows Removed by Filter: 1
Total runtime: 356.452 ms
(8 rows)

The tables have been vacuumed, analyzed and reindexed without any change. results are reproductibles.
galerie_album has 67033 rows (256 of them have id_webzine=18)
galerie_photo has 1494738 rows

Any idea or workaround ?

Regards,

Grégory Giannoni.