optoverview.tcl

sqlite-3.4.1,嵌入式数据库.是一个功能强大的开源数据库,给学习和研发以及小型公司的发展带来了全所未有的好处.

#
# Run this TCL script to generate HTML for the goals.html file.
#
set rcsid {$Id: optoverview.tcl,v 1.5 2005/11/24 13:15:34 drh Exp $}
source common.tcl
header {The SQLite Query Optimizer Overview}

proc CODE {text} {
  puts "<blockquote><pre>"
  puts $text
  puts "</pre></blockquote>"
}
proc SYNTAX {text} {
  puts "<blockquote><pre>"
  set t2 [string map {& &amp; < &lt; > &gt;} $text]
  regsub -all "/(\[^\n/\]+)/" $t2 {</b><i>\1</i><b>} t3
  puts "<b>$t3</b>"
  puts "</pre></blockquote>"
}
proc IMAGE {name {caption {}}} {
  puts "<center><img src=\"$name\">"
  if {$caption!=""} {
    puts "<br>$caption"
  }
  puts "</center>"
}
proc PARAGRAPH {text} {
  # regsub -all "/(\[a-zA-Z0-9\]+)/" $text {<i>\1</i>} t2
  regsub -all "\\*(\[^\n*\]+)\\*" $text {<tt><b><big>\1</big></b></tt>} t3
  puts "<p>$t3</p>\n"
}
set level(0) 0
set level(1) 0
proc HEADING {n name {tag {}}} {
  if {$tag!=""} {
    puts "<a name=\"$tag\">"
  }
  global level
  incr level($n)
  for {set i [expr {$n+1}]} {$i<10} {incr i} {
    set level($i) 0
  }
  if {$n==0} {
    set num {}
  } elseif {$n==1} {
    set num $level(1).0
  } else {
    set num $level(1)
    for {set i 2} {$i<=$n} {incr i} {
      append num .$level($i)
    }
  }
  incr n 1
  puts "<h$n>$num $name</h$n>"
}

HEADING 0 {The SQLite Query Optimizer Overview}

PARAGRAPH {
  This document provides a terse overview of how the query optimizer
  for SQLite works.  This is not a tutorial.  The reader is likely to
  need some prior knowledge of how database engines operate 
  in order to fully understand this text.
}

HEADING 1 {WHERE clause analysis} where_clause

PARAGRAPH {
  The WHERE clause on a query is broken up into "terms" where each term
  is separated from the others by an AND operator.
}
PARAGRAPH {
  All terms of the WHERE clause are analyzed to see if they can be
  satisfied using indices.
  Terms that cannot be satisfied through the use of indices become
  tests that are evaluated against each row of the relevant input
  tables.  No tests are done for terms that are completely satisfied by
  indices.  Sometimes
  one or more terms will provide hints to indices but still must be
  evaluated against each row of the input tables.
}

PARAGRAPH {
  The analysis of a term might cause new "virtual" terms to
  be added to the WHERE clause.  Virtual terms can be used with
  indices to restrict a search.  But virtual terms never generate code
  that is tested against input rows.
}

PARAGRAPH {
  To be usable by an index a term must be of one of the following
  forms:
}
SYNTAX {
  /column/ = /expression/
  /column/ > /expression/
  /column/ >= /expression/
  /column/ < /expression/
  /column/ <= /expression/
  /expression/ = /column/
  /expression/ > /column/
  /expression/ >= /column/
  /expression/ < /column/
  /expression/ <= /column/
  /column/ IN (/expression-list/)
  /column/ IN (/subquery/)
}
PARAGRAPH {
  If an index is created using a statement like this:
}
CODE {
  CREATE INDEX idx_ex1 ON ex1(a,b,c,d,e,...,y,z);
}
PARAGRAPH {
  Then the index might be used if the initial columns of the index
  (columns a, b, and so forth) appear in WHERE clause terms.
  All index columns must be used with
  the *=* or *IN* operators except for
  the right-most column which can use inequalities.  For the right-most
  column of an index that is used, there can be up to two inequalities
  that must sandwich the allowed values of the column between two extremes.
}
PARAGRAPH {
  It is not necessary for every column of an index to appear in a
  WHERE clause term in order for that index to be used. 
  But there can not be gaps in the columns of the index that are used.
  Thus for the example index above, if there is no WHERE clause term
  that constraints column c, then terms that constraint columns a and b can
  be used with the index but not terms that constraint columns d through z.
  Similarly, no index column will be used (for indexing purposes)
  that is to the right of a 
  column that is constrained only by inequalities.
  For the index above and WHERE clause like this:
}
CODE {
  ... WHERE a=5 AND b IN (1,2,3) AND c>12 AND d='hello'
}
PARAGRAPH {
  Only columns a, b, and c of the index would be usable.  The d column
  would not be usable because it occurs to the right of c and c is
  constrained only by inequalities.
}

