Re: Firebird 1.0 released

While it is true that you can't do binary searches on compressed indexes you
may get a large payoff with compressed indexes since the index fits in fewer
pages and so may be more efficiently cached in the buffer pool. Even a
small reduction in io load may compensate for the higher computational
demands of a compressed index.

Note also that insertion of a key can never cause following entries to
increase in size, only remain the same or decrease. Deletion of an entry
may cause the following entry to increase in size but never more than the
size of the entry deleted so deletes can't cause page splits.
-regards
richt

-----Original Message-----
From: pgsql-hackers-owner(at)postgresql(dot)org
[mailto:pgsql-hackers-owner(at)postgresql(dot)org]On Behalf Of Tom Lane
Sent: Tuesday, April 16, 2002 9:48 AM
To: Denis Perchine
Cc: Hackers
Subject: Re: [HACKERS] Firebird 1.0 released

Denis Perchine <dyp(at)perchine(dot)com> writes:
> I was interested in this:
> Firebird's indexes are very dense because they compress both the prefix
and
> the suffix of each key. Suffix compression is simply the elimination of
> trailing blanks or zeros, depending on the data type. Suffix compression
is
> performed on each segment of a segmented key. Prefix compression removes
the
> leading bytes that match the previous key. Thus a duplicate value has no
key
> stored at all. Dense storage in indexes minimizes the depth of the btrees,
> eliminating the advantage of other index types for most data.

> Do we do this? How feasible is this?

No, and it seems very bogus to me. With a storage scheme like that,
you could not do a random-access search --- the only way to know the
true value of each key is if you are doing a linear scan of the page,
so that you can keep track of the previous key value by dead reckoning.
(This assumes that the first key on each page is stored in full;
otherwise it's even worse.)

Another problem is that key inserts and deletes get more complex since
you have to recompute the following tuple. Life will get interesting
if the following tuple expands; you might have to split the page to hold
it. (Hmm, is it possible for a *delete* to force a page split under the
Firebird scheme? Not sure.)

The actual value of leading-byte suppression seems very data-dependent
to me, anyway. For example, for an integer key column on a
little-endian machine, leading-byte suppression would buy you nothing at
all. (Perhaps Firebird's implementation has enough datatype-specific
knowledge to trim integer keys at the proper end; I don't know. But I
wouldn't want to see us try to push datatype dependencies into our index
access methods.)

regards, tom lane

---------------------------(end of broadcast)---------------------------
TIP 4: Don't 'kill -9' the postmaster