To: Shaun Thomas <sthomas@leapfrogonline.com>
cc: Antoine Baudoux <ab@taktik.be>,
	"pgsql-performance@postgresql.org" <pgsql-performance@postgresql.org>
Subject: Re: multiple joins + Order by + LIMIT query performance issue 
In-reply-to: <1210092220.14833.33.camel@berners-lee> 
References: <938EC908-FB9A-4BFA-950A-053BE3C87085@taktik.be>
	<1210092220.14833.33.camel@berners-lee>
Comments: In-reply-to Shaun Thomas <sthomas@leapfrogonline.com>
	message dated "Tue, 06 May 2008 11:43:40 -0500"
Date: Tue, 06 May 2008 13:59:09 -0400
Message-ID: <16494.1210096749@sss.pgh.pa.us>
From: Tom Lane <tgl@sss.pgh.pa.us>

Shaun Thomas <sthomas@leapfrogonline.com> writes:
> I'm not sure what causes this, but the problem with indexes is that
> they're not necessarily in the order you want unless you also cluster
> them, so a backwards index scan is almost always the wrong answer.

Whether the scan is forwards or backwards has nothing to do with it.
The planner is using the index ordering to avoid having to do a
full-table scan and sort.  It's essentially betting that it will find
25 (or whatever your LIMIT is) rows that satisfy the other query
conditions soon enough in the index scan to make this faster than the
full-scan approach.  If there are a lot fewer matching rows than it
expects, or if the target rows aren't uniformly scattered in the index
ordering, then this way can be a loss; but when it's a win it can be
a big win, too, so "it's a bug take it out" is an unhelpful opinion.

If a misestimate of this kind is bugging you enough that you're willing
to change the query, I think you can fix it like this:

	select ... from foo order by x limit n;
=>
	select ... from (select ... from foo order by x) ss limit n;

The subselect will be planned without awareness of the LIMIT, so you
should get a plan using a sort rather than one that bets on the LIMIT
being reached quickly.

			regards, tom lane