Re: Page access pattern in query plan using index scan

On Wed, Jun 02, 2004 at 11:22:53PM -0400, Jack Orenstein wrote:
> Alvaro Herrera wrote:
> >On Wed, Jun 02, 2004 at 08:38:58PM -0400, Jack Orenstein wrote:
> >
> >
> >>What is the pattern of access to data pages? I can think of two likely
> >>answers:
> >>
> >>1) The index is scanned for ages 30 through 40. As each index entry is
> >>scanned, a row is retrieved.
> >
> >This one. There have been noises about doing the second, but it's non
> >trivial and there's no hacker currently working on it. Not to be
> >expected on the next version, I'd think.
>
> My naive guess about this is that you read the index entries, each one
> contains a page number, and you sort by the page number. The set of
> index entries could be large, requiring a potentially expensive sort.
> I don't know enough about query plan internals to know if this sort of
> plan can even be expressed currently, so maybe a major extension would
> be needed. And then the optimizer would have to be extended to
> consider the two approaches. Is this why you say the problem is
> non-trivial, or is there some additional set of issues that I'm
> missing?

Part of the problem is that the sort is not expressable in the current
code. Another part is that this kind of index scan is different and
violates some assumptions of the current indexscan, so it's not best in
all scenarios. Several planner/optimizer improvements are needed for
this to work. This has been discussed several times on the hackers'
list. If you want to read them, search for "bitmap indexes" on
http://www.pgsql.ru. Note that this seems to be different from what
other RDBMSs consider a bitmap index to be.

Regarding your other question: I don't know any application workaround.
There probably isn't any (unless you know how the tuples are sorted on
the heap, which is quite unlikely).

--
Alvaro Herrera (<alvherre[a]dcc.uchile.cl>)
"No hay cielo posible sin hundir nuestras raíces
en la profundidad de la tierra" (Malucha Pinto)