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