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

Alasdair Young <ayoung@vigilos.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