[prev in list] [next in list] [prev in thread] [next in thread] 

List:       postgresql-general
Subject:    [HACKERS] Indexam interface proposal
From:       Heikki Linnakangas <heikki () enterprisedb ! com>
Date:       2007-03-19 12:23:01
Message-ID: 45FE80A5.9080208 () enterprisedb ! com
[Download RAW message or body]

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

---------------------------(end of broadcast)---------------------------
TIP 4: Have you searched our list archives?

               http://archives.postgresql.org
[prev in list] [next in list] [prev in thread] [next in thread]