DB2/UDB B-Tree Indexing, Reverse Scans

[Zri Man]

I'm relatively new to DB2 and was reasonably amused to see the REVERSE
SCAN availability for Indexes.

My assumptions are as follows:

DB2/UDB uses B-Tree for indexing by default and is likely the main
offering for Indexing within the DB.

Reverse Scans could possibly only happen on the the leaf node of
the index

Now if these assumptions are indeed true:

I wonder how does the algorithm for a Reverse Scan work. I thought
at the level of the Leaf Node a scan of every entry is made.

And if that is so, how will a Reverse Scan Help is one question.

The other is, what predicates the optimizer, query plan to do a
reverse scan, what sets this bias?

It does not make sense to me to have a reverse scan.

Thanks,

Zridhar

[AK]

ALLOW REVERSE SCANS is not an algorythm, it's an option to choose when
builing indexes.
if an index is built without REVERSE SCAN option, it can be scanned in
one direction only. The simplest example is
SELECT MIN(X) FROM SOME_TABLE
returns right away, reading from the root to the first leaf page

SELECT MAX(X) FROM SOME_TABLE
returns in a while, reading from the root to the first leaf page, then
scanning all the leaf pages

[Zri Man]

I don't think can be a reverse scan at the root or non-leaf node pages
of an index.

And I think I'm right when I say that its an Algorithm that is behind a
Reverse Scan, I do know its an option when Building an index.

The question is what it gives the user.

I'm not sure how MIN and MAX can be helped by this at all.

As I said, I do not understand, given the organization of a B-Tree, how
there can be a Reverse Scan or for that matter a predicated Bias to the
Scan of an B-Tree Index.

[m0002a]

In DB2, allowing reverse scans will speed up some queries with and
order by decending sequence, where DB2 can use the index instead of
actually performed a sort of the rows.

Allow reverse scan also speeds up the MAX funciton, if the column in
the MAX is an indexed column.

[Serge Rielau]

m0****@yahoo.com wrote:

In DB2, allowing reverse scans will speed up some queries with and
order by decending sequence, where DB2 can use the index instead of
actually performed a sort of the rows.

Allow reverse scan also speeds up the MAX funciton, if the column in
the MAX is an indexed column.

Or encourage a merge-join if the other join partner is already sorted
that way.

To get back to the algorithm:
If you create an index i1 on T(c1 asc, c2 desc)
The leaf pages are pointered so DB2 can easily travers from one to teh
next without having to walk back you the index tree.
When allowing reverse scans there simply is a reverse pointer for each
forward pointer, so the index will be slightly bigger.

When the optimizer "asks" for a an order (c1 desc, c2 asc) the answer
will be that i1 provides this order. There really isn't much in the
sense of magic....

Cheers
Serge
--
Serge Rielau
DB2 SQL Compiler Development
IBM Toronto Lab

[Knut Stolze]

Zri Man wrote:

I don't think can be a reverse scan at the root or non-leaf node pages
of an index.

And I think I'm right when I say that its an Algorithm that is behind a
Reverse Scan, I do know its an option when Building an index.

The question is what it gives the user.

I'm not sure how MIN and MAX can be helped by this at all.

As I said, I do not understand, given the organization of a B-Tree, how
there can be a Reverse Scan or for that matter a predicated Bias to the
Scan of an B-Tree Index.

First, I don't know exactly if DB2 works that way...

A B-Tree - as it was invented by Rudolf Bayer in the early 70s - has only
pointers/references from a parent node to its sons (and maybe even the
backwards direction). In particular, there is no pointer/reference from
one leaf node to the next/previous one.

I'd say that DB2 implements per default a "next" pointer on the leaf nodes.
Those pointers allow a sequential scan of the leaf nodes in the sort order
of the index. Also, the pointers can be maintained during a split
operation without any additional I/O.

But note that you cannot do a reverse scan on the leaf nodes because you
don't know the predecessor of any given leaf - there are no "prev"
pointers. That is what ALLOW REVERSE SCAN adds. You do have now a
doubled-linked list at the leaf level, and you can perform index scans in
ascending and descending order. Besides the few bytes overhead for the
pointer (which is negligible), you will have to maintain the linked list
all the time, and that means you have 1 additional I/O operation because
the "prev" pointer of the successor page of the page being split has to be
corrected.

I don't know right now if there are other considerations when choosing
reverse scans. Have a look at the manual.

--
Knut Stolze
Information Integration Development
IBM Germany / University of Jena

[Zri Man]

Stolze,

Thanks for your detailed message, as also to the other contributors.

I guess its safe to assume that the elements of the sorted linked
list at the leaf node level will be scanned only when a query requires
sorted data, that is MIN or MAX and I guess the Reverse Scan is
svailable at the level to point either way.

Zridhar