Indexam interface proposal

Currently amgettuple returns one matching tuple at a time, in index
order. I'm proposing two changes to add support for
- candidate matches
- partial ordering

Those two features are essential to make clustered indexes work, and in
the future, binned bitmap indexes that don't have a bitmap for each
distinct value but for ranges of values.

There's a third feature looming in the future, that I haven't addressed:
- returning index values, for index-only scans or at least for filtering
rows before fetching heap tuples.

I'm proposing that we keep the one tuple per call nature of the
interface, but add a flag to mark candidate matches. index_getnext or
the executor would need to recheck the original quals for tuples marked
as candidates.

Another flag would be used to mean "this tuple marks the boundary of a
partial ordering". Let's call it boundary_mark for now.

For example, if an index scan returned tuples with the following keys,
with tuples on same line meaning the index doesn't know their relative
ordering.

1
3 4 2
5 8 6 7
9
10

amgettuple would return the above tuples like this:

1 3 4 2 5 8 6 7 9 10
* * * * *

where the tuples marked with * would have the boundary_mark-flag set. If
the plan requires ordered results, index_getnext would have to sort
tuples between two markers before returning them to the caller.

amgetmulti would also need to have the candidate-flag added as I
proposed in the "Bitmapindexscan changes" patch I sent earlier to
pgsql-patches.

This interface change would solve much of the ugliness of my GIT patch,
by generalizing the index quals checking and sorting code to index_getnext.

Another source of ugliness in the patch is in inserting new tuples.
Inserts need to reach to the heap to fetch heap tuples, to compare keys
when splitting a group. I don't see a clean fix for that, but I don't
think it's as bad as the index scan code.

--
Heikki Linnakangas
EnterpriseDB http://www.enterprisedb.com