Re: Firebird 1.0 released

From: Tom Lane <tgl(at)sss(dot)pgh(dot)pa(dot)us>
To: Denis Perchine <dyp(at)perchine(dot)com>
Cc: "Hackers" <pgsql-hackers(at)postgresql(dot)org>
Subject: Re: Firebird 1.0 released
Date: 2002-04-16 13:47:43
Message-ID: 11778.1018964863@sss.pgh.pa.us
Views: Raw Message | Whole Thread | Download mbox | Resend email
Thread:
Lists: pgsql-hackers

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

In response to

Responses

Browse pgsql-hackers by date

  From Date Subject
Next Message Louis-David Mitterrand 2002-04-16 14:03:53 Index Scans become Seq Scans after VACUUM ANALYSE
Previous Message Bosco Ng 2002-04-16 13:34:10 Just a Question