Simon Riggs <simon@2ndquadrant.com> writes:
> 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.
BTW, the above is equivalent to saying that the leaf-level index pages
aren't there: the downlink pointers on the level-1 index pages are
pointers to heap pages, instead, and you're right that they effectively
only index the lowest value per page (actually IIRC the highest value
per page, but same difference).
I think the "100x" figure is overoptimistic though. There will be a lot
fewer entries per leaf page because actual heap tuples will be a lot
larger than index entries (typically at least). Hence, you need more
level-1 entries and so the upper index levels are bigger than in a
simple index. Another point is that the heap will be somewhat bloated
compared to a simple heap because of containing more unused space.
The traditional rule-of-thumb is that a btree index is only about 2/3rds
full at steady state, and I suppose this would apply to a
btree-organized heap too.
Still, it seems like an idea worth investigating.
> 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.
I'd phrase that a little differently: an indexscan on such an index
would normally deliver unordered output, but you could demand ordered
output and get it by doing successive one-page sorts. I doubt it's
worth inventing a new layer of mergejoin code to do this rather than
keeping it at the index access level.
Come to think of it, the idea also seems to map nicely into bitmap index
scans: the index will directly hand back a list of potential pages to
look at, but they are all marked "lossy" because the index doesn't know
exactly which tuple(s) on the target pages match the query. The
existing bitmap-heap-scan code can take it from there.
regards, tom lane