hd_keywords {indexing} {indexing tutorial} proc figure {fignum tag img title} { hd_puts "

\n" hd_puts "\"figure
\n" hd_puts "Figure $fignum: $title\n" hd_puts "

\n" } proc code {txt} { hd_puts "
\n"
  regsub {^[ \n]*\n} $txt {} txt
  hd_puts [string trimright $txt]\n
  hd_puts "
\n" }

How Indexing Works

The best feature of SQL (in all its implementations, not just SQLite) is that it is a declarative language, not a procedural language. In other words, with SQL you tell the system what you want to compute, not how to compute it. The task of figuring out the how is delegated to the query optimizer or query planner subsystem within the SQL database engine, significantly reducing the workload on the programmer and the opportunity for the programmer to make mistakes.

Most of the time, the query planner does a good job without any help and the programmer does not have to think about it. However, the query planner needs indices to work with and it usually falls to the programmer to add indices to the schema that are sufficient for the query planner to accomplish its task.

This document is intended to provide programmers who are new to SQL and database with the background information needed to help them determine the best indices for use on their project.

1.0 Querying

1.1 Tables Without Indices

Every table in SQLite consists of zero or more rows with a unique integer key (the [rowid] or [INTEGER PRIMARY KEY]) followed by content. The rows are logically stored in order of increasing rowid. As an example, this note uses a table named "tab" which relates various fruits to the state where it is grown and its unit price. The schema is this:

code { CREATE TABLE tab( Fruit TEXT, State TEXT, Price REAL ); }

With some (arbitrary) data, such a table might be logically stored on disk as shown in figure 1:

figure 1 #fig1 tab.gif {Logical Layout Of Table "Tab"}

Key features to notice about this example are that the rows are sorted by rowid and that the order of the content is arbitrary.

Now suppose you want to look up the price of peaches. The query would be as follows:

code { SELECT price FROM tab WHERE fruit='Peach'; }

In order to satisfy this query, SQLite has to read every row out of the table, check to see if the "fruit" column has the value of "Peach" and if so, output the "price" column from that row. The process is illustrated by figure 2 below. This is called a full table scan since the entire content of the table must be read and examined in order to find the one row of interest. With a table of only 7 rows, this is not a big deal, but if your table contained 7 million rows, a full table scan might read megabytes of content in order to find a single 8-byte number. For that reason, one normally tries to avoid full table scans.

figure 2 #fig2 fullscan.gif {Full Table Scan}

1.2 Lookup By Rowid

One technique for avoiding a full table scan is to do lookups by rowid (or by the equivalent INTEGER PRIMARY KEY). To lookup the prices of peaches, one would query for the entry with a rowid of 4:

code { SELECT price FROM tab WHERE rowid=4; }

Since the information is stored in the table in rowid order, SQLite can find the correct row using doing a binary search on the rowid. If the table contains N element, the time required to look up the desired row is proportional to logN rather than being proportional to N as in a full table scan. If the table contains 10 million elements, that means the query will be on the order of N/logN or about 1 million times faster!

figure 3 #fig3 rowidlu.gif {Lookup By Rowid}

1.3 Lookup By Index

The problem with looking up information by rowid is that you probably do not care what the price of "item 4" is - you want to know the price of peaches. And so a rowid lookup is often not an option.

To make the original query more effcient, we can add an index on the "fruit" column of the "tab" table like this:

code { CREATE INDEX idx1 ON tab(fruit); }

An index is another table similar to the original "tab" table but with the content (the fruit column in this case) stored in front of the rowid and with all rows in content order. Figure 4 gives a logical view of the Idx1 index. The "fruit" column is the primary key used to order the elements of the table and the "rowid" is the secondary key used to break the tie when two or more rows have the same "fruit". In the example, the rowid has to be used as a tie-breaker for the "Orange" rows. Notice that since the rowid is always unique over all elements of the original table, the composite key of "fruit" followed by "rowid" will be unique over all elements of the index.

figure 4 #fig4 idx1.gif {An Index On The Fruit Column}

With the new index in place, we can devise an alternative plan for the original "Price of Peaches" query.

code { SELECT price FROM tab WHERE fruit='Peach'; }

The query starts by doing a binary search on the Idx1 index for entries that have fruit='Peach'. SQLite can do this binary search on the Idx1 index but not on the original Tab table because the rows in Idx1 are sorted by the "fruit" column. Having found a row in the Idx1 index that has fruit='Peach', the database engine can extract the rowid for that row, then do a separate binary search on the original Tab table to find the original row that contains fruit='Peach'. From the row in the Tab table, SQLite can extract the value of the price column. This procedure is illustrated by figure 5.

figure 5 #fig5 idx1lu1.gif {Indexed Lookup For The Price Of Peaches}

SQLite has to do two binary searches to find the price of peaches using the method show above. But for a table with a large number of rows, this is still much faster than doing a full table scan.

1.4 Multiple Result Rows

In the previous query the fruit='Peach' constraint narrowed the result down to a single row. But the same technique works even if multiple rows are obtained. Suppose we looked up the price of Oranges instead Peaches:

code {SELECT price FROM tab WHERE fruit='Orange'} figure 6 #fig6 idx1lu2.gif {Indexed Lookup For The Price Of Oranges}

In this case, SQLite still does a single binary search to find the first entry of the index where fruit='Orange'. Then it extracts the rowid from the index and uses that rowid to lookup the original table entry via binary search and output the price from the original table. But instead of quiting, the database engine then advances to the next row of index to repeat the process for next fruit='Orange' entry. Advancing to the next row of an index (or table) is much less costly than doing a binary search since the next row is often located on the same database page as the current row. In fact, the cost of advancing to the next row is so cheap in comparison to a binary search that we usually ignore it. So our estimate for the total cost of this query is 3 binary searchs. If the number of rows of output is K and the number of rows in the table is N, then in general the cost of doing the query proportional to (K+1)*logN.

1.5 Multiple AND-Connected WHERE-Clause Terms

Next, suppose that you want to look up the price of not just any orange, but specifically California-grown oranges. The appropriate query would be as follows:

code {SELECT price FROM tab WHERE fruit='Orange' AND state='CA'} figure 7 #fig7 idx1lu3.gif {Indexed Lookup Of California Oranges}

One approach to this query is to use the fruit='Orange' term of the WHERE clause to find all rows dealing with oranges, then filter those rows by rejecting any that are from states other than California. This process is shows by figure 7 above. This is a perfectly reasonable approach in most cases. Yes, the database engine did have to do an extra binary search for the Florida orange row that was later rejected, so it was not as efficient as we might hope, though for many applications it is efficient enough.

Suppose that in addition to the index on "fruit" there was also an index on "state".

code {CREATE INDEX Idx2 ON tab(state);} figure 8 #fig8 idx2.gif {Index On The State Column}

The "state" index works just like the "fruit" index in that it is a new table with an extra column in front of the rowid and sorted by that extra column as the primary key. The only difference is that in Idx2, the first column is "state" instead of "fruit" as it is with Idx1. In our example data set, the is more redundancy in the "state" column and so they are more duplicate entries. The ties are still resolved using the rowid.

Using the new Idx2 index on "state", SQLite has another option for lookup up the price of California oranges: it can look up every row that contains fruit from California and filter out those rows that are not oranges.

figure 9 #fig9 idx2lu1.gif {Indexed Lookup Of California Oranges}

Using Idx2 instead of Idx1 causes SQLite to examine a different set of rows, but it gets the same answer in the end (which is very important - remember that indices should never change the answer, only cause us to get to the answer more quickly) and it does the same amount of work. So the Idx2 index did not help performance in this case.

1.6 Multi-Column Indices

To get the maximum performance out of a query with multiple AND-connected terms in the WHERE clause, you really want a multi-column index with columns for each of the AND terms. In this case we create a new index on the "fruit" and "state" columns of Tab1:

code {CREATE INDEX Idx3 ON Tab(fruit, state);} figure 1 #fig10 idx3.gif {A Two-Column Index}

A multi-column index follows the same pattern as a single-column index; the indexed columns are added in front of the rowid. The only difference is that now multiple columns are added. The left-most column is the primary key used for ordering the rows in the index. The second column is used to break ties in the left-most column. If there were a third column, it would be used to break ties for the first to columns. And so forth for as many columns as their are in the index. Because rowid is guaranteed to be unique, every row of the index will be unique even if all of the content columns for two rows are the same. That case does not happen in our sample data, but there is one case (fruit='Orange') where there is a tie on the first column which must be broken by the second column.

Given the new multi-column Idx3 index, it is now possible for SQLite to find the price of California oranges using only 2 binary searches:

code {SELECT price FROM tab WHERE fruit='Orange' AND state='CA'} figure 11 #fig11 idx3lu1.gif {Lookup Using A Two-Column Index}

With the Idx3 index on both columns that are constrained by the WHERE clause, SQLite can do a single binary search against Idx3 to find the one rowid for California oranges, then do a single binary search to find the price for that item in the original table. There are no dead-ends and no wasted binary searches. This is a more efficient query.

Note that Idx3 contains all the same information as the original Idx1. And so if we have Idx3, we do not really need Idx1 any more. The "price of peaches" query can be satisfied using Idx3 by simply ignoring the "state" column of Idx3:

code {SELECT price FROM tab WHERE fruit='Peach'} figure 12 #fig12 idx3lu2.gif {Single-Column Lookup On A Multi-Column Index}

Hence, a good rule of thumb is that your database schema should never contain two indices where one index is a prefix of the other. Drop the index with fewer columns. SQLite will still be able to do efficient lookups with the longer index.

1.7 Covering Indices

The "price of California oranges" query was made more efficient through the use of a two-column index. But SQLite can do even better with a three-column index that also includes the "price" column:

code {CREATE INDEX Idx4 ON Tab(fruit, state, price);} figure 13 #fig13 idx4.gif {A Covering Index}

This new index contains all the columns of the original Tab table that are used by the query - both the search terms and the output. We call this a "covering index". Because all of the information needed is in the covering index, SQLite never needs to consult the original table in order to find the price.

code {SELECT price FROM tab WHERE fruit='Orange' AND state='CA';} figure 14 #fig14 idx4lu1.gif {Query Using A Covering Index}

Hence, by adding extra "output" columns onto the end of an index, one can avoid having to reference the original table and thereby cut the number of binary search for a query in half. This is a constant-factor improvement in performance (roughly a doubling of the speed). But on the other hand, it is also just a refinement; A two-fold performance increase is not nearly as dramatic as the one-millon-fold increase seen when the table was first indexed. And for most queries, the difference between 1 microsecond and 2 microseconds is unlikely to be noticed.

1.8 OR-Connected Terms In The WHERE Clause

Multi-column indices only work if the constraint terms in the WHERE clause of the query are connected by AND. So Idx3 and Idx4 are helpful when the search is for items that are both Oranges and grown in California, but neither index would be that useful if we wanted all items that were either oranges or are grown in California.

code { SELECT price FROM Tab1 WHERE fruit='Orange' OR state='CA'; }

When confronted with OR-connected terms in a WHERE clause, SQLite examines each OR term separately and tries to use an index to find the rowids associated with each term. It then takes the union of the resulting rowid sets to find the end result. The following figure illustrates this process:

figure 15 #fig15 orquery.gif {Query With OR Constraints}

The diagram above implies that SQLite computes all of the rowids first and then combines them with a union operation before starting to do rowid lookups on the original table. In reality, the rowid lookups are interspersed with rowid computations. SQLite uses one index at a time to find rowids but it remembers which rowids it has seen before so as to avoid duplicates. But that is just an implementation detail. The diagram, while not 100% accurate, provides a good overview of what is happening.

TBD: (1) Complex subexpressions connected by OR. (2) What happens if any OR term is not indexable

2.0 Sorting

SQLite (and all other SQL database engines) can use indices to speed up sorting, to satisfy ORDER BY clauses in queries, in addition using them for queries.

When no appropriate indices are available, a query with an ORDER BY clause must be sorted as a separate step. Consider this query:

code {SELECT * FROM tab ORDER BY fruit;}

SQLite processes this by gather the output of partial query that omits the ORDER BY clause, then running the output through a sorter.

figure 16 #fig16 obfruitnoidx.gif {Sorting Without An Index}

If the number of output rows is K, then the time needed to sort is proportional to KlogK. If K is small, the sorting time is usually not a factor, but in a query such as the above where K==N, the time needed to sort can be much greater than the time needed to run the original query. Furthermore, the entire output set is accumulated in memory, which can mean that a lot of memory is required to complete the query.

2.1 Sorting By Rowid

Because sorting can be expensive, SQLite works hard to convert ORDER BY clauses into no-ops. If SQLite is able to determine that output will naturally appear in the order specified, then no sorting is done. So, for example, if you request the output in rowid order, no sorting will be done:

code {SELECT * FROM tab ORDER BY rowid;} figure 17 #fig17 obrowid.gif {Sorting By Rowid}

You can also request a reverse-order sort like this:

code {SELECT * FROM tab ORDER BY rowid DESC;}

SQLite will still omit the sorting step. But in order for output to appear in the correct order, SQLite will do the table scan starting at the end and working toward the beginning, rather than starting at the beginning and working toward the end as shown in figure 17.

2.2 Sorting By Index

Of course, ordering the output of a query by rowid is seldom useful. Usually one wants to order the output by some other column, and so the natural output order will not be helpful.

If an index is available on the ORDER BY column, that index can be used for sorting. Consider the request for all items sorted by "fruit":

code {SELECT * FROM tab ORDER BY fruit;}

If the Idx1 index is available, then it can be used to cause the output to appear in sorted order naturally. The algorithm would look something like this:

figure 18 #fig18 obfruitidx1.gif {Sorting With An Index}

The Idx1 index is scanned from top to bottom (or from bottom to top if "ORDER BY fruit DESC" is used) in order to find the rowids for each item in order by fruit. Then for each rowid, a binary search is done to lookup and output that row. In this way, the output appears in the requested order with the need to gather then entire output and sort it using a separate step.

But does this really save time? The number of steps in the original indexless sort is proportional to NlogN since that is how much time it takes to sort N rows. But when we use Idx1 as shown here, we have to do N rowid lookups which take logN time each, so the total time of NlogN is the same!

SQLite uses a cost-based query planner. When there are two or more ways of solving the same query, SQLite tries to estimate the total amount of time needed to run the query using each plan, and then uses the plan with the lowest estimated cost. A cost is computed mostly from the estimated time, and so this case could go either way depending on the table size and what WHERE clause constraints were available, and so forth. But generally speaking, the indexed sort would probably be select, if for no other reason, because it does not need to accumulate the entire result set in memory before sorting and thus uses a lot less memory.

2.3 Sorting By Covering Index

If a covering index can be used for a query, then the multiple rowid looks can be avoided and the cost of the query drops dramatically.

figure 19 #fig19 obfruitidx4.gif {Sorting With A Covering Index}

With a covering index, SQLite can simply walk the index from one end to the other and deliver the output in time proportional to N and without having allocate a large buffer to hold the result set.