Re: Re: Adding additional index causes 20, 000x slowdown for certain select queries - postgres 9.0.3

"Kevin Grittner" <Kevin(dot)Grittner(at)wicourts(dot)gov> writes:
> Timothy Garnett <tgarnett(at)panjiva(dot)com> wrote:
> -> Index Scan Backward using
> index_customs_records_on_month_and_bl_number on customs_records
> (cost=0.00..78426750.74 rows=48623 width=908) (actual
> time=171344.182..3858893.588 rows=100 loops=1)

> We've seen a lot of those lately -- Index Scan Backward performing
> far worse than alternatives.

It's not clear to me that that has anything to do with Tim's problem.
It certainly wouldn't be 20000x faster if it were a forward scan.

> One part of it is that disk sectors
> are arranged for optimal performance on forward scans; but I don't
> think we've properly accounted for the higher cost of moving
> backward through our btree indexes, either. To quote from the
> README for the btree AM:

> | A backwards scan has one additional bit of complexity: after
> | following the left-link we must account for the possibility that
> | the left sibling page got split before we could read it. So, we
> | have to move right until we find a page whose right-link matches
> | the page we came from. (Actually, it's even harder than that; see
> | deletion discussion below.)

That's complicated, but it's not slow, except in the extremely
infrequent case where there actually was an index page split while your
scan was in flight to the page. The normal code path will only spend
one extra comparison to verify that no such split happened, and then it
goes on about its business.

The point about disk page layout is valid, so I could believe that in
a recently-built index there might be a significant difference in
forward vs backward scan speed, if none of the index were in memory.
The differential would degrade pretty rapidly due to page splits though
...

regards, tom lane