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