## Run this TCL script to generate HTML for the goals.html file.#set rcsid {$Id: optimizer.tcl,v 1.1 2005/08/30 22:44:06 drh Exp $}source common.tclheader {The SQLite Query Optimizer}proc CODE {text} {  puts "<blockquote><pre>"  puts $text  puts "</pre></blockquote>"}proc IMAGE {name {caption {}}} {  puts "<center><img src=\"$name\">"  if {$caption!=""} {    puts "<br>$caption"  }  puts "</center>"}proc PARAGRAPH {text} {  puts "<p>$text</p>\n"}proc HEADING {level name} {  puts "<h$level>$name</h$level>"}HEADING 1 {The SQLite Query Optimizer}PARAGRAPH {  This article describes how the SQLite query optimizer works.  This is not something you have to know in order to use SQLite - many  programmers use SQLite successfully without the slightest hint of what  goes on in the inside.  But a basic understanding of what SQLite is doing  behind the scenes will help you to write more efficient SQL.  And the  knowledge gained by studying the SQLite query optimizer has broad  application since most other relational database engines operate   similarly.  A solid understanding of how the query optimizer works is also  required before making meaningful changes or additions to the SQLite, so   this article should be read closely by anyone aspiring  to hack the source code.}HEADING 2 BackgroundPARAGRAPH {  It is important to understand that SQL is a programming language.  SQL is a perculiar programming language in that it  describes <u>what</u> the programmer wants to compute not <u>how</u>  to compute it as most other programming languages do.  But perculiar or not, SQL is still just a programming language.}PARAGRAPH {  It is very helpful to think of each SQL statement as a separate  program.  An important job of the SQL database engine is to translate each  SQL statement from its descriptive form that specifies what the  information is desired (the <u>what</u>)   into a procedural form that specifies how to go  about acquiring the desired information (the <u>how</u>).  The task of translating the <u>what</u> into a   <u>how</u> is assigned to the query optimizer.}PARAGRAPH {  The beauty of SQL comes from the fact that the optimizer frees the programmer  from having to worry over the details of <u>how</u>.  The programmer  only has to specify the <u>what</u> and then leave the optimizer  to deal with all of the minutae of implementing the  <u>how</u>.  Thus the programmer is able to think and work at a  much higher level and leave the optimizer to stress over the low-level  work.}HEADING 2 {Database Layout}PARAGRAPH {  An SQLite database consists of one or more "b-trees".  Each b-tree contains zero or more "rows".   A single row contains a "key" and some "data".  In general, both the key and the data are arbitrary binary  data of any length.  The keys must all be unique within a single b-tree.  Rows are stored in order of increasing key values - each  b-tree has a comparision functions for keys that determines  this order.}PARAGRAPH {  In SQLite, each SQL table is stored as a b-tree where the  key is a 64-bit integer and the data is the content of the  table row.  The 64-bit integer key is the ROWID.  And, of course,  if the table has an INTEGER PRIMARY KEY, then that integer is just  an alias for the ROWID.}PARAGRAPH {  Consider the following block of SQL code:}CODE {  CREATE TABLE ex1(     id INTEGER PRIMARY KEY,     x  VARCHAR(30),     y  INTEGER  );  INSERT INTO ex1 VALUES(NULL,'abc',12345);  INSERT INTO ex1 VALUES(NULL,456,'def');  INSERT INTO ex1 VALUES(100,'hello','world');  INSERT INTO ex1 VALUES(-5,'abc','xyz');  INSERT INTO ex1 VALUES(54321,NULL,987);}PARAGRAPH {  This code generates a new b-tree (named "ex1") containing 5 rows.  This table can be visualized as follows:}IMAGE table-ex1b2.gifPARAGRAPH {  Note that the key for each row if the b-tree is the INTEGER PRIMARY KEY  for that row.  (Remember that the INTEGER PRIMARY KEY is just an alias  for the ROWID.)  The other fields of the table form the data for each  entry in the b-tree.  Note also that the b-tree entries are in ROWID order  which is different from the order that they were originally inserted.}PARAGRAPH {  Now consider the following SQL query:}CODE {  SELECT y FROM ex1 WHERE x=456;}PARAGRAPH {  When the SQLite parser and query optimizer are handed this query, they  have to translate it into a procedure that will find the desired result.  In this case, they do what is call a "full table scan".  They start  at the beginning of the b-tree that contains the table and visit each  row.  Within each row, the value of the "x" column is tested and when it  is found to match 456, the value of the "y" column is output.  We can represent this procedure graphically as follows:}IMAGE fullscanb.gifPARAGRAPH {  A full table scan is the access method of last resort.  It will always  work.  But if the table contains millions of rows and you are only looking  a single one, it might take a very long time to find the particular row  you are interested in.  In particular, the time needed to access a single row of the table is  proportional to the total number of rows in the table.  So a big part of the job of the optimizer is to try to find ways to   satisfy the query without doing a full table scan.}PARAGRAPH {  The usual way to avoid doing a full table scan is use a binary search  to find the particular row or rows of interest in the table.  Consider the next query which searches on rowid instead of x:}CODE {  SELECT y FROM ex1 WHERE rowid=2;}PARAGRAPH {  In the previous query, we could not use a binary search for x because  the values of x were not ordered.  But the rowid values are ordered.  So instead of having to visit every row of the b-tree looking for one  that has a rowid value of 2, we can do a binary search for that particular  row and output its corresponding y value.  We show this graphically  as follows:}IMAGE direct1b.gifPARAGRAPH {  When doing a binary search, we only have to look at a number of  rows with is proportional to the logorithm of the number of entries  in the table.  For a table with just 5 entires as in the example above,  the difference between a full table scan and a binary search is  negligible.  In fact, the full table scan might be faster.  But in  a database that has 5 million rows, a binary search will be able to  find the desired row in only about 23 tries, whereas the full table  scan will need to look at all 5 million rows.  So the binary search  is about 200,000 times faster in that case.}PARAGRAPH {  A 200,000-fold speed improvement is huge.  So we always want to do  a binary search rather than a full table scan when we can.}PARAGRAPH {  The problem with a binary search is that the it only works if the  fields you are search for are in sorted order.  So we can do a binary  search when looking up the rowid because the rows of the table are  sorted by rowid.  But we cannot use a binary search when looking up  x because the values in the x column are in no particular order.}PARAGRAPH {  The way to work around this problem and to permit binary searching on  fields like x is to provide an index.  An index is another b-tree.  But in the index b-tree the key is not the rowid but rather the field  or fields being indexed followed by the rowid.  The data in an index b-tree is empty - it is not needed or used.  The following diagram shows an index on the x field of our example table:}IMAGE index-ex1-x-b.gifPARAGRAPH {  An important point to note in the index are that they keys of the  b-tree are in sorted order.  (Recall that NULL values in SQLite sort  first, followed by numeric values in numerical order, then strings, and  finally BLOBs.)  This is the property that will allow use to do a  binary search for the field x.  The rowid is also included in every  key for two reasons.  First, by including the rowid we guarantee that  every key will be unique.  And second, the rowid will be used to look  up the actual table entry after doing the binary search.  Finally, note  that the data portion of the index b-tree serves no purpose and is thus  kept empty to save space in the disk file.}PARAGRAPH {  Remember what the original query example looked like:}CODE {  SELECT y FROM ex1 WHERE x=456;}PARAGRAPH {  The first time this query was encountered we had to do a full table  scan.  But now that we have an index on x, we can do a binary search  on that index for the entry where x==456.  Then from that entry we  can find the rowid value and use the rowid to look up the corresponding  entry in the original table.  From the entry in the original table,  we can find the value y and return it as our result.  The following  diagram shows this process graphically:}IMAGE indirect1b1.gifPARAGRAPH {  With the index, we are able to look up an entry based on the value of  x after visiting only a logorithmic number of b-tree entries.  Unlike  the case where we were searching using rowid, we have to do two binary  searches for each output row.  But for a 5-million row table, that is  still only 46 searches instead of 5 million for a 100,000-fold speedup.}HEADING 3 {Parsing The WHERE Clause}# parsing the where clause# rowid lookup# index lookup# index lookup without the table# how an index is chosen# joins# join reordering# order by using an index# group by using an index# OR -> IN optimization# Bitmap indices# LIKE and GLOB optimization# subquery flattening# MIN and MAX optimizations