Re: No heap lookups on index

On Wed, 2006-01-18 at 18:27 -0500, Tom Lane wrote:
> Imagine an index that
> contains only the upper levels of a search tree --- links to what
> would be the leaf level point into the associated heap. In this
> design
> the heap is still a heap in the sense that you can seqscan it without
> any awareness of the index structure. What you can't do is insert
> tuples or move them around without the index AM's say-so.
> RelationGetBufferForTuple would become an index AM call, but otherwise
> I think the impact on existing code wouldn't be large.

Eureka! I had been thinking of a "block level index" which sounds almost
the same thing (as opposed to the row level indexes we have now). We
only need to index the row with the lowest value on any page so the main
index would get 100 times smaller. The main part of the index would not
need to be written to except when a block overflows.

I had imagined an ordering within a block to allow fast uniqueness
checks, but it would be pretty fast either way.

Merge joins with the same index become block-level joins without sorts.
We would just do an individual block sort before merging, so no need for
very large sort-merges. Even if the block level indexes differ, we only
need to sort one of the tables.

Hopefully we could avoid trying to support GIST-heaps?

Best Regards, Simon Riggs