Re: Indexes slower when used in decending vs. ascending order?

Oh: and as a followup, I ran the same query against the same data in 8.1
and it returned in 0.5 seconds. Looks like this bug/issue/feature in
pre-8.0 versions was to blame.

Thanks once again for your help.

- alasdair

-----Original Message-----
From: Tom Lane [mailto:tgl(at)sss(dot)pgh(dot)pa(dot)us]
Sent: Tuesday, April 11, 2006 1:54 PM
To: Alasdair Young
Cc: pgsql-novice(at)postgresql(dot)org
Subject: Re: [NOVICE] Indexes slower when used in decending vs.
ascending order?

Alasdair Young <ayoung(at)vigilos(dot)com> writes:
>> That's pretty spectacular. There is no way that Postgres is only
>> fetching one row per second; it's got to be discarding a whole lot of

>> rows under the hood. It'd be useful to run VACUUM VERBOSE on this
>> table and see what it's got to say.

> vigprem=# vacuum verbose log;
> INFO: --Relation public.log--
> INFO: Pages 82731: Changed 0, Empty 0; Tup 1654586: Vac 0, Keep 0,
> UnUsed 0.
> Total CPU 0.70s/0.26u sec elapsed 10.63 sec.
> VACUUM

[ looks again... ] Hmm, I can give you one quick performance tip:
use something newer than PG 7.3.x. VACUUM's output hasn't looked like
that in a long time.

Realizing that you're using such an old version, I now have another
theory: are there by any chance a whole lot of rows matching the WHERE
condition? If so I think this is explained by a problem we fixed in PG
8.0: the original coding for btree index search didn't handle lots of
equal keys very well. IIRC, what it's doing is descending the search
tree to find the first entry matching the WHERE condition --- and then,
because you asked for a backwards scan, it sequentially steps forward
over all the matching keys to get in position to scan them backwards.
In 8.0 we made the tree descent logic smart enough to arrive at the end
of the run of matching keys to start with.

2003-12-20 20:23 tgl

* src/: backend/access/nbtree/nbtinsert.c,
backend/access/nbtree/nbtpage.c,
backend/access/nbtree/nbtsearch.c,
include/access/nbtree.h: Improve btree's
initial-positioning-strategy code so that we never need to step
more than one entry after descending the search tree to arrive
at
the correct place to start the scan. This can improve the
behavior
substantially when there are many entries equal to the chosen
boundary value. Per suggestion from Dmitry Tkach, 14-Jul-03.

regards, tom lane