On Wed, Sep 4, 2013 at 12:02 PM, Tim Ward <tdw@...> wrote:

due to prefix compression within the index structures

Ah, yes, I did write one of those once - a 1980s spelling dictionary for a word processor, where being able to encode an entire word in the smallest possible number of five-bit codes was *much* more important than being able to read the list backwards. (I think we ended up with less than 3 bytes per word for an English dictionary?)

I'm slightly surprised that it's thought to matter with this century's disk prices however.

The index structure Firebird uses was designed in 1982 when disks were small and expensive.  Maybe decisions would be different if done today.  However, small stored key sizes significantly increases the number of keys on a page, reducing I/O required to read an index.  Disk I/O speed has increased less than CPU speed, or memory and disk sizes, so that's still a good reason for prefix compression.

Prefix compression is not the reason that Firebird doesn't read indexes in both directions.  Full records are stored on on each page and at intervals on large pages, so with a little jittering back and forth, the compression can be done backward - less efficient than forward, but possible. 

A major goal for Firebird's indexes was to minimize index locking and allow pages to be added to and dropped from indexes without blocking index reads.  There's a long paper on the IBPhoenix web site that explains exactly how that works.  The summary is that during index modifications, the forward pointers between pages in an index are always correct, but the back pointers are not guaranteed.  It's a classic careful write problem - A points to C and C points to A and you want to stick B in between them.   You set up B correctly, so it's got a forward pointer to C and a backward pointer to A, then change A so it points forward to B rather than C.  Until you rewrite C so it points backward to B rather than A, a backward scan is going to miss B.

Good luck,

Ann