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

"Glen Parker" <glenebob(at)nwlink(dot)com> writes:
>> 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

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

No, it sounds like handwaving. What's your "match results" step, and
does it take less than O(N^2) time? How do you get to *return* the
tuples in index order, without having read them all before you return
the first one? (Which is really what the problem is with the sort
alternative, at least for fast-start cases such as the LIMIT 1 example.)
What happens when you run out of memory for the list of TIDs ... er,
make that two lists of TIDs?

regards, tom lane