Re: A Silly Idea for Vertically-Oriented Databases

Ühel kenal päeval, E, 2007-09-10 kell 11:01, kirjutas Alvaro Herrera:
> Mark Mielke wrote:
> > Simon Riggs wrote:
> >> ISTM we would be able to do this fairly well if we implemented
> >> Index-only columns. i.e. columns that don't exist in the heap, only in
> >> an index. 
> >> Taken to the extreme, all columns could be removed from the heap and
> >> placed in an index(es). Only the visibility information would remain on
> >> the heap.
> >>   
> > Wouldn't the extreme be - even the visibility information is in the index? 
> 
> Maybe we could extract the visibility information and put it in a
> storage separate from the heap.  A seqscan would be a bit slower (have
> to check the heap and the visibility storage) but some index scans could
> be faster (can check the index and visibility storage, skipping the
> heap), and updates would be faster too (append into the heap, update
> visibility storage).  This would allow something closer to index-only
> scans.  Of course, the key is to allow efficient lookup of visibility
> info given a TID.
> 
> Has this been explored before?

I wrote to this list about a vague plan for doing it some months ago.

And I don't think that even seqscans need to be slower, as at least for
typical Data Warehouse application the visibility info can be compressed
a lot by even a simple RLE compression and thus you just do the sequscan
like this

while 1:   get next visible range   read in the visible range, without checking each tuple

I suspect that this can be made much more cache-friendly than current
scheme.

(A Guess: I even go as far as to claim that separate visibility heap
_may_ be more cahce friendly even uncompressed, so if we have every
second tuple deleted, it will still be faster (at least for bigger
tuples) to look up visibility in a dense visibility array and then
access just the visible tuples. Here even separate heap may be not
needed, just rearranging the heap structure to have visibility info in
the beginning of page together with tuple pointers may be a win )

Another bonus of separate visibility heap is that it can be maintained
separately, that is it can be shuffled around, CID's cleaned up,
compressed, etc. much more effectively than current one, which, among
other things will make VACUUM much more efficient, as neither
all-visible or all-dead pages need to be visited at all.

It can probably be made to serve as both DSM and VACUUM map also. And it
can be used for finding "best" insert spot for CLUSTERing-preserving
inserts/updates.


On subject of vertical or column-per-heap storage I see the biggest
obstacle to be te use of TID-s as tuple identifiers, as the "real" TIDs
(pageno32:tupleno:16) will be different for each column. So if we have a
table with a 1 kb text column, we will also have to store just 8 ints
per page in the int column if we want to preserve unique TID->tuple
mapping.

What we could do of course is start defining TID as just a 48-bit tuple
number and then have some rules for finding the PAGE:NR "tid" from that

it would be easy for fixed-size columns 
(PAGE:NR) = (TID/items_per_page:TID mod items_per_page)
but more complicated for VARLEN fields.

All the ideas I've had sofar for solving this have quite  a lot of
downsides. 

--------------
Hannu