Re: proposal: be smarter about i/o patterns in index scan

> -----Original Message-----
> From: pgsql-hackers-owner(at)postgresql(dot)org
> [mailto:pgsql-hackers-owner(at)postgresql(dot)org]On Behalf Of Tom Lane
> Sent: Wednesday, May 19, 2004 11:56 AM

> Not unless you add yet another sort step after the fetch step, that is
> the idea becomes
> 1. read index to get candidate TIDs
> 2. sort TIDs into physical order
> 3. read heap in physical order, check row visibility
> 4. sort selected rows into index order
>
> That would start to look like an unpleasant amount of overhead, since
> the sort would have to be over the entire output; you couldn't divide
> the scan into reasonable-size batches, whereas steps 1-3 can easily
> be run in batched style.

Or:

2. Sort AND COPY TID's into physical order.
3. Read heap in phy. order, match results to un-sorted TID list.

That sounds quite cheap.

Then you get to drop step 4 (which would *usually* be quite a bit more
expensive than a TID sort and copy?).

The cost of the proposed implementation would be higher *when everything is
in the cache*, granted. As a user, I will take that cost 10 times over in
return for such a large improvement in the no-cache situation.

-Glen