Subject Re: Performance of Firebird vs. other DBMS
Author johnson_dave2003
--- In, "laurenz_brein"
<laurenz_brein@y...> wrote:
> --- In, David Johnson wrote:
> >> The article did not make it clear to me why a SELECT MAX() could
> >> not profit from an ascending index.
> >
> > An ascending index would have to be traversed backwards to get a
> > max. Firebird opted for unidirectional indexes (like DB2, which
is a
> > locking database).
> Please bear with me, I still fail to grasp it.
> Why is it so much more expensive to get that last entry (or last
> couple of entries) from a B*-Tree than it is to get the first entry?
> Laurenz Albe

When looking for max on an ascending _unidirectional_ index, since
you do not know which of the rows are visible, you must effectively
do a table space scan to find the guaranteed max. Your most likely
candidate is the last row that you hit. Since you must hit the row
itself, not only the index entry, your I/O is enormously multiplied
because you must hit every row, keeping a reference to the last row
that met the criterion. Assuming an average sized table with
1,000,000 rows, you are talking about (index page count) +
(1,000,000) I/O's to identify the max against an ascending index.

Using a descending index means that the most likely candidate is the
your first candidate you hit. If the candidate is not visible you
just move to the next entry. You are typically talking about 2 I/O's
(1 index + 1 data) to identify the max row in a descending index.

This is magnified in the generational architecture, but also true for
locking architecture such as DB2.