HEADING 1 {The BETWEEN optimization} between_opt

PARAGRAPH {
  If a term of the WHERE clause is of the following form:
}
SYNTAX {
  /expr1/ BETWEEN /expr2/ AND /expr3/
}
PARAGRAPH {
  Then two virtual terms are added as follows:
}
SYNTAX {
  /expr1/ >= /expr2/ AND /expr1/ <= /expr3/
}
PARAGRAPH {
  If both virtual terms end up being used as constraints on an index,
  then the original BETWEEN term is omitted and the corresponding test
  is not performed on input rows.
  Thus if the BETWEEN term ends up being used as an index constraint
  no tests are ever performed on that term.
  On the other hand, the
  virtual terms themselves never causes tests to be performed on
  input rows.
  Thus if the BETWEEN term is not used as an index constraint and
  instead must be used to test input rows, the <i>expr1</i> expression is
  only evaluated once.
}

HEADING 1 {The OR optimization} or_opt

PARAGRAPH {
  If a term consists of multiple subterms containing a common column
  name and separated by OR, like this:
}
SYNTAX {
  /column/ = /expr1/ OR /column/ = /expr2/ OR /column/ = /expr3/ OR ...
}
PARAGRAPH {
  Then the term is rewritten as follows:
}
SYNTAX {
  /column/ IN (/expr1/,/expr2/,/expr3/,/expr4/,...)
}
PARAGRAPH {
  The rewritten term then might go on to constraint an index using the
  normal rules for *IN* operators.
  Note that <i>column</i> must be the same column in every OR-connected subterm,
  although the column can occur on either the left or the right side of
  the *=* operator.
}

HEADING 1 {The LIKE optimization} like_opt

PARAGRAPH {
  Terms that are composed of the LIKE or GLOB operator
  can sometimes be used to constrain indices.
  There are many conditions on this use:
}
PARAGRAPH {
  <ol>
  <li>The left-hand side of the LIKE or GLOB operator must be the name
      of an indexed column.</li>
  <li>The right-hand side of the LIKE or GLOB must be a string literal
      that does not begin with a wildcard character.</li>
  <li>The ESCAPE clause cannot appear on the LIKE operator.</li>
  <li>The build-in functions used to implement LIKE and GLOB must not
      have been overloaded using the sqlite3_create_function() API.</li>
  <li>For the GLOB operator, the column must use the default BINARY
      collating sequence.</li>
  <li>For the LIKE operator, if case_sensitive_like mode is enabled then
      the column must use the default BINARY collating sequence, or if
      case_sensitive_like mode is disabled then the column must use the
      built-in NOCASE collating sequence.</li>
  </ol>
}
PARAGRAPH {
  The LIKE operator has two modes that can be set by a pragma.  The
  default mode is for LIKE comparisons to be insensitive to differences
  of case for latin1 characters.  Thus, by default, the following
  expression is true:
}
CODE {
  'a' LIKE 'A'
}
PARAGRAPH {
  By turned on the case_sensitive_like pragma as follows:
}
CODE {
  PRAGMA case_sensitive_like=ON;
}
PARAGRAPH {
  Then the LIKE operator pays attention to case and the example above would
  evaluate to false.  Note that case insensitivity only applies to
  latin1 characters - basically the upper and lower case letters of English
  in the lower 127 byte codes of ASCII.  International character sets
  are case sensitive in SQLite unless a user-supplied collating
  sequence is used.  But if you employ a user-supplied collating sequence,
  the LIKE optimization describe here will never be taken.
}
PARAGRAPH {
  The LIKE operator is case insensitive by default because this is what
  the SQL standard requires.  You can change the default behavior at
  compile time by using the -DSQLITE_CASE_SENSITIVE_LIKE command-line option
  to the compiler.
}
PARAGRAPH {
  The LIKE optimization might occur if the column named on the left of the
  operator uses the BINARY collating sequence (which is the default) and
  case_sensitive_like is turned on.  Or the optimization might occur if
  the column uses the built-in NOCASE collating sequence and the 
  case_sensitive_like mode is off.  These are the only two combinations
  under which LIKE operators will be optimized.  If the column on the
  right-hand side of the LIKE operator uses any collating sequence other
  than the built-in BINARY and NOCASE collating sequences, then no optimizations
  will ever be attempted on the LIKE operator.
}