Re: bitmap scans, btree scans, and tid order

On P, 2005-05-15 at 23:58 -0700, Jeffrey Baker wrote:

> 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.

I think the 2nd option is probably the way to go. Probably not _all_
cases - it's probably cheper to not build a bitmap for cases where the
index returns only a few (or just one) rows.

OTOH, some scheme, where you fill sort_mem-sized memory structure with
tuples, which are fetched in heap order but stored in that structure in
index order could also be an interesting optimisastion for sort-order
preserving btree-index scans. this could also be used for bigger sort as
first step by saving each chunk to disk and then merging them back into
result.

in pseudocode one iteretion of this could go like this

TIDARRAY = ARRAY[1000]
I = 0
FOR TID in FETC_FROM_BTREE(0, 1000):
ARRAY [I] := (TID, I)
SORT_ARRAY_ON_TID() # this must be much faster than sorting
# whole tuples for this method to be a win
# over bitmap_scan + sort.
# using some self-ordering structure like
# btree/rbtree for TIDARRAY is also an option
OUTARRAY = ARRAY[1000]
FOR (TID, I) IN TIDARRAY:
OUTARRAY[I] = FETCH_FROM_HEAP(TID)
RETURN OUTARRAY

This can probably not use bitmap scan code, but has the nice property of
doing the disk accesses in file order but still returning the result in
index order.

--
Hannu Krosing <hannu(at)skype(dot)net>