O'Reilly logo

The Art of SQL by Peter Robson, Stephane Faroult

Stay ahead with the world's most comprehensive technology and business learning platform.

With Safari, you learn the way you learn best. Get unlimited access to videos, live online training, learning paths, books, tutorials, and more.

Start Free Trial

No credit card required

Indexes with Functions and Conversions

Indexes are usually implemented as tree structures—mostly complex trees—to avoid a fast decay of indexes on heavily inserted, updated, and deleted tables. To find the physical location of a row, the address of which is stored in the index, one must compare the key value to the value stored in the current node of the tree to be able to determine which sub-tree must be recursively searched. Let's now suppose that the value that drives our search doesn't exactly match an actual column value but can be compared to the result of a function f( ) applied to the column value. In that case we may be tempted to express a condition as follows:

    where f(indexed_column) = 'some value'

This kind of condition will typically torpedo the index, making it useless. The problem is that nothing guarantees that the function f( ) will keep the same order as the index data; in fact, in most cases it will not. For instance, let's suppose that our tree-index looks like Figure 3-6.

A simplistic representation of how names might be stored in an index

Figure 3-6. A simplistic representation of how names might be stored in an index

(If the names look familiar, it is because they are those of some of Napoleon's marshals.) Figure 3-6 is of course an outrageously simplified representation, just for the purpose of explaining a particular point; the actual indexes do not look exactly like the binary tree shown in Figure 3-6. If we look ...

With Safari, you learn the way you learn best. Get unlimited access to videos, live online training, learning paths, books, interactive tutorials, and more.

Start Free Trial

No credit card required