Lesson about index direction

Tim Ward wrote:

I've noted that the documentation says that whether your index is ASC or DESC matters, but it's not clear to me either why it should or exactly what the implications are.

Boiled down[#], I've got a table MYTABLE with an integer column MYCOLUMN with an index on it, and I'm looking at queries like

1. select COUNT(*) from MYTABLE where MYCOLUMN < 2
2. select COUNT(*) from MYTABLE where MYCOLUMN > 2

The vast majority of rows in the table have MYCOLUMN = 2, so I'm looking at these queries to return very small numbers very quickly. (MYCOLUMN = 2 means "this object is OK", and I'm looking to find the objects that are not OK.)

If the index is ASC then

1. is fast
2. is very slow (although it claims to be using the index, according to the plan, it's doing as much work as a table scan, according to the stats)

If the index is DESC then

1. is a bit slower but still fast
2. is fast.

Questions:

1. So it seems that if I want to do a ">" comparison in the WHERE clause I'm better off with a DESC index, but if I'm wanting to do a "<" comparison there isn't the same need to use an ASC index?
2. How does this indexing work anyway, that makes it sensitive to direction? - from other databases I'm sort-of vaguely used to the idea (without having got into the source code) that an index is a tree structure, and having walked down it to a particular node there's no different cost to going left (DESC) or right (ASC) from there?
3. The real cases are rather more complicated. I haven't actually re-run the experiments on this cut-down scenario so don't know for sure that it will behave in the same way. In particular the real index is on multiple columns, of which the last is the interesting one. Yes I know that multiple column indices aren't exactly encouraged in Firebird; at this stage I'm doing experiments, not writing production code.

Sean Leyne answers:

1. Correct!
2. Firebird is only able to walk indexes in one direction, due to prefix compression within the index structures, which is why ASC/DESC matters.
3. That is not completely true. There are plenty of cases where multi-column indexes are an excellent solution, much better than depending on the use of separate single column indexes. It really depends on your data usage/access modalities.

Tim Ward's reply:

...prefix compression... 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.

Ann W. Harrison answers:

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.

Mark Rotteveel asks:

I wonder though, when you are following the back pointers couldn't this be solved by checking the forward pointer from the 'current' page to see if it points back to your 'previous' page? And when it doesn't, you follow the forward pointers back to your 'previous' page adding those pages to a stack, and when you reach the 'previous' page then you process the page pages from the stack and start reading again from the 'current' page?

Ann W. Harrison answers:

To avoid internal deadlocks, Firebird allows each connection only one hard page lock at a time. Other locks are just bookkeeping so the engine can figure out who has a page in cache and whether the page is dirty. When someone else wants a page that's in your cache, the engine writes the page (if it's dirty and Classic) and releases the lock. When you reference the page again, Firebird reads it in (in Classic) or gives you a reference to the new version of the page (in SS). So there's no guarantee that the page that was the prior is still the prior.

In a contentious environment, pages change amazingly quickly. Vlad Khorsun solved a very mysterious problem that showed up as a wrong page type when looking for an item in an index. As it happens, there are actually three pointers to each page in the index, left, right, and parent. Sometimes a page would be removed from an index and reallocated to some other use (generally a data page) between the time the parent pointer was read and the page it pointed to was read.

Stacking page numbers really doesn't work. You have to come down from the top again. And yes, if you do the "I went from C to A, does A point forward to C?" check and start from the top again every time it fails, you could read the index backward. That's code that's never been written.