Re: bitmap scans, btree scans, and tid order

Tom Lane <tgl(at)sss(dot)pgh(dot)pa(dot)us> writes:

> "Jeffrey W. Baker" <jwbaker(at)acm(dot)org> writes:
> > I see that Tom has already done the infrastructure work by adding
> > getmulti, but getmulti isn't used by nodeIndexscan.c, only
> > nodeBitmapIndexscan.c. Will btree index scans be executed by creating
> > in-memory bitmaps in 8.1, or will some scans still be executed the usual
> > way?
>
> We aren't going to remove the existing indexscan behavior, because
> bitmap scans lose the ordering of the underlying index. There are many
> situations where that ordering is important. (See for instance the
> recent changes to make MAX/MIN use that behavior.)

Hm. There are other circumstances where the ordering doesn't matter. When
there's another unrelated ORDER BY clause or merge join wrapped around the
index scan for example.

This suggests one new 8.1 optimization strategy may be to add strategic no-op
OR clauses to cause 8.1 to use a bitmapOr node.

For example something like this where "flag" isn't very selective (say 25%)
might run more slowly than a sequential scan because of the random access
pattern.

SELECT id,name,flag
FROM tab
WHERE flag
ORDER BY name

But adding a no-op bitmapOr node like:

SELECT id,name,flag
FROM tab
WHERE flag
OR indexed_never_true_flag
ORDER BY name

Might run faster, perhaps even more quickly than the sequential scan because
the bitmap avoids the random access pattern but doesn't have to read the whole
table.

--
greg