Index scan?

Theo Kramer <theo@flame.co.za> writes:

Does anyone know why the following occurs?
coza=> explain select * from accounts where domain >= '%' order by domain;
NOTICE: QUERY PLAN:

Index Scan using domain_idx on accounts (cost=1434.50 rows=19611 width=106)

and
coza=> explain select * from accounts order by domain;
NOTICE: QUERY PLAN:

Sort (cost=3068.39 rows=58830 width=106)
-> Seq Scan on accounts (cost=3068.39 rows=58830 width=106)

Surely both queries give the same result set, yet the second example does not
use the index causing unnecessary overhead.

Yeah, this is a known limitation of the planner: it's only bright enough
to skip an explicit sort step for an ORDER BY clause when the plan that
*would be chosen anyway in the absence of ORDER BY* happens to produce
a properly sorted result. In your first example the WHERE clause can
be exploited to scan only part of the index (notice the difference in
estimated output row counts), so an indexscan gets chosen --- and that
just happens to deliver the sorted result you want. In the second
example the plan-picker sees no reason to use anything more expensive
than a sequential scan :-(

We need to push awareness of the output ordering requirement down into
the code that chooses the basic plan. It's on the TODO list (or should
be) but I dunno when someone will get around to it.

regards, tom lane

Tom Lane wrote:

Yeah, this is a known limitation of the planner: it's only bright enough
to skip an explicit sort step for an ORDER BY clause when the plan that
*would be chosen anyway in the absence of ORDER BY* happens to produce
a properly sorted result. In your first example the WHERE clause can
be exploited to scan only part of the index (notice the difference in
estimated output row counts), so an indexscan gets chosen --- and that
just happens to deliver the sorted result you want. In the second
example the plan-picker sees no reason to use anything more expensive
than a sequential scan :-(

We need to push awareness of the output ordering requirement down into
the code that chooses the basic plan. It's on the TODO list (or should
be) but I dunno when someone will get around to it.

I can't wait :-)
--------
Regards
Theo

Yeah, this is a known limitation of the planner: it's only bright enough
to skip an explicit sort step for an ORDER BY clause when the plan that
*would be chosen anyway in the absence of ORDER BY* happens to produce
a properly sorted result. In your first example the WHERE clause can
be exploited to scan only part of the index (notice the difference in
estimated output row counts), so an indexscan gets chosen --- and that
just happens to deliver the sorted result you want. In the second
example the plan-picker sees no reason to use anything more expensive
than a sequential scan :-(

We need to push awareness of the output ordering requirement down into
the code that chooses the basic plan. It's on the TODO list (or should
be) but I dunno when someone will get around to it.

Added to TODO:

* Allow optimizer to prefer plans that match ORDER BY

-- 
  Bruce Momjian                        |  http://www.op.net/~candle
  maillist@candle.pha.pa.us            |  (610) 853-3000
  +  If your life is a hard drive,     |  830 Blythe Avenue
  +  Christ can be your backup.        |  Drexel Hill, Pennsylvania 19026

Theo Kramer <theo@flame.co.za> writes:

Tom Lane wrote:

We need to push awareness of the output ordering requirement down into
the code that chooses the basic plan. It's on the TODO list (or should
be) but I dunno when someone will get around to it.

I can't wait :-)

I am about to do some major hacking on the planner/optimizer's
representation of path sort orders (for anyone who cares, PathOrder data
is going to be merged into the pathkeys structures). After the dust
settles, I will see what I can do with this issue --- it might be pretty
easy once the data structures are cleaned up.

Aside from the case with an ORDER BY clause, I believe the planner is
currently too dumb to exploit a pre-sorted path for GROUP BY. It
always puts in an explicit sort on the GROUP BY keys ...

regards, tom lane