/ Hex Artifact Content
Login

Artifact 815df406a38c9f69b27d37e8f7ede004c6d9f19e:


0000: 23 0a 23 20 52 75 6e 20 74 68 69 73 20 54 43 4c  #.# Run this TCL
0010: 20 73 63 72 69 70 74 20 74 6f 20 67 65 6e 65 72   script to gener
0020: 61 74 65 20 48 54 4d 4c 20 66 6f 72 20 74 68 65  ate HTML for the
0030: 20 67 6f 61 6c 73 2e 68 74 6d 6c 20 66 69 6c 65   goals.html file
0040: 2e 0a 23 0a 73 65 74 20 72 63 73 69 64 20 7b 24  ..#.set rcsid {$
0050: 49 64 3a 20 6f 70 74 6f 76 65 72 76 69 65 77 2e  Id: optoverview.
0060: 74 63 6c 2c 76 20 31 2e 35 20 32 30 30 35 2f 31  tcl,v 1.5 2005/1
0070: 31 2f 32 34 20 31 33 3a 31 35 3a 33 34 20 64 72  1/24 13:15:34 dr
0080: 68 20 45 78 70 20 24 7d 0a 73 6f 75 72 63 65 20  h Exp $}.source 
0090: 63 6f 6d 6d 6f 6e 2e 74 63 6c 0a 68 65 61 64 65  common.tcl.heade
00a0: 72 20 7b 54 68 65 20 53 51 4c 69 74 65 20 51 75  r {The SQLite Qu
00b0: 65 72 79 20 4f 70 74 69 6d 69 7a 65 72 20 4f 76  ery Optimizer Ov
00c0: 65 72 76 69 65 77 7d 0a 0a 70 72 6f 63 20 43 4f  erview}..proc CO
00d0: 44 45 20 7b 74 65 78 74 7d 20 7b 0a 20 20 70 75  DE {text} {.  pu
00e0: 74 73 20 22 3c 62 6c 6f 63 6b 71 75 6f 74 65 3e  ts "<blockquote>
00f0: 3c 70 72 65 3e 22 0a 20 20 70 75 74 73 20 24 74  <pre>".  puts $t
0100: 65 78 74 0a 20 20 70 75 74 73 20 22 3c 2f 70 72  ext.  puts "</pr
0110: 65 3e 3c 2f 62 6c 6f 63 6b 71 75 6f 74 65 3e 22  e></blockquote>"
0120: 0a 7d 0a 70 72 6f 63 20 53 59 4e 54 41 58 20 7b  .}.proc SYNTAX {
0130: 74 65 78 74 7d 20 7b 0a 20 20 70 75 74 73 20 22  text} {.  puts "
0140: 3c 62 6c 6f 63 6b 71 75 6f 74 65 3e 3c 70 72 65  <blockquote><pre
0150: 3e 22 0a 20 20 73 65 74 20 74 32 20 5b 73 74 72  >".  set t2 [str
0160: 69 6e 67 20 6d 61 70 20 7b 26 20 26 61 6d 70 3b  ing map {& &amp;
0170: 20 3c 20 26 6c 74 3b 20 3e 20 26 67 74 3b 7d 20   < &lt; > &gt;} 
0180: 24 74 65 78 74 5d 0a 20 20 72 65 67 73 75 62 20  $text].  regsub 
0190: 2d 61 6c 6c 20 22 2f 28 5c 5b 5e 5c 6e 2f 5c 5d  -all "/(\[^\n/\]
01a0: 2b 29 2f 22 20 24 74 32 20 7b 3c 2f 62 3e 3c 69  +)/" $t2 {</b><i
01b0: 3e 5c 31 3c 2f 69 3e 3c 62 3e 7d 20 74 33 0a 20  >\1</i><b>} t3. 
01c0: 20 70 75 74 73 20 22 3c 62 3e 24 74 33 3c 2f 62   puts "<b>$t3</b
01d0: 3e 22 0a 20 20 70 75 74 73 20 22 3c 2f 70 72 65  >".  puts "</pre
01e0: 3e 3c 2f 62 6c 6f 63 6b 71 75 6f 74 65 3e 22 0a  ></blockquote>".
01f0: 7d 0a 70 72 6f 63 20 49 4d 41 47 45 20 7b 6e 61  }.proc IMAGE {na
0200: 6d 65 20 7b 63 61 70 74 69 6f 6e 20 7b 7d 7d 7d  me {caption {}}}
0210: 20 7b 0a 20 20 70 75 74 73 20 22 3c 63 65 6e 74   {.  puts "<cent
0220: 65 72 3e 3c 69 6d 67 20 73 72 63 3d 5c 22 24 6e  er><img src=\"$n
0230: 61 6d 65 5c 22 3e 22 0a 20 20 69 66 20 7b 24 63  ame\">".  if {$c
0240: 61 70 74 69 6f 6e 21 3d 22 22 7d 20 7b 0a 20 20  aption!=""} {.  
0250: 20 20 70 75 74 73 20 22 3c 62 72 3e 24 63 61 70    puts "<br>$cap
0260: 74 69 6f 6e 22 0a 20 20 7d 0a 20 20 70 75 74 73  tion".  }.  puts
0270: 20 22 3c 2f 63 65 6e 74 65 72 3e 22 0a 7d 0a 70   "</center>".}.p
0280: 72 6f 63 20 50 41 52 41 47 52 41 50 48 20 7b 74  roc PARAGRAPH {t
0290: 65 78 74 7d 20 7b 0a 20 20 23 20 72 65 67 73 75  ext} {.  # regsu
02a0: 62 20 2d 61 6c 6c 20 22 2f 28 5c 5b 61 2d 7a 41  b -all "/(\[a-zA
02b0: 2d 5a 30 2d 39 5c 5d 2b 29 2f 22 20 24 74 65 78  -Z0-9\]+)/" $tex
02c0: 74 20 7b 3c 69 3e 5c 31 3c 2f 69 3e 7d 20 74 32  t {<i>\1</i>} t2
02d0: 0a 20 20 72 65 67 73 75 62 20 2d 61 6c 6c 20 22  .  regsub -all "
02e0: 5c 5c 2a 28 5c 5b 5e 5c 6e 2a 5c 5d 2b 29 5c 5c  \\*(\[^\n*\]+)\\
02f0: 2a 22 20 24 74 65 78 74 20 7b 3c 74 74 3e 3c 62  *" $text {<tt><b
0300: 3e 3c 62 69 67 3e 5c 31 3c 2f 62 69 67 3e 3c 2f  ><big>\1</big></
0310: 62 3e 3c 2f 74 74 3e 7d 20 74 33 0a 20 20 70 75  b></tt>} t3.  pu
0320: 74 73 20 22 3c 70 3e 24 74 33 3c 2f 70 3e 5c 6e  ts "<p>$t3</p>\n
0330: 22 0a 7d 0a 73 65 74 20 6c 65 76 65 6c 28 30 29  ".}.set level(0)
0340: 20 30 0a 73 65 74 20 6c 65 76 65 6c 28 31 29 20   0.set level(1) 
0350: 30 0a 70 72 6f 63 20 48 45 41 44 49 4e 47 20 7b  0.proc HEADING {
0360: 6e 20 6e 61 6d 65 20 7b 74 61 67 20 7b 7d 7d 7d  n name {tag {}}}
0370: 20 7b 0a 20 20 69 66 20 7b 24 74 61 67 21 3d 22   {.  if {$tag!="
0380: 22 7d 20 7b 0a 20 20 20 20 70 75 74 73 20 22 3c  "} {.    puts "<
0390: 61 20 6e 61 6d 65 3d 5c 22 24 74 61 67 5c 22 3e  a name=\"$tag\">
03a0: 22 0a 20 20 7d 0a 20 20 67 6c 6f 62 61 6c 20 6c  ".  }.  global l
03b0: 65 76 65 6c 0a 20 20 69 6e 63 72 20 6c 65 76 65  evel.  incr leve
03c0: 6c 28 24 6e 29 0a 20 20 66 6f 72 20 7b 73 65 74  l($n).  for {set
03d0: 20 69 20 5b 65 78 70 72 20 7b 24 6e 2b 31 7d 5d   i [expr {$n+1}]
03e0: 7d 20 7b 24 69 3c 31 30 7d 20 7b 69 6e 63 72 20  } {$i<10} {incr 
03f0: 69 7d 20 7b 0a 20 20 20 20 73 65 74 20 6c 65 76  i} {.    set lev
0400: 65 6c 28 24 69 29 20 30 0a 20 20 7d 0a 20 20 69  el($i) 0.  }.  i
0410: 66 20 7b 24 6e 3d 3d 30 7d 20 7b 0a 20 20 20 20  f {$n==0} {.    
0420: 73 65 74 20 6e 75 6d 20 7b 7d 0a 20 20 7d 20 65  set num {}.  } e
0430: 6c 73 65 69 66 20 7b 24 6e 3d 3d 31 7d 20 7b 0a  lseif {$n==1} {.
0440: 20 20 20 20 73 65 74 20 6e 75 6d 20 24 6c 65 76      set num $lev
0450: 65 6c 28 31 29 2e 30 0a 20 20 7d 20 65 6c 73 65  el(1).0.  } else
0460: 20 7b 0a 20 20 20 20 73 65 74 20 6e 75 6d 20 24   {.    set num $
0470: 6c 65 76 65 6c 28 31 29 0a 20 20 20 20 66 6f 72  level(1).    for
0480: 20 7b 73 65 74 20 69 20 32 7d 20 7b 24 69 3c 3d   {set i 2} {$i<=
0490: 24 6e 7d 20 7b 69 6e 63 72 20 69 7d 20 7b 0a 20  $n} {incr i} {. 
04a0: 20 20 20 20 20 61 70 70 65 6e 64 20 6e 75 6d 20       append num 
04b0: 2e 24 6c 65 76 65 6c 28 24 69 29 0a 20 20 20 20  .$level($i).    
04c0: 7d 0a 20 20 7d 0a 20 20 69 6e 63 72 20 6e 20 31  }.  }.  incr n 1
04d0: 0a 20 20 70 75 74 73 20 22 3c 68 24 6e 3e 24 6e  .  puts "<h$n>$n
04e0: 75 6d 20 24 6e 61 6d 65 3c 2f 68 24 6e 3e 22 0a  um $name</h$n>".
04f0: 7d 0a 0a 48 45 41 44 49 4e 47 20 30 20 7b 54 68  }..HEADING 0 {Th
0500: 65 20 53 51 4c 69 74 65 20 51 75 65 72 79 20 4f  e SQLite Query O
0510: 70 74 69 6d 69 7a 65 72 20 4f 76 65 72 76 69 65  ptimizer Overvie
0520: 77 7d 0a 0a 50 41 52 41 47 52 41 50 48 20 7b 0a  w}..PARAGRAPH {.
0530: 20 20 54 68 69 73 20 64 6f 63 75 6d 65 6e 74 20    This document 
0540: 70 72 6f 76 69 64 65 73 20 61 20 74 65 72 73 65  provides a terse
0550: 20 6f 76 65 72 76 69 65 77 20 6f 66 20 68 6f 77   overview of how
0560: 20 74 68 65 20 71 75 65 72 79 20 6f 70 74 69 6d   the query optim
0570: 69 7a 65 72 0a 20 20 66 6f 72 20 53 51 4c 69 74  izer.  for SQLit
0580: 65 20 77 6f 72 6b 73 2e 20 20 54 68 69 73 20 69  e works.  This i
0590: 73 20 6e 6f 74 20 61 20 74 75 74 6f 72 69 61 6c  s not a tutorial
05a0: 2e 20 20 54 68 65 20 72 65 61 64 65 72 20 69 73  .  The reader is
05b0: 20 6c 69 6b 65 6c 79 20 74 6f 0a 20 20 6e 65 65   likely to.  nee
05c0: 64 20 73 6f 6d 65 20 70 72 69 6f 72 20 6b 6e 6f  d some prior kno
05d0: 77 6c 65 64 67 65 20 6f 66 20 68 6f 77 20 64 61  wledge of how da
05e0: 74 61 62 61 73 65 20 65 6e 67 69 6e 65 73 20 6f  tabase engines o
05f0: 70 65 72 61 74 65 20 0a 20 20 69 6e 20 6f 72 64  perate .  in ord
0600: 65 72 20 74 6f 20 66 75 6c 6c 79 20 75 6e 64 65  er to fully unde
0610: 72 73 74 61 6e 64 20 74 68 69 73 20 74 65 78 74  rstand this text
0620: 2e 0a 7d 0a 0a 48 45 41 44 49 4e 47 20 31 20 7b  ..}..HEADING 1 {
0630: 57 48 45 52 45 20 63 6c 61 75 73 65 20 61 6e 61  WHERE clause ana
0640: 6c 79 73 69 73 7d 20 77 68 65 72 65 5f 63 6c 61  lysis} where_cla
0650: 75 73 65 0a 0a 50 41 52 41 47 52 41 50 48 20 7b  use..PARAGRAPH {
0660: 0a 20 20 54 68 65 20 57 48 45 52 45 20 63 6c 61  .  The WHERE cla
0670: 75 73 65 20 6f 6e 20 61 20 71 75 65 72 79 20 69  use on a query i
0680: 73 20 62 72 6f 6b 65 6e 20 75 70 20 69 6e 74 6f  s broken up into
0690: 20 22 74 65 72 6d 73 22 20 77 68 65 72 65 20 65   "terms" where e
06a0: 61 63 68 20 74 65 72 6d 0a 20 20 69 73 20 73 65  ach term.  is se
06b0: 70 61 72 61 74 65 64 20 66 72 6f 6d 20 74 68 65  parated from the
06c0: 20 6f 74 68 65 72 73 20 62 79 20 61 6e 20 41 4e   others by an AN
06d0: 44 20 6f 70 65 72 61 74 6f 72 2e 0a 7d 0a 50 41  D operator..}.PA
06e0: 52 41 47 52 41 50 48 20 7b 0a 20 20 41 6c 6c 20  RAGRAPH {.  All 
06f0: 74 65 72 6d 73 20 6f 66 20 74 68 65 20 57 48 45  terms of the WHE
0700: 52 45 20 63 6c 61 75 73 65 20 61 72 65 20 61 6e  RE clause are an
0710: 61 6c 79 7a 65 64 20 74 6f 20 73 65 65 20 69 66  alyzed to see if
0720: 20 74 68 65 79 20 63 61 6e 20 62 65 0a 20 20 73   they can be.  s
0730: 61 74 69 73 66 69 65 64 20 75 73 69 6e 67 20 69  atisfied using i
0740: 6e 64 69 63 65 73 2e 0a 20 20 54 65 72 6d 73 20  ndices..  Terms 
0750: 74 68 61 74 20 63 61 6e 6e 6f 74 20 62 65 20 73  that cannot be s
0760: 61 74 69 73 66 69 65 64 20 74 68 72 6f 75 67 68  atisfied through
0770: 20 74 68 65 20 75 73 65 20 6f 66 20 69 6e 64 69   the use of indi
0780: 63 65 73 20 62 65 63 6f 6d 65 0a 20 20 74 65 73  ces become.  tes
0790: 74 73 20 74 68 61 74 20 61 72 65 20 65 76 61 6c  ts that are eval
07a0: 75 61 74 65 64 20 61 67 61 69 6e 73 74 20 65 61  uated against ea
07b0: 63 68 20 72 6f 77 20 6f 66 20 74 68 65 20 72 65  ch row of the re
07c0: 6c 65 76 61 6e 74 20 69 6e 70 75 74 0a 20 20 74  levant input.  t
07d0: 61 62 6c 65 73 2e 20 20 4e 6f 20 74 65 73 74 73  ables.  No tests
07e0: 20 61 72 65 20 64 6f 6e 65 20 66 6f 72 20 74 65   are done for te
07f0: 72 6d 73 20 74 68 61 74 20 61 72 65 20 63 6f 6d  rms that are com
0800: 70 6c 65 74 65 6c 79 20 73 61 74 69 73 66 69 65  pletely satisfie
0810: 64 20 62 79 0a 20 20 69 6e 64 69 63 65 73 2e 20  d by.  indices. 
0820: 20 53 6f 6d 65 74 69 6d 65 73 0a 20 20 6f 6e 65   Sometimes.  one
0830: 20 6f 72 20 6d 6f 72 65 20 74 65 72 6d 73 20 77   or more terms w
0840: 69 6c 6c 20 70 72 6f 76 69 64 65 20 68 69 6e 74  ill provide hint
0850: 73 20 74 6f 20 69 6e 64 69 63 65 73 20 62 75 74  s to indices but
0860: 20 73 74 69 6c 6c 20 6d 75 73 74 20 62 65 0a 20   still must be. 
0870: 20 65 76 61 6c 75 61 74 65 64 20 61 67 61 69 6e   evaluated again
0880: 73 74 20 65 61 63 68 20 72 6f 77 20 6f 66 20 74  st each row of t
0890: 68 65 20 69 6e 70 75 74 20 74 61 62 6c 65 73 2e  he input tables.
08a0: 0a 7d 0a 0a 50 41 52 41 47 52 41 50 48 20 7b 0a  .}..PARAGRAPH {.
08b0: 20 20 54 68 65 20 61 6e 61 6c 79 73 69 73 20 6f    The analysis o
08c0: 66 20 61 20 74 65 72 6d 20 6d 69 67 68 74 20 63  f a term might c
08d0: 61 75 73 65 20 6e 65 77 20 22 76 69 72 74 75 61  ause new "virtua
08e0: 6c 22 20 74 65 72 6d 73 20 74 6f 0a 20 20 62 65  l" terms to.  be
08f0: 20 61 64 64 65 64 20 74 6f 20 74 68 65 20 57 48   added to the WH
0900: 45 52 45 20 63 6c 61 75 73 65 2e 20 20 56 69 72  ERE clause.  Vir
0910: 74 75 61 6c 20 74 65 72 6d 73 20 63 61 6e 20 62  tual terms can b
0920: 65 20 75 73 65 64 20 77 69 74 68 0a 20 20 69 6e  e used with.  in
0930: 64 69 63 65 73 20 74 6f 20 72 65 73 74 72 69 63  dices to restric
0940: 74 20 61 20 73 65 61 72 63 68 2e 20 20 42 75 74  t a search.  But
0950: 20 76 69 72 74 75 61 6c 20 74 65 72 6d 73 20 6e   virtual terms n
0960: 65 76 65 72 20 67 65 6e 65 72 61 74 65 20 63 6f  ever generate co
0970: 64 65 0a 20 20 74 68 61 74 20 69 73 20 74 65 73  de.  that is tes
0980: 74 65 64 20 61 67 61 69 6e 73 74 20 69 6e 70 75  ted against inpu
0990: 74 20 72 6f 77 73 2e 0a 7d 0a 0a 50 41 52 41 47  t rows..}..PARAG
09a0: 52 41 50 48 20 7b 0a 20 20 54 6f 20 62 65 20 75  RAPH {.  To be u
09b0: 73 61 62 6c 65 20 62 79 20 61 6e 20 69 6e 64 65  sable by an inde
09c0: 78 20 61 20 74 65 72 6d 20 6d 75 73 74 20 62 65  x a term must be
09d0: 20 6f 66 20 6f 6e 65 20 6f 66 20 74 68 65 20 66   of one of the f
09e0: 6f 6c 6c 6f 77 69 6e 67 0a 20 20 66 6f 72 6d 73  ollowing.  forms
09f0: 3a 0a 7d 0a 53 59 4e 54 41 58 20 7b 0a 20 20 2f  :.}.SYNTAX {.  /
0a00: 63 6f 6c 75 6d 6e 2f 20 3d 20 2f 65 78 70 72 65  column/ = /expre
0a10: 73 73 69 6f 6e 2f 0a 20 20 2f 63 6f 6c 75 6d 6e  ssion/.  /column
0a20: 2f 20 3e 20 2f 65 78 70 72 65 73 73 69 6f 6e 2f  / > /expression/
0a30: 0a 20 20 2f 63 6f 6c 75 6d 6e 2f 20 3e 3d 20 2f  .  /column/ >= /
0a40: 65 78 70 72 65 73 73 69 6f 6e 2f 0a 20 20 2f 63  expression/.  /c
0a50: 6f 6c 75 6d 6e 2f 20 3c 20 2f 65 78 70 72 65 73  olumn/ < /expres
0a60: 73 69 6f 6e 2f 0a 20 20 2f 63 6f 6c 75 6d 6e 2f  sion/.  /column/
0a70: 20 3c 3d 20 2f 65 78 70 72 65 73 73 69 6f 6e 2f   <= /expression/
0a80: 0a 20 20 2f 65 78 70 72 65 73 73 69 6f 6e 2f 20  .  /expression/ 
0a90: 3d 20 2f 63 6f 6c 75 6d 6e 2f 0a 20 20 2f 65 78  = /column/.  /ex
0aa0: 70 72 65 73 73 69 6f 6e 2f 20 3e 20 2f 63 6f 6c  pression/ > /col
0ab0: 75 6d 6e 2f 0a 20 20 2f 65 78 70 72 65 73 73 69  umn/.  /expressi
0ac0: 6f 6e 2f 20 3e 3d 20 2f 63 6f 6c 75 6d 6e 2f 0a  on/ >= /column/.
0ad0: 20 20 2f 65 78 70 72 65 73 73 69 6f 6e 2f 20 3c    /expression/ <
0ae0: 20 2f 63 6f 6c 75 6d 6e 2f 0a 20 20 2f 65 78 70   /column/.  /exp
0af0: 72 65 73 73 69 6f 6e 2f 20 3c 3d 20 2f 63 6f 6c  ression/ <= /col
0b00: 75 6d 6e 2f 0a 20 20 2f 63 6f 6c 75 6d 6e 2f 20  umn/.  /column/ 
0b10: 49 4e 20 28 2f 65 78 70 72 65 73 73 69 6f 6e 2d  IN (/expression-
0b20: 6c 69 73 74 2f 29 0a 20 20 2f 63 6f 6c 75 6d 6e  list/).  /column
0b30: 2f 20 49 4e 20 28 2f 73 75 62 71 75 65 72 79 2f  / IN (/subquery/
0b40: 29 0a 7d 0a 50 41 52 41 47 52 41 50 48 20 7b 0a  ).}.PARAGRAPH {.
0b50: 20 20 49 66 20 61 6e 20 69 6e 64 65 78 20 69 73    If an index is
0b60: 20 63 72 65 61 74 65 64 20 75 73 69 6e 67 20 61   created using a
0b70: 20 73 74 61 74 65 6d 65 6e 74 20 6c 69 6b 65 20   statement like 
0b80: 74 68 69 73 3a 0a 7d 0a 43 4f 44 45 20 7b 0a 20  this:.}.CODE {. 
0b90: 20 43 52 45 41 54 45 20 49 4e 44 45 58 20 69 64   CREATE INDEX id
0ba0: 78 5f 65 78 31 20 4f 4e 20 65 78 31 28 61 2c 62  x_ex1 ON ex1(a,b
0bb0: 2c 63 2c 64 2c 65 2c 2e 2e 2e 2c 79 2c 7a 29 3b  ,c,d,e,...,y,z);
0bc0: 0a 7d 0a 50 41 52 41 47 52 41 50 48 20 7b 0a 20  .}.PARAGRAPH {. 
0bd0: 20 54 68 65 6e 20 74 68 65 20 69 6e 64 65 78 20   Then the index 
0be0: 6d 69 67 68 74 20 62 65 20 75 73 65 64 20 69 66  might be used if
0bf0: 20 74 68 65 20 69 6e 69 74 69 61 6c 20 63 6f 6c   the initial col
0c00: 75 6d 6e 73 20 6f 66 20 74 68 65 20 69 6e 64 65  umns of the inde
0c10: 78 0a 20 20 28 63 6f 6c 75 6d 6e 73 20 61 2c 20  x.  (columns a, 
0c20: 62 2c 20 61 6e 64 20 73 6f 20 66 6f 72 74 68 29  b, and so forth)
0c30: 20 61 70 70 65 61 72 20 69 6e 20 57 48 45 52 45   appear in WHERE
0c40: 20 63 6c 61 75 73 65 20 74 65 72 6d 73 2e 0a 20   clause terms.. 
0c50: 20 41 6c 6c 20 69 6e 64 65 78 20 63 6f 6c 75 6d   All index colum
0c60: 6e 73 20 6d 75 73 74 20 62 65 20 75 73 65 64 20  ns must be used 
0c70: 77 69 74 68 0a 20 20 74 68 65 20 2a 3d 2a 20 6f  with.  the *=* o
0c80: 72 20 2a 49 4e 2a 20 6f 70 65 72 61 74 6f 72 73  r *IN* operators
0c90: 20 65 78 63 65 70 74 20 66 6f 72 0a 20 20 74 68   except for.  th
0ca0: 65 20 72 69 67 68 74 2d 6d 6f 73 74 20 63 6f 6c  e right-most col
0cb0: 75 6d 6e 20 77 68 69 63 68 20 63 61 6e 20 75 73  umn which can us
0cc0: 65 20 69 6e 65 71 75 61 6c 69 74 69 65 73 2e 20  e inequalities. 
0cd0: 20 46 6f 72 20 74 68 65 20 72 69 67 68 74 2d 6d   For the right-m
0ce0: 6f 73 74 0a 20 20 63 6f 6c 75 6d 6e 20 6f 66 20  ost.  column of 
0cf0: 61 6e 20 69 6e 64 65 78 20 74 68 61 74 20 69 73  an index that is
0d00: 20 75 73 65 64 2c 20 74 68 65 72 65 20 63 61 6e   used, there can
0d10: 20 62 65 20 75 70 20 74 6f 20 74 77 6f 20 69 6e   be up to two in
0d20: 65 71 75 61 6c 69 74 69 65 73 0a 20 20 74 68 61  equalities.  tha
0d30: 74 20 6d 75 73 74 20 73 61 6e 64 77 69 63 68 20  t must sandwich 
0d40: 74 68 65 20 61 6c 6c 6f 77 65 64 20 76 61 6c 75  the allowed valu
0d50: 65 73 20 6f 66 20 74 68 65 20 63 6f 6c 75 6d 6e  es of the column
0d60: 20 62 65 74 77 65 65 6e 20 74 77 6f 20 65 78 74   between two ext
0d70: 72 65 6d 65 73 2e 0a 7d 0a 50 41 52 41 47 52 41  remes..}.PARAGRA
0d80: 50 48 20 7b 0a 20 20 49 74 20 69 73 20 6e 6f 74  PH {.  It is not
0d90: 20 6e 65 63 65 73 73 61 72 79 20 66 6f 72 20 65   necessary for e
0da0: 76 65 72 79 20 63 6f 6c 75 6d 6e 20 6f 66 20 61  very column of a
0db0: 6e 20 69 6e 64 65 78 20 74 6f 20 61 70 70 65 61  n index to appea
0dc0: 72 20 69 6e 20 61 0a 20 20 57 48 45 52 45 20 63  r in a.  WHERE c
0dd0: 6c 61 75 73 65 20 74 65 72 6d 20 69 6e 20 6f 72  lause term in or
0de0: 64 65 72 20 66 6f 72 20 74 68 61 74 20 69 6e 64  der for that ind
0df0: 65 78 20 74 6f 20 62 65 20 75 73 65 64 2e 20 0a  ex to be used. .
0e00: 20 20 42 75 74 20 74 68 65 72 65 20 63 61 6e 20    But there can 
0e10: 6e 6f 74 20 62 65 20 67 61 70 73 20 69 6e 20 74  not be gaps in t
0e20: 68 65 20 63 6f 6c 75 6d 6e 73 20 6f 66 20 74 68  he columns of th
0e30: 65 20 69 6e 64 65 78 20 74 68 61 74 20 61 72 65  e index that are
0e40: 20 75 73 65 64 2e 0a 20 20 54 68 75 73 20 66 6f   used..  Thus fo
0e50: 72 20 74 68 65 20 65 78 61 6d 70 6c 65 20 69 6e  r the example in
0e60: 64 65 78 20 61 62 6f 76 65 2c 20 69 66 20 74 68  dex above, if th
0e70: 65 72 65 20 69 73 20 6e 6f 20 57 48 45 52 45 20  ere is no WHERE 
0e80: 63 6c 61 75 73 65 20 74 65 72 6d 0a 20 20 74 68  clause term.  th
0e90: 61 74 20 63 6f 6e 73 74 72 61 69 6e 74 73 20 63  at constraints c
0ea0: 6f 6c 75 6d 6e 20 63 2c 20 74 68 65 6e 20 74 65  olumn c, then te
0eb0: 72 6d 73 20 74 68 61 74 20 63 6f 6e 73 74 72 61  rms that constra
0ec0: 69 6e 74 20 63 6f 6c 75 6d 6e 73 20 61 20 61 6e  int columns a an
0ed0: 64 20 62 20 63 61 6e 0a 20 20 62 65 20 75 73 65  d b can.  be use
0ee0: 64 20 77 69 74 68 20 74 68 65 20 69 6e 64 65 78  d with the index
0ef0: 20 62 75 74 20 6e 6f 74 20 74 65 72 6d 73 20 74   but not terms t
0f00: 68 61 74 20 63 6f 6e 73 74 72 61 69 6e 74 20 63  hat constraint c
0f10: 6f 6c 75 6d 6e 73 20 64 20 74 68 72 6f 75 67 68  olumns d through
0f20: 20 7a 2e 0a 20 20 53 69 6d 69 6c 61 72 6c 79 2c   z..  Similarly,
0f30: 20 6e 6f 20 69 6e 64 65 78 20 63 6f 6c 75 6d 6e   no index column
0f40: 20 77 69 6c 6c 20 62 65 20 75 73 65 64 20 28 66   will be used (f
0f50: 6f 72 20 69 6e 64 65 78 69 6e 67 20 70 75 72 70  or indexing purp
0f60: 6f 73 65 73 29 0a 20 20 74 68 61 74 20 69 73 20  oses).  that is 
0f70: 74 6f 20 74 68 65 20 72 69 67 68 74 20 6f 66 20  to the right of 
0f80: 61 20 0a 20 20 63 6f 6c 75 6d 6e 20 74 68 61 74  a .  column that
0f90: 20 69 73 20 63 6f 6e 73 74 72 61 69 6e 65 64 20   is constrained 
0fa0: 6f 6e 6c 79 20 62 79 20 69 6e 65 71 75 61 6c 69  only by inequali
0fb0: 74 69 65 73 2e 0a 20 20 46 6f 72 20 74 68 65 20  ties..  For the 
0fc0: 69 6e 64 65 78 20 61 62 6f 76 65 20 61 6e 64 20  index above and 
0fd0: 57 48 45 52 45 20 63 6c 61 75 73 65 20 6c 69 6b  WHERE clause lik
0fe0: 65 20 74 68 69 73 3a 0a 7d 0a 43 4f 44 45 20 7b  e this:.}.CODE {
0ff0: 0a 20 20 2e 2e 2e 20 57 48 45 52 45 20 61 3d 35  .  ... WHERE a=5
1000: 20 41 4e 44 20 62 20 49 4e 20 28 31 2c 32 2c 33   AND b IN (1,2,3
1010: 29 20 41 4e 44 20 63 3e 31 32 20 41 4e 44 20 64  ) AND c>12 AND d
1020: 3d 27 68 65 6c 6c 6f 27 0a 7d 0a 50 41 52 41 47  ='hello'.}.PARAG
1030: 52 41 50 48 20 7b 0a 20 20 4f 6e 6c 79 20 63 6f  RAPH {.  Only co
1040: 6c 75 6d 6e 73 20 61 2c 20 62 2c 20 61 6e 64 20  lumns a, b, and 
1050: 63 20 6f 66 20 74 68 65 20 69 6e 64 65 78 20 77  c of the index w
1060: 6f 75 6c 64 20 62 65 20 75 73 61 62 6c 65 2e 20  ould be usable. 
1070: 20 54 68 65 20 64 20 63 6f 6c 75 6d 6e 0a 20 20   The d column.  
1080: 77 6f 75 6c 64 20 6e 6f 74 20 62 65 20 75 73 61  would not be usa
1090: 62 6c 65 20 62 65 63 61 75 73 65 20 69 74 20 6f  ble because it o
10a0: 63 63 75 72 73 20 74 6f 20 74 68 65 20 72 69 67  ccurs to the rig
10b0: 68 74 20 6f 66 20 63 20 61 6e 64 20 63 20 69 73  ht of c and c is
10c0: 0a 20 20 63 6f 6e 73 74 72 61 69 6e 65 64 20 6f  .  constrained o
10d0: 6e 6c 79 20 62 79 20 69 6e 65 71 75 61 6c 69 74  nly by inequalit
10e0: 69 65 73 2e 0a 7d 0a 0a 48 45 41 44 49 4e 47 20  ies..}..HEADING 
10f0: 31 20 7b 54 68 65 20 42 45 54 57 45 45 4e 20 6f  1 {The BETWEEN o
1100: 70 74 69 6d 69 7a 61 74 69 6f 6e 7d 20 62 65 74  ptimization} bet
1110: 77 65 65 6e 5f 6f 70 74 0a 0a 50 41 52 41 47 52  ween_opt..PARAGR
1120: 41 50 48 20 7b 0a 20 20 49 66 20 61 20 74 65 72  APH {.  If a ter
1130: 6d 20 6f 66 20 74 68 65 20 57 48 45 52 45 20 63  m of the WHERE c
1140: 6c 61 75 73 65 20 69 73 20 6f 66 20 74 68 65 20  lause is of the 
1150: 66 6f 6c 6c 6f 77 69 6e 67 20 66 6f 72 6d 3a 0a  following form:.
1160: 7d 0a 53 59 4e 54 41 58 20 7b 0a 20 20 2f 65 78  }.SYNTAX {.  /ex
1170: 70 72 31 2f 20 42 45 54 57 45 45 4e 20 2f 65 78  pr1/ BETWEEN /ex
1180: 70 72 32 2f 20 41 4e 44 20 2f 65 78 70 72 33 2f  pr2/ AND /expr3/
1190: 0a 7d 0a 50 41 52 41 47 52 41 50 48 20 7b 0a 20  .}.PARAGRAPH {. 
11a0: 20 54 68 65 6e 20 74 77 6f 20 76 69 72 74 75 61   Then two virtua
11b0: 6c 20 74 65 72 6d 73 20 61 72 65 20 61 64 64 65  l terms are adde
11c0: 64 20 61 73 20 66 6f 6c 6c 6f 77 73 3a 0a 7d 0a  d as follows:.}.
11d0: 53 59 4e 54 41 58 20 7b 0a 20 20 2f 65 78 70 72  SYNTAX {.  /expr
11e0: 31 2f 20 3e 3d 20 2f 65 78 70 72 32 2f 20 41 4e  1/ >= /expr2/ AN
11f0: 44 20 2f 65 78 70 72 31 2f 20 3c 3d 20 2f 65 78  D /expr1/ <= /ex
1200: 70 72 33 2f 0a 7d 0a 50 41 52 41 47 52 41 50 48  pr3/.}.PARAGRAPH
1210: 20 7b 0a 20 20 49 66 20 62 6f 74 68 20 76 69 72   {.  If both vir
1220: 74 75 61 6c 20 74 65 72 6d 73 20 65 6e 64 20 75  tual terms end u
1230: 70 20 62 65 69 6e 67 20 75 73 65 64 20 61 73 20  p being used as 
1240: 63 6f 6e 73 74 72 61 69 6e 74 73 20 6f 6e 20 61  constraints on a
1250: 6e 20 69 6e 64 65 78 2c 0a 20 20 74 68 65 6e 20  n index,.  then 
1260: 74 68 65 20 6f 72 69 67 69 6e 61 6c 20 42 45 54  the original BET
1270: 57 45 45 4e 20 74 65 72 6d 20 69 73 20 6f 6d 69  WEEN term is omi
1280: 74 74 65 64 20 61 6e 64 20 74 68 65 20 63 6f 72  tted and the cor
1290: 72 65 73 70 6f 6e 64 69 6e 67 20 74 65 73 74 0a  responding test.
12a0: 20 20 69 73 20 6e 6f 74 20 70 65 72 66 6f 72 6d    is not perform
12b0: 65 64 20 6f 6e 20 69 6e 70 75 74 20 72 6f 77 73  ed on input rows
12c0: 2e 0a 20 20 54 68 75 73 20 69 66 20 74 68 65 20  ..  Thus if the 
12d0: 42 45 54 57 45 45 4e 20 74 65 72 6d 20 65 6e 64  BETWEEN term end
12e0: 73 20 75 70 20 62 65 69 6e 67 20 75 73 65 64 20  s up being used 
12f0: 61 73 20 61 6e 20 69 6e 64 65 78 20 63 6f 6e 73  as an index cons
1300: 74 72 61 69 6e 74 0a 20 20 6e 6f 20 74 65 73 74  traint.  no test
1310: 73 20 61 72 65 20 65 76 65 72 20 70 65 72 66 6f  s are ever perfo
1320: 72 6d 65 64 20 6f 6e 20 74 68 61 74 20 74 65 72  rmed on that ter
1330: 6d 2e 0a 20 20 4f 6e 20 74 68 65 20 6f 74 68 65  m..  On the othe
1340: 72 20 68 61 6e 64 2c 20 74 68 65 0a 20 20 76 69  r hand, the.  vi
1350: 72 74 75 61 6c 20 74 65 72 6d 73 20 74 68 65 6d  rtual terms them
1360: 73 65 6c 76 65 73 20 6e 65 76 65 72 20 63 61 75  selves never cau
1370: 73 65 73 20 74 65 73 74 73 20 74 6f 20 62 65 20  ses tests to be 
1380: 70 65 72 66 6f 72 6d 65 64 20 6f 6e 0a 20 20 69  performed on.  i
1390: 6e 70 75 74 20 72 6f 77 73 2e 0a 20 20 54 68 75  nput rows..  Thu
13a0: 73 20 69 66 20 74 68 65 20 42 45 54 57 45 45 4e  s if the BETWEEN
13b0: 20 74 65 72 6d 20 69 73 20 6e 6f 74 20 75 73 65   term is not use
13c0: 64 20 61 73 20 61 6e 20 69 6e 64 65 78 20 63 6f  d as an index co
13d0: 6e 73 74 72 61 69 6e 74 20 61 6e 64 0a 20 20 69  nstraint and.  i
13e0: 6e 73 74 65 61 64 20 6d 75 73 74 20 62 65 20 75  nstead must be u
13f0: 73 65 64 20 74 6f 20 74 65 73 74 20 69 6e 70 75  sed to test inpu
1400: 74 20 72 6f 77 73 2c 20 74 68 65 20 3c 69 3e 65  t rows, the <i>e
1410: 78 70 72 31 3c 2f 69 3e 20 65 78 70 72 65 73 73  xpr1</i> express
1420: 69 6f 6e 20 69 73 0a 20 20 6f 6e 6c 79 20 65 76  ion is.  only ev
1430: 61 6c 75 61 74 65 64 20 6f 6e 63 65 2e 0a 7d 0a  aluated once..}.
1440: 0a 48 45 41 44 49 4e 47 20 31 20 7b 54 68 65 20  .HEADING 1 {The 
1450: 4f 52 20 6f 70 74 69 6d 69 7a 61 74 69 6f 6e 7d  OR optimization}
1460: 20 6f 72 5f 6f 70 74 0a 0a 50 41 52 41 47 52 41   or_opt..PARAGRA
1470: 50 48 20 7b 0a 20 20 49 66 20 61 20 74 65 72 6d  PH {.  If a term
1480: 20 63 6f 6e 73 69 73 74 73 20 6f 66 20 6d 75 6c   consists of mul
1490: 74 69 70 6c 65 20 73 75 62 74 65 72 6d 73 20 63  tiple subterms c
14a0: 6f 6e 74 61 69 6e 69 6e 67 20 61 20 63 6f 6d 6d  ontaining a comm
14b0: 6f 6e 20 63 6f 6c 75 6d 6e 0a 20 20 6e 61 6d 65  on column.  name
14c0: 20 61 6e 64 20 73 65 70 61 72 61 74 65 64 20 62   and separated b
14d0: 79 20 4f 52 2c 20 6c 69 6b 65 20 74 68 69 73 3a  y OR, like this:
14e0: 0a 7d 0a 53 59 4e 54 41 58 20 7b 0a 20 20 2f 63  .}.SYNTAX {.  /c
14f0: 6f 6c 75 6d 6e 2f 20 3d 20 2f 65 78 70 72 31 2f  olumn/ = /expr1/
1500: 20 4f 52 20 2f 63 6f 6c 75 6d 6e 2f 20 3d 20 2f   OR /column/ = /
1510: 65 78 70 72 32 2f 20 4f 52 20 2f 63 6f 6c 75 6d  expr2/ OR /colum
1520: 6e 2f 20 3d 20 2f 65 78 70 72 33 2f 20 4f 52 20  n/ = /expr3/ OR 
1530: 2e 2e 2e 0a 7d 0a 50 41 52 41 47 52 41 50 48 20  ....}.PARAGRAPH 
1540: 7b 0a 20 20 54 68 65 6e 20 74 68 65 20 74 65 72  {.  Then the ter
1550: 6d 20 69 73 20 72 65 77 72 69 74 74 65 6e 20 61  m is rewritten a
1560: 73 20 66 6f 6c 6c 6f 77 73 3a 0a 7d 0a 53 59 4e  s follows:.}.SYN
1570: 54 41 58 20 7b 0a 20 20 2f 63 6f 6c 75 6d 6e 2f  TAX {.  /column/
1580: 20 49 4e 20 28 2f 65 78 70 72 31 2f 2c 2f 65 78   IN (/expr1/,/ex
1590: 70 72 32 2f 2c 2f 65 78 70 72 33 2f 2c 2f 65 78  pr2/,/expr3/,/ex
15a0: 70 72 34 2f 2c 2e 2e 2e 29 0a 7d 0a 50 41 52 41  pr4/,...).}.PARA
15b0: 47 52 41 50 48 20 7b 0a 20 20 54 68 65 20 72 65  GRAPH {.  The re
15c0: 77 72 69 74 74 65 6e 20 74 65 72 6d 20 74 68 65  written term the
15d0: 6e 20 6d 69 67 68 74 20 67 6f 20 6f 6e 20 74 6f  n might go on to
15e0: 20 63 6f 6e 73 74 72 61 69 6e 74 20 61 6e 20 69   constraint an i
15f0: 6e 64 65 78 20 75 73 69 6e 67 20 74 68 65 0a 20  ndex using the. 
1600: 20 6e 6f 72 6d 61 6c 20 72 75 6c 65 73 20 66 6f   normal rules fo
1610: 72 20 2a 49 4e 2a 20 6f 70 65 72 61 74 6f 72 73  r *IN* operators
1620: 2e 0a 20 20 4e 6f 74 65 20 74 68 61 74 20 3c 69  ..  Note that <i
1630: 3e 63 6f 6c 75 6d 6e 3c 2f 69 3e 20 6d 75 73 74  >column</i> must
1640: 20 62 65 20 74 68 65 20 73 61 6d 65 20 63 6f 6c   be the same col
1650: 75 6d 6e 20 69 6e 20 65 76 65 72 79 20 4f 52 2d  umn in every OR-
1660: 63 6f 6e 6e 65 63 74 65 64 20 73 75 62 74 65 72  connected subter
1670: 6d 2c 0a 20 20 61 6c 74 68 6f 75 67 68 20 74 68  m,.  although th
1680: 65 20 63 6f 6c 75 6d 6e 20 63 61 6e 20 6f 63 63  e column can occ
1690: 75 72 20 6f 6e 20 65 69 74 68 65 72 20 74 68 65  ur on either the
16a0: 20 6c 65 66 74 20 6f 72 20 74 68 65 20 72 69 67   left or the rig
16b0: 68 74 20 73 69 64 65 20 6f 66 0a 20 20 74 68 65  ht side of.  the
16c0: 20 2a 3d 2a 20 6f 70 65 72 61 74 6f 72 2e 0a 7d   *=* operator..}
16d0: 0a 0a 48 45 41 44 49 4e 47 20 31 20 7b 54 68 65  ..HEADING 1 {The
16e0: 20 4c 49 4b 45 20 6f 70 74 69 6d 69 7a 61 74 69   LIKE optimizati
16f0: 6f 6e 7d 20 6c 69 6b 65 5f 6f 70 74 0a 0a 50 41  on} like_opt..PA
1700: 52 41 47 52 41 50 48 20 7b 0a 20 20 54 65 72 6d  RAGRAPH {.  Term
1710: 73 20 74 68 61 74 20 61 72 65 20 63 6f 6d 70 6f  s that are compo
1720: 73 65 64 20 6f 66 20 74 68 65 20 4c 49 4b 45 20  sed of the LIKE 
1730: 6f 72 20 47 4c 4f 42 20 6f 70 65 72 61 74 6f 72  or GLOB operator
1740: 0a 20 20 63 61 6e 20 73 6f 6d 65 74 69 6d 65 73  .  can sometimes
1750: 20 62 65 20 75 73 65 64 20 74 6f 20 63 6f 6e 73   be used to cons
1760: 74 72 61 69 6e 20 69 6e 64 69 63 65 73 2e 0a 20  train indices.. 
1770: 20 54 68 65 72 65 20 61 72 65 20 6d 61 6e 79 20   There are many 
1780: 63 6f 6e 64 69 74 69 6f 6e 73 20 6f 6e 20 74 68  conditions on th
1790: 69 73 20 75 73 65 3a 0a 7d 0a 50 41 52 41 47 52  is use:.}.PARAGR
17a0: 41 50 48 20 7b 0a 20 20 3c 6f 6c 3e 0a 20 20 3c  APH {.  <ol>.  <
17b0: 6c 69 3e 54 68 65 20 6c 65 66 74 2d 68 61 6e 64  li>The left-hand
17c0: 20 73 69 64 65 20 6f 66 20 74 68 65 20 4c 49 4b   side of the LIK
17d0: 45 20 6f 72 20 47 4c 4f 42 20 6f 70 65 72 61 74  E or GLOB operat
17e0: 6f 72 20 6d 75 73 74 20 62 65 20 74 68 65 20 6e  or must be the n
17f0: 61 6d 65 0a 20 20 20 20 20 20 6f 66 20 61 6e 20  ame.      of an 
1800: 69 6e 64 65 78 65 64 20 63 6f 6c 75 6d 6e 2e 3c  indexed column.<
1810: 2f 6c 69 3e 0a 20 20 3c 6c 69 3e 54 68 65 20 72  /li>.  <li>The r
1820: 69 67 68 74 2d 68 61 6e 64 20 73 69 64 65 20 6f  ight-hand side o
1830: 66 20 74 68 65 20 4c 49 4b 45 20 6f 72 20 47 4c  f the LIKE or GL
1840: 4f 42 20 6d 75 73 74 20 62 65 20 61 20 73 74 72  OB must be a str
1850: 69 6e 67 20 6c 69 74 65 72 61 6c 0a 20 20 20 20  ing literal.    
1860: 20 20 74 68 61 74 20 64 6f 65 73 20 6e 6f 74 20    that does not 
1870: 62 65 67 69 6e 20 77 69 74 68 20 61 20 77 69 6c  begin with a wil
1880: 64 63 61 72 64 20 63 68 61 72 61 63 74 65 72 2e  dcard character.
1890: 3c 2f 6c 69 3e 0a 20 20 3c 6c 69 3e 54 68 65 20  </li>.  <li>The 
18a0: 45 53 43 41 50 45 20 63 6c 61 75 73 65 20 63 61  ESCAPE clause ca
18b0: 6e 6e 6f 74 20 61 70 70 65 61 72 20 6f 6e 20 74  nnot appear on t
18c0: 68 65 20 4c 49 4b 45 20 6f 70 65 72 61 74 6f 72  he LIKE operator
18d0: 2e 3c 2f 6c 69 3e 0a 20 20 3c 6c 69 3e 54 68 65  .</li>.  <li>The
18e0: 20 62 75 69 6c 64 2d 69 6e 20 66 75 6e 63 74 69   build-in functi
18f0: 6f 6e 73 20 75 73 65 64 20 74 6f 20 69 6d 70 6c  ons used to impl
1900: 65 6d 65 6e 74 20 4c 49 4b 45 20 61 6e 64 20 47  ement LIKE and G
1910: 4c 4f 42 20 6d 75 73 74 20 6e 6f 74 0a 20 20 20  LOB must not.   
1920: 20 20 20 68 61 76 65 20 62 65 65 6e 20 6f 76 65     have been ove
1930: 72 6c 6f 61 64 65 64 20 75 73 69 6e 67 20 74 68  rloaded using th
1940: 65 20 73 71 6c 69 74 65 33 5f 63 72 65 61 74 65  e sqlite3_create
1950: 5f 66 75 6e 63 74 69 6f 6e 28 29 20 41 50 49 2e  _function() API.
1960: 3c 2f 6c 69 3e 0a 20 20 3c 6c 69 3e 46 6f 72 20  </li>.  <li>For 
1970: 74 68 65 20 47 4c 4f 42 20 6f 70 65 72 61 74 6f  the GLOB operato
1980: 72 2c 20 74 68 65 20 63 6f 6c 75 6d 6e 20 6d 75  r, the column mu
1990: 73 74 20 75 73 65 20 74 68 65 20 64 65 66 61 75  st use the defau
19a0: 6c 74 20 42 49 4e 41 52 59 0a 20 20 20 20 20 20  lt BINARY.      
19b0: 63 6f 6c 6c 61 74 69 6e 67 20 73 65 71 75 65 6e  collating sequen
19c0: 63 65 2e 3c 2f 6c 69 3e 0a 20 20 3c 6c 69 3e 46  ce.</li>.  <li>F
19d0: 6f 72 20 74 68 65 20 4c 49 4b 45 20 6f 70 65 72  or the LIKE oper
19e0: 61 74 6f 72 2c 20 69 66 20 63 61 73 65 5f 73 65  ator, if case_se
19f0: 6e 73 69 74 69 76 65 5f 6c 69 6b 65 20 6d 6f 64  nsitive_like mod
1a00: 65 20 69 73 20 65 6e 61 62 6c 65 64 20 74 68 65  e is enabled the
1a10: 6e 0a 20 20 20 20 20 20 74 68 65 20 63 6f 6c 75  n.      the colu
1a20: 6d 6e 20 6d 75 73 74 20 75 73 65 20 74 68 65 20  mn must use the 
1a30: 64 65 66 61 75 6c 74 20 42 49 4e 41 52 59 20 63  default BINARY c
1a40: 6f 6c 6c 61 74 69 6e 67 20 73 65 71 75 65 6e 63  ollating sequenc
1a50: 65 2c 20 6f 72 20 69 66 0a 20 20 20 20 20 20 63  e, or if.      c
1a60: 61 73 65 5f 73 65 6e 73 69 74 69 76 65 5f 6c 69  ase_sensitive_li
1a70: 6b 65 20 6d 6f 64 65 20 69 73 20 64 69 73 61 62  ke mode is disab
1a80: 6c 65 64 20 74 68 65 6e 20 74 68 65 20 63 6f 6c  led then the col
1a90: 75 6d 6e 20 6d 75 73 74 20 75 73 65 20 74 68 65  umn must use the
1aa0: 0a 20 20 20 20 20 20 62 75 69 6c 74 2d 69 6e 20  .      built-in 
1ab0: 4e 4f 43 41 53 45 20 63 6f 6c 6c 61 74 69 6e 67  NOCASE collating
1ac0: 20 73 65 71 75 65 6e 63 65 2e 3c 2f 6c 69 3e 0a   sequence.</li>.
1ad0: 20 20 3c 2f 6f 6c 3e 0a 7d 0a 50 41 52 41 47 52    </ol>.}.PARAGR
1ae0: 41 50 48 20 7b 0a 20 20 54 68 65 20 4c 49 4b 45  APH {.  The LIKE
1af0: 20 6f 70 65 72 61 74 6f 72 20 68 61 73 20 74 77   operator has tw
1b00: 6f 20 6d 6f 64 65 73 20 74 68 61 74 20 63 61 6e  o modes that can
1b10: 20 62 65 20 73 65 74 20 62 79 20 61 20 70 72 61   be set by a pra
1b20: 67 6d 61 2e 20 20 54 68 65 0a 20 20 64 65 66 61  gma.  The.  defa
1b30: 75 6c 74 20 6d 6f 64 65 20 69 73 20 66 6f 72 20  ult mode is for 
1b40: 4c 49 4b 45 20 63 6f 6d 70 61 72 69 73 6f 6e 73  LIKE comparisons
1b50: 20 74 6f 20 62 65 20 69 6e 73 65 6e 73 69 74 69   to be insensiti
1b60: 76 65 20 74 6f 20 64 69 66 66 65 72 65 6e 63 65  ve to difference
1b70: 73 0a 20 20 6f 66 20 63 61 73 65 20 66 6f 72 20  s.  of case for 
1b80: 6c 61 74 69 6e 31 20 63 68 61 72 61 63 74 65 72  latin1 character
1b90: 73 2e 20 20 54 68 75 73 2c 20 62 79 20 64 65 66  s.  Thus, by def
1ba0: 61 75 6c 74 2c 20 74 68 65 20 66 6f 6c 6c 6f 77  ault, the follow
1bb0: 69 6e 67 0a 20 20 65 78 70 72 65 73 73 69 6f 6e  ing.  expression
1bc0: 20 69 73 20 74 72 75 65 3a 0a 7d 0a 43 4f 44 45   is true:.}.CODE
1bd0: 20 7b 0a 20 20 27 61 27 20 4c 49 4b 45 20 27 41   {.  'a' LIKE 'A
1be0: 27 0a 7d 0a 50 41 52 41 47 52 41 50 48 20 7b 0a  '.}.PARAGRAPH {.
1bf0: 20 20 42 79 20 74 75 72 6e 65 64 20 6f 6e 20 74    By turned on t
1c00: 68 65 20 63 61 73 65 5f 73 65 6e 73 69 74 69 76  he case_sensitiv
1c10: 65 5f 6c 69 6b 65 20 70 72 61 67 6d 61 20 61 73  e_like pragma as
1c20: 20 66 6f 6c 6c 6f 77 73 3a 0a 7d 0a 43 4f 44 45   follows:.}.CODE
1c30: 20 7b 0a 20 20 50 52 41 47 4d 41 20 63 61 73 65   {.  PRAGMA case
1c40: 5f 73 65 6e 73 69 74 69 76 65 5f 6c 69 6b 65 3d  _sensitive_like=
1c50: 4f 4e 3b 0a 7d 0a 50 41 52 41 47 52 41 50 48 20  ON;.}.PARAGRAPH 
1c60: 7b 0a 20 20 54 68 65 6e 20 74 68 65 20 4c 49 4b  {.  Then the LIK
1c70: 45 20 6f 70 65 72 61 74 6f 72 20 70 61 79 73 20  E operator pays 
1c80: 61 74 74 65 6e 74 69 6f 6e 20 74 6f 20 63 61 73  attention to cas
1c90: 65 20 61 6e 64 20 74 68 65 20 65 78 61 6d 70 6c  e and the exampl
1ca0: 65 20 61 62 6f 76 65 20 77 6f 75 6c 64 0a 20 20  e above would.  
1cb0: 65 76 61 6c 75 61 74 65 20 74 6f 20 66 61 6c 73  evaluate to fals
1cc0: 65 2e 20 20 4e 6f 74 65 20 74 68 61 74 20 63 61  e.  Note that ca
1cd0: 73 65 20 69 6e 73 65 6e 73 69 74 69 76 69 74 79  se insensitivity
1ce0: 20 6f 6e 6c 79 20 61 70 70 6c 69 65 73 20 74 6f   only applies to
1cf0: 0a 20 20 6c 61 74 69 6e 31 20 63 68 61 72 61 63  .  latin1 charac
1d00: 74 65 72 73 20 2d 20 62 61 73 69 63 61 6c 6c 79  ters - basically
1d10: 20 74 68 65 20 75 70 70 65 72 20 61 6e 64 20 6c   the upper and l
1d20: 6f 77 65 72 20 63 61 73 65 20 6c 65 74 74 65 72  ower case letter
1d30: 73 20 6f 66 20 45 6e 67 6c 69 73 68 0a 20 20 69  s of English.  i
1d40: 6e 20 74 68 65 20 6c 6f 77 65 72 20 31 32 37 20  n the lower 127 
1d50: 62 79 74 65 20 63 6f 64 65 73 20 6f 66 20 41 53  byte codes of AS
1d60: 43 49 49 2e 20 20 49 6e 74 65 72 6e 61 74 69 6f  CII.  Internatio
1d70: 6e 61 6c 20 63 68 61 72 61 63 74 65 72 20 73 65  nal character se
1d80: 74 73 0a 20 20 61 72 65 20 63 61 73 65 20 73 65  ts.  are case se
1d90: 6e 73 69 74 69 76 65 20 69 6e 20 53 51 4c 69 74  nsitive in SQLit
1da0: 65 20 75 6e 6c 65 73 73 20 61 20 75 73 65 72 2d  e unless a user-
1db0: 73 75 70 70 6c 69 65 64 20 63 6f 6c 6c 61 74 69  supplied collati
1dc0: 6e 67 0a 20 20 73 65 71 75 65 6e 63 65 20 69 73  ng.  sequence is
1dd0: 20 75 73 65 64 2e 20 20 42 75 74 20 69 66 20 79   used.  But if y
1de0: 6f 75 20 65 6d 70 6c 6f 79 20 61 20 75 73 65 72  ou employ a user
1df0: 2d 73 75 70 70 6c 69 65 64 20 63 6f 6c 6c 61 74  -supplied collat
1e00: 69 6e 67 20 73 65 71 75 65 6e 63 65 2c 0a 20 20  ing sequence,.  
1e10: 74 68 65 20 4c 49 4b 45 20 6f 70 74 69 6d 69 7a  the LIKE optimiz
1e20: 61 74 69 6f 6e 20 64 65 73 63 72 69 62 65 20 68  ation describe h
1e30: 65 72 65 20 77 69 6c 6c 20 6e 65 76 65 72 20 62  ere will never b
1e40: 65 20 74 61 6b 65 6e 2e 0a 7d 0a 50 41 52 41 47  e taken..}.PARAG
1e50: 52 41 50 48 20 7b 0a 20 20 54 68 65 20 4c 49 4b  RAPH {.  The LIK
1e60: 45 20 6f 70 65 72 61 74 6f 72 20 69 73 20 63 61  E operator is ca
1e70: 73 65 20 69 6e 73 65 6e 73 69 74 69 76 65 20 62  se insensitive b
1e80: 79 20 64 65 66 61 75 6c 74 20 62 65 63 61 75 73  y default becaus
1e90: 65 20 74 68 69 73 20 69 73 20 77 68 61 74 0a 20  e this is what. 
1ea0: 20 74 68 65 20 53 51 4c 20 73 74 61 6e 64 61 72   the SQL standar
1eb0: 64 20 72 65 71 75 69 72 65 73 2e 20 20 59 6f 75  d requires.  You
1ec0: 20 63 61 6e 20 63 68 61 6e 67 65 20 74 68 65 20   can change the 
1ed0: 64 65 66 61 75 6c 74 20 62 65 68 61 76 69 6f 72  default behavior
1ee0: 20 61 74 0a 20 20 63 6f 6d 70 69 6c 65 20 74 69   at.  compile ti
1ef0: 6d 65 20 62 79 20 75 73 69 6e 67 20 74 68 65 20  me by using the 
1f00: 2d 44 53 51 4c 49 54 45 5f 43 41 53 45 5f 53 45  -DSQLITE_CASE_SE
1f10: 4e 53 49 54 49 56 45 5f 4c 49 4b 45 20 63 6f 6d  NSITIVE_LIKE com
1f20: 6d 61 6e 64 2d 6c 69 6e 65 20 6f 70 74 69 6f 6e  mand-line option
1f30: 0a 20 20 74 6f 20 74 68 65 20 63 6f 6d 70 69 6c  .  to the compil
1f40: 65 72 2e 0a 7d 0a 50 41 52 41 47 52 41 50 48 20  er..}.PARAGRAPH 
1f50: 7b 0a 20 20 54 68 65 20 4c 49 4b 45 20 6f 70 74  {.  The LIKE opt
1f60: 69 6d 69 7a 61 74 69 6f 6e 20 6d 69 67 68 74 20  imization might 
1f70: 6f 63 63 75 72 20 69 66 20 74 68 65 20 63 6f 6c  occur if the col
1f80: 75 6d 6e 20 6e 61 6d 65 64 20 6f 6e 20 74 68 65  umn named on the
1f90: 20 6c 65 66 74 20 6f 66 20 74 68 65 0a 20 20 6f   left of the.  o
1fa0: 70 65 72 61 74 6f 72 20 75 73 65 73 20 74 68 65  perator uses the
1fb0: 20 42 49 4e 41 52 59 20 63 6f 6c 6c 61 74 69 6e   BINARY collatin
1fc0: 67 20 73 65 71 75 65 6e 63 65 20 28 77 68 69 63  g sequence (whic
1fd0: 68 20 69 73 20 74 68 65 20 64 65 66 61 75 6c 74  h is the default
1fe0: 29 20 61 6e 64 0a 20 20 63 61 73 65 5f 73 65 6e  ) and.  case_sen
1ff0: 73 69 74 69 76 65 5f 6c 69 6b 65 20 69 73 20 74  sitive_like is t
2000: 75 72 6e 65 64 20 6f 6e 2e 20 20 4f 72 20 74 68  urned on.  Or th
2010: 65 20 6f 70 74 69 6d 69 7a 61 74 69 6f 6e 20 6d  e optimization m
2020: 69 67 68 74 20 6f 63 63 75 72 20 69 66 0a 20 20  ight occur if.  
2030: 74 68 65 20 63 6f 6c 75 6d 6e 20 75 73 65 73 20  the column uses 
2040: 74 68 65 20 62 75 69 6c 74 2d 69 6e 20 4e 4f 43  the built-in NOC
2050: 41 53 45 20 63 6f 6c 6c 61 74 69 6e 67 20 73 65  ASE collating se
2060: 71 75 65 6e 63 65 20 61 6e 64 20 74 68 65 20 0a  quence and the .
2070: 20 20 63 61 73 65 5f 73 65 6e 73 69 74 69 76 65    case_sensitive
2080: 5f 6c 69 6b 65 20 6d 6f 64 65 20 69 73 20 6f 66  _like mode is of
2090: 66 2e 20 20 54 68 65 73 65 20 61 72 65 20 74 68  f.  These are th
20a0: 65 20 6f 6e 6c 79 20 74 77 6f 20 63 6f 6d 62 69  e only two combi
20b0: 6e 61 74 69 6f 6e 73 0a 20 20 75 6e 64 65 72 20  nations.  under 
20c0: 77 68 69 63 68 20 4c 49 4b 45 20 6f 70 65 72 61  which LIKE opera
20d0: 74 6f 72 73 20 77 69 6c 6c 20 62 65 20 6f 70 74  tors will be opt
20e0: 69 6d 69 7a 65 64 2e 20 20 49 66 20 74 68 65 20  imized.  If the 
20f0: 63 6f 6c 75 6d 6e 20 6f 6e 20 74 68 65 0a 20 20  column on the.  
2100: 72 69 67 68 74 2d 68 61 6e 64 20 73 69 64 65 20  right-hand side 
2110: 6f 66 20 74 68 65 20 4c 49 4b 45 20 6f 70 65 72  of the LIKE oper
2120: 61 74 6f 72 20 75 73 65 73 20 61 6e 79 20 63 6f  ator uses any co
2130: 6c 6c 61 74 69 6e 67 20 73 65 71 75 65 6e 63 65  llating sequence
2140: 20 6f 74 68 65 72 0a 20 20 74 68 61 6e 20 74 68   other.  than th
2150: 65 20 62 75 69 6c 74 2d 69 6e 20 42 49 4e 41 52  e built-in BINAR
2160: 59 20 61 6e 64 20 4e 4f 43 41 53 45 20 63 6f 6c  Y and NOCASE col
2170: 6c 61 74 69 6e 67 20 73 65 71 75 65 6e 63 65 73  lating sequences
2180: 2c 20 74 68 65 6e 20 6e 6f 20 6f 70 74 69 6d 69  , then no optimi
2190: 7a 61 74 69 6f 6e 73 0a 20 20 77 69 6c 6c 20 65  zations.  will e
21a0: 76 65 72 20 62 65 20 61 74 74 65 6d 70 74 65 64  ver be attempted
21b0: 20 6f 6e 20 74 68 65 20 4c 49 4b 45 20 6f 70 65   on the LIKE ope
21c0: 72 61 74 6f 72 2e 0a 7d 0a 50 41 52 41 47 52 41  rator..}.PARAGRA
21d0: 50 48 20 7b 0a 20 20 54 68 65 20 47 4c 4f 42 20  PH {.  The GLOB 
21e0: 6f 70 65 72 61 74 6f 72 20 69 73 20 61 6c 77 61  operator is alwa
21f0: 79 73 20 63 61 73 65 20 73 65 6e 73 69 74 69 76  ys case sensitiv
2200: 65 2e 20 20 54 68 65 20 63 6f 6c 75 6d 6e 20 6f  e.  The column o
2210: 6e 20 74 68 65 20 6c 65 66 74 20 73 69 64 65 0a  n the left side.
2220: 20 20 6f 66 20 74 68 65 20 47 4c 4f 42 20 6f 70    of the GLOB op
2230: 65 72 61 74 6f 72 20 6d 75 73 74 20 61 6c 77 61  erator must alwa
2240: 79 73 20 75 73 65 20 74 68 65 20 62 75 69 6c 74  ys use the built
2250: 2d 69 6e 20 42 49 4e 41 52 59 20 63 6f 6c 6c 61  -in BINARY colla
2260: 74 69 6e 67 20 73 65 71 75 65 6e 63 65 0a 20 20  ting sequence.  
2270: 6f 72 20 6e 6f 20 61 74 74 65 6d 70 74 20 77 69  or no attempt wi
2280: 6c 6c 20 62 65 20 6d 61 64 65 20 74 6f 20 6f 70  ll be made to op
2290: 74 69 6d 69 7a 65 20 74 68 61 74 20 6f 70 65 72  timize that oper
22a0: 61 74 6f 72 20 77 69 74 68 20 69 6e 64 69 63 65  ator with indice
22b0: 73 2e 0a 7d 0a 50 41 52 41 47 52 41 50 48 20 7b  s..}.PARAGRAPH {
22c0: 0a 20 20 54 68 65 20 72 69 67 68 74 2d 68 61 6e  .  The right-han
22d0: 64 20 73 69 64 65 20 6f 66 20 74 68 65 20 47 4c  d side of the GL
22e0: 4f 42 20 6f 72 20 4c 49 4b 45 20 6f 70 65 72 61  OB or LIKE opera
22f0: 74 6f 72 20 6d 75 73 74 20 62 65 20 61 20 6c 69  tor must be a li
2300: 74 65 72 61 6c 20 73 74 72 69 6e 67 0a 20 20 76  teral string.  v
2310: 61 6c 75 65 20 74 68 61 74 20 64 6f 65 73 20 6e  alue that does n
2320: 6f 74 20 62 65 67 69 6e 20 77 69 74 68 20 61 20  ot begin with a 
2330: 77 69 6c 64 63 61 72 64 2e 20 20 49 66 20 74 68  wildcard.  If th
2340: 65 20 72 69 67 68 74 2d 68 61 6e 64 20 73 69 64  e right-hand sid
2350: 65 20 69 73 20 61 0a 20 20 70 61 72 61 6d 65 74  e is a.  paramet
2360: 65 72 20 74 68 61 74 20 69 73 20 62 6f 75 6e 64  er that is bound
2370: 20 74 6f 20 61 20 73 74 72 69 6e 67 2c 20 74 68   to a string, th
2380: 65 6e 20 6e 6f 20 6f 70 74 69 6d 69 7a 61 74 69  en no optimizati
2390: 6f 6e 20 69 73 20 61 74 74 65 6d 70 74 65 64 2e  on is attempted.
23a0: 0a 20 20 49 66 20 74 68 65 20 72 69 67 68 74 2d  .  If the right-
23b0: 68 61 6e 64 20 73 69 64 65 20 62 65 67 69 6e 73  hand side begins
23c0: 20 77 69 74 68 20 61 20 77 69 6c 64 63 61 72 64   with a wildcard
23d0: 20 63 68 61 72 61 63 74 65 72 20 74 68 65 6e 20   character then 
23e0: 6e 6f 20 0a 20 20 6f 70 74 69 6d 69 7a 61 74 69  no .  optimizati
23f0: 6f 6e 20 69 73 20 61 74 74 65 6d 70 74 65 64 2e  on is attempted.
2400: 0a 7d 0a 50 41 52 41 47 52 41 50 48 20 7b 0a 20  .}.PARAGRAPH {. 
2410: 20 53 75 70 70 6f 73 65 20 74 68 65 20 69 6e 69   Suppose the ini
2420: 74 69 61 6c 20 73 65 71 75 65 6e 63 65 20 6f 66  tial sequence of
2430: 20 6e 6f 6e 2d 77 69 6c 64 63 61 72 64 20 63 68   non-wildcard ch
2440: 61 72 61 63 74 65 72 73 20 6f 6e 20 74 68 65 20  aracters on the 
2450: 72 69 67 68 74 2d 68 61 6e 64 0a 20 20 73 69 64  right-hand.  sid
2460: 65 20 6f 66 20 74 68 65 20 4c 49 4b 45 20 6f 72  e of the LIKE or
2470: 20 47 4c 4f 42 20 6f 70 65 72 61 74 6f 72 20 69   GLOB operator i
2480: 73 20 3c 69 3e 78 3c 2f 69 3e 2e 20 20 57 65 20  s <i>x</i>.  We 
2490: 61 72 65 20 75 73 69 6e 67 20 61 20 73 69 6e 67  are using a sing
24a0: 6c 65 20 0a 20 20 63 68 61 72 61 63 74 65 72 20  le .  character 
24b0: 74 6f 20 64 65 6e 6f 74 65 20 74 68 69 73 20 6e  to denote this n
24c0: 6f 6e 2d 77 69 6c 64 63 61 72 64 20 70 72 65 66  on-wildcard pref
24d0: 69 78 20 62 75 74 20 74 68 65 20 72 65 61 64 65  ix but the reade
24e0: 72 20 73 68 6f 75 6c 64 0a 20 20 75 6e 64 65 72  r should.  under
24f0: 73 74 61 6e 64 20 74 68 61 74 20 74 68 65 20 70  stand that the p
2500: 72 65 66 69 78 20 63 61 6e 20 63 6f 6e 73 69 73  refix can consis
2510: 74 20 6f 66 20 6d 6f 72 65 20 74 68 61 6e 20 31  t of more than 1
2520: 20 63 68 61 72 61 63 74 65 72 2e 0a 20 20 4c 65   character..  Le
2530: 74 20 3c 69 3e 79 3c 2f 69 3e 20 74 68 65 20 73  t <i>y</i> the s
2540: 6d 61 6c 6c 65 73 74 20 73 74 72 69 6e 67 20 74  mallest string t
2550: 68 61 74 20 69 73 20 74 68 65 20 73 61 6d 65 20  hat is the same 
2560: 6c 65 6e 67 74 68 20 61 73 20 2f 78 2f 20 62 75  length as /x/ bu
2570: 74 20 77 68 69 63 68 0a 20 20 63 6f 6d 70 61 72  t which.  compar
2580: 65 73 20 67 72 65 61 74 65 72 20 74 68 61 6e 20  es greater than 
2590: 3c 69 3e 78 3c 2f 69 3e 2e 20 20 46 6f 72 20 65  <i>x</i>.  For e
25a0: 78 61 6d 70 6c 65 2c 20 69 66 20 3c 69 3e 78 3c  xample, if <i>x<
25b0: 2f 69 3e 20 69 73 20 2a 68 65 6c 6c 6f 2a 20 74  /i> is *hello* t
25c0: 68 65 6e 0a 20 20 3c 69 3e 79 3c 2f 69 3e 20 77  hen.  <i>y</i> w
25d0: 6f 75 6c 64 20 62 65 20 2a 68 65 6c 6c 70 2a 2e  ould be *hellp*.
25e0: 0a 20 20 54 68 65 20 4c 49 4b 45 20 61 6e 64 20  .  The LIKE and 
25f0: 47 4c 4f 42 20 6f 70 74 69 6d 69 7a 61 74 69 6f  GLOB optimizatio
2600: 6e 73 20 63 6f 6e 73 69 73 74 20 6f 66 20 61 64  ns consist of ad
2610: 64 69 6e 67 20 74 77 6f 20 76 69 72 74 75 61 6c  ding two virtual
2620: 20 74 65 72 6d 73 0a 20 20 6c 69 6b 65 20 74 68   terms.  like th
2630: 69 73 3a 0a 7d 0a 53 59 4e 54 41 58 20 7b 0a 20  is:.}.SYNTAX {. 
2640: 20 2f 63 6f 6c 75 6d 6e 2f 20 3e 3d 20 2f 78 2f   /column/ >= /x/
2650: 20 41 4e 44 20 2f 63 6f 6c 75 6d 6e 2f 20 3c 20   AND /column/ < 
2660: 2f 79 2f 0a 7d 0a 50 41 52 41 47 52 41 50 48 20  /y/.}.PARAGRAPH 
2670: 7b 0a 20 20 55 6e 64 65 72 20 6d 6f 73 74 20 63  {.  Under most c
2680: 69 72 63 75 6d 73 74 61 6e 63 65 73 2c 20 74 68  ircumstances, th
2690: 65 20 6f 72 69 67 69 6e 61 6c 20 4c 49 4b 45 20  e original LIKE 
26a0: 6f 72 20 47 4c 4f 42 20 6f 70 65 72 61 74 6f 72  or GLOB operator
26b0: 20 69 73 20 73 74 69 6c 6c 0a 20 20 74 65 73 74   is still.  test
26c0: 65 64 20 61 67 61 69 6e 73 74 20 65 61 63 68 20  ed against each 
26d0: 69 6e 70 75 74 20 72 6f 77 20 65 76 65 6e 20 69  input row even i
26e0: 66 20 74 68 65 20 76 69 72 74 75 61 6c 20 74 65  f the virtual te
26f0: 72 6d 73 20 61 72 65 20 75 73 65 64 20 74 6f 0a  rms are used to.
2700: 20 20 63 6f 6e 73 74 72 61 69 6e 20 61 6e 20 69    constrain an i
2710: 6e 64 65 78 2e 20 20 54 68 69 73 20 69 73 20 62  ndex.  This is b
2720: 65 63 61 75 73 65 20 77 65 20 64 6f 20 6e 6f 74  ecause we do not
2730: 20 6b 6e 6f 77 20 77 68 61 74 20 61 64 64 69 74   know what addit
2740: 69 6f 6e 61 6c 0a 20 20 63 6f 6e 73 74 72 61 69  ional.  constrai
2750: 6e 74 73 20 6d 61 79 20 62 65 20 69 6d 70 6f 73  nts may be impos
2760: 65 64 20 62 79 20 63 68 61 72 61 63 74 65 72 73  ed by characters
2770: 20 74 6f 20 74 68 65 20 72 69 67 68 74 0a 20 20   to the right.  
2780: 6f 66 20 74 68 65 20 3c 69 3e 78 3c 2f 69 3e 20  of the <i>x</i> 
2790: 70 72 65 66 69 78 2e 20 20 48 6f 77 65 76 65 72  prefix.  However
27a0: 2c 20 69 66 20 74 68 65 72 65 20 69 73 20 6f 6e  , if there is on
27b0: 6c 79 20 61 20 73 69 6e 67 6c 65 20 67 6c 6f 62  ly a single glob
27c0: 61 6c 20 77 69 6c 64 63 61 72 64 0a 20 20 74 6f  al wildcard.  to
27d0: 20 74 68 65 20 72 69 67 68 74 20 6f 66 20 3c 69   the right of <i
27e0: 3e 78 3c 2f 69 3e 2c 20 74 68 65 6e 20 74 68 65  >x</i>, then the
27f0: 20 6f 72 69 67 69 6e 61 6c 20 4c 49 4b 45 20 6f   original LIKE o
2800: 72 20 47 4c 4f 42 20 74 65 73 74 20 69 73 20 64  r GLOB test is d
2810: 69 73 61 62 6c 65 64 2e 0a 20 20 49 6e 20 6f 74  isabled..  In ot
2820: 68 65 72 20 77 6f 72 64 73 2c 20 69 66 20 74 68  her words, if th
2830: 65 20 70 61 74 74 65 72 6e 20 69 73 20 6c 69 6b  e pattern is lik
2840: 65 20 74 68 69 73 3a 0a 7d 0a 53 59 4e 54 41 58  e this:.}.SYNTAX
2850: 20 7b 0a 20 20 2f 63 6f 6c 75 6d 6e 2f 20 4c 49   {.  /column/ LI
2860: 4b 45 20 2f 78 2f 25 0a 20 20 2f 63 6f 6c 75 6d  KE /x/%.  /colum
2870: 6e 2f 20 47 4c 4f 42 20 2f 78 2f 2a 0a 7d 0a 50  n/ GLOB /x/*.}.P
2880: 41 52 41 47 52 41 50 48 20 7b 0a 20 20 54 68 65  ARAGRAPH {.  The
2890: 6e 20 74 68 65 20 6f 72 69 67 69 6e 61 6c 20 4c  n the original L
28a0: 49 4b 45 20 6f 72 20 47 4c 4f 42 20 74 65 73 74  IKE or GLOB test
28b0: 73 20 61 72 65 20 64 69 73 61 62 6c 65 64 20 77  s are disabled w
28c0: 68 65 6e 20 74 68 65 20 76 69 72 74 75 61 6c 0a  hen the virtual.
28d0: 20 20 74 65 72 6d 73 20 63 6f 6e 73 74 72 61 69    terms constrai
28e0: 6e 20 61 6e 20 69 6e 64 65 78 20 62 65 63 61 75  n an index becau
28f0: 73 65 20 69 6e 20 74 68 61 74 20 63 61 73 65 20  se in that case 
2900: 77 65 20 6b 6e 6f 77 20 74 68 61 74 20 61 6c 6c  we know that all
2910: 20 6f 66 20 74 68 65 0a 20 20 72 6f 77 73 20 73   of the.  rows s
2920: 65 6c 65 63 74 65 64 20 62 79 20 74 68 65 20 69  elected by the i
2930: 6e 64 65 78 20 77 69 6c 6c 20 70 61 73 73 20 74  ndex will pass t
2940: 68 65 20 4c 49 4b 45 20 6f 72 20 47 4c 4f 42 20  he LIKE or GLOB 
2950: 74 65 73 74 2e 0a 7d 0a 0a 48 45 41 44 49 4e 47  test..}..HEADING
2960: 20 31 20 7b 4a 6f 69 6e 73 7d 20 6a 6f 69 6e 73   1 {Joins} joins
2970: 0a 0a 50 41 52 41 47 52 41 50 48 20 7b 0a 20 20  ..PARAGRAPH {.  
2980: 54 68 65 20 63 75 72 72 65 6e 74 20 69 6d 70 6c  The current impl
2990: 65 6d 65 6e 74 61 74 69 6f 6e 20 6f 66 20 0a 20  ementation of . 
29a0: 20 53 51 4c 69 74 65 20 75 73 65 73 20 6f 6e 6c   SQLite uses onl
29b0: 79 20 6c 6f 6f 70 20 6a 6f 69 6e 73 2e 20 20 54  y loop joins.  T
29c0: 68 61 74 20 69 73 20 74 6f 20 73 61 79 2c 20 6a  hat is to say, j
29d0: 6f 69 6e 73 20 61 72 65 20 69 6d 70 6c 65 6d 65  oins are impleme
29e0: 6e 74 65 64 20 61 73 0a 20 20 6e 65 73 74 65 64  nted as.  nested
29f0: 20 6c 6f 6f 70 73 2e 0a 7d 0a 50 41 52 41 47 52   loops..}.PARAGR
2a00: 41 50 48 20 7b 0a 20 20 54 68 65 20 64 65 66 61  APH {.  The defa
2a10: 75 6c 74 20 6f 72 64 65 72 20 6f 66 20 74 68 65  ult order of the
2a20: 20 6e 65 73 74 65 64 20 6c 6f 6f 70 73 20 69 6e   nested loops in
2a30: 20 61 20 6a 6f 69 6e 20 69 73 20 66 6f 72 20 74   a join is for t
2a40: 68 65 20 6c 65 66 74 2d 6d 6f 73 74 0a 20 20 74  he left-most.  t
2a50: 61 62 6c 65 20 69 6e 20 74 68 65 20 46 52 4f 4d  able in the FROM
2a60: 20 63 6c 61 75 73 65 20 74 6f 20 66 6f 72 6d 20   clause to form 
2a70: 74 68 65 20 6f 75 74 65 72 20 6c 6f 6f 70 20 61  the outer loop a
2a80: 6e 64 20 74 68 65 20 72 69 67 68 74 2d 6d 6f 73  nd the right-mos
2a90: 74 0a 20 20 74 61 62 6c 65 20 74 6f 20 66 6f 72  t.  table to for
2aa0: 6d 20 74 68 65 20 69 6e 6e 65 72 20 6c 6f 6f 70  m the inner loop
2ab0: 2e 0a 20 20 48 6f 77 65 76 65 72 2c 20 53 51 4c  ..  However, SQL
2ac0: 69 74 65 20 77 69 6c 6c 20 6e 65 73 74 20 74 68  ite will nest th
2ad0: 65 20 6c 6f 6f 70 73 20 69 6e 20 61 20 64 69 66  e loops in a dif
2ae0: 66 65 72 65 6e 74 20 6f 72 64 65 72 20 69 66 20  ferent order if 
2af0: 64 6f 69 6e 67 20 73 6f 0a 20 20 77 69 6c 6c 20  doing so.  will 
2b00: 68 65 6c 70 20 69 74 20 74 6f 20 73 65 6c 65 63  help it to selec
2b10: 74 20 62 65 74 74 65 72 20 69 6e 64 69 63 65 73  t better indices
2b20: 2e 0a 7d 0a 50 41 52 41 47 52 41 50 48 20 7b 0a  ..}.PARAGRAPH {.
2b30: 20 20 49 6e 6e 65 72 20 6a 6f 69 6e 73 20 63 61    Inner joins ca
2b40: 6e 20 62 65 20 66 72 65 65 6c 79 20 72 65 6f 72  n be freely reor
2b50: 64 65 72 65 64 2e 20 20 48 6f 77 65 76 65 72 20  dered.  However 
2b60: 61 20 6c 65 66 74 20 6f 75 74 65 72 20 6a 6f 69  a left outer joi
2b70: 6e 20 69 73 0a 20 20 6e 65 69 74 68 65 72 20 63  n is.  neither c
2b80: 6f 6d 6d 75 74 61 74 69 76 65 20 6e 6f 72 20 61  ommutative nor a
2b90: 73 73 6f 63 69 61 74 69 76 65 20 61 6e 64 20 68  ssociative and h
2ba0: 65 6e 63 65 20 77 69 6c 6c 20 6e 6f 74 20 62 65  ence will not be
2bb0: 20 72 65 6f 72 64 65 72 65 64 2e 0a 20 20 49 6e   reordered..  In
2bc0: 6e 65 72 20 6a 6f 69 6e 73 20 74 6f 20 74 68 65  ner joins to the
2bd0: 20 6c 65 66 74 20 61 6e 64 20 72 69 67 68 74 20   left and right 
2be0: 6f 66 20 74 68 65 20 6f 75 74 65 72 20 6a 6f 69  of the outer joi
2bf0: 6e 20 6d 69 67 68 74 20 62 65 20 72 65 6f 72 64  n might be reord
2c00: 65 72 65 64 0a 20 20 69 66 20 74 68 65 20 6f 70  ered.  if the op
2c10: 74 69 6d 69 7a 65 72 20 74 68 69 6e 6b 73 20 74  timizer thinks t
2c20: 68 61 74 20 69 73 20 61 64 76 61 6e 74 61 67 65  hat is advantage
2c30: 6f 75 73 20 62 75 74 20 74 68 65 20 6f 75 74 65  ous but the oute
2c40: 72 20 6a 6f 69 6e 73 20 61 72 65 0a 20 20 61 6c  r joins are.  al
2c50: 77 61 79 73 20 65 76 61 6c 75 61 74 65 64 20 69  ways evaluated i
2c60: 6e 20 74 68 65 20 6f 72 64 65 72 20 69 6e 20 77  n the order in w
2c70: 68 69 63 68 20 74 68 65 79 20 6f 63 63 75 72 2e  hich they occur.
2c80: 0a 7d 0a 50 41 52 41 47 52 41 50 48 20 7b 0a 20  .}.PARAGRAPH {. 
2c90: 20 57 68 65 6e 20 73 65 6c 65 63 74 69 6e 67 20   When selecting 
2ca0: 74 68 65 20 6f 72 64 65 72 20 6f 66 20 74 61 62  the order of tab
2cb0: 6c 65 73 20 69 6e 20 61 20 6a 6f 69 6e 2c 20 53  les in a join, S
2cc0: 51 4c 69 74 65 20 75 73 65 73 20 61 20 67 72 65  QLite uses a gre
2cd0: 65 64 79 0a 20 20 61 6c 67 6f 72 69 74 68 6d 20  edy.  algorithm 
2ce0: 74 68 61 74 20 72 75 6e 73 20 69 6e 20 70 6f 6c  that runs in pol
2cf0: 79 6e 6f 6d 69 61 6c 20 74 69 6d 65 2e 0a 7d 0a  ynomial time..}.
2d00: 50 41 52 41 47 52 41 50 48 20 7b 0a 20 20 54 68  PARAGRAPH {.  Th
2d10: 65 20 4f 4e 20 61 6e 64 20 55 53 49 4e 47 20 63  e ON and USING c
2d20: 6c 61 75 73 65 73 20 6f 66 20 61 20 6a 6f 69 6e  lauses of a join
2d30: 20 61 72 65 20 63 6f 6e 76 65 72 74 65 64 20 69   are converted i
2d40: 6e 74 6f 20 61 64 64 69 74 69 6f 6e 61 6c 0a 20  nto additional. 
2d50: 20 74 65 72 6d 73 20 6f 66 20 74 68 65 20 57 48   terms of the WH
2d60: 45 52 45 20 63 6c 61 75 73 65 20 70 72 69 6f 72  ERE clause prior
2d70: 20 74 6f 20 57 48 45 52 45 20 63 6c 61 75 73 65   to WHERE clause
2d80: 20 61 6e 61 6c 79 73 69 73 20 64 65 73 63 72 69   analysis descri
2d90: 62 65 64 0a 20 20 61 62 6f 76 65 20 69 6e 20 70  bed.  above in p
2da0: 61 72 61 67 72 61 70 68 20 31 2e 30 2e 20 20 54  aragraph 1.0.  T
2db0: 68 75 73 0a 20 20 77 69 74 68 20 53 51 4c 69 74  hus.  with SQLit
2dc0: 65 2c 20 74 68 65 72 65 20 69 73 20 6e 6f 20 61  e, there is no a
2dd0: 64 76 61 6e 74 61 67 65 20 74 6f 20 75 73 65 20  dvantage to use 
2de0: 74 68 65 20 6e 65 77 65 72 20 53 51 4c 39 32 20  the newer SQL92 
2df0: 6a 6f 69 6e 20 73 79 6e 74 61 78 0a 20 20 6f 76  join syntax.  ov
2e00: 65 72 20 74 68 65 20 6f 6c 64 65 72 20 53 51 4c  er the older SQL
2e10: 38 39 20 63 6f 6d 6d 61 2d 6a 6f 69 6e 20 73 79  89 comma-join sy
2e20: 6e 74 61 78 2e 20 20 54 68 65 79 20 62 6f 74 68  ntax.  They both
2e30: 20 65 6e 64 20 75 70 20 61 63 63 6f 6d 70 6c 69   end up accompli
2e40: 73 68 69 6e 67 0a 20 20 65 78 61 63 74 6c 79 20  shing.  exactly 
2e50: 74 68 65 20 73 61 6d 65 20 74 68 69 6e 67 2e 0a  the same thing..
2e60: 7d 0a 50 41 52 41 47 52 41 50 48 20 7b 0a 20 20  }.PARAGRAPH {.  
2e70: 4a 6f 69 6e 20 72 65 6f 72 64 65 72 69 6e 67 20  Join reordering 
2e80: 69 73 20 61 75 74 6f 6d 61 74 69 63 20 61 6e 64  is automatic and
2e90: 20 75 73 75 61 6c 6c 79 20 77 6f 72 6b 73 20 77   usually works w
2ea0: 65 6c 6c 20 65 6e 6f 75 67 68 20 74 68 61 74 0a  ell enough that.
2eb0: 20 20 70 72 6f 67 72 61 6d 6d 65 72 20 64 6f 20    programmer do 
2ec0: 6e 6f 74 20 68 61 76 65 20 74 6f 20 74 68 69 6e  not have to thin
2ed0: 6b 20 61 62 6f 75 74 20 69 74 2e 20 20 42 75 74  k about it.  But
2ee0: 20 6f 63 63 61 73 69 6f 6e 61 6c 6c 79 20 73 6f   occasionally so
2ef0: 6d 65 0a 20 20 68 69 6e 74 73 20 66 72 6f 6d 20  me.  hints from 
2f00: 74 68 65 20 70 72 6f 67 72 61 6d 6d 65 72 20 61  the programmer a
2f10: 72 65 20 6e 65 65 64 65 64 2e 20 20 46 6f 72 20  re needed.  For 
2f20: 61 20 64 65 73 63 72 69 70 74 69 6f 6e 20 6f 66  a description of
2f30: 20 77 68 65 6e 0a 20 20 68 69 6e 74 73 20 6d 69   when.  hints mi
2f40: 67 68 74 20 62 65 20 6e 65 63 65 73 73 61 72 79  ght be necessary
2f50: 20 61 6e 64 20 68 6f 77 20 74 6f 20 70 72 6f 76   and how to prov
2f60: 69 64 65 20 74 68 6f 73 65 20 68 69 6e 74 73 2c  ide those hints,
2f70: 20 73 65 65 20 74 68 65 0a 20 20 3c 61 20 68 72   see the.  <a hr
2f80: 65 66 3d 22 68 74 74 70 3a 2f 2f 77 77 77 2e 73  ef="http://www.s
2f90: 71 6c 69 74 65 2e 6f 72 67 2f 63 76 73 74 72 61  qlite.org/cvstra
2fa0: 63 2f 77 69 6b 69 3f 70 3d 51 75 65 72 79 50 6c  c/wiki?p=QueryPl
2fb0: 61 6e 73 22 3e 51 75 65 72 79 50 6c 61 6e 73 3c  ans">QueryPlans<
2fc0: 2f 61 3e 0a 20 20 70 61 67 65 20 69 6e 20 74 68  /a>.  page in th
2fd0: 65 20 57 69 6b 69 2e 0a 7d 0a 0a 48 45 41 44 49  e Wiki..}..HEADI
2fe0: 4e 47 20 31 20 7b 43 68 6f 6f 73 69 6e 67 20 62  NG 1 {Choosing b
2ff0: 65 74 77 65 65 6e 20 6d 75 6c 74 69 70 6c 65 20  etween multiple 
3000: 69 6e 64 69 63 65 73 7d 20 6d 75 6c 74 69 5f 69  indices} multi_i
3010: 6e 64 65 78 0a 0a 50 41 52 41 47 52 41 50 48 20  ndex..PARAGRAPH 
3020: 7b 0a 20 20 45 61 63 68 20 74 61 62 6c 65 20 69  {.  Each table i
3030: 6e 20 74 68 65 20 46 52 4f 4d 20 63 6c 61 75 73  n the FROM claus
3040: 65 20 6f 66 20 61 20 71 75 65 72 79 20 63 61 6e  e of a query can
3050: 20 75 73 65 20 61 74 20 6d 6f 73 74 20 6f 6e 65   use at most one
3060: 20 69 6e 64 65 78 2c 0a 20 20 61 6e 64 20 53 51   index,.  and SQ
3070: 4c 69 74 65 20 73 74 72 69 76 65 73 20 74 6f 20  Lite strives to 
3080: 75 73 65 20 61 74 20 6c 65 61 73 74 20 6f 6e 65  use at least one
3090: 20 69 6e 64 65 78 20 6f 6e 20 65 61 63 68 20 74   index on each t
30a0: 61 62 6c 65 2e 20 20 53 6f 6d 65 74 69 6d 65 73  able.  Sometimes
30b0: 2c 0a 20 20 74 77 6f 20 6f 72 20 6d 6f 72 65 20  ,.  two or more 
30c0: 69 6e 64 69 63 65 73 20 6d 69 67 68 74 20 62 65  indices might be
30d0: 20 63 61 6e 64 69 64 61 74 65 73 20 66 6f 72 20   candidates for 
30e0: 75 73 65 20 6f 6e 20 61 20 73 69 6e 67 6c 65 20  use on a single 
30f0: 74 61 62 6c 65 2e 0a 20 20 46 6f 72 20 65 78 61  table..  For exa
3100: 6d 70 6c 65 3a 0a 7d 0a 43 4f 44 45 20 7b 0a 20  mple:.}.CODE {. 
3110: 20 43 52 45 41 54 45 20 54 41 42 4c 45 20 65 78   CREATE TABLE ex
3120: 32 28 78 2c 79 2c 7a 29 3b 0a 20 20 43 52 45 41  2(x,y,z);.  CREA
3130: 54 45 20 49 4e 44 45 58 20 65 78 32 69 31 20 4f  TE INDEX ex2i1 O
3140: 4e 20 65 78 32 28 78 29 3b 0a 20 20 43 52 45 41  N ex2(x);.  CREA
3150: 54 45 20 49 4e 44 45 58 20 65 78 32 69 32 20 4f  TE INDEX ex2i2 O
3160: 4e 20 65 78 32 28 79 29 3b 0a 20 20 53 45 4c 45  N ex2(y);.  SELE
3170: 43 54 20 7a 20 46 52 4f 4d 20 65 78 32 20 57 48  CT z FROM ex2 WH
3180: 45 52 45 20 78 3d 35 20 41 4e 44 20 79 3d 36 3b  ERE x=5 AND y=6;
3190: 0a 7d 0a 50 41 52 41 47 52 41 50 48 20 7b 0a 20  .}.PARAGRAPH {. 
31a0: 20 46 6f 72 20 74 68 65 20 53 45 4c 45 43 54 20   For the SELECT 
31b0: 73 74 61 74 65 6d 65 6e 74 20 61 62 6f 76 65 2c  statement above,
31c0: 20 74 68 65 20 6f 70 74 69 6d 69 7a 65 72 20 63   the optimizer c
31d0: 61 6e 20 75 73 65 20 74 68 65 20 65 78 32 69 31  an use the ex2i1
31e0: 20 69 6e 64 65 78 0a 20 20 74 6f 20 6c 6f 6f 6b   index.  to look
31f0: 75 70 20 72 6f 77 73 20 6f 66 20 65 78 32 20 74  up rows of ex2 t
3200: 68 61 74 20 63 6f 6e 74 61 69 6e 20 78 3d 35 20  hat contain x=5 
3210: 61 6e 64 20 74 68 65 6e 20 74 65 73 74 20 65 61  and then test ea
3220: 63 68 20 72 6f 77 20 61 67 61 69 6e 73 74 0a 20  ch row against. 
3230: 20 74 68 65 20 79 3d 36 20 74 65 72 6d 2e 20 20   the y=6 term.  
3240: 4f 72 20 69 74 20 63 61 6e 20 75 73 65 20 74 68  Or it can use th
3250: 65 20 65 78 32 69 32 20 69 6e 64 65 78 20 74 6f  e ex2i2 index to
3260: 20 6c 6f 6f 6b 75 70 20 72 6f 77 73 0a 20 20 6f   lookup rows.  o
3270: 66 20 65 78 32 20 74 68 61 74 20 63 6f 6e 74 61  f ex2 that conta
3280: 69 6e 20 79 3d 36 20 74 68 65 6e 20 74 65 73 74  in y=6 then test
3290: 20 65 61 63 68 20 6f 66 20 74 68 6f 73 65 20 72   each of those r
32a0: 6f 77 73 20 61 67 61 69 6e 73 74 20 74 68 65 0a  ows against the.
32b0: 20 20 78 3d 35 20 74 65 72 6d 2e 0a 7d 0a 50 41    x=5 term..}.PA
32c0: 52 41 47 52 41 50 48 20 7b 0a 20 20 57 68 65 6e  RAGRAPH {.  When
32d0: 20 66 61 63 65 64 20 77 69 74 68 20 61 20 63 68   faced with a ch
32e0: 6f 69 63 65 20 6f 66 20 74 77 6f 20 6f 72 20 6d  oice of two or m
32f0: 6f 72 65 20 69 6e 64 69 63 65 73 2c 20 53 51 4c  ore indices, SQL
3300: 69 74 65 20 74 72 69 65 73 20 74 6f 20 65 73 74  ite tries to est
3310: 69 6d 61 74 65 0a 20 20 74 68 65 20 74 6f 74 61  imate.  the tota
3320: 6c 20 61 6d 6f 75 6e 74 20 6f 66 20 77 6f 72 6b  l amount of work
3330: 20 6e 65 65 64 65 64 20 74 6f 20 70 65 72 66 6f   needed to perfo
3340: 72 6d 20 74 68 65 20 71 75 65 72 79 20 75 73 69  rm the query usi
3350: 6e 67 20 65 61 63 68 20 6f 70 74 69 6f 6e 2e 0a  ng each option..
3360: 20 20 49 74 20 74 68 65 6e 20 73 65 6c 65 63 74    It then select
3370: 73 20 74 68 65 20 6f 70 74 69 6f 6e 20 74 68 61  s the option tha
3380: 74 20 67 69 76 65 73 20 74 68 65 20 6c 65 61 73  t gives the leas
3390: 74 20 65 73 74 69 6d 61 74 65 64 20 77 6f 72 6b  t estimated work
33a0: 2e 0a 7d 0a 50 41 52 41 47 52 41 50 48 20 7b 0a  ..}.PARAGRAPH {.
33b0: 20 20 54 6f 20 68 65 6c 70 20 74 68 65 20 6f 70    To help the op
33c0: 74 69 6d 69 7a 65 72 20 67 65 74 20 61 20 6d 6f  timizer get a mo
33d0: 72 65 20 61 63 63 75 72 61 74 65 20 65 73 74 69  re accurate esti
33e0: 6d 61 74 65 20 6f 66 20 74 68 65 20 77 6f 72 6b  mate of the work
33f0: 20 69 6e 76 6f 6c 76 65 64 0a 20 20 69 6e 20 75   involved.  in u
3400: 73 69 6e 67 20 76 61 72 69 6f 75 73 20 69 6e 64  sing various ind
3410: 69 63 65 73 2c 20 74 68 65 20 75 73 65 72 20 6d  ices, the user m
3420: 61 79 20 6f 70 74 69 6f 6e 61 6c 20 72 75 6e 20  ay optional run 
3430: 74 68 65 20 41 4e 41 4c 59 5a 45 20 63 6f 6d 6d  the ANALYZE comm
3440: 61 6e 64 2e 0a 20 20 54 68 65 20 41 4e 41 4c 59  and..  The ANALY
3450: 5a 45 20 63 6f 6d 6d 61 6e 64 20 73 63 61 6e 73  ZE command scans
3460: 20 61 6c 6c 20 69 6e 64 69 63 65 73 20 6f 66 20   all indices of 
3470: 64 61 74 61 62 61 73 65 20 77 68 65 72 65 20 74  database where t
3480: 68 65 72 65 20 6d 69 67 68 74 0a 20 20 62 65 20  here might.  be 
3490: 61 20 63 68 6f 69 63 65 20 62 65 74 77 65 65 6e  a choice between
34a0: 20 74 77 6f 20 6f 72 20 6d 6f 72 65 20 69 6e 64   two or more ind
34b0: 69 63 65 73 20 61 6e 64 20 67 61 74 68 65 72 73  ices and gathers
34c0: 20 73 74 61 74 69 73 74 69 63 73 20 6f 6e 20 74   statistics on t
34d0: 68 65 0a 20 20 73 65 6c 65 63 74 69 76 65 6e 65  he.  selectivene
34e0: 73 73 20 6f 66 20 74 68 6f 73 65 20 69 6e 64 69  ss of those indi
34f0: 63 65 73 2e 20 20 54 68 65 20 72 65 73 75 6c 74  ces.  The result
3500: 73 20 6f 66 20 74 68 69 73 20 73 63 61 6e 20 61  s of this scan a
3510: 72 65 20 73 74 6f 72 65 64 0a 20 20 69 6e 20 74  re stored.  in t
3520: 68 65 20 73 71 6c 69 74 65 5f 73 74 61 74 31 20  he sqlite_stat1 
3530: 74 61 62 6c 65 2e 0a 20 20 54 68 65 20 63 6f 6e  table..  The con
3540: 74 65 6e 74 73 20 6f 66 20 74 68 65 20 73 71 6c  tents of the sql
3550: 69 74 65 5f 73 74 61 74 31 20 74 61 62 6c 65 20  ite_stat1 table 
3560: 61 72 65 20 6e 6f 74 20 75 70 64 61 74 65 64 20  are not updated 
3570: 61 73 20 74 68 65 20 64 61 74 61 62 61 73 65 0a  as the database.
3580: 20 20 63 68 61 6e 67 65 73 20 73 6f 20 61 66 74    changes so aft
3590: 65 72 20 6d 61 6b 69 6e 67 20 73 69 67 6e 69 66  er making signif
35a0: 69 63 61 6e 74 20 63 68 61 6e 67 65 73 20 69 74  icant changes it
35b0: 20 6d 69 67 68 74 20 62 65 20 70 72 75 64 65 6e   might be pruden
35c0: 74 20 74 6f 0a 20 20 72 65 72 75 6e 20 41 4e 41  t to.  rerun ANA
35d0: 4c 59 5a 45 2e 0a 20 20 54 68 65 20 72 65 73 75  LYZE..  The resu
35e0: 6c 74 73 20 6f 66 20 61 6e 20 41 4e 41 4c 59 5a  lts of an ANALYZ
35f0: 45 20 63 6f 6d 6d 61 6e 64 20 61 72 65 20 6f 6e  E command are on
3600: 6c 79 20 61 76 61 69 6c 61 62 6c 65 20 74 6f 20  ly available to 
3610: 64 61 74 61 62 61 73 65 20 63 6f 6e 6e 65 63 74  database connect
3620: 69 6f 6e 73 0a 20 20 74 68 61 74 20 61 72 65 20  ions.  that are 
3630: 6f 70 65 6e 65 64 20 61 66 74 65 72 20 74 68 65  opened after the
3640: 20 41 4e 41 4c 59 5a 45 20 63 6f 6d 6d 61 6e 64   ANALYZE command
3650: 20 63 6f 6d 70 6c 65 74 65 73 2e 0a 7d 0a 50 41   completes..}.PA
3660: 52 41 47 52 41 50 48 20 7b 0a 20 20 4f 6e 63 65  RAGRAPH {.  Once
3670: 20 63 72 65 61 74 65 64 2c 20 74 68 65 20 73 71   created, the sq
3680: 6c 69 74 65 5f 73 74 61 74 31 20 74 61 62 6c 65  lite_stat1 table
3690: 20 63 61 6e 6e 6f 74 20 62 65 20 64 72 6f 70 70   cannot be dropp
36a0: 65 64 2e 20 20 42 75 74 20 69 74 73 0a 20 20 63  ed.  But its.  c
36b0: 6f 6e 74 65 6e 74 20 63 61 6e 20 62 65 20 76 69  ontent can be vi
36c0: 65 77 65 64 2c 20 6d 6f 64 69 66 69 65 64 2c 20  ewed, modified, 
36d0: 6f 72 20 65 72 61 73 65 64 2e 20 20 45 72 61 73  or erased.  Eras
36e0: 69 6e 67 20 74 68 65 20 65 6e 74 69 72 65 20 63  ing the entire c
36f0: 6f 6e 74 65 6e 74 0a 20 20 6f 66 20 74 68 65 20  ontent.  of the 
3700: 73 71 6c 69 74 65 5f 73 74 61 74 31 20 74 61 62  sqlite_stat1 tab
3710: 6c 65 20 68 61 73 20 74 68 65 20 65 66 66 65 63  le has the effec
3720: 74 20 6f 66 20 75 6e 64 6f 69 6e 67 20 74 68 65  t of undoing the
3730: 20 41 4e 41 4c 59 5a 45 20 63 6f 6d 6d 61 6e 64   ANALYZE command
3740: 2e 0a 20 20 43 68 61 6e 67 69 6e 67 20 74 68 65  ..  Changing the
3750: 20 63 6f 6e 74 65 6e 74 20 6f 66 20 74 68 65 20   content of the 
3760: 73 71 6c 69 74 65 5f 73 74 61 74 31 20 74 61 62  sqlite_stat1 tab
3770: 6c 65 20 63 61 6e 20 67 65 74 20 74 68 65 20 6f  le can get the o
3780: 70 74 69 6d 69 7a 65 72 0a 20 20 64 65 65 70 6c  ptimizer.  deepl
3790: 79 20 63 6f 6e 66 75 73 65 64 20 61 6e 64 20 63  y confused and c
37a0: 61 75 73 65 20 69 74 20 74 6f 20 6d 61 6b 65 20  ause it to make 
37b0: 73 69 6c 6c 79 20 69 6e 64 65 78 20 63 68 6f 69  silly index choi
37c0: 63 65 73 2e 20 20 4d 61 6b 69 6e 67 0a 20 20 75  ces.  Making.  u
37d0: 70 64 61 74 65 73 20 74 6f 20 74 68 65 20 73 71  pdates to the sq
37e0: 6c 69 74 65 5f 73 74 61 74 31 20 74 61 62 6c 65  lite_stat1 table
37f0: 20 28 65 78 63 65 70 74 20 62 79 20 72 75 6e 6e   (except by runn
3800: 69 6e 67 20 41 4e 41 4c 59 5a 45 29 20 69 73 0a  ing ANALYZE) is.
3810: 20 20 6e 6f 74 20 72 65 63 6f 6d 6d 65 6e 64 65    not recommende
3820: 64 2e 0a 7d 0a 50 41 52 41 47 52 41 50 48 20 7b  d..}.PARAGRAPH {
3830: 0a 20 20 54 65 72 6d 73 20 6f 66 20 74 68 65 20  .  Terms of the 
3840: 57 48 45 52 45 20 63 6c 61 75 73 65 20 63 61 6e  WHERE clause can
3850: 20 62 65 20 6d 61 6e 75 61 6c 6c 79 20 64 69 73   be manually dis
3860: 71 75 61 6c 69 66 69 65 64 20 66 6f 72 20 75 73  qualified for us
3870: 65 20 77 69 74 68 0a 20 20 69 6e 64 69 63 65 73  e with.  indices
3880: 20 62 79 20 70 72 65 70 65 6e 64 69 6e 67 20 61   by prepending a
3890: 20 75 6e 61 72 79 20 2a 2b 2a 20 6f 70 65 72 61   unary *+* opera
38a0: 74 6f 72 20 74 6f 20 74 68 65 20 63 6f 6c 75 6d  tor to the colum
38b0: 6e 20 6e 61 6d 65 2e 20 20 54 68 65 0a 20 20 75  n name.  The.  u
38c0: 6e 61 72 79 20 2a 2b 2a 20 69 73 20 61 20 6e 6f  nary *+* is a no
38d0: 2d 6f 70 20 61 6e 64 20 77 69 6c 6c 20 6e 6f 74  -op and will not
38e0: 20 73 6c 6f 77 20 64 6f 77 6e 20 74 68 65 20 65   slow down the e
38f0: 76 61 6c 75 61 74 69 6f 6e 20 6f 66 20 74 68 65  valuation of the
3900: 20 74 65 73 74 0a 20 20 73 70 65 63 69 66 69 65   test.  specifie
3910: 64 20 62 79 20 74 68 65 20 74 65 72 6d 2e 0a 20  d by the term.. 
3920: 20 42 75 74 20 69 74 20 77 69 6c 6c 20 70 72 65   But it will pre
3930: 76 65 6e 74 20 74 68 65 20 74 65 72 6d 20 66 72  vent the term fr
3940: 6f 6d 20 63 6f 6e 73 74 72 61 69 6e 69 6e 67 20  om constraining 
3950: 61 6e 20 69 6e 64 65 78 2e 0a 20 20 53 6f 2c 20  an index..  So, 
3960: 69 6e 20 74 68 65 20 65 78 61 6d 70 6c 65 20 61  in the example a
3970: 62 6f 76 65 2c 20 69 66 20 74 68 65 20 71 75 65  bove, if the que
3980: 72 79 20 77 65 72 65 20 72 65 77 72 69 74 74 65  ry were rewritte
3990: 6e 20 61 73 3a 0a 7d 0a 43 4f 44 45 20 7b 0a 20  n as:.}.CODE {. 
39a0: 20 53 45 4c 45 43 54 20 7a 20 46 52 4f 4d 20 65   SELECT z FROM e
39b0: 78 32 20 57 48 45 52 45 20 2b 78 3d 35 20 41 4e  x2 WHERE +x=5 AN
39c0: 44 20 79 3d 36 3b 0a 7d 0a 50 41 52 41 47 52 41  D y=6;.}.PARAGRA
39d0: 50 48 20 7b 0a 20 20 54 68 65 20 2a 2b 2a 20 6f  PH {.  The *+* o
39e0: 70 65 72 61 74 6f 72 20 6f 6e 20 74 68 65 20 2a  perator on the *
39f0: 78 2a 20 63 6f 6c 75 6d 6e 20 77 6f 75 6c 64 20  x* column would 
3a00: 70 72 65 76 65 6e 74 20 74 68 61 74 20 74 65 72  prevent that ter
3a10: 6d 20 66 72 6f 6d 20 0a 20 20 63 6f 6e 73 74 72  m from .  constr
3a20: 61 69 6e 69 6e 67 20 61 6e 20 69 6e 64 65 78 2e  aining an index.
3a30: 20 20 54 68 69 73 20 77 6f 75 6c 64 20 66 6f 72    This would for
3a40: 63 65 20 74 68 65 20 75 73 65 20 6f 66 20 74 68  ce the use of th
3a50: 65 20 65 78 32 69 32 20 69 6e 64 65 78 2e 0a 7d  e ex2i2 index..}
3a60: 0a 0a 48 45 41 44 49 4e 47 20 31 20 7b 41 76 6f  ..HEADING 1 {Avo
3a70: 69 64 61 6e 63 65 20 6f 66 20 74 61 62 6c 65 20  idance of table 
3a80: 6c 6f 6f 6b 75 70 73 7d 20 69 6e 64 65 78 5f 6f  lookups} index_o
3a90: 6e 6c 79 0a 0a 50 41 52 41 47 52 41 50 48 20 7b  nly..PARAGRAPH {
3aa0: 0a 20 20 57 68 65 6e 20 64 6f 69 6e 67 20 61 6e  .  When doing an
3ab0: 20 69 6e 64 65 78 65 64 20 6c 6f 6f 6b 75 70 20   indexed lookup 
3ac0: 6f 66 20 61 20 72 6f 77 2c 20 74 68 65 20 75 73  of a row, the us
3ad0: 75 61 6c 20 70 72 6f 63 65 64 75 72 65 20 69 73  ual procedure is
3ae0: 20 74 6f 0a 20 20 64 6f 20 61 20 62 69 6e 61 72   to.  do a binar
3af0: 79 20 73 65 61 72 63 68 20 6f 6e 20 74 68 65 20  y search on the 
3b00: 69 6e 64 65 78 20 74 6f 20 66 69 6e 64 20 74 68  index to find th
3b10: 65 20 69 6e 64 65 78 20 65 6e 74 72 79 2c 20 74  e index entry, t
3b20: 68 65 6e 20 65 78 74 72 61 63 74 0a 20 20 74 68  hen extract.  th
3b30: 65 20 72 6f 77 69 64 20 66 72 6f 6d 20 74 68 65  e rowid from the
3b40: 20 69 6e 64 65 78 20 61 6e 64 20 75 73 65 20 74   index and use t
3b50: 68 61 74 20 72 6f 77 69 64 20 74 6f 20 64 6f 20  hat rowid to do 
3b60: 61 20 62 69 6e 61 72 79 20 73 65 61 72 63 68 20  a binary search 
3b70: 6f 6e 0a 20 20 74 68 65 20 6f 72 69 67 69 6e 61  on.  the origina
3b80: 6c 20 74 61 62 6c 65 2e 20 20 54 68 75 73 20 61  l table.  Thus a
3b90: 20 74 79 70 69 63 61 6c 20 69 6e 64 65 78 65 64   typical indexed
3ba0: 20 6c 6f 6f 6b 75 70 20 69 6e 76 6f 6c 76 65 73   lookup involves
3bb0: 20 74 77 6f 0a 20 20 62 69 6e 61 72 79 20 73 65   two.  binary se
3bc0: 61 72 63 68 65 73 2e 0a 20 20 49 66 2c 20 68 6f  arches..  If, ho
3bd0: 77 65 76 65 72 2c 20 61 6c 6c 20 63 6f 6c 75 6d  wever, all colum
3be0: 6e 73 20 74 68 61 74 20 77 65 72 65 20 74 6f 20  ns that were to 
3bf0: 62 65 20 66 65 74 63 68 65 64 20 66 72 6f 6d 20  be fetched from 
3c00: 74 68 65 20 74 61 62 6c 65 20 61 72 65 0a 20 20  the table are.  
3c10: 61 6c 72 65 61 64 79 20 61 76 61 69 6c 61 62 6c  already availabl
3c20: 65 20 69 6e 20 74 68 65 20 69 6e 64 65 78 20 69  e in the index i
3c30: 74 73 65 6c 66 2c 20 53 51 4c 69 74 65 20 77 69  tself, SQLite wi
3c40: 6c 6c 20 75 73 65 20 74 68 65 20 76 61 6c 75 65  ll use the value
3c50: 73 0a 20 20 63 6f 6e 74 61 69 6e 65 64 20 69 6e  s.  contained in
3c60: 20 74 68 65 20 69 6e 64 65 78 20 61 6e 64 20 77   the index and w
3c70: 69 6c 6c 20 6e 65 76 65 72 20 6c 6f 6f 6b 20 75  ill never look u
3c80: 70 20 74 68 65 20 6f 72 69 67 69 6e 61 6c 20 74  p the original t
3c90: 61 62 6c 65 0a 20 20 72 6f 77 2e 20 20 54 68 69  able.  row.  Thi
3ca0: 73 20 73 61 76 65 73 20 6f 6e 65 20 62 69 6e 61  s saves one bina
3cb0: 72 79 20 73 65 61 72 63 68 20 66 6f 72 20 65 61  ry search for ea
3cc0: 63 68 20 72 6f 77 20 61 6e 64 20 63 61 6e 20 6d  ch row and can m
3cd0: 61 6b 65 20 6d 61 6e 79 0a 20 20 71 75 65 72 69  ake many.  queri
3ce0: 65 73 20 72 75 6e 20 74 77 69 63 65 20 61 73 20  es run twice as 
3cf0: 66 61 73 74 2e 0a 7d 0a 0a 48 45 41 44 49 4e 47  fast..}..HEADING
3d00: 20 31 20 7b 4f 52 44 45 52 20 42 59 20 6f 70 74   1 {ORDER BY opt
3d10: 69 6d 69 7a 61 74 69 6f 6e 73 7d 20 6f 72 64 65  imizations} orde
3d20: 72 5f 62 79 0a 0a 50 41 52 41 47 52 41 50 48 20  r_by..PARAGRAPH 
3d30: 7b 0a 20 20 53 51 4c 69 74 65 20 61 74 74 65 6d  {.  SQLite attem
3d40: 70 74 73 20 74 6f 20 75 73 65 20 61 6e 20 69 6e  pts to use an in
3d50: 64 65 78 20 74 6f 20 73 61 74 69 73 66 79 20 74  dex to satisfy t
3d60: 68 65 20 4f 52 44 45 52 20 42 59 20 63 6c 61 75  he ORDER BY clau
3d70: 73 65 20 6f 66 20 61 0a 20 20 71 75 65 72 79 20  se of a.  query 
3d80: 77 68 65 6e 20 70 6f 73 73 69 62 6c 65 2e 0a 20  when possible.. 
3d90: 20 57 68 65 6e 20 66 61 63 65 64 20 77 69 74 68   When faced with
3da0: 20 74 68 65 20 63 68 6f 69 63 65 20 6f 66 20 75   the choice of u
3db0: 73 69 6e 67 20 61 6e 20 69 6e 64 65 78 20 74 6f  sing an index to
3dc0: 20 73 61 74 69 73 66 79 20 57 48 45 52 45 20 63   satisfy WHERE c
3dd0: 6c 61 75 73 65 0a 20 20 63 6f 6e 73 74 72 61 69  lause.  constrai
3de0: 6e 74 73 20 6f 72 20 73 61 74 69 73 66 79 69 6e  nts or satisfyin
3df0: 67 20 61 6e 20 4f 52 44 45 52 20 42 59 20 63 6c  g an ORDER BY cl
3e00: 61 75 73 65 2c 20 53 51 4c 69 74 65 20 64 6f 65  ause, SQLite doe
3e10: 73 20 74 68 65 20 73 61 6d 65 0a 20 20 77 6f 72  s the same.  wor
3e20: 6b 20 61 6e 61 6c 79 73 69 73 20 64 65 73 63 72  k analysis descr
3e30: 69 62 65 64 20 69 6e 20 73 65 63 74 69 6f 6e 20  ibed in section 
3e40: 36 2e 30 0a 20 20 61 6e 64 20 63 68 6f 6f 73 65  6.0.  and choose
3e50: 73 20 74 68 65 20 69 6e 64 65 78 20 74 68 61 74  s the index that
3e60: 20 69 74 20 62 65 6c 69 65 76 65 73 20 77 69 6c   it believes wil
3e70: 6c 20 72 65 73 75 6c 74 20 69 6e 20 74 68 65 20  l result in the 
3e80: 66 61 73 74 65 73 74 20 61 6e 73 77 65 72 2e 0a  fastest answer..
3e90: 0a 7d 0a 0a 48 45 41 44 49 4e 47 20 31 20 7b 53  .}..HEADING 1 {S
3ea0: 75 62 71 75 65 72 79 20 66 6c 61 74 74 65 6e 69  ubquery flatteni
3eb0: 6e 67 7d 20 66 6c 61 74 74 65 6e 69 6e 67 0a 0a  ng} flattening..
3ec0: 50 41 52 41 47 52 41 50 48 20 7b 0a 20 20 57 68  PARAGRAPH {.  Wh
3ed0: 65 6e 20 61 20 73 75 62 71 75 65 72 79 20 6f 63  en a subquery oc
3ee0: 63 75 72 73 20 69 6e 20 74 68 65 20 46 52 4f 4d  curs in the FROM
3ef0: 20 63 6c 61 75 73 65 20 6f 66 20 61 20 53 45 4c   clause of a SEL
3f00: 45 43 54 2c 20 74 68 65 20 64 65 66 61 75 6c 74  ECT, the default
3f10: 0a 20 20 62 65 68 61 76 69 6f 72 20 69 73 20 74  .  behavior is t
3f20: 6f 20 65 76 61 6c 75 61 74 65 20 74 68 65 20 73  o evaluate the s
3f30: 75 62 71 75 65 72 79 20 69 6e 74 6f 20 61 20 74  ubquery into a t
3f40: 72 61 6e 73 69 65 6e 74 20 74 61 62 6c 65 2c 20  ransient table, 
3f50: 74 68 65 6e 20 72 75 6e 0a 20 20 74 68 65 20 6f  then run.  the o
3f60: 75 74 65 72 20 53 45 4c 45 43 54 20 61 67 61 69  uter SELECT agai
3f70: 6e 73 74 20 74 68 65 20 74 72 61 6e 73 69 65 6e  nst the transien
3f80: 74 20 74 61 62 6c 65 2e 20 0a 20 20 54 68 69 73  t table. .  This
3f90: 20 69 73 20 70 72 6f 62 6c 65 6d 61 74 69 63 20   is problematic 
3fa0: 73 69 6e 63 65 20 74 68 65 20 74 72 61 6e 73 69  since the transi
3fb0: 65 6e 74 20 74 61 62 6c 65 20 77 69 6c 6c 20 6e  ent table will n
3fc0: 6f 74 20 68 61 76 65 20 61 6e 79 20 69 6e 64 69  ot have any indi
3fd0: 63 65 73 0a 20 20 61 6e 64 20 74 68 65 20 6f 75  ces.  and the ou
3fe0: 74 65 72 20 71 75 65 72 79 20 28 77 68 69 63 68  ter query (which
3ff0: 20 69 73 20 6c 69 6b 65 6c 79 20 61 20 6a 6f 69   is likely a joi
4000: 6e 29 20 77 69 6c 6c 20 62 65 20 66 6f 72 63 65  n) will be force
4010: 64 20 74 6f 20 64 6f 20 61 0a 20 20 66 75 6c 6c  d to do a.  full
4020: 20 74 61 62 6c 65 20 73 63 61 6e 20 6f 6e 20 74   table scan on t
4030: 68 65 20 74 72 61 6e 73 69 65 6e 74 20 74 61 62  he transient tab
4040: 6c 65 2e 0a 7d 0a 50 41 52 41 47 52 41 50 48 20  le..}.PARAGRAPH 
4050: 7b 0a 20 20 54 6f 20 6f 76 65 72 63 6f 6d 65 20  {.  To overcome 
4060: 74 68 69 73 20 70 72 6f 62 6c 65 6d 2c 20 53 51  this problem, SQ
4070: 4c 69 74 65 20 61 74 74 65 6d 70 74 73 20 74 6f  Lite attempts to
4080: 20 66 6c 61 74 74 65 6e 20 73 75 62 71 75 65 72   flatten subquer
4090: 69 65 73 20 69 6e 0a 20 20 74 68 65 20 46 52 4f  ies in.  the FRO
40a0: 4d 20 63 6c 61 75 73 65 20 6f 66 20 61 20 53 45  M clause of a SE
40b0: 4c 45 43 54 2e 0a 20 20 54 68 69 73 20 69 6e 76  LECT..  This inv
40c0: 6f 6c 76 65 73 20 69 6e 73 65 72 74 69 6e 67 20  olves inserting 
40d0: 74 68 65 20 46 52 4f 4d 20 63 6c 61 75 73 65 20  the FROM clause 
40e0: 6f 66 20 74 68 65 20 73 75 62 71 75 65 72 79 20  of the subquery 
40f0: 69 6e 74 6f 20 74 68 65 0a 20 20 46 52 4f 4d 20  into the.  FROM 
4100: 63 6c 61 75 73 65 20 6f 66 20 74 68 65 20 6f 75  clause of the ou
4110: 74 65 72 20 71 75 65 72 79 20 61 6e 64 20 72 65  ter query and re
4120: 77 72 69 74 69 6e 67 20 65 78 70 72 65 73 73 69  writing expressi
4130: 6f 6e 73 20 69 6e 0a 20 20 74 68 65 20 6f 75 74  ons in.  the out
4140: 65 72 20 71 75 65 72 79 20 74 68 61 74 20 72 65  er query that re
4150: 66 65 72 20 74 6f 20 74 68 65 20 72 65 73 75 6c  fer to the resul
4160: 74 20 73 65 74 20 6f 66 20 74 68 65 20 73 75 62  t set of the sub
4170: 71 75 65 72 79 2e 0a 20 20 46 6f 72 20 65 78 61  query..  For exa
4180: 6d 70 6c 65 3a 0a 7d 0a 43 4f 44 45 20 7b 0a 20  mple:.}.CODE {. 
4190: 20 53 45 4c 45 43 54 20 61 20 46 52 4f 4d 20 28   SELECT a FROM (
41a0: 53 45 4c 45 43 54 20 78 2b 79 20 41 53 20 61 20  SELECT x+y AS a 
41b0: 46 52 4f 4d 20 74 31 20 57 48 45 52 45 20 7a 3c  FROM t1 WHERE z<
41c0: 31 30 30 29 20 57 48 45 52 45 20 61 3e 35 0a 7d  100) WHERE a>5.}
41d0: 0a 50 41 52 41 47 52 41 50 48 20 7b 0a 20 20 57  .PARAGRAPH {.  W
41e0: 6f 75 6c 64 20 62 65 20 72 65 77 72 69 74 74 65  ould be rewritte
41f0: 6e 20 75 73 69 6e 67 20 71 75 65 72 79 20 66 6c  n using query fl
4200: 61 74 74 65 6e 69 6e 67 20 61 73 3a 0a 7d 0a 43  attening as:.}.C
4210: 4f 44 45 20 7b 0a 20 20 53 45 4c 45 43 54 20 78  ODE {.  SELECT x
4220: 2b 79 20 41 53 20 61 20 46 52 4f 4d 20 74 31 20  +y AS a FROM t1 
4230: 57 48 45 52 45 20 7a 3c 31 30 30 20 41 4e 44 20  WHERE z<100 AND 
4240: 61 3e 35 0a 7d 0a 50 41 52 41 47 52 41 50 48 20  a>5.}.PARAGRAPH 
4250: 7b 0a 20 20 54 68 65 72 65 20 69 73 20 61 20 6c  {.  There is a l
4260: 6f 6e 67 20 6c 69 73 74 20 6f 66 20 63 6f 6e 64  ong list of cond
4270: 69 74 69 6f 6e 73 20 74 68 61 74 20 6d 75 73 74  itions that must
4280: 20 61 6c 6c 20 62 65 20 6d 65 74 20 69 6e 20 6f   all be met in o
4290: 72 64 65 72 20 66 6f 72 0a 20 20 71 75 65 72 79  rder for.  query
42a0: 20 66 6c 61 74 74 65 6e 69 6e 67 20 74 6f 20 6f   flattening to o
42b0: 63 63 75 72 2e 0a 7d 0a 50 41 52 41 47 52 41 50  ccur..}.PARAGRAP
42c0: 48 20 7b 0a 20 20 3c 6f 6c 3e 0a 20 20 3c 6c 69  H {.  <ol>.  <li
42d0: 3e 20 54 68 65 20 73 75 62 71 75 65 72 79 20 61  > The subquery a
42e0: 6e 64 20 74 68 65 20 6f 75 74 65 72 20 71 75 65  nd the outer que
42f0: 72 79 20 64 6f 20 6e 6f 74 20 62 6f 74 68 20 75  ry do not both u
4300: 73 65 20 61 67 67 72 65 67 61 74 65 73 2e 3c 2f  se aggregates.</
4310: 6c 69 3e 0a 20 20 3c 6c 69 3e 20 54 68 65 20 73  li>.  <li> The s
4320: 75 62 71 75 65 72 79 20 69 73 20 6e 6f 74 20 61  ubquery is not a
4330: 6e 20 61 67 67 72 65 67 61 74 65 20 6f 72 20 74  n aggregate or t
4340: 68 65 20 6f 75 74 65 72 20 71 75 65 72 79 20 69  he outer query i
4350: 73 20 6e 6f 74 20 61 20 6a 6f 69 6e 2e 20 3c 2f  s not a join. </
4360: 6c 69 3e 0a 20 20 3c 6c 69 3e 20 54 68 65 20 73  li>.  <li> The s
4370: 75 62 71 75 65 72 79 20 69 73 20 6e 6f 74 20 74  ubquery is not t
4380: 68 65 20 72 69 67 68 74 20 6f 70 65 72 61 6e 64  he right operand
4390: 20 6f 66 20 61 20 6c 65 66 74 20 6f 75 74 65 72   of a left outer
43a0: 20 6a 6f 69 6e 2c 20 6f 72 0a 20 20 20 20 20 20   join, or.      
43b0: 20 20 20 20 74 68 65 20 73 75 62 71 75 65 72 79      the subquery
43c0: 20 69 73 20 6e 6f 74 20 69 74 73 65 6c 66 20 61   is not itself a
43d0: 20 6a 6f 69 6e 2e 20 3c 2f 6c 69 3e 0a 20 20 3c   join. </li>.  <
43e0: 6c 69 3e 20 20 54 68 65 20 73 75 62 71 75 65 72  li>  The subquer
43f0: 79 20 69 73 20 6e 6f 74 20 44 49 53 54 49 4e 43  y is not DISTINC
4400: 54 20 6f 72 20 74 68 65 20 6f 75 74 65 72 20 71  T or the outer q
4410: 75 65 72 79 20 69 73 20 6e 6f 74 20 61 20 6a 6f  uery is not a jo
4420: 69 6e 2e 20 3c 2f 6c 69 3e 0a 20 20 3c 6c 69 3e  in. </li>.  <li>
4430: 20 20 54 68 65 20 73 75 62 71 75 65 72 79 20 69    The subquery i
4440: 73 20 6e 6f 74 20 44 49 53 54 49 4e 43 54 20 6f  s not DISTINCT o
4450: 72 20 74 68 65 20 6f 75 74 65 72 20 71 75 65 72  r the outer quer
4460: 79 20 64 6f 65 73 20 6e 6f 74 20 75 73 65 0a 20  y does not use. 
4470: 20 20 20 20 20 20 20 20 20 61 67 67 72 65 67 61           aggrega
4480: 74 65 73 2e 20 3c 2f 6c 69 3e 0a 20 20 3c 6c 69  tes. </li>.  <li
4490: 3e 20 20 54 68 65 20 73 75 62 71 75 65 72 79 20  >  The subquery 
44a0: 64 6f 65 73 20 6e 6f 74 20 75 73 65 20 61 67 67  does not use agg
44b0: 72 65 67 61 74 65 73 20 6f 72 20 74 68 65 20 6f  regates or the o
44c0: 75 74 65 72 20 71 75 65 72 79 20 69 73 20 6e 6f  uter query is no
44d0: 74 0a 20 20 20 20 20 20 20 20 20 20 44 49 53 54  t.          DIST
44e0: 49 4e 43 54 2e 20 3c 2f 6c 69 3e 0a 20 20 3c 6c  INCT. </li>.  <l
44f0: 69 3e 20 20 54 68 65 20 73 75 62 71 75 65 72 79  i>  The subquery
4500: 20 68 61 73 20 61 20 46 52 4f 4d 20 63 6c 61 75   has a FROM clau
4510: 73 65 2e 20 3c 2f 6c 69 3e 0a 20 20 3c 6c 69 3e  se. </li>.  <li>
4520: 20 20 54 68 65 20 73 75 62 71 75 65 72 79 20 64    The subquery d
4530: 6f 65 73 20 6e 6f 74 20 75 73 65 20 4c 49 4d 49  oes not use LIMI
4540: 54 20 6f 72 20 74 68 65 20 6f 75 74 65 72 20 71  T or the outer q
4550: 75 65 72 79 20 69 73 20 6e 6f 74 20 61 20 6a 6f  uery is not a jo
4560: 69 6e 2e 20 3c 2f 6c 69 3e 0a 20 20 3c 6c 69 3e  in. </li>.  <li>
4570: 20 20 54 68 65 20 73 75 62 71 75 65 72 79 20 64    The subquery d
4580: 6f 65 73 20 6e 6f 74 20 75 73 65 20 4c 49 4d 49  oes not use LIMI
4590: 54 20 6f 72 20 74 68 65 20 6f 75 74 65 72 20 71  T or the outer q
45a0: 75 65 72 79 20 64 6f 65 73 20 6e 6f 74 20 75 73  uery does not us
45b0: 65 0a 20 20 20 20 20 20 20 20 20 61 67 67 72 65  e.         aggre
45c0: 67 61 74 65 73 2e 20 3c 2f 6c 69 3e 0a 20 20 3c  gates. </li>.  <
45d0: 6c 69 3e 20 20 54 68 65 20 73 75 62 71 75 65 72  li>  The subquer
45e0: 79 20 64 6f 65 73 20 6e 6f 74 20 75 73 65 20 61  y does not use a
45f0: 67 67 72 65 67 61 74 65 73 20 6f 72 20 74 68 65  ggregates or the
4600: 20 6f 75 74 65 72 20 71 75 65 72 79 20 64 6f 65   outer query doe
4610: 73 20 6e 6f 74 0a 20 20 20 20 20 20 20 20 20 75  s not.         u
4620: 73 65 20 4c 49 4d 49 54 2e 20 3c 2f 6c 69 3e 0a  se LIMIT. </li>.
4630: 20 20 3c 6c 69 3e 20 20 54 68 65 20 73 75 62 71    <li>  The subq
4640: 75 65 72 79 20 61 6e 64 20 74 68 65 20 6f 75 74  uery and the out
4650: 65 72 20 71 75 65 72 79 20 64 6f 20 6e 6f 74 20  er query do not 
4660: 62 6f 74 68 20 68 61 76 65 20 4f 52 44 45 52 20  both have ORDER 
4670: 42 59 20 63 6c 61 75 73 65 73 2e 3c 2f 6c 69 3e  BY clauses.</li>
4680: 0a 20 20 3c 6c 69 3e 20 20 54 68 65 20 73 75 62  .  <li>  The sub
4690: 71 75 65 72 79 20 69 73 20 6e 6f 74 20 74 68 65  query is not the
46a0: 20 72 69 67 68 74 20 74 65 72 6d 20 6f 66 20 61   right term of a
46b0: 20 4c 45 46 54 20 4f 55 54 45 52 20 4a 4f 49 4e   LEFT OUTER JOIN
46c0: 20 6f 72 20 74 68 65 0a 20 20 20 20 20 20 20 20   or the.        
46d0: 20 73 75 62 71 75 65 72 79 20 68 61 73 20 6e 6f   subquery has no
46e0: 20 57 48 45 52 45 20 63 6c 61 75 73 65 2e 20 20   WHERE clause.  
46f0: 3c 2f 6c 69 3e 0a 20 20 3c 2f 6f 6c 3e 0a 7d 0a  </li>.  </ol>.}.
4700: 50 41 52 41 47 52 41 50 48 20 7b 0a 20 20 54 68  PARAGRAPH {.  Th
4710: 65 20 70 72 6f 6f 66 20 74 68 61 74 20 71 75 65  e proof that que
4720: 72 79 20 66 6c 61 74 74 65 6e 69 6e 67 20 6d 61  ry flattening ma
4730: 79 20 73 61 66 65 6c 79 20 6f 63 63 75 72 20 69  y safely occur i
4740: 66 20 61 6c 6c 20 6f 66 20 74 68 65 20 74 68 65  f all of the the
4750: 0a 20 20 61 62 6f 76 65 20 63 6f 6e 64 69 74 69  .  above conditi
4760: 6f 6e 73 20 61 72 65 20 6d 65 74 20 69 73 20 6c  ons are met is l
4770: 65 66 74 20 61 73 20 61 6e 20 65 78 65 72 63 69  eft as an exerci
4780: 73 65 20 74 6f 20 74 68 65 20 72 65 61 64 65 72  se to the reader
4790: 2e 0a 7d 0a 50 41 52 41 47 52 41 50 48 20 7b 0a  ..}.PARAGRAPH {.
47a0: 20 20 51 75 65 72 79 20 66 6c 61 74 74 65 6e 69    Query flatteni
47b0: 6e 67 20 69 73 20 61 6e 20 69 6d 70 6f 72 74 61  ng is an importa
47c0: 6e 74 20 6f 70 74 69 6d 69 7a 61 74 69 6f 6e 20  nt optimization 
47d0: 77 68 65 6e 20 76 69 65 77 73 20 61 72 65 20 75  when views are u
47e0: 73 65 64 20 61 73 0a 20 20 65 61 63 68 20 75 73  sed as.  each us
47f0: 65 20 6f 66 20 61 20 76 69 65 77 20 69 73 20 74  e of a view is t
4800: 72 61 6e 73 6c 61 74 65 64 20 69 6e 74 6f 20 61  ranslated into a
4810: 20 73 75 62 71 75 65 72 79 2e 0a 7d 0a 0a 48 45   subquery..}..HE
4820: 41 44 49 4e 47 20 31 20 7b 54 68 65 20 4d 49 4e  ADING 1 {The MIN
4830: 2f 4d 41 58 20 6f 70 74 69 6d 69 7a 61 74 69 6f  /MAX optimizatio
4840: 6e 7d 20 6d 69 6e 6d 61 78 0a 0a 50 41 52 41 47  n} minmax..PARAG
4850: 52 41 50 48 20 7b 0a 20 20 51 75 65 72 69 65 73  RAPH {.  Queries
4860: 20 6f 66 20 74 68 65 20 66 6f 6c 6c 6f 77 69 6e   of the followin
4870: 67 20 66 6f 72 6d 73 20 77 69 6c 6c 20 62 65 20  g forms will be 
4880: 6f 70 74 69 6d 69 7a 65 64 20 74 6f 20 72 75 6e  optimized to run
4890: 20 69 6e 20 6c 6f 67 61 72 69 74 68 6d 69 63 0a   in logarithmic.
48a0: 20 20 74 69 6d 65 20 61 73 73 75 6d 69 6e 67 20    time assuming 
48b0: 61 70 70 72 6f 70 72 69 61 74 65 20 69 6e 64 69  appropriate indi
48c0: 63 65 73 20 65 78 69 73 74 3a 0a 7d 0a 43 4f 44  ces exist:.}.COD
48d0: 45 20 7b 0a 20 20 53 45 4c 45 43 54 20 4d 49 4e  E {.  SELECT MIN
48e0: 28 78 29 20 46 52 4f 4d 20 74 61 62 6c 65 3b 0a  (x) FROM table;.
48f0: 20 20 53 45 4c 45 43 54 20 4d 41 58 28 78 29 20    SELECT MAX(x) 
4900: 46 52 4f 4d 20 74 61 62 6c 65 3b 0a 7d 0a 50 41  FROM table;.}.PA
4910: 52 41 47 52 41 50 48 20 7b 0a 20 20 49 6e 20 6f  RAGRAPH {.  In o
4920: 72 64 65 72 20 66 6f 72 20 74 68 65 73 65 20 6f  rder for these o
4930: 70 74 69 6d 69 7a 61 74 69 6f 6e 73 20 74 6f 20  ptimizations to 
4940: 6f 63 63 75 72 2c 20 74 68 65 79 20 6d 75 73 74  occur, they must
4950: 20 61 70 70 65 61 72 20 69 6e 20 65 78 61 63 74   appear in exact
4960: 6c 79 0a 20 20 74 68 65 20 66 6f 72 6d 20 73 68  ly.  the form sh
4970: 6f 77 6e 20 61 62 6f 76 65 20 2d 20 63 68 61 6e  own above - chan
4980: 67 69 6e 67 20 6f 6e 6c 79 20 74 68 65 20 6e 61  ging only the na
4990: 6d 65 20 6f 66 20 74 68 65 20 74 61 62 6c 65 20  me of the table 
49a0: 61 6e 64 20 63 6f 6c 75 6d 6e 2e 0a 20 20 49 74  and column..  It
49b0: 20 69 73 20 6e 6f 74 20 70 65 72 6d 69 73 73 69   is not permissi
49c0: 62 6c 65 20 74 6f 20 61 64 64 20 61 20 57 48 45  ble to add a WHE
49d0: 52 45 20 63 6c 61 75 73 65 20 6f 72 20 64 6f 20  RE clause or do 
49e0: 61 6e 79 20 61 72 69 74 68 6d 65 74 69 63 20 6f  any arithmetic o
49f0: 6e 20 74 68 65 0a 20 20 72 65 73 75 6c 74 2e 20  n the.  result. 
4a00: 20 54 68 65 20 72 65 73 75 6c 74 20 73 65 74 20   The result set 
4a10: 6d 75 73 74 20 63 6f 6e 74 61 69 6e 20 61 20 73  must contain a s
4a20: 69 6e 67 6c 65 20 63 6f 6c 75 6d 6e 2e 0a 20 20  ingle column..  
4a30: 54 68 65 20 63 6f 6c 75 6d 6e 20 69 6e 20 74 68  The column in th
4a40: 65 20 4d 49 4e 20 6f 72 20 4d 41 58 20 66 75 6e  e MIN or MAX fun
4a50: 63 74 69 6f 6e 20 6d 75 73 74 20 62 65 20 61 6e  ction must be an
4a60: 20 69 6e 64 65 78 65 64 20 63 6f 6c 75 6d 6e 2e   indexed column.
4a70: 0a 7d 0a                                         .}.