Grouped Index Tuples

I've brought the GIT patch up-to-date with CVS head. The latest version
can be found at http://community.enterprisedb.com/git/

I also reran the CPU bound test cases with the latest patch.

I want this in 8.3 in some form, and I have the time to do any required
changes. If someone wants to see more tests, I can arrange that as well.

The patch is pretty big at the moment. I think the best way to proceed
with this is to extract some smaller, incremental patches from it that
just refactor the current b-tree code. After that, the final patch that
implements GIT should be much smaller and more readable. And there's
still a bunch of todo items there as well...

But before I start doing that, I need some review and general agreement
on the design. What I don't want to happen is that three days after the
feature freeze, someone finally looks at it and finds a major issue or
just thinks it's an unreadable mess, and we no longer have the time to
fix it.

One question that I'm sure someone will ask is do we need this if we
have bitmap indexes? Both aim at having a smaller index, after all. The
use cases are quite different; GIT is effective whenever you have a
table that's reasonably well-clustered. Unlike the bitmap indexam, GIT's
effectiveness doesn't depend on the number of distinct values, in
particular it works well with unique indexes. GIT is comparable to
clustered indexes in other DBMSs (in fact we might want to call GIT that
in the end).

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