Documentation Source Text

Hex Artifact Content
Login

Artifact 157b8b29a63eead12c7ff62f8fc20a0c3a94741f:


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 74  nning</title>.<t
0020: 63 6c 3e 0a 68 64 5f 6b 65 79 77 6f 72 64 73 20  cl>.hd_keywords 
0030: 7b 69 6e 64 65 78 69 6e 67 7d 20 7b 69 6e 64 65  {indexing} {inde
0040: 78 69 6e 67 20 74 75 74 6f 72 69 61 6c 7d 0a 70  xing tutorial}.p
0050: 72 6f 63 20 66 69 67 75 72 65 20 7b 66 69 67 6e  roc figure {fign
0060: 75 6d 20 74 61 67 20 69 6d 67 20 74 69 74 6c 65  um tag img title
0070: 7d 20 7b 0a 20 20 68 64 5f 70 75 74 73 20 22 3c  } {.  hd_puts "<
0080: 70 3e 3c 63 65 6e 74 65 72 3e 5c 6e 22 0a 20 20  p><center>\n".  
0090: 68 64 5f 70 75 74 73 20 22 3c 69 6d 67 20 73 72  hd_puts "<img sr
00a0: 63 3d 5c 22 69 6d 61 67 65 73 2f 71 70 2f 24 69  c=\"images/qp/$i
00b0: 6d 67 5c 22 20 61 6c 74 3d 5c 22 66 69 67 75 72  mg\" alt=\"figur
00c0: 65 20 24 66 69 67 6e 75 6d 5c 22 3e 3c 62 72 3e  e $fignum\"><br>
00d0: 5c 6e 22 0a 20 20 68 64 5f 70 75 74 73 20 22 46  \n".  hd_puts "F
00e0: 69 67 75 72 65 20 24 66 69 67 6e 75 6d 3a 20 24  igure $fignum: $
00f0: 74 69 74 6c 65 5c 6e 22 0a 20 20 68 64 5f 70 75  title\n".  hd_pu
0100: 74 73 20 22 3c 2f 63 65 6e 74 65 72 3e 3c 2f 70  ts "</center></p
0110: 3e 5c 6e 22 0a 7d 0a 70 72 6f 63 20 63 6f 64 65  >\n".}.proc code
0120: 20 7b 74 78 74 7d 20 7b 0a 20 20 68 64 5f 70 75   {txt} {.  hd_pu
0130: 74 73 20 22 3c 63 65 6e 74 65 72 3e 3c 74 61 62  ts "<center><tab
0140: 6c 65 3e 3c 74 72 3e 3c 74 64 3e 3c 70 72 65 3e  le><tr><td><pre>
0150: 5c 6e 22 0a 20 20 72 65 67 73 75 62 20 7b 5e 5b  \n".  regsub {^[
0160: 20 5c 6e 5d 2a 5c 6e 7d 20 24 74 78 74 20 7b 7d   \n]*\n} $txt {}
0170: 20 74 78 74 0a 20 20 68 64 5f 70 75 74 73 20 5b   txt.  hd_puts [
0180: 73 74 72 69 6e 67 20 74 72 69 6d 72 69 67 68 74  string trimright
0190: 20 24 74 78 74 5d 5c 6e 0a 20 20 68 64 5f 70 75   $txt]\n.  hd_pu
01a0: 74 73 20 22 3c 2f 70 72 65 3e 3c 2f 74 61 62 6c  ts "</pre></tabl
01b0: 65 3e 3c 2f 63 65 6e 74 65 72 3e 5c 6e 22 0a 7d  e></center>\n".}
01c0: 0a 3c 2f 74 63 6c 3e 0a 3c 68 31 20 61 6c 69 67  .</tcl>.<h1 alig
01d0: 6e 3d 22 63 65 6e 74 65 72 22 3e 51 75 65 72 79  n="center">Query
01e0: 20 50 6c 61 6e 6e 69 6e 67 3c 2f 68 31 3e 0a 0a   Planning</h1>..
01f0: 3c 70 3e 0a 54 68 65 20 62 65 73 74 20 66 65 61  <p>.The best fea
0200: 74 75 72 65 20 6f 66 20 53 51 4c 20 28 69 6e 20  ture of SQL (in 
0210: 3c 75 3e 61 6c 6c 3c 2f 75 3e 20 69 74 73 20 69  <u>all</u> its i
0220: 6d 70 6c 65 6d 65 6e 74 61 74 69 6f 6e 73 2c 20  mplementations, 
0230: 6e 6f 74 20 6a 75 73 74 20 53 51 4c 69 74 65 29  not just SQLite)
0240: 0a 69 73 20 74 68 61 74 20 69 74 20 69 73 20 61  .is that it is a
0250: 20 3c 69 3e 64 65 63 6c 61 72 61 74 69 76 65 3c   <i>declarative<
0260: 2f 69 3e 20 6c 61 6e 67 75 61 67 65 2c 20 6e 6f  /i> language, no
0270: 74 20 61 20 3c 69 3e 70 72 6f 63 65 64 75 72 61  t a <i>procedura
0280: 6c 3c 2f 69 3e 0a 6c 61 6e 67 75 61 67 65 2e 20  l</i>.language. 
0290: 20 57 68 65 6e 20 70 72 6f 67 72 61 6d 6d 69 6e   When programmin
02a0: 67 20 69 6e 20 53 51 4c 20 79 6f 75 20 74 65 6c  g in SQL you tel
02b0: 6c 20 74 68 65 20 73 79 73 74 65 6d 20 3c 69 3e  l the system <i>
02c0: 77 68 61 74 3c 2f 69 3e 20 79 6f 75 0a 77 61 6e  what</i> you.wan
02d0: 74 20 74 6f 20 63 6f 6d 70 75 74 65 2c 20 6e 6f  t to compute, no
02e0: 74 20 3c 69 3e 68 6f 77 3c 2f 69 3e 20 74 6f 20  t <i>how</i> to 
02f0: 63 6f 6d 70 75 74 65 20 69 74 2e 20 20 54 68 65  compute it.  The
0300: 20 74 61 73 6b 20 6f 66 20 66 69 67 75 72 69 6e   task of figurin
0310: 67 20 6f 75 74 0a 74 68 65 20 3c 69 3e 68 6f 77  g out.the <i>how
0320: 3c 2f 69 3e 20 69 73 20 64 65 6c 65 67 61 74 65  </i> is delegate
0330: 64 20 74 6f 20 74 68 65 20 3c 69 3e 71 75 65 72  d to the <i>quer
0340: 79 20 70 6c 61 6e 6e 65 72 3c 2f 69 3e 20 73 75  y planner</i> su
0350: 62 73 79 73 74 65 6d 20 77 69 74 68 69 6e 20 0a  bsystem within .
0360: 74 68 65 20 53 51 4c 20 64 61 74 61 62 61 73 65  the SQL database
0370: 20 65 6e 67 69 6e 65 2e 0a 52 65 6c 69 65 76 69   engine..Relievi
0380: 6e 67 20 74 68 65 20 70 72 6f 67 72 61 6d 6d 65  ng the programme
0390: 72 20 66 72 6f 6d 20 74 68 65 20 63 68 6f 72 65  r from the chore
03a0: 20 6f 66 20 64 65 73 69 67 6e 69 6e 67 20 73 70   of designing sp
03b0: 65 63 69 66 69 63 0a 71 75 65 72 79 20 61 6c 67  ecific.query alg
03c0: 6f 72 69 74 68 6d 73 20 72 65 64 75 63 65 73 20  orithms reduces 
03d0: 74 68 65 20 77 6f 72 6b 6c 6f 61 64 20 6f 6e 20  the workload on 
03e0: 74 68 65 20 70 72 6f 67 72 61 6d 6d 65 72 20 61  the programmer a
03f0: 6e 64 20 0a 72 65 64 75 63 65 73 20 74 68 65 20  nd .reduces the 
0400: 6e 75 6d 62 65 72 20 6f 66 20 6f 70 70 6f 72 74  number of opport
0410: 75 6e 69 74 69 65 73 20 66 6f 72 20 74 68 65 0a  unities for the.
0420: 70 72 6f 67 72 61 6d 6d 65 72 20 74 6f 20 6d 61  programmer to ma
0430: 6b 65 20 6d 69 73 74 61 6b 65 73 2e 0a 3c 2f 70  ke mistakes..</p
0440: 3e 0a 0a 3c 70 3e 0a 4d 6f 73 74 20 6f 66 20 74  >..<p>.Most of t
0450: 68 65 20 74 69 6d 65 2c 20 74 68 65 20 71 75 65  he time, the que
0460: 72 79 20 70 6c 61 6e 6e 65 72 20 69 6e 20 53 51  ry planner in SQ
0470: 4c 69 74 65 20 64 6f 65 73 20 61 20 67 6f 6f 64  Lite does a good
0480: 20 6a 6f 62 20 6f 6e 20 69 74 73 0a 6f 77 6e 20   job on its.own 
0490: 61 6e 64 20 77 69 74 68 6f 75 74 20 6f 75 74 73  and without outs
04a0: 69 64 65 20 68 65 6c 70 2e 0a 48 6f 77 65 76 65  ide help..Howeve
04b0: 72 2c 20 74 68 65 20 71 75 65 72 79 20 70 6c 61  r, the query pla
04c0: 6e 6e 65 72 20 6e 65 65 64 73 20 69 6e 64 69 63  nner needs indic
04d0: 65 73 20 74 6f 0a 77 6f 72 6b 20 77 69 74 68 20  es to.work with 
04e0: 61 6e 64 20 69 74 20 75 73 75 61 6c 6c 79 20 66  and it usually f
04f0: 61 6c 6c 73 20 74 6f 20 74 68 65 20 70 72 6f 67  alls to the prog
0500: 72 61 6d 6d 65 72 20 74 6f 20 61 64 64 20 69 6e  rammer to add in
0510: 64 69 63 65 73 20 74 6f 20 74 68 65 0a 73 63 68  dices to the.sch
0520: 65 6d 61 20 74 68 61 74 20 61 72 65 20 73 75 66  ema that are suf
0530: 66 69 63 69 65 6e 74 20 66 6f 72 20 74 68 65 20  ficient for the 
0540: 71 75 65 72 79 20 70 6c 61 6e 6e 65 72 20 74 6f  query planner to
0550: 20 61 63 63 6f 6d 70 6c 69 73 68 20 69 74 73 20   accomplish its 
0560: 74 61 73 6b 2e 0a 3c 2f 70 3e 0a 0a 3c 70 3e 0a  task..</p>..<p>.
0570: 54 68 69 73 20 64 6f 63 75 6d 65 6e 74 20 69 73  This document is
0580: 20 69 6e 74 65 6e 64 65 64 20 74 6f 20 70 72 6f   intended to pro
0590: 76 69 64 65 20 70 72 6f 67 72 61 6d 6d 65 72 73  vide programmers
05a0: 20 77 68 6f 20 61 72 65 20 6e 65 77 20 74 6f 20   who are new to 
05b0: 53 51 4c 0a 77 69 74 68 20 62 61 63 6b 67 72 6f  SQL.with backgro
05c0: 75 6e 64 20 69 6e 66 6f 72 6d 61 74 69 6f 6e 20  und information 
05d0: 74 6f 20 68 65 6c 70 20 74 68 65 6d 20 75 6e 64  to help them und
05e0: 65 72 73 74 61 6e 64 0a 77 68 61 74 20 69 73 20  erstand.what is 
05f0: 67 6f 69 6e 67 20 6f 6e 20 62 65 68 69 6e 64 20  going on behind 
0600: 74 68 65 20 73 63 65 6e 65 73 20 77 69 74 68 20  the scenes with 
0610: 53 51 4c 69 74 65 2c 20 77 68 69 63 68 20 69 6e  SQLite, which in
0620: 20 74 75 72 6e 20 73 68 6f 75 6c 64 20 6d 61 6b   turn should mak
0630: 65 0a 69 74 20 65 61 73 69 65 72 20 66 6f 72 20  e.it easier for 
0640: 70 72 6f 67 72 61 6d 6d 65 72 73 20 74 6f 20 63  programmers to c
0650: 72 65 61 74 65 20 74 68 65 20 69 6e 64 69 63 65  reate the indice
0660: 73 20 74 68 61 74 20 77 69 6c 6c 20 68 65 6c 70  s that will help
0670: 20 74 68 65 20 53 51 4c 69 74 65 0a 71 75 65 72   the SQLite.quer
0680: 79 20 70 6c 61 6e 6e 65 72 20 74 6f 20 70 69 63  y planner to pic
0690: 6b 20 74 68 65 20 62 65 73 74 20 70 6c 61 6e 73  k the best plans
06a0: 2e 0a 3c 2f 70 3e 0a 0a 3c 74 63 6c 3e 68 64 5f  ..</p>..<tcl>hd_
06b0: 66 72 61 67 6d 65 6e 74 20 73 65 61 72 63 68 69  fragment searchi
06c0: 6e 67 20 73 74 72 61 74 65 67 69 65 73 3c 2f 74  ng strategies</t
06d0: 63 6c 3e 0a 3c 68 32 3e 31 2e 30 20 53 65 61 72  cl>.<h2>1.0 Sear
06e0: 63 68 69 6e 67 3c 2f 68 32 3e 0a 0a 3c 68 33 3e  ching</h2>..<h3>
06f0: 31 2e 31 20 54 61 62 6c 65 73 20 57 69 74 68 6f  1.1 Tables Witho
0700: 75 74 20 49 6e 64 69 63 65 73 3c 2f 68 33 3e 0a  ut Indices</h3>.
0710: 0a 3c 70 3e 0a 45 76 65 72 79 20 74 61 62 6c 65  .<p>.Every table
0720: 20 69 6e 20 53 51 4c 69 74 65 20 63 6f 6e 73 69   in SQLite consi
0730: 73 74 73 20 6f 66 20 7a 65 72 6f 20 6f 72 20 6d  sts of zero or m
0740: 6f 72 65 20 72 6f 77 73 20 77 69 74 68 20 61 20  ore rows with a 
0750: 75 6e 69 71 75 65 20 69 6e 74 65 67 65 72 0a 6b  unique integer.k
0760: 65 79 20 28 74 68 65 20 5b 72 6f 77 69 64 5d 20  ey (the [rowid] 
0770: 6f 72 20 5b 49 4e 54 45 47 45 52 20 50 52 49 4d  or [INTEGER PRIM
0780: 41 52 59 20 4b 45 59 5d 29 20 66 6f 6c 6c 6f 77  ARY KEY]) follow
0790: 65 64 20 62 79 20 63 6f 6e 74 65 6e 74 2e 20 20  ed by content.  
07a0: 54 68 65 20 72 6f 77 73 0a 61 72 65 20 6c 6f 67  The rows.are log
07b0: 69 63 61 6c 6c 79 20 73 74 6f 72 65 64 20 69 6e  ically stored in
07c0: 20 6f 72 64 65 72 20 6f 66 20 69 6e 63 72 65 61   order of increa
07d0: 73 69 6e 67 20 72 6f 77 69 64 2e 20 20 41 73 20  sing rowid.  As 
07e0: 61 6e 20 65 78 61 6d 70 6c 65 2c 20 74 68 69 73  an example, this
07f0: 0a 61 72 74 69 63 6c 65 20 75 73 65 73 20 61 20  .article uses a 
0800: 74 61 62 6c 65 20 6e 61 6d 65 64 20 22 46 72 75  table named "Fru
0810: 69 74 73 46 6f 72 53 61 6c 65 22 20 77 68 69 63  itsForSale" whic
0820: 68 20 72 65 6c 61 74 65 73 20 76 61 72 69 6f 75  h relates variou
0830: 73 20 66 72 75 69 74 73 20 0a 74 6f 20 74 68 65  s fruits .to the
0840: 20 73 74 61 74 65 0a 77 68 65 72 65 20 74 68 65   state.where the
0850: 79 20 61 72 65 20 67 72 6f 77 6e 20 61 6e 64 20  y are grown and 
0860: 74 68 65 69 72 20 75 6e 69 74 20 70 72 69 63 65  their unit price
0870: 20 61 74 20 6d 61 72 6b 65 74 2e 20 20 54 68 65   at market.  The
0880: 20 73 63 68 65 6d 61 20 69 73 20 74 68 69 73 3a   schema is this:
0890: 0a 3c 2f 70 3e 0a 0a 3c 74 63 6c 3e 63 6f 64 65  .</p>..<tcl>code
08a0: 20 7b 0a 43 52 45 41 54 45 20 54 41 42 4c 45 20   {.CREATE TABLE 
08b0: 46 72 75 69 74 73 46 6f 72 53 61 6c 65 28 0a 20  FruitsForSale(. 
08c0: 20 46 72 75 69 74 20 54 45 58 54 2c 0a 20 20 53   Fruit TEXT,.  S
08d0: 74 61 74 65 20 54 45 58 54 2c 0a 20 20 50 72 69  tate TEXT,.  Pri
08e0: 63 65 20 52 45 41 4c 0a 29 3b 0a 7d 3c 2f 74 63  ce REAL.);.}</tc
08f0: 6c 3e 0a 0a 3c 70 3e 0a 57 69 74 68 20 73 6f 6d  l>..<p>.With som
0900: 65 20 28 61 72 62 69 74 72 61 72 79 29 20 64 61  e (arbitrary) da
0910: 74 61 2c 20 73 75 63 68 20 61 20 74 61 62 6c 65  ta, such a table
0920: 20 6d 69 67 68 74 20 62 65 20 6c 6f 67 69 63 61   might be logica
0930: 6c 6c 79 20 73 74 6f 72 65 64 20 6f 6e 20 64 69  lly stored on di
0940: 73 6b 0a 61 73 20 73 68 6f 77 6e 20 69 6e 20 66  sk.as shown in f
0950: 69 67 75 72 65 20 31 3a 0a 3c 2f 70 3e 0a 0a 3c  igure 1:.</p>..<
0960: 74 63 6c 3e 66 69 67 75 72 65 20 31 20 23 66 69  tcl>figure 1 #fi
0970: 67 31 20 74 61 62 2e 67 69 66 20 7b 4c 6f 67 69  g1 tab.gif {Logi
0980: 63 61 6c 20 4c 61 79 6f 75 74 20 4f 66 20 54 61  cal Layout Of Ta
0990: 62 6c 65 20 22 46 72 75 69 74 73 46 6f 72 53 61  ble "FruitsForSa
09a0: 6c 65 22 7d 3c 2f 74 63 6c 3e 0a 0a 3c 70 3e 0a  le"}</tcl>..<p>.
09b0: 54 68 65 20 6b 65 79 20 66 65 61 74 75 72 65 73  The key features
09c0: 20 74 6f 20 6e 6f 74 69 63 65 20 69 6e 20 74 68   to notice in th
09d0: 69 73 20 65 78 61 6d 70 6c 65 20 69 73 20 74 68  is example is th
09e0: 61 74 20 74 68 65 20 72 6f 77 69 64 73 20 61 72  at the rowids ar
09f0: 65 20 6e 6f 74 0a 63 6f 6e 73 65 63 75 74 69 76  e not.consecutiv
0a00: 65 20 62 75 74 20 74 68 65 79 20 61 72 65 20 6f  e but they are o
0a10: 72 64 65 72 65 64 2e 20 20 53 51 4c 69 74 65 20  rdered.  SQLite 
0a20: 75 73 75 61 6c 6c 79 20 63 72 65 61 74 65 73 20  usually creates 
0a30: 72 6f 77 69 64 73 20 62 65 67 69 6e 6e 69 6e 67  rowids beginning
0a40: 0a 77 69 74 68 20 6f 6e 65 20 61 6e 64 20 69 6e  .with one and in
0a50: 63 72 65 61 73 69 6e 67 20 62 79 20 6f 6e 65 20  creasing by one 
0a60: 77 69 74 68 20 65 61 63 68 20 61 64 64 65 64 20  with each added 
0a70: 72 6f 77 2e 20 20 42 75 74 20 69 66 20 72 6f 77  row.  But if row
0a80: 73 20 61 72 65 20 0a 64 65 6c 65 74 65 64 2c 20  s are .deleted, 
0a90: 67 61 70 73 20 63 61 6e 20 61 70 70 65 61 72 20  gaps can appear 
0aa0: 69 6e 20 74 68 65 20 73 65 71 75 65 6e 63 65 2e  in the sequence.
0ab0: 20 20 41 6e 64 20 74 68 65 20 61 70 70 6c 69 63    And the applic
0ac0: 61 74 69 6f 6e 20 63 61 6e 20 63 6f 6e 74 72 6f  ation can contro
0ad0: 6c 0a 74 68 65 20 72 6f 77 69 64 20 61 73 73 69  l.the rowid assi
0ae0: 67 6e 65 64 20 69 66 20 64 65 73 69 72 65 64 2c  gned if desired,
0af0: 20 73 6f 20 74 68 61 74 20 72 6f 77 73 20 61 72   so that rows ar
0b00: 65 20 6e 6f 74 20 6e 65 63 65 73 73 61 72 69 6c  e not necessaril
0b10: 79 20 69 6e 73 65 72 74 65 64 20 0a 61 74 20 74  y inserted .at t
0b20: 68 65 20 62 6f 74 74 6f 6d 2e 20 20 42 75 74 20  he bottom.  But 
0b30: 72 65 67 61 72 64 6c 65 73 73 20 6f 66 20 77 68  regardless of wh
0b40: 61 74 20 68 61 70 70 65 6e 73 2c 20 74 68 65 20  at happens, the 
0b50: 72 6f 77 69 64 73 20 61 72 65 20 61 6c 77 61 79  rowids are alway
0b60: 73 20 0a 75 6e 69 71 75 65 20 61 6e 64 20 69 6e  s .unique and in
0b70: 20 73 74 72 69 63 74 6c 79 20 61 73 63 65 6e 64   strictly ascend
0b80: 69 6e 67 20 6f 72 64 65 72 2e 0a 3c 2f 70 3e 0a  ing order..</p>.
0b90: 0a 3c 70 3e 0a 4e 6f 77 20 73 75 70 70 6f 73 65  .<p>.Now suppose
0ba0: 20 79 6f 75 20 77 61 6e 74 20 74 6f 20 6c 6f 6f   you want to loo
0bb0: 6b 20 75 70 20 74 68 65 20 70 72 69 63 65 20 6f  k up the price o
0bc0: 66 20 70 65 61 63 68 65 73 2e 20 20 54 68 65 20  f peaches.  The 
0bd0: 71 75 65 72 79 20 77 6f 75 6c 64 0a 62 65 20 61  query would.be a
0be0: 73 20 66 6f 6c 6c 6f 77 73 3a 0a 3c 2f 70 3e 0a  s follows:.</p>.
0bf0: 0a 3c 74 63 6c 3e 63 6f 64 65 20 7b 0a 53 45 4c  .<tcl>code {.SEL
0c00: 45 43 54 20 70 72 69 63 65 20 46 52 4f 4d 20 66  ECT price FROM f
0c10: 72 75 69 74 73 66 6f 72 73 61 6c 65 20 57 48 45  ruitsforsale WHE
0c20: 52 45 20 66 72 75 69 74 3d 27 50 65 61 63 68 27  RE fruit='Peach'
0c30: 3b 0a 7d 3c 2f 74 63 6c 3e 0a 0a 3c 70 3e 0a 49  ;.}</tcl>..<p>.I
0c40: 6e 20 6f 72 64 65 72 20 74 6f 20 73 61 74 69 73  n order to satis
0c50: 66 79 20 74 68 69 73 20 71 75 65 72 79 2c 20 53  fy this query, S
0c60: 51 4c 69 74 65 20 68 61 73 20 74 6f 20 72 65 61  QLite has to rea
0c70: 64 20 65 76 65 72 79 20 72 6f 77 20 6f 75 74 20  d every row out 
0c80: 6f 66 20 74 68 65 0a 74 61 62 6c 65 2c 20 63 68  of the.table, ch
0c90: 65 63 6b 20 74 6f 20 73 65 65 20 69 66 20 74 68  eck to see if th
0ca0: 65 20 22 66 72 75 69 74 22 20 63 6f 6c 75 6d 6e  e "fruit" column
0cb0: 20 68 61 73 20 74 68 65 20 76 61 6c 75 65 20 6f   has the value o
0cc0: 66 20 22 50 65 61 63 68 22 20 61 6e 64 20 69 66  f "Peach" and if
0cd0: 0a 73 6f 2c 20 6f 75 74 70 75 74 20 74 68 65 20  .so, output the 
0ce0: 22 70 72 69 63 65 22 20 63 6f 6c 75 6d 6e 20 66  "price" column f
0cf0: 72 6f 6d 20 74 68 61 74 20 72 6f 77 2e 20 20 54  rom that row.  T
0d00: 68 65 20 70 72 6f 63 65 73 73 20 69 73 20 69 6c  he process is il
0d10: 6c 75 73 74 72 61 74 65 64 0a 62 79 20 3c 61 20  lustrated.by <a 
0d20: 68 72 65 66 3d 22 23 66 69 67 32 22 3e 66 69 67  href="#fig2">fig
0d30: 75 72 65 20 32 3c 2f 61 3e 20 62 65 6c 6f 77 2e  ure 2</a> below.
0d40: 0a 54 68 69 73 20 69 73 20 63 61 6c 6c 65 64 20  .This is called 
0d50: 61 20 3c 69 3e 66 75 6c 6c 20 74 61 62 6c 65 20  a <i>full table 
0d60: 73 63 61 6e 3c 2f 69 3e 20 73 69 6e 63 65 20 74  scan</i> since t
0d70: 68 65 20 65 6e 74 69 72 65 20 63 6f 6e 74 65 6e  he entire conten
0d80: 74 20 6f 66 20 74 68 65 0a 74 61 62 6c 65 20 6d  t of the.table m
0d90: 75 73 74 20 62 65 20 72 65 61 64 20 61 6e 64 20  ust be read and 
0da0: 65 78 61 6d 69 6e 65 64 20 69 6e 20 6f 72 64 65  examined in orde
0db0: 72 20 74 6f 20 66 69 6e 64 20 74 68 65 20 6f 6e  r to find the on
0dc0: 65 20 72 6f 77 20 6f 66 20 69 6e 74 65 72 65 73  e row of interes
0dd0: 74 2e 0a 57 69 74 68 20 61 20 74 61 62 6c 65 20  t..With a table 
0de0: 6f 66 20 6f 6e 6c 79 20 37 20 72 6f 77 73 2c 20  of only 7 rows, 
0df0: 74 68 69 73 20 69 73 20 6e 6f 74 20 61 20 62 69  this is not a bi
0e00: 67 20 64 65 61 6c 2c 20 62 75 74 20 69 66 20 79  g deal, but if y
0e10: 6f 75 72 20 74 61 62 6c 65 0a 63 6f 6e 74 61 69  our table.contai
0e20: 6e 65 64 20 37 20 6d 69 6c 6c 69 6f 6e 20 72 6f  ned 7 million ro
0e30: 77 73 2c 20 61 20 66 75 6c 6c 20 74 61 62 6c 65  ws, a full table
0e40: 20 73 63 61 6e 20 6d 69 67 68 74 20 72 65 61 64   scan might read
0e50: 20 6d 65 67 61 62 79 74 65 73 20 6f 66 20 63 6f   megabytes of co
0e60: 6e 74 65 6e 74 20 69 6e 20 6f 72 64 65 72 20 74  ntent in order t
0e70: 6f 20 66 69 6e 64 20 61 20 73 69 6e 67 6c 65 20  o find a single 
0e80: 38 2d 62 79 74 65 20 6e 75 6d 62 65 72 2e 20 20  8-byte number.  
0e90: 46 6f 72 20 74 68 61 74 20 72 65 61 73 6f 6e 2c  For that reason,
0ea0: 20 6f 6e 65 20 6e 6f 72 6d 61 6c 6c 79 0a 74 72   one normally.tr
0eb0: 69 65 73 20 74 6f 20 61 76 6f 69 64 20 66 75 6c  ies to avoid ful
0ec0: 6c 20 74 61 62 6c 65 20 73 63 61 6e 73 2e 0a 3c  l table scans..<
0ed0: 2f 70 3e 0a 0a 3c 74 63 6c 3e 66 69 67 75 72 65  /p>..<tcl>figure
0ee0: 20 32 20 23 66 69 67 32 20 66 75 6c 6c 73 63 61   2 #fig2 fullsca
0ef0: 6e 2e 67 69 66 20 7b 46 75 6c 6c 20 54 61 62 6c  n.gif {Full Tabl
0f00: 65 20 53 63 61 6e 7d 3c 2f 74 63 6c 3e 0a 0a 3c  e Scan}</tcl>..<
0f10: 68 33 3e 31 2e 32 20 4c 6f 6f 6b 75 70 20 42 79  h3>1.2 Lookup By
0f20: 20 52 6f 77 69 64 3c 2f 68 33 3e 0a 0a 3c 70 3e   Rowid</h3>..<p>
0f30: 0a 4f 6e 65 20 74 65 63 68 6e 69 71 75 65 20 66  .One technique f
0f40: 6f 72 20 61 76 6f 69 64 69 6e 67 20 61 20 66 75  or avoiding a fu
0f50: 6c 6c 20 74 61 62 6c 65 20 73 63 61 6e 20 69 73  ll table scan is
0f60: 20 74 6f 20 64 6f 20 6c 6f 6f 6b 75 70 73 20 62   to do lookups b
0f70: 79 0a 72 6f 77 69 64 20 28 6f 72 20 62 79 20 74  y.rowid (or by t
0f80: 68 65 20 65 71 75 69 76 61 6c 65 6e 74 20 49 4e  he equivalent IN
0f90: 54 45 47 45 52 20 50 52 49 4d 41 52 59 20 4b 45  TEGER PRIMARY KE
0fa0: 59 29 2e 20 20 20 54 6f 20 6c 6f 6f 6b 75 70 20  Y).   To lookup 
0fb0: 74 68 65 0a 70 72 69 63 65 20 6f 66 20 70 65 61  the.price of pea
0fc0: 63 68 65 73 2c 20 6f 6e 65 20 77 6f 75 6c 64 20  ches, one would 
0fd0: 71 75 65 72 79 20 66 6f 72 20 74 68 65 20 65 6e  query for the en
0fe0: 74 72 79 20 77 69 74 68 20 61 20 72 6f 77 69 64  try with a rowid
0ff0: 20 6f 66 20 34 3a 0a 3c 2f 70 3e 0a 0a 3c 74 63   of 4:.</p>..<tc
1000: 6c 3e 63 6f 64 65 20 7b 0a 53 45 4c 45 43 54 20  l>code {.SELECT 
1010: 70 72 69 63 65 20 46 52 4f 4d 20 66 72 75 69 74  price FROM fruit
1020: 73 66 6f 72 73 61 6c 65 20 57 48 45 52 45 20 72  sforsale WHERE r
1030: 6f 77 69 64 3d 34 3b 0a 7d 3c 2f 74 63 6c 3e 0a  owid=4;.}</tcl>.
1040: 0a 3c 70 3e 0a 53 69 6e 63 65 20 74 68 65 20 69  .<p>.Since the i
1050: 6e 66 6f 72 6d 61 74 69 6f 6e 20 69 73 20 73 74  nformation is st
1060: 6f 72 65 64 20 69 6e 20 74 68 65 20 74 61 62 6c  ored in the tabl
1070: 65 20 69 6e 20 72 6f 77 69 64 20 6f 72 64 65 72  e in rowid order
1080: 2c 20 53 51 4c 69 74 65 0a 63 61 6e 20 66 69 6e  , SQLite.can fin
1090: 64 20 74 68 65 20 63 6f 72 72 65 63 74 20 72 6f  d the correct ro
10a0: 77 20 75 73 69 6e 67 20 64 6f 69 6e 67 20 61 20  w using doing a 
10b0: 62 69 6e 61 72 79 20 73 65 61 72 63 68 20 6f 6e  binary search on
10c0: 20 74 68 65 20 72 6f 77 69 64 2e 0a 49 66 20 74   the rowid..If t
10d0: 68 65 20 74 61 62 6c 65 20 63 6f 6e 74 61 69 6e  he table contain
10e0: 73 20 4e 20 65 6c 65 6d 65 6e 74 2c 20 74 68 65  s N element, the
10f0: 20 74 69 6d 65 20 72 65 71 75 69 72 65 64 20 74   time required t
1100: 6f 20 6c 6f 6f 6b 20 75 70 20 74 68 65 0a 64 65  o look up the.de
1110: 73 69 72 65 64 20 72 6f 77 20 69 73 20 70 72 6f  sired row is pro
1120: 70 6f 72 74 69 6f 6e 61 6c 20 74 6f 20 6c 6f 67  portional to log
1130: 4e 20 72 61 74 68 65 72 20 74 68 61 6e 20 62 65  N rather than be
1140: 69 6e 67 20 70 72 6f 70 6f 72 74 69 6f 6e 61 6c  ing proportional
1150: 0a 74 6f 20 4e 20 61 73 20 69 6e 20 61 20 66 75  .to N as in a fu
1160: 6c 6c 20 74 61 62 6c 65 20 73 63 61 6e 2e 20 20  ll table scan.  
1170: 49 66 20 74 68 65 20 74 61 62 6c 65 20 63 6f 6e  If the table con
1180: 74 61 69 6e 73 20 31 30 20 6d 69 6c 6c 69 6f 6e  tains 10 million
1190: 20 65 6c 65 6d 65 6e 74 73 2c 0a 74 68 61 74 20   elements,.that 
11a0: 6d 65 61 6e 73 20 74 68 65 20 71 75 65 72 79 20  means the query 
11b0: 77 69 6c 6c 20 62 65 20 6f 6e 20 74 68 65 20 6f  will be on the o
11c0: 72 64 65 72 20 6f 66 20 4e 2f 6c 6f 67 4e 20 6f  rder of N/logN o
11d0: 72 20 61 62 6f 75 74 20 31 20 6d 69 6c 6c 69 6f  r about 1 millio
11e0: 6e 0a 74 69 6d 65 73 20 66 61 73 74 65 72 21 0a  n.times faster!.
11f0: 3c 2f 70 3e 0a 0a 3c 74 63 6c 3e 66 69 67 75 72  </p>..<tcl>figur
1200: 65 20 33 20 23 66 69 67 33 20 72 6f 77 69 64 6c  e 3 #fig3 rowidl
1210: 75 2e 67 69 66 20 7b 4c 6f 6f 6b 75 70 20 42 79  u.gif {Lookup By
1220: 20 52 6f 77 69 64 7d 3c 2f 74 63 6c 3e 0a 0a 3c   Rowid}</tcl>..<
1230: 68 33 3e 31 2e 33 20 4c 6f 6f 6b 75 70 20 42 79  h3>1.3 Lookup By
1240: 20 49 6e 64 65 78 3c 2f 68 33 3e 0a 3c 70 3e 0a   Index</h3>.<p>.
1250: 54 68 65 20 70 72 6f 62 6c 65 6d 20 77 69 74 68  The problem with
1260: 20 6c 6f 6f 6b 69 6e 67 20 75 70 20 69 6e 66 6f   looking up info
1270: 72 6d 61 74 69 6f 6e 20 62 79 20 72 6f 77 69 64  rmation by rowid
1280: 20 69 73 20 74 68 61 74 20 79 6f 75 20 70 72 6f   is that you pro
1290: 62 61 62 6c 79 0a 64 6f 20 6e 6f 74 20 63 61 72  bably.do not car
12a0: 65 20 77 68 61 74 20 74 68 65 20 70 72 69 63 65  e what the price
12b0: 20 6f 66 20 22 69 74 65 6d 20 34 22 20 69 73 20   of "item 4" is 
12c0: 2d 20 79 6f 75 20 77 61 6e 74 20 74 6f 20 6b 6e  - you want to kn
12d0: 6f 77 20 74 68 65 20 70 72 69 63 65 0a 6f 66 20  ow the price.of 
12e0: 70 65 61 63 68 65 73 2e 20 20 41 6e 64 20 73 6f  peaches.  And so
12f0: 20 61 20 72 6f 77 69 64 20 6c 6f 6f 6b 75 70 20   a rowid lookup 
1300: 69 73 20 6e 6f 74 20 68 65 6c 70 66 75 6c 2e 0a  is not helpful..
1310: 3c 2f 70 3e 0a 0a 3c 70 3e 0a 54 6f 20 6d 61 6b  </p>..<p>.To mak
1320: 65 20 74 68 65 20 6f 72 69 67 69 6e 61 6c 20 71  e the original q
1330: 75 65 72 79 20 6d 6f 72 65 20 65 66 66 69 63 69  uery more effici
1340: 65 6e 74 2c 20 77 65 20 63 61 6e 20 61 64 64 20  ent, we can add 
1350: 61 6e 20 69 6e 64 65 78 20 6f 6e 20 74 68 65 0a  an index on the.
1360: 22 66 72 75 69 74 22 20 63 6f 6c 75 6d 6e 20 6f  "fruit" column o
1370: 66 20 74 68 65 20 22 66 72 75 69 74 73 66 6f 72  f the "fruitsfor
1380: 73 61 6c 65 22 20 74 61 62 6c 65 20 6c 69 6b 65  sale" table like
1390: 20 74 68 69 73 3a 0a 3c 2f 70 3e 0a 0a 3c 74 63   this:.</p>..<tc
13a0: 6c 3e 63 6f 64 65 20 7b 0a 43 52 45 41 54 45 20  l>code {.CREATE 
13b0: 49 4e 44 45 58 20 69 64 78 31 20 4f 4e 20 66 72  INDEX idx1 ON fr
13c0: 75 69 74 73 66 6f 72 73 61 6c 65 28 66 72 75 69  uitsforsale(frui
13d0: 74 29 3b 0a 7d 3c 2f 74 63 6c 3e 0a 0a 3c 70 3e  t);.}</tcl>..<p>
13e0: 0a 41 6e 20 69 6e 64 65 78 20 69 73 20 61 6e 6f  .An index is ano
13f0: 74 68 65 72 20 74 61 62 6c 65 20 73 69 6d 69 6c  ther table simil
1400: 61 72 20 74 6f 20 74 68 65 20 6f 72 69 67 69 6e  ar to the origin
1410: 61 6c 20 22 66 72 75 69 74 73 66 6f 72 73 61 6c  al "fruitsforsal
1420: 65 22 20 74 61 62 6c 65 0a 62 75 74 20 77 69 74  e" table.but wit
1430: 68 20 74 68 65 20 63 6f 6e 74 65 6e 74 20 28 74  h the content (t
1440: 68 65 20 66 72 75 69 74 20 63 6f 6c 75 6d 6e 20  he fruit column 
1450: 69 6e 20 74 68 69 73 20 63 61 73 65 29 20 73 74  in this case) st
1460: 6f 72 65 64 20 69 6e 20 66 72 6f 6e 74 20 6f 66  ored in front of
1470: 20 74 68 65 0a 72 6f 77 69 64 20 61 6e 64 20 77   the.rowid and w
1480: 69 74 68 20 61 6c 6c 20 72 6f 77 73 20 69 6e 20  ith all rows in 
1490: 63 6f 6e 74 65 6e 74 20 6f 72 64 65 72 2e 0a 3c  content order..<
14a0: 61 20 68 72 65 66 3d 22 23 66 69 67 34 22 3e 46  a href="#fig4">F
14b0: 69 67 75 72 65 20 34 3c 2f 61 3e 20 67 69 76 65  igure 4</a> give
14c0: 73 20 61 20 6c 6f 67 69 63 61 6c 20 76 69 65 77  s a logical view
14d0: 20 6f 66 20 74 68 65 20 49 64 78 31 20 69 6e 64   of the Idx1 ind
14e0: 65 78 2e 0a 54 68 65 20 22 66 72 75 69 74 22 20  ex..The "fruit" 
14f0: 63 6f 6c 75 6d 6e 20 69 73 20 74 68 65 20 70 72  column is the pr
1500: 69 6d 61 72 79 20 6b 65 79 20 75 73 65 64 20 74  imary key used t
1510: 6f 20 6f 72 64 65 72 20 74 68 65 20 65 6c 65 6d  o order the elem
1520: 65 6e 74 73 20 6f 66 20 74 68 65 0a 74 61 62 6c  ents of the.tabl
1530: 65 20 61 6e 64 20 74 68 65 20 22 72 6f 77 69 64  e and the "rowid
1540: 22 20 69 73 20 74 68 65 20 73 65 63 6f 6e 64 61  " is the seconda
1550: 72 79 20 6b 65 79 20 75 73 65 64 20 74 6f 20 62  ry key used to b
1560: 72 65 61 6b 20 74 68 65 20 74 69 65 20 77 68 65  reak the tie whe
1570: 6e 0a 74 77 6f 20 6f 72 20 6d 6f 72 65 20 72 6f  n.two or more ro
1580: 77 73 20 68 61 76 65 20 74 68 65 20 73 61 6d 65  ws have the same
1590: 20 22 66 72 75 69 74 22 2e 20 20 49 6e 20 74 68   "fruit".  In th
15a0: 65 20 65 78 61 6d 70 6c 65 2c 20 74 68 65 20 72  e example, the r
15b0: 6f 77 69 64 0a 68 61 73 20 74 6f 20 62 65 20 75  owid.has to be u
15c0: 73 65 64 20 61 73 20 61 20 74 69 65 2d 62 72 65  sed as a tie-bre
15d0: 61 6b 65 72 20 66 6f 72 20 74 68 65 20 22 4f 72  aker for the "Or
15e0: 61 6e 67 65 22 20 72 6f 77 73 2e 0a 4e 6f 74 69  ange" rows..Noti
15f0: 63 65 20 74 68 61 74 20 73 69 6e 63 65 20 74 68  ce that since th
1600: 65 20 72 6f 77 69 64 0a 69 73 20 61 6c 77 61 79  e rowid.is alway
1610: 73 20 75 6e 69 71 75 65 20 6f 76 65 72 20 61 6c  s unique over al
1620: 6c 20 65 6c 65 6d 65 6e 74 73 20 6f 66 20 74 68  l elements of th
1630: 65 20 6f 72 69 67 69 6e 61 6c 20 74 61 62 6c 65  e original table
1640: 2c 20 74 68 65 20 63 6f 6d 70 6f 73 69 74 65 20  , the composite 
1650: 6b 65 79 0a 6f 66 20 22 66 72 75 69 74 22 20 66  key.of "fruit" f
1660: 6f 6c 6c 6f 77 65 64 20 62 79 20 22 72 6f 77 69  ollowed by "rowi
1670: 64 22 20 77 69 6c 6c 20 62 65 20 75 6e 69 71 75  d" will be uniqu
1680: 65 20 6f 76 65 72 20 61 6c 6c 20 65 6c 65 6d 65  e over all eleme
1690: 6e 74 73 20 6f 66 20 74 68 65 20 69 6e 64 65 78  nts of the index
16a0: 2e 0a 3c 2f 70 3e 0a 0a 3c 74 63 6c 3e 66 69 67  ..</p>..<tcl>fig
16b0: 75 72 65 20 34 20 23 66 69 67 34 20 69 64 78 31  ure 4 #fig4 idx1
16c0: 2e 67 69 66 20 7b 41 6e 20 49 6e 64 65 78 20 4f  .gif {An Index O
16d0: 6e 20 54 68 65 20 46 72 75 69 74 20 43 6f 6c 75  n The Fruit Colu
16e0: 6d 6e 7d 3c 2f 74 63 6c 3e 0a 0a 3c 70 3e 0a 57  mn}</tcl>..<p>.W
16f0: 69 74 68 20 74 68 65 20 6e 65 77 20 69 6e 64 65  ith the new inde
1700: 78 20 69 6e 20 70 6c 61 63 65 2c 20 77 65 20 63  x in place, we c
1710: 61 6e 20 64 65 76 69 73 65 20 61 6e 20 61 6c 74  an devise an alt
1720: 65 72 6e 61 74 69 76 65 20 70 6c 61 6e 20 66 6f  ernative plan fo
1730: 72 20 74 68 65 0a 6f 72 69 67 69 6e 61 6c 20 22  r the.original "
1740: 50 72 69 63 65 20 6f 66 20 50 65 61 63 68 65 73  Price of Peaches
1750: 22 20 71 75 65 72 79 2e 0a 3c 2f 70 3e 0a 0a 3c  " query..</p>..<
1760: 74 63 6c 3e 63 6f 64 65 20 7b 0a 53 45 4c 45 43  tcl>code {.SELEC
1770: 54 20 70 72 69 63 65 20 46 52 4f 4d 20 66 72 75  T price FROM fru
1780: 69 74 73 66 6f 72 73 61 6c 65 20 57 48 45 52 45  itsforsale WHERE
1790: 20 66 72 75 69 74 3d 27 50 65 61 63 68 27 3b 0a   fruit='Peach';.
17a0: 7d 3c 2f 74 63 6c 3e 0a 0a 3c 70 3e 0a 54 68 65  }</tcl>..<p>.The
17b0: 20 71 75 65 72 79 20 73 74 61 72 74 73 20 62 79   query starts by
17c0: 20 64 6f 69 6e 67 20 61 20 62 69 6e 61 72 79 20   doing a binary 
17d0: 73 65 61 72 63 68 20 6f 6e 20 74 68 65 20 49 64  search on the Id
17e0: 78 31 20 69 6e 64 65 78 20 66 6f 72 20 65 6e 74  x1 index for ent
17f0: 72 69 65 73 0a 74 68 61 74 20 68 61 76 65 20 66  ries.that have f
1800: 72 75 69 74 3d 27 50 65 61 63 68 27 2e 20 20 53  ruit='Peach'.  S
1810: 51 4c 69 74 65 20 63 61 6e 20 64 6f 20 74 68 69  QLite can do thi
1820: 73 20 62 69 6e 61 72 79 20 73 65 61 72 63 68 20  s binary search 
1830: 6f 6e 20 74 68 65 20 49 64 78 31 20 69 6e 64 65  on the Idx1 inde
1840: 78 0a 62 75 74 20 6e 6f 74 20 6f 6e 20 74 68 65  x.but not on the
1850: 20 6f 72 69 67 69 6e 61 6c 20 46 72 75 69 74 73   original Fruits
1860: 46 6f 72 53 61 6c 65 20 74 61 62 6c 65 20 62 65  ForSale table be
1870: 63 61 75 73 65 20 74 68 65 20 72 6f 77 73 20 69  cause the rows i
1880: 6e 20 49 64 78 31 20 61 72 65 20 73 6f 72 74 65  n Idx1 are sorte
1890: 64 0a 62 79 20 74 68 65 20 22 66 72 75 69 74 22  d.by the "fruit"
18a0: 20 63 6f 6c 75 6d 6e 2e 20 20 48 61 76 69 6e 67   column.  Having
18b0: 20 66 6f 75 6e 64 20 61 20 72 6f 77 20 69 6e 20   found a row in 
18c0: 74 68 65 20 49 64 78 31 20 69 6e 64 65 78 20 74  the Idx1 index t
18d0: 68 61 74 20 68 61 73 0a 66 72 75 69 74 3d 27 50  hat has.fruit='P
18e0: 65 61 63 68 27 2c 20 74 68 65 20 64 61 74 61 62  each', the datab
18f0: 61 73 65 20 65 6e 67 69 6e 65 20 63 61 6e 20 65  ase engine can e
1900: 78 74 72 61 63 74 20 74 68 65 20 72 6f 77 69 64  xtract the rowid
1910: 20 66 6f 72 20 74 68 61 74 20 72 6f 77 2c 0a 74   for that row,.t
1920: 68 65 6e 20 64 6f 20 61 20 73 65 70 61 72 61 74  hen do a separat
1930: 65 20 62 69 6e 61 72 79 20 73 65 61 72 63 68 20  e binary search 
1940: 6f 6e 20 74 68 65 20 6f 72 69 67 69 6e 61 6c 20  on the original 
1950: 46 72 75 69 74 73 46 6f 72 53 61 6c 65 20 74 61  FruitsForSale ta
1960: 62 6c 65 20 74 6f 20 66 69 6e 64 20 74 68 65 0a  ble to find the.
1970: 6f 72 69 67 69 6e 61 6c 20 72 6f 77 20 74 68 61  original row tha
1980: 74 20 63 6f 6e 74 61 69 6e 73 20 66 72 75 69 74  t contains fruit
1990: 3d 27 50 65 61 63 68 27 2e 20 20 46 72 6f 6d 20  ='Peach'.  From 
19a0: 74 68 65 20 72 6f 77 20 69 6e 20 74 68 65 20 46  the row in the F
19b0: 72 75 69 74 73 46 6f 72 53 61 6c 65 20 74 61 62  ruitsForSale tab
19c0: 6c 65 2c 0a 53 51 4c 69 74 65 20 63 61 6e 20 65  le,.SQLite can e
19d0: 78 74 72 61 63 74 20 74 68 65 20 76 61 6c 75 65  xtract the value
19e0: 20 6f 66 20 74 68 65 20 70 72 69 63 65 20 63 6f   of the price co
19f0: 6c 75 6d 6e 2e 0a 54 68 69 73 20 70 72 6f 63 65  lumn..This proce
1a00: 64 75 72 65 20 69 73 20 69 6c 6c 75 73 74 72 61  dure is illustra
1a10: 74 65 64 20 62 79 20 3c 61 20 68 72 65 66 3d 22  ted by <a href="
1a20: 23 66 69 67 35 22 3e 66 69 67 75 72 65 20 35 3c  #fig5">figure 5<
1a30: 2f 61 3e 2e 0a 3c 2f 70 3e 0a 0a 3c 74 63 6c 3e  /a>..</p>..<tcl>
1a40: 66 69 67 75 72 65 20 35 20 23 66 69 67 35 20 69  figure 5 #fig5 i
1a50: 64 78 31 6c 75 31 2e 67 69 66 20 7b 49 6e 64 65  dx1lu1.gif {Inde
1a60: 78 65 64 20 4c 6f 6f 6b 75 70 20 46 6f 72 20 54  xed Lookup For T
1a70: 68 65 20 50 72 69 63 65 20 4f 66 20 50 65 61 63  he Price Of Peac
1a80: 68 65 73 7d 3c 2f 74 63 6c 3e 0a 0a 3c 70 3e 0a  hes}</tcl>..<p>.
1a90: 53 51 4c 69 74 65 20 68 61 73 20 74 6f 20 64 6f  SQLite has to do
1aa0: 20 74 77 6f 20 62 69 6e 61 72 79 20 73 65 61 72   two binary sear
1ab0: 63 68 65 73 20 74 6f 20 66 69 6e 64 20 74 68 65  ches to find the
1ac0: 20 70 72 69 63 65 20 6f 66 20 70 65 61 63 68 65   price of peache
1ad0: 73 20 75 73 69 6e 67 0a 74 68 65 20 6d 65 74 68  s using.the meth
1ae0: 6f 64 20 73 68 6f 77 20 61 62 6f 76 65 2e 20 20  od show above.  
1af0: 42 75 74 20 66 6f 72 20 61 20 74 61 62 6c 65 20  But for a table 
1b00: 77 69 74 68 20 61 20 6c 61 72 67 65 20 6e 75 6d  with a large num
1b10: 62 65 72 20 6f 66 20 72 6f 77 73 2c 20 74 68 69  ber of rows, thi
1b20: 73 0a 69 73 20 73 74 69 6c 6c 20 6d 75 63 68 20  s.is still much 
1b30: 66 61 73 74 65 72 20 74 68 61 6e 20 64 6f 69 6e  faster than doin
1b40: 67 20 61 20 66 75 6c 6c 20 74 61 62 6c 65 20 73  g a full table s
1b50: 63 61 6e 2e 0a 3c 2f 70 3e 0a 0a 3c 68 33 3e 31  can..</p>..<h3>1
1b60: 2e 34 20 4d 75 6c 74 69 70 6c 65 20 52 65 73 75  .4 Multiple Resu
1b70: 6c 74 20 52 6f 77 73 3c 2f 68 33 3e 0a 0a 3c 70  lt Rows</h3>..<p
1b80: 3e 0a 49 6e 20 74 68 65 20 70 72 65 76 69 6f 75  >.In the previou
1b90: 73 20 71 75 65 72 79 20 74 68 65 20 66 72 75 69  s query the frui
1ba0: 74 3d 27 50 65 61 63 68 27 20 63 6f 6e 73 74 72  t='Peach' constr
1bb0: 61 69 6e 74 20 6e 61 72 72 6f 77 65 64 20 74 68  aint narrowed th
1bc0: 65 20 72 65 73 75 6c 74 0a 64 6f 77 6e 20 74 6f  e result.down to
1bd0: 20 61 20 73 69 6e 67 6c 65 20 72 6f 77 2e 20 20   a single row.  
1be0: 42 75 74 20 74 68 65 20 73 61 6d 65 20 74 65 63  But the same tec
1bf0: 68 6e 69 71 75 65 20 77 6f 72 6b 73 20 65 76 65  hnique works eve
1c00: 6e 20 69 66 20 6d 75 6c 74 69 70 6c 65 0a 72 6f  n if multiple.ro
1c10: 77 73 20 61 72 65 20 6f 62 74 61 69 6e 65 64 2e  ws are obtained.
1c20: 20 20 53 75 70 70 6f 73 65 20 77 65 20 6c 6f 6f    Suppose we loo
1c30: 6b 65 64 20 75 70 20 74 68 65 20 70 72 69 63 65  ked up the price
1c40: 20 6f 66 20 4f 72 61 6e 67 65 73 20 69 6e 73 74   of Oranges inst
1c50: 65 61 64 20 0a 50 65 61 63 68 65 73 3a 0a 3c 2f  ead .Peaches:.</
1c60: 70 3e 0a 0a 3c 74 63 6c 3e 0a 63 6f 64 65 20 7b  p>..<tcl>.code {
1c70: 53 45 4c 45 43 54 20 70 72 69 63 65 20 46 52 4f  SELECT price FRO
1c80: 4d 20 66 72 75 69 74 73 66 6f 72 73 61 6c 65 20  M fruitsforsale 
1c90: 57 48 45 52 45 20 66 72 75 69 74 3d 27 4f 72 61  WHERE fruit='Ora
1ca0: 6e 67 65 27 7d 0a 66 69 67 75 72 65 20 36 20 23  nge'}.figure 6 #
1cb0: 66 69 67 36 20 69 64 78 31 6c 75 32 2e 67 69 66  fig6 idx1lu2.gif
1cc0: 20 7b 49 6e 64 65 78 65 64 20 4c 6f 6f 6b 75 70   {Indexed Lookup
1cd0: 20 46 6f 72 20 54 68 65 20 50 72 69 63 65 20 4f   For The Price O
1ce0: 66 20 4f 72 61 6e 67 65 73 7d 0a 3c 2f 74 63 6c  f Oranges}.</tcl
1cf0: 3e 0a 0a 3c 70 3e 0a 49 6e 20 74 68 69 73 20 63  >..<p>.In this c
1d00: 61 73 65 2c 20 53 51 4c 69 74 65 20 73 74 69 6c  ase, SQLite stil
1d10: 6c 20 64 6f 65 73 20 61 20 73 69 6e 67 6c 65 20  l does a single 
1d20: 62 69 6e 61 72 79 20 73 65 61 72 63 68 20 74 6f  binary search to
1d30: 20 66 69 6e 64 20 74 68 65 20 66 69 72 73 74 0a   find the first.
1d40: 65 6e 74 72 79 20 6f 66 20 74 68 65 20 69 6e 64  entry of the ind
1d50: 65 78 20 77 68 65 72 65 20 66 72 75 69 74 3d 27  ex where fruit='
1d60: 4f 72 61 6e 67 65 27 2e 20 20 54 68 65 6e 20 69  Orange'.  Then i
1d70: 74 20 65 78 74 72 61 63 74 73 20 74 68 65 20 72  t extracts the r
1d80: 6f 77 69 64 20 66 72 6f 6d 0a 74 68 65 20 69 6e  owid from.the in
1d90: 64 65 78 20 61 6e 64 20 75 73 65 73 20 74 68 61  dex and uses tha
1da0: 74 20 72 6f 77 69 64 20 74 6f 20 6c 6f 6f 6b 75  t rowid to looku
1db0: 70 20 74 68 65 20 6f 72 69 67 69 6e 61 6c 20 74  p the original t
1dc0: 61 62 6c 65 20 65 6e 74 72 79 20 76 69 61 0a 62  able entry via.b
1dd0: 69 6e 61 72 79 20 73 65 61 72 63 68 20 61 6e 64  inary search and
1de0: 20 6f 75 74 70 75 74 20 74 68 65 20 70 72 69 63   output the pric
1df0: 65 20 66 72 6f 6d 20 74 68 65 20 6f 72 69 67 69  e from the origi
1e00: 6e 61 6c 20 74 61 62 6c 65 2e 20 20 42 75 74 20  nal table.  But 
1e10: 69 6e 73 74 65 61 64 0a 6f 66 20 71 75 69 74 74  instead.of quitt
1e20: 69 6e 67 2c 20 74 68 65 20 64 61 74 61 62 61 73  ing, the databas
1e30: 65 20 65 6e 67 69 6e 65 20 74 68 65 6e 20 61 64  e engine then ad
1e40: 76 61 6e 63 65 73 20 74 6f 20 74 68 65 20 6e 65  vances to the ne
1e50: 78 74 20 72 6f 77 20 6f 66 20 69 6e 64 65 78 0a  xt row of index.
1e60: 74 6f 20 72 65 70 65 61 74 20 74 68 65 20 70 72  to repeat the pr
1e70: 6f 63 65 73 73 20 66 6f 72 20 6e 65 78 74 20 66  ocess for next f
1e80: 72 75 69 74 3d 27 4f 72 61 6e 67 65 27 20 65 6e  ruit='Orange' en
1e90: 74 72 79 2e 20 20 41 64 76 61 6e 63 69 6e 67 20  try.  Advancing 
1ea0: 74 6f 20 74 68 65 0a 6e 65 78 74 20 72 6f 77 20  to the.next row 
1eb0: 6f 66 20 61 6e 20 69 6e 64 65 78 20 28 6f 72 20  of an index (or 
1ec0: 74 61 62 6c 65 29 20 69 73 20 6d 75 63 68 20 6c  table) is much l
1ed0: 65 73 73 20 63 6f 73 74 6c 79 20 74 68 61 6e 20  ess costly than 
1ee0: 64 6f 69 6e 67 20 61 20 62 69 6e 61 72 79 0a 73  doing a binary.s
1ef0: 65 61 72 63 68 20 73 69 6e 63 65 20 74 68 65 20  earch since the 
1f00: 6e 65 78 74 20 72 6f 77 20 69 73 20 6f 66 74 65  next row is ofte
1f10: 6e 20 6c 6f 63 61 74 65 64 20 6f 6e 20 74 68 65  n located on the
1f20: 20 73 61 6d 65 20 64 61 74 61 62 61 73 65 20 70   same database p
1f30: 61 67 65 20 61 73 0a 74 68 65 20 63 75 72 72 65  age as.the curre
1f40: 6e 74 20 72 6f 77 2e 20 20 49 6e 20 66 61 63 74  nt row.  In fact
1f50: 2c 20 74 68 65 20 63 6f 73 74 20 6f 66 20 61 64  , the cost of ad
1f60: 76 61 6e 63 69 6e 67 20 74 6f 20 74 68 65 20 6e  vancing to the n
1f70: 65 78 74 20 72 6f 77 20 69 73 20 73 6f 0a 63 68  ext row is so.ch
1f80: 65 61 70 20 69 6e 20 63 6f 6d 70 61 72 69 73 6f  eap in compariso
1f90: 6e 20 74 6f 20 61 20 62 69 6e 61 72 79 20 73 65  n to a binary se
1fa0: 61 72 63 68 20 74 68 61 74 20 77 65 20 75 73 75  arch that we usu
1fb0: 61 6c 6c 79 20 69 67 6e 6f 72 65 20 69 74 2e 20  ally ignore it. 
1fc0: 20 53 6f 0a 6f 75 72 20 65 73 74 69 6d 61 74 65   So.our estimate
1fd0: 20 66 6f 72 20 74 68 65 20 74 6f 74 61 6c 20 63   for the total c
1fe0: 6f 73 74 20 6f 66 20 74 68 69 73 20 71 75 65 72  ost of this quer
1ff0: 79 20 69 73 20 33 20 62 69 6e 61 72 79 20 73 65  y is 3 binary se
2000: 61 72 63 68 65 73 2e 0a 49 66 20 74 68 65 20 6e  arches..If the n
2010: 75 6d 62 65 72 20 6f 66 20 72 6f 77 73 20 6f 66  umber of rows of
2020: 20 6f 75 74 70 75 74 20 69 73 20 4b 20 61 6e 64   output is K and
2030: 20 74 68 65 20 6e 75 6d 62 65 72 20 6f 66 20 72   the number of r
2040: 6f 77 73 20 69 6e 20 74 68 65 20 74 61 62 6c 65  ows in the table
2050: 0a 69 73 20 4e 2c 20 74 68 65 6e 20 69 6e 20 67  .is N, then in g
2060: 65 6e 65 72 61 6c 20 74 68 65 20 63 6f 73 74 20  eneral the cost 
2070: 6f 66 20 64 6f 69 6e 67 20 74 68 65 20 71 75 65  of doing the que
2080: 72 79 20 70 72 6f 70 6f 72 74 69 6f 6e 61 6c 0a  ry proportional.
2090: 74 6f 20 28 4b 2b 31 29 2a 6c 6f 67 4e 2e 0a 3c  to (K+1)*logN..<
20a0: 2f 70 3e 0a 0a 3c 68 33 3e 31 2e 35 20 4d 75 6c  /p>..<h3>1.5 Mul
20b0: 74 69 70 6c 65 20 41 4e 44 2d 43 6f 6e 6e 65 63  tiple AND-Connec
20c0: 74 65 64 20 57 48 45 52 45 2d 43 6c 61 75 73 65  ted WHERE-Clause
20d0: 20 54 65 72 6d 73 3c 2f 68 33 3e 0a 0a 3c 70 3e   Terms</h3>..<p>
20e0: 0a 4e 65 78 74 2c 20 73 75 70 70 6f 73 65 20 74  .Next, suppose t
20f0: 68 61 74 20 79 6f 75 20 77 61 6e 74 20 74 6f 20  hat you want to 
2100: 6c 6f 6f 6b 20 75 70 20 74 68 65 20 70 72 69 63  look up the pric
2110: 65 20 6f 66 20 6e 6f 74 20 6a 75 73 74 20 61 6e  e of not just an
2120: 79 20 6f 72 61 6e 67 65 2c 0a 62 75 74 20 73 70  y orange,.but sp
2130: 65 63 69 66 69 63 61 6c 6c 79 20 43 61 6c 69 66  ecifically Calif
2140: 6f 72 6e 69 61 2d 67 72 6f 77 6e 20 6f 72 61 6e  ornia-grown oran
2150: 67 65 73 2e 20 20 54 68 65 20 61 70 70 72 6f 70  ges.  The approp
2160: 72 69 61 74 65 20 71 75 65 72 79 20 77 6f 75 6c  riate query woul
2170: 64 0a 62 65 20 61 73 20 66 6f 6c 6c 6f 77 73 3a  d.be as follows:
2180: 0a 3c 2f 70 3e 0a 0a 3c 74 63 6c 3e 0a 63 6f 64  .</p>..<tcl>.cod
2190: 65 20 7b 53 45 4c 45 43 54 20 70 72 69 63 65 20  e {SELECT price 
21a0: 46 52 4f 4d 20 66 72 75 69 74 73 66 6f 72 73 61  FROM fruitsforsa
21b0: 6c 65 20 57 48 45 52 45 20 66 72 75 69 74 3d 27  le WHERE fruit='
21c0: 4f 72 61 6e 67 65 27 20 41 4e 44 20 73 74 61 74  Orange' AND stat
21d0: 65 3d 27 43 41 27 7d 0a 66 69 67 75 72 65 20 37  e='CA'}.figure 7
21e0: 20 23 66 69 67 37 20 69 64 78 31 6c 75 33 2e 67   #fig7 idx1lu3.g
21f0: 69 66 20 7b 49 6e 64 65 78 65 64 20 4c 6f 6f 6b  if {Indexed Look
2200: 75 70 20 4f 66 20 43 61 6c 69 66 6f 72 6e 69 61  up Of California
2210: 20 4f 72 61 6e 67 65 73 7d 0a 3c 2f 74 63 6c 3e   Oranges}.</tcl>
2220: 0a 0a 3c 70 3e 0a 4f 6e 65 20 61 70 70 72 6f 61  ..<p>.One approa
2230: 63 68 20 74 6f 20 74 68 69 73 20 71 75 65 72 79  ch to this query
2240: 20 69 73 20 74 6f 20 75 73 65 20 74 68 65 20 66   is to use the f
2250: 72 75 69 74 3d 27 4f 72 61 6e 67 65 27 20 74 65  ruit='Orange' te
2260: 72 6d 20 6f 66 20 74 68 65 20 57 48 45 52 45 0a  rm of the WHERE.
2270: 63 6c 61 75 73 65 20 74 6f 20 66 69 6e 64 20 61  clause to find a
2280: 6c 6c 20 72 6f 77 73 20 64 65 61 6c 69 6e 67 20  ll rows dealing 
2290: 77 69 74 68 20 6f 72 61 6e 67 65 73 2c 20 74 68  with oranges, th
22a0: 65 6e 20 66 69 6c 74 65 72 20 74 68 6f 73 65 20  en filter those 
22b0: 72 6f 77 73 0a 62 79 20 72 65 6a 65 63 74 69 6e  rows.by rejectin
22c0: 67 20 61 6e 79 20 74 68 61 74 20 61 72 65 20 66  g any that are f
22d0: 72 6f 6d 20 73 74 61 74 65 73 20 6f 74 68 65 72  rom states other
22e0: 20 74 68 61 6e 20 43 61 6c 69 66 6f 72 6e 69 61   than California
22f0: 2e 20 20 54 68 69 73 0a 70 72 6f 63 65 73 73 20  .  This.process 
2300: 69 73 20 73 68 6f 77 6e 20 62 79 20 3c 61 20 68  is shown by <a h
2310: 72 65 66 3d 22 23 66 69 67 37 22 3e 66 69 67 75  ref="#fig7">figu
2320: 72 65 20 37 3c 2f 61 3e 20 61 62 6f 76 65 2e 20  re 7</a> above. 
2330: 20 54 68 69 73 20 69 73 20 61 20 70 65 72 66 65   This is a perfe
2340: 63 74 6c 79 0a 72 65 61 73 6f 6e 61 62 6c 65 20  ctly.reasonable 
2350: 61 70 70 72 6f 61 63 68 20 69 6e 20 6d 6f 73 74  approach in most
2360: 20 63 61 73 65 73 2e 20 20 59 65 73 2c 20 74 68   cases.  Yes, th
2370: 65 20 64 61 74 61 62 61 73 65 20 65 6e 67 69 6e  e database engin
2380: 65 20 64 69 64 20 68 61 76 65 0a 74 6f 20 64 6f  e did have.to do
2390: 20 61 6e 20 65 78 74 72 61 20 62 69 6e 61 72 79   an extra binary
23a0: 20 73 65 61 72 63 68 20 66 6f 72 20 74 68 65 20   search for the 
23b0: 46 6c 6f 72 69 64 61 20 6f 72 61 6e 67 65 20 72  Florida orange r
23c0: 6f 77 20 74 68 61 74 20 77 61 73 0a 6c 61 74 65  ow that was.late
23d0: 72 20 72 65 6a 65 63 74 65 64 2c 20 73 6f 20 69  r rejected, so i
23e0: 74 20 77 61 73 20 6e 6f 74 20 61 73 20 65 66 66  t was not as eff
23f0: 69 63 69 65 6e 74 20 61 73 20 77 65 20 6d 69 67  icient as we mig
2400: 68 74 20 68 6f 70 65 2c 20 74 68 6f 75 67 68 0a  ht hope, though.
2410: 66 6f 72 20 6d 61 6e 79 20 61 70 70 6c 69 63 61  for many applica
2420: 74 69 6f 6e 73 20 69 74 20 69 73 20 65 66 66 69  tions it is effi
2430: 63 69 65 6e 74 20 65 6e 6f 75 67 68 2e 20 20 0a  cient enough.  .
2440: 3c 2f 70 3e 0a 0a 3c 70 3e 0a 53 75 70 70 6f 73  </p>..<p>.Suppos
2450: 65 20 74 68 61 74 20 69 6e 20 61 64 64 69 74 69  e that in additi
2460: 6f 6e 20 74 6f 20 74 68 65 20 69 6e 64 65 78 20  on to the index 
2470: 6f 6e 20 22 66 72 75 69 74 22 20 74 68 65 72 65  on "fruit" there
2480: 20 77 61 73 20 61 6c 73 6f 0a 61 6e 20 69 6e 64   was also.an ind
2490: 65 78 20 6f 6e 20 22 73 74 61 74 65 22 2e 0a 3c  ex on "state"..<
24a0: 2f 70 3e 0a 0a 3c 74 63 6c 3e 0a 63 6f 64 65 20  /p>..<tcl>.code 
24b0: 7b 43 52 45 41 54 45 20 49 4e 44 45 58 20 49 64  {CREATE INDEX Id
24c0: 78 32 20 4f 4e 20 66 72 75 69 74 73 66 6f 72 73  x2 ON fruitsfors
24d0: 61 6c 65 28 73 74 61 74 65 29 3b 7d 0a 66 69 67  ale(state);}.fig
24e0: 75 72 65 20 38 20 23 66 69 67 38 20 69 64 78 32  ure 8 #fig8 idx2
24f0: 2e 67 69 66 20 7b 49 6e 64 65 78 20 4f 6e 20 54  .gif {Index On T
2500: 68 65 20 53 74 61 74 65 20 43 6f 6c 75 6d 6e 7d  he State Column}
2510: 0a 3c 2f 74 63 6c 3e 0a 0a 3c 70 3e 0a 54 68 65  .</tcl>..<p>.The
2520: 20 22 73 74 61 74 65 22 20 69 6e 64 65 78 20 77   "state" index w
2530: 6f 72 6b 73 20 6a 75 73 74 20 6c 69 6b 65 20 74  orks just like t
2540: 68 65 20 22 66 72 75 69 74 22 20 69 6e 64 65 78  he "fruit" index
2550: 20 69 6e 20 74 68 61 74 20 69 74 20 69 73 20 61   in that it is a
2560: 0a 6e 65 77 20 74 61 62 6c 65 20 77 69 74 68 20  .new table with 
2570: 61 6e 20 65 78 74 72 61 20 63 6f 6c 75 6d 6e 20  an extra column 
2580: 69 6e 20 66 72 6f 6e 74 20 6f 66 20 74 68 65 20  in front of the 
2590: 72 6f 77 69 64 20 61 6e 64 20 73 6f 72 74 65 64  rowid and sorted
25a0: 20 62 79 0a 74 68 61 74 20 65 78 74 72 61 20 63   by.that extra c
25b0: 6f 6c 75 6d 6e 20 61 73 20 74 68 65 20 70 72 69  olumn as the pri
25c0: 6d 61 72 79 20 6b 65 79 2e 20 20 54 68 65 20 6f  mary key.  The o
25d0: 6e 6c 79 20 64 69 66 66 65 72 65 6e 63 65 20 69  nly difference i
25e0: 73 20 74 68 61 74 0a 69 6e 20 49 64 78 32 2c 20  s that.in Idx2, 
25f0: 74 68 65 20 66 69 72 73 74 20 63 6f 6c 75 6d 6e  the first column
2600: 20 69 73 20 22 73 74 61 74 65 22 20 69 6e 73 74   is "state" inst
2610: 65 61 64 20 6f 66 20 22 66 72 75 69 74 22 20 61  ead of "fruit" a
2620: 73 20 69 74 20 69 73 20 77 69 74 68 0a 49 64 78  s it is with.Idx
2630: 31 2e 20 20 49 6e 20 6f 75 72 20 65 78 61 6d 70  1.  In our examp
2640: 6c 65 20 64 61 74 61 20 73 65 74 2c 20 74 68 65  le data set, the
2650: 20 69 73 20 6d 6f 72 65 20 72 65 64 75 6e 64 61   is more redunda
2660: 6e 63 79 20 69 6e 20 74 68 65 20 22 73 74 61 74  ncy in the "stat
2670: 65 22 0a 63 6f 6c 75 6d 6e 20 61 6e 64 20 73 6f  e".column and so
2680: 20 74 68 65 79 20 61 72 65 20 6d 6f 72 65 20 64   they are more d
2690: 75 70 6c 69 63 61 74 65 20 65 6e 74 72 69 65 73  uplicate entries
26a0: 2e 20 20 54 68 65 20 74 69 65 73 20 61 72 65 20  .  The ties are 
26b0: 73 74 69 6c 6c 0a 72 65 73 6f 6c 76 65 64 20 75  still.resolved u
26c0: 73 69 6e 67 20 74 68 65 20 72 6f 77 69 64 2e 0a  sing the rowid..
26d0: 3c 2f 70 3e 0a 0a 3c 70 3e 0a 55 73 69 6e 67 20  </p>..<p>.Using 
26e0: 74 68 65 20 6e 65 77 20 49 64 78 32 20 69 6e 64  the new Idx2 ind
26f0: 65 78 20 6f 6e 20 22 73 74 61 74 65 22 2c 20 53  ex on "state", S
2700: 51 4c 69 74 65 20 68 61 73 20 61 6e 6f 74 68 65  QLite has anothe
2710: 72 20 6f 70 74 69 6f 6e 20 66 6f 72 0a 6c 6f 6f  r option for.loo
2720: 6b 75 70 20 75 70 20 74 68 65 20 70 72 69 63 65  kup up the price
2730: 20 6f 66 20 43 61 6c 69 66 6f 72 6e 69 61 20 6f   of California o
2740: 72 61 6e 67 65 73 3a 20 20 69 74 20 63 61 6e 20  ranges:  it can 
2750: 6c 6f 6f 6b 20 75 70 20 65 76 65 72 79 20 72 6f  look up every ro
2760: 77 0a 74 68 61 74 20 63 6f 6e 74 61 69 6e 73 20  w.that contains 
2770: 66 72 75 69 74 20 66 72 6f 6d 20 43 61 6c 69 66  fruit from Calif
2780: 6f 72 6e 69 61 20 61 6e 64 20 66 69 6c 74 65 72  ornia and filter
2790: 20 6f 75 74 20 74 68 6f 73 65 20 72 6f 77 73 20   out those rows 
27a0: 74 68 61 74 0a 61 72 65 20 6e 6f 74 20 6f 72 61  that.are not ora
27b0: 6e 67 65 73 2e 0a 3c 2f 70 3e 0a 0a 3c 74 63 6c  nges..</p>..<tcl
27c0: 3e 66 69 67 75 72 65 20 39 20 23 66 69 67 39 20  >figure 9 #fig9 
27d0: 69 64 78 32 6c 75 31 2e 67 69 66 20 7b 49 6e 64  idx2lu1.gif {Ind
27e0: 65 78 65 64 20 4c 6f 6f 6b 75 70 20 4f 66 20 43  exed Lookup Of C
27f0: 61 6c 69 66 6f 72 6e 69 61 20 4f 72 61 6e 67 65  alifornia Orange
2800: 73 7d 3c 2f 74 63 6c 3e 0a 0a 3c 70 3e 0a 55 73  s}</tcl>..<p>.Us
2810: 69 6e 67 20 49 64 78 32 20 69 6e 73 74 65 61 64  ing Idx2 instead
2820: 20 6f 66 20 49 64 78 31 20 63 61 75 73 65 73 20   of Idx1 causes 
2830: 53 51 4c 69 74 65 20 74 6f 20 65 78 61 6d 69 6e  SQLite to examin
2840: 65 20 61 20 64 69 66 66 65 72 65 6e 74 20 73 65  e a different se
2850: 74 20 6f 66 0a 72 6f 77 73 2c 20 62 75 74 20 69  t of.rows, but i
2860: 74 20 67 65 74 73 20 74 68 65 20 73 61 6d 65 20  t gets the same 
2870: 61 6e 73 77 65 72 20 69 6e 20 74 68 65 20 65 6e  answer in the en
2880: 64 20 28 77 68 69 63 68 20 69 73 20 76 65 72 79  d (which is very
2890: 20 69 6d 70 6f 72 74 61 6e 74 20 2d 0a 72 65 6d   important -.rem
28a0: 65 6d 62 65 72 20 74 68 61 74 20 69 6e 64 69 63  ember that indic
28b0: 65 73 20 73 68 6f 75 6c 64 20 6e 65 76 65 72 20  es should never 
28c0: 63 68 61 6e 67 65 20 74 68 65 20 61 6e 73 77 65  change the answe
28d0: 72 2c 20 6f 6e 6c 79 20 68 65 6c 70 20 53 51 4c  r, only help SQL
28e0: 69 74 65 20 74 6f 0a 67 65 74 20 74 6f 20 74 68  ite to.get to th
28f0: 65 20 61 6e 73 77 65 72 20 6d 6f 72 65 20 71 75  e answer more qu
2900: 69 63 6b 6c 79 29 20 61 6e 64 20 69 74 20 64 6f  ickly) and it do
2910: 65 73 20 74 68 65 20 73 61 6d 65 20 61 6d 6f 75  es the same amou
2920: 6e 74 20 6f 66 20 77 6f 72 6b 2e 0a 53 6f 20 74  nt of work..So t
2930: 68 65 20 49 64 78 32 20 69 6e 64 65 78 20 64 69  he Idx2 index di
2940: 64 20 6e 6f 74 20 68 65 6c 70 20 70 65 72 66 6f  d not help perfo
2950: 72 6d 61 6e 63 65 20 69 6e 20 74 68 69 73 20 63  rmance in this c
2960: 61 73 65 2e 0a 3c 2f 70 3e 0a 0a 3c 70 3e 0a 54  ase..</p>..<p>.T
2970: 68 65 20 6c 61 73 74 20 74 77 6f 20 71 75 65 72  he last two quer
2980: 69 65 73 20 74 61 6b 65 20 74 68 65 20 73 61 6d  ies take the sam
2990: 65 20 61 6d 6f 75 6e 74 20 6f 66 20 74 69 6d 65  e amount of time
29a0: 2c 20 69 6e 20 6f 75 72 20 65 78 61 6d 70 6c 65  , in our example
29b0: 2e 0a 53 6f 20 77 68 69 63 68 20 69 6e 64 65 78  ..So which index
29c0: 2c 20 49 64 78 31 20 6f 72 20 49 64 78 32 2c 20  , Idx1 or Idx2, 
29d0: 77 69 6c 6c 20 53 51 4c 69 74 65 20 63 68 6f 6f  will SQLite choo
29e0: 73 65 3f 20 20 49 66 20 74 68 65 0a 5b 41 4e 41  se?  If the.[ANA
29f0: 4c 59 5a 45 5d 20 63 6f 6d 6d 61 6e 64 20 68 61  LYZE] command ha
2a00: 73 20 62 65 65 6e 20 72 75 6e 20 6f 6e 20 74 68  s been run on th
2a10: 65 20 64 61 74 61 62 61 73 65 2c 20 73 6f 20 74  e database, so t
2a20: 68 61 74 20 53 51 4c 69 74 65 20 68 61 73 0a 68  hat SQLite has.h
2a30: 61 64 20 61 6e 20 6f 70 70 6f 72 74 75 6e 69 74  ad an opportunit
2a40: 79 20 74 6f 20 67 61 74 68 65 72 20 73 74 61 74  y to gather stat
2a50: 69 73 74 69 63 73 20 61 62 6f 75 74 20 74 68 65  istics about the
2a60: 20 61 76 61 69 6c 61 62 6c 65 20 69 6e 64 69 63   available indic
2a70: 65 73 2c 0a 74 68 65 6e 20 53 51 4c 69 74 65 20  es,.then SQLite 
2a80: 77 69 6c 6c 20 6b 6e 6f 77 20 74 68 61 74 20 74  will know that t
2a90: 68 65 20 49 64 78 31 20 74 61 62 6c 65 20 75 73  he Idx1 table us
2aa0: 75 61 6c 6c 79 20 6e 61 72 72 6f 77 73 20 74 68  ually narrows th
2ab0: 65 20 73 65 61 72 63 68 0a 64 6f 77 6e 20 74 6f  e search.down to
2ac0: 20 61 20 73 69 6e 67 6c 65 20 69 74 65 6d 20 28   a single item (
2ad0: 6f 75 72 20 65 78 61 6d 70 6c 65 20 6f 66 20 66  our example of f
2ae0: 72 75 69 74 3d 27 4f 72 61 6e 67 65 27 20 69 73  ruit='Orange' is
2af0: 20 74 68 65 20 65 78 63 65 70 74 69 6f 6e 0a 74   the exception.t
2b00: 6f 20 74 68 69 73 20 72 75 6c 65 29 20 77 68 65  o this rule) whe
2b10: 72 65 20 61 73 20 74 68 65 20 49 64 78 20 74 61  re as the Idx ta
2b20: 62 6c 65 20 77 69 6c 6c 20 6e 6f 72 6d 61 6c 6c  ble will normall
2b30: 79 20 6f 6e 6c 79 20 6e 61 72 72 6f 77 20 74 68  y only narrow th
2b40: 65 20 0a 73 65 61 72 63 68 20 64 6f 77 6e 20 74  e .search down t
2b50: 6f 20 74 77 6f 20 72 6f 77 73 2e 20 20 53 6f 2c  o two rows.  So,
2b60: 20 69 66 20 61 6c 6c 20 65 6c 73 65 20 69 73 20   if all else is 
2b70: 65 71 75 61 6c 2c 20 53 51 4c 69 74 65 20 77 69  equal, SQLite wi
2b80: 6c 6c 0a 63 68 6f 6f 73 65 20 49 64 78 31 20 77  ll.choose Idx1 w
2b90: 69 74 68 20 74 68 65 20 68 6f 70 65 20 6f 66 20  ith the hope of 
2ba0: 6e 61 72 72 6f 77 69 6e 67 20 74 68 65 20 73 65  narrowing the se
2bb0: 61 72 63 68 20 74 6f 20 61 73 20 73 6d 61 6c 6c  arch to as small
2bc0: 0a 61 20 6e 75 6d 62 65 72 20 6f 66 20 72 6f 77  .a number of row
2bd0: 73 20 61 73 20 70 6f 73 73 69 62 6c 65 2e 20 20  s as possible.  
2be0: 54 68 69 73 20 63 68 6f 69 63 65 20 69 73 20 6f  This choice is o
2bf0: 6e 6c 79 20 70 6f 73 73 69 62 6c 65 20 62 65 63  nly possible bec
2c00: 61 75 73 65 0a 6f 66 20 74 68 65 20 73 74 61 74  ause.of the stat
2c10: 69 73 74 69 63 73 20 70 72 6f 76 69 64 65 64 20  istics provided 
2c20: 62 79 20 5b 41 4e 41 4c 59 5a 45 5d 2e 20 20 49  by [ANALYZE].  I
2c30: 66 20 5b 41 4e 41 4c 59 5a 45 5d 20 68 61 73 20  f [ANALYZE] has 
2c40: 6e 6f 74 20 62 65 65 6e 0a 72 75 6e 20 74 68 65  not been.run the
2c50: 6e 20 74 68 65 20 63 68 6f 69 63 65 20 6f 66 20  n the choice of 
2c60: 77 68 69 63 68 20 69 6e 64 65 78 20 74 6f 20 75  which index to u
2c70: 73 65 20 69 73 20 61 72 62 69 74 72 61 72 79 2e  se is arbitrary.
2c80: 0a 3c 2f 70 3e 0a 0a 3c 68 33 3e 31 2e 36 20 4d  .</p>..<h3>1.6 M
2c90: 75 6c 74 69 2d 43 6f 6c 75 6d 6e 20 49 6e 64 69  ulti-Column Indi
2ca0: 63 65 73 3c 2f 68 33 3e 0a 0a 3c 70 3e 0a 54 6f  ces</h3>..<p>.To
2cb0: 20 67 65 74 20 74 68 65 20 6d 61 78 69 6d 75 6d   get the maximum
2cc0: 20 70 65 72 66 6f 72 6d 61 6e 63 65 20 6f 75 74   performance out
2cd0: 20 6f 66 20 61 20 71 75 65 72 79 20 77 69 74 68   of a query with
2ce0: 20 6d 75 6c 74 69 70 6c 65 20 41 4e 44 2d 63 6f   multiple AND-co
2cf0: 6e 6e 65 63 74 65 64 0a 74 65 72 6d 73 20 69 6e  nnected.terms in
2d00: 20 74 68 65 20 57 48 45 52 45 20 63 6c 61 75 73   the WHERE claus
2d10: 65 2c 20 79 6f 75 20 72 65 61 6c 6c 79 20 77 61  e, you really wa
2d20: 6e 74 20 61 20 6d 75 6c 74 69 2d 63 6f 6c 75 6d  nt a multi-colum
2d30: 6e 20 69 6e 64 65 78 20 77 69 74 68 0a 63 6f 6c  n index with.col
2d40: 75 6d 6e 73 20 66 6f 72 20 65 61 63 68 20 6f 66  umns for each of
2d50: 20 74 68 65 20 41 4e 44 20 74 65 72 6d 73 2e 20   the AND terms. 
2d60: 20 49 6e 20 74 68 69 73 20 63 61 73 65 20 77 65   In this case we
2d70: 20 63 72 65 61 74 65 20 61 20 6e 65 77 20 69 6e   create a new in
2d80: 64 65 78 0a 6f 6e 20 74 68 65 20 22 66 72 75 69  dex.on the "frui
2d90: 74 22 20 61 6e 64 20 22 73 74 61 74 65 22 20 63  t" and "state" c
2da0: 6f 6c 75 6d 6e 73 20 6f 66 20 46 72 75 69 74 73  olumns of Fruits
2db0: 46 6f 72 53 61 6c 65 3a 0a 3c 2f 70 3e 0a 0a 3c  ForSale:.</p>..<
2dc0: 74 63 6c 3e 0a 63 6f 64 65 20 7b 43 52 45 41 54  tcl>.code {CREAT
2dd0: 45 20 49 4e 44 45 58 20 49 64 78 33 20 4f 4e 20  E INDEX Idx3 ON 
2de0: 46 72 75 69 74 73 46 6f 72 53 61 6c 65 28 66 72  FruitsForSale(fr
2df0: 75 69 74 2c 20 73 74 61 74 65 29 3b 7d 0a 66 69  uit, state);}.fi
2e00: 67 75 72 65 20 31 20 23 66 69 67 31 30 20 69 64  gure 1 #fig10 id
2e10: 78 33 2e 67 69 66 20 7b 41 20 54 77 6f 2d 43 6f  x3.gif {A Two-Co
2e20: 6c 75 6d 6e 20 49 6e 64 65 78 7d 0a 3c 2f 74 63  lumn Index}.</tc
2e30: 6c 3e 0a 0a 3c 70 3e 0a 41 20 6d 75 6c 74 69 2d  l>..<p>.A multi-
2e40: 63 6f 6c 75 6d 6e 20 69 6e 64 65 78 20 66 6f 6c  column index fol
2e50: 6c 6f 77 73 20 74 68 65 20 73 61 6d 65 20 70 61  lows the same pa
2e60: 74 74 65 72 6e 20 61 73 20 61 20 73 69 6e 67 6c  ttern as a singl
2e70: 65 2d 63 6f 6c 75 6d 6e 20 69 6e 64 65 78 3b 0a  e-column index;.
2e80: 74 68 65 20 69 6e 64 65 78 65 64 20 63 6f 6c 75  the indexed colu
2e90: 6d 6e 73 20 61 72 65 20 61 64 64 65 64 20 69 6e  mns are added in
2ea0: 20 66 72 6f 6e 74 20 6f 66 20 74 68 65 20 72 6f   front of the ro
2eb0: 77 69 64 2e 20 20 54 68 65 20 6f 6e 6c 79 20 64  wid.  The only d
2ec0: 69 66 66 65 72 65 6e 63 65 0a 69 73 20 74 68 61  ifference.is tha
2ed0: 74 20 6e 6f 77 20 6d 75 6c 74 69 70 6c 65 20 63  t now multiple c
2ee0: 6f 6c 75 6d 6e 73 20 61 72 65 20 61 64 64 65 64  olumns are added
2ef0: 2e 20 20 54 68 65 20 6c 65 66 74 2d 6d 6f 73 74  .  The left-most
2f00: 20 63 6f 6c 75 6d 6e 20 69 73 20 74 68 65 0a 70   column is the.p
2f10: 72 69 6d 61 72 79 20 6b 65 79 20 75 73 65 64 20  rimary key used 
2f20: 66 6f 72 20 6f 72 64 65 72 69 6e 67 20 74 68 65  for ordering the
2f30: 20 72 6f 77 73 20 69 6e 20 74 68 65 20 69 6e 64   rows in the ind
2f40: 65 78 2e 20 20 54 68 65 20 73 65 63 6f 6e 64 20  ex.  The second 
2f50: 63 6f 6c 75 6d 6e 20 69 73 0a 75 73 65 64 20 74  column is.used t
2f60: 6f 20 62 72 65 61 6b 20 74 69 65 73 20 69 6e 20  o break ties in 
2f70: 74 68 65 20 6c 65 66 74 2d 6d 6f 73 74 20 63 6f  the left-most co
2f80: 6c 75 6d 6e 2e 20 20 49 66 20 74 68 65 72 65 20  lumn.  If there 
2f90: 77 65 72 65 20 61 20 74 68 69 72 64 20 63 6f 6c  were a third col
2fa0: 75 6d 6e 2c 0a 69 74 20 77 6f 75 6c 64 20 62 65  umn,.it would be
2fb0: 20 75 73 65 64 20 74 6f 20 62 72 65 61 6b 20 74   used to break t
2fc0: 69 65 73 20 66 6f 72 20 74 68 65 20 66 69 72 73  ies for the firs
2fd0: 74 20 74 6f 20 63 6f 6c 75 6d 6e 73 2e 20 20 41  t to columns.  A
2fe0: 6e 64 20 73 6f 20 66 6f 72 74 68 20 66 6f 72 0a  nd so forth for.
2ff0: 61 73 20 6d 61 6e 79 20 63 6f 6c 75 6d 6e 73 20  as many columns 
3000: 61 73 20 74 68 65 69 72 20 61 72 65 20 69 6e 20  as their are in 
3010: 74 68 65 20 69 6e 64 65 78 2e 20 20 42 65 63 61  the index.  Beca
3020: 75 73 65 20 72 6f 77 69 64 20 69 73 20 67 75 61  use rowid is gua
3030: 72 61 6e 74 65 65 64 0a 74 6f 20 62 65 20 75 6e  ranteed.to be un
3040: 69 71 75 65 2c 20 65 76 65 72 79 20 72 6f 77 20  ique, every row 
3050: 6f 66 20 74 68 65 20 69 6e 64 65 78 20 77 69 6c  of the index wil
3060: 6c 20 62 65 20 75 6e 69 71 75 65 20 65 76 65 6e  l be unique even
3070: 20 69 66 20 61 6c 6c 20 6f 66 20 74 68 65 0a 63   if all of the.c
3080: 6f 6e 74 65 6e 74 20 63 6f 6c 75 6d 6e 73 20 66  ontent columns f
3090: 6f 72 20 74 77 6f 20 72 6f 77 73 20 61 72 65 20  or two rows are 
30a0: 74 68 65 20 73 61 6d 65 2e 20 20 54 68 61 74 20  the same.  That 
30b0: 63 61 73 65 20 64 6f 65 73 20 6e 6f 74 20 68 61  case does not ha
30c0: 70 70 65 6e 0a 69 6e 20 6f 75 72 20 73 61 6d 70  ppen.in our samp
30d0: 6c 65 20 64 61 74 61 2c 20 62 75 74 20 74 68 65  le data, but the
30e0: 72 65 20 69 73 20 6f 6e 65 20 63 61 73 65 20 28  re is one case (
30f0: 66 72 75 69 74 3d 27 4f 72 61 6e 67 65 27 29 20  fruit='Orange') 
3100: 77 68 65 72 65 20 74 68 65 72 65 0a 69 73 20 61  where there.is a
3110: 20 74 69 65 20 6f 6e 20 74 68 65 20 66 69 72 73   tie on the firs
3120: 74 20 63 6f 6c 75 6d 6e 20 77 68 69 63 68 20 6d  t column which m
3130: 75 73 74 20 62 65 20 62 72 6f 6b 65 6e 20 62 79  ust be broken by
3140: 20 74 68 65 20 73 65 63 6f 6e 64 20 63 6f 6c 75   the second colu
3150: 6d 6e 2e 0a 3c 2f 70 3e 0a 0a 3c 70 3e 0a 47 69  mn..</p>..<p>.Gi
3160: 76 65 6e 20 74 68 65 20 6e 65 77 20 6d 75 6c 74  ven the new mult
3170: 69 2d 63 6f 6c 75 6d 6e 20 49 64 78 33 20 69 6e  i-column Idx3 in
3180: 64 65 78 2c 20 69 74 20 69 73 20 6e 6f 77 20 70  dex, it is now p
3190: 6f 73 73 69 62 6c 65 20 66 6f 72 20 53 51 4c 69  ossible for SQLi
31a0: 74 65 0a 74 6f 20 66 69 6e 64 20 74 68 65 20 70  te.to find the p
31b0: 72 69 63 65 20 6f 66 20 43 61 6c 69 66 6f 72 6e  rice of Californ
31c0: 69 61 20 6f 72 61 6e 67 65 73 20 75 73 69 6e 67  ia oranges using
31d0: 20 6f 6e 6c 79 20 32 20 62 69 6e 61 72 79 20 73   only 2 binary s
31e0: 65 61 72 63 68 65 73 3a 0a 3c 2f 70 3e 0a 0a 3c  earches:.</p>..<
31f0: 74 63 6c 3e 0a 63 6f 64 65 20 7b 53 45 4c 45 43  tcl>.code {SELEC
3200: 54 20 70 72 69 63 65 20 46 52 4f 4d 20 66 72 75  T price FROM fru
3210: 69 74 73 66 6f 72 73 61 6c 65 20 57 48 45 52 45  itsforsale WHERE
3220: 20 66 72 75 69 74 3d 27 4f 72 61 6e 67 65 27 20   fruit='Orange' 
3230: 41 4e 44 20 73 74 61 74 65 3d 27 43 41 27 7d 0a  AND state='CA'}.
3240: 66 69 67 75 72 65 20 31 31 20 23 66 69 67 31 31  figure 11 #fig11
3250: 20 69 64 78 33 6c 75 31 2e 67 69 66 20 7b 4c 6f   idx3lu1.gif {Lo
3260: 6f 6b 75 70 20 55 73 69 6e 67 20 41 20 54 77 6f  okup Using A Two
3270: 2d 43 6f 6c 75 6d 6e 20 49 6e 64 65 78 7d 0a 3c  -Column Index}.<
3280: 2f 74 63 6c 3e 0a 0a 3c 70 3e 0a 57 69 74 68 20  /tcl>..<p>.With 
3290: 74 68 65 20 49 64 78 33 20 69 6e 64 65 78 20 6f  the Idx3 index o
32a0: 6e 20 62 6f 74 68 20 63 6f 6c 75 6d 6e 73 20 74  n both columns t
32b0: 68 61 74 20 61 72 65 20 63 6f 6e 73 74 72 61 69  hat are constrai
32c0: 6e 65 64 20 62 79 20 74 68 65 20 57 48 45 52 45  ned by the WHERE
32d0: 20 63 6c 61 75 73 65 2c 0a 53 51 4c 69 74 65 20   clause,.SQLite 
32e0: 63 61 6e 20 64 6f 20 61 20 73 69 6e 67 6c 65 20  can do a single 
32f0: 62 69 6e 61 72 79 20 73 65 61 72 63 68 20 61 67  binary search ag
3300: 61 69 6e 73 74 20 49 64 78 33 20 74 6f 20 66 69  ainst Idx3 to fi
3310: 6e 64 20 74 68 65 20 6f 6e 65 20 72 6f 77 69 64  nd the one rowid
3320: 0a 66 6f 72 20 43 61 6c 69 66 6f 72 6e 69 61 20  .for California 
3330: 6f 72 61 6e 67 65 73 2c 20 74 68 65 6e 20 64 6f  oranges, then do
3340: 20 61 20 73 69 6e 67 6c 65 20 62 69 6e 61 72 79   a single binary
3350: 20 73 65 61 72 63 68 20 74 6f 20 66 69 6e 64 20   search to find 
3360: 74 68 65 20 70 72 69 63 65 0a 66 6f 72 20 74 68  the price.for th
3370: 61 74 20 69 74 65 6d 20 69 6e 20 74 68 65 20 6f  at item in the o
3380: 72 69 67 69 6e 61 6c 20 74 61 62 6c 65 2e 20 20  riginal table.  
3390: 54 68 65 72 65 20 61 72 65 20 6e 6f 20 64 65 61  There are no dea
33a0: 64 2d 65 6e 64 73 20 61 6e 64 20 6e 6f 0a 77 61  d-ends and no.wa
33b0: 73 74 65 64 20 62 69 6e 61 72 79 20 73 65 61 72  sted binary sear
33c0: 63 68 65 73 2e 20 20 54 68 69 73 20 69 73 20 61  ches.  This is a
33d0: 20 6d 6f 72 65 20 65 66 66 69 63 69 65 6e 74 20   more efficient 
33e0: 71 75 65 72 79 2e 0a 3c 2f 70 3e 0a 0a 3c 70 3e  query..</p>..<p>
33f0: 0a 4e 6f 74 65 20 74 68 61 74 20 49 64 78 33 20  .Note that Idx3 
3400: 63 6f 6e 74 61 69 6e 73 20 61 6c 6c 20 74 68 65  contains all the
3410: 20 73 61 6d 65 20 69 6e 66 6f 72 6d 61 74 69 6f   same informatio
3420: 6e 20 61 73 20 74 68 65 20 6f 72 69 67 69 6e 61  n as the origina
3430: 6c 20 0a 3c 61 20 68 72 65 66 3d 22 23 66 69 67  l .<a href="#fig
3440: 33 22 3e 49 64 78 31 3c 2f 61 3e 2e 20 20 41 6e  3">Idx1</a>.  An
3450: 64 20 73 6f 20 69 66 20 77 65 20 68 61 76 65 20  d so if we have 
3460: 49 64 78 33 2c 20 77 65 20 64 6f 20 6e 6f 74 20  Idx3, we do not 
3470: 72 65 61 6c 6c 79 20 6e 65 65 64 20 49 64 78 31  really need Idx1
3480: 0a 61 6e 79 20 6d 6f 72 65 2e 20 20 54 68 65 20  .any more.  The 
3490: 22 70 72 69 63 65 20 6f 66 20 70 65 61 63 68 65  "price of peache
34a0: 73 22 20 71 75 65 72 79 20 63 61 6e 20 62 65 20  s" query can be 
34b0: 73 61 74 69 73 66 69 65 64 20 75 73 69 6e 67 20  satisfied using 
34c0: 49 64 78 33 0a 62 79 20 73 69 6d 70 6c 79 20 69  Idx3.by simply i
34d0: 67 6e 6f 72 69 6e 67 20 74 68 65 20 22 73 74 61  gnoring the "sta
34e0: 74 65 22 20 63 6f 6c 75 6d 6e 20 6f 66 20 49 64  te" column of Id
34f0: 78 33 3a 0a 3c 2f 70 3e 0a 0a 3c 74 63 6c 3e 0a  x3:.</p>..<tcl>.
3500: 63 6f 64 65 20 7b 53 45 4c 45 43 54 20 70 72 69  code {SELECT pri
3510: 63 65 20 46 52 4f 4d 20 66 72 75 69 74 73 66 6f  ce FROM fruitsfo
3520: 72 73 61 6c 65 20 57 48 45 52 45 20 66 72 75 69  rsale WHERE frui
3530: 74 3d 27 50 65 61 63 68 27 7d 0a 66 69 67 75 72  t='Peach'}.figur
3540: 65 20 31 32 20 23 66 69 67 31 32 20 69 64 78 33  e 12 #fig12 idx3
3550: 6c 75 32 2e 67 69 66 20 7b 53 69 6e 67 6c 65 2d  lu2.gif {Single-
3560: 43 6f 6c 75 6d 6e 20 4c 6f 6f 6b 75 70 20 4f 6e  Column Lookup On
3570: 20 41 20 4d 75 6c 74 69 2d 43 6f 6c 75 6d 6e 20   A Multi-Column 
3580: 49 6e 64 65 78 7d 0a 3c 2f 74 63 6c 3e 0a 0a 3c  Index}.</tcl>..<
3590: 70 3e 0a 48 65 6e 63 65 2c 20 61 20 67 6f 6f 64  p>.Hence, a good
35a0: 20 72 75 6c 65 20 6f 66 20 74 68 75 6d 62 20 69   rule of thumb i
35b0: 73 20 74 68 61 74 20 79 6f 75 72 20 64 61 74 61  s that your data
35c0: 62 61 73 65 20 73 63 68 65 6d 61 20 73 68 6f 75  base schema shou
35d0: 6c 64 20 6e 65 76 65 72 0a 63 6f 6e 74 61 69 6e  ld never.contain
35e0: 20 74 77 6f 20 69 6e 64 69 63 65 73 20 77 68 65   two indices whe
35f0: 72 65 20 6f 6e 65 20 69 6e 64 65 78 20 69 73 20  re one index is 
3600: 61 20 70 72 65 66 69 78 20 6f 66 20 74 68 65 20  a prefix of the 
3610: 6f 74 68 65 72 2e 20 20 44 72 6f 70 20 74 68 65  other.  Drop the
3620: 0a 69 6e 64 65 78 20 77 69 74 68 20 66 65 77 65  .index with fewe
3630: 72 20 63 6f 6c 75 6d 6e 73 2e 20 20 53 51 4c 69  r columns.  SQLi
3640: 74 65 20 77 69 6c 6c 20 73 74 69 6c 6c 20 62 65  te will still be
3650: 20 61 62 6c 65 20 74 6f 20 64 6f 20 65 66 66 69   able to do effi
3660: 63 69 65 6e 74 0a 6c 6f 6f 6b 75 70 73 20 77 69  cient.lookups wi
3670: 74 68 20 74 68 65 20 6c 6f 6e 67 65 72 20 69 6e  th the longer in
3680: 64 65 78 2e 0a 3c 2f 70 3e 0a 0a 3c 74 63 6c 3e  dex..</p>..<tcl>
3690: 68 64 5f 66 72 61 67 6d 65 6e 74 20 63 6f 76 69  hd_fragment covi
36a0: 64 78 20 7b 63 6f 76 65 72 69 6e 67 20 69 6e 64  dx {covering ind
36b0: 65 78 7d 20 7b 63 6f 76 65 72 69 6e 67 20 69 6e  ex} {covering in
36c0: 64 69 63 65 73 7d 3c 2f 74 63 6c 3e 0a 3c 68 33  dices}</tcl>.<h3
36d0: 3e 31 2e 37 20 43 6f 76 65 72 69 6e 67 20 49 6e  >1.7 Covering In
36e0: 64 69 63 65 73 3c 2f 68 33 3e 0a 0a 3c 70 3e 0a  dices</h3>..<p>.
36f0: 54 68 65 20 22 70 72 69 63 65 20 6f 66 20 43 61  The "price of Ca
3700: 6c 69 66 6f 72 6e 69 61 20 6f 72 61 6e 67 65 73  lifornia oranges
3710: 22 20 71 75 65 72 79 20 77 61 73 20 6d 61 64 65  " query was made
3720: 20 6d 6f 72 65 20 65 66 66 69 63 69 65 6e 74 20   more efficient 
3730: 74 68 72 6f 75 67 68 0a 74 68 65 20 75 73 65 20  through.the use 
3740: 6f 66 20 61 20 74 77 6f 2d 63 6f 6c 75 6d 6e 20  of a two-column 
3750: 69 6e 64 65 78 2e 20 20 42 75 74 20 53 51 4c 69  index.  But SQLi
3760: 74 65 20 63 61 6e 20 64 6f 20 65 76 65 6e 20 62  te can do even b
3770: 65 74 74 65 72 20 77 69 74 68 20 61 0a 74 68 72  etter with a.thr
3780: 65 65 2d 63 6f 6c 75 6d 6e 20 69 6e 64 65 78 20  ee-column index 
3790: 74 68 61 74 20 61 6c 73 6f 20 69 6e 63 6c 75 64  that also includ
37a0: 65 73 20 74 68 65 20 22 70 72 69 63 65 22 20 63  es the "price" c
37b0: 6f 6c 75 6d 6e 3a 0a 3c 2f 70 3e 0a 0a 3c 74 63  olumn:.</p>..<tc
37c0: 6c 3e 0a 63 6f 64 65 20 7b 43 52 45 41 54 45 20  l>.code {CREATE 
37d0: 49 4e 44 45 58 20 49 64 78 34 20 4f 4e 20 46 72  INDEX Idx4 ON Fr
37e0: 75 69 74 73 46 6f 72 53 61 6c 65 28 66 72 75 69  uitsForSale(frui
37f0: 74 2c 20 73 74 61 74 65 2c 20 70 72 69 63 65 29  t, state, price)
3800: 3b 7d 0a 66 69 67 75 72 65 20 31 33 20 23 66 69  ;}.figure 13 #fi
3810: 67 31 33 20 69 64 78 34 2e 67 69 66 20 7b 41 20  g13 idx4.gif {A 
3820: 43 6f 76 65 72 69 6e 67 20 49 6e 64 65 78 7d 0a  Covering Index}.
3830: 3c 2f 74 63 6c 3e 0a 0a 3c 70 3e 0a 54 68 69 73  </tcl>..<p>.This
3840: 20 6e 65 77 20 69 6e 64 65 78 20 63 6f 6e 74 61   new index conta
3850: 69 6e 73 20 61 6c 6c 20 74 68 65 20 63 6f 6c 75  ins all the colu
3860: 6d 6e 73 20 6f 66 20 74 68 65 20 6f 72 69 67 69  mns of the origi
3870: 6e 61 6c 20 46 72 75 69 74 73 46 6f 72 53 61 6c  nal FruitsForSal
3880: 65 20 74 61 62 6c 65 20 74 68 61 74 0a 61 72 65  e table that.are
3890: 20 75 73 65 64 20 62 79 20 74 68 65 20 71 75 65   used by the que
38a0: 72 79 20 2d 20 62 6f 74 68 20 74 68 65 20 73 65  ry - both the se
38b0: 61 72 63 68 20 74 65 72 6d 73 20 61 6e 64 20 74  arch terms and t
38c0: 68 65 20 6f 75 74 70 75 74 2e 20 20 57 65 20 63  he output.  We c
38d0: 61 6c 6c 0a 74 68 69 73 20 61 20 22 63 6f 76 65  all.this a "cove
38e0: 72 69 6e 67 20 69 6e 64 65 78 22 2e 20 20 42 65  ring index".  Be
38f0: 63 61 75 73 65 20 61 6c 6c 20 6f 66 20 74 68 65  cause all of the
3900: 20 69 6e 66 6f 72 6d 61 74 69 6f 6e 20 6e 65 65   information nee
3910: 64 65 64 20 69 73 20 69 6e 0a 74 68 65 20 63 6f  ded is in.the co
3920: 76 65 72 69 6e 67 20 69 6e 64 65 78 2c 20 53 51  vering index, SQ
3930: 4c 69 74 65 20 6e 65 76 65 72 20 6e 65 65 64 73  Lite never needs
3940: 20 74 6f 20 63 6f 6e 73 75 6c 74 20 74 68 65 20   to consult the 
3950: 6f 72 69 67 69 6e 61 6c 20 74 61 62 6c 65 0a 69  original table.i
3960: 6e 20 6f 72 64 65 72 20 74 6f 20 66 69 6e 64 20  n order to find 
3970: 74 68 65 20 70 72 69 63 65 2e 0a 3c 2f 70 3e 0a  the price..</p>.
3980: 0a 3c 74 63 6c 3e 0a 63 6f 64 65 20 7b 53 45 4c  .<tcl>.code {SEL
3990: 45 43 54 20 70 72 69 63 65 20 46 52 4f 4d 20 66  ECT price FROM f
39a0: 72 75 69 74 73 66 6f 72 73 61 6c 65 20 57 48 45  ruitsforsale WHE
39b0: 52 45 20 66 72 75 69 74 3d 27 4f 72 61 6e 67 65  RE fruit='Orange
39c0: 27 20 41 4e 44 20 73 74 61 74 65 3d 27 43 41 27  ' AND state='CA'
39d0: 3b 7d 0a 66 69 67 75 72 65 20 31 34 20 23 66 69  ;}.figure 14 #fi
39e0: 67 31 34 20 69 64 78 34 6c 75 31 2e 67 69 66 20  g14 idx4lu1.gif 
39f0: 7b 51 75 65 72 79 20 55 73 69 6e 67 20 41 20 43  {Query Using A C
3a00: 6f 76 65 72 69 6e 67 20 49 6e 64 65 78 7d 0a 3c  overing Index}.<
3a10: 2f 74 63 6c 3e 0a 0a 3c 70 3e 0a 48 65 6e 63 65  /tcl>..<p>.Hence
3a20: 2c 20 62 79 20 61 64 64 69 6e 67 20 65 78 74 72  , by adding extr
3a30: 61 20 22 6f 75 74 70 75 74 22 20 63 6f 6c 75 6d  a "output" colum
3a40: 6e 73 20 6f 6e 74 6f 20 74 68 65 20 65 6e 64 20  ns onto the end 
3a50: 6f 66 20 61 6e 20 69 6e 64 65 78 2c 20 6f 6e 65  of an index, one
3a60: 0a 63 61 6e 20 61 76 6f 69 64 20 68 61 76 69 6e  .can avoid havin
3a70: 67 20 74 6f 20 72 65 66 65 72 65 6e 63 65 20 74  g to reference t
3a80: 68 65 20 6f 72 69 67 69 6e 61 6c 20 74 61 62 6c  he original tabl
3a90: 65 20 61 6e 64 20 74 68 65 72 65 62 79 0a 63 75  e and thereby.cu
3aa0: 74 20 74 68 65 20 6e 75 6d 62 65 72 20 6f 66 20  t the number of 
3ab0: 62 69 6e 61 72 79 20 73 65 61 72 63 68 65 73 20  binary searches 
3ac0: 66 6f 72 20 61 20 71 75 65 72 79 20 69 6e 20 68  for a query in h
3ad0: 61 6c 66 2e 20 20 54 68 69 73 20 69 73 20 61 0a  alf.  This is a.
3ae0: 63 6f 6e 73 74 61 6e 74 2d 66 61 63 74 6f 72 20  constant-factor 
3af0: 69 6d 70 72 6f 76 65 6d 65 6e 74 20 69 6e 20 70  improvement in p
3b00: 65 72 66 6f 72 6d 61 6e 63 65 20 28 72 6f 75 67  erformance (roug
3b10: 68 6c 79 20 61 20 64 6f 75 62 6c 69 6e 67 20 6f  hly a doubling o
3b20: 66 0a 74 68 65 20 73 70 65 65 64 29 2e 20 20 42  f.the speed).  B
3b30: 75 74 20 6f 6e 20 74 68 65 20 6f 74 68 65 72 20  ut on the other 
3b40: 68 61 6e 64 2c 20 69 74 20 69 73 20 61 6c 73 6f  hand, it is also
3b50: 20 6a 75 73 74 20 61 20 72 65 66 69 6e 65 6d 65   just a refineme
3b60: 6e 74 3b 0a 41 20 74 77 6f 2d 66 6f 6c 64 20 70  nt;.A two-fold p
3b70: 65 72 66 6f 72 6d 61 6e 63 65 20 69 6e 63 72 65  erformance incre
3b80: 61 73 65 20 69 73 20 6e 6f 74 20 6e 65 61 72 6c  ase is not nearl
3b90: 79 20 61 73 20 64 72 61 6d 61 74 69 63 20 61 73  y as dramatic as
3ba0: 20 74 68 65 0a 6f 6e 65 2d 6d 69 6c 6c 69 6f 6e   the.one-million
3bb0: 2d 66 6f 6c 64 20 69 6e 63 72 65 61 73 65 20 73  -fold increase s
3bc0: 65 65 6e 20 77 68 65 6e 20 74 68 65 20 74 61 62  een when the tab
3bd0: 6c 65 20 77 61 73 20 66 69 72 73 74 20 69 6e 64  le was first ind
3be0: 65 78 65 64 2e 0a 41 6e 64 20 66 6f 72 20 6d 6f  exed..And for mo
3bf0: 73 74 20 71 75 65 72 69 65 73 2c 20 74 68 65 20  st queries, the 
3c00: 64 69 66 66 65 72 65 6e 63 65 20 62 65 74 77 65  difference betwe
3c10: 65 6e 20 31 20 6d 69 63 72 6f 73 65 63 6f 6e 64  en 1 microsecond
3c20: 20 61 6e 64 0a 32 20 6d 69 63 72 6f 73 65 63 6f   and.2 microseco
3c30: 6e 64 73 20 69 73 20 75 6e 6c 69 6b 65 6c 79 20  nds is unlikely 
3c40: 74 6f 20 62 65 20 6e 6f 74 69 63 65 64 2e 0a 3c  to be noticed..<
3c50: 2f 70 3e 0a 0a 3c 74 63 6c 3e 68 64 5f 66 72 61  /p>..<tcl>hd_fra
3c60: 67 6d 65 6e 74 20 6f 72 5f 69 6e 5f 77 68 65 72  gment or_in_wher
3c70: 65 20 6f 72 2d 63 6f 6e 6e 65 63 74 65 64 2d 74  e or-connected-t
3c80: 65 72 6d 73 3c 2f 74 63 6c 3e 0a 3c 68 33 3e 31  erms</tcl>.<h3>1
3c90: 2e 38 20 4f 52 2d 43 6f 6e 6e 65 63 74 65 64 20  .8 OR-Connected 
3ca0: 54 65 72 6d 73 20 49 6e 20 54 68 65 20 57 48 45  Terms In The WHE
3cb0: 52 45 20 43 6c 61 75 73 65 3c 2f 68 33 3e 0a 0a  RE Clause</h3>..
3cc0: 3c 70 3e 0a 4d 75 6c 74 69 2d 63 6f 6c 75 6d 6e  <p>.Multi-column
3cd0: 20 69 6e 64 69 63 65 73 20 6f 6e 6c 79 20 77 6f   indices only wo
3ce0: 72 6b 20 69 66 20 74 68 65 20 63 6f 6e 73 74 72  rk if the constr
3cf0: 61 69 6e 74 20 74 65 72 6d 73 20 69 6e 20 74 68  aint terms in th
3d00: 65 20 57 48 45 52 45 0a 63 6c 61 75 73 65 20 6f  e WHERE.clause o
3d10: 66 20 74 68 65 20 71 75 65 72 79 20 61 72 65 20  f the query are 
3d20: 63 6f 6e 6e 65 63 74 65 64 20 62 79 20 41 4e 44  connected by AND
3d30: 2e 0a 53 6f 20 49 64 78 33 20 61 6e 64 20 49 64  ..So Idx3 and Id
3d40: 78 34 20 61 72 65 20 68 65 6c 70 66 75 6c 20 77  x4 are helpful w
3d50: 68 65 6e 20 74 68 65 20 73 65 61 72 63 68 20 69  hen the search i
3d60: 73 20 66 6f 72 20 69 74 65 6d 73 20 74 68 61 74  s for items that
3d70: 0a 61 72 65 20 62 6f 74 68 20 4f 72 61 6e 67 65  .are both Orange
3d80: 73 20 61 6e 64 20 67 72 6f 77 6e 20 69 6e 20 43  s and grown in C
3d90: 61 6c 69 66 6f 72 6e 69 61 2c 20 62 75 74 20 6e  alifornia, but n
3da0: 65 69 74 68 65 72 20 69 6e 64 65 78 20 77 6f 75  either index wou
3db0: 6c 64 0a 62 65 20 74 68 61 74 20 75 73 65 66 75  ld.be that usefu
3dc0: 6c 20 69 66 20 77 65 20 77 61 6e 74 65 64 20 61  l if we wanted a
3dd0: 6c 6c 20 69 74 65 6d 73 20 74 68 61 74 20 77 65  ll items that we
3de0: 72 65 20 65 69 74 68 65 72 20 6f 72 61 6e 67 65  re either orange
3df0: 73 0a 3c 69 3e 6f 72 3c 2f 69 3e 20 61 72 65 20  s.<i>or</i> are 
3e00: 67 72 6f 77 6e 20 69 6e 20 43 61 6c 69 66 6f 72  grown in Califor
3e10: 6e 69 61 2e 0a 3c 2f 70 3e 0a 0a 3c 74 63 6c 3e  nia..</p>..<tcl>
3e20: 63 6f 64 65 20 7b 0a 53 45 4c 45 43 54 20 70 72  code {.SELECT pr
3e30: 69 63 65 20 46 52 4f 4d 20 46 72 75 69 74 73 46  ice FROM FruitsF
3e40: 6f 72 53 61 6c 65 20 57 48 45 52 45 20 66 72 75  orSale WHERE fru
3e50: 69 74 3d 27 4f 72 61 6e 67 65 27 20 4f 52 20 73  it='Orange' OR s
3e60: 74 61 74 65 3d 27 43 41 27 3b 0a 7d 3c 2f 74 63  tate='CA';.}</tc
3e70: 6c 3e 0a 0a 3c 70 3e 0a 57 68 65 6e 20 63 6f 6e  l>..<p>.When con
3e80: 66 72 6f 6e 74 65 64 20 77 69 74 68 20 4f 52 2d  fronted with OR-
3e90: 63 6f 6e 6e 65 63 74 65 64 20 74 65 72 6d 73 20  connected terms 
3ea0: 69 6e 20 61 20 57 48 45 52 45 20 63 6c 61 75 73  in a WHERE claus
3eb0: 65 2c 20 53 51 4c 69 74 65 20 0a 65 78 61 6d 69  e, SQLite .exami
3ec0: 6e 65 73 20 65 61 63 68 20 4f 52 20 74 65 72 6d  nes each OR term
3ed0: 20 73 65 70 61 72 61 74 65 6c 79 20 61 6e 64 20   separately and 
3ee0: 74 72 69 65 73 20 74 6f 20 75 73 65 20 61 6e 20  tries to use an 
3ef0: 69 6e 64 65 78 20 74 6f 0a 66 69 6e 64 20 74 68  index to.find th
3f00: 65 20 72 6f 77 69 64 73 20 61 73 73 6f 63 69 61  e rowids associa
3f10: 74 65 64 20 77 69 74 68 20 65 61 63 68 20 74 65  ted with each te
3f20: 72 6d 2e 0a 49 74 20 74 68 65 6e 20 74 61 6b 65  rm..It then take
3f30: 73 20 74 68 65 20 75 6e 69 6f 6e 20 6f 66 20 74  s the union of t
3f40: 68 65 20 72 65 73 75 6c 74 69 6e 67 20 72 6f 77  he resulting row
3f50: 69 64 20 73 65 74 73 20 74 6f 20 66 69 6e 64 0a  id sets to find.
3f60: 74 68 65 20 65 6e 64 20 72 65 73 75 6c 74 2e 20  the end result. 
3f70: 20 54 68 65 20 66 6f 6c 6c 6f 77 69 6e 67 20 66   The following f
3f80: 69 67 75 72 65 20 69 6c 6c 75 73 74 72 61 74 65  igure illustrate
3f90: 73 20 74 68 69 73 20 70 72 6f 63 65 73 73 3a 0a  s this process:.
3fa0: 3c 2f 70 3e 0a 0a 3c 74 63 6c 3e 66 69 67 75 72  </p>..<tcl>figur
3fb0: 65 20 31 35 20 23 66 69 67 31 35 20 6f 72 71 75  e 15 #fig15 orqu
3fc0: 65 72 79 2e 67 69 66 20 7b 51 75 65 72 79 20 57  ery.gif {Query W
3fd0: 69 74 68 20 4f 52 20 43 6f 6e 73 74 72 61 69 6e  ith OR Constrain
3fe0: 74 73 7d 3c 2f 74 63 6c 3e 0a 0a 3c 70 3e 0a 54  ts}</tcl>..<p>.T
3ff0: 68 65 20 64 69 61 67 72 61 6d 20 61 62 6f 76 65  he diagram above
4000: 20 69 6d 70 6c 69 65 73 20 74 68 61 74 20 53 51   implies that SQ
4010: 4c 69 74 65 20 63 6f 6d 70 75 74 65 73 20 61 6c  Lite computes al
4020: 6c 20 6f 66 20 74 68 65 20 72 6f 77 69 64 73 20  l of the rowids 
4030: 66 69 72 73 74 0a 61 6e 64 20 74 68 65 6e 20 63  first.and then c
4040: 6f 6d 62 69 6e 65 73 20 74 68 65 6d 20 77 69 74  ombines them wit
4050: 68 20 61 20 75 6e 69 6f 6e 20 6f 70 65 72 61 74  h a union operat
4060: 69 6f 6e 20 62 65 66 6f 72 65 20 73 74 61 72 74  ion before start
4070: 69 6e 67 20 74 6f 20 64 6f 0a 72 6f 77 69 64 20  ing to do.rowid 
4080: 6c 6f 6f 6b 75 70 73 20 6f 6e 20 74 68 65 20 6f  lookups on the o
4090: 72 69 67 69 6e 61 6c 20 74 61 62 6c 65 2e 20 20  riginal table.  
40a0: 49 6e 20 72 65 61 6c 69 74 79 2c 20 74 68 65 20  In reality, the 
40b0: 72 6f 77 69 64 20 6c 6f 6f 6b 75 70 73 0a 61 72  rowid lookups.ar
40c0: 65 20 69 6e 74 65 72 73 70 65 72 73 65 64 20 77  e interspersed w
40d0: 69 74 68 20 72 6f 77 69 64 20 63 6f 6d 70 75 74  ith rowid comput
40e0: 61 74 69 6f 6e 73 2e 20 20 53 51 4c 69 74 65 20  ations.  SQLite 
40f0: 75 73 65 73 20 6f 6e 65 20 69 6e 64 65 78 20 61  uses one index a
4100: 74 0a 61 20 74 69 6d 65 20 74 6f 20 66 69 6e 64  t.a time to find
4110: 20 72 6f 77 69 64 73 20 77 68 69 6c 65 20 72 65   rowids while re
4120: 6d 65 6d 62 65 72 69 6e 67 20 77 68 69 63 68 20  membering which 
4130: 72 6f 77 69 64 73 20 69 74 20 68 61 73 20 73 65  rowids it has se
4140: 65 6e 0a 62 65 66 6f 72 65 20 73 6f 20 61 73 20  en.before so as 
4150: 74 6f 20 61 76 6f 69 64 20 64 75 70 6c 69 63 61  to avoid duplica
4160: 74 65 73 2e 20 20 54 68 61 74 20 69 73 20 6a 75  tes.  That is ju
4170: 73 74 20 61 6e 20 69 6d 70 6c 65 6d 65 6e 74 61  st an implementa
4180: 74 69 6f 6e 0a 64 65 74 61 69 6c 2c 20 74 68 6f  tion.detail, tho
4190: 75 67 68 2e 20 20 54 68 65 20 64 69 61 67 72 61  ugh.  The diagra
41a0: 6d 2c 20 77 68 69 6c 65 20 6e 6f 74 20 31 30 30  m, while not 100
41b0: 25 20 61 63 63 75 72 61 74 65 2c 20 70 72 6f 76  % accurate, prov
41c0: 69 64 65 73 20 61 20 67 6f 6f 64 0a 6f 76 65 72  ides a good.over
41d0: 76 69 65 77 20 6f 66 20 77 68 61 74 20 69 73 20  view of what is 
41e0: 68 61 70 70 65 6e 69 6e 67 2e 0a 3c 2f 70 3e 0a  happening..</p>.
41f0: 0a 3c 70 3e 0a 49 6e 20 6f 72 64 65 72 20 66 6f  .<p>.In order fo
4200: 72 20 74 68 65 20 4f 52 2d 62 79 2d 55 4e 49 4f  r the OR-by-UNIO
4210: 4e 20 74 65 63 68 6e 69 71 75 65 20 73 68 6f 77  N technique show
4220: 6e 20 61 62 6f 76 65 20 74 6f 20 62 65 20 75 73  n above to be us
4230: 65 66 75 6c 2c 20 74 68 65 72 65 0a 6d 75 73 74  eful, there.must
4240: 20 62 65 20 61 6e 20 69 6e 64 65 78 20 61 76 61   be an index ava
4250: 69 6c 61 62 6c 65 20 74 68 61 74 20 68 65 6c 70  ilable that help
4260: 73 20 72 65 73 6f 6c 76 65 20 65 76 65 72 79 20  s resolve every 
4270: 4f 52 2d 63 6f 6e 6e 65 63 74 65 64 20 74 65 72  OR-connected ter
4280: 6d 0a 69 6e 20 74 68 65 20 57 48 45 52 45 20 63  m.in the WHERE c
4290: 6c 61 75 73 65 2e 20 20 49 66 20 65 76 65 6e 20  lause.  If even 
42a0: 61 20 73 69 6e 67 6c 65 20 4f 52 2d 63 6f 6e 6e  a single OR-conn
42b0: 65 63 74 65 64 20 74 65 72 6d 20 69 73 20 6e 6f  ected term is no
42c0: 74 20 69 6e 64 65 78 65 64 2c 0a 74 68 65 6e 20  t indexed,.then 
42d0: 61 20 66 75 6c 6c 20 74 61 62 6c 65 20 73 63 61  a full table sca
42e0: 6e 20 77 6f 75 6c 64 20 68 61 76 65 20 74 6f 20  n would have to 
42f0: 62 65 20 64 6f 6e 65 20 69 6e 20 6f 72 64 65 72  be done in order
4300: 20 74 6f 20 66 69 6e 64 20 74 68 65 20 72 6f 77   to find the row
4310: 69 64 73 0a 67 65 6e 65 72 61 74 65 64 20 62 79  ids.generated by
4320: 20 74 68 65 20 6f 6e 65 20 74 65 72 6d 2c 20 61   the one term, a
4330: 6e 64 20 69 66 20 53 51 4c 69 74 65 20 68 61 73  nd if SQLite has
4340: 20 74 6f 20 64 6f 20 61 20 66 75 6c 6c 20 74 61   to do a full ta
4350: 62 6c 65 20 73 63 61 6e 2c 20 69 74 0a 6d 69 67  ble scan, it.mig
4360: 68 74 20 61 73 20 77 65 6c 6c 20 64 6f 20 69 74  ht as well do it
4370: 20 6f 6e 20 74 68 65 20 6f 72 69 67 69 6e 61 6c   on the original
4380: 20 74 61 62 6c 65 20 61 6e 64 20 67 65 74 20 61   table and get a
4390: 6c 6c 20 6f 66 20 74 68 65 20 72 65 73 75 6c 74  ll of the result
43a0: 73 20 69 6e 0a 61 20 73 69 6e 67 6c 65 20 70 61  s in.a single pa
43b0: 73 73 20 77 69 74 68 6f 75 74 20 68 61 76 69 6e  ss without havin
43c0: 67 20 74 6f 20 6d 65 73 73 20 77 69 74 68 20 75  g to mess with u
43d0: 6e 69 6f 6e 20 6f 70 65 72 61 74 69 6f 6e 73 20  nion operations 
43e0: 61 6e 64 20 66 6f 6c 6c 6f 77 2d 6f 6e 0a 62 69  and follow-on.bi
43f0: 6e 61 72 79 20 73 65 61 72 63 68 65 73 2e 0a 3c  nary searches..<
4400: 2f 70 3e 0a 0a 3c 70 3e 0a 4f 6e 65 20 63 61 6e  /p>..<p>.One can
4410: 20 73 65 65 20 68 6f 77 20 74 68 65 20 4f 52 2d   see how the OR-
4420: 62 79 2d 55 4e 49 4f 4e 20 74 65 63 68 6e 69 71  by-UNION techniq
4430: 75 65 20 63 6f 75 6c 64 20 61 6c 73 6f 20 62 65  ue could also be
4440: 20 6c 65 76 65 72 61 67 65 64 20 74 6f 0a 75 73   leveraged to.us
4450: 65 20 6d 75 6c 74 69 70 6c 65 20 69 6e 64 69 63  e multiple indic
4460: 65 73 20 6f 6e 20 71 75 65 72 69 65 73 20 77 68  es on queries wh
4470: 65 72 65 20 74 68 65 20 57 48 45 52 45 20 63 6c  ere the WHERE cl
4480: 61 75 73 65 20 68 61 73 20 74 65 72 6d 73 20 63  ause has terms c
4490: 6f 6e 6e 65 63 74 65 64 0a 62 79 20 41 4e 44 2c  onnected.by AND,
44a0: 20 62 79 20 75 73 69 6e 67 20 61 6e 20 69 6e 74   by using an int
44b0: 65 72 73 65 63 74 20 6f 70 65 72 61 74 6f 72 20  ersect operator 
44c0: 69 6e 20 70 6c 61 63 65 20 6f 66 20 75 6e 69 6f  in place of unio
44d0: 6e 2e 20 20 4d 61 6e 79 20 53 51 4c 0a 64 61 74  n.  Many SQL.dat
44e0: 61 62 61 73 65 20 65 6e 67 69 6e 65 73 20 77 69  abase engines wi
44f0: 6c 6c 20 64 6f 20 6a 75 73 74 20 74 68 61 74 2e  ll do just that.
4500: 20 20 42 75 74 20 74 68 65 20 70 65 72 66 6f 72    But the perfor
4510: 6d 61 6e 63 65 20 67 61 69 6e 20 6f 76 65 72 20  mance gain over 
4520: 75 73 69 6e 67 0a 6a 75 73 74 20 61 20 73 69 6e  using.just a sin
4530: 67 6c 65 20 69 6e 64 65 78 20 69 73 20 73 6c 69  gle index is sli
4540: 67 68 74 20 61 6e 64 20 73 6f 20 53 51 4c 69 74  ght and so SQLit
4550: 65 20 64 6f 65 73 20 6e 6f 74 20 69 6d 70 6c 65  e does not imple
4560: 6d 65 6e 74 20 74 68 61 74 20 74 65 63 68 6e 69  ment that techni
4570: 71 75 65 0a 61 74 20 74 68 69 73 20 74 69 6d 65  que.at this time
4580: 2e 20 20 48 6f 77 65 76 65 72 2c 20 61 20 66 75  .  However, a fu
4590: 74 75 72 65 20 76 65 72 73 69 6f 6e 20 53 51 4c  ture version SQL
45a0: 69 74 65 20 6d 69 67 68 74 20 62 65 20 65 6e 68  ite might be enh
45b0: 61 6e 63 65 64 20 74 6f 20 73 75 70 70 6f 72 74  anced to support
45c0: 0a 41 4e 44 2d 62 79 2d 49 4e 54 45 52 53 45 43  .AND-by-INTERSEC
45d0: 54 2e 0a 3c 2f 70 3e 0a 0a 3c 74 63 6c 3e 68 64  T..</p>..<tcl>hd
45e0: 5f 66 72 61 67 6d 65 6e 74 20 73 6f 72 74 69 6e  _fragment sortin
45f0: 67 20 73 6f 72 74 69 6e 67 3c 2f 74 63 6c 3e 0a  g sorting</tcl>.
4600: 3c 68 32 3e 32 2e 30 20 53 6f 72 74 69 6e 67 3c  <h2>2.0 Sorting<
4610: 2f 68 32 3e 0a 0a 3c 70 3e 0a 53 51 4c 69 74 65  /h2>..<p>.SQLite
4620: 20 28 6c 69 6b 65 20 61 6c 6c 20 6f 74 68 65 72   (like all other
4630: 20 53 51 4c 20 64 61 74 61 62 61 73 65 20 65 6e   SQL database en
4640: 67 69 6e 65 73 29 20 63 61 6e 20 61 6c 73 6f 20  gines) can also 
4650: 75 73 65 20 69 6e 64 69 63 65 73 20 74 6f 0a 73  use indices to.s
4660: 61 74 69 73 66 79 20 74 68 65 20 4f 52 44 45 52  atisfy the ORDER
4670: 20 42 59 20 63 6c 61 75 73 65 73 20 69 6e 20 61   BY clauses in a
4680: 20 71 75 65 72 79 2c 20 69 6e 20 61 64 64 69 74   query, in addit
4690: 69 6f 6e 20 74 6f 20 65 78 70 65 64 69 74 69 6e  ion to expeditin
46a0: 67 0a 6c 6f 6f 6b 75 70 2e 20 20 49 6e 20 6f 74  g.lookup.  In ot
46b0: 68 65 72 20 77 6f 72 64 73 2c 20 69 6e 64 69 63  her words, indic
46c0: 65 73 20 63 61 6e 20 62 65 20 75 73 65 64 20 74  es can be used t
46d0: 6f 20 73 70 65 65 64 20 75 70 20 73 6f 72 74 69  o speed up sorti
46e0: 6e 67 20 61 73 0a 77 65 6c 6c 20 61 73 20 73 65  ng as.well as se
46f0: 61 72 63 68 69 6e 67 2e 0a 3c 2f 70 3e 0a 0a 3c  arching..</p>..<
4700: 70 3e 0a 57 68 65 6e 20 6e 6f 20 61 70 70 72 6f  p>.When no appro
4710: 70 72 69 61 74 65 20 69 6e 64 69 63 65 73 20 61  priate indices a
4720: 72 65 20 61 76 61 69 6c 61 62 6c 65 2c 20 61 20  re available, a 
4730: 71 75 65 72 79 20 77 69 74 68 20 61 6e 20 4f 52  query with an OR
4740: 44 45 52 20 42 59 0a 63 6c 61 75 73 65 20 6d 75  DER BY.clause mu
4750: 73 74 20 62 65 20 73 6f 72 74 65 64 20 61 73 20  st be sorted as 
4760: 61 20 73 65 70 61 72 61 74 65 20 73 74 65 70 2e  a separate step.
4770: 20 20 43 6f 6e 73 69 64 65 72 20 74 68 69 73 20    Consider this 
4780: 71 75 65 72 79 3a 0a 3c 2f 70 3e 0a 0a 3c 74 63  query:.</p>..<tc
4790: 6c 3e 63 6f 64 65 20 7b 53 45 4c 45 43 54 20 2a  l>code {SELECT *
47a0: 20 46 52 4f 4d 20 66 72 75 69 74 73 66 6f 72 73   FROM fruitsfors
47b0: 61 6c 65 20 4f 52 44 45 52 20 42 59 20 66 72 75  ale ORDER BY fru
47c0: 69 74 3b 7d 3c 2f 74 63 6c 3e 0a 0a 3c 70 3e 0a  it;}</tcl>..<p>.
47d0: 53 51 4c 69 74 65 20 70 72 6f 63 65 73 73 65 73  SQLite processes
47e0: 20 74 68 69 73 20 62 79 20 67 61 74 68 65 72 20   this by gather 
47f0: 61 6c 6c 20 74 68 65 20 6f 75 74 70 75 74 20 6f  all the output o
4800: 66 20 71 75 65 72 79 20 61 6e 64 20 74 68 65 6e  f query and then
4810: 0a 72 75 6e 6e 69 6e 67 20 74 68 61 74 20 6f 75  .running that ou
4820: 74 70 75 74 20 74 68 72 6f 75 67 68 20 61 20 73  tput through a s
4830: 6f 72 74 65 72 2e 0a 3c 2f 70 3e 0a 0a 3c 74 63  orter..</p>..<tc
4840: 6c 3e 66 69 67 75 72 65 20 31 36 20 23 66 69 67  l>figure 16 #fig
4850: 31 36 20 6f 62 66 72 75 69 74 6e 6f 69 64 78 2e  16 obfruitnoidx.
4860: 67 69 66 20 7b 53 6f 72 74 69 6e 67 20 57 69 74  gif {Sorting Wit
4870: 68 6f 75 74 20 41 6e 20 49 6e 64 65 78 7d 3c 2f  hout An Index}</
4880: 74 63 6c 3e 0a 0a 3c 70 3e 0a 49 66 20 74 68 65  tcl>..<p>.If the
4890: 20 6e 75 6d 62 65 72 20 6f 66 20 6f 75 74 70 75   number of outpu
48a0: 74 20 72 6f 77 73 20 69 73 20 4b 2c 20 74 68 65  t rows is K, the
48b0: 6e 20 74 68 65 20 74 69 6d 65 20 6e 65 65 64 65  n the time neede
48c0: 64 20 74 6f 20 73 6f 72 74 20 69 73 0a 70 72 6f  d to sort is.pro
48d0: 70 6f 72 74 69 6f 6e 61 6c 20 74 6f 20 4b 6c 6f  portional to Klo
48e0: 67 4b 2e 20 20 49 66 20 4b 20 69 73 20 73 6d 61  gK.  If K is sma
48f0: 6c 6c 2c 20 74 68 65 20 73 6f 72 74 69 6e 67 20  ll, the sorting 
4900: 74 69 6d 65 20 69 73 20 75 73 75 61 6c 6c 79 0a  time is usually.
4910: 6e 6f 74 20 61 20 66 61 63 74 6f 72 2c 20 62 75  not a factor, bu
4920: 74 20 69 6e 20 61 20 71 75 65 72 79 20 73 75 63  t in a query suc
4930: 68 20 61 73 20 74 68 65 20 61 62 6f 76 65 20 77  h as the above w
4940: 68 65 72 65 20 4b 3d 3d 4e 2c 20 74 68 65 20 74  here K==N, the t
4950: 69 6d 65 0a 6e 65 65 64 65 64 20 74 6f 20 73 6f  ime.needed to so
4960: 72 74 20 63 61 6e 20 62 65 20 6d 75 63 68 20 67  rt can be much g
4970: 72 65 61 74 65 72 20 74 68 61 6e 20 74 68 65 20  reater than the 
4980: 74 69 6d 65 20 6e 65 65 64 65 64 20 74 6f 20 64  time needed to d
4990: 6f 20 61 0a 66 75 6c 6c 20 74 61 62 6c 65 20 73  o a.full table s
49a0: 63 61 6e 2e 20 20 46 75 72 74 68 65 72 6d 6f 72  can.  Furthermor
49b0: 65 2c 20 74 68 65 20 65 6e 74 69 72 65 20 6f 75  e, the entire ou
49c0: 74 70 75 74 20 69 73 20 61 63 63 75 6d 75 6c 61  tput is accumula
49d0: 74 65 64 20 69 6e 0a 74 65 6d 70 6f 72 61 72 79  ted in.temporary
49e0: 20 73 74 6f 72 61 67 65 20 28 77 68 69 63 68 20   storage (which 
49f0: 6d 69 67 68 74 20 62 65 20 65 69 74 68 65 72 20  might be either 
4a00: 69 6e 20 6d 61 69 6e 20 6d 65 6d 6f 72 79 20 6f  in main memory o
4a10: 72 20 6f 6e 20 64 69 73 6b 2c 0a 64 65 70 65 6e  r on disk,.depen
4a20: 64 69 6e 67 20 6f 6e 20 76 61 72 69 6f 75 73 20  ding on various 
4a30: 63 6f 6d 70 69 6c 65 2d 74 69 6d 65 20 61 6e 64  compile-time and
4a40: 20 72 75 6e 2d 74 69 6d 65 20 73 65 74 74 69 6e   run-time settin
4a50: 67 73 29 0a 77 68 69 63 68 20 63 61 6e 20 6d 65  gs).which can me
4a60: 61 6e 20 74 68 61 74 20 61 20 6c 6f 74 20 6f 66  an that a lot of
4a70: 20 74 65 6d 70 6f 72 61 72 79 20 73 74 6f 72 61   temporary stora
4a80: 67 65 20 69 73 20 72 65 71 75 69 72 65 64 20 74  ge is required t
4a90: 6f 20 63 6f 6d 70 6c 65 74 65 0a 74 68 65 20 71  o complete.the q
4aa0: 75 65 72 79 2e 0a 3c 2f 70 3e 0a 0a 3c 68 33 3e  uery..</p>..<h3>
4ab0: 32 2e 31 20 53 6f 72 74 69 6e 67 20 42 79 20 52  2.1 Sorting By R
4ac0: 6f 77 69 64 3c 2f 68 33 3e 0a 0a 3c 70 3e 0a 42  owid</h3>..<p>.B
4ad0: 65 63 61 75 73 65 20 73 6f 72 74 69 6e 67 20 63  ecause sorting c
4ae0: 61 6e 20 62 65 20 65 78 70 65 6e 73 69 76 65 2c  an be expensive,
4af0: 20 53 51 4c 69 74 65 20 77 6f 72 6b 73 20 68 61   SQLite works ha
4b00: 72 64 20 74 6f 20 63 6f 6e 76 65 72 74 20 4f 52  rd to convert OR
4b10: 44 45 52 20 42 59 0a 63 6c 61 75 73 65 73 20 69  DER BY.clauses i
4b20: 6e 74 6f 20 6e 6f 2d 6f 70 73 2e 20 20 49 66 20  nto no-ops.  If 
4b30: 53 51 4c 69 74 65 20 64 65 74 65 72 6d 69 6e 65  SQLite determine
4b40: 73 20 74 68 61 74 20 6f 75 74 70 75 74 20 77 69  s that output wi
4b50: 6c 6c 0a 6e 61 74 75 72 61 6c 6c 79 20 61 70 70  ll.naturally app
4b60: 65 61 72 20 69 6e 20 74 68 65 20 6f 72 64 65 72  ear in the order
4b70: 20 73 70 65 63 69 66 69 65 64 2c 20 74 68 65 6e   specified, then
4b80: 20 6e 6f 20 73 6f 72 74 69 6e 67 20 69 73 20 64   no sorting is d
4b90: 6f 6e 65 2e 0a 53 6f 2c 20 66 6f 72 20 65 78 61  one..So, for exa
4ba0: 6d 70 6c 65 2c 20 69 66 20 79 6f 75 20 72 65 71  mple, if you req
4bb0: 75 65 73 74 20 74 68 65 20 6f 75 74 70 75 74 20  uest the output 
4bc0: 69 6e 20 72 6f 77 69 64 20 6f 72 64 65 72 2c 20  in rowid order, 
4bd0: 6e 6f 20 73 6f 72 74 69 6e 67 0a 77 69 6c 6c 20  no sorting.will 
4be0: 62 65 20 64 6f 6e 65 3a 0a 3c 2f 70 3e 0a 0a 3c  be done:.</p>..<
4bf0: 74 63 6c 3e 0a 63 6f 64 65 20 7b 53 45 4c 45 43  tcl>.code {SELEC
4c00: 54 20 2a 20 46 52 4f 4d 20 66 72 75 69 74 73 66  T * FROM fruitsf
4c10: 6f 72 73 61 6c 65 20 4f 52 44 45 52 20 42 59 20  orsale ORDER BY 
4c20: 72 6f 77 69 64 3b 7d 0a 66 69 67 75 72 65 20 31  rowid;}.figure 1
4c30: 37 20 23 66 69 67 31 37 20 6f 62 72 6f 77 69 64  7 #fig17 obrowid
4c40: 2e 67 69 66 20 7b 53 6f 72 74 69 6e 67 20 42 79  .gif {Sorting By
4c50: 20 52 6f 77 69 64 7d 0a 3c 2f 74 63 6c 3e 0a 0a   Rowid}.</tcl>..
4c60: 3c 70 3e 0a 59 6f 75 20 63 61 6e 20 61 6c 73 6f  <p>.You can also
4c70: 20 72 65 71 75 65 73 74 20 61 20 72 65 76 65 72   request a rever
4c80: 73 65 2d 6f 72 64 65 72 20 73 6f 72 74 20 6c 69  se-order sort li
4c90: 6b 65 20 74 68 69 73 3a 0a 3c 2f 70 3e 0a 0a 3c  ke this:.</p>..<
4ca0: 74 63 6c 3e 63 6f 64 65 20 7b 53 45 4c 45 43 54  tcl>code {SELECT
4cb0: 20 2a 20 46 52 4f 4d 20 66 72 75 69 74 73 66 6f   * FROM fruitsfo
4cc0: 72 73 61 6c 65 20 4f 52 44 45 52 20 42 59 20 72  rsale ORDER BY r
4cd0: 6f 77 69 64 20 44 45 53 43 3b 7d 3c 2f 74 63 6c  owid DESC;}</tcl
4ce0: 3e 0a 0a 3c 70 3e 0a 53 51 4c 69 74 65 20 77 69  >..<p>.SQLite wi
4cf0: 6c 6c 20 73 74 69 6c 6c 20 6f 6d 69 74 20 74 68  ll still omit th
4d00: 65 20 73 6f 72 74 69 6e 67 20 73 74 65 70 2e 20  e sorting step. 
4d10: 20 42 75 74 20 69 6e 20 6f 72 64 65 72 20 66 6f   But in order fo
4d20: 72 20 6f 75 74 70 75 74 20 74 6f 0a 61 70 70 65  r output to.appe
4d30: 61 72 20 69 6e 20 74 68 65 20 63 6f 72 72 65 63  ar in the correc
4d40: 74 20 6f 72 64 65 72 2c 20 53 51 4c 69 74 65 20  t order, SQLite 
4d50: 77 69 6c 6c 20 64 6f 20 74 68 65 20 74 61 62 6c  will do the tabl
4d60: 65 20 73 63 61 6e 20 73 74 61 72 74 69 6e 67 20  e scan starting 
4d70: 61 74 0a 74 68 65 20 65 6e 64 20 61 6e 64 20 77  at.the end and w
4d80: 6f 72 6b 69 6e 67 20 74 6f 77 61 72 64 20 74 68  orking toward th
4d90: 65 20 62 65 67 69 6e 6e 69 6e 67 2c 20 72 61 74  e beginning, rat
4da0: 68 65 72 20 74 68 61 6e 20 73 74 61 72 74 69 6e  her than startin
4db0: 67 20 61 74 20 74 68 65 0a 62 65 67 69 6e 6e 69  g at the.beginni
4dc0: 6e 67 20 61 6e 64 20 77 6f 72 6b 69 6e 67 20 74  ng and working t
4dd0: 6f 77 61 72 64 20 74 68 65 20 65 6e 64 20 61 73  oward the end as
4de0: 20 73 68 6f 77 6e 20 69 6e 20 0a 3c 61 20 68 72   shown in .<a hr
4df0: 65 66 3d 22 23 66 69 67 31 37 22 3e 66 69 67 75  ef="#fig17">figu
4e00: 72 65 20 31 37 3c 2f 61 3e 2e 0a 3c 2f 70 3e 0a  re 17</a>..</p>.
4e10: 0a 3c 68 33 3e 32 2e 32 20 53 6f 72 74 69 6e 67  .<h3>2.2 Sorting
4e20: 20 42 79 20 49 6e 64 65 78 3c 2f 68 33 3e 0a 0a   By Index</h3>..
4e30: 3c 70 3e 0a 4f 66 20 63 6f 75 72 73 65 2c 20 6f  <p>.Of course, o
4e40: 72 64 65 72 69 6e 67 20 74 68 65 20 6f 75 74 70  rdering the outp
4e50: 75 74 20 6f 66 20 61 20 71 75 65 72 79 20 62 79  ut of a query by
4e60: 20 72 6f 77 69 64 20 69 73 20 73 65 6c 64 6f 6d   rowid is seldom
4e70: 20 75 73 65 66 75 6c 2e 0a 55 73 75 61 6c 6c 79   useful..Usually
4e80: 20 6f 6e 65 20 77 61 6e 74 73 20 74 6f 20 6f 72   one wants to or
4e90: 64 65 72 20 74 68 65 20 6f 75 74 70 75 74 20 62  der the output b
4ea0: 79 20 73 6f 6d 65 20 6f 74 68 65 72 20 63 6f 6c  y some other col
4eb0: 75 6d 6e 2e 0a 3c 2f 70 3e 0a 0a 3c 70 3e 0a 49  umn..</p>..<p>.I
4ec0: 66 20 61 6e 20 69 6e 64 65 78 20 69 73 20 61 76  f an index is av
4ed0: 61 69 6c 61 62 6c 65 20 6f 6e 20 74 68 65 20 4f  ailable on the O
4ee0: 52 44 45 52 20 42 59 20 63 6f 6c 75 6d 6e 2c 20  RDER BY column, 
4ef0: 74 68 61 74 20 69 6e 64 65 78 20 63 61 6e 20 62  that index can b
4f00: 65 20 75 73 65 64 0a 66 6f 72 20 73 6f 72 74 69  e used.for sorti
4f10: 6e 67 2e 20 20 43 6f 6e 73 69 64 65 72 20 74 68  ng.  Consider th
4f20: 65 20 72 65 71 75 65 73 74 20 66 6f 72 20 61 6c  e request for al
4f30: 6c 20 69 74 65 6d 73 20 73 6f 72 74 65 64 20 62  l items sorted b
4f40: 79 20 22 66 72 75 69 74 22 3a 0a 3c 2f 70 3e 0a  y "fruit":.</p>.
4f50: 0a 3c 74 63 6c 3e 63 6f 64 65 20 7b 53 45 4c 45  .<tcl>code {SELE
4f60: 43 54 20 2a 20 46 52 4f 4d 20 66 72 75 69 74 73  CT * FROM fruits
4f70: 66 6f 72 73 61 6c 65 20 4f 52 44 45 52 20 42 59  forsale ORDER BY
4f80: 20 66 72 75 69 74 3b 7d 3c 2f 74 63 6c 3e 0a 0a   fruit;}</tcl>..
4f90: 3c 74 63 6c 3e 66 69 67 75 72 65 20 31 38 20 23  <tcl>figure 18 #
4fa0: 66 69 67 31 38 20 6f 62 66 72 75 69 74 69 64 78  fig18 obfruitidx
4fb0: 31 2e 67 69 66 20 7b 53 6f 72 74 69 6e 67 20 57  1.gif {Sorting W
4fc0: 69 74 68 20 41 6e 20 49 6e 64 65 78 7d 3c 2f 74  ith An Index}</t
4fd0: 63 6c 3e 0a 0a 3c 70 3e 0a 54 68 65 20 49 64 78  cl>..<p>.The Idx
4fe0: 31 20 69 6e 64 65 78 20 69 73 20 73 63 61 6e 6e  1 index is scann
4ff0: 65 64 20 66 72 6f 6d 20 74 6f 70 20 74 6f 20 62  ed from top to b
5000: 6f 74 74 6f 6d 20 28 6f 72 20 66 72 6f 6d 20 62  ottom (or from b
5010: 6f 74 74 6f 6d 20 74 6f 20 74 6f 70 20 69 66 0a  ottom to top if.
5020: 22 4f 52 44 45 52 20 42 59 20 66 72 75 69 74 20  "ORDER BY fruit 
5030: 44 45 53 43 22 20 69 73 20 75 73 65 64 29 20 69  DESC" is used) i
5040: 6e 20 6f 72 64 65 72 20 74 6f 20 66 69 6e 64 20  n order to find 
5050: 74 68 65 20 72 6f 77 69 64 73 20 66 6f 72 20 65  the rowids for e
5060: 61 63 68 20 69 74 65 6d 0a 69 6e 20 6f 72 64 65  ach item.in orde
5070: 72 20 62 79 20 66 72 75 69 74 2e 20 20 54 68 65  r by fruit.  The
5080: 6e 20 66 6f 72 20 65 61 63 68 20 72 6f 77 69 64  n for each rowid
5090: 2c 20 61 20 62 69 6e 61 72 79 20 73 65 61 72 63  , a binary searc
50a0: 68 20 69 73 20 64 6f 6e 65 20 74 6f 20 6c 6f 6f  h is done to loo
50b0: 6b 75 70 0a 61 6e 64 20 6f 75 74 70 75 74 20 74  kup.and output t
50c0: 68 61 74 20 72 6f 77 2e 20 20 49 6e 20 74 68 69  hat row.  In thi
50d0: 73 20 77 61 79 2c 20 74 68 65 20 6f 75 74 70 75  s way, the outpu
50e0: 74 20 61 70 70 65 61 72 73 20 69 6e 20 74 68 65  t appears in the
50f0: 20 72 65 71 75 65 73 74 65 64 20 6f 72 64 65 72   requested order
5100: 0a 77 69 74 68 20 74 68 65 20 6e 65 65 64 20 74  .with the need t
5110: 6f 20 67 61 74 68 65 72 20 74 68 65 6e 20 65 6e  o gather then en
5120: 74 69 72 65 20 6f 75 74 70 75 74 20 61 6e 64 20  tire output and 
5130: 73 6f 72 74 20 69 74 20 75 73 69 6e 67 20 61 20  sort it using a 
5140: 73 65 70 61 72 61 74 65 20 73 74 65 70 2e 0a 3c  separate step..<
5150: 2f 70 3e 0a 0a 3c 70 3e 0a 42 75 74 20 64 6f 65  /p>..<p>.But doe
5160: 73 20 74 68 69 73 20 72 65 61 6c 6c 79 20 73 61  s this really sa
5170: 76 65 20 74 69 6d 65 3f 20 20 54 68 65 20 6e 75  ve time?  The nu
5180: 6d 62 65 72 20 6f 66 20 73 74 65 70 73 20 69 6e  mber of steps in
5190: 20 74 68 65 20 0a 3c 61 20 68 72 65 66 3d 22 23   the .<a href="#
51a0: 66 69 67 31 36 22 3e 6f 72 69 67 69 6e 61 6c 20  fig16">original 
51b0: 69 6e 64 65 78 6c 65 73 73 20 73 6f 72 74 3c 2f  indexless sort</
51c0: 61 3e 20 69 73 20 70 72 6f 70 6f 72 74 69 6f 6e  a> is proportion
51d0: 61 6c 20 74 6f 20 4e 6c 6f 67 4e 20 73 69 6e 63  al to NlogN sinc
51e0: 65 0a 74 68 61 74 20 69 73 20 68 6f 77 20 6d 75  e.that is how mu
51f0: 63 68 20 74 69 6d 65 20 69 74 20 74 61 6b 65 73  ch time it takes
5200: 20 74 6f 20 73 6f 72 74 20 4e 20 72 6f 77 73 2e   to sort N rows.
5210: 20 20 42 75 74 20 77 68 65 6e 20 77 65 20 75 73    But when we us
5220: 65 20 49 64 78 31 20 61 73 0a 73 68 6f 77 6e 20  e Idx1 as.shown 
5230: 68 65 72 65 2c 20 77 65 20 68 61 76 65 20 74 6f  here, we have to
5240: 20 64 6f 20 4e 20 72 6f 77 69 64 20 6c 6f 6f 6b   do N rowid look
5250: 75 70 73 20 77 68 69 63 68 20 74 61 6b 65 20 6c  ups which take l
5260: 6f 67 4e 20 74 69 6d 65 20 65 61 63 68 2c 20 73  ogN time each, s
5270: 6f 0a 74 68 65 20 74 6f 74 61 6c 20 74 69 6d 65  o.the total time
5280: 20 6f 66 20 4e 6c 6f 67 4e 20 69 73 20 74 68 65   of NlogN is the
5290: 20 73 61 6d 65 21 0a 3c 2f 70 3e 0a 0a 3c 70 3e   same!.</p>..<p>
52a0: 0a 53 51 4c 69 74 65 20 75 73 65 73 20 61 20 63  .SQLite uses a c
52b0: 6f 73 74 2d 62 61 73 65 64 20 71 75 65 72 79 20  ost-based query 
52c0: 70 6c 61 6e 6e 65 72 2e 20 20 57 68 65 6e 20 74  planner.  When t
52d0: 68 65 72 65 20 61 72 65 20 74 77 6f 20 6f 72 20  here are two or 
52e0: 6d 6f 72 65 20 77 61 79 73 0a 6f 66 20 73 6f 6c  more ways.of sol
52f0: 76 69 6e 67 20 74 68 65 20 73 61 6d 65 20 71 75  ving the same qu
5300: 65 72 79 2c 20 53 51 4c 69 74 65 20 74 72 69 65  ery, SQLite trie
5310: 73 20 74 6f 20 65 73 74 69 6d 61 74 65 20 74 68  s to estimate th
5320: 65 20 74 6f 74 61 6c 20 61 6d 6f 75 6e 74 20 6f  e total amount o
5330: 66 0a 74 69 6d 65 20 6e 65 65 64 65 64 20 74 6f  f.time needed to
5340: 20 72 75 6e 20 74 68 65 20 71 75 65 72 79 20 75   run the query u
5350: 73 69 6e 67 20 65 61 63 68 20 70 6c 61 6e 2c 20  sing each plan, 
5360: 61 6e 64 20 74 68 65 6e 20 75 73 65 73 20 74 68  and then uses th
5370: 65 20 70 6c 61 6e 20 77 69 74 68 0a 74 68 65 20  e plan with.the 
5380: 6c 6f 77 65 73 74 20 65 73 74 69 6d 61 74 65 64  lowest estimated
5390: 20 63 6f 73 74 2e 20 20 41 20 63 6f 73 74 20 69   cost.  A cost i
53a0: 73 20 63 6f 6d 70 75 74 65 64 20 6d 6f 73 74 6c  s computed mostl
53b0: 79 20 66 72 6f 6d 20 74 68 65 20 65 73 74 69 6d  y from the estim
53c0: 61 74 65 64 0a 74 69 6d 65 2c 20 61 6e 64 20 73  ated.time, and s
53d0: 6f 20 74 68 69 73 20 63 61 73 65 20 63 6f 75 6c  o this case coul
53e0: 64 20 67 6f 20 65 69 74 68 65 72 20 77 61 79 20  d go either way 
53f0: 64 65 70 65 6e 64 69 6e 67 20 6f 6e 20 74 68 65  depending on the
5400: 20 74 61 62 6c 65 20 73 69 7a 65 20 61 6e 64 0a   table size and.
5410: 77 68 61 74 20 57 48 45 52 45 20 63 6c 61 75 73  what WHERE claus
5420: 65 20 63 6f 6e 73 74 72 61 69 6e 74 73 20 77 65  e constraints we
5430: 72 65 20 61 76 61 69 6c 61 62 6c 65 2c 20 61 6e  re available, an
5440: 64 20 73 6f 20 66 6f 72 74 68 2e 20 20 42 75 74  d so forth.  But
5450: 20 67 65 6e 65 72 61 6c 6c 79 0a 73 70 65 61 6b   generally.speak
5460: 69 6e 67 2c 20 74 68 65 20 69 6e 64 65 78 65 64  ing, the indexed
5470: 20 73 6f 72 74 20 77 6f 75 6c 64 20 70 72 6f 62   sort would prob
5480: 61 62 6c 79 20 62 65 20 63 68 6f 73 65 6e 2c 20  ably be chosen, 
5490: 69 66 20 66 6f 72 20 6e 6f 20 6f 74 68 65 72 0a  if for no other.
54a0: 72 65 61 73 6f 6e 2c 20 62 65 63 61 75 73 65 20  reason, because 
54b0: 69 74 20 64 6f 65 73 20 6e 6f 74 20 6e 65 65 64  it does not need
54c0: 20 74 6f 20 61 63 63 75 6d 75 6c 61 74 65 20 74   to accumulate t
54d0: 68 65 20 65 6e 74 69 72 65 20 72 65 73 75 6c 74  he entire result
54e0: 20 73 65 74 20 69 6e 0a 74 65 6d 70 6f 72 61 72   set in.temporar
54f0: 79 20 73 74 6f 72 61 67 65 20 62 65 66 6f 72 65  y storage before
5500: 20 73 6f 72 74 69 6e 67 20 61 6e 64 20 74 68 75   sorting and thu
5510: 73 20 75 73 65 73 20 6d 75 63 68 20 6c 65 73 73  s uses much less
5520: 20 74 65 6d 70 6f 72 61 72 79 20 73 74 6f 72 61   temporary stora
5530: 67 65 2e 0a 3c 2f 70 3e 0a 0a 3c 68 33 3e 32 2e  ge..</p>..<h3>2.
5540: 33 20 53 6f 72 74 69 6e 67 20 42 79 20 43 6f 76  3 Sorting By Cov
5550: 65 72 69 6e 67 20 49 6e 64 65 78 3c 2f 68 33 3e  ering Index</h3>
5560: 0a 0a 3c 70 3e 0a 49 66 20 61 20 63 6f 76 65 72  ..<p>.If a cover
5570: 69 6e 67 20 69 6e 64 65 78 20 63 61 6e 20 62 65  ing index can be
5580: 20 75 73 65 64 20 66 6f 72 20 61 20 71 75 65 72   used for a quer
5590: 79 2c 20 74 68 65 6e 20 74 68 65 20 6d 75 6c 74  y, then the mult
55a0: 69 70 6c 65 20 72 6f 77 69 64 20 6c 6f 6f 6b 75  iple rowid looku
55b0: 70 73 0a 63 61 6e 20 62 65 20 61 76 6f 69 64 65  ps.can be avoide
55c0: 64 20 61 6e 64 20 74 68 65 20 63 6f 73 74 20 6f  d and the cost o
55d0: 66 20 74 68 65 20 71 75 65 72 79 20 64 72 6f 70  f the query drop
55e0: 73 20 64 72 61 6d 61 74 69 63 61 6c 6c 79 2e 0a  s dramatically..
55f0: 3c 2f 70 3e 0a 0a 3c 74 63 6c 3e 0a 66 69 67 75  </p>..<tcl>.figu
5600: 72 65 20 31 39 20 23 66 69 67 31 39 20 6f 62 66  re 19 #fig19 obf
5610: 72 75 69 74 69 64 78 34 2e 67 69 66 20 7b 53 6f  ruitidx4.gif {So
5620: 72 74 69 6e 67 20 57 69 74 68 20 41 20 43 6f 76  rting With A Cov
5630: 65 72 69 6e 67 20 49 6e 64 65 78 7d 0a 3c 2f 74  ering Index}.</t
5640: 63 6c 3e 0a 0a 3c 70 3e 0a 57 69 74 68 20 61 20  cl>..<p>.With a 
5650: 63 6f 76 65 72 69 6e 67 20 69 6e 64 65 78 2c 20  covering index, 
5660: 53 51 4c 69 74 65 20 63 61 6e 20 73 69 6d 70 6c  SQLite can simpl
5670: 79 20 77 61 6c 6b 20 74 68 65 20 69 6e 64 65 78  y walk the index
5680: 20 66 72 6f 6d 20 6f 6e 65 20 65 6e 64 20 74 6f   from one end to
5690: 20 74 68 65 0a 6f 74 68 65 72 20 61 6e 64 20 64   the.other and d
56a0: 65 6c 69 76 65 72 20 74 68 65 20 6f 75 74 70 75  eliver the outpu
56b0: 74 20 69 6e 20 74 69 6d 65 20 70 72 6f 70 6f 72  t in time propor
56c0: 74 69 6f 6e 61 6c 20 74 6f 20 4e 20 61 6e 64 20  tional to N and 
56d0: 77 69 74 68 6f 75 74 20 68 61 76 69 6e 67 0a 61  without having.a
56e0: 6c 6c 6f 63 61 74 65 20 61 20 6c 61 72 67 65 20  llocate a large 
56f0: 62 75 66 66 65 72 20 74 6f 20 68 6f 6c 64 20 74  buffer to hold t
5700: 68 65 20 72 65 73 75 6c 74 20 73 65 74 2e 0a 3c  he result set..<
5710: 2f 70 3e 0a 0a 3c 68 32 3e 33 2e 30 20 53 65 61  /p>..<h2>3.0 Sea
5720: 72 63 68 69 6e 67 20 41 6e 64 20 53 6f 72 74 69  rching And Sorti
5730: 6e 67 20 41 74 20 54 68 65 20 53 61 6d 65 20 54  ng At The Same T
5740: 69 6d 65 3c 2f 68 32 3e 0a 0a 3c 70 3e 0a 54 68  ime</h2>..<p>.Th
5750: 65 20 70 72 65 76 69 6f 75 73 20 64 69 73 63 75  e previous discu
5760: 73 73 69 6f 6e 20 68 61 73 20 74 72 65 61 74 65  ssion has treate
5770: 64 20 73 65 61 72 63 68 69 6e 67 20 61 6e 64 20  d searching and 
5780: 73 6f 72 74 69 6e 67 20 61 73 20 73 65 70 61 72  sorting as separ
5790: 61 74 65 0a 74 6f 70 69 63 73 2e 20 20 42 75 74  ate.topics.  But
57a0: 20 69 6e 20 70 72 61 63 74 69 63 65 2c 20 69 74   in practice, it
57b0: 20 69 73 20 6f 66 74 65 6e 20 74 68 65 20 63 61   is often the ca
57c0: 73 65 20 74 68 61 74 20 6f 6e 65 20 77 61 6e 74  se that one want
57d0: 73 20 74 6f 20 73 65 61 72 63 68 0a 61 6e 64 20  s to search.and 
57e0: 73 6f 72 74 20 61 74 20 74 68 65 20 73 61 6d 65  sort at the same
57f0: 20 74 69 6d 65 2e 20 20 46 6f 72 74 75 6e 61 74   time.  Fortunat
5800: 65 6c 79 2c 20 69 74 20 69 73 20 70 6f 73 73 69  ely, it is possi
5810: 62 6c 65 20 74 6f 20 64 6f 20 74 68 69 73 0a 75  ble to do this.u
5820: 73 69 6e 67 20 61 20 73 69 6e 67 6c 65 20 69 6e  sing a single in
5830: 64 65 78 2e 0a 3c 2f 70 3e 0a 0a 3c 68 33 3e 33  dex..</p>..<h3>3
5840: 2e 31 20 53 65 61 72 63 68 69 6e 67 20 41 6e 64  .1 Searching And
5850: 20 53 6f 72 74 69 6e 67 20 57 69 74 68 20 41 20   Sorting With A 
5860: 4d 75 6c 74 69 2d 43 6f 6c 75 6d 6e 20 49 6e 64  Multi-Column Ind
5870: 65 78 3c 2f 68 33 3e 0a 0a 3c 70 3e 0a 53 75 70  ex</h3>..<p>.Sup
5880: 70 6f 73 65 20 77 65 20 77 61 6e 74 20 74 6f 20  pose we want to 
5890: 66 69 6e 64 20 74 68 65 20 70 72 69 63 65 73 20  find the prices 
58a0: 6f 66 20 61 6c 6c 20 6b 69 6e 64 73 20 6f 66 20  of all kinds of 
58b0: 6f 72 61 6e 67 65 73 20 73 6f 72 74 65 64 20 69  oranges sorted i
58c0: 6e 0a 6f 72 64 65 72 20 6f 66 20 74 68 65 20 73  n.order of the s
58d0: 74 61 74 65 20 77 68 65 72 65 20 74 68 65 79 20  tate where they 
58e0: 61 72 65 20 67 72 6f 77 6e 2e 20 20 54 68 65 20  are grown.  The 
58f0: 71 75 65 72 79 20 69 73 20 74 68 69 73 3a 0a 3c  query is this:.<
5900: 2f 70 3e 0a 0a 3c 74 63 6c 3e 0a 63 6f 64 65 20  /p>..<tcl>.code 
5910: 7b 53 45 4c 45 43 54 20 70 72 69 63 65 20 46 52  {SELECT price FR
5920: 4f 4d 20 66 72 75 69 74 66 6f 72 73 61 6c 65 20  OM fruitforsale 
5930: 57 48 45 52 45 20 66 72 75 69 74 3d 27 4f 72 61  WHERE fruit='Ora
5940: 6e 67 65 27 20 4f 52 44 45 52 20 42 59 20 73 74  nge' ORDER BY st
5950: 61 74 65 7d 0a 3c 2f 74 63 6c 3e 0a 0a 3c 70 3e  ate}.</tcl>..<p>
5960: 0a 54 68 65 20 71 75 65 72 79 20 63 6f 6e 74 61  .The query conta
5970: 69 6e 73 20 62 6f 74 68 20 61 20 73 65 61 72 63  ins both a searc
5980: 68 20 72 65 73 74 72 69 63 74 69 6f 6e 20 69 6e  h restriction in
5990: 20 74 68 65 20 57 48 45 52 45 20 63 6c 61 75 73   the WHERE claus
59a0: 65 0a 61 6e 64 20 61 20 73 6f 72 74 20 6f 72 64  e.and a sort ord
59b0: 65 72 20 69 6e 20 74 68 65 20 4f 52 44 45 52 20  er in the ORDER 
59c0: 42 59 20 63 6c 61 75 73 65 2e 20 20 42 6f 74 68  BY clause.  Both
59d0: 20 74 68 65 20 73 65 61 72 63 68 20 61 6e 64 20   the search and 
59e0: 74 68 65 20 73 6f 72 74 0a 63 61 6e 20 62 65 20  the sort.can be 
59f0: 61 63 63 6f 6d 70 6c 69 73 68 65 64 20 61 74 20  accomplished at 
5a00: 74 68 65 20 73 61 6d 65 20 74 69 6d 65 20 75 73  the same time us
5a10: 69 6e 67 20 74 68 65 20 74 77 6f 2d 63 6f 6c 75  ing the two-colu
5a20: 6d 6e 20 69 6e 64 65 78 20 49 64 78 33 2e 0a 3c  mn index Idx3..<
5a30: 2f 70 3e 0a 0a 3c 74 63 6c 3e 0a 66 69 67 75 72  /p>..<tcl>.figur
5a40: 65 20 32 30 20 23 66 69 67 32 30 20 66 72 75 69  e 20 #fig20 frui
5a50: 74 6f 62 73 74 61 74 65 30 2e 67 69 66 20 7b 53  tobstate0.gif {S
5a60: 65 61 72 63 68 20 41 6e 64 20 53 6f 72 74 20 42  earch And Sort B
5a70: 79 20 4d 75 6c 74 69 2d 43 6f 6c 75 6d 6e 20 49  y Multi-Column I
5a80: 6e 64 65 78 7d 0a 3c 2f 74 63 6c 3e 0a 0a 3c 70  ndex}.</tcl>..<p
5a90: 3e 0a 54 68 65 20 71 75 65 72 79 20 64 6f 65 73  >.The query does
5aa0: 20 61 20 62 69 6e 61 72 79 20 73 65 61 72 63 68   a binary search
5ab0: 20 6f 6e 20 74 68 65 20 69 6e 64 65 78 20 74 6f   on the index to
5ac0: 20 66 69 6e 64 20 74 68 65 20 73 75 62 73 65 74   find the subset
5ad0: 20 6f 66 20 72 6f 77 73 0a 74 68 61 74 20 68 61   of rows.that ha
5ae0: 76 65 20 66 72 75 69 74 3d 27 4f 72 61 6e 67 65  ve fruit='Orange
5af0: 27 2e 20 20 28 42 65 63 61 75 73 65 20 74 68 65  '.  (Because the
5b00: 20 66 72 75 69 74 20 63 6f 6c 75 6d 6e 20 69 73   fruit column is
5b10: 20 74 68 65 20 6c 65 66 74 2d 6d 6f 73 74 20 63   the left-most c
5b20: 6f 6c 75 6d 6e 0a 6f 66 20 74 68 65 20 69 6e 64  olumn.of the ind
5b30: 65 78 20 61 6e 64 20 74 68 65 20 72 6f 77 73 20  ex and the rows 
5b40: 6f 66 20 74 68 65 20 69 6e 64 65 78 20 61 72 65  of the index are
5b50: 20 69 6e 20 73 6f 72 74 65 64 20 6f 72 64 65 72   in sorted order
5b60: 2c 20 61 6c 6c 20 73 75 63 68 20 0a 72 6f 77 73  , all such .rows
5b70: 20 77 69 6c 6c 20 62 65 20 61 64 6a 61 63 65 6e   will be adjacen
5b80: 74 2e 29 20 20 54 68 65 6e 20 69 74 20 73 63 61  t.)  Then it sca
5b90: 6e 73 20 74 68 65 20 6d 61 74 63 68 69 6e 67 20  ns the matching 
5ba0: 69 6e 64 65 78 20 72 6f 77 73 20 66 72 6f 6d 20  index rows from 
5bb0: 74 6f 70 20 74 6f 0a 62 6f 74 74 6f 6d 20 74 6f  top to.bottom to
5bc0: 20 67 65 74 20 74 68 65 20 72 6f 77 69 64 73 20   get the rowids 
5bd0: 66 6f 72 20 74 68 65 20 6f 72 69 67 69 6e 61 6c  for the original
5be0: 20 74 61 62 6c 65 2c 20 61 6e 64 20 66 6f 72 20   table, and for 
5bf0: 65 61 63 68 20 72 6f 77 69 64 20 64 6f 65 73 0a  each rowid does.
5c00: 61 20 62 69 6e 61 72 79 20 73 65 61 72 63 68 20  a binary search 
5c10: 6f 6e 20 74 68 65 20 6f 72 69 67 69 6e 61 6c 20  on the original 
5c20: 74 61 62 6c 65 20 74 6f 20 66 69 6e 64 20 74 68  table to find th
5c30: 65 20 70 72 69 63 65 2e 0a 3c 2f 70 3e 0a 0a 3c  e price..</p>..<
5c40: 70 3e 0a 59 6f 75 20 77 69 6c 6c 20 6e 6f 74 69  p>.You will noti
5c50: 63 65 20 74 68 61 74 20 74 68 65 72 65 20 69 73  ce that there is
5c60: 20 6e 6f 20 22 73 6f 72 74 22 20 62 6f 78 20 61   no "sort" box a
5c70: 6e 79 77 68 65 72 65 20 69 6e 20 74 68 65 20 61  nywhere in the a
5c80: 62 6f 76 65 20 64 69 61 67 72 61 6d 2e 0a 54 68  bove diagram..Th
5c90: 65 20 4f 52 44 45 52 20 42 59 20 63 6c 61 75 73  e ORDER BY claus
5ca0: 65 20 6f 66 20 74 68 65 20 71 75 65 72 79 20 68  e of the query h
5cb0: 61 73 20 62 65 63 6f 6d 65 20 61 20 6e 6f 2d 6f  as become a no-o
5cc0: 70 2e 20 20 4e 6f 20 73 6f 72 74 69 6e 67 20 68  p.  No sorting h
5cd0: 61 73 20 74 6f 20 62 65 0a 64 6f 6e 65 20 68 65  as to be.done he
5ce0: 72 65 20 62 65 63 61 75 73 65 20 74 68 65 20 6f  re because the o
5cf0: 75 74 70 75 74 20 6f 72 64 65 72 20 69 73 20 62  utput order is b
5d00: 79 20 74 68 65 20 73 74 61 74 65 20 63 6f 6c 75  y the state colu
5d10: 6d 6e 20 61 6e 64 20 74 68 65 20 73 74 61 74 65  mn and the state
5d20: 0a 63 6f 6c 75 6d 6e 20 61 6c 73 6f 20 68 61 70  .column also hap
5d30: 70 65 6e 73 20 74 6f 20 62 65 20 74 68 65 20 66  pens to be the f
5d40: 69 72 73 74 20 63 6f 6c 75 6d 6e 20 61 66 74 65  irst column afte
5d50: 72 20 74 68 65 20 66 72 75 69 74 20 63 6f 6c 75  r the fruit colu
5d60: 6d 6e 20 69 6e 20 74 68 65 0a 69 6e 64 65 78 2e  mn in the.index.
5d70: 20 20 53 6f 2c 20 69 66 20 77 65 20 73 63 61 6e    So, if we scan
5d80: 20 65 6e 74 72 69 65 73 20 6f 66 20 74 68 65 20   entries of the 
5d90: 69 6e 64 65 78 20 74 68 61 74 20 68 61 76 65 20  index that have 
5da0: 74 68 65 20 73 61 6d 65 20 76 61 6c 75 65 20 66  the same value f
5db0: 6f 72 0a 74 68 65 20 66 72 75 69 74 20 63 6f 6c  or.the fruit col
5dc0: 75 6d 6e 20 66 72 6f 6d 20 74 6f 70 20 74 6f 20  umn from top to 
5dd0: 62 6f 74 74 6f 6d 2c 20 74 68 6f 73 65 20 69 6e  bottom, those in
5de0: 64 65 78 20 65 6e 74 72 69 65 73 20 61 72 65 20  dex entries are 
5df0: 67 75 61 72 61 6e 74 65 65 64 20 74 6f 0a 62 65  guaranteed to.be
5e00: 20 6f 72 64 65 72 65 64 20 62 79 20 74 68 65 20   ordered by the 
5e10: 73 74 61 74 65 20 63 6f 6c 75 6d 6e 2e 0a 3c 2f  state column..</
5e20: 70 3e 0a 0a 3c 74 63 6c 3e 68 64 5f 66 72 61 67  p>..<tcl>hd_frag
5e30: 6d 65 6e 74 20 7b 73 72 63 68 73 6f 72 74 63 6f  ment {srchsortco
5e40: 76 69 64 78 7d 3c 2f 74 63 6c 3e 0a 3c 68 33 3e  vidx}</tcl>.<h3>
5e50: 33 2e 32 20 53 65 61 72 63 68 69 6e 67 20 41 6e  3.2 Searching An
5e60: 64 20 53 6f 72 74 69 6e 67 20 57 69 74 68 20 41  d Sorting With A
5e70: 20 43 6f 76 65 72 69 6e 67 20 49 6e 64 65 78 3c   Covering Index<
5e80: 2f 68 33 3e 0a 0a 3c 70 3e 0a 41 20 5b 63 6f 76  /h3>..<p>.A [cov
5e90: 65 72 69 6e 67 20 69 6e 64 65 78 5d 20 63 61 6e  ering index] can
5ea0: 20 61 6c 73 6f 20 62 65 20 75 73 65 64 20 74 6f   also be used to
5eb0: 20 73 65 61 72 63 68 20 61 6e 64 20 73 6f 72 74   search and sort
5ec0: 20 61 74 20 74 68 65 20 73 61 6d 65 20 74 69 6d   at the same tim
5ed0: 65 2e 0a 43 6f 6e 73 69 64 65 72 20 74 68 65 20  e..Consider the 
5ee0: 66 6f 6c 6c 6f 77 69 6e 67 3a 0a 3c 2f 70 3e 0a  following:.</p>.
5ef0: 0a 3c 74 63 6c 3e 0a 63 6f 64 65 20 7b 53 45 4c  .<tcl>.code {SEL
5f00: 45 43 54 20 2a 20 46 52 4f 4d 20 66 72 75 69 74  ECT * FROM fruit
5f10: 66 6f 72 73 61 6c 65 20 57 48 45 52 45 20 66 72  forsale WHERE fr
5f20: 75 69 74 3d 27 4f 72 61 6e 67 65 27 20 4f 52 44  uit='Orange' ORD
5f30: 45 52 20 42 59 20 73 74 61 74 65 7d 0a 66 69 67  ER BY state}.fig
5f40: 75 72 65 20 32 31 20 23 66 69 67 32 31 20 66 72  ure 21 #fig21 fr
5f50: 75 69 74 6f 62 73 74 61 74 65 2e 67 69 66 20 7b  uitobstate.gif {
5f60: 53 65 61 72 63 68 20 41 6e 64 20 53 6f 72 74 20  Search And Sort 
5f70: 42 79 20 43 6f 76 65 72 69 6e 67 20 49 6e 64 65  By Covering Inde
5f80: 78 7d 0a 3c 2f 74 63 6c 3e 0a 0a 3c 70 3e 0a 41  x}.</tcl>..<p>.A
5f90: 73 20 62 65 66 6f 72 65 2c 20 53 51 4c 69 74 65  s before, SQLite
5fa0: 20 64 6f 65 73 20 73 69 6e 67 6c 65 20 62 69 6e   does single bin
5fb0: 61 72 79 20 73 65 61 72 63 68 0a 66 6f 72 20 74  ary search.for t
5fc0: 68 65 20 72 61 6e 67 65 20 6f 66 20 72 6f 77 73  he range of rows
5fd0: 20 69 6e 20 74 68 65 20 63 6f 76 65 72 69 6e 67   in the covering
5fe0: 0a 69 6e 64 65 78 20 74 68 61 74 20 73 61 74 69  .index that sati
5ff0: 73 66 79 20 74 68 65 20 57 48 45 52 45 20 63 6c  sfy the WHERE cl
6000: 61 75 73 65 2c 20 74 68 65 20 73 63 61 6e 73 20  ause, the scans 
6010: 74 68 61 74 20 72 61 6e 67 65 20 66 72 6f 6d 20  that range from 
6020: 74 6f 70 20 74 6f 20 0a 62 6f 74 74 6f 6d 20 74  top to .bottom t
6030: 6f 20 67 65 74 20 74 68 65 20 64 65 73 69 72 65  o get the desire
6040: 64 20 72 65 73 75 6c 74 73 2e 20 20 0a 54 68 65  d results.  .The
6050: 20 72 6f 77 73 20 74 68 61 74 20 73 61 74 69 73   rows that satis
6060: 66 79 20 74 68 65 20 57 48 45 52 45 20 63 6c 61  fy the WHERE cla
6070: 75 73 65 20 61 72 65 20 67 75 61 72 61 6e 74 65  use are guarante
6080: 65 64 20 74 6f 20 62 65 20 61 64 6a 61 63 65 6e  ed to be adjacen
6090: 74 0a 73 69 6e 63 65 20 74 68 65 20 57 48 45 52  t.since the WHER
60a0: 45 20 63 6c 61 75 73 65 20 69 73 20 61 6e 20 65  E clause is an e
60b0: 71 75 61 6c 69 74 79 20 63 6f 6e 73 74 72 61 69  quality constrai
60c0: 6e 74 20 6f 6e 20 74 68 65 20 6c 65 66 74 2d 6d  nt on the left-m
60d0: 6f 73 74 0a 63 6f 6c 75 6d 6e 20 6f 66 20 74 68  ost.column of th
60e0: 65 20 69 6e 64 65 78 2e 20 20 41 6e 64 20 62 79  e index.  And by
60f0: 20 73 63 61 6e 6e 69 6e 67 20 74 68 65 20 6d 61   scanning the ma
6100: 74 63 68 69 6e 67 20 69 6e 64 65 78 20 72 6f 77  tching index row
6110: 73 20 66 72 6f 6d 0a 74 6f 70 20 74 6f 20 62 6f  s from.top to bo
6120: 74 74 6f 6d 2c 20 74 68 65 20 6f 75 74 70 75 74  ttom, the output
6130: 20 69 73 20 67 75 61 72 61 6e 74 65 65 64 20 74   is guaranteed t
6140: 6f 20 62 65 20 6f 72 64 65 72 65 64 20 62 79 20  o be ordered by 
6150: 73 74 61 74 65 20 73 69 6e 63 65 20 74 68 65 0a  state since the.
6160: 73 74 61 74 65 20 63 6f 6c 75 6d 6e 20 69 73 20  state column is 
6170: 74 68 65 20 76 65 72 79 20 6e 65 78 74 20 63 6f  the very next co
6180: 6c 75 6d 6e 20 74 6f 20 74 68 65 20 72 69 67 68  lumn to the righ
6190: 74 20 6f 66 20 74 68 65 20 66 72 75 69 74 20 63  t of the fruit c
61a0: 6f 6c 75 6d 6e 2e 0a 41 6e 64 20 73 6f 20 74 68  olumn..And so th
61b0: 65 20 72 65 73 75 6c 74 69 6e 67 20 71 75 65 72  e resulting quer
61c0: 79 20 69 73 20 76 65 72 79 20 65 66 66 69 63 69  y is very effici
61d0: 65 6e 74 2e 0a 3c 2f 70 3e 0a 0a 3c 70 3e 0a 53  ent..</p>..<p>.S
61e0: 51 4c 69 74 65 20 63 61 6e 20 70 75 6c 6c 20 61  QLite can pull a
61f0: 20 73 69 6d 69 6c 61 72 20 74 72 69 63 6b 20 66   similar trick f
6200: 6f 72 20 61 20 64 65 73 63 65 6e 64 69 6e 67 20  or a descending 
6210: 4f 52 44 45 52 20 42 59 3a 0a 3c 2f 70 3e 0a 0a  ORDER BY:.</p>..
6220: 3c 74 63 6c 3e 0a 63 6f 64 65 20 7b 53 45 4c 45  <tcl>.code {SELE
6230: 43 54 20 2a 20 46 52 4f 4d 20 66 72 75 69 74 66  CT * FROM fruitf
6240: 6f 72 73 61 6c 65 20 57 48 45 52 45 20 66 72 75  orsale WHERE fru
6250: 69 74 3d 27 4f 72 61 6e 67 65 27 20 4f 52 44 45  it='Orange' ORDE
6260: 52 20 42 59 20 73 74 61 74 65 20 44 45 53 43 7d  R BY state DESC}
6270: 0a 3c 2f 74 63 6c 3e 0a 0a 3c 70 3e 0a 54 68 65  .</tcl>..<p>.The
6280: 20 73 61 6d 65 20 62 61 73 69 63 20 61 6c 67 6f   same basic algo
6290: 72 69 74 68 6d 20 69 73 20 66 6f 6c 6c 6f 77 65  rithm is followe
62a0: 64 2c 20 65 78 63 65 70 74 20 74 68 69 73 20 74  d, except this t
62b0: 69 6d 65 20 74 68 65 20 6d 61 74 63 68 69 6e 67  ime the matching
62c0: 20 72 6f 77 73 0a 6f 66 20 74 68 65 20 69 6e 64   rows.of the ind
62d0: 65 78 20 61 72 65 20 73 63 61 6e 6e 65 64 20 66  ex are scanned f
62e0: 72 6f 6d 20 62 6f 74 74 6f 6d 20 74 6f 20 74 6f  rom bottom to to
62f0: 70 20 69 6e 73 74 65 61 64 20 6f 66 20 66 72 6f  p instead of fro
6300: 6d 20 74 6f 70 20 74 6f 20 62 6f 74 74 6f 6d 2c  m top to bottom,
6310: 0a 73 6f 20 74 68 61 74 20 74 68 65 20 73 74 61  .so that the sta
6320: 74 65 73 20 77 69 6c 6c 20 61 70 70 65 61 72 20  tes will appear 
6330: 69 6e 20 64 65 73 63 65 6e 64 69 6e 67 20 6f 72  in descending or
6340: 64 65 72 2e 0a 3c 2f 70 3e 0a 0a 3c 68 32 3e 54  der..</p>..<h2>T
6350: 6f 20 42 65 20 43 6f 6e 74 69 6e 75 65 64 2e 2e  o Be Continued..
6360: 2e 3c 2f 68 32 3e 0a 0a 3c 70 3e 46 75 72 74 68  .</h2>..<p>Furth
6370: 65 72 20 74 6f 70 69 63 73 3a 3c 2f 70 3e 0a 0a  er topics:</p>..
6380: 3c 70 3e 3c 75 6c 3e 0a 3c 6c 69 3e 48 6f 77 20  <p><ul>.<li>How 
6390: 74 6f 20 63 6f 6e 73 74 72 75 63 74 20 61 20 67  to construct a g
63a0: 6f 6f 64 20 69 6e 64 65 78 0a 3c 6c 69 3e 4a 6f  ood index.<li>Jo
63b0: 69 6e 73 20 61 6e 64 20 6a 6f 69 6e 2d 6f 72 64  ins and join-ord
63c0: 65 72 0a 3c 6c 69 3e 41 75 74 6f 6d 61 74 69 63  er.<li>Automatic
63d0: 20 74 72 61 6e 73 69 65 6e 74 20 69 6e 64 69 63   transient indic
63e0: 65 73 0a 3c 6c 69 3e 48 6f 77 20 74 6f 20 64 65  es.<li>How to de
63f0: 74 65 72 6d 69 6e 65 20 77 68 61 74 20 71 75 65  termine what que
6400: 72 79 20 70 6c 61 6e 20 53 51 4c 69 74 65 20 69  ry plan SQLite i
6410: 73 20 75 73 69 6e 67 0a 3c 6c 69 3e 41 75 74 6f  s using.<li>Auto
6420: 6d 61 74 69 63 20 64 65 74 65 63 74 69 6f 6e 20  matic detection 
6430: 6f 66 20 69 6e 65 66 66 69 63 69 65 6e 74 20 71  of inefficient q
6440: 75 65 72 79 20 70 6c 61 6e 73 0a 3c 6c 69 3e 54  uery plans.<li>T
6450: 65 63 68 6e 69 71 75 65 73 20 66 6f 72 20 69 6e  echniques for in
6460: 66 6c 75 65 6e 63 69 6e 67 20 77 68 61 74 20 71  fluencing what q
6470: 75 65 72 79 20 70 6c 61 6e 20 53 51 4c 69 74 65  uery plan SQLite
6480: 20 63 68 6f 6f 73 65 73 0a 3c 2f 75 6c 3e 0a 3c   chooses.</ul>.<
6490: 2f 70 3e 0a                                      /p>.