Good explanation Alexander ... like I said, I still need to get into the code. But this technical detail explains why it may be a bit more difficult than I expected to resolve the minor (almost non) issue of count performance.

> I though that because FB indexes are compressed (RLE Encoded AFAIR) one
> could not traverse on the reverse way.

You never traverse indeces in reverse, even on systems where the indeces are not compressed. In a B+ tree, to find the last index you load the root page, traverse to the last entry, if it is a leaf node your return the record, if it is a branch node than you repeat the process on the indicated page.

Using 8k page size and 50 character more or less keys+pointers entries, you get roughly 160 index entries per page. The first two layers of the B+ tree can address 160^2 records if the indeces are full. A third layer addresses 4,096,000 records. A max operation against an ascending index on a 4,000,000 row table should only need to read three pages maximum. This is consistent with the results I achieved in the random read tests. Note that my primary key is quite large - using an integer key would result in even greater efficiency in indexing.

> if you have an index on column "name" the engine could just scan the index
> to find the data you want, and don't need to access each data-page.

Hmmm ... so Firebird does not support index-only scans. That is interesting and important to know. Index only scans can result in orders of improvement in performance in some queries. It does not impact my immediate project, but I have seen the addition of an index for the sole purpose of acquiring index only scans on other DBMS's improve performance of a complex operation from 30 minutes (after prepare) to 10 seconds (after prepare). The actual prepare took 10 minutes in both with and without the additional index, but using precompiled and static SQL it never impacted my users. It looks like I need to write a couple more tests. :o)

I also wonder how much compression is achieved on indeces. Larger and more complex indeces would benefit most from RLE encoding, but simpler indeces may not benefit at all. The benefit of more compact indeces translates to less I/O, at the expense of CPU cycles. I/O is still much more expensive (time wise) than CPU, so there may yet be performance benefit to compression.

I am looking forward to Firebird 2 also - from the chatter I have seen, it looks like it will implement many good featuires.



[Non-text portions of this message have been removed]