Documentation Source Text

Hex Artifact Content
Login

Artifact b9e97368fb4616dda824f5d810590a3f2505ac4f:


0000: 3c 74 69 74 6c 65 3e 51 75 65 72 79 20 50 6c 61  <title>Query Pla
0010: 6e 6e 69 6e 67 3c 2f 74 69 74 6c 65 3e 0a 3c 61  nning</title>.<a
0020: 6c 74 2d 74 69 74 6c 65 3e 48 6f 77 20 49 6e 64  lt-title>How Ind
0030: 65 78 65 73 20 57 6f 72 6b 3c 2f 61 6c 74 2d 74  exes Work</alt-t
0040: 69 74 6c 65 3e 0a 3c 74 63 6c 3e 0a 68 64 5f 6b  itle>.<tcl>.hd_k
0050: 65 79 77 6f 72 64 73 20 7b 69 6e 64 65 78 69 6e  eywords {indexin
0060: 67 7d 20 7b 69 6e 64 65 78 69 6e 67 20 74 75 74  g} {indexing tut
0070: 6f 72 69 61 6c 7d 0a 70 72 6f 63 20 66 69 67 75  orial}.proc figu
0080: 72 65 20 7b 66 69 67 6e 75 6d 20 74 61 67 20 69  re {fignum tag i
0090: 6d 67 20 74 69 74 6c 65 7d 20 7b 0a 20 20 69 66  mg title} {.  if
00a0: 20 7b 24 74 61 67 21 3d 22 22 7d 20 7b 0a 20 20   {$tag!=""} {.  
00b0: 20 20 73 65 74 20 74 61 67 20 5b 73 74 72 69 6e    set tag [strin
00c0: 67 20 74 72 69 6d 20 24 74 61 67 20 23 5d 0a 20  g trim $tag #]. 
00d0: 20 20 20 68 64 5f 70 75 74 73 20 22 3c 61 20 6e     hd_puts "<a n
00e0: 61 6d 65 3d 27 24 74 61 67 27 3e 3c 2f 61 3e 5c  ame='$tag'></a>\
00f0: 6e 22 0a 20 20 7d 0a 20 20 68 64 5f 70 75 74 73  n".  }.  hd_puts
0100: 20 22 3c 70 3e 3c 63 65 6e 74 65 72 3e 5c 6e 22   "<p><center>\n"
0110: 0a 20 20 68 64 5f 70 75 74 73 20 22 3c 69 6d 67  .  hd_puts "<img
0120: 20 73 72 63 3d 5c 22 69 6d 61 67 65 73 2f 71 70   src=\"images/qp
0130: 2f 24 69 6d 67 5c 22 20 61 6c 74 3d 5c 22 66 69  /$img\" alt=\"fi
0140: 67 75 72 65 20 24 66 69 67 6e 75 6d 5c 22 3e 3c  gure $fignum\"><
0150: 62 72 3e 5c 6e 22 0a 20 20 68 64 5f 70 75 74 73  br>\n".  hd_puts
0160: 20 22 46 69 67 75 72 65 20 24 66 69 67 6e 75 6d   "Figure $fignum
0170: 3a 20 24 74 69 74 6c 65 5c 6e 22 0a 20 20 68 64  : $title\n".  hd
0180: 5f 70 75 74 73 20 22 3c 2f 63 65 6e 74 65 72 3e  _puts "</center>
0190: 3c 2f 70 3e 5c 6e 22 0a 7d 0a 70 72 6f 63 20 63  </p>\n".}.proc c
01a0: 6f 64 65 20 7b 74 78 74 7d 20 7b 0a 20 20 68 64  ode {txt} {.  hd
01b0: 5f 70 75 74 73 20 22 3c 63 65 6e 74 65 72 3e 3c  _puts "<center><
01c0: 74 61 62 6c 65 3e 3c 74 72 3e 3c 74 64 3e 3c 70  table><tr><td><p
01d0: 72 65 3e 5c 6e 22 0a 20 20 72 65 67 73 75 62 20  re>\n".  regsub 
01e0: 7b 5e 5b 20 5c 6e 5d 2a 5c 6e 7d 20 24 74 78 74  {^[ \n]*\n} $txt
01f0: 20 7b 7d 20 74 78 74 0a 20 20 68 64 5f 70 75 74   {} txt.  hd_put
0200: 73 20 5b 73 74 72 69 6e 67 20 74 72 69 6d 72 69  s [string trimri
0210: 67 68 74 20 24 74 78 74 5d 5c 6e 0a 20 20 68 64  ght $txt]\n.  hd
0220: 5f 70 75 74 73 20 22 3c 2f 70 72 65 3e 3c 2f 74  _puts "</pre></t
0230: 61 62 6c 65 3e 3c 2f 63 65 6e 74 65 72 3e 5c 6e  able></center>\n
0240: 22 0a 7d 0a 3c 2f 74 63 6c 3e 0a 0a 3c 74 61 62  ".}.</tcl>..<tab
0250: 6c 65 5f 6f 66 5f 63 6f 6e 74 65 6e 74 73 3e 0a  le_of_contents>.
0260: 0a 3c 68 32 20 73 74 79 6c 65 3d 22 6d 61 72 67  .<h2 style="marg
0270: 69 6e 2d 6c 65 66 74 3a 31 2e 30 65 6d 22 20 6e  in-left:1.0em" n
0280: 6f 74 6f 63 20 69 64 3d 6f 76 65 72 76 69 65 77  otoc id=overview
0290: 3e 20 4f 76 65 72 76 69 65 77 3c 2f 68 32 3e 20  > Overview</h2> 
02a0: 0a 0a 3c 70 3e 0a 54 68 65 20 62 65 73 74 20 66  ..<p>.The best f
02b0: 65 61 74 75 72 65 20 6f 66 20 53 51 4c 20 28 69  eature of SQL (i
02c0: 6e 20 3c 75 3e 61 6c 6c 3c 2f 75 3e 20 69 74 73  n <u>all</u> its
02d0: 20 69 6d 70 6c 65 6d 65 6e 74 61 74 69 6f 6e 73   implementations
02e0: 2c 20 6e 6f 74 20 6a 75 73 74 20 53 51 4c 69 74  , not just SQLit
02f0: 65 29 0a 69 73 20 74 68 61 74 20 69 74 20 69 73  e).is that it is
0300: 20 61 20 3c 69 3e 64 65 63 6c 61 72 61 74 69 76   a <i>declarativ
0310: 65 3c 2f 69 3e 20 6c 61 6e 67 75 61 67 65 2c 20  e</i> language, 
0320: 6e 6f 74 20 61 20 3c 69 3e 70 72 6f 63 65 64 75  not a <i>procedu
0330: 72 61 6c 3c 2f 69 3e 0a 6c 61 6e 67 75 61 67 65  ral</i>.language
0340: 2e 20 20 57 68 65 6e 20 70 72 6f 67 72 61 6d 6d  .  When programm
0350: 69 6e 67 20 69 6e 20 53 51 4c 20 79 6f 75 20 74  ing in SQL you t
0360: 65 6c 6c 20 74 68 65 20 73 79 73 74 65 6d 20 3c  ell the system <
0370: 69 3e 77 68 61 74 3c 2f 69 3e 20 79 6f 75 0a 77  i>what</i> you.w
0380: 61 6e 74 20 74 6f 20 63 6f 6d 70 75 74 65 2c 20  ant to compute, 
0390: 6e 6f 74 20 3c 69 3e 68 6f 77 3c 2f 69 3e 20 74  not <i>how</i> t
03a0: 6f 20 63 6f 6d 70 75 74 65 20 69 74 2e 20 20 54  o compute it.  T
03b0: 68 65 20 74 61 73 6b 20 6f 66 20 66 69 67 75 72  he task of figur
03c0: 69 6e 67 20 6f 75 74 0a 74 68 65 20 3c 69 3e 68  ing out.the <i>h
03d0: 6f 77 3c 2f 69 3e 20 69 73 20 64 65 6c 65 67 61  ow</i> is delega
03e0: 74 65 64 20 74 6f 20 74 68 65 20 3c 69 3e 71 75  ted to the <i>qu
03f0: 65 72 79 20 70 6c 61 6e 6e 65 72 3c 2f 69 3e 20  ery planner</i> 
0400: 73 75 62 73 79 73 74 65 6d 20 77 69 74 68 69 6e  subsystem within
0410: 20 0a 74 68 65 20 53 51 4c 20 64 61 74 61 62 61   .the SQL databa
0420: 73 65 20 65 6e 67 69 6e 65 2e 3c 2f 70 3e 0a 0a  se engine.</p>..
0430: 3c 70 3e 46 6f 72 20 61 6e 79 20 67 69 76 65 6e  <p>For any given
0440: 20 53 51 4c 20 73 74 61 74 65 6d 65 6e 74 2c 20   SQL statement, 
0450: 74 68 65 72 65 20 6d 69 67 68 74 20 62 65 20 68  there might be h
0460: 75 6e 64 72 65 64 73 20 6f 72 20 74 68 6f 75 73  undreds or thous
0470: 61 6e 64 73 20 6f 72 0a 65 76 65 6e 20 6d 69 6c  ands or.even mil
0480: 6c 69 6f 6e 73 20 6f 66 20 64 69 66 66 65 72 65  lions of differe
0490: 6e 74 20 61 6c 67 6f 72 69 74 68 6d 73 20 6f 66  nt algorithms of
04a0: 20 70 65 72 66 6f 72 6d 69 6e 67 20 74 68 65 20   performing the 
04b0: 6f 70 65 72 61 74 69 6f 6e 2e 20 20 41 6c 6c 0a  operation.  All.
04c0: 6f 66 20 74 68 65 73 65 20 61 6c 67 6f 72 69 74  of these algorit
04d0: 68 6d 73 20 77 69 6c 6c 20 67 65 74 20 74 68 65  hms will get the
04e0: 20 63 6f 72 72 65 63 74 20 61 6e 73 77 65 72 2c   correct answer,
04f0: 20 74 68 6f 75 67 68 20 73 6f 6d 65 20 77 69 6c   though some wil
0500: 6c 20 72 75 6e 0a 66 61 73 74 65 72 20 74 68 61  l run.faster tha
0510: 6e 20 6f 74 68 65 72 73 2e 0a 54 68 65 20 71 75  n others..The qu
0520: 65 72 79 20 70 6c 61 6e 6e 65 72 20 69 73 20 61  ery planner is a
0530: 6e 20 0a 5b 68 74 74 70 73 3a 2f 2f 65 6e 2e 77  n .[https://en.w
0540: 69 6b 69 70 65 64 69 61 2e 6f 72 67 2f 77 69 6b  ikipedia.org/wik
0550: 69 2f 41 72 74 69 66 69 63 69 61 6c 5f 69 6e 74  i/Artificial_int
0560: 65 6c 6c 69 67 65 6e 63 65 7c 41 49 5d 20 74 68  elligence|AI] th
0570: 61 74 20 0a 74 72 69 65 73 20 74 6f 20 70 69 63  at .tries to pic
0580: 6b 20 74 68 65 20 66 61 73 74 65 73 74 20 61 6e  k the fastest an
0590: 64 20 6d 6f 73 74 20 65 66 66 69 63 69 65 6e 74  d most efficient
05a0: 20 61 6c 67 6f 72 69 74 68 6d 20 66 6f 72 20 65   algorithm for e
05b0: 61 63 68 20 53 51 4c 0a 73 74 61 74 65 6d 65 6e  ach SQL.statemen
05c0: 74 2e 0a 3c 2f 70 3e 0a 0a 3c 70 3e 0a 4d 6f 73  t..</p>..<p>.Mos
05d0: 74 20 6f 66 20 74 68 65 20 74 69 6d 65 2c 20 74  t of the time, t
05e0: 68 65 20 71 75 65 72 79 20 70 6c 61 6e 6e 65 72  he query planner
05f0: 20 69 6e 20 53 51 4c 69 74 65 20 64 6f 65 73 20   in SQLite does 
0600: 61 20 67 6f 6f 64 20 6a 6f 62 2e 0a 48 6f 77 65  a good job..Howe
0610: 76 65 72 2c 20 74 68 65 20 71 75 65 72 79 20 70  ver, the query p
0620: 6c 61 6e 6e 65 72 20 6e 65 65 64 73 20 69 6e 64  lanner needs ind
0630: 69 63 65 73 20 74 6f 0a 77 6f 72 6b 20 77 69 74  ices to.work wit
0640: 68 2e 20 20 0a 54 68 65 73 65 20 69 6e 64 69 63  h.  .These indic
0650: 65 73 20 6d 75 73 74 20 6e 6f 72 6d 61 6c 6c 79  es must normally
0660: 20 62 65 20 61 64 64 65 64 20 62 79 20 70 72 6f   be added by pro
0670: 67 72 61 6d 6d 65 72 73 2e 0a 52 61 72 65 6c 79  grammers..Rarely
0680: 2c 20 74 68 65 20 71 75 65 72 79 20 70 6c 61 6e  , the query plan
0690: 6e 65 72 20 41 49 20 77 69 6c 6c 20 6d 61 6b 65  ner AI will make
06a0: 20 61 20 73 75 62 6f 70 74 69 6d 61 6c 20 61 6c   a suboptimal al
06b0: 67 6f 72 69 74 68 6d 0a 63 68 6f 69 63 65 2e 0a  gorithm.choice..
06c0: 49 6e 20 74 68 6f 73 65 20 63 61 73 65 73 2c 20  In those cases, 
06d0: 70 72 6f 67 72 61 6d 6d 65 72 73 20 6d 61 79 20  programmers may 
06e0: 77 61 6e 74 20 74 6f 20 70 72 6f 76 69 64 65 20  want to provide 
06f0: 61 64 64 69 74 69 6f 6e 61 6c 0a 68 69 6e 74 73  additional.hints
0700: 20 74 6f 20 68 65 6c 70 20 74 68 65 20 71 75 65   to help the que
0710: 72 79 20 70 6c 61 6e 6e 65 72 20 64 6f 20 61 20  ry planner do a 
0720: 62 65 74 74 65 72 20 6a 6f 62 2e 0a 3c 2f 70 3e  better job..</p>
0730: 0a 0a 3c 70 3e 0a 54 68 69 73 20 64 6f 63 75 6d  ..<p>.This docum
0740: 65 6e 74 20 70 72 6f 76 69 64 65 73 20 62 61 63  ent provides bac
0750: 6b 67 72 6f 75 6e 64 20 69 6e 66 6f 72 6d 61 74  kground informat
0760: 69 6f 6e 20 61 62 6f 75 74 20 68 6f 77 20 74 68  ion about how th
0770: 65 0a 53 51 4c 69 74 65 20 71 75 65 72 79 20 70  e.SQLite query p
0780: 6c 61 6e 6e 65 72 20 61 6e 64 20 71 75 65 72 79  lanner and query
0790: 20 65 6e 67 69 6e 65 20 77 6f 72 6b 2e 0a 50 72   engine work..Pr
07a0: 6f 67 72 61 6d 6d 65 72 73 20 63 61 6e 20 75 73  ogrammers can us
07b0: 65 20 74 68 69 73 20 69 6e 66 6f 72 6d 61 74 69  e this informati
07c0: 6f 6e 20 74 6f 20 68 65 6c 70 20 63 72 65 61 74  on to help creat
07d0: 65 20 62 65 74 74 65 72 0a 69 6e 64 65 78 65 73  e better.indexes
07e0: 2c 20 61 6e 64 20 70 72 6f 76 69 64 65 20 68 69  , and provide hi
07f0: 6e 74 73 20 74 6f 20 68 65 6c 70 20 74 68 65 20  nts to help the 
0800: 71 75 65 72 79 20 70 6c 61 6e 6e 65 72 20 77 68  query planner wh
0810: 65 6e 0a 6e 65 65 64 65 64 2e 0a 3c 2f 70 3e 0a  en.needed..</p>.
0820: 0a 3c 70 3e 0a 41 64 64 69 74 69 6f 6e 61 6c 20  .<p>.Additional 
0830: 69 6e 66 6f 72 6d 61 74 69 6f 6e 20 69 73 20 70  information is p
0840: 72 6f 76 69 64 65 64 20 69 6e 20 74 68 65 0a 5b  rovided in the.[
0850: 53 51 4c 69 74 65 20 71 75 65 72 79 20 70 6c 61  SQLite query pla
0860: 6e 6e 65 72 5d 20 61 6e 64 20 0a 5b 6e 65 78 74  nner] and .[next
0870: 20 67 65 6e 65 72 61 74 69 6f 6e 20 71 75 65 72   generation quer
0880: 79 20 70 6c 61 6e 6e 65 72 5d 20 64 6f 63 75 6d  y planner] docum
0890: 65 6e 74 73 2e 0a 3c 2f 70 3e 0a 0a 3c 74 63 6c  ents..</p>..<tcl
08a0: 3e 68 64 5f 66 72 61 67 6d 65 6e 74 20 73 65 61  >hd_fragment sea
08b0: 72 63 68 69 6e 67 20 73 74 72 61 74 65 67 69 65  rching strategie
08c0: 73 3c 2f 74 63 6c 3e 0a 3c 68 31 3e 20 53 65 61  s</tcl>.<h1> Sea
08d0: 72 63 68 69 6e 67 3c 2f 68 31 3e 0a 0a 3c 68 32  rching</h1>..<h2
08e0: 3e 20 54 61 62 6c 65 73 20 57 69 74 68 6f 75 74  > Tables Without
08f0: 20 49 6e 64 69 63 65 73 3c 2f 68 32 3e 0a 0a 3c   Indices</h2>..<
0900: 70 3e 0a 4d 6f 73 74 20 74 61 62 6c 65 73 20 69  p>.Most tables i
0910: 6e 20 53 51 4c 69 74 65 20 63 6f 6e 73 69 73 74  n SQLite consist
0920: 20 6f 66 20 7a 65 72 6f 20 6f 72 20 6d 6f 72 65   of zero or more
0930: 20 72 6f 77 73 20 77 69 74 68 20 61 20 75 6e 69   rows with a uni
0940: 71 75 65 20 69 6e 74 65 67 65 72 0a 6b 65 79 20  que integer.key 
0950: 28 74 68 65 20 5b 72 6f 77 69 64 5d 20 6f 72 20  (the [rowid] or 
0960: 5b 49 4e 54 45 47 45 52 20 50 52 49 4d 41 52 59  [INTEGER PRIMARY
0970: 20 4b 45 59 5d 29 20 66 6f 6c 6c 6f 77 65 64 20   KEY]) followed 
0980: 62 79 20 63 6f 6e 74 65 6e 74 2e 20 20 0a 28 54  by content.  .(T
0990: 68 65 20 65 78 63 65 70 74 69 6f 6e 20 69 73 20  he exception is 
09a0: 5b 57 49 54 48 4f 55 54 20 52 4f 57 49 44 5d 20  [WITHOUT ROWID] 
09b0: 74 61 62 6c 65 73 2e 29 0a 54 68 65 20 72 6f 77  tables.).The row
09c0: 73 0a 61 72 65 20 6c 6f 67 69 63 61 6c 6c 79 20  s.are logically 
09d0: 73 74 6f 72 65 64 20 69 6e 20 6f 72 64 65 72 20  stored in order 
09e0: 6f 66 20 69 6e 63 72 65 61 73 69 6e 67 20 72 6f  of increasing ro
09f0: 77 69 64 2e 20 20 41 73 20 61 6e 20 65 78 61 6d  wid.  As an exam
0a00: 70 6c 65 2c 20 74 68 69 73 0a 61 72 74 69 63 6c  ple, this.articl
0a10: 65 20 75 73 65 73 20 61 20 74 61 62 6c 65 20 6e  e uses a table n
0a20: 61 6d 65 64 20 22 46 72 75 69 74 73 46 6f 72 53  amed "FruitsForS
0a30: 61 6c 65 22 20 77 68 69 63 68 20 72 65 6c 61 74  ale" which relat
0a40: 65 73 20 76 61 72 69 6f 75 73 20 66 72 75 69 74  es various fruit
0a50: 73 20 0a 74 6f 20 74 68 65 20 73 74 61 74 65 0a  s .to the state.
0a60: 77 68 65 72 65 20 74 68 65 79 20 61 72 65 20 67  where they are g
0a70: 72 6f 77 6e 20 61 6e 64 20 74 68 65 69 72 20 75  rown and their u
0a80: 6e 69 74 20 70 72 69 63 65 20 61 74 20 6d 61 72  nit price at mar
0a90: 6b 65 74 2e 20 20 54 68 65 20 73 63 68 65 6d 61  ket.  The schema
0aa0: 20 69 73 20 74 68 69 73 3a 0a 3c 2f 70 3e 0a 0a   is this:.</p>..
0ab0: 3c 74 63 6c 3e 63 6f 64 65 20 7b 0a 43 52 45 41  <tcl>code {.CREA
0ac0: 54 45 20 54 41 42 4c 45 20 46 72 75 69 74 73 46  TE TABLE FruitsF
0ad0: 6f 72 53 61 6c 65 28 0a 20 20 46 72 75 69 74 20  orSale(.  Fruit 
0ae0: 54 45 58 54 2c 0a 20 20 53 74 61 74 65 20 54 45  TEXT,.  State TE
0af0: 58 54 2c 0a 20 20 50 72 69 63 65 20 52 45 41 4c  XT,.  Price REAL
0b00: 0a 29 3b 0a 7d 3c 2f 74 63 6c 3e 0a 0a 3c 70 3e  .);.}</tcl>..<p>
0b10: 0a 57 69 74 68 20 73 6f 6d 65 20 28 61 72 62 69  .With some (arbi
0b20: 74 72 61 72 79 29 20 64 61 74 61 2c 20 73 75 63  trary) data, suc
0b30: 68 20 61 20 74 61 62 6c 65 20 6d 69 67 68 74 20  h a table might 
0b40: 62 65 20 6c 6f 67 69 63 61 6c 6c 79 20 73 74 6f  be logically sto
0b50: 72 65 64 20 6f 6e 20 64 69 73 6b 0a 61 73 20 73  red on disk.as s
0b60: 68 6f 77 6e 20 69 6e 20 66 69 67 75 72 65 20 31  hown in figure 1
0b70: 3a 0a 3c 2f 70 3e 0a 0a 3c 74 63 6c 3e 66 69 67  :.</p>..<tcl>fig
0b80: 75 72 65 20 31 20 23 66 69 67 31 20 74 61 62 2e  ure 1 #fig1 tab.
0b90: 67 69 66 20 7b 4c 6f 67 69 63 61 6c 20 4c 61 79  gif {Logical Lay
0ba0: 6f 75 74 20 4f 66 20 54 61 62 6c 65 20 22 46 72  out Of Table "Fr
0bb0: 75 69 74 73 46 6f 72 53 61 6c 65 22 7d 3c 2f 74  uitsForSale"}</t
0bc0: 63 6c 3e 0a 0a 3c 70 3e 0a 49 6e 20 74 68 69 73  cl>..<p>.In this
0bd0: 20 65 78 61 6d 70 6c 65 2c 20 74 68 65 20 72 6f   example, the ro
0be0: 77 69 64 73 20 61 72 65 20 6e 6f 74 0a 63 6f 6e  wids are not.con
0bf0: 73 65 63 75 74 69 76 65 20 62 75 74 20 74 68 65  secutive but the
0c00: 79 20 61 72 65 20 6f 72 64 65 72 65 64 2e 20 20  y are ordered.  
0c10: 53 51 4c 69 74 65 20 75 73 75 61 6c 6c 79 20 63  SQLite usually c
0c20: 72 65 61 74 65 73 20 72 6f 77 69 64 73 20 62 65  reates rowids be
0c30: 67 69 6e 6e 69 6e 67 0a 77 69 74 68 20 6f 6e 65  ginning.with one
0c40: 20 61 6e 64 20 69 6e 63 72 65 61 73 69 6e 67 20   and increasing 
0c50: 62 79 20 6f 6e 65 20 77 69 74 68 20 65 61 63 68  by one with each
0c60: 20 61 64 64 65 64 20 72 6f 77 2e 20 20 42 75 74   added row.  But
0c70: 20 69 66 20 72 6f 77 73 20 61 72 65 20 0a 64 65   if rows are .de
0c80: 6c 65 74 65 64 2c 20 67 61 70 73 20 63 61 6e 20  leted, gaps can 
0c90: 61 70 70 65 61 72 20 69 6e 20 74 68 65 20 73 65  appear in the se
0ca0: 71 75 65 6e 63 65 2e 20 20 41 6e 64 20 74 68 65  quence.  And the
0cb0: 20 61 70 70 6c 69 63 61 74 69 6f 6e 20 63 61 6e   application can
0cc0: 20 63 6f 6e 74 72 6f 6c 0a 74 68 65 20 72 6f 77   control.the row
0cd0: 69 64 20 61 73 73 69 67 6e 65 64 20 69 66 20 64  id assigned if d
0ce0: 65 73 69 72 65 64 2c 20 73 6f 20 74 68 61 74 20  esired, so that 
0cf0: 72 6f 77 73 20 61 72 65 20 6e 6f 74 20 6e 65 63  rows are not nec
0d00: 65 73 73 61 72 69 6c 79 20 69 6e 73 65 72 74 65  essarily inserte
0d10: 64 20 0a 61 74 20 74 68 65 20 62 6f 74 74 6f 6d  d .at the bottom
0d20: 2e 20 20 42 75 74 20 72 65 67 61 72 64 6c 65 73  .  But regardles
0d30: 73 20 6f 66 20 77 68 61 74 20 68 61 70 70 65 6e  s of what happen
0d40: 73 2c 20 74 68 65 20 72 6f 77 69 64 73 20 61 72  s, the rowids ar
0d50: 65 20 61 6c 77 61 79 73 20 0a 75 6e 69 71 75 65  e always .unique
0d60: 20 61 6e 64 20 69 6e 20 73 74 72 69 63 74 6c 79   and in strictly
0d70: 20 61 73 63 65 6e 64 69 6e 67 20 6f 72 64 65 72   ascending order
0d80: 2e 0a 3c 2f 70 3e 0a 0a 3c 70 3e 0a 53 75 70 70  ..</p>..<p>.Supp
0d90: 6f 73 65 20 79 6f 75 20 77 61 6e 74 20 74 6f 20  ose you want to 
0da0: 6c 6f 6f 6b 20 75 70 20 74 68 65 20 70 72 69 63  look up the pric
0db0: 65 20 6f 66 20 70 65 61 63 68 65 73 2e 20 20 54  e of peaches.  T
0dc0: 68 65 20 71 75 65 72 79 20 77 6f 75 6c 64 0a 62  he query would.b
0dd0: 65 20 61 73 20 66 6f 6c 6c 6f 77 73 3a 0a 3c 2f  e as follows:.</
0de0: 70 3e 0a 0a 3c 74 63 6c 3e 63 6f 64 65 20 7b 0a  p>..<tcl>code {.
0df0: 53 45 4c 45 43 54 20 70 72 69 63 65 20 46 52 4f  SELECT price FRO
0e00: 4d 20 66 72 75 69 74 73 66 6f 72 73 61 6c 65 20  M fruitsforsale 
0e10: 57 48 45 52 45 20 66 72 75 69 74 3d 27 50 65 61  WHERE fruit='Pea
0e20: 63 68 27 3b 0a 7d 3c 2f 74 63 6c 3e 0a 0a 3c 70  ch';.}</tcl>..<p
0e30: 3e 0a 54 6f 20 73 61 74 69 73 66 79 20 74 68 69  >.To satisfy thi
0e40: 73 20 71 75 65 72 79 2c 20 53 51 4c 69 74 65 20  s query, SQLite 
0e50: 72 65 61 64 73 20 65 76 65 72 79 20 72 6f 77 20  reads every row 
0e60: 6f 75 74 20 6f 66 20 74 68 65 0a 74 61 62 6c 65  out of the.table
0e70: 2c 20 63 68 65 63 6b 73 20 74 6f 20 73 65 65 20  , checks to see 
0e80: 69 66 20 74 68 65 20 22 66 72 75 69 74 22 20 63  if the "fruit" c
0e90: 6f 6c 75 6d 6e 20 68 61 73 20 74 68 65 20 76 61  olumn has the va
0ea0: 6c 75 65 20 6f 66 20 22 50 65 61 63 68 22 20 61  lue of "Peach" a
0eb0: 6e 64 20 69 66 0a 73 6f 2c 20 6f 75 74 70 75 74  nd if.so, output
0ec0: 73 20 74 68 65 20 22 70 72 69 63 65 22 20 63 6f  s the "price" co
0ed0: 6c 75 6d 6e 20 66 72 6f 6d 20 74 68 61 74 20 72  lumn from that r
0ee0: 6f 77 2e 20 20 54 68 65 20 70 72 6f 63 65 73 73  ow.  The process
0ef0: 20 69 73 20 69 6c 6c 75 73 74 72 61 74 65 64 0a   is illustrated.
0f00: 62 79 20 3c 61 20 68 72 65 66 3d 22 23 66 69 67  by <a href="#fig
0f10: 32 22 3e 66 69 67 75 72 65 20 32 3c 2f 61 3e 20  2">figure 2</a> 
0f20: 62 65 6c 6f 77 2e 0a 54 68 69 73 20 69 73 20 61  below..This is a
0f30: 6c 67 6f 72 69 74 68 6d 20 69 73 20 63 61 6c 6c  lgorithm is call
0f40: 65 64 20 61 20 3c 69 3e 66 75 6c 6c 20 74 61 62  ed a <i>full tab
0f50: 6c 65 20 73 63 61 6e 3c 2f 69 3e 20 0a 73 69 6e  le scan</i> .sin
0f60: 63 65 20 74 68 65 20 65 6e 74 69 72 65 20 63 6f  ce the entire co
0f70: 6e 74 65 6e 74 20 6f 66 20 74 68 65 0a 74 61 62  ntent of the.tab
0f80: 6c 65 20 6d 75 73 74 20 62 65 20 72 65 61 64 20  le must be read 
0f90: 61 6e 64 20 65 78 61 6d 69 6e 65 64 20 69 6e 20  and examined in 
0fa0: 6f 72 64 65 72 20 74 6f 20 66 69 6e 64 20 74 68  order to find th
0fb0: 65 20 6f 6e 65 20 72 6f 77 20 6f 66 20 69 6e 74  e one row of int
0fc0: 65 72 65 73 74 2e 0a 57 69 74 68 20 61 20 74 61  erest..With a ta
0fd0: 62 6c 65 20 6f 66 20 6f 6e 6c 79 20 37 20 72 6f  ble of only 7 ro
0fe0: 77 73 2c 20 61 20 66 75 6c 6c 20 74 61 62 6c 65  ws, a full table
0ff0: 20 73 63 61 6e 20 69 73 20 61 63 63 65 70 74 61   scan is accepta
1000: 62 6c 65 2c 20 0a 62 75 74 20 69 66 20 74 68 65  ble, .but if the
1010: 20 74 61 62 6c 65 20 63 6f 6e 74 61 69 6e 65 64   table contained
1020: 20 37 20 6d 69 6c 6c 69 6f 6e 20 72 6f 77 73 2c   7 million rows,
1030: 20 61 20 66 75 6c 6c 20 74 61 62 6c 65 20 73 63   a full table sc
1040: 61 6e 20 6d 69 67 68 74 20 72 65 61 64 20 0a 6d  an might read .m
1050: 65 67 61 62 79 74 65 73 20 6f 66 20 63 6f 6e 74  egabytes of cont
1060: 65 6e 74 20 69 6e 20 6f 72 64 65 72 20 74 6f 20  ent in order to 
1070: 66 69 6e 64 20 61 20 73 69 6e 67 6c 65 20 38 2d  find a single 8-
1080: 62 79 74 65 20 6e 75 6d 62 65 72 2e 20 20 0a 46  byte number.  .F
1090: 6f 72 20 74 68 61 74 20 72 65 61 73 6f 6e 2c 20  or that reason, 
10a0: 6f 6e 65 20 6e 6f 72 6d 61 6c 6c 79 20 74 72 69  one normally tri
10b0: 65 73 20 74 6f 20 61 76 6f 69 64 20 66 75 6c 6c  es to avoid full
10c0: 20 74 61 62 6c 65 20 73 63 61 6e 73 2e 0a 3c 2f   table scans..</
10d0: 70 3e 0a 0a 3c 74 63 6c 3e 66 69 67 75 72 65 20  p>..<tcl>figure 
10e0: 32 20 23 66 69 67 32 20 66 75 6c 6c 73 63 61 6e  2 #fig2 fullscan
10f0: 2e 67 69 66 20 7b 46 75 6c 6c 20 54 61 62 6c 65  .gif {Full Table
1100: 20 53 63 61 6e 7d 3c 2f 74 63 6c 3e 0a 0a 3c 68   Scan}</tcl>..<h
1110: 32 3e 20 4c 6f 6f 6b 75 70 20 42 79 20 52 6f 77  2> Lookup By Row
1120: 69 64 3c 2f 68 32 3e 0a 0a 3c 70 3e 0a 4f 6e 65  id</h2>..<p>.One
1130: 20 74 65 63 68 6e 69 71 75 65 20 66 6f 72 20 61   technique for a
1140: 76 6f 69 64 69 6e 67 20 61 20 66 75 6c 6c 20 74  voiding a full t
1150: 61 62 6c 65 20 73 63 61 6e 20 69 73 20 74 6f 20  able scan is to 
1160: 64 6f 20 6c 6f 6f 6b 75 70 73 20 62 79 0a 72 6f  do lookups by.ro
1170: 77 69 64 20 28 6f 72 20 62 79 20 74 68 65 20 65  wid (or by the e
1180: 71 75 69 76 61 6c 65 6e 74 20 5b 49 4e 54 45 47  quivalent [INTEG
1190: 45 52 20 50 52 49 4d 41 52 59 20 4b 45 59 5d 29  ER PRIMARY KEY])
11a0: 2e 20 20 20 54 6f 20 6c 6f 6f 6b 75 70 20 74 68  .   To lookup th
11b0: 65 0a 70 72 69 63 65 20 6f 66 20 70 65 61 63 68  e.price of peach
11c0: 65 73 2c 20 6f 6e 65 20 77 6f 75 6c 64 20 71 75  es, one would qu
11d0: 65 72 79 20 66 6f 72 20 74 68 65 20 65 6e 74 72  ery for the entr
11e0: 79 20 77 69 74 68 20 61 20 72 6f 77 69 64 20 6f  y with a rowid o
11f0: 66 20 34 3a 0a 3c 2f 70 3e 0a 0a 3c 74 63 6c 3e  f 4:.</p>..<tcl>
1200: 63 6f 64 65 20 7b 0a 53 45 4c 45 43 54 20 70 72  code {.SELECT pr
1210: 69 63 65 20 46 52 4f 4d 20 66 72 75 69 74 73 66  ice FROM fruitsf
1220: 6f 72 73 61 6c 65 20 57 48 45 52 45 20 72 6f 77  orsale WHERE row
1230: 69 64 3d 34 3b 0a 7d 3c 2f 74 63 6c 3e 0a 0a 3c  id=4;.}</tcl>..<
1240: 70 3e 0a 53 69 6e 63 65 20 74 68 65 20 69 6e 66  p>.Since the inf
1250: 6f 72 6d 61 74 69 6f 6e 20 69 73 20 73 74 6f 72  ormation is stor
1260: 65 64 20 69 6e 20 74 68 65 20 74 61 62 6c 65 20  ed in the table 
1270: 69 6e 20 72 6f 77 69 64 20 6f 72 64 65 72 2c 20  in rowid order, 
1280: 53 51 4c 69 74 65 0a 63 61 6e 20 66 69 6e 64 20  SQLite.can find 
1290: 74 68 65 20 63 6f 72 72 65 63 74 20 72 6f 77 20  the correct row 
12a0: 75 73 69 6e 67 20 61 20 62 69 6e 61 72 79 20 73  using a binary s
12b0: 65 61 72 63 68 2e 0a 49 66 20 74 68 65 20 74 61  earch..If the ta
12c0: 62 6c 65 20 63 6f 6e 74 61 69 6e 73 20 4e 20 65  ble contains N e
12d0: 6c 65 6d 65 6e 74 2c 20 74 68 65 20 74 69 6d 65  lement, the time
12e0: 20 72 65 71 75 69 72 65 64 20 74 6f 20 6c 6f 6f   required to loo
12f0: 6b 20 75 70 20 74 68 65 0a 64 65 73 69 72 65 64  k up the.desired
1300: 20 72 6f 77 20 69 73 20 70 72 6f 70 6f 72 74 69   row is proporti
1310: 6f 6e 61 6c 20 74 6f 20 6c 6f 67 4e 20 72 61 74  onal to logN rat
1320: 68 65 72 20 74 68 61 6e 20 62 65 69 6e 67 20 70  her than being p
1330: 72 6f 70 6f 72 74 69 6f 6e 61 6c 0a 74 6f 20 4e  roportional.to N
1340: 20 61 73 20 69 6e 20 61 20 66 75 6c 6c 20 74 61   as in a full ta
1350: 62 6c 65 20 73 63 61 6e 2e 20 20 49 66 20 74 68  ble scan.  If th
1360: 65 20 74 61 62 6c 65 20 63 6f 6e 74 61 69 6e 73  e table contains
1370: 20 31 30 20 6d 69 6c 6c 69 6f 6e 20 65 6c 65 6d   10 million elem
1380: 65 6e 74 73 2c 0a 74 68 61 74 20 6d 65 61 6e 73  ents,.that means
1390: 20 74 68 65 20 71 75 65 72 79 20 77 69 6c 6c 20   the query will 
13a0: 62 65 20 6f 6e 20 74 68 65 20 6f 72 64 65 72 20  be on the order 
13b0: 6f 66 20 4e 2f 6c 6f 67 4e 20 6f 72 20 61 62 6f  of N/logN or abo
13c0: 75 74 20 31 20 6d 69 6c 6c 69 6f 6e 0a 74 69 6d  ut 1 million.tim
13d0: 65 73 20 66 61 73 74 65 72 2e 0a 3c 2f 70 3e 0a  es faster..</p>.
13e0: 0a 3c 74 63 6c 3e 66 69 67 75 72 65 20 33 20 23  .<tcl>figure 3 #
13f0: 66 69 67 33 20 72 6f 77 69 64 6c 75 2e 67 69 66  fig3 rowidlu.gif
1400: 20 7b 4c 6f 6f 6b 75 70 20 42 79 20 52 6f 77 69   {Lookup By Rowi
1410: 64 7d 3c 2f 74 63 6c 3e 0a 0a 3c 68 32 3e 20 4c  d}</tcl>..<h2> L
1420: 6f 6f 6b 75 70 20 42 79 20 49 6e 64 65 78 3c 2f  ookup By Index</
1430: 68 32 3e 0a 3c 70 3e 0a 54 68 65 20 70 72 6f 62  h2>.<p>.The prob
1440: 6c 65 6d 20 77 69 74 68 20 6c 6f 6f 6b 69 6e 67  lem with looking
1450: 20 75 70 20 69 6e 66 6f 72 6d 61 74 69 6f 6e 20   up information 
1460: 62 79 20 72 6f 77 69 64 20 69 73 20 74 68 61 74  by rowid is that
1470: 20 79 6f 75 20 70 72 6f 62 61 62 6c 79 0a 64 6f   you probably.do
1480: 20 6e 6f 74 20 63 61 72 65 20 77 68 61 74 20 74   not care what t
1490: 68 65 20 70 72 69 63 65 20 6f 66 20 22 69 74 65  he price of "ite
14a0: 6d 20 34 22 20 69 73 20 2d 20 79 6f 75 20 77 61  m 4" is - you wa
14b0: 6e 74 20 74 6f 20 6b 6e 6f 77 20 74 68 65 20 70  nt to know the p
14c0: 72 69 63 65 0a 6f 66 20 70 65 61 63 68 65 73 2e  rice.of peaches.
14d0: 20 20 41 6e 64 20 73 6f 20 61 20 72 6f 77 69 64    And so a rowid
14e0: 20 6c 6f 6f 6b 75 70 20 69 73 20 6e 6f 74 20 68   lookup is not h
14f0: 65 6c 70 66 75 6c 2e 0a 3c 2f 70 3e 0a 0a 3c 70  elpful..</p>..<p
1500: 3e 0a 54 6f 20 6d 61 6b 65 20 74 68 65 20 6f 72  >.To make the or
1510: 69 67 69 6e 61 6c 20 71 75 65 72 79 20 6d 6f 72  iginal query mor
1520: 65 20 65 66 66 69 63 69 65 6e 74 2c 20 77 65 20  e efficient, we 
1530: 63 61 6e 20 61 64 64 20 61 6e 20 69 6e 64 65 78  can add an index
1540: 20 6f 6e 20 74 68 65 0a 22 66 72 75 69 74 22 20   on the."fruit" 
1550: 63 6f 6c 75 6d 6e 20 6f 66 20 74 68 65 20 22 66  column of the "f
1560: 72 75 69 74 73 66 6f 72 73 61 6c 65 22 20 74 61  ruitsforsale" ta
1570: 62 6c 65 20 6c 69 6b 65 20 74 68 69 73 3a 0a 3c  ble like this:.<
1580: 2f 70 3e 0a 0a 3c 74 63 6c 3e 63 6f 64 65 20 7b  /p>..<tcl>code {
1590: 0a 43 52 45 41 54 45 20 49 4e 44 45 58 20 49 64  .CREATE INDEX Id
15a0: 78 31 20 4f 4e 20 66 72 75 69 74 73 66 6f 72 73  x1 ON fruitsfors
15b0: 61 6c 65 28 66 72 75 69 74 29 3b 0a 7d 3c 2f 74  ale(fruit);.}</t
15c0: 63 6c 3e 0a 0a 3c 70 3e 0a 41 6e 20 69 6e 64 65  cl>..<p>.An inde
15d0: 78 20 69 73 20 61 6e 6f 74 68 65 72 20 74 61 62  x is another tab
15e0: 6c 65 20 73 69 6d 69 6c 61 72 20 74 6f 20 74 68  le similar to th
15f0: 65 20 6f 72 69 67 69 6e 61 6c 20 22 66 72 75 69  e original "frui
1600: 74 73 66 6f 72 73 61 6c 65 22 20 74 61 62 6c 65  tsforsale" table
1610: 0a 62 75 74 20 77 69 74 68 20 74 68 65 20 63 6f  .but with the co
1620: 6e 74 65 6e 74 20 28 74 68 65 20 66 72 75 69 74  ntent (the fruit
1630: 20 63 6f 6c 75 6d 6e 20 69 6e 20 74 68 69 73 20   column in this 
1640: 63 61 73 65 29 20 73 74 6f 72 65 64 20 69 6e 20  case) stored in 
1650: 66 72 6f 6e 74 20 6f 66 20 74 68 65 0a 72 6f 77  front of the.row
1660: 69 64 20 61 6e 64 20 77 69 74 68 20 61 6c 6c 20  id and with all 
1670: 72 6f 77 73 20 69 6e 20 63 6f 6e 74 65 6e 74 20  rows in content 
1680: 6f 72 64 65 72 2e 0a 3c 61 20 68 72 65 66 3d 22  order..<a href="
1690: 23 66 69 67 34 22 3e 46 69 67 75 72 65 20 34 3c  #fig4">Figure 4<
16a0: 2f 61 3e 20 67 69 76 65 73 20 61 20 6c 6f 67 69  /a> gives a logi
16b0: 63 61 6c 20 76 69 65 77 20 6f 66 20 74 68 65 20  cal view of the 
16c0: 49 64 78 31 20 69 6e 64 65 78 2e 0a 54 68 65 20  Idx1 index..The 
16d0: 22 66 72 75 69 74 22 20 63 6f 6c 75 6d 6e 20 69  "fruit" column i
16e0: 73 20 74 68 65 20 70 72 69 6d 61 72 79 20 6b 65  s the primary ke
16f0: 79 20 75 73 65 64 20 74 6f 20 6f 72 64 65 72 20  y used to order 
1700: 74 68 65 20 65 6c 65 6d 65 6e 74 73 20 6f 66 20  the elements of 
1710: 74 68 65 0a 74 61 62 6c 65 20 61 6e 64 20 74 68  the.table and th
1720: 65 20 22 72 6f 77 69 64 22 20 69 73 20 74 68 65  e "rowid" is the
1730: 20 73 65 63 6f 6e 64 61 72 79 20 6b 65 79 20 75   secondary key u
1740: 73 65 64 20 74 6f 20 62 72 65 61 6b 20 74 68 65  sed to break the
1750: 20 74 69 65 20 77 68 65 6e 0a 74 77 6f 20 6f 72   tie when.two or
1760: 20 6d 6f 72 65 20 72 6f 77 73 20 68 61 76 65 20   more rows have 
1770: 74 68 65 20 73 61 6d 65 20 22 66 72 75 69 74 22  the same "fruit"
1780: 2e 20 20 49 6e 20 74 68 65 20 65 78 61 6d 70 6c  .  In the exampl
1790: 65 2c 20 74 68 65 20 72 6f 77 69 64 0a 68 61 73  e, the rowid.has
17a0: 20 74 6f 20 62 65 20 75 73 65 64 20 61 73 20 61   to be used as a
17b0: 20 74 69 65 2d 62 72 65 61 6b 65 72 20 66 6f 72   tie-breaker for
17c0: 20 74 68 65 20 22 4f 72 61 6e 67 65 22 20 72 6f   the "Orange" ro
17d0: 77 73 2e 0a 4e 6f 74 69 63 65 20 74 68 61 74 20  ws..Notice that 
17e0: 73 69 6e 63 65 20 74 68 65 20 72 6f 77 69 64 0a  since the rowid.
17f0: 69 73 20 61 6c 77 61 79 73 20 75 6e 69 71 75 65  is always unique
1800: 20 6f 76 65 72 20 61 6c 6c 20 65 6c 65 6d 65 6e   over all elemen
1810: 74 73 20 6f 66 20 74 68 65 20 6f 72 69 67 69 6e  ts of the origin
1820: 61 6c 20 74 61 62 6c 65 2c 20 74 68 65 20 63 6f  al table, the co
1830: 6d 70 6f 73 69 74 65 20 6b 65 79 0a 6f 66 20 22  mposite key.of "
1840: 66 72 75 69 74 22 20 66 6f 6c 6c 6f 77 65 64 20  fruit" followed 
1850: 62 79 20 22 72 6f 77 69 64 22 20 77 69 6c 6c 20  by "rowid" will 
1860: 62 65 20 75 6e 69 71 75 65 20 6f 76 65 72 20 61  be unique over a
1870: 6c 6c 20 65 6c 65 6d 65 6e 74 73 20 6f 66 20 74  ll elements of t
1880: 68 65 20 69 6e 64 65 78 2e 0a 3c 2f 70 3e 0a 0a  he index..</p>..
1890: 3c 74 63 6c 3e 66 69 67 75 72 65 20 34 20 23 66  <tcl>figure 4 #f
18a0: 69 67 34 20 69 64 78 31 2e 67 69 66 20 7b 41 6e  ig4 idx1.gif {An
18b0: 20 49 6e 64 65 78 20 4f 6e 20 54 68 65 20 46 72   Index On The Fr
18c0: 75 69 74 20 43 6f 6c 75 6d 6e 7d 3c 2f 74 63 6c  uit Column}</tcl
18d0: 3e 0a 0a 3c 70 3e 0a 54 68 69 73 20 6e 65 77 20  >..<p>.This new 
18e0: 69 6e 64 65 78 20 63 61 6e 20 62 65 20 75 73 65  index can be use
18f0: 64 20 74 6f 20 69 6d 70 6c 65 6d 65 6e 74 20 61  d to implement a
1900: 20 66 61 73 74 65 72 20 61 6c 67 6f 72 69 74 68   faster algorith
1910: 6d 20 66 6f 72 20 74 68 65 0a 6f 72 69 67 69 6e  m for the.origin
1920: 61 6c 20 22 50 72 69 63 65 20 6f 66 20 50 65 61  al "Price of Pea
1930: 63 68 65 73 22 20 71 75 65 72 79 2e 0a 3c 2f 70  ches" query..</p
1940: 3e 0a 0a 3c 74 63 6c 3e 63 6f 64 65 20 7b 0a 53  >..<tcl>code {.S
1950: 45 4c 45 43 54 20 70 72 69 63 65 20 46 52 4f 4d  ELECT price FROM
1960: 20 66 72 75 69 74 73 66 6f 72 73 61 6c 65 20 57   fruitsforsale W
1970: 48 45 52 45 20 66 72 75 69 74 3d 27 50 65 61 63  HERE fruit='Peac
1980: 68 27 3b 0a 7d 3c 2f 74 63 6c 3e 0a 0a 3c 70 3e  h';.}</tcl>..<p>
1990: 0a 54 68 65 20 71 75 65 72 79 20 73 74 61 72 74  .The query start
19a0: 73 20 62 79 20 64 6f 69 6e 67 20 61 20 62 69 6e  s by doing a bin
19b0: 61 72 79 20 73 65 61 72 63 68 20 6f 6e 20 74 68  ary search on th
19c0: 65 20 49 64 78 31 20 69 6e 64 65 78 20 66 6f 72  e Idx1 index for
19d0: 20 65 6e 74 72 69 65 73 0a 74 68 61 74 20 68 61   entries.that ha
19e0: 76 65 20 66 72 75 69 74 3d 27 50 65 61 63 68 27  ve fruit='Peach'
19f0: 2e 20 20 53 51 4c 69 74 65 20 63 61 6e 20 64 6f  .  SQLite can do
1a00: 20 74 68 69 73 20 62 69 6e 61 72 79 20 73 65 61   this binary sea
1a10: 72 63 68 20 6f 6e 20 74 68 65 20 49 64 78 31 20  rch on the Idx1 
1a20: 69 6e 64 65 78 0a 62 75 74 20 6e 6f 74 20 6f 6e  index.but not on
1a30: 20 74 68 65 20 6f 72 69 67 69 6e 61 6c 20 46 72   the original Fr
1a40: 75 69 74 73 46 6f 72 53 61 6c 65 20 74 61 62 6c  uitsForSale tabl
1a50: 65 20 62 65 63 61 75 73 65 20 74 68 65 20 72 6f  e because the ro
1a60: 77 73 20 69 6e 20 49 64 78 31 20 61 72 65 20 73  ws in Idx1 are s
1a70: 6f 72 74 65 64 0a 62 79 20 74 68 65 20 22 66 72  orted.by the "fr
1a80: 75 69 74 22 20 63 6f 6c 75 6d 6e 2e 20 20 48 61  uit" column.  Ha
1a90: 76 69 6e 67 20 66 6f 75 6e 64 20 61 20 72 6f 77  ving found a row
1aa0: 20 69 6e 20 74 68 65 20 49 64 78 31 20 69 6e 64   in the Idx1 ind
1ab0: 65 78 20 74 68 61 74 20 68 61 73 0a 66 72 75 69  ex that has.frui
1ac0: 74 3d 27 50 65 61 63 68 27 2c 20 74 68 65 20 64  t='Peach', the d
1ad0: 61 74 61 62 61 73 65 20 65 6e 67 69 6e 65 20 63  atabase engine c
1ae0: 61 6e 20 65 78 74 72 61 63 74 20 74 68 65 20 72  an extract the r
1af0: 6f 77 69 64 20 66 6f 72 20 74 68 61 74 20 72 6f  owid for that ro
1b00: 77 2e 0a 54 68 65 6e 20 74 68 65 20 64 61 74 61  w..Then the data
1b10: 62 61 73 65 20 65 6e 67 69 6e 65 73 20 64 6f 65  base engines doe
1b20: 73 20 61 20 73 65 63 6f 6e 64 20 62 69 6e 61 72  s a second binar
1b30: 79 20 73 65 61 72 63 68 0a 6f 6e 20 74 68 65 20  y search.on the 
1b40: 6f 72 69 67 69 6e 61 6c 20 46 72 75 69 74 73 46  original FruitsF
1b50: 6f 72 53 61 6c 65 20 74 61 62 6c 65 20 74 6f 20  orSale table to 
1b60: 66 69 6e 64 20 74 68 65 0a 6f 72 69 67 69 6e 61  find the.origina
1b70: 6c 20 72 6f 77 20 74 68 61 74 20 63 6f 6e 74 61  l row that conta
1b80: 69 6e 73 20 66 72 75 69 74 3d 27 50 65 61 63 68  ins fruit='Peach
1b90: 27 2e 20 20 0a 46 72 6f 6d 20 74 68 65 20 72 6f  '.  .From the ro
1ba0: 77 20 69 6e 20 74 68 65 20 46 72 75 69 74 73 46  w in the FruitsF
1bb0: 6f 72 53 61 6c 65 20 74 61 62 6c 65 2c 0a 53 51  orSale table,.SQ
1bc0: 4c 69 74 65 20 63 61 6e 20 74 68 65 6e 20 65 78  Lite can then ex
1bd0: 74 72 61 63 74 20 74 68 65 20 76 61 6c 75 65 20  tract the value 
1be0: 6f 66 20 74 68 65 20 70 72 69 63 65 20 63 6f 6c  of the price col
1bf0: 75 6d 6e 2e 0a 54 68 69 73 20 70 72 6f 63 65 64  umn..This proced
1c00: 75 72 65 20 69 73 20 69 6c 6c 75 73 74 72 61 74  ure is illustrat
1c10: 65 64 20 62 79 20 3c 61 20 68 72 65 66 3d 22 23  ed by <a href="#
1c20: 66 69 67 35 22 3e 66 69 67 75 72 65 20 35 3c 2f  fig5">figure 5</
1c30: 61 3e 2e 0a 3c 2f 70 3e 0a 0a 3c 74 63 6c 3e 66  a>..</p>..<tcl>f
1c40: 69 67 75 72 65 20 35 20 23 66 69 67 35 20 69 64  igure 5 #fig5 id
1c50: 78 31 6c 75 31 2e 67 69 66 20 7b 49 6e 64 65 78  x1lu1.gif {Index
1c60: 65 64 20 4c 6f 6f 6b 75 70 20 46 6f 72 20 54 68  ed Lookup For Th
1c70: 65 20 50 72 69 63 65 20 4f 66 20 50 65 61 63 68  e Price Of Peach
1c80: 65 73 7d 3c 2f 74 63 6c 3e 0a 0a 3c 70 3e 0a 53  es}</tcl>..<p>.S
1c90: 51 4c 69 74 65 20 68 61 73 20 74 6f 20 64 6f 20  QLite has to do 
1ca0: 74 77 6f 20 62 69 6e 61 72 79 20 73 65 61 72 63  two binary searc
1cb0: 68 65 73 20 74 6f 20 66 69 6e 64 20 74 68 65 20  hes to find the 
1cc0: 70 72 69 63 65 20 6f 66 20 70 65 61 63 68 65 73  price of peaches
1cd0: 20 75 73 69 6e 67 0a 74 68 65 20 6d 65 74 68 6f   using.the metho
1ce0: 64 20 73 68 6f 77 20 61 62 6f 76 65 2e 20 20 42  d show above.  B
1cf0: 75 74 20 66 6f 72 20 61 20 74 61 62 6c 65 20 77  ut for a table w
1d00: 69 74 68 20 61 20 6c 61 72 67 65 20 6e 75 6d 62  ith a large numb
1d10: 65 72 20 6f 66 20 72 6f 77 73 2c 20 74 68 69 73  er of rows, this
1d20: 0a 69 73 20 73 74 69 6c 6c 20 6d 75 63 68 20 66  .is still much f
1d30: 61 73 74 65 72 20 74 68 61 6e 20 64 6f 69 6e 67  aster than doing
1d40: 20 61 20 66 75 6c 6c 20 74 61 62 6c 65 20 73 63   a full table sc
1d50: 61 6e 2e 0a 3c 2f 70 3e 0a 0a 3c 68 32 3e 20 4d  an..</p>..<h2> M
1d60: 75 6c 74 69 70 6c 65 20 52 65 73 75 6c 74 20 52  ultiple Result R
1d70: 6f 77 73 3c 2f 68 32 3e 0a 0a 3c 70 3e 0a 49 6e  ows</h2>..<p>.In
1d80: 20 74 68 65 20 70 72 65 76 69 6f 75 73 20 71 75   the previous qu
1d90: 65 72 79 20 74 68 65 20 66 72 75 69 74 3d 27 50  ery the fruit='P
1da0: 65 61 63 68 27 20 63 6f 6e 73 74 72 61 69 6e 74  each' constraint
1db0: 20 6e 61 72 72 6f 77 65 64 20 74 68 65 20 72 65   narrowed the re
1dc0: 73 75 6c 74 0a 64 6f 77 6e 20 74 6f 20 61 20 73  sult.down to a s
1dd0: 69 6e 67 6c 65 20 72 6f 77 2e 20 20 42 75 74 20  ingle row.  But 
1de0: 74 68 65 20 73 61 6d 65 20 74 65 63 68 6e 69 71  the same techniq
1df0: 75 65 20 77 6f 72 6b 73 20 65 76 65 6e 20 69 66  ue works even if
1e00: 20 6d 75 6c 74 69 70 6c 65 0a 72 6f 77 73 20 61   multiple.rows a
1e10: 72 65 20 6f 62 74 61 69 6e 65 64 2e 20 20 53 75  re obtained.  Su
1e20: 70 70 6f 73 65 20 77 65 20 6c 6f 6f 6b 65 64 20  ppose we looked 
1e30: 75 70 20 74 68 65 20 70 72 69 63 65 20 6f 66 20  up the price of 
1e40: 4f 72 61 6e 67 65 73 20 69 6e 73 74 65 61 64 20  Oranges instead 
1e50: 6f 66 0a 50 65 61 63 68 65 73 3a 0a 3c 2f 70 3e  of.Peaches:.</p>
1e60: 0a 0a 3c 74 63 6c 3e 0a 63 6f 64 65 20 7b 53 45  ..<tcl>.code {SE
1e70: 4c 45 43 54 20 70 72 69 63 65 20 46 52 4f 4d 20  LECT price FROM 
1e80: 66 72 75 69 74 73 66 6f 72 73 61 6c 65 20 57 48  fruitsforsale WH
1e90: 45 52 45 20 66 72 75 69 74 3d 27 4f 72 61 6e 67  ERE fruit='Orang
1ea0: 65 27 7d 0a 66 69 67 75 72 65 20 36 20 23 66 69  e'}.figure 6 #fi
1eb0: 67 36 20 69 64 78 31 6c 75 32 2e 67 69 66 20 7b  g6 idx1lu2.gif {
1ec0: 49 6e 64 65 78 65 64 20 4c 6f 6f 6b 75 70 20 46  Indexed Lookup F
1ed0: 6f 72 20 54 68 65 20 50 72 69 63 65 20 4f 66 20  or The Price Of 
1ee0: 4f 72 61 6e 67 65 73 7d 0a 3c 2f 74 63 6c 3e 0a  Oranges}.</tcl>.
1ef0: 0a 3c 70 3e 0a 49 6e 20 74 68 69 73 20 63 61 73  .<p>.In this cas
1f00: 65 2c 20 53 51 4c 69 74 65 20 73 74 69 6c 6c 20  e, SQLite still 
1f10: 64 6f 65 73 20 61 20 73 69 6e 67 6c 65 20 62 69  does a single bi
1f20: 6e 61 72 79 20 73 65 61 72 63 68 20 74 6f 20 66  nary search to f
1f30: 69 6e 64 20 74 68 65 20 66 69 72 73 74 0a 65 6e  ind the first.en
1f40: 74 72 79 20 6f 66 20 74 68 65 20 69 6e 64 65 78  try of the index
1f50: 20 77 68 65 72 65 20 66 72 75 69 74 3d 27 4f 72   where fruit='Or
1f60: 61 6e 67 65 27 2e 20 20 54 68 65 6e 20 69 74 20  ange'.  Then it 
1f70: 65 78 74 72 61 63 74 73 20 74 68 65 20 72 6f 77  extracts the row
1f80: 69 64 20 66 72 6f 6d 0a 74 68 65 20 69 6e 64 65  id from.the inde
1f90: 78 20 61 6e 64 20 75 73 65 73 20 74 68 61 74 20  x and uses that 
1fa0: 72 6f 77 69 64 20 74 6f 20 6c 6f 6f 6b 75 70 20  rowid to lookup 
1fb0: 74 68 65 20 6f 72 69 67 69 6e 61 6c 20 74 61 62  the original tab
1fc0: 6c 65 20 65 6e 74 72 79 20 76 69 61 0a 62 69 6e  le entry via.bin
1fd0: 61 72 79 20 73 65 61 72 63 68 20 61 6e 64 20 6f  ary search and o
1fe0: 75 74 70 75 74 20 74 68 65 20 70 72 69 63 65 20  utput the price 
1ff0: 66 72 6f 6d 20 74 68 65 20 6f 72 69 67 69 6e 61  from the origina
2000: 6c 20 74 61 62 6c 65 2e 20 20 42 75 74 20 69 6e  l table.  But in
2010: 73 74 65 61 64 0a 6f 66 20 71 75 69 74 74 69 6e  stead.of quittin
2020: 67 2c 20 74 68 65 20 64 61 74 61 62 61 73 65 20  g, the database 
2030: 65 6e 67 69 6e 65 20 74 68 65 6e 20 61 64 76 61  engine then adva
2040: 6e 63 65 73 20 74 6f 20 74 68 65 20 6e 65 78 74  nces to the next
2050: 20 72 6f 77 20 6f 66 20 69 6e 64 65 78 0a 74 6f   row of index.to
2060: 20 72 65 70 65 61 74 20 74 68 65 20 70 72 6f 63   repeat the proc
2070: 65 73 73 20 66 6f 72 20 6e 65 78 74 20 66 72 75  ess for next fru
2080: 69 74 3d 27 4f 72 61 6e 67 65 27 20 65 6e 74 72  it='Orange' entr
2090: 79 2e 20 20 41 64 76 61 6e 63 69 6e 67 20 74 6f  y.  Advancing to
20a0: 20 74 68 65 0a 6e 65 78 74 20 72 6f 77 20 6f 66   the.next row of
20b0: 20 61 6e 20 69 6e 64 65 78 20 28 6f 72 20 74 61   an index (or ta
20c0: 62 6c 65 29 20 69 73 20 6d 75 63 68 20 6c 65 73  ble) is much les
20d0: 73 20 63 6f 73 74 6c 79 20 74 68 61 6e 20 64 6f  s costly than do
20e0: 69 6e 67 20 61 20 62 69 6e 61 72 79 0a 73 65 61  ing a binary.sea
20f0: 72 63 68 20 73 69 6e 63 65 20 74 68 65 20 6e 65  rch since the ne
2100: 78 74 20 72 6f 77 20 69 73 20 6f 66 74 65 6e 20  xt row is often 
2110: 6c 6f 63 61 74 65 64 20 6f 6e 20 74 68 65 20 73  located on the s
2120: 61 6d 65 20 64 61 74 61 62 61 73 65 20 70 61 67  ame database pag
2130: 65 20 61 73 0a 74 68 65 20 63 75 72 72 65 6e 74  e as.the current
2140: 20 72 6f 77 2e 20 20 49 6e 20 66 61 63 74 2c 20   row.  In fact, 
2150: 74 68 65 20 63 6f 73 74 20 6f 66 20 61 64 76 61  the cost of adva
2160: 6e 63 69 6e 67 20 74 6f 20 74 68 65 20 6e 65 78  ncing to the nex
2170: 74 20 72 6f 77 20 69 73 20 73 6f 0a 63 68 65 61  t row is so.chea
2180: 70 20 69 6e 20 63 6f 6d 70 61 72 69 73 6f 6e 20  p in comparison 
2190: 74 6f 20 61 20 62 69 6e 61 72 79 20 73 65 61 72  to a binary sear
21a0: 63 68 20 74 68 61 74 20 77 65 20 75 73 75 61 6c  ch that we usual
21b0: 6c 79 20 69 67 6e 6f 72 65 20 69 74 2e 20 20 53  ly ignore it.  S
21c0: 6f 0a 6f 75 72 20 65 73 74 69 6d 61 74 65 20 66  o.our estimate f
21d0: 6f 72 20 74 68 65 20 74 6f 74 61 6c 20 63 6f 73  or the total cos
21e0: 74 20 6f 66 20 74 68 69 73 20 71 75 65 72 79 20  t of this query 
21f0: 69 73 20 33 20 62 69 6e 61 72 79 20 73 65 61 72  is 3 binary sear
2200: 63 68 65 73 2e 0a 49 66 20 74 68 65 20 6e 75 6d  ches..If the num
2210: 62 65 72 20 6f 66 20 72 6f 77 73 20 6f 66 20 6f  ber of rows of o
2220: 75 74 70 75 74 20 69 73 20 4b 20 61 6e 64 20 74  utput is K and t
2230: 68 65 20 6e 75 6d 62 65 72 20 6f 66 20 72 6f 77  he number of row
2240: 73 20 69 6e 20 74 68 65 20 74 61 62 6c 65 0a 69  s in the table.i
2250: 73 20 4e 2c 20 74 68 65 6e 20 69 6e 20 67 65 6e  s N, then in gen
2260: 65 72 61 6c 20 74 68 65 20 63 6f 73 74 20 6f 66  eral the cost of
2270: 20 64 6f 69 6e 67 20 74 68 65 20 71 75 65 72 79   doing the query
2280: 20 69 73 20 70 72 6f 70 6f 72 74 69 6f 6e 61 6c   is proportional
2290: 0a 74 6f 20 28 4b 2b 31 29 2a 6c 6f 67 4e 2e 0a  .to (K+1)*logN..
22a0: 3c 2f 70 3e 0a 0a 3c 68 32 3e 20 4d 75 6c 74 69  </p>..<h2> Multi
22b0: 70 6c 65 20 41 4e 44 2d 43 6f 6e 6e 65 63 74 65  ple AND-Connecte
22c0: 64 20 57 48 45 52 45 2d 43 6c 61 75 73 65 20 54  d WHERE-Clause T
22d0: 65 72 6d 73 3c 2f 68 32 3e 0a 0a 3c 70 3e 0a 4e  erms</h2>..<p>.N
22e0: 65 78 74 2c 20 73 75 70 70 6f 73 65 20 74 68 61  ext, suppose tha
22f0: 74 20 79 6f 75 20 77 61 6e 74 20 74 6f 20 6c 6f  t you want to lo
2300: 6f 6b 20 75 70 20 74 68 65 20 70 72 69 63 65 20  ok up the price 
2310: 6f 66 20 6e 6f 74 20 6a 75 73 74 20 61 6e 79 20  of not just any 
2320: 6f 72 61 6e 67 65 2c 0a 62 75 74 20 73 70 65 63  orange,.but spec
2330: 69 66 69 63 61 6c 6c 79 20 43 61 6c 69 66 6f 72  ifically Califor
2340: 6e 69 61 2d 67 72 6f 77 6e 20 6f 72 61 6e 67 65  nia-grown orange
2350: 73 2e 20 20 54 68 65 20 61 70 70 72 6f 70 72 69  s.  The appropri
2360: 61 74 65 20 71 75 65 72 79 20 77 6f 75 6c 64 0a  ate query would.
2370: 62 65 20 61 73 20 66 6f 6c 6c 6f 77 73 3a 0a 3c  be as follows:.<
2380: 2f 70 3e 0a 0a 3c 74 63 6c 3e 0a 63 6f 64 65 20  /p>..<tcl>.code 
2390: 7b 53 45 4c 45 43 54 20 70 72 69 63 65 20 46 52  {SELECT price FR
23a0: 4f 4d 20 66 72 75 69 74 73 66 6f 72 73 61 6c 65  OM fruitsforsale
23b0: 20 57 48 45 52 45 20 66 72 75 69 74 3d 27 4f 72   WHERE fruit='Or
23c0: 61 6e 67 65 27 20 41 4e 44 20 73 74 61 74 65 3d  ange' AND state=
23d0: 27 43 41 27 7d 0a 66 69 67 75 72 65 20 37 20 23  'CA'}.figure 7 #
23e0: 66 69 67 37 20 69 64 78 31 6c 75 33 2e 67 69 66  fig7 idx1lu3.gif
23f0: 20 7b 49 6e 64 65 78 65 64 20 4c 6f 6f 6b 75 70   {Indexed Lookup
2400: 20 4f 66 20 43 61 6c 69 66 6f 72 6e 69 61 20 4f   Of California O
2410: 72 61 6e 67 65 73 7d 0a 3c 2f 74 63 6c 3e 0a 0a  ranges}.</tcl>..
2420: 3c 70 3e 0a 4f 6e 65 20 61 70 70 72 6f 61 63 68  <p>.One approach
2430: 20 74 6f 20 74 68 69 73 20 71 75 65 72 79 20 69   to this query i
2440: 73 20 74 6f 20 75 73 65 20 74 68 65 20 66 72 75  s to use the fru
2450: 69 74 3d 27 4f 72 61 6e 67 65 27 20 74 65 72 6d  it='Orange' term
2460: 20 6f 66 20 74 68 65 20 57 48 45 52 45 0a 63 6c   of the WHERE.cl
2470: 61 75 73 65 20 74 6f 20 66 69 6e 64 20 61 6c 6c  ause to find all
2480: 20 72 6f 77 73 20 64 65 61 6c 69 6e 67 20 77 69   rows dealing wi
2490: 74 68 20 6f 72 61 6e 67 65 73 2c 20 74 68 65 6e  th oranges, then
24a0: 20 66 69 6c 74 65 72 20 74 68 6f 73 65 20 72 6f   filter those ro
24b0: 77 73 0a 62 79 20 72 65 6a 65 63 74 69 6e 67 20  ws.by rejecting 
24c0: 61 6e 79 20 74 68 61 74 20 61 72 65 20 66 72 6f  any that are fro
24d0: 6d 20 73 74 61 74 65 73 20 6f 74 68 65 72 20 74  m states other t
24e0: 68 61 6e 20 43 61 6c 69 66 6f 72 6e 69 61 2e 20  han California. 
24f0: 20 54 68 69 73 0a 70 72 6f 63 65 73 73 20 69 73   This.process is
2500: 20 73 68 6f 77 6e 20 62 79 20 3c 61 20 68 72 65   shown by <a hre
2510: 66 3d 22 23 66 69 67 37 22 3e 66 69 67 75 72 65  f="#fig7">figure
2520: 20 37 3c 2f 61 3e 20 61 62 6f 76 65 2e 20 20 54   7</a> above.  T
2530: 68 69 73 20 69 73 20 61 20 70 65 72 66 65 63 74  his is a perfect
2540: 6c 79 0a 72 65 61 73 6f 6e 61 62 6c 65 20 61 70  ly.reasonable ap
2550: 70 72 6f 61 63 68 20 69 6e 20 6d 6f 73 74 20 63  proach in most c
2560: 61 73 65 73 2e 20 20 59 65 73 2c 20 74 68 65 20  ases.  Yes, the 
2570: 64 61 74 61 62 61 73 65 20 65 6e 67 69 6e 65 20  database engine 
2580: 64 69 64 20 68 61 76 65 0a 74 6f 20 64 6f 20 61  did have.to do a
2590: 6e 20 65 78 74 72 61 20 62 69 6e 61 72 79 20 73  n extra binary s
25a0: 65 61 72 63 68 20 66 6f 72 20 74 68 65 20 46 6c  earch for the Fl
25b0: 6f 72 69 64 61 20 6f 72 61 6e 67 65 20 72 6f 77  orida orange row
25c0: 20 74 68 61 74 20 77 61 73 0a 6c 61 74 65 72 20   that was.later 
25d0: 72 65 6a 65 63 74 65 64 2c 20 73 6f 20 69 74 20  rejected, so it 
25e0: 77 61 73 20 6e 6f 74 20 61 73 20 65 66 66 69 63  was not as effic
25f0: 69 65 6e 74 20 61 73 20 77 65 20 6d 69 67 68 74  ient as we might
2600: 20 68 6f 70 65 2c 20 74 68 6f 75 67 68 0a 66 6f   hope, though.fo
2610: 72 20 6d 61 6e 79 20 61 70 70 6c 69 63 61 74 69  r many applicati
2620: 6f 6e 73 20 69 74 20 69 73 20 65 66 66 69 63 69  ons it is effici
2630: 65 6e 74 20 65 6e 6f 75 67 68 2e 20 20 0a 3c 2f  ent enough.  .</
2640: 70 3e 0a 0a 3c 70 3e 0a 53 75 70 70 6f 73 65 20  p>..<p>.Suppose 
2650: 74 68 61 74 20 69 6e 20 61 64 64 69 74 69 6f 6e  that in addition
2660: 20 74 6f 20 74 68 65 20 69 6e 64 65 78 20 6f 6e   to the index on
2670: 20 22 66 72 75 69 74 22 20 74 68 65 72 65 20 77   "fruit" there w
2680: 61 73 20 61 6c 73 6f 0a 61 6e 20 69 6e 64 65 78  as also.an index
2690: 20 6f 6e 20 22 73 74 61 74 65 22 2e 0a 3c 2f 70   on "state"..</p
26a0: 3e 0a 0a 3c 74 63 6c 3e 0a 63 6f 64 65 20 7b 43  >..<tcl>.code {C
26b0: 52 45 41 54 45 20 49 4e 44 45 58 20 49 64 78 32  REATE INDEX Idx2
26c0: 20 4f 4e 20 66 72 75 69 74 73 66 6f 72 73 61 6c   ON fruitsforsal
26d0: 65 28 73 74 61 74 65 29 3b 7d 0a 66 69 67 75 72  e(state);}.figur
26e0: 65 20 38 20 23 66 69 67 38 20 69 64 78 32 2e 67  e 8 #fig8 idx2.g
26f0: 69 66 20 7b 49 6e 64 65 78 20 4f 6e 20 54 68 65  if {Index On The
2700: 20 53 74 61 74 65 20 43 6f 6c 75 6d 6e 7d 0a 3c   State Column}.<
2710: 2f 74 63 6c 3e 0a 0a 3c 70 3e 0a 54 68 65 20 22  /tcl>..<p>.The "
2720: 73 74 61 74 65 22 20 69 6e 64 65 78 20 77 6f 72  state" index wor
2730: 6b 73 20 6a 75 73 74 20 6c 69 6b 65 20 74 68 65  ks just like the
2740: 20 22 66 72 75 69 74 22 20 69 6e 64 65 78 20 69   "fruit" index i
2750: 6e 20 74 68 61 74 20 69 74 20 69 73 20 61 0a 6e  n that it is a.n
2760: 65 77 20 74 61 62 6c 65 20 77 69 74 68 20 61 6e  ew table with an
2770: 20 65 78 74 72 61 20 63 6f 6c 75 6d 6e 20 69 6e   extra column in
2780: 20 66 72 6f 6e 74 20 6f 66 20 74 68 65 20 72 6f   front of the ro
2790: 77 69 64 20 61 6e 64 20 73 6f 72 74 65 64 20 62  wid and sorted b
27a0: 79 0a 74 68 61 74 20 65 78 74 72 61 20 63 6f 6c  y.that extra col
27b0: 75 6d 6e 20 61 73 20 74 68 65 20 70 72 69 6d 61  umn as the prima
27c0: 72 79 20 6b 65 79 2e 20 20 54 68 65 20 6f 6e 6c  ry key.  The onl
27d0: 79 20 64 69 66 66 65 72 65 6e 63 65 20 69 73 20  y difference is 
27e0: 74 68 61 74 0a 69 6e 20 49 64 78 32 2c 20 74 68  that.in Idx2, th
27f0: 65 20 66 69 72 73 74 20 63 6f 6c 75 6d 6e 20 69  e first column i
2800: 73 20 22 73 74 61 74 65 22 20 69 6e 73 74 65 61  s "state" instea
2810: 64 20 6f 66 20 22 66 72 75 69 74 22 20 61 73 20  d of "fruit" as 
2820: 69 74 20 69 73 20 77 69 74 68 0a 49 64 78 31 2e  it is with.Idx1.
2830: 20 20 49 6e 20 6f 75 72 20 65 78 61 6d 70 6c 65    In our example
2840: 20 64 61 74 61 20 73 65 74 2c 20 74 68 65 72 65   data set, there
2850: 20 69 73 20 6d 6f 72 65 20 72 65 64 75 6e 64 61   is more redunda
2860: 6e 63 79 20 69 6e 20 74 68 65 20 22 73 74 61 74  ncy in the "stat
2870: 65 22 0a 63 6f 6c 75 6d 6e 20 61 6e 64 20 73 6f  e".column and so
2880: 20 74 68 65 79 20 61 72 65 20 6d 6f 72 65 20 64   they are more d
2890: 75 70 6c 69 63 61 74 65 20 65 6e 74 72 69 65 73  uplicate entries
28a0: 2e 20 20 54 68 65 20 74 69 65 73 20 61 72 65 20  .  The ties are 
28b0: 73 74 69 6c 6c 0a 72 65 73 6f 6c 76 65 64 20 75  still.resolved u
28c0: 73 69 6e 67 20 74 68 65 20 72 6f 77 69 64 2e 0a  sing the rowid..
28d0: 3c 2f 70 3e 0a 0a 3c 70 3e 0a 55 73 69 6e 67 20  </p>..<p>.Using 
28e0: 74 68 65 20 6e 65 77 20 49 64 78 32 20 69 6e 64  the new Idx2 ind
28f0: 65 78 20 6f 6e 20 22 73 74 61 74 65 22 2c 20 53  ex on "state", S
2900: 51 4c 69 74 65 20 68 61 73 20 61 6e 6f 74 68 65  QLite has anothe
2910: 72 20 6f 70 74 69 6f 6e 20 66 6f 72 0a 6c 6f 6f  r option for.loo
2920: 6b 75 70 20 75 70 20 74 68 65 20 70 72 69 63 65  kup up the price
2930: 20 6f 66 20 43 61 6c 69 66 6f 72 6e 69 61 20 6f   of California o
2940: 72 61 6e 67 65 73 3a 20 20 69 74 20 63 61 6e 20  ranges:  it can 
2950: 6c 6f 6f 6b 20 75 70 20 65 76 65 72 79 20 72 6f  look up every ro
2960: 77 0a 74 68 61 74 20 63 6f 6e 74 61 69 6e 73 20  w.that contains 
2970: 66 72 75 69 74 20 66 72 6f 6d 20 43 61 6c 69 66  fruit from Calif
2980: 6f 72 6e 69 61 20 61 6e 64 20 66 69 6c 74 65 72  ornia and filter
2990: 20 6f 75 74 20 74 68 6f 73 65 20 72 6f 77 73 20   out those rows 
29a0: 74 68 61 74 0a 61 72 65 20 6e 6f 74 20 6f 72 61  that.are not ora
29b0: 6e 67 65 73 2e 0a 3c 2f 70 3e 0a 0a 3c 74 63 6c  nges..</p>..<tcl
29c0: 3e 66 69 67 75 72 65 20 39 20 23 66 69 67 39 20  >figure 9 #fig9 
29d0: 69 64 78 32 6c 75 31 2e 67 69 66 20 7b 49 6e 64  idx2lu1.gif {Ind
29e0: 65 78 65 64 20 4c 6f 6f 6b 75 70 20 4f 66 20 43  exed Lookup Of C
29f0: 61 6c 69 66 6f 72 6e 69 61 20 4f 72 61 6e 67 65  alifornia Orange
2a00: 73 7d 3c 2f 74 63 6c 3e 0a 0a 3c 70 3e 0a 55 73  s}</tcl>..<p>.Us
2a10: 69 6e 67 20 49 64 78 32 20 69 6e 73 74 65 61 64  ing Idx2 instead
2a20: 20 6f 66 20 49 64 78 31 20 63 61 75 73 65 73 20   of Idx1 causes 
2a30: 53 51 4c 69 74 65 20 74 6f 20 65 78 61 6d 69 6e  SQLite to examin
2a40: 65 20 61 20 64 69 66 66 65 72 65 6e 74 20 73 65  e a different se
2a50: 74 20 6f 66 0a 72 6f 77 73 2c 20 62 75 74 20 69  t of.rows, but i
2a60: 74 20 67 65 74 73 20 74 68 65 20 73 61 6d 65 20  t gets the same 
2a70: 61 6e 73 77 65 72 20 69 6e 20 74 68 65 20 65 6e  answer in the en
2a80: 64 20 28 77 68 69 63 68 20 69 73 20 76 65 72 79  d (which is very
2a90: 20 69 6d 70 6f 72 74 61 6e 74 20 2d 0a 72 65 6d   important -.rem
2aa0: 65 6d 62 65 72 20 74 68 61 74 20 69 6e 64 69 63  ember that indic
2ab0: 65 73 20 73 68 6f 75 6c 64 20 6e 65 76 65 72 20  es should never 
2ac0: 63 68 61 6e 67 65 20 74 68 65 20 61 6e 73 77 65  change the answe
2ad0: 72 2c 20 6f 6e 6c 79 20 68 65 6c 70 20 53 51 4c  r, only help SQL
2ae0: 69 74 65 20 74 6f 0a 67 65 74 20 74 6f 20 74 68  ite to.get to th
2af0: 65 20 61 6e 73 77 65 72 20 6d 6f 72 65 20 71 75  e answer more qu
2b00: 69 63 6b 6c 79 29 20 61 6e 64 20 69 74 20 64 6f  ickly) and it do
2b10: 65 73 20 74 68 65 20 73 61 6d 65 20 61 6d 6f 75  es the same amou
2b20: 6e 74 20 6f 66 20 77 6f 72 6b 2e 0a 53 6f 20 74  nt of work..So t
2b30: 68 65 20 49 64 78 32 20 69 6e 64 65 78 20 64 69  he Idx2 index di
2b40: 64 20 6e 6f 74 20 68 65 6c 70 20 70 65 72 66 6f  d not help perfo
2b50: 72 6d 61 6e 63 65 20 69 6e 20 74 68 69 73 20 63  rmance in this c
2b60: 61 73 65 2e 0a 3c 2f 70 3e 0a 0a 3c 70 3e 0a 54  ase..</p>..<p>.T
2b70: 68 65 20 6c 61 73 74 20 74 77 6f 20 71 75 65 72  he last two quer
2b80: 69 65 73 20 74 61 6b 65 20 74 68 65 20 73 61 6d  ies take the sam
2b90: 65 20 61 6d 6f 75 6e 74 20 6f 66 20 74 69 6d 65  e amount of time
2ba0: 2c 20 69 6e 20 6f 75 72 20 65 78 61 6d 70 6c 65  , in our example
2bb0: 2e 0a 53 6f 20 77 68 69 63 68 20 69 6e 64 65 78  ..So which index
2bc0: 2c 20 49 64 78 31 20 6f 72 20 49 64 78 32 2c 20  , Idx1 or Idx2, 
2bd0: 77 69 6c 6c 20 53 51 4c 69 74 65 20 63 68 6f 6f  will SQLite choo
2be0: 73 65 3f 20 20 49 66 20 74 68 65 0a 5b 41 4e 41  se?  If the.[ANA
2bf0: 4c 59 5a 45 5d 20 63 6f 6d 6d 61 6e 64 20 68 61  LYZE] command ha
2c00: 73 20 62 65 65 6e 20 72 75 6e 20 6f 6e 20 74 68  s been run on th
2c10: 65 20 64 61 74 61 62 61 73 65 2c 20 73 6f 20 74  e database, so t
2c20: 68 61 74 20 53 51 4c 69 74 65 20 68 61 73 0a 68  hat SQLite has.h
2c30: 61 64 20 61 6e 20 6f 70 70 6f 72 74 75 6e 69 74  ad an opportunit
2c40: 79 20 74 6f 20 67 61 74 68 65 72 20 73 74 61 74  y to gather stat
2c50: 69 73 74 69 63 73 20 61 62 6f 75 74 20 74 68 65  istics about the
2c60: 20 61 76 61 69 6c 61 62 6c 65 20 69 6e 64 69 63   available indic
2c70: 65 73 2c 0a 74 68 65 6e 20 53 51 4c 69 74 65 20  es,.then SQLite 
2c80: 77 69 6c 6c 20 6b 6e 6f 77 20 74 68 61 74 20 74  will know that t
2c90: 68 65 20 49 64 78 31 20 69 6e 64 65 78 20 75 73  he Idx1 index us
2ca0: 75 61 6c 6c 79 20 6e 61 72 72 6f 77 73 20 74 68  ually narrows th
2cb0: 65 20 73 65 61 72 63 68 0a 64 6f 77 6e 20 74 6f  e search.down to
2cc0: 20 61 20 73 69 6e 67 6c 65 20 69 74 65 6d 20 28   a single item (
2cd0: 6f 75 72 20 65 78 61 6d 70 6c 65 20 6f 66 20 66  our example of f
2ce0: 72 75 69 74 3d 27 4f 72 61 6e 67 65 27 20 69 73  ruit='Orange' is
2cf0: 20 74 68 65 20 65 78 63 65 70 74 69 6f 6e 0a 74   the exception.t
2d00: 6f 20 74 68 69 73 20 72 75 6c 65 29 20 77 68 65  o this rule) whe
2d10: 72 65 61 73 20 74 68 65 20 49 64 78 32 20 69 6e  reas the Idx2 in
2d20: 64 65 78 20 77 69 6c 6c 20 6e 6f 72 6d 61 6c 6c  dex will normall
2d30: 79 20 6f 6e 6c 79 20 6e 61 72 72 6f 77 20 74 68  y only narrow th
2d40: 65 20 0a 73 65 61 72 63 68 20 64 6f 77 6e 20 74  e .search down t
2d50: 6f 20 74 77 6f 20 72 6f 77 73 2e 20 20 53 6f 2c  o two rows.  So,
2d60: 20 69 66 20 61 6c 6c 20 65 6c 73 65 20 69 73 20   if all else is 
2d70: 65 71 75 61 6c 2c 20 53 51 4c 69 74 65 20 77 69  equal, SQLite wi
2d80: 6c 6c 0a 63 68 6f 6f 73 65 20 49 64 78 31 20 77  ll.choose Idx1 w
2d90: 69 74 68 20 74 68 65 20 68 6f 70 65 20 6f 66 20  ith the hope of 
2da0: 6e 61 72 72 6f 77 69 6e 67 20 74 68 65 20 73 65  narrowing the se
2db0: 61 72 63 68 20 74 6f 20 61 73 20 73 6d 61 6c 6c  arch to as small
2dc0: 0a 61 20 6e 75 6d 62 65 72 20 6f 66 20 72 6f 77  .a number of row
2dd0: 73 20 61 73 20 70 6f 73 73 69 62 6c 65 2e 20 20  s as possible.  
2de0: 54 68 69 73 20 63 68 6f 69 63 65 20 69 73 20 6f  This choice is o
2df0: 6e 6c 79 20 70 6f 73 73 69 62 6c 65 20 62 65 63  nly possible bec
2e00: 61 75 73 65 0a 6f 66 20 74 68 65 20 73 74 61 74  ause.of the stat
2e10: 69 73 74 69 63 73 20 70 72 6f 76 69 64 65 64 20  istics provided 
2e20: 62 79 20 5b 41 4e 41 4c 59 5a 45 5d 2e 20 20 49  by [ANALYZE].  I
2e30: 66 20 5b 41 4e 41 4c 59 5a 45 5d 20 68 61 73 20  f [ANALYZE] has 
2e40: 6e 6f 74 20 62 65 65 6e 0a 72 75 6e 20 74 68 65  not been.run the
2e50: 6e 20 74 68 65 20 63 68 6f 69 63 65 20 6f 66 20  n the choice of 
2e60: 77 68 69 63 68 20 69 6e 64 65 78 20 74 6f 20 75  which index to u
2e70: 73 65 20 69 73 20 61 72 62 69 74 72 61 72 79 2e  se is arbitrary.
2e80: 0a 3c 2f 70 3e 0a 0a 3c 68 32 3e 20 4d 75 6c 74  .</p>..<h2> Mult
2e90: 69 2d 43 6f 6c 75 6d 6e 20 49 6e 64 69 63 65 73  i-Column Indices
2ea0: 3c 2f 68 32 3e 0a 0a 3c 70 3e 0a 54 6f 20 67 65  </h2>..<p>.To ge
2eb0: 74 20 74 68 65 20 6d 61 78 69 6d 75 6d 20 70 65  t the maximum pe
2ec0: 72 66 6f 72 6d 61 6e 63 65 20 6f 75 74 20 6f 66  rformance out of
2ed0: 20 61 20 71 75 65 72 79 20 77 69 74 68 20 6d 75   a query with mu
2ee0: 6c 74 69 70 6c 65 20 41 4e 44 2d 63 6f 6e 6e 65  ltiple AND-conne
2ef0: 63 74 65 64 0a 74 65 72 6d 73 20 69 6e 20 74 68  cted.terms in th
2f00: 65 20 57 48 45 52 45 20 63 6c 61 75 73 65 2c 20  e WHERE clause, 
2f10: 79 6f 75 20 72 65 61 6c 6c 79 20 77 61 6e 74 20  you really want 
2f20: 61 20 6d 75 6c 74 69 2d 63 6f 6c 75 6d 6e 20 69  a multi-column i
2f30: 6e 64 65 78 20 77 69 74 68 0a 63 6f 6c 75 6d 6e  ndex with.column
2f40: 73 20 66 6f 72 20 65 61 63 68 20 6f 66 20 74 68  s for each of th
2f50: 65 20 41 4e 44 20 74 65 72 6d 73 2e 20 20 49 6e  e AND terms.  In
2f60: 20 74 68 69 73 20 63 61 73 65 20 77 65 20 63 72   this case we cr
2f70: 65 61 74 65 20 61 20 6e 65 77 20 69 6e 64 65 78  eate a new index
2f80: 0a 6f 6e 20 74 68 65 20 22 66 72 75 69 74 22 20  .on the "fruit" 
2f90: 61 6e 64 20 22 73 74 61 74 65 22 20 63 6f 6c 75  and "state" colu
2fa0: 6d 6e 73 20 6f 66 20 46 72 75 69 74 73 46 6f 72  mns of FruitsFor
2fb0: 53 61 6c 65 3a 0a 3c 2f 70 3e 0a 0a 3c 74 63 6c  Sale:.</p>..<tcl
2fc0: 3e 0a 63 6f 64 65 20 7b 43 52 45 41 54 45 20 49  >.code {CREATE I
2fd0: 4e 44 45 58 20 49 64 78 33 20 4f 4e 20 46 72 75  NDEX Idx3 ON Fru
2fe0: 69 74 73 46 6f 72 53 61 6c 65 28 66 72 75 69 74  itsForSale(fruit
2ff0: 2c 20 73 74 61 74 65 29 3b 7d 0a 66 69 67 75 72  , state);}.figur
3000: 65 20 31 20 23 66 69 67 31 30 20 69 64 78 33 2e  e 1 #fig10 idx3.
3010: 67 69 66 20 7b 41 20 54 77 6f 2d 43 6f 6c 75 6d  gif {A Two-Colum
3020: 6e 20 49 6e 64 65 78 7d 0a 3c 2f 74 63 6c 3e 0a  n Index}.</tcl>.
3030: 0a 3c 70 3e 0a 41 20 6d 75 6c 74 69 2d 63 6f 6c  .<p>.A multi-col
3040: 75 6d 6e 20 69 6e 64 65 78 20 66 6f 6c 6c 6f 77  umn index follow
3050: 73 20 74 68 65 20 73 61 6d 65 20 70 61 74 74 65  s the same patte
3060: 72 6e 20 61 73 20 61 20 73 69 6e 67 6c 65 2d 63  rn as a single-c
3070: 6f 6c 75 6d 6e 20 69 6e 64 65 78 3b 0a 74 68 65  olumn index;.the
3080: 20 69 6e 64 65 78 65 64 20 63 6f 6c 75 6d 6e 73   indexed columns
3090: 20 61 72 65 20 61 64 64 65 64 20 69 6e 20 66 72   are added in fr
30a0: 6f 6e 74 20 6f 66 20 74 68 65 20 72 6f 77 69 64  ont of the rowid
30b0: 2e 20 20 54 68 65 20 6f 6e 6c 79 20 64 69 66 66  .  The only diff
30c0: 65 72 65 6e 63 65 0a 69 73 20 74 68 61 74 20 6e  erence.is that n
30d0: 6f 77 20 6d 75 6c 74 69 70 6c 65 20 63 6f 6c 75  ow multiple colu
30e0: 6d 6e 73 20 61 72 65 20 61 64 64 65 64 2e 20 20  mns are added.  
30f0: 54 68 65 20 6c 65 66 74 2d 6d 6f 73 74 20 63 6f  The left-most co
3100: 6c 75 6d 6e 20 69 73 20 74 68 65 0a 70 72 69 6d  lumn is the.prim
3110: 61 72 79 20 6b 65 79 20 75 73 65 64 20 66 6f 72  ary key used for
3120: 20 6f 72 64 65 72 69 6e 67 20 74 68 65 20 72 6f   ordering the ro
3130: 77 73 20 69 6e 20 74 68 65 20 69 6e 64 65 78 2e  ws in the index.
3140: 20 20 54 68 65 20 73 65 63 6f 6e 64 20 63 6f 6c    The second col
3150: 75 6d 6e 20 69 73 0a 75 73 65 64 20 74 6f 20 62  umn is.used to b
3160: 72 65 61 6b 20 74 69 65 73 20 69 6e 20 74 68 65  reak ties in the
3170: 20 6c 65 66 74 2d 6d 6f 73 74 20 63 6f 6c 75 6d   left-most colum
3180: 6e 2e 20 20 49 66 20 74 68 65 72 65 20 77 65 72  n.  If there wer
3190: 65 20 61 20 74 68 69 72 64 20 63 6f 6c 75 6d 6e  e a third column
31a0: 2c 0a 69 74 20 77 6f 75 6c 64 20 62 65 20 75 73  ,.it would be us
31b0: 65 64 20 74 6f 20 62 72 65 61 6b 20 74 69 65 73  ed to break ties
31c0: 20 66 6f 72 20 74 68 65 20 66 69 72 73 74 20 74   for the first t
31d0: 77 6f 20 63 6f 6c 75 6d 6e 73 2e 20 20 41 6e 64  wo columns.  And
31e0: 20 73 6f 20 66 6f 72 74 68 20 66 6f 72 0a 61 6c   so forth for.al
31f0: 6c 20 63 6f 6c 75 6d 6e 73 20 69 6e 20 74 68 65  l columns in the
3200: 20 69 6e 64 65 78 2e 20 20 42 65 63 61 75 73 65   index.  Because
3210: 20 72 6f 77 69 64 20 69 73 20 67 75 61 72 61 6e   rowid is guaran
3220: 74 65 65 64 0a 74 6f 20 62 65 20 75 6e 69 71 75  teed.to be uniqu
3230: 65 2c 20 65 76 65 72 79 20 72 6f 77 20 6f 66 20  e, every row of 
3240: 74 68 65 20 69 6e 64 65 78 20 77 69 6c 6c 20 62  the index will b
3250: 65 20 75 6e 69 71 75 65 20 65 76 65 6e 20 69 66  e unique even if
3260: 20 61 6c 6c 20 6f 66 20 74 68 65 0a 63 6f 6e 74   all of the.cont
3270: 65 6e 74 20 63 6f 6c 75 6d 6e 73 20 66 6f 72 20  ent columns for 
3280: 74 77 6f 20 72 6f 77 73 20 61 72 65 20 74 68 65  two rows are the
3290: 20 73 61 6d 65 2e 20 20 54 68 61 74 20 63 61 73   same.  That cas
32a0: 65 20 64 6f 65 73 20 6e 6f 74 20 68 61 70 70 65  e does not happe
32b0: 6e 0a 69 6e 20 6f 75 72 20 73 61 6d 70 6c 65 20  n.in our sample 
32c0: 64 61 74 61 2c 20 62 75 74 20 74 68 65 72 65 20  data, but there 
32d0: 69 73 20 6f 6e 65 20 63 61 73 65 20 28 66 72 75  is one case (fru
32e0: 69 74 3d 27 4f 72 61 6e 67 65 27 29 20 77 68 65  it='Orange') whe
32f0: 72 65 20 74 68 65 72 65 0a 69 73 20 61 20 74 69  re there.is a ti
3300: 65 20 6f 6e 20 74 68 65 20 66 69 72 73 74 20 63  e on the first c
3310: 6f 6c 75 6d 6e 20 77 68 69 63 68 20 6d 75 73 74  olumn which must
3320: 20 62 65 20 62 72 6f 6b 65 6e 20 62 79 20 74 68   be broken by th
3330: 65 20 73 65 63 6f 6e 64 20 63 6f 6c 75 6d 6e 2e  e second column.
3340: 0a 3c 2f 70 3e 0a 0a 3c 70 3e 0a 47 69 76 65 6e  .</p>..<p>.Given
3350: 20 74 68 65 20 6e 65 77 20 6d 75 6c 74 69 2d 63   the new multi-c
3360: 6f 6c 75 6d 6e 20 49 64 78 33 20 69 6e 64 65 78  olumn Idx3 index
3370: 2c 20 69 74 20 69 73 20 6e 6f 77 20 70 6f 73 73  , it is now poss
3380: 69 62 6c 65 20 66 6f 72 20 53 51 4c 69 74 65 0a  ible for SQLite.
3390: 74 6f 20 66 69 6e 64 20 74 68 65 20 70 72 69 63  to find the pric
33a0: 65 20 6f 66 20 43 61 6c 69 66 6f 72 6e 69 61 20  e of California 
33b0: 6f 72 61 6e 67 65 73 20 75 73 69 6e 67 20 6f 6e  oranges using on
33c0: 6c 79 20 32 20 62 69 6e 61 72 79 20 73 65 61 72  ly 2 binary sear
33d0: 63 68 65 73 3a 0a 3c 2f 70 3e 0a 0a 3c 74 63 6c  ches:.</p>..<tcl
33e0: 3e 0a 63 6f 64 65 20 7b 53 45 4c 45 43 54 20 70  >.code {SELECT p
33f0: 72 69 63 65 20 46 52 4f 4d 20 66 72 75 69 74 73  rice FROM fruits
3400: 66 6f 72 73 61 6c 65 20 57 48 45 52 45 20 66 72  forsale WHERE fr
3410: 75 69 74 3d 27 4f 72 61 6e 67 65 27 20 41 4e 44  uit='Orange' AND
3420: 20 73 74 61 74 65 3d 27 43 41 27 7d 0a 66 69 67   state='CA'}.fig
3430: 75 72 65 20 31 31 20 23 66 69 67 31 31 20 69 64  ure 11 #fig11 id
3440: 78 33 6c 75 31 2e 67 69 66 20 7b 4c 6f 6f 6b 75  x3lu1.gif {Looku
3450: 70 20 55 73 69 6e 67 20 41 20 54 77 6f 2d 43 6f  p Using A Two-Co
3460: 6c 75 6d 6e 20 49 6e 64 65 78 7d 0a 3c 2f 74 63  lumn Index}.</tc
3470: 6c 3e 0a 0a 3c 70 3e 0a 57 69 74 68 20 74 68 65  l>..<p>.With the
3480: 20 49 64 78 33 20 69 6e 64 65 78 20 6f 6e 20 62   Idx3 index on b
3490: 6f 74 68 20 63 6f 6c 75 6d 6e 73 20 74 68 61 74  oth columns that
34a0: 20 61 72 65 20 63 6f 6e 73 74 72 61 69 6e 65 64   are constrained
34b0: 20 62 79 20 74 68 65 20 57 48 45 52 45 20 63 6c   by the WHERE cl
34c0: 61 75 73 65 2c 0a 53 51 4c 69 74 65 20 63 61 6e  ause,.SQLite can
34d0: 20 64 6f 20 61 20 73 69 6e 67 6c 65 20 62 69 6e   do a single bin
34e0: 61 72 79 20 73 65 61 72 63 68 20 61 67 61 69 6e  ary search again
34f0: 73 74 20 49 64 78 33 20 74 6f 20 66 69 6e 64 20  st Idx3 to find 
3500: 74 68 65 20 6f 6e 65 20 72 6f 77 69 64 0a 66 6f  the one rowid.fo
3510: 72 20 43 61 6c 69 66 6f 72 6e 69 61 20 6f 72 61  r California ora
3520: 6e 67 65 73 2c 20 74 68 65 6e 20 64 6f 20 61 20  nges, then do a 
3530: 73 69 6e 67 6c 65 20 62 69 6e 61 72 79 20 73 65  single binary se
3540: 61 72 63 68 20 74 6f 20 66 69 6e 64 20 74 68 65  arch to find the
3550: 20 70 72 69 63 65 0a 66 6f 72 20 74 68 61 74 20   price.for that 
3560: 69 74 65 6d 20 69 6e 20 74 68 65 20 6f 72 69 67  item in the orig
3570: 69 6e 61 6c 20 74 61 62 6c 65 2e 20 20 54 68 65  inal table.  The
3580: 72 65 20 61 72 65 20 6e 6f 20 64 65 61 64 2d 65  re are no dead-e
3590: 6e 64 73 20 61 6e 64 20 6e 6f 0a 77 61 73 74 65  nds and no.waste
35a0: 64 20 62 69 6e 61 72 79 20 73 65 61 72 63 68 65  d binary searche
35b0: 73 2e 20 20 54 68 69 73 20 69 73 20 61 20 6d 6f  s.  This is a mo
35c0: 72 65 20 65 66 66 69 63 69 65 6e 74 20 71 75 65  re efficient que
35d0: 72 79 2e 0a 3c 2f 70 3e 0a 0a 3c 70 3e 0a 4e 6f  ry..</p>..<p>.No
35e0: 74 65 20 74 68 61 74 20 49 64 78 33 20 63 6f 6e  te that Idx3 con
35f0: 74 61 69 6e 73 20 61 6c 6c 20 74 68 65 20 73 61  tains all the sa
3600: 6d 65 20 69 6e 66 6f 72 6d 61 74 69 6f 6e 20 61  me information a
3610: 73 20 74 68 65 20 6f 72 69 67 69 6e 61 6c 20 0a  s the original .
3620: 3c 61 20 68 72 65 66 3d 22 23 66 69 67 33 22 3e  <a href="#fig3">
3630: 49 64 78 31 3c 2f 61 3e 2e 20 20 41 6e 64 20 73  Idx1</a>.  And s
3640: 6f 20 69 66 20 77 65 20 68 61 76 65 20 49 64 78  o if we have Idx
3650: 33 2c 20 77 65 20 64 6f 20 6e 6f 74 20 72 65 61  3, we do not rea
3660: 6c 6c 79 20 6e 65 65 64 20 49 64 78 31 0a 61 6e  lly need Idx1.an
3670: 79 20 6d 6f 72 65 2e 20 20 54 68 65 20 22 70 72  y more.  The "pr
3680: 69 63 65 20 6f 66 20 70 65 61 63 68 65 73 22 20  ice of peaches" 
3690: 71 75 65 72 79 20 63 61 6e 20 62 65 20 73 61 74  query can be sat
36a0: 69 73 66 69 65 64 20 75 73 69 6e 67 20 49 64 78  isfied using Idx
36b0: 33 0a 62 79 20 73 69 6d 70 6c 79 20 69 67 6e 6f  3.by simply igno
36c0: 72 69 6e 67 20 74 68 65 20 22 73 74 61 74 65 22  ring the "state"
36d0: 20 63 6f 6c 75 6d 6e 20 6f 66 20 49 64 78 33 3a   column of Idx3:
36e0: 0a 3c 2f 70 3e 0a 0a 3c 74 63 6c 3e 0a 63 6f 64  .</p>..<tcl>.cod
36f0: 65 20 7b 53 45 4c 45 43 54 20 70 72 69 63 65 20  e {SELECT price 
3700: 46 52 4f 4d 20 66 72 75 69 74 73 66 6f 72 73 61  FROM fruitsforsa
3710: 6c 65 20 57 48 45 52 45 20 66 72 75 69 74 3d 27  le WHERE fruit='
3720: 50 65 61 63 68 27 7d 0a 66 69 67 75 72 65 20 31  Peach'}.figure 1
3730: 32 20 23 66 69 67 31 32 20 69 64 78 33 6c 75 32  2 #fig12 idx3lu2
3740: 2e 67 69 66 20 7b 53 69 6e 67 6c 65 2d 43 6f 6c  .gif {Single-Col
3750: 75 6d 6e 20 4c 6f 6f 6b 75 70 20 4f 6e 20 41 20  umn Lookup On A 
3760: 4d 75 6c 74 69 2d 43 6f 6c 75 6d 6e 20 49 6e 64  Multi-Column Ind
3770: 65 78 7d 0a 3c 2f 74 63 6c 3e 0a 0a 3c 70 3e 0a  ex}.</tcl>..<p>.
3780: 48 65 6e 63 65 2c 20 61 20 67 6f 6f 64 20 72 75  Hence, a good ru
3790: 6c 65 20 6f 66 20 74 68 75 6d 62 20 69 73 20 74  le of thumb is t
37a0: 68 61 74 20 79 6f 75 72 20 64 61 74 61 62 61 73  hat your databas
37b0: 65 20 73 63 68 65 6d 61 20 73 68 6f 75 6c 64 20  e schema should 
37c0: 6e 65 76 65 72 0a 63 6f 6e 74 61 69 6e 20 74 77  never.contain tw
37d0: 6f 20 69 6e 64 69 63 65 73 20 77 68 65 72 65 20  o indices where 
37e0: 6f 6e 65 20 69 6e 64 65 78 20 69 73 20 61 20 70  one index is a p
37f0: 72 65 66 69 78 20 6f 66 20 74 68 65 20 6f 74 68  refix of the oth
3800: 65 72 2e 20 20 44 72 6f 70 20 74 68 65 0a 69 6e  er.  Drop the.in
3810: 64 65 78 20 77 69 74 68 20 66 65 77 65 72 20 63  dex with fewer c
3820: 6f 6c 75 6d 6e 73 2e 20 20 53 51 4c 69 74 65 20  olumns.  SQLite 
3830: 77 69 6c 6c 20 73 74 69 6c 6c 20 62 65 20 61 62  will still be ab
3840: 6c 65 20 74 6f 20 64 6f 20 65 66 66 69 63 69 65  le to do efficie
3850: 6e 74 0a 6c 6f 6f 6b 75 70 73 20 77 69 74 68 20  nt.lookups with 
3860: 74 68 65 20 6c 6f 6e 67 65 72 20 69 6e 64 65 78  the longer index
3870: 2e 0a 3c 2f 70 3e 0a 0a 3c 74 63 6c 3e 68 64 5f  ..</p>..<tcl>hd_
3880: 66 72 61 67 6d 65 6e 74 20 63 6f 76 69 64 78 20  fragment covidx 
3890: 7b 63 6f 76 65 72 69 6e 67 20 69 6e 64 65 78 7d  {covering index}
38a0: 20 7b 63 6f 76 65 72 69 6e 67 20 69 6e 64 69 63   {covering indic
38b0: 65 73 7d 3c 2f 74 63 6c 3e 0a 3c 68 32 3e 20 43  es}</tcl>.<h2> C
38c0: 6f 76 65 72 69 6e 67 20 49 6e 64 69 63 65 73 3c  overing Indices<
38d0: 2f 68 32 3e 0a 0a 3c 70 3e 0a 54 68 65 20 22 70  /h2>..<p>.The "p
38e0: 72 69 63 65 20 6f 66 20 43 61 6c 69 66 6f 72 6e  rice of Californ
38f0: 69 61 20 6f 72 61 6e 67 65 73 22 20 71 75 65 72  ia oranges" quer
3900: 79 20 77 61 73 20 6d 61 64 65 20 6d 6f 72 65 20  y was made more 
3910: 65 66 66 69 63 69 65 6e 74 20 74 68 72 6f 75 67  efficient throug
3920: 68 0a 74 68 65 20 75 73 65 20 6f 66 20 61 20 74  h.the use of a t
3930: 77 6f 2d 63 6f 6c 75 6d 6e 20 69 6e 64 65 78 2e  wo-column index.
3940: 20 20 42 75 74 20 53 51 4c 69 74 65 20 63 61 6e    But SQLite can
3950: 20 64 6f 20 65 76 65 6e 20 62 65 74 74 65 72 20   do even better 
3960: 77 69 74 68 20 61 0a 74 68 72 65 65 2d 63 6f 6c  with a.three-col
3970: 75 6d 6e 20 69 6e 64 65 78 20 74 68 61 74 20 61  umn index that a
3980: 6c 73 6f 20 69 6e 63 6c 75 64 65 73 20 74 68 65  lso includes the
3990: 20 22 70 72 69 63 65 22 20 63 6f 6c 75 6d 6e 3a   "price" column:
39a0: 0a 3c 2f 70 3e 0a 0a 3c 74 63 6c 3e 0a 63 6f 64  .</p>..<tcl>.cod
39b0: 65 20 7b 43 52 45 41 54 45 20 49 4e 44 45 58 20  e {CREATE INDEX 
39c0: 49 64 78 34 20 4f 4e 20 46 72 75 69 74 73 46 6f  Idx4 ON FruitsFo
39d0: 72 53 61 6c 65 28 66 72 75 69 74 2c 20 73 74 61  rSale(fruit, sta
39e0: 74 65 2c 20 70 72 69 63 65 29 3b 7d 0a 66 69 67  te, price);}.fig
39f0: 75 72 65 20 31 33 20 23 66 69 67 31 33 20 69 64  ure 13 #fig13 id
3a00: 78 34 2e 67 69 66 20 7b 41 20 43 6f 76 65 72 69  x4.gif {A Coveri
3a10: 6e 67 20 49 6e 64 65 78 7d 0a 3c 2f 74 63 6c 3e  ng Index}.</tcl>
3a20: 0a 0a 3c 70 3e 0a 54 68 69 73 20 6e 65 77 20 69  ..<p>.This new i
3a30: 6e 64 65 78 20 63 6f 6e 74 61 69 6e 73 20 61 6c  ndex contains al
3a40: 6c 20 74 68 65 20 63 6f 6c 75 6d 6e 73 20 6f 66  l the columns of
3a50: 20 74 68 65 20 6f 72 69 67 69 6e 61 6c 20 46 72   the original Fr
3a60: 75 69 74 73 46 6f 72 53 61 6c 65 20 74 61 62 6c  uitsForSale tabl
3a70: 65 20 74 68 61 74 0a 61 72 65 20 75 73 65 64 20  e that.are used 
3a80: 62 79 20 74 68 65 20 71 75 65 72 79 20 2d 20 62  by the query - b
3a90: 6f 74 68 20 74 68 65 20 73 65 61 72 63 68 20 74  oth the search t
3aa0: 65 72 6d 73 20 61 6e 64 20 74 68 65 20 6f 75 74  erms and the out
3ab0: 70 75 74 2e 20 20 57 65 20 63 61 6c 6c 0a 74 68  put.  We call.th
3ac0: 69 73 20 61 20 22 63 6f 76 65 72 69 6e 67 20 69  is a "covering i
3ad0: 6e 64 65 78 22 2e 20 20 42 65 63 61 75 73 65 20  ndex".  Because 
3ae0: 61 6c 6c 20 6f 66 20 74 68 65 20 69 6e 66 6f 72  all of the infor
3af0: 6d 61 74 69 6f 6e 20 6e 65 65 64 65 64 20 69 73  mation needed is
3b00: 20 69 6e 0a 74 68 65 20 63 6f 76 65 72 69 6e 67   in.the covering
3b10: 20 69 6e 64 65 78 2c 20 53 51 4c 69 74 65 20 6e   index, SQLite n
3b20: 65 76 65 72 20 6e 65 65 64 73 20 74 6f 20 63 6f  ever needs to co
3b30: 6e 73 75 6c 74 20 74 68 65 20 6f 72 69 67 69 6e  nsult the origin
3b40: 61 6c 20 74 61 62 6c 65 0a 69 6e 20 6f 72 64 65  al table.in orde
3b50: 72 20 74 6f 20 66 69 6e 64 20 74 68 65 20 70 72  r to find the pr
3b60: 69 63 65 2e 0a 3c 2f 70 3e 0a 0a 3c 74 63 6c 3e  ice..</p>..<tcl>
3b70: 0a 63 6f 64 65 20 7b 53 45 4c 45 43 54 20 70 72  .code {SELECT pr
3b80: 69 63 65 20 46 52 4f 4d 20 66 72 75 69 74 73 66  ice FROM fruitsf
3b90: 6f 72 73 61 6c 65 20 57 48 45 52 45 20 66 72 75  orsale WHERE fru
3ba0: 69 74 3d 27 4f 72 61 6e 67 65 27 20 41 4e 44 20  it='Orange' AND 
3bb0: 73 74 61 74 65 3d 27 43 41 27 3b 7d 0a 66 69 67  state='CA';}.fig
3bc0: 75 72 65 20 31 34 20 23 66 69 67 31 34 20 69 64  ure 14 #fig14 id
3bd0: 78 34 6c 75 31 2e 67 69 66 20 7b 51 75 65 72 79  x4lu1.gif {Query
3be0: 20 55 73 69 6e 67 20 41 20 43 6f 76 65 72 69 6e   Using A Coverin
3bf0: 67 20 49 6e 64 65 78 7d 0a 3c 2f 74 63 6c 3e 0a  g Index}.</tcl>.
3c00: 0a 3c 70 3e 0a 48 65 6e 63 65 2c 20 62 79 20 61  .<p>.Hence, by a
3c10: 64 64 69 6e 67 20 65 78 74 72 61 20 22 6f 75 74  dding extra "out
3c20: 70 75 74 22 20 63 6f 6c 75 6d 6e 73 20 6f 6e 74  put" columns ont
3c30: 6f 20 74 68 65 20 65 6e 64 20 6f 66 20 61 6e 20  o the end of an 
3c40: 69 6e 64 65 78 2c 20 6f 6e 65 0a 63 61 6e 20 61  index, one.can a
3c50: 76 6f 69 64 20 68 61 76 69 6e 67 20 74 6f 20 72  void having to r
3c60: 65 66 65 72 65 6e 63 65 20 74 68 65 20 6f 72 69  eference the ori
3c70: 67 69 6e 61 6c 20 74 61 62 6c 65 20 61 6e 64 20  ginal table and 
3c80: 74 68 65 72 65 62 79 0a 63 75 74 20 74 68 65 20  thereby.cut the 
3c90: 6e 75 6d 62 65 72 20 6f 66 20 62 69 6e 61 72 79  number of binary
3ca0: 20 73 65 61 72 63 68 65 73 20 66 6f 72 20 61 20   searches for a 
3cb0: 71 75 65 72 79 20 69 6e 20 68 61 6c 66 2e 20 20  query in half.  
3cc0: 54 68 69 73 20 69 73 20 61 0a 63 6f 6e 73 74 61  This is a.consta
3cd0: 6e 74 2d 66 61 63 74 6f 72 20 69 6d 70 72 6f 76  nt-factor improv
3ce0: 65 6d 65 6e 74 20 69 6e 20 70 65 72 66 6f 72 6d  ement in perform
3cf0: 61 6e 63 65 20 28 72 6f 75 67 68 6c 79 20 61 20  ance (roughly a 
3d00: 64 6f 75 62 6c 69 6e 67 20 6f 66 0a 74 68 65 20  doubling of.the 
3d10: 73 70 65 65 64 29 2e 20 20 42 75 74 20 6f 6e 20  speed).  But on 
3d20: 74 68 65 20 6f 74 68 65 72 20 68 61 6e 64 2c 20  the other hand, 
3d30: 69 74 20 69 73 20 61 6c 73 6f 20 6a 75 73 74 20  it is also just 
3d40: 61 20 72 65 66 69 6e 65 6d 65 6e 74 3b 0a 41 20  a refinement;.A 
3d50: 74 77 6f 2d 66 6f 6c 64 20 70 65 72 66 6f 72 6d  two-fold perform
3d60: 61 6e 63 65 20 69 6e 63 72 65 61 73 65 20 69 73  ance increase is
3d70: 20 6e 6f 74 20 6e 65 61 72 6c 79 20 61 73 20 64   not nearly as d
3d80: 72 61 6d 61 74 69 63 20 61 73 20 74 68 65 0a 6f  ramatic as the.o
3d90: 6e 65 2d 6d 69 6c 6c 69 6f 6e 2d 66 6f 6c 64 20  ne-million-fold 
3da0: 69 6e 63 72 65 61 73 65 20 73 65 65 6e 20 77 68  increase seen wh
3db0: 65 6e 20 74 68 65 20 74 61 62 6c 65 20 77 61 73  en the table was
3dc0: 20 66 69 72 73 74 20 69 6e 64 65 78 65 64 2e 0a   first indexed..
3dd0: 41 6e 64 20 66 6f 72 20 6d 6f 73 74 20 71 75 65  And for most que
3de0: 72 69 65 73 2c 20 74 68 65 20 64 69 66 66 65 72  ries, the differ
3df0: 65 6e 63 65 20 62 65 74 77 65 65 6e 20 31 20 6d  ence between 1 m
3e00: 69 63 72 6f 73 65 63 6f 6e 64 20 61 6e 64 0a 32  icrosecond and.2
3e10: 20 6d 69 63 72 6f 73 65 63 6f 6e 64 73 20 69 73   microseconds is
3e20: 20 75 6e 6c 69 6b 65 6c 79 20 74 6f 20 62 65 20   unlikely to be 
3e30: 6e 6f 74 69 63 65 64 2e 0a 3c 2f 70 3e 0a 0a 3c  noticed..</p>..<
3e40: 74 63 6c 3e 68 64 5f 66 72 61 67 6d 65 6e 74 20  tcl>hd_fragment 
3e50: 6f 72 5f 69 6e 5f 77 68 65 72 65 20 6f 72 2d 63  or_in_where or-c
3e60: 6f 6e 6e 65 63 74 65 64 2d 74 65 72 6d 73 3c 2f  onnected-terms</
3e70: 74 63 6c 3e 0a 3c 68 32 3e 20 4f 52 2d 43 6f 6e  tcl>.<h2> OR-Con
3e80: 6e 65 63 74 65 64 20 54 65 72 6d 73 20 49 6e 20  nected Terms In 
3e90: 54 68 65 20 57 48 45 52 45 20 43 6c 61 75 73 65  The WHERE Clause
3ea0: 3c 2f 68 32 3e 0a 0a 3c 70 3e 0a 4d 75 6c 74 69  </h2>..<p>.Multi
3eb0: 2d 63 6f 6c 75 6d 6e 20 69 6e 64 69 63 65 73 20  -column indices 
3ec0: 6f 6e 6c 79 20 77 6f 72 6b 20 69 66 20 74 68 65  only work if the
3ed0: 20 63 6f 6e 73 74 72 61 69 6e 74 20 74 65 72 6d   constraint term
3ee0: 73 20 69 6e 20 74 68 65 20 57 48 45 52 45 0a 63  s in the WHERE.c
3ef0: 6c 61 75 73 65 20 6f 66 20 74 68 65 20 71 75 65  lause of the que
3f00: 72 79 20 61 72 65 20 63 6f 6e 6e 65 63 74 65 64  ry are connected
3f10: 20 62 79 20 41 4e 44 2e 0a 53 6f 20 49 64 78 33   by AND..So Idx3
3f20: 20 61 6e 64 20 49 64 78 34 20 61 72 65 20 68 65   and Idx4 are he
3f30: 6c 70 66 75 6c 20 77 68 65 6e 20 74 68 65 20 73  lpful when the s
3f40: 65 61 72 63 68 20 69 73 20 66 6f 72 20 69 74 65  earch is for ite
3f50: 6d 73 20 74 68 61 74 0a 61 72 65 20 62 6f 74 68  ms that.are both
3f60: 20 4f 72 61 6e 67 65 73 20 61 6e 64 20 67 72 6f   Oranges and gro
3f70: 77 6e 20 69 6e 20 43 61 6c 69 66 6f 72 6e 69 61  wn in California
3f80: 2c 20 62 75 74 20 6e 65 69 74 68 65 72 20 69 6e  , but neither in
3f90: 64 65 78 20 77 6f 75 6c 64 0a 62 65 20 74 68 61  dex would.be tha
3fa0: 74 20 75 73 65 66 75 6c 20 69 66 20 77 65 20 77  t useful if we w
3fb0: 61 6e 74 65 64 20 61 6c 6c 20 69 74 65 6d 73 20  anted all items 
3fc0: 74 68 61 74 20 77 65 72 65 20 65 69 74 68 65 72  that were either
3fd0: 20 6f 72 61 6e 67 65 73 0a 3c 69 3e 6f 72 3c 2f   oranges.<i>or</
3fe0: 69 3e 20 61 72 65 20 67 72 6f 77 6e 20 69 6e 20  i> are grown in 
3ff0: 43 61 6c 69 66 6f 72 6e 69 61 2e 0a 3c 2f 70 3e  California..</p>
4000: 0a 0a 3c 74 63 6c 3e 63 6f 64 65 20 7b 0a 53 45  ..<tcl>code {.SE
4010: 4c 45 43 54 20 70 72 69 63 65 20 46 52 4f 4d 20  LECT price FROM 
4020: 46 72 75 69 74 73 46 6f 72 53 61 6c 65 20 57 48  FruitsForSale WH
4030: 45 52 45 20 66 72 75 69 74 3d 27 4f 72 61 6e 67  ERE fruit='Orang
4040: 65 27 20 4f 52 20 73 74 61 74 65 3d 27 43 41 27  e' OR state='CA'
4050: 3b 0a 7d 3c 2f 74 63 6c 3e 0a 0a 3c 70 3e 0a 57  ;.}</tcl>..<p>.W
4060: 68 65 6e 20 63 6f 6e 66 72 6f 6e 74 65 64 20 77  hen confronted w
4070: 69 74 68 20 4f 52 2d 63 6f 6e 6e 65 63 74 65 64  ith OR-connected
4080: 20 74 65 72 6d 73 20 69 6e 20 61 20 57 48 45 52   terms in a WHER
4090: 45 20 63 6c 61 75 73 65 2c 20 53 51 4c 69 74 65  E clause, SQLite
40a0: 20 0a 65 78 61 6d 69 6e 65 73 20 65 61 63 68 20   .examines each 
40b0: 4f 52 20 74 65 72 6d 20 73 65 70 61 72 61 74 65  OR term separate
40c0: 6c 79 20 61 6e 64 20 74 72 69 65 73 20 74 6f 20  ly and tries to 
40d0: 75 73 65 20 61 6e 20 69 6e 64 65 78 20 74 6f 0a  use an index to.
40e0: 66 69 6e 64 20 74 68 65 20 72 6f 77 69 64 73 20  find the rowids 
40f0: 61 73 73 6f 63 69 61 74 65 64 20 77 69 74 68 20  associated with 
4100: 65 61 63 68 20 74 65 72 6d 2e 0a 49 74 20 74 68  each term..It th
4110: 65 6e 20 74 61 6b 65 73 20 74 68 65 20 75 6e 69  en takes the uni
4120: 6f 6e 20 6f 66 20 74 68 65 20 72 65 73 75 6c 74  on of the result
4130: 69 6e 67 20 72 6f 77 69 64 20 73 65 74 73 20 74  ing rowid sets t
4140: 6f 20 66 69 6e 64 0a 74 68 65 20 65 6e 64 20 72  o find.the end r
4150: 65 73 75 6c 74 2e 20 20 54 68 65 20 66 6f 6c 6c  esult.  The foll
4160: 6f 77 69 6e 67 20 66 69 67 75 72 65 20 69 6c 6c  owing figure ill
4170: 75 73 74 72 61 74 65 73 20 74 68 69 73 20 70 72  ustrates this pr
4180: 6f 63 65 73 73 3a 0a 3c 2f 70 3e 0a 0a 3c 74 63  ocess:.</p>..<tc
4190: 6c 3e 66 69 67 75 72 65 20 31 35 20 23 66 69 67  l>figure 15 #fig
41a0: 31 35 20 6f 72 71 75 65 72 79 2e 67 69 66 20 7b  15 orquery.gif {
41b0: 51 75 65 72 79 20 57 69 74 68 20 4f 52 20 43 6f  Query With OR Co
41c0: 6e 73 74 72 61 69 6e 74 73 7d 3c 2f 74 63 6c 3e  nstraints}</tcl>
41d0: 0a 0a 3c 70 3e 0a 54 68 65 20 64 69 61 67 72 61  ..<p>.The diagra
41e0: 6d 20 61 62 6f 76 65 20 69 6d 70 6c 69 65 73 20  m above implies 
41f0: 74 68 61 74 20 53 51 4c 69 74 65 20 63 6f 6d 70  that SQLite comp
4200: 75 74 65 73 20 61 6c 6c 20 6f 66 20 74 68 65 20  utes all of the 
4210: 72 6f 77 69 64 73 20 66 69 72 73 74 0a 61 6e 64  rowids first.and
4220: 20 74 68 65 6e 20 63 6f 6d 62 69 6e 65 73 20 74   then combines t
4230: 68 65 6d 20 77 69 74 68 20 61 20 75 6e 69 6f 6e  hem with a union
4240: 20 6f 70 65 72 61 74 69 6f 6e 20 62 65 66 6f 72   operation befor
4250: 65 20 73 74 61 72 74 69 6e 67 20 74 6f 20 64 6f  e starting to do
4260: 0a 72 6f 77 69 64 20 6c 6f 6f 6b 75 70 73 20 6f  .rowid lookups o
4270: 6e 20 74 68 65 20 6f 72 69 67 69 6e 61 6c 20 74  n the original t
4280: 61 62 6c 65 2e 20 20 49 6e 20 72 65 61 6c 69 74  able.  In realit
4290: 79 2c 20 74 68 65 20 72 6f 77 69 64 20 6c 6f 6f  y, the rowid loo
42a0: 6b 75 70 73 0a 61 72 65 20 69 6e 74 65 72 73 70  kups.are intersp
42b0: 65 72 73 65 64 20 77 69 74 68 20 72 6f 77 69 64  ersed with rowid
42c0: 20 63 6f 6d 70 75 74 61 74 69 6f 6e 73 2e 20 20   computations.  
42d0: 53 51 4c 69 74 65 20 75 73 65 73 20 6f 6e 65 20  SQLite uses one 
42e0: 69 6e 64 65 78 20 61 74 0a 61 20 74 69 6d 65 20  index at.a time 
42f0: 74 6f 20 66 69 6e 64 20 72 6f 77 69 64 73 20 77  to find rowids w
4300: 68 69 6c 65 20 72 65 6d 65 6d 62 65 72 69 6e 67  hile remembering
4310: 20 77 68 69 63 68 20 72 6f 77 69 64 73 20 69 74   which rowids it
4320: 20 68 61 73 20 73 65 65 6e 0a 62 65 66 6f 72 65   has seen.before
4330: 20 73 6f 20 61 73 20 74 6f 20 61 76 6f 69 64 20   so as to avoid 
4340: 64 75 70 6c 69 63 61 74 65 73 2e 20 20 54 68 61  duplicates.  Tha
4350: 74 20 69 73 20 6a 75 73 74 20 61 6e 20 69 6d 70  t is just an imp
4360: 6c 65 6d 65 6e 74 61 74 69 6f 6e 0a 64 65 74 61  lementation.deta
4370: 69 6c 2c 20 74 68 6f 75 67 68 2e 20 20 54 68 65  il, though.  The
4380: 20 64 69 61 67 72 61 6d 2c 20 77 68 69 6c 65 20   diagram, while 
4390: 6e 6f 74 20 31 30 30 25 20 61 63 63 75 72 61 74  not 100% accurat
43a0: 65 2c 20 70 72 6f 76 69 64 65 73 20 61 20 67 6f  e, provides a go
43b0: 6f 64 0a 6f 76 65 72 76 69 65 77 20 6f 66 20 77  od.overview of w
43c0: 68 61 74 20 69 73 20 68 61 70 70 65 6e 69 6e 67  hat is happening
43d0: 2e 0a 3c 2f 70 3e 0a 0a 3c 70 3e 0a 49 6e 20 6f  ..</p>..<p>.In o
43e0: 72 64 65 72 20 66 6f 72 20 74 68 65 20 4f 52 2d  rder for the OR-
43f0: 62 79 2d 55 4e 49 4f 4e 20 74 65 63 68 6e 69 71  by-UNION techniq
4400: 75 65 20 73 68 6f 77 6e 20 61 62 6f 76 65 20 74  ue shown above t
4410: 6f 20 62 65 20 75 73 65 66 75 6c 2c 20 74 68 65  o be useful, the
4420: 72 65 0a 6d 75 73 74 20 62 65 20 61 6e 20 69 6e  re.must be an in
4430: 64 65 78 20 61 76 61 69 6c 61 62 6c 65 20 74 68  dex available th
4440: 61 74 20 68 65 6c 70 73 20 72 65 73 6f 6c 76 65  at helps resolve
4450: 20 65 76 65 72 79 20 4f 52 2d 63 6f 6e 6e 65 63   every OR-connec
4460: 74 65 64 20 74 65 72 6d 0a 69 6e 20 74 68 65 20  ted term.in the 
4470: 57 48 45 52 45 20 63 6c 61 75 73 65 2e 20 20 49  WHERE clause.  I
4480: 66 20 65 76 65 6e 20 61 20 73 69 6e 67 6c 65 20  f even a single 
4490: 4f 52 2d 63 6f 6e 6e 65 63 74 65 64 20 74 65 72  OR-connected ter
44a0: 6d 20 69 73 20 6e 6f 74 20 69 6e 64 65 78 65 64  m is not indexed
44b0: 2c 0a 74 68 65 6e 20 61 20 66 75 6c 6c 20 74 61  ,.then a full ta
44c0: 62 6c 65 20 73 63 61 6e 20 77 6f 75 6c 64 20 68  ble scan would h
44d0: 61 76 65 20 74 6f 20 62 65 20 64 6f 6e 65 20 69  ave to be done i
44e0: 6e 20 6f 72 64 65 72 20 74 6f 20 66 69 6e 64 20  n order to find 
44f0: 74 68 65 20 72 6f 77 69 64 73 0a 67 65 6e 65 72  the rowids.gener
4500: 61 74 65 64 20 62 79 20 74 68 65 20 6f 6e 65 20  ated by the one 
4510: 74 65 72 6d 2c 20 61 6e 64 20 69 66 20 53 51 4c  term, and if SQL
4520: 69 74 65 20 68 61 73 20 74 6f 20 64 6f 20 61 20  ite has to do a 
4530: 66 75 6c 6c 20 74 61 62 6c 65 20 73 63 61 6e 2c  full table scan,
4540: 20 69 74 0a 6d 69 67 68 74 20 61 73 20 77 65 6c   it.might as wel
4550: 6c 20 64 6f 20 69 74 20 6f 6e 20 74 68 65 20 6f  l do it on the o
4560: 72 69 67 69 6e 61 6c 20 74 61 62 6c 65 20 61 6e  riginal table an
4570: 64 20 67 65 74 20 61 6c 6c 20 6f 66 20 74 68 65  d get all of the
4580: 20 72 65 73 75 6c 74 73 20 69 6e 0a 61 20 73 69   results in.a si
4590: 6e 67 6c 65 20 70 61 73 73 20 77 69 74 68 6f 75  ngle pass withou
45a0: 74 20 68 61 76 69 6e 67 20 74 6f 20 6d 65 73 73  t having to mess
45b0: 20 77 69 74 68 20 75 6e 69 6f 6e 20 6f 70 65 72   with union oper
45c0: 61 74 69 6f 6e 73 20 61 6e 64 20 66 6f 6c 6c 6f  ations and follo
45d0: 77 2d 6f 6e 0a 62 69 6e 61 72 79 20 73 65 61 72  w-on.binary sear
45e0: 63 68 65 73 2e 0a 3c 2f 70 3e 0a 0a 3c 70 3e 0a  ches..</p>..<p>.
45f0: 4f 6e 65 20 63 61 6e 20 73 65 65 20 68 6f 77 20  One can see how 
4600: 74 68 65 20 4f 52 2d 62 79 2d 55 4e 49 4f 4e 20  the OR-by-UNION 
4610: 74 65 63 68 6e 69 71 75 65 20 63 6f 75 6c 64 20  technique could 
4620: 61 6c 73 6f 20 62 65 20 6c 65 76 65 72 61 67 65  also be leverage
4630: 64 20 74 6f 0a 75 73 65 20 6d 75 6c 74 69 70 6c  d to.use multipl
4640: 65 20 69 6e 64 69 63 65 73 20 6f 6e 20 71 75 65  e indices on que
4650: 72 69 65 73 20 77 68 65 72 65 20 74 68 65 20 57  ries where the W
4660: 48 45 52 45 20 63 6c 61 75 73 65 20 68 61 73 20  HERE clause has 
4670: 74 65 72 6d 73 20 63 6f 6e 6e 65 63 74 65 64 0a  terms connected.
4680: 62 79 20 41 4e 44 2c 20 62 79 20 75 73 69 6e 67  by AND, by using
4690: 20 61 6e 20 69 6e 74 65 72 73 65 63 74 20 6f 70   an intersect op
46a0: 65 72 61 74 6f 72 20 69 6e 20 70 6c 61 63 65 20  erator in place 
46b0: 6f 66 20 75 6e 69 6f 6e 2e 20 20 4d 61 6e 79 20  of union.  Many 
46c0: 53 51 4c 0a 64 61 74 61 62 61 73 65 20 65 6e 67  SQL.database eng
46d0: 69 6e 65 73 20 77 69 6c 6c 20 64 6f 20 6a 75 73  ines will do jus
46e0: 74 20 74 68 61 74 2e 20 20 42 75 74 20 74 68 65  t that.  But the
46f0: 20 70 65 72 66 6f 72 6d 61 6e 63 65 20 67 61 69   performance gai
4700: 6e 20 6f 76 65 72 20 75 73 69 6e 67 0a 6a 75 73  n over using.jus
4710: 74 20 61 20 73 69 6e 67 6c 65 20 69 6e 64 65 78  t a single index
4720: 20 69 73 20 73 6c 69 67 68 74 20 61 6e 64 20 73   is slight and s
4730: 6f 20 53 51 4c 69 74 65 20 64 6f 65 73 20 6e 6f  o SQLite does no
4740: 74 20 69 6d 70 6c 65 6d 65 6e 74 20 74 68 61 74  t implement that
4750: 20 74 65 63 68 6e 69 71 75 65 0a 61 74 20 74 68   technique.at th
4760: 69 73 20 74 69 6d 65 2e 20 20 48 6f 77 65 76 65  is time.  Howeve
4770: 72 2c 20 61 20 66 75 74 75 72 65 20 76 65 72 73  r, a future vers
4780: 69 6f 6e 20 53 51 4c 69 74 65 20 6d 69 67 68 74  ion SQLite might
4790: 20 62 65 20 65 6e 68 61 6e 63 65 64 20 74 6f 20   be enhanced to 
47a0: 73 75 70 70 6f 72 74 0a 41 4e 44 2d 62 79 2d 49  support.AND-by-I
47b0: 4e 54 45 52 53 45 43 54 2e 0a 3c 2f 70 3e 0a 0a  NTERSECT..</p>..
47c0: 3c 74 63 6c 3e 68 64 5f 66 72 61 67 6d 65 6e 74  <tcl>hd_fragment
47d0: 20 73 6f 72 74 69 6e 67 20 73 6f 72 74 69 6e 67   sorting sorting
47e0: 3c 2f 74 63 6c 3e 0a 3c 68 31 3e 20 53 6f 72 74  </tcl>.<h1> Sort
47f0: 69 6e 67 3c 2f 68 31 3e 0a 0a 3c 70 3e 0a 53 51  ing</h1>..<p>.SQ
4800: 4c 69 74 65 20 28 6c 69 6b 65 20 61 6c 6c 20 6f  Lite (like all o
4810: 74 68 65 72 20 53 51 4c 20 64 61 74 61 62 61 73  ther SQL databas
4820: 65 20 65 6e 67 69 6e 65 73 29 20 63 61 6e 20 61  e engines) can a
4830: 6c 73 6f 20 75 73 65 20 69 6e 64 69 63 65 73 20  lso use indices 
4840: 74 6f 0a 73 61 74 69 73 66 79 20 74 68 65 20 4f  to.satisfy the O
4850: 52 44 45 52 20 42 59 20 63 6c 61 75 73 65 73 20  RDER BY clauses 
4860: 69 6e 20 61 20 71 75 65 72 79 2c 20 69 6e 20 61  in a query, in a
4870: 64 64 69 74 69 6f 6e 20 74 6f 20 65 78 70 65 64  ddition to exped
4880: 69 74 69 6e 67 0a 6c 6f 6f 6b 75 70 2e 20 20 49  iting.lookup.  I
4890: 6e 20 6f 74 68 65 72 20 77 6f 72 64 73 2c 20 69  n other words, i
48a0: 6e 64 69 63 65 73 20 63 61 6e 20 62 65 20 75 73  ndices can be us
48b0: 65 64 20 74 6f 20 73 70 65 65 64 20 75 70 20 73  ed to speed up s
48c0: 6f 72 74 69 6e 67 20 61 73 0a 77 65 6c 6c 20 61  orting as.well a
48d0: 73 20 73 65 61 72 63 68 69 6e 67 2e 0a 3c 2f 70  s searching..</p
48e0: 3e 0a 0a 3c 70 3e 0a 57 68 65 6e 20 6e 6f 20 61  >..<p>.When no a
48f0: 70 70 72 6f 70 72 69 61 74 65 20 69 6e 64 69 63  ppropriate indic
4900: 65 73 20 61 72 65 20 61 76 61 69 6c 61 62 6c 65  es are available
4910: 2c 20 61 20 71 75 65 72 79 20 77 69 74 68 20 61  , a query with a
4920: 6e 20 4f 52 44 45 52 20 42 59 0a 63 6c 61 75 73  n ORDER BY.claus
4930: 65 20 6d 75 73 74 20 62 65 20 73 6f 72 74 65 64  e must be sorted
4940: 20 61 73 20 61 20 73 65 70 61 72 61 74 65 20 73   as a separate s
4950: 74 65 70 2e 20 20 43 6f 6e 73 69 64 65 72 20 74  tep.  Consider t
4960: 68 69 73 20 71 75 65 72 79 3a 0a 3c 2f 70 3e 0a  his query:.</p>.
4970: 0a 3c 74 63 6c 3e 63 6f 64 65 20 7b 53 45 4c 45  .<tcl>code {SELE
4980: 43 54 20 2a 20 46 52 4f 4d 20 66 72 75 69 74 73  CT * FROM fruits
4990: 66 6f 72 73 61 6c 65 20 4f 52 44 45 52 20 42 59  forsale ORDER BY
49a0: 20 66 72 75 69 74 3b 7d 3c 2f 74 63 6c 3e 0a 0a   fruit;}</tcl>..
49b0: 3c 70 3e 0a 53 51 4c 69 74 65 20 70 72 6f 63 65  <p>.SQLite proce
49c0: 73 73 65 73 20 74 68 69 73 20 62 79 20 67 61 74  sses this by gat
49d0: 68 65 72 69 6e 67 20 61 6c 6c 20 74 68 65 20 6f  hering all the o
49e0: 75 74 70 75 74 20 6f 66 20 71 75 65 72 79 20 61  utput of query a
49f0: 6e 64 20 74 68 65 6e 0a 72 75 6e 6e 69 6e 67 20  nd then.running 
4a00: 74 68 61 74 20 6f 75 74 70 75 74 20 74 68 72 6f  that output thro
4a10: 75 67 68 20 61 20 73 6f 72 74 65 72 2e 0a 3c 2f  ugh a sorter..</
4a20: 70 3e 0a 0a 3c 74 63 6c 3e 66 69 67 75 72 65 20  p>..<tcl>figure 
4a30: 31 36 20 23 66 69 67 31 36 20 6f 62 66 72 75 69  16 #fig16 obfrui
4a40: 74 6e 6f 69 64 78 2e 67 69 66 20 7b 53 6f 72 74  tnoidx.gif {Sort
4a50: 69 6e 67 20 57 69 74 68 6f 75 74 20 41 6e 20 49  ing Without An I
4a60: 6e 64 65 78 7d 3c 2f 74 63 6c 3e 0a 0a 3c 70 3e  ndex}</tcl>..<p>
4a70: 0a 49 66 20 74 68 65 20 6e 75 6d 62 65 72 20 6f  .If the number o
4a80: 66 20 6f 75 74 70 75 74 20 72 6f 77 73 20 69 73  f output rows is
4a90: 20 4b 2c 20 74 68 65 6e 20 74 68 65 20 74 69 6d   K, then the tim
4aa0: 65 20 6e 65 65 64 65 64 20 74 6f 20 73 6f 72 74  e needed to sort
4ab0: 20 69 73 0a 70 72 6f 70 6f 72 74 69 6f 6e 61 6c   is.proportional
4ac0: 20 74 6f 20 4b 6c 6f 67 4b 2e 20 20 49 66 20 4b   to KlogK.  If K
4ad0: 20 69 73 20 73 6d 61 6c 6c 2c 20 74 68 65 20 73   is small, the s
4ae0: 6f 72 74 69 6e 67 20 74 69 6d 65 20 69 73 20 75  orting time is u
4af0: 73 75 61 6c 6c 79 0a 6e 6f 74 20 61 20 66 61 63  sually.not a fac
4b00: 74 6f 72 2c 20 62 75 74 20 69 6e 20 61 20 71 75  tor, but in a qu
4b10: 65 72 79 20 73 75 63 68 20 61 73 20 74 68 65 20  ery such as the 
4b20: 61 62 6f 76 65 20 77 68 65 72 65 20 4b 3d 3d 4e  above where K==N
4b30: 2c 20 74 68 65 20 74 69 6d 65 0a 6e 65 65 64 65  , the time.neede
4b40: 64 20 74 6f 20 73 6f 72 74 20 63 61 6e 20 62 65  d to sort can be
4b50: 20 6d 75 63 68 20 67 72 65 61 74 65 72 20 74 68   much greater th
4b60: 61 6e 20 74 68 65 20 74 69 6d 65 20 6e 65 65 64  an the time need
4b70: 65 64 20 74 6f 20 64 6f 20 61 0a 66 75 6c 6c 20  ed to do a.full 
4b80: 74 61 62 6c 65 20 73 63 61 6e 2e 20 20 46 75 72  table scan.  Fur
4b90: 74 68 65 72 6d 6f 72 65 2c 20 74 68 65 20 65 6e  thermore, the en
4ba0: 74 69 72 65 20 6f 75 74 70 75 74 20 69 73 20 61  tire output is a
4bb0: 63 63 75 6d 75 6c 61 74 65 64 20 69 6e 0a 74 65  ccumulated in.te
4bc0: 6d 70 6f 72 61 72 79 20 73 74 6f 72 61 67 65 20  mporary storage 
4bd0: 28 77 68 69 63 68 20 6d 69 67 68 74 20 62 65 20  (which might be 
4be0: 65 69 74 68 65 72 20 69 6e 20 6d 61 69 6e 20 6d  either in main m
4bf0: 65 6d 6f 72 79 20 6f 72 20 6f 6e 20 64 69 73 6b  emory or on disk
4c00: 2c 0a 64 65 70 65 6e 64 69 6e 67 20 6f 6e 20 76  ,.depending on v
4c10: 61 72 69 6f 75 73 20 63 6f 6d 70 69 6c 65 2d 74  arious compile-t
4c20: 69 6d 65 20 61 6e 64 20 72 75 6e 2d 74 69 6d 65  ime and run-time
4c30: 20 73 65 74 74 69 6e 67 73 29 0a 77 68 69 63 68   settings).which
4c40: 20 63 61 6e 20 6d 65 61 6e 20 74 68 61 74 20 61   can mean that a
4c50: 20 6c 6f 74 20 6f 66 20 74 65 6d 70 6f 72 61 72   lot of temporar
4c60: 79 20 73 74 6f 72 61 67 65 20 69 73 20 72 65 71  y storage is req
4c70: 75 69 72 65 64 20 74 6f 20 63 6f 6d 70 6c 65 74  uired to complet
4c80: 65 0a 74 68 65 20 71 75 65 72 79 2e 0a 3c 2f 70  e.the query..</p
4c90: 3e 0a 0a 3c 68 32 3e 20 53 6f 72 74 69 6e 67 20  >..<h2> Sorting 
4ca0: 42 79 20 52 6f 77 69 64 3c 2f 68 32 3e 0a 0a 3c  By Rowid</h2>..<
4cb0: 70 3e 0a 42 65 63 61 75 73 65 20 73 6f 72 74 69  p>.Because sorti
4cc0: 6e 67 20 63 61 6e 20 62 65 20 65 78 70 65 6e 73  ng can be expens
4cd0: 69 76 65 2c 20 53 51 4c 69 74 65 20 77 6f 72 6b  ive, SQLite work
4ce0: 73 20 68 61 72 64 20 74 6f 20 63 6f 6e 76 65 72  s hard to conver
4cf0: 74 20 4f 52 44 45 52 20 42 59 0a 63 6c 61 75 73  t ORDER BY.claus
4d00: 65 73 20 69 6e 74 6f 20 6e 6f 2d 6f 70 73 2e 20  es into no-ops. 
4d10: 20 49 66 20 53 51 4c 69 74 65 20 64 65 74 65 72   If SQLite deter
4d20: 6d 69 6e 65 73 20 74 68 61 74 20 6f 75 74 70 75  mines that outpu
4d30: 74 20 77 69 6c 6c 0a 6e 61 74 75 72 61 6c 6c 79  t will.naturally
4d40: 20 61 70 70 65 61 72 20 69 6e 20 74 68 65 20 6f   appear in the o
4d50: 72 64 65 72 20 73 70 65 63 69 66 69 65 64 2c 20  rder specified, 
4d60: 74 68 65 6e 20 6e 6f 20 73 6f 72 74 69 6e 67 20  then no sorting 
4d70: 69 73 20 64 6f 6e 65 2e 0a 53 6f 2c 20 66 6f 72  is done..So, for
4d80: 20 65 78 61 6d 70 6c 65 2c 20 69 66 20 79 6f 75   example, if you
4d90: 20 72 65 71 75 65 73 74 20 74 68 65 20 6f 75 74   request the out
4da0: 70 75 74 20 69 6e 20 72 6f 77 69 64 20 6f 72 64  put in rowid ord
4db0: 65 72 2c 20 6e 6f 20 73 6f 72 74 69 6e 67 0a 77  er, no sorting.w
4dc0: 69 6c 6c 20 62 65 20 64 6f 6e 65 3a 0a 3c 2f 70  ill be done:.</p
4dd0: 3e 0a 0a 3c 74 63 6c 3e 0a 63 6f 64 65 20 7b 53  >..<tcl>.code {S
4de0: 45 4c 45 43 54 20 2a 20 46 52 4f 4d 20 66 72 75  ELECT * FROM fru
4df0: 69 74 73 66 6f 72 73 61 6c 65 20 4f 52 44 45 52  itsforsale ORDER
4e00: 20 42 59 20 72 6f 77 69 64 3b 7d 0a 66 69 67 75   BY rowid;}.figu
4e10: 72 65 20 31 37 20 23 66 69 67 31 37 20 6f 62 72  re 17 #fig17 obr
4e20: 6f 77 69 64 2e 67 69 66 20 7b 53 6f 72 74 69 6e  owid.gif {Sortin
4e30: 67 20 42 79 20 52 6f 77 69 64 7d 0a 3c 2f 74 63  g By Rowid}.</tc
4e40: 6c 3e 0a 0a 3c 70 3e 0a 59 6f 75 20 63 61 6e 20  l>..<p>.You can 
4e50: 61 6c 73 6f 20 72 65 71 75 65 73 74 20 61 20 72  also request a r
4e60: 65 76 65 72 73 65 2d 6f 72 64 65 72 20 73 6f 72  everse-order sor
4e70: 74 20 6c 69 6b 65 20 74 68 69 73 3a 0a 3c 2f 70  t like this:.</p
4e80: 3e 0a 0a 3c 74 63 6c 3e 63 6f 64 65 20 7b 53 45  >..<tcl>code {SE
4e90: 4c 45 43 54 20 2a 20 46 52 4f 4d 20 66 72 75 69  LECT * FROM frui
4ea0: 74 73 66 6f 72 73 61 6c 65 20 4f 52 44 45 52 20  tsforsale ORDER 
4eb0: 42 59 20 72 6f 77 69 64 20 44 45 53 43 3b 7d 3c  BY rowid DESC;}<
4ec0: 2f 74 63 6c 3e 0a 0a 3c 70 3e 0a 53 51 4c 69 74  /tcl>..<p>.SQLit
4ed0: 65 20 77 69 6c 6c 20 73 74 69 6c 6c 20 6f 6d 69  e will still omi
4ee0: 74 20 74 68 65 20 73 6f 72 74 69 6e 67 20 73 74  t the sorting st
4ef0: 65 70 2e 20 20 42 75 74 20 69 6e 20 6f 72 64 65  ep.  But in orde
4f00: 72 20 66 6f 72 20 6f 75 74 70 75 74 20 74 6f 0a  r for output to.
4f10: 61 70 70 65 61 72 20 69 6e 20 74 68 65 20 63 6f  appear in the co
4f20: 72 72 65 63 74 20 6f 72 64 65 72 2c 20 53 51 4c  rrect order, SQL
4f30: 69 74 65 20 77 69 6c 6c 20 64 6f 20 74 68 65 20  ite will do the 
4f40: 74 61 62 6c 65 20 73 63 61 6e 20 73 74 61 72 74  table scan start
4f50: 69 6e 67 20 61 74 0a 74 68 65 20 65 6e 64 20 61  ing at.the end a
4f60: 6e 64 20 77 6f 72 6b 69 6e 67 20 74 6f 77 61 72  nd working towar
4f70: 64 20 74 68 65 20 62 65 67 69 6e 6e 69 6e 67 2c  d the beginning,
4f80: 20 72 61 74 68 65 72 20 74 68 61 6e 20 73 74 61   rather than sta
4f90: 72 74 69 6e 67 20 61 74 20 74 68 65 0a 62 65 67  rting at the.beg
4fa0: 69 6e 6e 69 6e 67 20 61 6e 64 20 77 6f 72 6b 69  inning and worki
4fb0: 6e 67 20 74 6f 77 61 72 64 20 74 68 65 20 65 6e  ng toward the en
4fc0: 64 20 61 73 20 73 68 6f 77 6e 20 69 6e 20 0a 3c  d as shown in .<
4fd0: 61 20 68 72 65 66 3d 22 23 66 69 67 31 37 22 3e  a href="#fig17">
4fe0: 66 69 67 75 72 65 20 31 37 3c 2f 61 3e 2e 0a 3c  figure 17</a>..<
4ff0: 2f 70 3e 0a 0a 3c 68 32 3e 20 53 6f 72 74 69 6e  /p>..<h2> Sortin
5000: 67 20 42 79 20 49 6e 64 65 78 3c 2f 68 32 3e 0a  g By Index</h2>.
5010: 0a 3c 70 3e 0a 4f 66 20 63 6f 75 72 73 65 2c 20  .<p>.Of course, 
5020: 6f 72 64 65 72 69 6e 67 20 74 68 65 20 6f 75 74  ordering the out
5030: 70 75 74 20 6f 66 20 61 20 71 75 65 72 79 20 62  put of a query b
5040: 79 20 72 6f 77 69 64 20 69 73 20 73 65 6c 64 6f  y rowid is seldo
5050: 6d 20 75 73 65 66 75 6c 2e 0a 55 73 75 61 6c 6c  m useful..Usuall
5060: 79 20 6f 6e 65 20 77 61 6e 74 73 20 74 6f 20 6f  y one wants to o
5070: 72 64 65 72 20 74 68 65 20 6f 75 74 70 75 74 20  rder the output 
5080: 62 79 20 73 6f 6d 65 20 6f 74 68 65 72 20 63 6f  by some other co
5090: 6c 75 6d 6e 2e 0a 3c 2f 70 3e 0a 0a 3c 70 3e 0a  lumn..</p>..<p>.
50a0: 49 66 20 61 6e 20 69 6e 64 65 78 20 69 73 20 61  If an index is a
50b0: 76 61 69 6c 61 62 6c 65 20 6f 6e 20 74 68 65 20  vailable on the 
50c0: 4f 52 44 45 52 20 42 59 20 63 6f 6c 75 6d 6e 2c  ORDER BY column,
50d0: 20 74 68 61 74 20 69 6e 64 65 78 20 63 61 6e 20   that index can 
50e0: 62 65 20 75 73 65 64 0a 66 6f 72 20 73 6f 72 74  be used.for sort
50f0: 69 6e 67 2e 20 20 43 6f 6e 73 69 64 65 72 20 74  ing.  Consider t
5100: 68 65 20 72 65 71 75 65 73 74 20 66 6f 72 20 61  he request for a
5110: 6c 6c 20 69 74 65 6d 73 20 73 6f 72 74 65 64 20  ll items sorted 
5120: 62 79 20 22 66 72 75 69 74 22 3a 0a 3c 2f 70 3e  by "fruit":.</p>
5130: 0a 0a 3c 74 63 6c 3e 63 6f 64 65 20 7b 53 45 4c  ..<tcl>code {SEL
5140: 45 43 54 20 2a 20 46 52 4f 4d 20 66 72 75 69 74  ECT * FROM fruit
5150: 73 66 6f 72 73 61 6c 65 20 4f 52 44 45 52 20 42  sforsale ORDER B
5160: 59 20 66 72 75 69 74 3b 7d 3c 2f 74 63 6c 3e 0a  Y fruit;}</tcl>.
5170: 0a 3c 74 63 6c 3e 66 69 67 75 72 65 20 31 38 20  .<tcl>figure 18 
5180: 23 66 69 67 31 38 20 6f 62 66 72 75 69 74 69 64  #fig18 obfruitid
5190: 78 31 2e 67 69 66 20 7b 53 6f 72 74 69 6e 67 20  x1.gif {Sorting 
51a0: 57 69 74 68 20 41 6e 20 49 6e 64 65 78 7d 3c 2f  With An Index}</
51b0: 74 63 6c 3e 0a 0a 3c 70 3e 0a 54 68 65 20 49 64  tcl>..<p>.The Id
51c0: 78 31 20 69 6e 64 65 78 20 69 73 20 73 63 61 6e  x1 index is scan
51d0: 6e 65 64 20 66 72 6f 6d 20 74 6f 70 20 74 6f 20  ned from top to 
51e0: 62 6f 74 74 6f 6d 20 28 6f 72 20 66 72 6f 6d 20  bottom (or from 
51f0: 62 6f 74 74 6f 6d 20 74 6f 20 74 6f 70 20 69 66  bottom to top if
5200: 0a 22 4f 52 44 45 52 20 42 59 20 66 72 75 69 74  ."ORDER BY fruit
5210: 20 44 45 53 43 22 20 69 73 20 75 73 65 64 29 20   DESC" is used) 
5220: 69 6e 20 6f 72 64 65 72 20 74 6f 20 66 69 6e 64  in order to find
5230: 20 74 68 65 20 72 6f 77 69 64 73 20 66 6f 72 20   the rowids for 
5240: 65 61 63 68 20 69 74 65 6d 0a 69 6e 20 6f 72 64  each item.in ord
5250: 65 72 20 62 79 20 66 72 75 69 74 2e 20 20 54 68  er by fruit.  Th
5260: 65 6e 20 66 6f 72 20 65 61 63 68 20 72 6f 77 69  en for each rowi
5270: 64 2c 20 61 20 62 69 6e 61 72 79 20 73 65 61 72  d, a binary sear
5280: 63 68 20 69 73 20 64 6f 6e 65 20 74 6f 20 6c 6f  ch is done to lo
5290: 6f 6b 75 70 0a 61 6e 64 20 6f 75 74 70 75 74 20  okup.and output 
52a0: 74 68 61 74 20 72 6f 77 2e 20 20 49 6e 20 74 68  that row.  In th
52b0: 69 73 20 77 61 79 2c 20 74 68 65 20 6f 75 74 70  is way, the outp
52c0: 75 74 20 61 70 70 65 61 72 73 20 69 6e 20 74 68  ut appears in th
52d0: 65 20 72 65 71 75 65 73 74 65 64 20 6f 72 64 65  e requested orde
52e0: 72 0a 77 69 74 68 6f 75 74 20 74 68 65 20 6e 65  r.without the ne
52f0: 65 64 20 74 6f 20 67 61 74 68 65 72 20 74 68 65  ed to gather the
5300: 20 65 6e 74 69 72 65 20 6f 75 74 70 75 74 20 61   entire output a
5310: 6e 64 20 73 6f 72 74 20 69 74 20 75 73 69 6e 67  nd sort it using
5320: 20 61 20 73 65 70 61 72 61 74 65 20 73 74 65 70   a separate step
5330: 2e 0a 3c 2f 70 3e 0a 0a 3c 70 3e 0a 42 75 74 20  ..</p>..<p>.But 
5340: 64 6f 65 73 20 74 68 69 73 20 72 65 61 6c 6c 79  does this really
5350: 20 73 61 76 65 20 74 69 6d 65 3f 20 20 54 68 65   save time?  The
5360: 20 6e 75 6d 62 65 72 20 6f 66 20 73 74 65 70 73   number of steps
5370: 20 69 6e 20 74 68 65 20 0a 3c 61 20 68 72 65 66   in the .<a href
5380: 3d 22 23 66 69 67 31 36 22 3e 6f 72 69 67 69 6e  ="#fig16">origin
5390: 61 6c 20 69 6e 64 65 78 6c 65 73 73 20 73 6f 72  al indexless sor
53a0: 74 3c 2f 61 3e 20 69 73 20 70 72 6f 70 6f 72 74  t</a> is proport
53b0: 69 6f 6e 61 6c 20 74 6f 20 4e 6c 6f 67 4e 20 73  ional to NlogN s
53c0: 69 6e 63 65 0a 74 68 61 74 20 69 73 20 68 6f 77  ince.that is how
53d0: 20 6d 75 63 68 20 74 69 6d 65 20 69 74 20 74 61   much time it ta
53e0: 6b 65 73 20 74 6f 20 73 6f 72 74 20 4e 20 72 6f  kes to sort N ro
53f0: 77 73 2e 20 20 42 75 74 20 77 68 65 6e 20 77 65  ws.  But when we
5400: 20 75 73 65 20 49 64 78 31 20 61 73 0a 73 68 6f   use Idx1 as.sho
5410: 77 6e 20 68 65 72 65 2c 20 77 65 20 68 61 76 65  wn here, we have
5420: 20 74 6f 20 64 6f 20 4e 20 72 6f 77 69 64 20 6c   to do N rowid l
5430: 6f 6f 6b 75 70 73 20 77 68 69 63 68 20 74 61 6b  ookups which tak
5440: 65 20 6c 6f 67 4e 20 74 69 6d 65 20 65 61 63 68  e logN time each
5450: 2c 20 73 6f 0a 74 68 65 20 74 6f 74 61 6c 20 74  , so.the total t
5460: 69 6d 65 20 6f 66 20 4e 6c 6f 67 4e 20 69 73 20  ime of NlogN is 
5470: 74 68 65 20 73 61 6d 65 21 0a 3c 2f 70 3e 0a 0a  the same!.</p>..
5480: 3c 70 3e 0a 53 51 4c 69 74 65 20 75 73 65 73 20  <p>.SQLite uses 
5490: 61 20 63 6f 73 74 2d 62 61 73 65 64 20 71 75 65  a cost-based que
54a0: 72 79 20 70 6c 61 6e 6e 65 72 2e 20 20 57 68 65  ry planner.  Whe
54b0: 6e 20 74 68 65 72 65 20 61 72 65 20 74 77 6f 20  n there are two 
54c0: 6f 72 20 6d 6f 72 65 20 77 61 79 73 0a 6f 66 20  or more ways.of 
54d0: 73 6f 6c 76 69 6e 67 20 74 68 65 20 73 61 6d 65  solving the same
54e0: 20 71 75 65 72 79 2c 20 53 51 4c 69 74 65 20 74   query, SQLite t
54f0: 72 69 65 73 20 74 6f 20 65 73 74 69 6d 61 74 65  ries to estimate
5500: 20 74 68 65 20 74 6f 74 61 6c 20 61 6d 6f 75 6e   the total amoun
5510: 74 20 6f 66 0a 74 69 6d 65 20 6e 65 65 64 65 64  t of.time needed
5520: 20 74 6f 20 72 75 6e 20 74 68 65 20 71 75 65 72   to run the quer
5530: 79 20 75 73 69 6e 67 20 65 61 63 68 20 70 6c 61  y using each pla
5540: 6e 2c 20 61 6e 64 20 74 68 65 6e 20 75 73 65 73  n, and then uses
5550: 20 74 68 65 20 70 6c 61 6e 20 77 69 74 68 0a 74   the plan with.t
5560: 68 65 20 6c 6f 77 65 73 74 20 65 73 74 69 6d 61  he lowest estima
5570: 74 65 64 20 63 6f 73 74 2e 20 20 41 20 63 6f 73  ted cost.  A cos
5580: 74 20 69 73 20 63 6f 6d 70 75 74 65 64 20 6d 6f  t is computed mo
5590: 73 74 6c 79 20 66 72 6f 6d 20 74 68 65 20 65 73  stly from the es
55a0: 74 69 6d 61 74 65 64 0a 74 69 6d 65 2c 20 61 6e  timated.time, an
55b0: 64 20 73 6f 20 74 68 69 73 20 63 61 73 65 20 63  d so this case c
55c0: 6f 75 6c 64 20 67 6f 20 65 69 74 68 65 72 20 77  ould go either w
55d0: 61 79 20 64 65 70 65 6e 64 69 6e 67 20 6f 6e 20  ay depending on 
55e0: 74 68 65 20 74 61 62 6c 65 20 73 69 7a 65 20 61  the table size a
55f0: 6e 64 0a 77 68 61 74 20 57 48 45 52 45 20 63 6c  nd.what WHERE cl
5600: 61 75 73 65 20 63 6f 6e 73 74 72 61 69 6e 74 73  ause constraints
5610: 20 77 65 72 65 20 61 76 61 69 6c 61 62 6c 65 2c   were available,
5620: 20 61 6e 64 20 73 6f 20 66 6f 72 74 68 2e 20 20   and so forth.  
5630: 42 75 74 20 67 65 6e 65 72 61 6c 6c 79 0a 73 70  But generally.sp
5640: 65 61 6b 69 6e 67 2c 20 74 68 65 20 69 6e 64 65  eaking, the inde
5650: 78 65 64 20 73 6f 72 74 20 77 6f 75 6c 64 20 70  xed sort would p
5660: 72 6f 62 61 62 6c 79 20 62 65 20 63 68 6f 73 65  robably be chose
5670: 6e 2c 20 69 66 20 66 6f 72 20 6e 6f 20 6f 74 68  n, if for no oth
5680: 65 72 0a 72 65 61 73 6f 6e 2c 20 62 65 63 61 75  er.reason, becau
5690: 73 65 20 69 74 20 64 6f 65 73 20 6e 6f 74 20 6e  se it does not n
56a0: 65 65 64 20 74 6f 20 61 63 63 75 6d 75 6c 61 74  eed to accumulat
56b0: 65 20 74 68 65 20 65 6e 74 69 72 65 20 72 65 73  e the entire res
56c0: 75 6c 74 20 73 65 74 20 69 6e 0a 74 65 6d 70 6f  ult set in.tempo
56d0: 72 61 72 79 20 73 74 6f 72 61 67 65 20 62 65 66  rary storage bef
56e0: 6f 72 65 20 73 6f 72 74 69 6e 67 20 61 6e 64 20  ore sorting and 
56f0: 74 68 75 73 20 75 73 65 73 20 6d 75 63 68 20 6c  thus uses much l
5700: 65 73 73 20 74 65 6d 70 6f 72 61 72 79 20 73 74  ess temporary st
5710: 6f 72 61 67 65 2e 0a 3c 2f 70 3e 0a 0a 3c 68 32  orage..</p>..<h2
5720: 3e 20 53 6f 72 74 69 6e 67 20 42 79 20 43 6f 76  > Sorting By Cov
5730: 65 72 69 6e 67 20 49 6e 64 65 78 3c 2f 68 32 3e  ering Index</h2>
5740: 0a 0a 3c 70 3e 0a 49 66 20 61 20 63 6f 76 65 72  ..<p>.If a cover
5750: 69 6e 67 20 69 6e 64 65 78 20 63 61 6e 20 62 65  ing index can be
5760: 20 75 73 65 64 20 66 6f 72 20 61 20 71 75 65 72   used for a quer
5770: 79 2c 20 74 68 65 6e 20 74 68 65 20 6d 75 6c 74  y, then the mult
5780: 69 70 6c 65 20 72 6f 77 69 64 20 6c 6f 6f 6b 75  iple rowid looku
5790: 70 73 0a 63 61 6e 20 62 65 20 61 76 6f 69 64 65  ps.can be avoide
57a0: 64 20 61 6e 64 20 74 68 65 20 63 6f 73 74 20 6f  d and the cost o
57b0: 66 20 74 68 65 20 71 75 65 72 79 20 64 72 6f 70  f the query drop
57c0: 73 20 64 72 61 6d 61 74 69 63 61 6c 6c 79 2e 0a  s dramatically..
57d0: 3c 2f 70 3e 0a 0a 3c 74 63 6c 3e 0a 66 69 67 75  </p>..<tcl>.figu
57e0: 72 65 20 31 39 20 23 66 69 67 31 39 20 6f 62 66  re 19 #fig19 obf
57f0: 72 75 69 74 69 64 78 34 2e 67 69 66 20 7b 53 6f  ruitidx4.gif {So
5800: 72 74 69 6e 67 20 57 69 74 68 20 41 20 43 6f 76  rting With A Cov
5810: 65 72 69 6e 67 20 49 6e 64 65 78 7d 0a 3c 2f 74  ering Index}.</t
5820: 63 6c 3e 0a 0a 3c 70 3e 0a 57 69 74 68 20 61 20  cl>..<p>.With a 
5830: 63 6f 76 65 72 69 6e 67 20 69 6e 64 65 78 2c 20  covering index, 
5840: 53 51 4c 69 74 65 20 63 61 6e 20 73 69 6d 70 6c  SQLite can simpl
5850: 79 20 77 61 6c 6b 20 74 68 65 20 69 6e 64 65 78  y walk the index
5860: 20 66 72 6f 6d 20 6f 6e 65 20 65 6e 64 20 74 6f   from one end to
5870: 20 74 68 65 0a 6f 74 68 65 72 20 61 6e 64 20 64   the.other and d
5880: 65 6c 69 76 65 72 20 74 68 65 20 6f 75 74 70 75  eliver the outpu
5890: 74 20 69 6e 20 74 69 6d 65 20 70 72 6f 70 6f 72  t in time propor
58a0: 74 69 6f 6e 61 6c 20 74 6f 20 4e 20 61 6e 64 20  tional to N and 
58b0: 77 69 74 68 6f 75 74 20 68 61 76 69 6e 67 0a 61  without having.a
58c0: 6c 6c 6f 63 61 74 65 20 61 20 6c 61 72 67 65 20  llocate a large 
58d0: 62 75 66 66 65 72 20 74 6f 20 68 6f 6c 64 20 74  buffer to hold t
58e0: 68 65 20 72 65 73 75 6c 74 20 73 65 74 2e 0a 3c  he result set..<
58f0: 2f 70 3e 0a 0a 3c 68 31 3e 20 53 65 61 72 63 68  /p>..<h1> Search
5900: 69 6e 67 20 41 6e 64 20 53 6f 72 74 69 6e 67 20  ing And Sorting 
5910: 41 74 20 54 68 65 20 53 61 6d 65 20 54 69 6d 65  At The Same Time
5920: 3c 2f 68 31 3e 0a 0a 3c 70 3e 0a 54 68 65 20 70  </h1>..<p>.The p
5930: 72 65 76 69 6f 75 73 20 64 69 73 63 75 73 73 69  revious discussi
5940: 6f 6e 20 68 61 73 20 74 72 65 61 74 65 64 20 73  on has treated s
5950: 65 61 72 63 68 69 6e 67 20 61 6e 64 20 73 6f 72  earching and sor
5960: 74 69 6e 67 20 61 73 20 73 65 70 61 72 61 74 65  ting as separate
5970: 0a 74 6f 70 69 63 73 2e 20 20 42 75 74 20 69 6e  .topics.  But in
5980: 20 70 72 61 63 74 69 63 65 2c 20 69 74 20 69 73   practice, it is
5990: 20 6f 66 74 65 6e 20 74 68 65 20 63 61 73 65 20   often the case 
59a0: 74 68 61 74 20 6f 6e 65 20 77 61 6e 74 73 20 74  that one wants t
59b0: 6f 20 73 65 61 72 63 68 0a 61 6e 64 20 73 6f 72  o search.and sor
59c0: 74 20 61 74 20 74 68 65 20 73 61 6d 65 20 74 69  t at the same ti
59d0: 6d 65 2e 20 20 46 6f 72 74 75 6e 61 74 65 6c 79  me.  Fortunately
59e0: 2c 20 69 74 20 69 73 20 70 6f 73 73 69 62 6c 65  , it is possible
59f0: 20 74 6f 20 64 6f 20 74 68 69 73 0a 75 73 69 6e   to do this.usin
5a00: 67 20 61 20 73 69 6e 67 6c 65 20 69 6e 64 65 78  g a single index
5a10: 2e 0a 3c 2f 70 3e 0a 0a 3c 68 32 3e 20 53 65 61  ..</p>..<h2> Sea
5a20: 72 63 68 69 6e 67 20 41 6e 64 20 53 6f 72 74 69  rching And Sorti
5a30: 6e 67 20 57 69 74 68 20 41 20 4d 75 6c 74 69 2d  ng With A Multi-
5a40: 43 6f 6c 75 6d 6e 20 49 6e 64 65 78 3c 2f 68 32  Column Index</h2
5a50: 3e 0a 0a 3c 70 3e 0a 53 75 70 70 6f 73 65 20 77  >..<p>.Suppose w
5a60: 65 20 77 61 6e 74 20 74 6f 20 66 69 6e 64 20 74  e want to find t
5a70: 68 65 20 70 72 69 63 65 73 20 6f 66 20 61 6c 6c  he prices of all
5a80: 20 6b 69 6e 64 73 20 6f 66 20 6f 72 61 6e 67 65   kinds of orange
5a90: 73 20 73 6f 72 74 65 64 20 69 6e 0a 6f 72 64 65  s sorted in.orde
5aa0: 72 20 6f 66 20 74 68 65 20 73 74 61 74 65 20 77  r of the state w
5ab0: 68 65 72 65 20 74 68 65 79 20 61 72 65 20 67 72  here they are gr
5ac0: 6f 77 6e 2e 20 20 54 68 65 20 71 75 65 72 79 20  own.  The query 
5ad0: 69 73 20 74 68 69 73 3a 0a 3c 2f 70 3e 0a 0a 3c  is this:.</p>..<
5ae0: 74 63 6c 3e 0a 63 6f 64 65 20 7b 53 45 4c 45 43  tcl>.code {SELEC
5af0: 54 20 70 72 69 63 65 20 46 52 4f 4d 20 66 72 75  T price FROM fru
5b00: 69 74 66 6f 72 73 61 6c 65 20 57 48 45 52 45 20  itforsale WHERE 
5b10: 66 72 75 69 74 3d 27 4f 72 61 6e 67 65 27 20 4f  fruit='Orange' O
5b20: 52 44 45 52 20 42 59 20 73 74 61 74 65 7d 0a 3c  RDER BY state}.<
5b30: 2f 74 63 6c 3e 0a 0a 3c 70 3e 0a 54 68 65 20 71  /tcl>..<p>.The q
5b40: 75 65 72 79 20 63 6f 6e 74 61 69 6e 73 20 62 6f  uery contains bo
5b50: 74 68 20 61 20 73 65 61 72 63 68 20 72 65 73 74  th a search rest
5b60: 72 69 63 74 69 6f 6e 20 69 6e 20 74 68 65 20 57  riction in the W
5b70: 48 45 52 45 20 63 6c 61 75 73 65 0a 61 6e 64 20  HERE clause.and 
5b80: 61 20 73 6f 72 74 20 6f 72 64 65 72 20 69 6e 20  a sort order in 
5b90: 74 68 65 20 4f 52 44 45 52 20 42 59 20 63 6c 61  the ORDER BY cla
5ba0: 75 73 65 2e 20 20 42 6f 74 68 20 74 68 65 20 73  use.  Both the s
5bb0: 65 61 72 63 68 20 61 6e 64 20 74 68 65 20 73 6f  earch and the so
5bc0: 72 74 0a 63 61 6e 20 62 65 20 61 63 63 6f 6d 70  rt.can be accomp
5bd0: 6c 69 73 68 65 64 20 61 74 20 74 68 65 20 73 61  lished at the sa
5be0: 6d 65 20 74 69 6d 65 20 75 73 69 6e 67 20 74 68  me time using th
5bf0: 65 20 74 77 6f 2d 63 6f 6c 75 6d 6e 20 69 6e 64  e two-column ind
5c00: 65 78 20 49 64 78 33 2e 0a 3c 2f 70 3e 0a 0a 3c  ex Idx3..</p>..<
5c10: 74 63 6c 3e 0a 66 69 67 75 72 65 20 32 30 20 23  tcl>.figure 20 #
5c20: 66 69 67 32 30 20 66 72 75 69 74 6f 62 73 74 61  fig20 fruitobsta
5c30: 74 65 30 2e 67 69 66 20 7b 53 65 61 72 63 68 20  te0.gif {Search 
5c40: 41 6e 64 20 53 6f 72 74 20 42 79 20 4d 75 6c 74  And Sort By Mult
5c50: 69 2d 43 6f 6c 75 6d 6e 20 49 6e 64 65 78 7d 0a  i-Column Index}.
5c60: 3c 2f 74 63 6c 3e 0a 0a 3c 70 3e 0a 54 68 65 20  </tcl>..<p>.The 
5c70: 71 75 65 72 79 20 64 6f 65 73 20 61 20 62 69 6e  query does a bin
5c80: 61 72 79 20 73 65 61 72 63 68 20 6f 6e 20 74 68  ary search on th
5c90: 65 20 69 6e 64 65 78 20 74 6f 20 66 69 6e 64 20  e index to find 
5ca0: 74 68 65 20 73 75 62 73 65 74 20 6f 66 20 72 6f  the subset of ro
5cb0: 77 73 0a 74 68 61 74 20 68 61 76 65 20 66 72 75  ws.that have fru
5cc0: 69 74 3d 27 4f 72 61 6e 67 65 27 2e 20 20 28 42  it='Orange'.  (B
5cd0: 65 63 61 75 73 65 20 74 68 65 20 66 72 75 69 74  ecause the fruit
5ce0: 20 63 6f 6c 75 6d 6e 20 69 73 20 74 68 65 20 6c   column is the l
5cf0: 65 66 74 2d 6d 6f 73 74 20 63 6f 6c 75 6d 6e 0a  eft-most column.
5d00: 6f 66 20 74 68 65 20 69 6e 64 65 78 20 61 6e 64  of the index and
5d10: 20 74 68 65 20 72 6f 77 73 20 6f 66 20 74 68 65   the rows of the
5d20: 20 69 6e 64 65 78 20 61 72 65 20 69 6e 20 73 6f   index are in so
5d30: 72 74 65 64 20 6f 72 64 65 72 2c 20 61 6c 6c 20  rted order, all 
5d40: 73 75 63 68 20 0a 72 6f 77 73 20 77 69 6c 6c 20  such .rows will 
5d50: 62 65 20 61 64 6a 61 63 65 6e 74 2e 29 20 20 54  be adjacent.)  T
5d60: 68 65 6e 20 69 74 20 73 63 61 6e 73 20 74 68 65  hen it scans the
5d70: 20 6d 61 74 63 68 69 6e 67 20 69 6e 64 65 78 20   matching index 
5d80: 72 6f 77 73 20 66 72 6f 6d 20 74 6f 70 20 74 6f  rows from top to
5d90: 0a 62 6f 74 74 6f 6d 20 74 6f 20 67 65 74 20 74  .bottom to get t
5da0: 68 65 20 72 6f 77 69 64 73 20 66 6f 72 20 74 68  he rowids for th
5db0: 65 20 6f 72 69 67 69 6e 61 6c 20 74 61 62 6c 65  e original table
5dc0: 2c 20 61 6e 64 20 66 6f 72 20 65 61 63 68 20 72  , and for each r
5dd0: 6f 77 69 64 20 64 6f 65 73 0a 61 20 62 69 6e 61  owid does.a bina
5de0: 72 79 20 73 65 61 72 63 68 20 6f 6e 20 74 68 65  ry search on the
5df0: 20 6f 72 69 67 69 6e 61 6c 20 74 61 62 6c 65 20   original table 
5e00: 74 6f 20 66 69 6e 64 20 74 68 65 20 70 72 69 63  to find the pric
5e10: 65 2e 0a 3c 2f 70 3e 0a 0a 3c 70 3e 0a 59 6f 75  e..</p>..<p>.You
5e20: 20 77 69 6c 6c 20 6e 6f 74 69 63 65 20 74 68 61   will notice tha
5e30: 74 20 74 68 65 72 65 20 69 73 20 6e 6f 20 22 73  t there is no "s
5e40: 6f 72 74 22 20 62 6f 78 20 61 6e 79 77 68 65 72  ort" box anywher
5e50: 65 20 69 6e 20 74 68 65 20 61 62 6f 76 65 20 64  e in the above d
5e60: 69 61 67 72 61 6d 2e 0a 54 68 65 20 4f 52 44 45  iagram..The ORDE
5e70: 52 20 42 59 20 63 6c 61 75 73 65 20 6f 66 20 74  R BY clause of t
5e80: 68 65 20 71 75 65 72 79 20 68 61 73 20 62 65 63  he query has bec
5e90: 6f 6d 65 20 61 20 6e 6f 2d 6f 70 2e 20 20 4e 6f  ome a no-op.  No
5ea0: 20 73 6f 72 74 69 6e 67 20 68 61 73 20 74 6f 20   sorting has to 
5eb0: 62 65 0a 64 6f 6e 65 20 68 65 72 65 20 62 65 63  be.done here bec
5ec0: 61 75 73 65 20 74 68 65 20 6f 75 74 70 75 74 20  ause the output 
5ed0: 6f 72 64 65 72 20 69 73 20 62 79 20 74 68 65 20  order is by the 
5ee0: 73 74 61 74 65 20 63 6f 6c 75 6d 6e 20 61 6e 64  state column and
5ef0: 20 74 68 65 20 73 74 61 74 65 0a 63 6f 6c 75 6d   the state.colum
5f00: 6e 20 61 6c 73 6f 20 68 61 70 70 65 6e 73 20 74  n also happens t
5f10: 6f 20 62 65 20 74 68 65 20 66 69 72 73 74 20 63  o be the first c
5f20: 6f 6c 75 6d 6e 20 61 66 74 65 72 20 74 68 65 20  olumn after the 
5f30: 66 72 75 69 74 20 63 6f 6c 75 6d 6e 20 69 6e 20  fruit column in 
5f40: 74 68 65 0a 69 6e 64 65 78 2e 20 20 53 6f 2c 20  the.index.  So, 
5f50: 69 66 20 77 65 20 73 63 61 6e 20 65 6e 74 72 69  if we scan entri
5f60: 65 73 20 6f 66 20 74 68 65 20 69 6e 64 65 78 20  es of the index 
5f70: 74 68 61 74 20 68 61 76 65 20 74 68 65 20 73 61  that have the sa
5f80: 6d 65 20 76 61 6c 75 65 20 66 6f 72 0a 74 68 65  me value for.the
5f90: 20 66 72 75 69 74 20 63 6f 6c 75 6d 6e 20 66 72   fruit column fr
5fa0: 6f 6d 20 74 6f 70 20 74 6f 20 62 6f 74 74 6f 6d  om top to bottom
5fb0: 2c 20 74 68 6f 73 65 20 69 6e 64 65 78 20 65 6e  , those index en
5fc0: 74 72 69 65 73 20 61 72 65 20 67 75 61 72 61 6e  tries are guaran
5fd0: 74 65 65 64 20 74 6f 0a 62 65 20 6f 72 64 65 72  teed to.be order
5fe0: 65 64 20 62 79 20 74 68 65 20 73 74 61 74 65 20  ed by the state 
5ff0: 63 6f 6c 75 6d 6e 2e 0a 3c 2f 70 3e 0a 0a 3c 74  column..</p>..<t
6000: 63 6c 3e 68 64 5f 66 72 61 67 6d 65 6e 74 20 7b  cl>hd_fragment {
6010: 73 72 63 68 73 6f 72 74 63 6f 76 69 64 78 7d 3c  srchsortcovidx}<
6020: 2f 74 63 6c 3e 0a 3c 68 32 3e 20 53 65 61 72 63  /tcl>.<h2> Searc
6030: 68 69 6e 67 20 41 6e 64 20 53 6f 72 74 69 6e 67  hing And Sorting
6040: 20 57 69 74 68 20 41 20 43 6f 76 65 72 69 6e 67   With A Covering
6050: 20 49 6e 64 65 78 3c 2f 68 32 3e 0a 0a 3c 70 3e   Index</h2>..<p>
6060: 0a 41 20 5b 63 6f 76 65 72 69 6e 67 20 69 6e 64  .A [covering ind
6070: 65 78 5d 20 63 61 6e 20 61 6c 73 6f 20 62 65 20  ex] can also be 
6080: 75 73 65 64 20 74 6f 20 73 65 61 72 63 68 20 61  used to search a
6090: 6e 64 20 73 6f 72 74 20 61 74 20 74 68 65 20 73  nd sort at the s
60a0: 61 6d 65 20 74 69 6d 65 2e 0a 43 6f 6e 73 69 64  ame time..Consid
60b0: 65 72 20 74 68 65 20 66 6f 6c 6c 6f 77 69 6e 67  er the following
60c0: 3a 0a 3c 2f 70 3e 0a 0a 3c 74 63 6c 3e 0a 63 6f  :.</p>..<tcl>.co
60d0: 64 65 20 7b 53 45 4c 45 43 54 20 2a 20 46 52 4f  de {SELECT * FRO
60e0: 4d 20 66 72 75 69 74 66 6f 72 73 61 6c 65 20 57  M fruitforsale W
60f0: 48 45 52 45 20 66 72 75 69 74 3d 27 4f 72 61 6e  HERE fruit='Oran
6100: 67 65 27 20 4f 52 44 45 52 20 42 59 20 73 74 61  ge' ORDER BY sta
6110: 74 65 7d 0a 66 69 67 75 72 65 20 32 31 20 23 66  te}.figure 21 #f
6120: 69 67 32 31 20 66 72 75 69 74 6f 62 73 74 61 74  ig21 fruitobstat
6130: 65 2e 67 69 66 20 7b 53 65 61 72 63 68 20 41 6e  e.gif {Search An
6140: 64 20 53 6f 72 74 20 42 79 20 43 6f 76 65 72 69  d Sort By Coveri
6150: 6e 67 20 49 6e 64 65 78 7d 0a 3c 2f 74 63 6c 3e  ng Index}.</tcl>
6160: 0a 0a 3c 70 3e 0a 41 73 20 62 65 66 6f 72 65 2c  ..<p>.As before,
6170: 20 53 51 4c 69 74 65 20 64 6f 65 73 20 73 69 6e   SQLite does sin
6180: 67 6c 65 20 62 69 6e 61 72 79 20 73 65 61 72 63  gle binary searc
6190: 68 0a 66 6f 72 20 74 68 65 20 72 61 6e 67 65 20  h.for the range 
61a0: 6f 66 20 72 6f 77 73 20 69 6e 20 74 68 65 20 63  of rows in the c
61b0: 6f 76 65 72 69 6e 67 0a 69 6e 64 65 78 20 74 68  overing.index th
61c0: 61 74 20 73 61 74 69 73 66 79 20 74 68 65 20 57  at satisfy the W
61d0: 48 45 52 45 20 63 6c 61 75 73 65 2c 20 74 68 65  HERE clause, the
61e0: 20 73 63 61 6e 73 20 74 68 61 74 20 72 61 6e 67   scans that rang
61f0: 65 20 66 72 6f 6d 20 74 6f 70 20 74 6f 20 0a 62  e from top to .b
6200: 6f 74 74 6f 6d 20 74 6f 20 67 65 74 20 74 68 65  ottom to get the
6210: 20 64 65 73 69 72 65 64 20 72 65 73 75 6c 74 73   desired results
6220: 2e 20 20 0a 54 68 65 20 72 6f 77 73 20 74 68 61  .  .The rows tha
6230: 74 20 73 61 74 69 73 66 79 20 74 68 65 20 57 48  t satisfy the WH
6240: 45 52 45 20 63 6c 61 75 73 65 20 61 72 65 20 67  ERE clause are g
6250: 75 61 72 61 6e 74 65 65 64 20 74 6f 20 62 65 20  uaranteed to be 
6260: 61 64 6a 61 63 65 6e 74 0a 73 69 6e 63 65 20 74  adjacent.since t
6270: 68 65 20 57 48 45 52 45 20 63 6c 61 75 73 65 20  he WHERE clause 
6280: 69 73 20 61 6e 20 65 71 75 61 6c 69 74 79 20 63  is an equality c
6290: 6f 6e 73 74 72 61 69 6e 74 20 6f 6e 20 74 68 65  onstraint on the
62a0: 20 6c 65 66 74 2d 6d 6f 73 74 0a 63 6f 6c 75 6d   left-most.colum
62b0: 6e 20 6f 66 20 74 68 65 20 69 6e 64 65 78 2e 20  n of the index. 
62c0: 20 41 6e 64 20 62 79 20 73 63 61 6e 6e 69 6e 67   And by scanning
62d0: 20 74 68 65 20 6d 61 74 63 68 69 6e 67 20 69 6e   the matching in
62e0: 64 65 78 20 72 6f 77 73 20 66 72 6f 6d 0a 74 6f  dex rows from.to
62f0: 70 20 74 6f 20 62 6f 74 74 6f 6d 2c 20 74 68 65  p to bottom, the
6300: 20 6f 75 74 70 75 74 20 69 73 20 67 75 61 72 61   output is guara
6310: 6e 74 65 65 64 20 74 6f 20 62 65 20 6f 72 64 65  nteed to be orde
6320: 72 65 64 20 62 79 20 73 74 61 74 65 20 73 69 6e  red by state sin
6330: 63 65 20 74 68 65 0a 73 74 61 74 65 20 63 6f 6c  ce the.state col
6340: 75 6d 6e 20 69 73 20 74 68 65 20 76 65 72 79 20  umn is the very 
6350: 6e 65 78 74 20 63 6f 6c 75 6d 6e 20 74 6f 20 74  next column to t
6360: 68 65 20 72 69 67 68 74 20 6f 66 20 74 68 65 20  he right of the 
6370: 66 72 75 69 74 20 63 6f 6c 75 6d 6e 2e 0a 41 6e  fruit column..An
6380: 64 20 73 6f 20 74 68 65 20 72 65 73 75 6c 74 69  d so the resulti
6390: 6e 67 20 71 75 65 72 79 20 69 73 20 76 65 72 79  ng query is very
63a0: 20 65 66 66 69 63 69 65 6e 74 2e 0a 3c 2f 70 3e   efficient..</p>
63b0: 0a 0a 3c 70 3e 0a 53 51 4c 69 74 65 20 63 61 6e  ..<p>.SQLite can
63c0: 20 70 75 6c 6c 20 61 20 73 69 6d 69 6c 61 72 20   pull a similar 
63d0: 74 72 69 63 6b 20 66 6f 72 20 61 20 64 65 73 63  trick for a desc
63e0: 65 6e 64 69 6e 67 20 4f 52 44 45 52 20 42 59 3a  ending ORDER BY:
63f0: 0a 3c 2f 70 3e 0a 0a 3c 74 63 6c 3e 0a 63 6f 64  .</p>..<tcl>.cod
6400: 65 20 7b 53 45 4c 45 43 54 20 2a 20 46 52 4f 4d  e {SELECT * FROM
6410: 20 66 72 75 69 74 66 6f 72 73 61 6c 65 20 57 48   fruitforsale WH
6420: 45 52 45 20 66 72 75 69 74 3d 27 4f 72 61 6e 67  ERE fruit='Orang
6430: 65 27 20 4f 52 44 45 52 20 42 59 20 73 74 61 74  e' ORDER BY stat
6440: 65 20 44 45 53 43 7d 0a 3c 2f 74 63 6c 3e 0a 0a  e DESC}.</tcl>..
6450: 3c 70 3e 0a 54 68 65 20 73 61 6d 65 20 62 61 73  <p>.The same bas
6460: 69 63 20 61 6c 67 6f 72 69 74 68 6d 20 69 73 20  ic algorithm is 
6470: 66 6f 6c 6c 6f 77 65 64 2c 20 65 78 63 65 70 74  followed, except
6480: 20 74 68 69 73 20 74 69 6d 65 20 74 68 65 20 6d   this time the m
6490: 61 74 63 68 69 6e 67 20 72 6f 77 73 0a 6f 66 20  atching rows.of 
64a0: 74 68 65 20 69 6e 64 65 78 20 61 72 65 20 73 63  the index are sc
64b0: 61 6e 6e 65 64 20 66 72 6f 6d 20 62 6f 74 74 6f  anned from botto
64c0: 6d 20 74 6f 20 74 6f 70 20 69 6e 73 74 65 61 64  m to top instead
64d0: 20 6f 66 20 66 72 6f 6d 20 74 6f 70 20 74 6f 20   of from top to 
64e0: 62 6f 74 74 6f 6d 2c 0a 73 6f 20 74 68 61 74 20  bottom,.so that 
64f0: 74 68 65 20 73 74 61 74 65 73 20 77 69 6c 6c 20  the states will 
6500: 61 70 70 65 61 72 20 69 6e 20 64 65 73 63 65 6e  appear in descen
6510: 64 69 6e 67 20 6f 72 64 65 72 2e 0a 3c 2f 70 3e  ding order..</p>
6520: 0a 0a 3c 74 63 6c 3e 68 64 5f 66 72 61 67 6d 65  ..<tcl>hd_fragme
6530: 6e 74 20 7b 70 61 72 74 69 61 6c 73 6f 72 74 7d  nt {partialsort}
6540: 20 7b 70 61 72 74 69 61 6c 20 73 6f 72 74 69 6e   {partial sortin
6550: 67 20 62 79 20 69 6e 64 65 78 7d 20 7b 62 6c 6f  g by index} {blo
6560: 63 6b 20 73 6f 72 74 69 6e 67 7d 3c 2f 74 63 6c  ck sorting}</tcl
6570: 3e 0a 3c 68 32 3e 20 50 61 72 74 69 61 6c 20 53  >.<h2> Partial S
6580: 6f 72 74 69 6e 67 20 55 73 69 6e 67 20 41 6e 20  orting Using An 
6590: 49 6e 64 65 78 20 28 61 2e 6b 2e 61 2e 20 42 6c  Index (a.k.a. Bl
65a0: 6f 63 6b 20 53 6f 72 74 69 6e 67 29 3c 2f 68 32  ock Sorting)</h2
65b0: 3e 0a 0a 3c 70 3e 0a 53 6f 6d 65 74 69 6d 65 73  >..<p>.Sometimes
65c0: 20 6f 6e 6c 79 20 70 61 72 74 20 6f 66 20 61 6e   only part of an
65d0: 20 4f 52 44 45 52 20 42 59 20 63 6c 61 75 73 65   ORDER BY clause
65e0: 20 63 61 6e 20 62 65 20 73 61 74 69 73 66 69 65   can be satisfie
65f0: 64 20 75 73 69 6e 67 20 69 6e 64 65 78 65 73 2e  d using indexes.
6600: 0a 43 6f 6e 73 69 64 65 72 2c 20 66 6f 72 20 65  .Consider, for e
6610: 78 61 6d 70 6c 65 2c 20 74 68 65 20 66 6f 6c 6c  xample, the foll
6620: 6f 77 69 6e 67 20 71 75 65 72 79 3a 0a 3c 2f 70  owing query:.</p
6630: 3e 0a 0a 3c 74 63 6c 3e 0a 63 6f 64 65 20 7b 53  >..<tcl>.code {S
6640: 45 4c 45 43 54 20 2a 20 46 52 4f 4d 20 66 72 75  ELECT * FROM fru
6650: 69 74 66 6f 72 73 61 6c 65 20 4f 52 44 45 52 20  itforsale ORDER 
6660: 42 59 20 66 72 75 69 74 2c 20 70 72 69 63 65 7d  BY fruit, price}
6670: 0a 3c 2f 74 63 6c 3e 0a 0a 3c 70 3e 0a 49 66 20  .</tcl>..<p>.If 
6680: 74 68 65 20 63 6f 76 65 72 69 6e 67 20 69 6e 64  the covering ind
6690: 65 78 20 69 73 20 75 73 65 64 20 66 6f 72 20 74  ex is used for t
66a0: 68 65 20 73 63 61 6e 2c 20 74 68 65 20 22 66 72  he scan, the "fr
66b0: 75 69 74 22 20 63 6f 6c 75 6d 6e 20 77 69 6c 6c  uit" column will
66c0: 20 61 70 70 65 61 72 0a 6e 61 74 75 72 61 6c 6c   appear.naturall
66d0: 79 20 69 6e 20 74 68 65 20 63 6f 72 72 65 63 74  y in the correct
66e0: 20 6f 72 64 65 72 2c 20 62 75 74 20 77 68 65 6e   order, but when
66f0: 20 74 68 65 72 65 20 61 72 65 20 74 77 6f 20 6f   there are two o
6700: 72 20 6d 6f 72 65 20 72 6f 77 73 20 77 69 74 68  r more rows with
6710: 0a 74 68 65 20 73 61 6d 65 20 66 72 75 69 74 2c  .the same fruit,
6720: 20 74 68 65 20 70 72 69 63 65 20 6d 69 67 68 74   the price might
6730: 20 62 65 20 6f 75 74 20 6f 66 20 6f 72 64 65 72   be out of order
6740: 2e 20 20 57 68 65 6e 20 74 68 69 73 20 6f 63 63  .  When this occ
6750: 75 72 73 2c 20 53 51 4c 69 74 65 0a 64 6f 65 73  urs, SQLite.does
6760: 20 6d 61 6e 79 20 73 6d 61 6c 6c 20 73 6f 72 74   many small sort
6770: 73 2c 20 6f 6e 65 20 73 6f 72 74 20 66 6f 72 20  s, one sort for 
6780: 65 61 63 68 20 64 69 73 74 69 6e 63 74 20 76 61  each distinct va
6790: 6c 75 65 20 6f 66 20 66 72 75 69 74 2c 20 72 61  lue of fruit, ra
67a0: 74 68 65 72 0a 74 68 61 6e 20 6f 6e 65 20 6c 61  ther.than one la
67b0: 72 67 65 20 73 6f 72 74 2e 20 20 46 69 67 75 72  rge sort.  Figur
67c0: 65 20 32 32 20 62 65 6c 6f 77 20 69 6c 6c 75 73  e 22 below illus
67d0: 74 72 61 74 65 73 20 74 68 65 20 63 6f 6e 63 65  trates the conce
67e0: 70 74 2e 0a 3c 2f 70 3e 0a 0a 3c 74 63 6c 3e 0a  pt..</p>..<tcl>.
67f0: 66 69 67 75 72 65 20 32 32 20 23 66 69 67 32 32  figure 22 #fig22
6800: 20 70 61 72 74 69 61 6c 2d 73 6f 72 74 2e 67 69   partial-sort.gi
6810: 66 20 7b 50 61 72 74 69 61 6c 20 53 6f 72 74 20  f {Partial Sort 
6820: 42 79 20 49 6e 64 65 78 7d 0a 3c 2f 74 63 6c 3e  By Index}.</tcl>
6830: 0a 0a 3c 70 3e 0a 49 6e 20 74 68 65 20 65 78 61  ..<p>.In the exa
6840: 6d 70 6c 65 2c 20 69 6e 73 74 65 61 64 20 6f 66  mple, instead of
6850: 20 61 20 73 69 6e 67 6c 65 20 73 6f 72 74 20 6f   a single sort o
6860: 66 20 37 20 65 6c 65 6d 65 6e 74 73 2c 20 74 68  f 7 elements, th
6870: 65 72 65 0a 61 72 65 20 35 20 73 6f 72 74 73 20  ere.are 5 sorts 
6880: 6f 66 20 6f 6e 65 2d 65 6c 65 6d 65 6e 74 20 65  of one-element e
6890: 61 63 68 20 61 6e 64 20 31 20 73 6f 72 74 20 6f  ach and 1 sort o
68a0: 66 20 32 20 65 6c 65 6d 65 6e 74 73 20 66 6f 72  f 2 elements for
68b0: 20 74 68 65 0a 63 61 73 65 20 6f 66 20 66 72 75   the.case of fru
68c0: 69 74 3d 3d 27 4f 72 61 6e 67 65 27 2e 0a 0a 3c  it=='Orange'...<
68d0: 70 3e 0a 54 68 65 20 61 64 76 61 6e 74 61 67 65  p>.The advantage
68e0: 73 20 6f 66 20 64 6f 69 6e 67 20 6d 61 6e 79 20  s of doing many 
68f0: 73 6d 61 6c 6c 65 72 20 73 6f 72 74 73 20 69 6e  smaller sorts in
6900: 73 74 65 61 64 20 6f 66 20 61 20 73 69 6e 67 6c  stead of a singl
6910: 65 20 6c 61 72 67 65 20 73 6f 72 74 0a 61 72 65  e large sort.are
6920: 3a 0a 3c 6f 6c 3e 0a 3c 6c 69 3e 4d 75 6c 74 69  :.<ol>.<li>Multi
6930: 70 6c 65 20 73 6d 61 6c 6c 20 73 6f 72 74 73 20  ple small sorts 
6940: 63 6f 6c 6c 65 63 74 69 76 65 6c 79 20 75 73 65  collectively use
6950: 20 66 65 77 65 72 20 43 50 55 20 63 79 63 6c 65   fewer CPU cycle
6960: 73 20 74 68 61 6e 20 61 20 73 69 6e 67 6c 65 0a  s than a single.
6970: 20 20 20 20 6c 61 72 67 65 20 73 6f 72 74 2e 0a      large sort..
6980: 3c 6c 69 3e 45 61 63 68 20 73 6d 61 6c 6c 20 73  <li>Each small s
6990: 6f 72 74 20 69 73 20 72 75 6e 20 69 6e 64 65 70  ort is run indep
69a0: 65 6e 64 65 6e 74 6c 79 2c 20 6d 65 61 6e 69 6e  endently, meanin
69b0: 67 20 74 68 61 74 20 6d 75 63 68 20 6c 65 73 73  g that much less
69c0: 20 69 6e 66 6f 72 6d 61 74 69 6f 6e 0a 20 20 20   information.   
69d0: 20 6e 65 65 64 73 20 74 6f 20 62 65 20 6b 65 70   needs to be kep
69e0: 74 20 69 6e 20 74 65 6d 70 6f 72 61 72 79 20 73  t in temporary s
69f0: 74 6f 72 61 67 65 20 61 74 20 61 6e 79 20 6f 6e  torage at any on
6a00: 65 20 74 69 6d 65 2e 0a 3c 6c 69 3e 54 68 6f 73  e time..<li>Thos
6a10: 65 20 63 6f 6c 75 6d 6e 73 20 6f 66 20 74 68 65  e columns of the
6a20: 20 4f 52 44 45 52 20 42 59 20 74 68 61 74 20 61   ORDER BY that a
6a30: 72 65 20 61 6c 72 65 61 64 79 20 69 6e 20 74 68  re already in th
6a40: 65 20 63 6f 72 72 65 63 74 20 6f 72 64 65 72 0a  e correct order.
6a50: 20 20 20 20 64 75 65 20 74 6f 20 69 6e 64 65 78      due to index
6a60: 65 73 20 63 61 6e 20 62 65 20 6f 6d 69 74 74 65  es can be omitte
6a70: 64 20 66 72 6f 6d 20 74 68 65 20 73 6f 72 74 20  d from the sort 
6a80: 6b 65 79 2c 20 66 75 72 74 68 65 72 20 72 65 64  key, further red
6a90: 75 63 69 6e 67 0a 20 20 20 20 73 74 6f 72 61 67  ucing.    storag
6aa0: 65 20 72 65 71 75 69 72 65 6d 65 6e 74 73 20 61  e requirements a
6ab0: 6e 64 20 43 50 55 20 74 69 6d 65 2e 0a 3c 6c 69  nd CPU time..<li
6ac0: 3e 4f 75 74 70 75 74 20 72 6f 77 73 20 63 61 6e  >Output rows can
6ad0: 20 62 65 20 72 65 74 75 72 6e 65 64 20 74 6f 20   be returned to 
6ae0: 74 68 65 20 61 70 70 6c 69 63 61 74 69 6f 6e 20  the application 
6af0: 61 73 20 65 61 63 68 20 73 6d 61 6c 6c 20 73 6f  as each small so
6b00: 72 74 0a 20 20 20 20 63 6f 6d 70 6c 65 74 65 73  rt.    completes
6b10: 2c 20 61 6e 64 20 77 65 6c 6c 20 62 65 66 6f 72  , and well befor
6b20: 65 20 74 68 65 20 74 61 62 6c 65 20 73 63 61 6e  e the table scan
6b30: 20 69 73 20 63 6f 6d 70 6c 65 74 65 2e 0a 3c 6c   is complete..<l
6b40: 69 3e 49 66 20 61 20 4c 49 4d 49 54 20 63 6c 61  i>If a LIMIT cla
6b50: 75 73 65 20 69 73 20 70 72 65 73 65 6e 74 2c 20  use is present, 
6b60: 69 74 20 6d 69 67 68 74 20 62 65 20 70 6f 73 73  it might be poss
6b70: 69 62 6c 65 20 74 6f 20 61 76 6f 69 64 20 73 63  ible to avoid sc
6b80: 61 6e 6e 69 6e 67 0a 20 20 20 20 74 68 65 20 65  anning.    the e
6b90: 6e 74 69 72 65 20 74 61 62 6c 65 2e 0a 3c 2f 6f  ntire table..</o
6ba0: 6c 3e 0a 0a 3c 70 3e 42 65 63 61 75 73 65 20 6f  l>..<p>Because o
6bb0: 66 20 74 68 65 73 65 20 61 64 76 61 6e 74 61 67  f these advantag
6bc0: 65 73 2c 20 53 51 4c 69 74 65 20 61 6c 77 61 79  es, SQLite alway
6bd0: 73 20 74 72 69 65 73 20 74 6f 20 64 6f 20 61 20  s tries to do a 
6be0: 70 61 72 74 69 61 6c 20 73 6f 72 74 20 75 73 69  partial sort usi
6bf0: 6e 67 20 61 6e 0a 69 6e 64 65 78 20 65 76 65 6e  ng an.index even
6c00: 20 69 66 20 61 20 63 6f 6d 70 6c 65 74 65 20 73   if a complete s
6c10: 6f 72 74 20 62 79 20 69 6e 64 65 78 20 69 73 20  ort by index is 
6c20: 6e 6f 74 20 70 6f 73 73 69 62 6c 65 2e 3c 2f 70  not possible.</p
6c30: 3e 0a 0a 3c 68 31 3e 20 57 49 54 48 4f 55 54 20  >..<h1> WITHOUT 
6c40: 52 4f 57 49 44 20 74 61 62 6c 65 73 3c 2f 68 31  ROWID tables</h1
6c50: 3e 0a 0a 3c 70 3e 0a 54 68 65 20 62 61 73 69 63  >..<p>.The basic
6c60: 20 70 72 69 6e 63 69 70 61 6c 73 20 64 65 73 63   principals desc
6c70: 72 69 62 65 64 20 61 62 6f 76 65 20 61 70 70 6c  ribed above appl
6c80: 79 20 74 6f 20 62 6f 74 68 20 6f 72 64 69 6e 61  y to both ordina
6c90: 72 79 20 72 6f 77 69 64 20 74 61 62 6c 65 73 0a  ry rowid tables.
6ca0: 61 6e 64 20 5b 57 49 54 48 4f 55 54 20 52 4f 57  and [WITHOUT ROW
6cb0: 49 44 5d 20 74 61 62 6c 65 73 2e 0a 54 68 65 20  ID] tables..The 
6cc0: 6f 6e 6c 79 20 64 69 66 66 65 72 65 6e 63 65 20  only difference 
6cd0: 69 73 20 74 68 61 74 20 74 68 65 20 72 6f 77 69  is that the rowi
6ce0: 64 20 63 6f 6c 75 6d 6e 20 74 68 61 74 20 73 65  d column that se
6cf0: 72 76 65 73 20 61 73 20 74 68 65 20 6b 65 79 20  rves as the key 
6d00: 66 6f 72 0a 74 61 62 6c 65 73 20 61 6e 64 20 74  for.tables and t
6d10: 68 61 74 20 61 70 70 65 61 72 73 20 61 73 20 74  hat appears as t
6d20: 68 65 20 72 69 67 68 74 2d 6d 6f 73 74 20 74 65  he right-most te
6d30: 72 6d 20 69 6e 20 69 6e 64 65 78 65 73 20 69 73  rm in indexes is
6d40: 20 72 65 70 6c 61 63 65 64 20 62 79 0a 74 68 65   replaced by.the
6d50: 20 50 52 49 4d 41 52 59 20 4b 45 59 2e 0a 3c 2f   PRIMARY KEY..</
6d60: 70 3e 0a                                         p>.