Re: bitmap scans, btree scans, and tid order

Neil Conway wrote:
> Jeffrey Baker wrote:
>
>> Would you take a patch that retained the optimized executions of plans
>> returning 1 tuple and also fixed the random heap problem?
>
>
> Can you elaborate on what you're proposing? Obviously sorted b+-tree
> output is important for a lot more than just min()/max(). I don't see an
> obvious way to produce sorted output from a bitmap tree index scan
> without requiring an additional sort step (which would be rather
> pointless -- the whole point of the optimization is to avoid an
> additional sort).

I understand the importance of returning tuples in index order for many
plans (although I probably haven't thought of all the cases. min/max is
the most obvious; order by + limit is another). The only problem I'm
trying to solve is when an indexscan returns a large result, causing the
heap to be visited in index order, which is to say random order, from
the disk's perspective. When I investigated this last year, sorting the
intermediate result of the index scan in disk order was good for a
reduction by two-thirds in actual execution time, and sorting the scan
result in chunks of 1000 tuples was enough to reduce the time by half.

I'm considering one of the following courses of action:

Change nodeIndexscan.c to call index_getmulti, and to handle multiple
tuples returned. That code would sort the tuple array and store the
tuples in the result in disk order.

-or-

Change the planner/executor to use the bitmap scan in all cases where
index order is unimportant. From my reading of the current code, the
bitmap scan is only used in case of a join.

-jwb