Documentation Source Text

Hex Artifact Content
Login

Artifact 87df6fa20aefe8267f6f104f529131f13c233fc1:


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 65 61 76 69   engine..Releavi
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 61 6e 64 20 64 61 74 61 62 61 73 65  SQL.and database
05c0: 73 20 77 69 74 68 20 74 68 65 20 62 61 63 6b 67  s with the backg
05d0: 72 6f 75 6e 64 20 69 6e 66 6f 72 6d 61 74 69 6f  round informatio
05e0: 6e 20 74 6f 20 68 65 6c 70 20 74 68 65 6d 20 75  n to help them u
05f0: 6e 64 65 72 73 74 61 6e 64 0a 77 68 61 74 20 69  nderstand.what i
0600: 73 20 67 6f 69 6e 67 20 6f 6e 20 62 65 68 69 6e  s going on behin
0610: 64 20 74 68 65 20 73 63 65 6e 65 73 20 77 69 74  d the scenes wit
0620: 68 20 53 51 4c 69 74 65 2c 20 77 68 69 63 68 20  h SQLite, which 
0630: 69 6e 20 74 75 72 6e 20 73 68 6f 75 6c 64 20 6d  in turn should m
0640: 61 6b 65 0a 69 74 20 65 61 73 69 65 72 20 66 6f  ake.it easier fo
0650: 72 20 70 72 6f 67 72 61 6d 6d 65 72 73 20 74 6f  r programmers to
0660: 20 63 72 65 61 74 65 20 74 68 65 20 69 6e 64 69   create the indi
0670: 63 65 73 20 74 68 61 74 20 77 69 6c 6c 20 68 65  ces that will he
0680: 6c 70 20 74 68 65 20 53 51 4c 69 74 65 0a 71 75  lp the SQLite.qu
0690: 65 72 79 20 70 6c 61 6e 6e 65 72 20 74 6f 20 70  ery planner to p
06a0: 69 63 6b 20 74 68 65 20 62 65 73 74 20 70 6c 61  ick the best pla
06b0: 6e 73 2e 0a 3c 2f 70 3e 0a 0a 3c 68 32 3e 31 2e  ns..</p>..<h2>1.
06c0: 30 20 51 75 65 72 79 69 6e 67 3c 2f 68 32 3e 0a  0 Querying</h2>.
06d0: 0a 3c 68 33 3e 31 2e 31 20 54 61 62 6c 65 73 20  .<h3>1.1 Tables 
06e0: 57 69 74 68 6f 75 74 20 49 6e 64 69 63 65 73 3c  Without Indices<
06f0: 2f 68 33 3e 0a 0a 3c 70 3e 0a 45 76 65 72 79 20  /h3>..<p>.Every 
0700: 74 61 62 6c 65 20 69 6e 20 53 51 4c 69 74 65 20  table in SQLite 
0710: 63 6f 6e 73 69 73 74 73 20 6f 66 20 7a 65 72 6f  consists of zero
0720: 20 6f 72 20 6d 6f 72 65 20 72 6f 77 73 20 77 69   or more rows wi
0730: 74 68 20 61 20 75 6e 69 71 75 65 20 69 6e 74 65  th a unique inte
0740: 67 65 72 0a 6b 65 79 20 28 74 68 65 20 5b 72 6f  ger.key (the [ro
0750: 77 69 64 5d 20 6f 72 20 5b 49 4e 54 45 47 45 52  wid] or [INTEGER
0760: 20 50 52 49 4d 41 52 59 20 4b 45 59 5d 29 20 66   PRIMARY KEY]) f
0770: 6f 6c 6c 6f 77 65 64 20 62 79 20 63 6f 6e 74 65  ollowed by conte
0780: 6e 74 2e 20 20 54 68 65 20 72 6f 77 73 0a 61 72  nt.  The rows.ar
0790: 65 20 6c 6f 67 69 63 61 6c 6c 79 20 73 74 6f 72  e logically stor
07a0: 65 64 20 69 6e 20 6f 72 64 65 72 20 6f 66 20 69  ed in order of i
07b0: 6e 63 72 65 61 73 69 6e 67 20 72 6f 77 69 64 2e  ncreasing rowid.
07c0: 20 20 41 73 20 61 6e 20 65 78 61 6d 70 6c 65 2c    As an example,
07d0: 20 74 68 69 73 0a 61 72 74 69 63 6c 65 20 75 73   this.article us
07e0: 65 73 20 61 20 74 61 62 6c 65 20 6e 61 6d 65 64  es a table named
07f0: 20 22 46 72 75 69 74 73 46 6f 72 53 61 6c 65 22   "FruitsForSale"
0800: 20 77 68 69 63 68 20 72 65 6c 61 74 65 73 20 76   which relates v
0810: 61 72 69 6f 75 73 20 66 72 75 69 74 73 20 0a 74  arious fruits .t
0820: 6f 20 74 68 65 20 73 74 61 74 65 0a 77 68 65 72  o the state.wher
0830: 65 20 74 68 65 79 20 61 72 65 20 67 72 6f 77 6e  e they are grown
0840: 20 61 6e 64 20 74 68 65 69 72 20 75 6e 69 74 20   and their unit 
0850: 70 72 69 63 65 20 61 74 20 6d 61 72 6b 65 74 2e  price at market.
0860: 20 20 54 68 65 20 73 63 68 65 6d 61 20 69 73 20    The schema is 
0870: 74 68 69 73 3a 0a 3c 2f 70 3e 0a 0a 3c 74 63 6c  this:.</p>..<tcl
0880: 3e 63 6f 64 65 20 7b 0a 43 52 45 41 54 45 20 54  >code {.CREATE T
0890: 41 42 4c 45 20 46 72 75 69 74 73 46 6f 72 53 61  ABLE FruitsForSa
08a0: 6c 65 28 0a 20 20 46 72 75 69 74 20 54 45 58 54  le(.  Fruit TEXT
08b0: 2c 0a 20 20 53 74 61 74 65 20 54 45 58 54 2c 0a  ,.  State TEXT,.
08c0: 20 20 50 72 69 63 65 20 52 45 41 4c 0a 29 3b 0a    Price REAL.);.
08d0: 7d 3c 2f 74 63 6c 3e 0a 0a 3c 70 3e 0a 57 69 74  }</tcl>..<p>.Wit
08e0: 68 20 73 6f 6d 65 20 28 61 72 62 69 74 72 61 72  h some (arbitrar
08f0: 79 29 20 64 61 74 61 2c 20 73 75 63 68 20 61 20  y) data, such a 
0900: 74 61 62 6c 65 20 6d 69 67 68 74 20 62 65 20 6c  table might be l
0910: 6f 67 69 63 61 6c 6c 79 20 73 74 6f 72 65 64 20  ogically stored 
0920: 6f 6e 20 64 69 73 6b 0a 61 73 20 73 68 6f 77 6e  on disk.as shown
0930: 20 69 6e 20 66 69 67 75 72 65 20 31 3a 0a 3c 2f   in figure 1:.</
0940: 70 3e 0a 0a 3c 74 63 6c 3e 66 69 67 75 72 65 20  p>..<tcl>figure 
0950: 31 20 23 66 69 67 31 20 74 61 62 2e 67 69 66 20  1 #fig1 tab.gif 
0960: 7b 4c 6f 67 69 63 61 6c 20 4c 61 79 6f 75 74 20  {Logical Layout 
0970: 4f 66 20 54 61 62 6c 65 20 22 46 72 75 69 74 73  Of Table "Fruits
0980: 46 6f 72 53 61 6c 65 22 7d 3c 2f 74 63 6c 3e 0a  ForSale"}</tcl>.
0990: 0a 3c 70 3e 0a 54 68 65 20 6b 65 79 20 66 65 61  .<p>.The key fea
09a0: 74 75 72 65 73 20 74 6f 20 6e 6f 74 69 63 65 20  tures to notice 
09b0: 69 6e 20 74 68 69 73 20 65 78 61 6d 70 6c 65 20  in this example 
09c0: 69 73 20 74 68 61 74 20 74 68 65 20 72 6f 77 69  is that the rowi
09d0: 64 73 20 61 72 65 20 6e 6f 74 0a 63 6f 6e 73 65  ds are not.conse
09e0: 63 75 74 69 76 65 20 62 75 74 20 74 68 65 79 20  cutive but they 
09f0: 61 72 65 20 6f 72 64 65 72 65 64 2e 20 20 53 51  are ordered.  SQ
0a00: 4c 69 74 65 20 75 73 75 61 6c 6c 79 20 63 72 65  Lite usually cre
0a10: 61 74 65 73 20 72 6f 77 69 64 73 20 62 65 67 69  ates rowids begi
0a20: 6e 6e 69 6e 67 0a 77 69 74 68 20 6f 6e 65 20 61  nning.with one a
0a30: 6e 64 20 69 6e 63 72 65 61 73 69 6e 67 20 62 79  nd increasing by
0a40: 20 6f 6e 65 20 77 69 74 68 20 65 61 63 68 20 61   one with each a
0a50: 64 64 65 64 20 72 6f 77 2e 20 20 42 75 74 20 69  dded row.  But i
0a60: 66 20 72 6f 77 73 20 61 72 65 20 0a 64 65 6c 65  f rows are .dele
0a70: 74 65 64 2c 20 67 61 70 73 20 63 61 6e 20 61 70  ted, gaps can ap
0a80: 70 65 61 72 20 69 6e 20 74 68 65 20 73 65 71 75  pear in the sequ
0a90: 65 6e 63 65 2e 20 20 41 6e 64 20 74 68 65 20 61  ence.  And the a
0aa0: 70 70 6c 69 63 61 74 69 6f 6e 20 63 61 6e 20 63  pplication can c
0ab0: 6f 6e 74 72 6f 6c 0a 74 68 65 20 72 6f 77 69 64  ontrol.the rowid
0ac0: 20 61 73 73 69 67 6e 65 64 20 69 66 20 64 65 73   assigned if des
0ad0: 69 72 65 64 2c 20 73 6f 20 74 68 61 74 20 72 6f  ired, so that ro
0ae0: 77 73 20 61 72 65 20 6e 6f 74 20 6e 65 63 65 73  ws are not neces
0af0: 73 61 72 69 6c 79 20 69 6e 73 65 72 74 65 64 20  sarily inserted 
0b00: 0a 61 74 20 74 68 65 20 62 6f 74 74 6f 6d 2e 20  .at the bottom. 
0b10: 20 42 75 74 20 72 65 67 61 72 64 6c 65 73 73 20   But regardless 
0b20: 6f 66 20 77 68 61 74 20 68 61 70 70 65 6e 73 2c  of what happens,
0b30: 20 74 68 65 20 72 6f 77 69 64 73 20 61 72 65 20   the rowids are 
0b40: 61 6c 77 61 79 73 20 0a 75 6e 69 71 75 65 20 61  always .unique a
0b50: 6e 64 20 69 6e 20 73 74 72 69 63 74 6c 79 20 61  nd in strictly a
0b60: 73 63 65 6e 64 69 6e 67 20 6f 72 64 65 72 2e 0a  scending order..
0b70: 3c 2f 70 3e 0a 0a 3c 70 3e 0a 4e 6f 77 20 73 75  </p>..<p>.Now su
0b80: 70 70 6f 73 65 20 79 6f 75 20 77 61 6e 74 20 74  ppose you want t
0b90: 6f 20 6c 6f 6f 6b 20 75 70 20 74 68 65 20 70 72  o look up the pr
0ba0: 69 63 65 20 6f 66 20 70 65 61 63 68 65 73 2e 20  ice of peaches. 
0bb0: 20 54 68 65 20 71 75 65 72 79 20 77 6f 75 6c 64   The query would
0bc0: 0a 62 65 20 61 73 20 66 6f 6c 6c 6f 77 73 3a 0a  .be as follows:.
0bd0: 3c 2f 70 3e 0a 0a 3c 74 63 6c 3e 63 6f 64 65 20  </p>..<tcl>code 
0be0: 7b 0a 53 45 4c 45 43 54 20 70 72 69 63 65 20 46  {.SELECT price F
0bf0: 52 4f 4d 20 66 72 75 69 74 73 66 6f 72 73 61 6c  ROM fruitsforsal
0c00: 65 20 57 48 45 52 45 20 66 72 75 69 74 3d 27 50  e WHERE fruit='P
0c10: 65 61 63 68 27 3b 0a 7d 3c 2f 74 63 6c 3e 0a 0a  each';.}</tcl>..
0c20: 3c 70 3e 0a 49 6e 20 6f 72 64 65 72 20 74 6f 20  <p>.In order to 
0c30: 73 61 74 69 73 66 79 20 74 68 69 73 20 71 75 65  satisfy this que
0c40: 72 79 2c 20 53 51 4c 69 74 65 20 68 61 73 20 74  ry, SQLite has t
0c50: 6f 20 72 65 61 64 20 65 76 65 72 79 20 72 6f 77  o read every row
0c60: 20 6f 75 74 20 6f 66 20 74 68 65 0a 74 61 62 6c   out of the.tabl
0c70: 65 2c 20 63 68 65 63 6b 20 74 6f 20 73 65 65 20  e, check to see 
0c80: 69 66 20 74 68 65 20 22 66 72 75 69 74 22 20 63  if the "fruit" c
0c90: 6f 6c 75 6d 6e 20 68 61 73 20 74 68 65 20 76 61  olumn has the va
0ca0: 6c 75 65 20 6f 66 20 22 50 65 61 63 68 22 20 61  lue of "Peach" a
0cb0: 6e 64 20 69 66 0a 73 6f 2c 20 6f 75 74 70 75 74  nd if.so, output
0cc0: 20 74 68 65 20 22 70 72 69 63 65 22 20 63 6f 6c   the "price" col
0cd0: 75 6d 6e 20 66 72 6f 6d 20 74 68 61 74 20 72 6f  umn from that ro
0ce0: 77 2e 20 20 54 68 65 20 70 72 6f 63 65 73 73 20  w.  The process 
0cf0: 69 73 20 69 6c 6c 75 73 74 72 61 74 65 64 0a 62  is illustrated.b
0d00: 79 20 3c 61 20 68 72 65 66 3d 22 23 66 69 67 32  y <a href="#fig2
0d10: 22 3e 66 69 67 75 72 65 20 32 3c 2f 61 3e 20 62  ">figure 2</a> b
0d20: 65 6c 6f 77 2e 0a 54 68 69 73 20 69 73 20 63 61  elow..This is ca
0d30: 6c 6c 65 64 20 61 20 3c 69 3e 66 75 6c 6c 20 74  lled a <i>full t
0d40: 61 62 6c 65 20 73 63 61 6e 3c 2f 69 3e 20 73 69  able scan</i> si
0d50: 6e 63 65 20 74 68 65 20 65 6e 74 69 72 65 20 63  nce the entire c
0d60: 6f 6e 74 65 6e 74 20 6f 66 20 74 68 65 0a 74 61  ontent of the.ta
0d70: 62 6c 65 20 6d 75 73 74 20 62 65 20 72 65 61 64  ble must be read
0d80: 20 61 6e 64 20 65 78 61 6d 69 6e 65 64 20 69 6e   and examined in
0d90: 20 6f 72 64 65 72 20 74 6f 20 66 69 6e 64 20 74   order to find t
0da0: 68 65 20 6f 6e 65 20 72 6f 77 20 6f 66 20 69 6e  he one row of in
0db0: 74 65 72 65 73 74 2e 0a 57 69 74 68 20 61 20 74  terest..With a t
0dc0: 61 62 6c 65 20 6f 66 20 6f 6e 6c 79 20 37 20 72  able of only 7 r
0dd0: 6f 77 73 2c 20 74 68 69 73 20 69 73 20 6e 6f 74  ows, this is not
0de0: 20 61 20 62 69 67 20 64 65 61 6c 2c 20 62 75 74   a big deal, but
0df0: 20 69 66 20 79 6f 75 72 20 74 61 62 6c 65 0a 63   if your table.c
0e00: 6f 6e 74 61 69 6e 65 64 20 37 20 6d 69 6c 6c 69  ontained 7 milli
0e10: 6f 6e 20 72 6f 77 73 2c 20 61 20 66 75 6c 6c 20  on rows, a full 
0e20: 74 61 62 6c 65 20 73 63 61 6e 20 6d 69 67 68 74  table scan might
0e30: 20 72 65 61 64 20 6d 65 67 61 62 79 74 65 73 20   read megabytes 
0e40: 6f 66 20 63 6f 6e 74 65 6e 74 20 69 6e 20 6f 72  of content in or
0e50: 64 65 72 20 74 6f 20 66 69 6e 64 20 61 20 73 69  der to find a si
0e60: 6e 67 6c 65 20 38 2d 62 79 74 65 20 6e 75 6d 62  ngle 8-byte numb
0e70: 65 72 2e 20 20 46 6f 72 20 74 68 61 74 20 72 65  er.  For that re
0e80: 61 73 6f 6e 2c 20 6f 6e 65 20 6e 6f 72 6d 61 6c  ason, one normal
0e90: 6c 79 0a 74 72 69 65 73 20 74 6f 20 61 76 6f 69  ly.tries to avoi
0ea0: 64 20 66 75 6c 6c 20 74 61 62 6c 65 20 73 63 61  d full table sca
0eb0: 6e 73 2e 0a 3c 2f 70 3e 0a 0a 3c 74 63 6c 3e 66  ns..</p>..<tcl>f
0ec0: 69 67 75 72 65 20 32 20 23 66 69 67 32 20 66 75  igure 2 #fig2 fu
0ed0: 6c 6c 73 63 61 6e 2e 67 69 66 20 7b 46 75 6c 6c  llscan.gif {Full
0ee0: 20 54 61 62 6c 65 20 53 63 61 6e 7d 3c 2f 74 63   Table Scan}</tc
0ef0: 6c 3e 0a 0a 3c 68 33 3e 31 2e 32 20 4c 6f 6f 6b  l>..<h3>1.2 Look
0f00: 75 70 20 42 79 20 52 6f 77 69 64 3c 2f 68 33 3e  up By Rowid</h3>
0f10: 0a 0a 3c 70 3e 0a 4f 6e 65 20 74 65 63 68 6e 69  ..<p>.One techni
0f20: 71 75 65 20 66 6f 72 20 61 76 6f 69 64 69 6e 67  que for avoiding
0f30: 20 61 20 66 75 6c 6c 20 74 61 62 6c 65 20 73 63   a full table sc
0f40: 61 6e 20 69 73 20 74 6f 20 64 6f 20 6c 6f 6f 6b  an is to do look
0f50: 75 70 73 20 62 79 0a 72 6f 77 69 64 20 28 6f 72  ups by.rowid (or
0f60: 20 62 79 20 74 68 65 20 65 71 75 69 76 61 6c 65   by the equivale
0f70: 6e 74 20 49 4e 54 45 47 45 52 20 50 52 49 4d 41  nt INTEGER PRIMA
0f80: 52 59 20 4b 45 59 29 2e 20 20 20 54 6f 20 6c 6f  RY KEY).   To lo
0f90: 6f 6b 75 70 20 74 68 65 0a 70 72 69 63 65 20 6f  okup the.price o
0fa0: 66 20 70 65 61 63 68 65 73 2c 20 6f 6e 65 20 77  f peaches, one w
0fb0: 6f 75 6c 64 20 71 75 65 72 79 20 66 6f 72 20 74  ould query for t
0fc0: 68 65 20 65 6e 74 72 79 20 77 69 74 68 20 61 20  he entry with a 
0fd0: 72 6f 77 69 64 20 6f 66 20 34 3a 0a 3c 2f 70 3e  rowid of 4:.</p>
0fe0: 0a 0a 3c 74 63 6c 3e 63 6f 64 65 20 7b 0a 53 45  ..<tcl>code {.SE
0ff0: 4c 45 43 54 20 70 72 69 63 65 20 46 52 4f 4d 20  LECT price FROM 
1000: 66 72 75 69 74 73 66 6f 72 73 61 6c 65 20 57 48  fruitsforsale WH
1010: 45 52 45 20 72 6f 77 69 64 3d 34 3b 0a 7d 3c 2f  ERE rowid=4;.}</
1020: 74 63 6c 3e 0a 0a 3c 70 3e 0a 53 69 6e 63 65 20  tcl>..<p>.Since 
1030: 74 68 65 20 69 6e 66 6f 72 6d 61 74 69 6f 6e 20  the information 
1040: 69 73 20 73 74 6f 72 65 64 20 69 6e 20 74 68 65  is stored in the
1050: 20 74 61 62 6c 65 20 69 6e 20 72 6f 77 69 64 20   table in rowid 
1060: 6f 72 64 65 72 2c 20 53 51 4c 69 74 65 0a 63 61  order, SQLite.ca
1070: 6e 20 66 69 6e 64 20 74 68 65 20 63 6f 72 72 65  n find the corre
1080: 63 74 20 72 6f 77 20 75 73 69 6e 67 20 64 6f 69  ct row using doi
1090: 6e 67 20 61 20 62 69 6e 61 72 79 20 73 65 61 72  ng a binary sear
10a0: 63 68 20 6f 6e 20 74 68 65 20 72 6f 77 69 64 2e  ch on the rowid.
10b0: 0a 49 66 20 74 68 65 20 74 61 62 6c 65 20 63 6f  .If the table co
10c0: 6e 74 61 69 6e 73 20 4e 20 65 6c 65 6d 65 6e 74  ntains N element
10d0: 2c 20 74 68 65 20 74 69 6d 65 20 72 65 71 75 69  , the time requi
10e0: 72 65 64 20 74 6f 20 6c 6f 6f 6b 20 75 70 20 74  red to look up t
10f0: 68 65 0a 64 65 73 69 72 65 64 20 72 6f 77 20 69  he.desired row i
1100: 73 20 70 72 6f 70 6f 72 74 69 6f 6e 61 6c 20 74  s proportional t
1110: 6f 20 6c 6f 67 4e 20 72 61 74 68 65 72 20 74 68  o logN rather th
1120: 61 6e 20 62 65 69 6e 67 20 70 72 6f 70 6f 72 74  an being proport
1130: 69 6f 6e 61 6c 0a 74 6f 20 4e 20 61 73 20 69 6e  ional.to N as in
1140: 20 61 20 66 75 6c 6c 20 74 61 62 6c 65 20 73 63   a full table sc
1150: 61 6e 2e 20 20 49 66 20 74 68 65 20 74 61 62 6c  an.  If the tabl
1160: 65 20 63 6f 6e 74 61 69 6e 73 20 31 30 20 6d 69  e contains 10 mi
1170: 6c 6c 69 6f 6e 20 65 6c 65 6d 65 6e 74 73 2c 0a  llion elements,.
1180: 74 68 61 74 20 6d 65 61 6e 73 20 74 68 65 20 71  that means the q
1190: 75 65 72 79 20 77 69 6c 6c 20 62 65 20 6f 6e 20  uery will be on 
11a0: 74 68 65 20 6f 72 64 65 72 20 6f 66 20 4e 2f 6c  the order of N/l
11b0: 6f 67 4e 20 6f 72 20 61 62 6f 75 74 20 31 20 6d  ogN or about 1 m
11c0: 69 6c 6c 69 6f 6e 0a 74 69 6d 65 73 20 66 61 73  illion.times fas
11d0: 74 65 72 21 0a 3c 2f 70 3e 0a 0a 3c 74 63 6c 3e  ter!.</p>..<tcl>
11e0: 66 69 67 75 72 65 20 33 20 23 66 69 67 33 20 72  figure 3 #fig3 r
11f0: 6f 77 69 64 6c 75 2e 67 69 66 20 7b 4c 6f 6f 6b  owidlu.gif {Look
1200: 75 70 20 42 79 20 52 6f 77 69 64 7d 3c 2f 74 63  up By Rowid}</tc
1210: 6c 3e 0a 0a 3c 68 33 3e 31 2e 33 20 4c 6f 6f 6b  l>..<h3>1.3 Look
1220: 75 70 20 42 79 20 49 6e 64 65 78 3c 2f 68 33 3e  up By Index</h3>
1230: 0a 3c 70 3e 0a 54 68 65 20 70 72 6f 62 6c 65 6d  .<p>.The problem
1240: 20 77 69 74 68 20 6c 6f 6f 6b 69 6e 67 20 75 70   with looking up
1250: 20 69 6e 66 6f 72 6d 61 74 69 6f 6e 20 62 79 20   information by 
1260: 72 6f 77 69 64 20 69 73 20 74 68 61 74 20 79 6f  rowid is that yo
1270: 75 20 70 72 6f 62 61 62 6c 79 0a 64 6f 20 6e 6f  u probably.do no
1280: 74 20 63 61 72 65 20 77 68 61 74 20 74 68 65 20  t care what the 
1290: 70 72 69 63 65 20 6f 66 20 22 69 74 65 6d 20 34  price of "item 4
12a0: 22 20 69 73 20 2d 20 79 6f 75 20 77 61 6e 74 20  " is - you want 
12b0: 74 6f 20 6b 6e 6f 77 20 74 68 65 20 70 72 69 63  to know the pric
12c0: 65 0a 6f 66 20 70 65 61 63 68 65 73 2e 20 20 41  e.of peaches.  A
12d0: 6e 64 20 73 6f 20 61 20 72 6f 77 69 64 20 6c 6f  nd so a rowid lo
12e0: 6f 6b 75 70 20 69 73 20 69 73 20 6e 6f 74 20 68  okup is is not h
12f0: 65 6c 70 66 75 6c 2e 0a 3c 2f 70 3e 0a 0a 3c 70  elpful..</p>..<p
1300: 3e 0a 54 6f 20 6d 61 6b 65 20 74 68 65 20 6f 72  >.To make the or
1310: 69 67 69 6e 61 6c 20 71 75 65 72 79 20 6d 6f 72  iginal query mor
1320: 65 20 65 66 66 69 63 69 65 6e 74 2c 20 77 65 20  e efficient, we 
1330: 63 61 6e 20 61 64 64 20 61 6e 20 69 6e 64 65 78  can add an index
1340: 20 6f 6e 20 74 68 65 0a 22 66 72 75 69 74 22 20   on the."fruit" 
1350: 63 6f 6c 75 6d 6e 20 6f 66 20 74 68 65 20 22 66  column of the "f
1360: 72 75 69 74 73 66 6f 72 73 61 6c 65 22 20 74 61  ruitsforsale" ta
1370: 62 6c 65 20 6c 69 6b 65 20 74 68 69 73 3a 0a 3c  ble like this:.<
1380: 2f 70 3e 0a 0a 3c 74 63 6c 3e 63 6f 64 65 20 7b  /p>..<tcl>code {
1390: 0a 43 52 45 41 54 45 20 49 4e 44 45 58 20 69 64  .CREATE INDEX id
13a0: 78 31 20 4f 4e 20 66 72 75 69 74 73 66 6f 72 73  x1 ON fruitsfors
13b0: 61 6c 65 28 66 72 75 69 74 29 3b 0a 7d 3c 2f 74  ale(fruit);.}</t
13c0: 63 6c 3e 0a 0a 3c 70 3e 0a 41 6e 20 69 6e 64 65  cl>..<p>.An inde
13d0: 78 20 69 73 20 61 6e 6f 74 68 65 72 20 74 61 62  x is another tab
13e0: 6c 65 20 73 69 6d 69 6c 61 72 20 74 6f 20 74 68  le similar to th
13f0: 65 20 6f 72 69 67 69 6e 61 6c 20 22 66 72 75 69  e original "frui
1400: 74 73 66 6f 72 73 61 6c 65 22 20 74 61 62 6c 65  tsforsale" table
1410: 0a 62 75 74 20 77 69 74 68 20 74 68 65 20 63 6f  .but with the co
1420: 6e 74 65 6e 74 20 28 74 68 65 20 66 72 75 69 74  ntent (the fruit
1430: 20 63 6f 6c 75 6d 6e 20 69 6e 20 74 68 69 73 20   column in this 
1440: 63 61 73 65 29 20 73 74 6f 72 65 64 20 69 6e 20  case) stored in 
1450: 66 72 6f 6e 74 20 6f 66 20 74 68 65 0a 72 6f 77  front of the.row
1460: 69 64 20 61 6e 64 20 77 69 74 68 20 61 6c 6c 20  id and with all 
1470: 72 6f 77 73 20 69 6e 20 63 6f 6e 74 65 6e 74 20  rows in content 
1480: 6f 72 64 65 72 2e 0a 3c 61 20 68 72 65 66 3d 22  order..<a href="
1490: 23 66 69 67 34 22 3e 46 69 67 75 72 65 20 34 3c  #fig4">Figure 4<
14a0: 2f 61 3e 20 67 69 76 65 73 20 61 20 6c 6f 67 69  /a> gives a logi
14b0: 63 61 6c 20 76 69 65 77 20 6f 66 20 74 68 65 20  cal view of the 
14c0: 49 64 78 31 20 69 6e 64 65 78 2e 0a 54 68 65 20  Idx1 index..The 
14d0: 22 66 72 75 69 74 22 20 63 6f 6c 75 6d 6e 20 69  "fruit" column i
14e0: 73 20 74 68 65 20 70 72 69 6d 61 72 79 20 6b 65  s the primary ke
14f0: 79 20 75 73 65 64 20 74 6f 20 6f 72 64 65 72 20  y used to order 
1500: 74 68 65 20 65 6c 65 6d 65 6e 74 73 20 6f 66 20  the elements of 
1510: 74 68 65 0a 74 61 62 6c 65 20 61 6e 64 20 74 68  the.table and th
1520: 65 20 22 72 6f 77 69 64 22 20 69 73 20 74 68 65  e "rowid" is the
1530: 20 73 65 63 6f 6e 64 61 72 79 20 6b 65 79 20 75   secondary key u
1540: 73 65 64 20 74 6f 20 62 72 65 61 6b 20 74 68 65  sed to break the
1550: 20 74 69 65 20 77 68 65 6e 0a 74 77 6f 20 6f 72   tie when.two or
1560: 20 6d 6f 72 65 20 72 6f 77 73 20 68 61 76 65 20   more rows have 
1570: 74 68 65 20 73 61 6d 65 20 22 66 72 75 69 74 22  the same "fruit"
1580: 2e 20 20 49 6e 20 74 68 65 20 65 78 61 6d 70 6c  .  In the exampl
1590: 65 2c 20 74 68 65 20 72 6f 77 69 64 0a 68 61 73  e, the rowid.has
15a0: 20 74 6f 20 62 65 20 75 73 65 64 20 61 73 20 61   to be used as a
15b0: 20 74 69 65 2d 62 72 65 61 6b 65 72 20 66 6f 72   tie-breaker for
15c0: 20 74 68 65 20 22 4f 72 61 6e 67 65 22 20 72 6f   the "Orange" ro
15d0: 77 73 2e 0a 4e 6f 74 69 63 65 20 74 68 61 74 20  ws..Notice that 
15e0: 73 69 6e 63 65 20 74 68 65 20 72 6f 77 69 64 0a  since the rowid.
15f0: 69 73 20 61 6c 77 61 79 73 20 75 6e 69 71 75 65  is always unique
1600: 20 6f 76 65 72 20 61 6c 6c 20 65 6c 65 6d 65 6e   over all elemen
1610: 74 73 20 6f 66 20 74 68 65 20 6f 72 69 67 69 6e  ts of the origin
1620: 61 6c 20 74 61 62 6c 65 2c 20 74 68 65 20 63 6f  al table, the co
1630: 6d 70 6f 73 69 74 65 20 6b 65 79 0a 6f 66 20 22  mposite key.of "
1640: 66 72 75 69 74 22 20 66 6f 6c 6c 6f 77 65 64 20  fruit" followed 
1650: 62 79 20 22 72 6f 77 69 64 22 20 77 69 6c 6c 20  by "rowid" will 
1660: 62 65 20 75 6e 69 71 75 65 20 6f 76 65 72 20 61  be unique over a
1670: 6c 6c 20 65 6c 65 6d 65 6e 74 73 20 6f 66 20 74  ll elements of t
1680: 68 65 20 69 6e 64 65 78 2e 0a 3c 2f 70 3e 0a 0a  he index..</p>..
1690: 3c 74 63 6c 3e 66 69 67 75 72 65 20 34 20 23 66  <tcl>figure 4 #f
16a0: 69 67 34 20 69 64 78 31 2e 67 69 66 20 7b 41 6e  ig4 idx1.gif {An
16b0: 20 49 6e 64 65 78 20 4f 6e 20 54 68 65 20 46 72   Index On The Fr
16c0: 75 69 74 20 43 6f 6c 75 6d 6e 7d 3c 2f 74 63 6c  uit Column}</tcl
16d0: 3e 0a 0a 3c 70 3e 0a 57 69 74 68 20 74 68 65 20  >..<p>.With the 
16e0: 6e 65 77 20 69 6e 64 65 78 20 69 6e 20 70 6c 61  new index in pla
16f0: 63 65 2c 20 77 65 20 63 61 6e 20 64 65 76 69 73  ce, we can devis
1700: 65 20 61 6e 20 61 6c 74 65 72 6e 61 74 69 76 65  e an alternative
1710: 20 70 6c 61 6e 20 66 6f 72 20 74 68 65 0a 6f 72   plan for the.or
1720: 69 67 69 6e 61 6c 20 22 50 72 69 63 65 20 6f 66  iginal "Price of
1730: 20 50 65 61 63 68 65 73 22 20 71 75 65 72 79 2e   Peaches" query.
1740: 0a 3c 2f 70 3e 0a 0a 3c 74 63 6c 3e 63 6f 64 65  .</p>..<tcl>code
1750: 20 7b 0a 53 45 4c 45 43 54 20 70 72 69 63 65 20   {.SELECT price 
1760: 46 52 4f 4d 20 66 72 75 69 74 73 66 6f 72 73 61  FROM fruitsforsa
1770: 6c 65 20 57 48 45 52 45 20 66 72 75 69 74 3d 27  le WHERE fruit='
1780: 50 65 61 63 68 27 3b 0a 7d 3c 2f 74 63 6c 3e 0a  Peach';.}</tcl>.
1790: 0a 3c 70 3e 0a 54 68 65 20 71 75 65 72 79 20 73  .<p>.The query s
17a0: 74 61 72 74 73 20 62 79 20 64 6f 69 6e 67 20 61  tarts by doing a
17b0: 20 62 69 6e 61 72 79 20 73 65 61 72 63 68 20 6f   binary search o
17c0: 6e 20 74 68 65 20 49 64 78 31 20 69 6e 64 65 78  n the Idx1 index
17d0: 20 66 6f 72 20 65 6e 74 72 69 65 73 0a 74 68 61   for entries.tha
17e0: 74 20 68 61 76 65 20 66 72 75 69 74 3d 27 50 65  t have fruit='Pe
17f0: 61 63 68 27 2e 20 20 53 51 4c 69 74 65 20 63 61  ach'.  SQLite ca
1800: 6e 20 64 6f 20 74 68 69 73 20 62 69 6e 61 72 79  n do this binary
1810: 20 73 65 61 72 63 68 20 6f 6e 20 74 68 65 20 49   search on the I
1820: 64 78 31 20 69 6e 64 65 78 0a 62 75 74 20 6e 6f  dx1 index.but no
1830: 74 20 6f 6e 20 74 68 65 20 6f 72 69 67 69 6e 61  t on the origina
1840: 6c 20 46 72 75 69 74 73 46 6f 72 53 61 6c 65 20  l FruitsForSale 
1850: 74 61 62 6c 65 20 62 65 63 61 75 73 65 20 74 68  table because th
1860: 65 20 72 6f 77 73 20 69 6e 20 49 64 78 31 20 61  e rows in Idx1 a
1870: 72 65 20 73 6f 72 74 65 64 0a 62 79 20 74 68 65  re sorted.by the
1880: 20 22 66 72 75 69 74 22 20 63 6f 6c 75 6d 6e 2e   "fruit" column.
1890: 20 20 48 61 76 69 6e 67 20 66 6f 75 6e 64 20 61    Having found a
18a0: 20 72 6f 77 20 69 6e 20 74 68 65 20 49 64 78 31   row in the Idx1
18b0: 20 69 6e 64 65 78 20 74 68 61 74 20 68 61 73 0a   index that has.
18c0: 66 72 75 69 74 3d 27 50 65 61 63 68 27 2c 20 74  fruit='Peach', t
18d0: 68 65 20 64 61 74 61 62 61 73 65 20 65 6e 67 69  he database engi
18e0: 6e 65 20 63 61 6e 20 65 78 74 72 61 63 74 20 74  ne can extract t
18f0: 68 65 20 72 6f 77 69 64 20 66 6f 72 20 74 68 61  he rowid for tha
1900: 74 20 72 6f 77 2c 0a 74 68 65 6e 20 64 6f 20 61  t row,.then do a
1910: 20 73 65 70 61 72 61 74 65 20 62 69 6e 61 72 79   separate binary
1920: 20 73 65 61 72 63 68 20 6f 6e 20 74 68 65 20 6f   search on the o
1930: 72 69 67 69 6e 61 6c 20 46 72 75 69 74 73 46 6f  riginal FruitsFo
1940: 72 53 61 6c 65 20 74 61 62 6c 65 20 74 6f 20 66  rSale table to f
1950: 69 6e 64 20 74 68 65 0a 6f 72 69 67 69 6e 61 6c  ind the.original
1960: 20 72 6f 77 20 74 68 61 74 20 63 6f 6e 74 61 69   row that contai
1970: 6e 73 20 66 72 75 69 74 3d 27 50 65 61 63 68 27  ns fruit='Peach'
1980: 2e 20 20 46 72 6f 6d 20 74 68 65 20 72 6f 77 20  .  From the row 
1990: 69 6e 20 74 68 65 20 46 72 75 69 74 73 46 6f 72  in the FruitsFor
19a0: 53 61 6c 65 20 74 61 62 6c 65 2c 0a 53 51 4c 69  Sale table,.SQLi
19b0: 74 65 20 63 61 6e 20 65 78 74 72 61 63 74 20 74  te can extract t
19c0: 68 65 20 76 61 6c 75 65 20 6f 66 20 74 68 65 20  he value of the 
19d0: 70 72 69 63 65 20 63 6f 6c 75 6d 6e 2e 0a 54 68  price column..Th
19e0: 69 73 20 70 72 6f 63 65 64 75 72 65 20 69 73 20  is procedure is 
19f0: 69 6c 6c 75 73 74 72 61 74 65 64 20 62 79 20 3c  illustrated by <
1a00: 61 20 68 72 65 66 3d 22 23 66 69 67 35 22 3e 66  a href="#fig5">f
1a10: 69 67 75 72 65 20 35 3c 2f 61 3e 2e 0a 3c 2f 70  igure 5</a>..</p
1a20: 3e 0a 0a 3c 74 63 6c 3e 66 69 67 75 72 65 20 35  >..<tcl>figure 5
1a30: 20 23 66 69 67 35 20 69 64 78 31 6c 75 31 2e 67   #fig5 idx1lu1.g
1a40: 69 66 20 7b 49 6e 64 65 78 65 64 20 4c 6f 6f 6b  if {Indexed Look
1a50: 75 70 20 46 6f 72 20 54 68 65 20 50 72 69 63 65  up For The Price
1a60: 20 4f 66 20 50 65 61 63 68 65 73 7d 3c 2f 74 63   Of Peaches}</tc
1a70: 6c 3e 0a 0a 3c 70 3e 0a 53 51 4c 69 74 65 20 68  l>..<p>.SQLite h
1a80: 61 73 20 74 6f 20 64 6f 20 74 77 6f 20 62 69 6e  as to do two bin
1a90: 61 72 79 20 73 65 61 72 63 68 65 73 20 74 6f 20  ary searches to 
1aa0: 66 69 6e 64 20 74 68 65 20 70 72 69 63 65 20 6f  find the price o
1ab0: 66 20 70 65 61 63 68 65 73 20 75 73 69 6e 67 0a  f peaches using.
1ac0: 74 68 65 20 6d 65 74 68 6f 64 20 73 68 6f 77 20  the method show 
1ad0: 61 62 6f 76 65 2e 20 20 42 75 74 20 66 6f 72 20  above.  But for 
1ae0: 61 20 74 61 62 6c 65 20 77 69 74 68 20 61 20 6c  a table with a l
1af0: 61 72 67 65 20 6e 75 6d 62 65 72 20 6f 66 20 72  arge number of r
1b00: 6f 77 73 2c 20 74 68 69 73 0a 69 73 20 73 74 69  ows, this.is sti
1b10: 6c 6c 20 6d 75 63 68 20 66 61 73 74 65 72 20 74  ll much faster t
1b20: 68 61 6e 20 64 6f 69 6e 67 20 61 20 66 75 6c 6c  han doing a full
1b30: 20 74 61 62 6c 65 20 73 63 61 6e 2e 0a 3c 2f 70   table scan..</p
1b40: 3e 0a 0a 3c 68 33 3e 31 2e 34 20 4d 75 6c 74 69  >..<h3>1.4 Multi
1b50: 70 6c 65 20 52 65 73 75 6c 74 20 52 6f 77 73 3c  ple Result Rows<
1b60: 2f 68 33 3e 0a 0a 3c 70 3e 0a 49 6e 20 74 68 65  /h3>..<p>.In the
1b70: 20 70 72 65 76 69 6f 75 73 20 71 75 65 72 79 20   previous query 
1b80: 74 68 65 20 66 72 75 69 74 3d 27 50 65 61 63 68  the fruit='Peach
1b90: 27 20 63 6f 6e 73 74 72 61 69 6e 74 20 6e 61 72  ' constraint nar
1ba0: 72 6f 77 65 64 20 74 68 65 20 72 65 73 75 6c 74  rowed the result
1bb0: 0a 64 6f 77 6e 20 74 6f 20 61 20 73 69 6e 67 6c  .down to a singl
1bc0: 65 20 72 6f 77 2e 20 20 42 75 74 20 74 68 65 20  e row.  But the 
1bd0: 73 61 6d 65 20 74 65 63 68 6e 69 71 75 65 20 77  same technique w
1be0: 6f 72 6b 73 20 65 76 65 6e 20 69 66 20 6d 75 6c  orks even if mul
1bf0: 74 69 70 6c 65 0a 72 6f 77 73 20 61 72 65 20 6f  tiple.rows are o
1c00: 62 74 61 69 6e 65 64 2e 20 20 53 75 70 70 6f 73  btained.  Suppos
1c10: 65 20 77 65 20 6c 6f 6f 6b 65 64 20 75 70 20 74  e we looked up t
1c20: 68 65 20 70 72 69 63 65 20 6f 66 20 4f 72 61 6e  he price of Oran
1c30: 67 65 73 20 69 6e 73 74 65 61 64 20 0a 50 65 61  ges instead .Pea
1c40: 63 68 65 73 3a 0a 3c 2f 70 3e 0a 0a 3c 74 63 6c  ches:.</p>..<tcl
1c50: 3e 0a 63 6f 64 65 20 7b 53 45 4c 45 43 54 20 70  >.code {SELECT p
1c60: 72 69 63 65 20 46 52 4f 4d 20 66 72 75 69 74 73  rice FROM fruits
1c70: 66 6f 72 73 61 6c 65 20 57 48 45 52 45 20 66 72  forsale WHERE fr
1c80: 75 69 74 3d 27 4f 72 61 6e 67 65 27 7d 0a 66 69  uit='Orange'}.fi
1c90: 67 75 72 65 20 36 20 23 66 69 67 36 20 69 64 78  gure 6 #fig6 idx
1ca0: 31 6c 75 32 2e 67 69 66 20 7b 49 6e 64 65 78 65  1lu2.gif {Indexe
1cb0: 64 20 4c 6f 6f 6b 75 70 20 46 6f 72 20 54 68 65  d Lookup For The
1cc0: 20 50 72 69 63 65 20 4f 66 20 4f 72 61 6e 67 65   Price Of Orange
1cd0: 73 7d 0a 3c 2f 74 63 6c 3e 0a 0a 3c 70 3e 0a 49  s}.</tcl>..<p>.I
1ce0: 6e 20 74 68 69 73 20 63 61 73 65 2c 20 53 51 4c  n this case, SQL
1cf0: 69 74 65 20 73 74 69 6c 6c 20 64 6f 65 73 20 61  ite still does a
1d00: 20 73 69 6e 67 6c 65 20 62 69 6e 61 72 79 20 73   single binary s
1d10: 65 61 72 63 68 20 74 6f 20 66 69 6e 64 20 74 68  earch to find th
1d20: 65 20 66 69 72 73 74 0a 65 6e 74 72 79 20 6f 66  e first.entry of
1d30: 20 74 68 65 20 69 6e 64 65 78 20 77 68 65 72 65   the index where
1d40: 20 66 72 75 69 74 3d 27 4f 72 61 6e 67 65 27 2e   fruit='Orange'.
1d50: 20 20 54 68 65 6e 20 69 74 20 65 78 74 72 61 63    Then it extrac
1d60: 74 73 20 74 68 65 20 72 6f 77 69 64 20 66 72 6f  ts the rowid fro
1d70: 6d 0a 74 68 65 20 69 6e 64 65 78 20 61 6e 64 20  m.the index and 
1d80: 75 73 65 73 20 74 68 61 74 20 72 6f 77 69 64 20  uses that rowid 
1d90: 74 6f 20 6c 6f 6f 6b 75 70 20 74 68 65 20 6f 72  to lookup the or
1da0: 69 67 69 6e 61 6c 20 74 61 62 6c 65 20 65 6e 74  iginal table ent
1db0: 72 79 20 76 69 61 0a 62 69 6e 61 72 79 20 73 65  ry via.binary se
1dc0: 61 72 63 68 20 61 6e 64 20 6f 75 74 70 75 74 20  arch and output 
1dd0: 74 68 65 20 70 72 69 63 65 20 66 72 6f 6d 20 74  the price from t
1de0: 68 65 20 6f 72 69 67 69 6e 61 6c 20 74 61 62 6c  he original tabl
1df0: 65 2e 20 20 42 75 74 20 69 6e 73 74 65 61 64 0a  e.  But instead.
1e00: 6f 66 20 71 75 69 74 69 6e 67 2c 20 74 68 65 20  of quiting, the 
1e10: 64 61 74 61 62 61 73 65 20 65 6e 67 69 6e 65 20  database engine 
1e20: 74 68 65 6e 20 61 64 76 61 6e 63 65 73 20 74 6f  then advances to
1e30: 20 74 68 65 20 6e 65 78 74 20 72 6f 77 20 6f 66   the next row of
1e40: 20 69 6e 64 65 78 0a 74 6f 20 72 65 70 65 61 74   index.to repeat
1e50: 20 74 68 65 20 70 72 6f 63 65 73 73 20 66 6f 72   the process for
1e60: 20 6e 65 78 74 20 66 72 75 69 74 3d 27 4f 72 61   next fruit='Ora
1e70: 6e 67 65 27 20 65 6e 74 72 79 2e 20 20 41 64 76  nge' entry.  Adv
1e80: 61 6e 63 69 6e 67 20 74 6f 20 74 68 65 0a 6e 65  ancing to the.ne
1e90: 78 74 20 72 6f 77 20 6f 66 20 61 6e 20 69 6e 64  xt row of an ind
1ea0: 65 78 20 28 6f 72 20 74 61 62 6c 65 29 20 69 73  ex (or table) is
1eb0: 20 6d 75 63 68 20 6c 65 73 73 20 63 6f 73 74 6c   much less costl
1ec0: 79 20 74 68 61 6e 20 64 6f 69 6e 67 20 61 20 62  y than doing a b
1ed0: 69 6e 61 72 79 0a 73 65 61 72 63 68 20 73 69 6e  inary.search sin
1ee0: 63 65 20 74 68 65 20 6e 65 78 74 20 72 6f 77 20  ce the next row 
1ef0: 69 73 20 6f 66 74 65 6e 20 6c 6f 63 61 74 65 64  is often located
1f00: 20 6f 6e 20 74 68 65 20 73 61 6d 65 20 64 61 74   on the same dat
1f10: 61 62 61 73 65 20 70 61 67 65 20 61 73 0a 74 68  abase page as.th
1f20: 65 20 63 75 72 72 65 6e 74 20 72 6f 77 2e 20 20  e current row.  
1f30: 49 6e 20 66 61 63 74 2c 20 74 68 65 20 63 6f 73  In fact, the cos
1f40: 74 20 6f 66 20 61 64 76 61 6e 63 69 6e 67 20 74  t of advancing t
1f50: 6f 20 74 68 65 20 6e 65 78 74 20 72 6f 77 20 69  o the next row i
1f60: 73 20 73 6f 0a 63 68 65 61 70 20 69 6e 20 63 6f  s so.cheap in co
1f70: 6d 70 61 72 69 73 6f 6e 20 74 6f 20 61 20 62 69  mparison to a bi
1f80: 6e 61 72 79 20 73 65 61 72 63 68 20 74 68 61 74  nary search that
1f90: 20 77 65 20 75 73 75 61 6c 6c 79 20 69 67 6e 6f   we usually igno
1fa0: 72 65 20 69 74 2e 20 20 53 6f 0a 6f 75 72 20 65  re it.  So.our e
1fb0: 73 74 69 6d 61 74 65 20 66 6f 72 20 74 68 65 20  stimate for the 
1fc0: 74 6f 74 61 6c 20 63 6f 73 74 20 6f 66 20 74 68  total cost of th
1fd0: 69 73 20 71 75 65 72 79 20 69 73 20 33 20 62 69  is query is 3 bi
1fe0: 6e 61 72 79 20 73 65 61 72 63 68 65 73 2e 0a 49  nary searches..I
1ff0: 66 20 74 68 65 20 6e 75 6d 62 65 72 20 6f 66 20  f the number of 
2000: 72 6f 77 73 20 6f 66 20 6f 75 74 70 75 74 20 69  rows of output i
2010: 73 20 4b 20 61 6e 64 20 74 68 65 20 6e 75 6d 62  s K and the numb
2020: 65 72 20 6f 66 20 72 6f 77 73 20 69 6e 20 74 68  er of rows in th
2030: 65 20 74 61 62 6c 65 0a 69 73 20 4e 2c 20 74 68  e table.is N, th
2040: 65 6e 20 69 6e 20 67 65 6e 65 72 61 6c 20 74 68  en in general th
2050: 65 20 63 6f 73 74 20 6f 66 20 64 6f 69 6e 67 20  e cost of doing 
2060: 74 68 65 20 71 75 65 72 79 20 70 72 6f 70 6f 72  the query propor
2070: 74 69 6f 6e 61 6c 0a 74 6f 20 28 4b 2b 31 29 2a  tional.to (K+1)*
2080: 6c 6f 67 4e 2e 0a 3c 2f 70 3e 0a 0a 3c 68 33 3e  logN..</p>..<h3>
2090: 31 2e 35 20 4d 75 6c 74 69 70 6c 65 20 41 4e 44  1.5 Multiple AND
20a0: 2d 43 6f 6e 6e 65 63 74 65 64 20 57 48 45 52 45  -Connected WHERE
20b0: 2d 43 6c 61 75 73 65 20 54 65 72 6d 73 3c 2f 68  -Clause Terms</h
20c0: 33 3e 0a 0a 3c 70 3e 0a 4e 65 78 74 2c 20 73 75  3>..<p>.Next, su
20d0: 70 70 6f 73 65 20 74 68 61 74 20 79 6f 75 20 77  ppose that you w
20e0: 61 6e 74 20 74 6f 20 6c 6f 6f 6b 20 75 70 20 74  ant to look up t
20f0: 68 65 20 70 72 69 63 65 20 6f 66 20 6e 6f 74 20  he price of not 
2100: 6a 75 73 74 20 61 6e 79 20 6f 72 61 6e 67 65 2c  just any orange,
2110: 0a 62 75 74 20 73 70 65 63 69 66 69 63 61 6c 6c  .but specificall
2120: 79 20 43 61 6c 69 66 6f 72 6e 69 61 2d 67 72 6f  y California-gro
2130: 77 6e 20 6f 72 61 6e 67 65 73 2e 20 20 54 68 65  wn oranges.  The
2140: 20 61 70 70 72 6f 70 72 69 61 74 65 20 71 75 65   appropriate que
2150: 72 79 20 77 6f 75 6c 64 0a 62 65 20 61 73 20 66  ry would.be as f
2160: 6f 6c 6c 6f 77 73 3a 0a 3c 2f 70 3e 0a 0a 3c 74  ollows:.</p>..<t
2170: 63 6c 3e 0a 63 6f 64 65 20 7b 53 45 4c 45 43 54  cl>.code {SELECT
2180: 20 70 72 69 63 65 20 46 52 4f 4d 20 66 72 75 69   price FROM frui
2190: 74 73 66 6f 72 73 61 6c 65 20 57 48 45 52 45 20  tsforsale WHERE 
21a0: 66 72 75 69 74 3d 27 4f 72 61 6e 67 65 27 20 41  fruit='Orange' A
21b0: 4e 44 20 73 74 61 74 65 3d 27 43 41 27 7d 0a 66  ND state='CA'}.f
21c0: 69 67 75 72 65 20 37 20 23 66 69 67 37 20 69 64  igure 7 #fig7 id
21d0: 78 31 6c 75 33 2e 67 69 66 20 7b 49 6e 64 65 78  x1lu3.gif {Index
21e0: 65 64 20 4c 6f 6f 6b 75 70 20 4f 66 20 43 61 6c  ed Lookup Of Cal
21f0: 69 66 6f 72 6e 69 61 20 4f 72 61 6e 67 65 73 7d  ifornia Oranges}
2200: 0a 3c 2f 74 63 6c 3e 0a 0a 3c 70 3e 0a 4f 6e 65  .</tcl>..<p>.One
2210: 20 61 70 70 72 6f 61 63 68 20 74 6f 20 74 68 69   approach to thi
2220: 73 20 71 75 65 72 79 20 69 73 20 74 6f 20 75 73  s query is to us
2230: 65 20 74 68 65 20 66 72 75 69 74 3d 27 4f 72 61  e the fruit='Ora
2240: 6e 67 65 27 20 74 65 72 6d 20 6f 66 20 74 68 65  nge' term of the
2250: 20 57 48 45 52 45 0a 63 6c 61 75 73 65 20 74 6f   WHERE.clause to
2260: 20 66 69 6e 64 20 61 6c 6c 20 72 6f 77 73 20 64   find all rows d
2270: 65 61 6c 69 6e 67 20 77 69 74 68 20 6f 72 61 6e  ealing with oran
2280: 67 65 73 2c 20 74 68 65 6e 20 66 69 6c 74 65 72  ges, then filter
2290: 20 74 68 6f 73 65 20 72 6f 77 73 0a 62 79 20 72   those rows.by r
22a0: 65 6a 65 63 74 69 6e 67 20 61 6e 79 20 74 68 61  ejecting any tha
22b0: 74 20 61 72 65 20 66 72 6f 6d 20 73 74 61 74 65  t are from state
22c0: 73 20 6f 74 68 65 72 20 74 68 61 6e 20 43 61 6c  s other than Cal
22d0: 69 66 6f 72 6e 69 61 2e 20 20 54 68 69 73 0a 70  ifornia.  This.p
22e0: 72 6f 63 65 73 73 20 69 73 20 73 68 6f 77 73 20  rocess is shows 
22f0: 62 79 20 3c 61 20 68 72 65 66 3d 22 23 66 69 67  by <a href="#fig
2300: 37 22 3e 66 69 67 75 72 65 20 37 3c 2f 61 3e 20  7">figure 7</a> 
2310: 61 62 6f 76 65 2e 20 20 54 68 69 73 20 69 73 20  above.  This is 
2320: 61 20 70 65 72 66 65 63 74 6c 79 0a 72 65 61 73  a perfectly.reas
2330: 6f 6e 61 62 6c 65 20 61 70 70 72 6f 61 63 68 20  onable approach 
2340: 69 6e 20 6d 6f 73 74 20 63 61 73 65 73 2e 20 20  in most cases.  
2350: 59 65 73 2c 20 74 68 65 20 64 61 74 61 62 61 73  Yes, the databas
2360: 65 20 65 6e 67 69 6e 65 20 64 69 64 20 68 61 76  e engine did hav
2370: 65 0a 74 6f 20 64 6f 20 61 6e 20 65 78 74 72 61  e.to do an extra
2380: 20 62 69 6e 61 72 79 20 73 65 61 72 63 68 20 66   binary search f
2390: 6f 72 20 74 68 65 20 46 6c 6f 72 69 64 61 20 6f  or the Florida o
23a0: 72 61 6e 67 65 20 72 6f 77 20 74 68 61 74 20 77  range row that w
23b0: 61 73 0a 6c 61 74 65 72 20 72 65 6a 65 63 74 65  as.later rejecte
23c0: 64 2c 20 73 6f 20 69 74 20 77 61 73 20 6e 6f 74  d, so it was not
23d0: 20 61 73 20 65 66 66 69 63 69 65 6e 74 20 61 73   as efficient as
23e0: 20 77 65 20 6d 69 67 68 74 20 68 6f 70 65 2c 20   we might hope, 
23f0: 74 68 6f 75 67 68 0a 66 6f 72 20 6d 61 6e 79 20  though.for many 
2400: 61 70 70 6c 69 63 61 74 69 6f 6e 73 20 69 74 20  applications it 
2410: 69 73 20 65 66 66 69 63 69 65 6e 74 20 65 6e 6f  is efficient eno
2420: 75 67 68 2e 20 20 0a 3c 2f 70 3e 0a 0a 3c 70 3e  ugh.  .</p>..<p>
2430: 0a 53 75 70 70 6f 73 65 20 74 68 61 74 20 69 6e  .Suppose that in
2440: 20 61 64 64 69 74 69 6f 6e 20 74 6f 20 74 68 65   addition to the
2450: 20 69 6e 64 65 78 20 6f 6e 20 22 66 72 75 69 74   index on "fruit
2460: 22 20 74 68 65 72 65 20 77 61 73 20 61 6c 73 6f  " there was also
2470: 0a 61 6e 20 69 6e 64 65 78 20 6f 6e 20 22 73 74  .an index on "st
2480: 61 74 65 22 2e 0a 3c 2f 70 3e 0a 0a 3c 74 63 6c  ate"..</p>..<tcl
2490: 3e 0a 63 6f 64 65 20 7b 43 52 45 41 54 45 20 49  >.code {CREATE I
24a0: 4e 44 45 58 20 49 64 78 32 20 4f 4e 20 66 72 75  NDEX Idx2 ON fru
24b0: 69 74 73 66 6f 72 73 61 6c 65 28 73 74 61 74 65  itsforsale(state
24c0: 29 3b 7d 0a 66 69 67 75 72 65 20 38 20 23 66 69  );}.figure 8 #fi
24d0: 67 38 20 69 64 78 32 2e 67 69 66 20 7b 49 6e 64  g8 idx2.gif {Ind
24e0: 65 78 20 4f 6e 20 54 68 65 20 53 74 61 74 65 20  ex On The State 
24f0: 43 6f 6c 75 6d 6e 7d 0a 3c 2f 74 63 6c 3e 0a 0a  Column}.</tcl>..
2500: 3c 70 3e 0a 54 68 65 20 22 73 74 61 74 65 22 20  <p>.The "state" 
2510: 69 6e 64 65 78 20 77 6f 72 6b 73 20 6a 75 73 74  index works just
2520: 20 6c 69 6b 65 20 74 68 65 20 22 66 72 75 69 74   like the "fruit
2530: 22 20 69 6e 64 65 78 20 69 6e 20 74 68 61 74 20  " index in that 
2540: 69 74 20 69 73 20 61 0a 6e 65 77 20 74 61 62 6c  it is a.new tabl
2550: 65 20 77 69 74 68 20 61 6e 20 65 78 74 72 61 20  e with an extra 
2560: 63 6f 6c 75 6d 6e 20 69 6e 20 66 72 6f 6e 74 20  column in front 
2570: 6f 66 20 74 68 65 20 72 6f 77 69 64 20 61 6e 64  of the rowid and
2580: 20 73 6f 72 74 65 64 20 62 79 0a 74 68 61 74 20   sorted by.that 
2590: 65 78 74 72 61 20 63 6f 6c 75 6d 6e 20 61 73 20  extra column as 
25a0: 74 68 65 20 70 72 69 6d 61 72 79 20 6b 65 79 2e  the primary key.
25b0: 20 20 54 68 65 20 6f 6e 6c 79 20 64 69 66 66 65    The only diffe
25c0: 72 65 6e 63 65 20 69 73 20 74 68 61 74 0a 69 6e  rence is that.in
25d0: 20 49 64 78 32 2c 20 74 68 65 20 66 69 72 73 74   Idx2, the first
25e0: 20 63 6f 6c 75 6d 6e 20 69 73 20 22 73 74 61 74   column is "stat
25f0: 65 22 20 69 6e 73 74 65 61 64 20 6f 66 20 22 66  e" instead of "f
2600: 72 75 69 74 22 20 61 73 20 69 74 20 69 73 20 77  ruit" as it is w
2610: 69 74 68 0a 49 64 78 31 2e 20 20 49 6e 20 6f 75  ith.Idx1.  In ou
2620: 72 20 65 78 61 6d 70 6c 65 20 64 61 74 61 20 73  r example data s
2630: 65 74 2c 20 74 68 65 20 69 73 20 6d 6f 72 65 20  et, the is more 
2640: 72 65 64 75 6e 64 61 6e 63 79 20 69 6e 20 74 68  redundancy in th
2650: 65 20 22 73 74 61 74 65 22 0a 63 6f 6c 75 6d 6e  e "state".column
2660: 20 61 6e 64 20 73 6f 20 74 68 65 79 20 61 72 65   and so they are
2670: 20 6d 6f 72 65 20 64 75 70 6c 69 63 61 74 65 20   more duplicate 
2680: 65 6e 74 72 69 65 73 2e 20 20 54 68 65 20 74 69  entries.  The ti
2690: 65 73 20 61 72 65 20 73 74 69 6c 6c 0a 72 65 73  es are still.res
26a0: 6f 6c 76 65 64 20 75 73 69 6e 67 20 74 68 65 20  olved using the 
26b0: 72 6f 77 69 64 2e 0a 3c 2f 70 3e 0a 0a 3c 70 3e  rowid..</p>..<p>
26c0: 0a 55 73 69 6e 67 20 74 68 65 20 6e 65 77 20 49  .Using the new I
26d0: 64 78 32 20 69 6e 64 65 78 20 6f 6e 20 22 73 74  dx2 index on "st
26e0: 61 74 65 22 2c 20 53 51 4c 69 74 65 20 68 61 73  ate", SQLite has
26f0: 20 61 6e 6f 74 68 65 72 20 6f 70 74 69 6f 6e 20   another option 
2700: 66 6f 72 0a 6c 6f 6f 6b 75 70 20 75 70 20 74 68  for.lookup up th
2710: 65 20 70 72 69 63 65 20 6f 66 20 43 61 6c 69 66  e price of Calif
2720: 6f 72 6e 69 61 20 6f 72 61 6e 67 65 73 3a 20 20  ornia oranges:  
2730: 69 74 20 63 61 6e 20 6c 6f 6f 6b 20 75 70 20 65  it can look up e
2740: 76 65 72 79 20 72 6f 77 0a 74 68 61 74 20 63 6f  very row.that co
2750: 6e 74 61 69 6e 73 20 66 72 75 69 74 20 66 72 6f  ntains fruit fro
2760: 6d 20 43 61 6c 69 66 6f 72 6e 69 61 20 61 6e 64  m California and
2770: 20 66 69 6c 74 65 72 20 6f 75 74 20 74 68 6f 73   filter out thos
2780: 65 20 72 6f 77 73 20 74 68 61 74 0a 61 72 65 20  e rows that.are 
2790: 6e 6f 74 20 6f 72 61 6e 67 65 73 2e 0a 3c 2f 70  not oranges..</p
27a0: 3e 0a 0a 3c 74 63 6c 3e 66 69 67 75 72 65 20 39  >..<tcl>figure 9
27b0: 20 23 66 69 67 39 20 69 64 78 32 6c 75 31 2e 67   #fig9 idx2lu1.g
27c0: 69 66 20 7b 49 6e 64 65 78 65 64 20 4c 6f 6f 6b  if {Indexed Look
27d0: 75 70 20 4f 66 20 43 61 6c 69 66 6f 72 6e 69 61  up Of California
27e0: 20 4f 72 61 6e 67 65 73 7d 3c 2f 74 63 6c 3e 0a   Oranges}</tcl>.
27f0: 0a 3c 70 3e 0a 55 73 69 6e 67 20 49 64 78 32 20  .<p>.Using Idx2 
2800: 69 6e 73 74 65 61 64 20 6f 66 20 49 64 78 31 20  instead of Idx1 
2810: 63 61 75 73 65 73 20 53 51 4c 69 74 65 20 74 6f  causes SQLite to
2820: 20 65 78 61 6d 69 6e 65 20 61 20 64 69 66 66 65   examine a diffe
2830: 72 65 6e 74 20 73 65 74 20 6f 66 0a 72 6f 77 73  rent set of.rows
2840: 2c 20 62 75 74 20 69 74 20 67 65 74 73 20 74 68  , but it gets th
2850: 65 20 73 61 6d 65 20 61 6e 73 77 65 72 20 69 6e  e same answer in
2860: 20 74 68 65 20 65 6e 64 20 28 77 68 69 63 68 20   the end (which 
2870: 69 73 20 76 65 72 79 20 69 6d 70 6f 72 74 61 6e  is very importan
2880: 74 20 2d 0a 72 65 6d 65 6d 62 65 72 20 74 68 61  t -.remember tha
2890: 74 20 69 6e 64 69 63 65 73 20 73 68 6f 75 6c 64  t indices should
28a0: 20 6e 65 76 65 72 20 63 68 61 6e 67 65 20 74 68   never change th
28b0: 65 20 61 6e 73 77 65 72 2c 20 6f 6e 6c 79 20 68  e answer, only h
28c0: 65 6c 70 20 53 51 4c 69 74 65 20 74 6f 0a 67 65  elp SQLite to.ge
28d0: 74 20 74 6f 20 74 68 65 20 61 6e 73 77 65 72 20  t to the answer 
28e0: 6d 6f 72 65 20 71 75 69 63 6b 6c 79 29 20 61 6e  more quickly) an
28f0: 64 20 69 74 20 64 6f 65 73 20 74 68 65 20 73 61  d it does the sa
2900: 6d 65 20 61 6d 6f 75 6e 74 20 6f 66 20 77 6f 72  me amount of wor
2910: 6b 2e 0a 53 6f 20 74 68 65 20 49 64 78 32 20 69  k..So the Idx2 i
2920: 6e 64 65 78 20 64 69 64 20 6e 6f 74 20 68 65 6c  ndex did not hel
2930: 70 20 70 65 72 66 6f 72 6d 61 6e 63 65 20 69 6e  p performance in
2940: 20 74 68 69 73 20 63 61 73 65 2e 0a 3c 2f 70 3e   this case..</p>
2950: 0a 0a 3c 70 3e 0a 54 68 65 20 6c 61 73 74 20 74  ..<p>.The last t
2960: 77 6f 20 71 75 65 72 69 65 73 20 74 61 6b 65 20  wo queries take 
2970: 74 68 65 20 73 61 6d 65 20 61 6d 6f 75 6e 74 20  the same amount 
2980: 6f 66 20 74 69 6d 65 2c 20 69 6e 20 6f 75 72 20  of time, in our 
2990: 65 78 61 6d 70 6c 65 2e 0a 53 6f 20 77 68 69 63  example..So whic
29a0: 68 20 69 6e 64 65 78 2c 20 49 64 78 31 20 6f 72  h index, Idx1 or
29b0: 20 49 64 78 32 2c 20 77 69 6c 6c 20 53 51 4c 69   Idx2, will SQLi
29c0: 74 65 20 63 68 6f 6f 73 65 3f 20 20 49 66 20 74  te choose?  If t
29d0: 68 65 0a 5b 41 4e 41 4c 59 5a 45 5d 20 63 6f 6d  he.[ANALYZE] com
29e0: 6d 61 6e 64 20 68 61 73 20 62 65 65 6e 20 72 75  mand has been ru
29f0: 6e 20 6f 6e 20 74 68 65 20 64 61 74 61 62 61 73  n on the databas
2a00: 65 2c 20 73 6f 20 74 68 61 74 20 53 51 4c 69 74  e, so that SQLit
2a10: 65 20 68 61 73 0a 68 61 64 20 61 6e 20 6f 70 70  e has.had an opp
2a20: 6f 72 74 75 6e 69 74 79 20 74 6f 20 67 61 74 68  ortunity to gath
2a30: 65 72 20 73 74 61 74 69 73 74 69 63 73 20 61 62  er statistics ab
2a40: 6f 75 74 20 74 68 65 20 61 76 61 69 6c 61 62 6c  out the availabl
2a50: 65 20 69 6e 64 69 63 65 73 2c 0a 74 68 65 6e 20  e indices,.then 
2a60: 53 51 4c 69 74 65 20 77 69 6c 6c 20 6b 6e 6f 77  SQLite will know
2a70: 20 74 68 61 74 20 74 68 65 20 49 64 78 31 20 74   that the Idx1 t
2a80: 61 62 6c 65 20 75 73 75 61 6c 6c 79 20 6e 61 72  able usually nar
2a90: 72 6f 77 73 20 74 68 65 20 73 65 61 72 63 68 0a  rows the search.
2aa0: 64 6f 77 6e 20 74 6f 20 61 20 73 69 6e 67 6c 65  down to a single
2ab0: 20 69 74 65 6d 20 28 6f 75 72 20 65 78 61 6d 70   item (our examp
2ac0: 6c 65 20 6f 66 20 66 72 75 69 74 3d 27 4f 72 61  le of fruit='Ora
2ad0: 6e 67 65 27 20 69 73 20 74 68 65 20 65 78 63 65  nge' is the exce
2ae0: 70 74 69 6f 6e 0a 74 6f 20 74 68 69 73 20 72 75  ption.to this ru
2af0: 6c 65 29 20 77 68 65 72 65 20 61 73 20 74 68 65  le) where as the
2b00: 20 49 64 78 20 74 61 62 6c 65 20 77 69 6c 6c 20   Idx table will 
2b10: 6e 6f 72 6d 61 6c 6c 79 20 6f 6e 6c 79 20 6e 61  normally only na
2b20: 72 72 6f 77 20 74 68 65 20 0a 73 65 61 72 63 68  rrow the .search
2b30: 20 64 6f 77 6e 20 74 6f 20 74 77 6f 20 72 6f 77   down to two row
2b40: 73 2e 20 20 53 6f 2c 20 69 66 20 61 6c 6c 20 65  s.  So, if all e
2b50: 6c 73 65 20 69 73 20 65 71 75 61 6c 2c 20 53 51  lse is equal, SQ
2b60: 4c 69 74 65 20 77 69 6c 6c 0a 63 68 6f 6f 73 65  Lite will.choose
2b70: 20 49 64 78 31 20 77 69 74 68 20 74 68 65 20 68   Idx1 with the h
2b80: 6f 70 65 20 6f 66 20 6e 61 72 72 6f 77 69 6e 67  ope of narrowing
2b90: 20 74 68 65 20 73 65 61 72 63 68 20 74 6f 20 61   the search to a
2ba0: 73 20 73 6d 61 6c 6c 0a 61 20 6e 75 6d 62 65 72  s small.a number
2bb0: 20 6f 66 20 72 6f 77 73 20 61 73 20 70 6f 73 73   of rows as poss
2bc0: 69 62 6c 65 2e 20 20 54 68 69 73 20 63 68 6f 69  ible.  This choi
2bd0: 63 65 20 69 73 20 6f 6e 6c 79 20 70 6f 73 73 69  ce is only possi
2be0: 62 6c 65 20 62 65 63 61 75 73 65 0a 6f 66 20 74  ble because.of t
2bf0: 68 65 20 73 74 61 74 69 73 74 69 63 73 20 70 72  he statistics pr
2c00: 6f 76 69 64 65 64 20 62 79 20 5b 41 4e 41 4c 59  ovided by [ANALY
2c10: 5a 45 5d 2e 20 20 49 66 20 5b 41 4e 41 4c 59 5a  ZE].  If [ANALYZ
2c20: 45 5d 20 68 61 73 20 6e 6f 74 20 62 65 65 6e 0a  E] has not been.
2c30: 72 75 6e 20 74 68 65 6e 20 74 68 65 20 63 68 6f  run then the cho
2c40: 69 63 65 20 6f 66 20 77 68 69 63 68 20 69 6e 64  ice of which ind
2c50: 65 78 20 74 6f 20 75 73 65 20 69 73 20 61 72 62  ex to use is arb
2c60: 69 74 72 61 72 79 2e 0a 3c 2f 70 3e 0a 0a 3c 68  itrary..</p>..<h
2c70: 33 3e 31 2e 36 20 4d 75 6c 74 69 2d 43 6f 6c 75  3>1.6 Multi-Colu
2c80: 6d 6e 20 49 6e 64 69 63 65 73 3c 2f 68 33 3e 0a  mn Indices</h3>.
2c90: 0a 3c 70 3e 0a 54 6f 20 67 65 74 20 74 68 65 20  .<p>.To get the 
2ca0: 6d 61 78 69 6d 75 6d 20 70 65 72 66 6f 72 6d 61  maximum performa
2cb0: 6e 63 65 20 6f 75 74 20 6f 66 20 61 20 71 75 65  nce out of a que
2cc0: 72 79 20 77 69 74 68 20 6d 75 6c 74 69 70 6c 65  ry with multiple
2cd0: 20 41 4e 44 2d 63 6f 6e 6e 65 63 74 65 64 0a 74   AND-connected.t
2ce0: 65 72 6d 73 20 69 6e 20 74 68 65 20 57 48 45 52  erms in the WHER
2cf0: 45 20 63 6c 61 75 73 65 2c 20 79 6f 75 20 72 65  E clause, you re
2d00: 61 6c 6c 79 20 77 61 6e 74 20 61 20 6d 75 6c 74  ally want a mult
2d10: 69 2d 63 6f 6c 75 6d 6e 20 69 6e 64 65 78 20 77  i-column index w
2d20: 69 74 68 0a 63 6f 6c 75 6d 6e 73 20 66 6f 72 20  ith.columns for 
2d30: 65 61 63 68 20 6f 66 20 74 68 65 20 41 4e 44 20  each of the AND 
2d40: 74 65 72 6d 73 2e 20 20 49 6e 20 74 68 69 73 20  terms.  In this 
2d50: 63 61 73 65 20 77 65 20 63 72 65 61 74 65 20 61  case we create a
2d60: 20 6e 65 77 20 69 6e 64 65 78 0a 6f 6e 20 74 68   new index.on th
2d70: 65 20 22 66 72 75 69 74 22 20 61 6e 64 20 22 73  e "fruit" and "s
2d80: 74 61 74 65 22 20 63 6f 6c 75 6d 6e 73 20 6f 66  tate" columns of
2d90: 20 46 72 75 69 74 73 46 6f 72 53 61 6c 65 3a 0a   FruitsForSale:.
2da0: 3c 2f 70 3e 0a 0a 3c 74 63 6c 3e 0a 63 6f 64 65  </p>..<tcl>.code
2db0: 20 7b 43 52 45 41 54 45 20 49 4e 44 45 58 20 49   {CREATE INDEX I
2dc0: 64 78 33 20 4f 4e 20 46 72 75 69 74 73 46 6f 72  dx3 ON FruitsFor
2dd0: 53 61 6c 65 28 66 72 75 69 74 2c 20 73 74 61 74  Sale(fruit, stat
2de0: 65 29 3b 7d 0a 66 69 67 75 72 65 20 31 20 23 66  e);}.figure 1 #f
2df0: 69 67 31 30 20 69 64 78 33 2e 67 69 66 20 7b 41  ig10 idx3.gif {A
2e00: 20 54 77 6f 2d 43 6f 6c 75 6d 6e 20 49 6e 64 65   Two-Column Inde
2e10: 78 7d 0a 3c 2f 74 63 6c 3e 0a 0a 3c 70 3e 0a 41  x}.</tcl>..<p>.A
2e20: 20 6d 75 6c 74 69 2d 63 6f 6c 75 6d 6e 20 69 6e   multi-column in
2e30: 64 65 78 20 66 6f 6c 6c 6f 77 73 20 74 68 65 20  dex follows the 
2e40: 73 61 6d 65 20 70 61 74 74 65 72 6e 20 61 73 20  same pattern as 
2e50: 61 20 73 69 6e 67 6c 65 2d 63 6f 6c 75 6d 6e 20  a single-column 
2e60: 69 6e 64 65 78 3b 0a 74 68 65 20 69 6e 64 65 78  index;.the index
2e70: 65 64 20 63 6f 6c 75 6d 6e 73 20 61 72 65 20 61  ed columns are a
2e80: 64 64 65 64 20 69 6e 20 66 72 6f 6e 74 20 6f 66  dded in front of
2e90: 20 74 68 65 20 72 6f 77 69 64 2e 20 20 54 68 65   the rowid.  The
2ea0: 20 6f 6e 6c 79 20 64 69 66 66 65 72 65 6e 63 65   only difference
2eb0: 0a 69 73 20 74 68 61 74 20 6e 6f 77 20 6d 75 6c  .is that now mul
2ec0: 74 69 70 6c 65 20 63 6f 6c 75 6d 6e 73 20 61 72  tiple columns ar
2ed0: 65 20 61 64 64 65 64 2e 20 20 54 68 65 20 6c 65  e added.  The le
2ee0: 66 74 2d 6d 6f 73 74 20 63 6f 6c 75 6d 6e 20 69  ft-most column i
2ef0: 73 20 74 68 65 0a 70 72 69 6d 61 72 79 20 6b 65  s the.primary ke
2f00: 79 20 75 73 65 64 20 66 6f 72 20 6f 72 64 65 72  y used for order
2f10: 69 6e 67 20 74 68 65 20 72 6f 77 73 20 69 6e 20  ing the rows in 
2f20: 74 68 65 20 69 6e 64 65 78 2e 20 20 54 68 65 20  the index.  The 
2f30: 73 65 63 6f 6e 64 20 63 6f 6c 75 6d 6e 20 69 73  second column is
2f40: 0a 75 73 65 64 20 74 6f 20 62 72 65 61 6b 20 74  .used to break t
2f50: 69 65 73 20 69 6e 20 74 68 65 20 6c 65 66 74 2d  ies in the left-
2f60: 6d 6f 73 74 20 63 6f 6c 75 6d 6e 2e 20 20 49 66  most column.  If
2f70: 20 74 68 65 72 65 20 77 65 72 65 20 61 20 74 68   there were a th
2f80: 69 72 64 20 63 6f 6c 75 6d 6e 2c 0a 69 74 20 77  ird column,.it w
2f90: 6f 75 6c 64 20 62 65 20 75 73 65 64 20 74 6f 20  ould be used to 
2fa0: 62 72 65 61 6b 20 74 69 65 73 20 66 6f 72 20 74  break ties for t
2fb0: 68 65 20 66 69 72 73 74 20 74 6f 20 63 6f 6c 75  he first to colu
2fc0: 6d 6e 73 2e 20 20 41 6e 64 20 73 6f 20 66 6f 72  mns.  And so for
2fd0: 74 68 20 66 6f 72 0a 61 73 20 6d 61 6e 79 20 63  th for.as many c
2fe0: 6f 6c 75 6d 6e 73 20 61 73 20 74 68 65 69 72 20  olumns as their 
2ff0: 61 72 65 20 69 6e 20 74 68 65 20 69 6e 64 65 78  are in the index
3000: 2e 20 20 42 65 63 61 75 73 65 20 72 6f 77 69 64  .  Because rowid
3010: 20 69 73 20 67 75 61 72 61 6e 74 65 65 64 0a 74   is guaranteed.t
3020: 6f 20 62 65 20 75 6e 69 71 75 65 2c 20 65 76 65  o be unique, eve
3030: 72 79 20 72 6f 77 20 6f 66 20 74 68 65 20 69 6e  ry row of the in
3040: 64 65 78 20 77 69 6c 6c 20 62 65 20 75 6e 69 71  dex will be uniq
3050: 75 65 20 65 76 65 6e 20 69 66 20 61 6c 6c 20 6f  ue even if all o
3060: 66 20 74 68 65 0a 63 6f 6e 74 65 6e 74 20 63 6f  f the.content co
3070: 6c 75 6d 6e 73 20 66 6f 72 20 74 77 6f 20 72 6f  lumns for two ro
3080: 77 73 20 61 72 65 20 74 68 65 20 73 61 6d 65 2e  ws are the same.
3090: 20 20 54 68 61 74 20 63 61 73 65 20 64 6f 65 73    That case does
30a0: 20 6e 6f 74 20 68 61 70 70 65 6e 0a 69 6e 20 6f   not happen.in o
30b0: 75 72 20 73 61 6d 70 6c 65 20 64 61 74 61 2c 20  ur sample data, 
30c0: 62 75 74 20 74 68 65 72 65 20 69 73 20 6f 6e 65  but there is one
30d0: 20 63 61 73 65 20 28 66 72 75 69 74 3d 27 4f 72   case (fruit='Or
30e0: 61 6e 67 65 27 29 20 77 68 65 72 65 20 74 68 65  ange') where the
30f0: 72 65 0a 69 73 20 61 20 74 69 65 20 6f 6e 20 74  re.is a tie on t
3100: 68 65 20 66 69 72 73 74 20 63 6f 6c 75 6d 6e 20  he first column 
3110: 77 68 69 63 68 20 6d 75 73 74 20 62 65 20 62 72  which must be br
3120: 6f 6b 65 6e 20 62 79 20 74 68 65 20 73 65 63 6f  oken by the seco
3130: 6e 64 20 63 6f 6c 75 6d 6e 2e 0a 3c 2f 70 3e 0a  nd column..</p>.
3140: 0a 3c 70 3e 0a 47 69 76 65 6e 20 74 68 65 20 6e  .<p>.Given the n
3150: 65 77 20 6d 75 6c 74 69 2d 63 6f 6c 75 6d 6e 20  ew multi-column 
3160: 49 64 78 33 20 69 6e 64 65 78 2c 20 69 74 20 69  Idx3 index, it i
3170: 73 20 6e 6f 77 20 70 6f 73 73 69 62 6c 65 20 66  s now possible f
3180: 6f 72 20 53 51 4c 69 74 65 0a 74 6f 20 66 69 6e  or SQLite.to fin
3190: 64 20 74 68 65 20 70 72 69 63 65 20 6f 66 20 43  d the price of C
31a0: 61 6c 69 66 6f 72 6e 69 61 20 6f 72 61 6e 67 65  alifornia orange
31b0: 73 20 75 73 69 6e 67 20 6f 6e 6c 79 20 32 20 62  s using only 2 b
31c0: 69 6e 61 72 79 20 73 65 61 72 63 68 65 73 3a 0a  inary searches:.
31d0: 3c 2f 70 3e 0a 0a 3c 74 63 6c 3e 0a 63 6f 64 65  </p>..<tcl>.code
31e0: 20 7b 53 45 4c 45 43 54 20 70 72 69 63 65 20 46   {SELECT price F
31f0: 52 4f 4d 20 66 72 75 69 74 73 66 6f 72 73 61 6c  ROM fruitsforsal
3200: 65 20 57 48 45 52 45 20 66 72 75 69 74 3d 27 4f  e WHERE fruit='O
3210: 72 61 6e 67 65 27 20 41 4e 44 20 73 74 61 74 65  range' AND state
3220: 3d 27 43 41 27 7d 0a 66 69 67 75 72 65 20 31 31  ='CA'}.figure 11
3230: 20 23 66 69 67 31 31 20 69 64 78 33 6c 75 31 2e   #fig11 idx3lu1.
3240: 67 69 66 20 7b 4c 6f 6f 6b 75 70 20 55 73 69 6e  gif {Lookup Usin
3250: 67 20 41 20 54 77 6f 2d 43 6f 6c 75 6d 6e 20 49  g A Two-Column I
3260: 6e 64 65 78 7d 0a 3c 2f 74 63 6c 3e 0a 0a 3c 70  ndex}.</tcl>..<p
3270: 3e 0a 57 69 74 68 20 74 68 65 20 49 64 78 33 20  >.With the Idx3 
3280: 69 6e 64 65 78 20 6f 6e 20 62 6f 74 68 20 63 6f  index on both co
3290: 6c 75 6d 6e 73 20 74 68 61 74 20 61 72 65 20 63  lumns that are c
32a0: 6f 6e 73 74 72 61 69 6e 65 64 20 62 79 20 74 68  onstrained by th
32b0: 65 20 57 48 45 52 45 20 63 6c 61 75 73 65 2c 0a  e WHERE clause,.
32c0: 53 51 4c 69 74 65 20 63 61 6e 20 64 6f 20 61 20  SQLite can do a 
32d0: 73 69 6e 67 6c 65 20 62 69 6e 61 72 79 20 73 65  single binary se
32e0: 61 72 63 68 20 61 67 61 69 6e 73 74 20 49 64 78  arch against Idx
32f0: 33 20 74 6f 20 66 69 6e 64 20 74 68 65 20 6f 6e  3 to find the on
3300: 65 20 72 6f 77 69 64 0a 66 6f 72 20 43 61 6c 69  e rowid.for Cali
3310: 66 6f 72 6e 69 61 20 6f 72 61 6e 67 65 73 2c 20  fornia oranges, 
3320: 74 68 65 6e 20 64 6f 20 61 20 73 69 6e 67 6c 65  then do a single
3330: 20 62 69 6e 61 72 79 20 73 65 61 72 63 68 20 74   binary search t
3340: 6f 20 66 69 6e 64 20 74 68 65 20 70 72 69 63 65  o find the price
3350: 0a 66 6f 72 20 74 68 61 74 20 69 74 65 6d 20 69  .for that item i
3360: 6e 20 74 68 65 20 6f 72 69 67 69 6e 61 6c 20 74  n the original t
3370: 61 62 6c 65 2e 20 20 54 68 65 72 65 20 61 72 65  able.  There are
3380: 20 6e 6f 20 64 65 61 64 2d 65 6e 64 73 20 61 6e   no dead-ends an
3390: 64 20 6e 6f 0a 77 61 73 74 65 64 20 62 69 6e 61  d no.wasted bina
33a0: 72 79 20 73 65 61 72 63 68 65 73 2e 20 20 54 68  ry searches.  Th
33b0: 69 73 20 69 73 20 61 20 6d 6f 72 65 20 65 66 66  is is a more eff
33c0: 69 63 69 65 6e 74 20 71 75 65 72 79 2e 0a 3c 2f  icient query..</
33d0: 70 3e 0a 0a 3c 70 3e 0a 4e 6f 74 65 20 74 68 61  p>..<p>.Note tha
33e0: 74 20 49 64 78 33 20 63 6f 6e 74 61 69 6e 73 20  t Idx3 contains 
33f0: 61 6c 6c 20 74 68 65 20 73 61 6d 65 20 69 6e 66  all the same inf
3400: 6f 72 6d 61 74 69 6f 6e 20 61 73 20 74 68 65 20  ormation as the 
3410: 6f 72 69 67 69 6e 61 6c 20 0a 3c 61 20 68 72 65  original .<a hre
3420: 66 3d 22 23 66 69 67 33 22 3e 49 64 78 31 3c 2f  f="#fig3">Idx1</
3430: 61 3e 2e 20 20 41 6e 64 20 73 6f 20 69 66 20 77  a>.  And so if w
3440: 65 20 68 61 76 65 20 49 64 78 33 2c 20 77 65 20  e have Idx3, we 
3450: 64 6f 20 6e 6f 74 20 72 65 61 6c 6c 79 20 6e 65  do not really ne
3460: 65 64 20 49 64 78 31 0a 61 6e 79 20 6d 6f 72 65  ed Idx1.any more
3470: 2e 20 20 54 68 65 20 22 70 72 69 63 65 20 6f 66  .  The "price of
3480: 20 70 65 61 63 68 65 73 22 20 71 75 65 72 79 20   peaches" query 
3490: 63 61 6e 20 62 65 20 73 61 74 69 73 66 69 65 64  can be satisfied
34a0: 20 75 73 69 6e 67 20 49 64 78 33 0a 62 79 20 73   using Idx3.by s
34b0: 69 6d 70 6c 79 20 69 67 6e 6f 72 69 6e 67 20 74  imply ignoring t
34c0: 68 65 20 22 73 74 61 74 65 22 20 63 6f 6c 75 6d  he "state" colum
34d0: 6e 20 6f 66 20 49 64 78 33 3a 0a 3c 2f 70 3e 0a  n of Idx3:.</p>.
34e0: 0a 3c 74 63 6c 3e 0a 63 6f 64 65 20 7b 53 45 4c  .<tcl>.code {SEL
34f0: 45 43 54 20 70 72 69 63 65 20 46 52 4f 4d 20 66  ECT price FROM f
3500: 72 75 69 74 73 66 6f 72 73 61 6c 65 20 57 48 45  ruitsforsale WHE
3510: 52 45 20 66 72 75 69 74 3d 27 50 65 61 63 68 27  RE fruit='Peach'
3520: 7d 0a 66 69 67 75 72 65 20 31 32 20 23 66 69 67  }.figure 12 #fig
3530: 31 32 20 69 64 78 33 6c 75 32 2e 67 69 66 20 7b  12 idx3lu2.gif {
3540: 53 69 6e 67 6c 65 2d 43 6f 6c 75 6d 6e 20 4c 6f  Single-Column Lo
3550: 6f 6b 75 70 20 4f 6e 20 41 20 4d 75 6c 74 69 2d  okup On A Multi-
3560: 43 6f 6c 75 6d 6e 20 49 6e 64 65 78 7d 0a 3c 2f  Column Index}.</
3570: 74 63 6c 3e 0a 0a 3c 70 3e 0a 48 65 6e 63 65 2c  tcl>..<p>.Hence,
3580: 20 61 20 67 6f 6f 64 20 72 75 6c 65 20 6f 66 20   a good rule of 
3590: 74 68 75 6d 62 20 69 73 20 74 68 61 74 20 79 6f  thumb is that yo
35a0: 75 72 20 64 61 74 61 62 61 73 65 20 73 63 68 65  ur database sche
35b0: 6d 61 20 73 68 6f 75 6c 64 20 6e 65 76 65 72 0a  ma should never.
35c0: 63 6f 6e 74 61 69 6e 20 74 77 6f 20 69 6e 64 69  contain two indi
35d0: 63 65 73 20 77 68 65 72 65 20 6f 6e 65 20 69 6e  ces where one in
35e0: 64 65 78 20 69 73 20 61 20 70 72 65 66 69 78 20  dex is a prefix 
35f0: 6f 66 20 74 68 65 20 6f 74 68 65 72 2e 20 20 44  of the other.  D
3600: 72 6f 70 20 74 68 65 0a 69 6e 64 65 78 20 77 69  rop the.index wi
3610: 74 68 20 66 65 77 65 72 20 63 6f 6c 75 6d 6e 73  th fewer columns
3620: 2e 20 20 53 51 4c 69 74 65 20 77 69 6c 6c 20 73  .  SQLite will s
3630: 74 69 6c 6c 20 62 65 20 61 62 6c 65 20 74 6f 20  till be able to 
3640: 64 6f 20 65 66 66 69 63 69 65 6e 74 0a 6c 6f 6f  do efficient.loo
3650: 6b 75 70 73 20 77 69 74 68 20 74 68 65 20 6c 6f  kups with the lo
3660: 6e 67 65 72 20 69 6e 64 65 78 2e 0a 3c 2f 70 3e  nger index..</p>
3670: 0a 0a 3c 68 33 3e 31 2e 37 20 43 6f 76 65 72 69  ..<h3>1.7 Coveri
3680: 6e 67 20 49 6e 64 69 63 65 73 3c 2f 68 33 3e 0a  ng Indices</h3>.
3690: 0a 3c 70 3e 0a 54 68 65 20 22 70 72 69 63 65 20  .<p>.The "price 
36a0: 6f 66 20 43 61 6c 69 66 6f 72 6e 69 61 20 6f 72  of California or
36b0: 61 6e 67 65 73 22 20 71 75 65 72 79 20 77 61 73  anges" query was
36c0: 20 6d 61 64 65 20 6d 6f 72 65 20 65 66 66 69 63   made more effic
36d0: 69 65 6e 74 20 74 68 72 6f 75 67 68 0a 74 68 65  ient through.the
36e0: 20 75 73 65 20 6f 66 20 61 20 74 77 6f 2d 63 6f   use of a two-co
36f0: 6c 75 6d 6e 20 69 6e 64 65 78 2e 20 20 42 75 74  lumn index.  But
3700: 20 53 51 4c 69 74 65 20 63 61 6e 20 64 6f 20 65   SQLite can do e
3710: 76 65 6e 20 62 65 74 74 65 72 20 77 69 74 68 20  ven better with 
3720: 61 0a 74 68 72 65 65 2d 63 6f 6c 75 6d 6e 20 69  a.three-column i
3730: 6e 64 65 78 20 74 68 61 74 20 61 6c 73 6f 20 69  ndex that also i
3740: 6e 63 6c 75 64 65 73 20 74 68 65 20 22 70 72 69  ncludes the "pri
3750: 63 65 22 20 63 6f 6c 75 6d 6e 3a 0a 3c 2f 70 3e  ce" column:.</p>
3760: 0a 0a 3c 74 63 6c 3e 0a 63 6f 64 65 20 7b 43 52  ..<tcl>.code {CR
3770: 45 41 54 45 20 49 4e 44 45 58 20 49 64 78 34 20  EATE INDEX Idx4 
3780: 4f 4e 20 46 72 75 69 74 73 46 6f 72 53 61 6c 65  ON FruitsForSale
3790: 28 66 72 75 69 74 2c 20 73 74 61 74 65 2c 20 70  (fruit, state, p
37a0: 72 69 63 65 29 3b 7d 0a 66 69 67 75 72 65 20 31  rice);}.figure 1
37b0: 33 20 23 66 69 67 31 33 20 69 64 78 34 2e 67 69  3 #fig13 idx4.gi
37c0: 66 20 7b 41 20 43 6f 76 65 72 69 6e 67 20 49 6e  f {A Covering In
37d0: 64 65 78 7d 0a 3c 2f 74 63 6c 3e 0a 0a 3c 70 3e  dex}.</tcl>..<p>
37e0: 0a 54 68 69 73 20 6e 65 77 20 69 6e 64 65 78 20  .This new index 
37f0: 63 6f 6e 74 61 69 6e 73 20 61 6c 6c 20 74 68 65  contains all the
3800: 20 63 6f 6c 75 6d 6e 73 20 6f 66 20 74 68 65 20   columns of the 
3810: 6f 72 69 67 69 6e 61 6c 20 46 72 75 69 74 73 46  original FruitsF
3820: 6f 72 53 61 6c 65 20 74 61 62 6c 65 20 74 68 61  orSale table tha
3830: 74 0a 61 72 65 20 75 73 65 64 20 62 79 20 74 68  t.are used by th
3840: 65 20 71 75 65 72 79 20 2d 20 62 6f 74 68 20 74  e query - both t
3850: 68 65 20 73 65 61 72 63 68 20 74 65 72 6d 73 20  he search terms 
3860: 61 6e 64 20 74 68 65 20 6f 75 74 70 75 74 2e 20  and the output. 
3870: 20 57 65 20 63 61 6c 6c 0a 74 68 69 73 20 61 20   We call.this a 
3880: 22 63 6f 76 65 72 69 6e 67 20 69 6e 64 65 78 22  "covering index"
3890: 2e 20 20 42 65 63 61 75 73 65 20 61 6c 6c 20 6f  .  Because all o
38a0: 66 20 74 68 65 20 69 6e 66 6f 72 6d 61 74 69 6f  f the informatio
38b0: 6e 20 6e 65 65 64 65 64 20 69 73 20 69 6e 0a 74  n needed is in.t
38c0: 68 65 20 63 6f 76 65 72 69 6e 67 20 69 6e 64 65  he covering inde
38d0: 78 2c 20 53 51 4c 69 74 65 20 6e 65 76 65 72 20  x, SQLite never 
38e0: 6e 65 65 64 73 20 74 6f 20 63 6f 6e 73 75 6c 74  needs to consult
38f0: 20 74 68 65 20 6f 72 69 67 69 6e 61 6c 20 74 61   the original ta
3900: 62 6c 65 0a 69 6e 20 6f 72 64 65 72 20 74 6f 20  ble.in order to 
3910: 66 69 6e 64 20 74 68 65 20 70 72 69 63 65 2e 0a  find the price..
3920: 3c 2f 70 3e 0a 0a 3c 74 63 6c 3e 0a 63 6f 64 65  </p>..<tcl>.code
3930: 20 7b 53 45 4c 45 43 54 20 70 72 69 63 65 20 46   {SELECT price F
3940: 52 4f 4d 20 66 72 75 69 74 73 66 6f 72 73 61 6c  ROM fruitsforsal
3950: 65 20 57 48 45 52 45 20 66 72 75 69 74 3d 27 4f  e WHERE fruit='O
3960: 72 61 6e 67 65 27 20 41 4e 44 20 73 74 61 74 65  range' AND state
3970: 3d 27 43 41 27 3b 7d 0a 66 69 67 75 72 65 20 31  ='CA';}.figure 1
3980: 34 20 23 66 69 67 31 34 20 69 64 78 34 6c 75 31  4 #fig14 idx4lu1
3990: 2e 67 69 66 20 7b 51 75 65 72 79 20 55 73 69 6e  .gif {Query Usin
39a0: 67 20 41 20 43 6f 76 65 72 69 6e 67 20 49 6e 64  g A Covering Ind
39b0: 65 78 7d 0a 3c 2f 74 63 6c 3e 0a 0a 3c 70 3e 0a  ex}.</tcl>..<p>.
39c0: 48 65 6e 63 65 2c 20 62 79 20 61 64 64 69 6e 67  Hence, by adding
39d0: 20 65 78 74 72 61 20 22 6f 75 74 70 75 74 22 20   extra "output" 
39e0: 63 6f 6c 75 6d 6e 73 20 6f 6e 74 6f 20 74 68 65  columns onto the
39f0: 20 65 6e 64 20 6f 66 20 61 6e 20 69 6e 64 65 78   end of an index
3a00: 2c 20 6f 6e 65 0a 63 61 6e 20 61 76 6f 69 64 20  , one.can avoid 
3a10: 68 61 76 69 6e 67 20 74 6f 20 72 65 66 65 72 65  having to refere
3a20: 6e 63 65 20 74 68 65 20 6f 72 69 67 69 6e 61 6c  nce the original
3a30: 20 74 61 62 6c 65 20 61 6e 64 20 74 68 65 72 65   table and there
3a40: 62 79 0a 63 75 74 20 74 68 65 20 6e 75 6d 62 65  by.cut the numbe
3a50: 72 20 6f 66 20 62 69 6e 61 72 79 20 73 65 61 72  r of binary sear
3a60: 63 68 65 73 20 66 6f 72 20 61 20 71 75 65 72 79  ches for a query
3a70: 20 69 6e 20 68 61 6c 66 2e 20 20 54 68 69 73 20   in half.  This 
3a80: 69 73 20 61 0a 63 6f 6e 73 74 61 6e 74 2d 66 61  is a.constant-fa
3a90: 63 74 6f 72 20 69 6d 70 72 6f 76 65 6d 65 6e 74  ctor improvement
3aa0: 20 69 6e 20 70 65 72 66 6f 72 6d 61 6e 63 65 20   in performance 
3ab0: 28 72 6f 75 67 68 6c 79 20 61 20 64 6f 75 62 6c  (roughly a doubl
3ac0: 69 6e 67 20 6f 66 0a 74 68 65 20 73 70 65 65 64  ing of.the speed
3ad0: 29 2e 20 20 42 75 74 20 6f 6e 20 74 68 65 20 6f  ).  But on the o
3ae0: 74 68 65 72 20 68 61 6e 64 2c 20 69 74 20 69 73  ther hand, it is
3af0: 20 61 6c 73 6f 20 6a 75 73 74 20 61 20 72 65 66   also just a ref
3b00: 69 6e 65 6d 65 6e 74 3b 0a 41 20 74 77 6f 2d 66  inement;.A two-f
3b10: 6f 6c 64 20 70 65 72 66 6f 72 6d 61 6e 63 65 20  old performance 
3b20: 69 6e 63 72 65 61 73 65 20 69 73 20 6e 6f 74 20  increase is not 
3b30: 6e 65 61 72 6c 79 20 61 73 20 64 72 61 6d 61 74  nearly as dramat
3b40: 69 63 20 61 73 20 74 68 65 0a 6f 6e 65 2d 6d 69  ic as the.one-mi
3b50: 6c 6c 69 6f 6e 2d 66 6f 6c 64 20 69 6e 63 72 65  llion-fold incre
3b60: 61 73 65 20 73 65 65 6e 20 77 68 65 6e 20 74 68  ase seen when th
3b70: 65 20 74 61 62 6c 65 20 77 61 73 20 66 69 72 73  e table was firs
3b80: 74 20 69 6e 64 65 78 65 64 2e 0a 41 6e 64 20 66  t indexed..And f
3b90: 6f 72 20 6d 6f 73 74 20 71 75 65 72 69 65 73 2c  or most queries,
3ba0: 20 74 68 65 20 64 69 66 66 65 72 65 6e 63 65 20   the difference 
3bb0: 62 65 74 77 65 65 6e 20 31 20 6d 69 63 72 6f 73  between 1 micros
3bc0: 65 63 6f 6e 64 20 61 6e 64 0a 32 20 6d 69 63 72  econd and.2 micr
3bd0: 6f 73 65 63 6f 6e 64 73 20 69 73 20 75 6e 6c 69  oseconds is unli
3be0: 6b 65 6c 79 20 74 6f 20 62 65 20 6e 6f 74 69 63  kely to be notic
3bf0: 65 64 2e 0a 3c 2f 70 3e 0a 0a 3c 68 33 3e 31 2e  ed..</p>..<h3>1.
3c00: 38 20 4f 52 2d 43 6f 6e 6e 65 63 74 65 64 20 54  8 OR-Connected T
3c10: 65 72 6d 73 20 49 6e 20 54 68 65 20 57 48 45 52  erms In The WHER
3c20: 45 20 43 6c 61 75 73 65 3c 2f 68 33 3e 0a 0a 3c  E Clause</h3>..<
3c30: 70 3e 0a 4d 75 6c 74 69 2d 63 6f 6c 75 6d 6e 20  p>.Multi-column 
3c40: 69 6e 64 69 63 65 73 20 6f 6e 6c 79 20 77 6f 72  indices only wor
3c50: 6b 20 69 66 20 74 68 65 20 63 6f 6e 73 74 72 61  k if the constra
3c60: 69 6e 74 20 74 65 72 6d 73 20 69 6e 20 74 68 65  int terms in the
3c70: 20 57 48 45 52 45 0a 63 6c 61 75 73 65 20 6f 66   WHERE.clause of
3c80: 20 74 68 65 20 71 75 65 72 79 20 61 72 65 20 63   the query are c
3c90: 6f 6e 6e 65 63 74 65 64 20 62 79 20 41 4e 44 2e  onnected by AND.
3ca0: 0a 53 6f 20 49 64 78 33 20 61 6e 64 20 49 64 78  .So Idx3 and Idx
3cb0: 34 20 61 72 65 20 68 65 6c 70 66 75 6c 20 77 68  4 are helpful wh
3cc0: 65 6e 20 74 68 65 20 73 65 61 72 63 68 20 69 73  en the search is
3cd0: 20 66 6f 72 20 69 74 65 6d 73 20 74 68 61 74 0a   for items that.
3ce0: 61 72 65 20 62 6f 74 68 20 4f 72 61 6e 67 65 73  are both Oranges
3cf0: 20 61 6e 64 20 67 72 6f 77 6e 20 69 6e 20 43 61   and grown in Ca
3d00: 6c 69 66 6f 72 6e 69 61 2c 20 62 75 74 20 6e 65  lifornia, but ne
3d10: 69 74 68 65 72 20 69 6e 64 65 78 20 77 6f 75 6c  ither index woul
3d20: 64 0a 62 65 20 74 68 61 74 20 75 73 65 66 75 6c  d.be that useful
3d30: 20 69 66 20 77 65 20 77 61 6e 74 65 64 20 61 6c   if we wanted al
3d40: 6c 20 69 74 65 6d 73 20 74 68 61 74 20 77 65 72  l items that wer
3d50: 65 20 65 69 74 68 65 72 20 6f 72 61 6e 67 65 73  e either oranges
3d60: 0a 3c 69 3e 6f 72 3c 2f 69 3e 20 61 72 65 20 67  .<i>or</i> are g
3d70: 72 6f 77 6e 20 69 6e 20 43 61 6c 69 66 6f 72 6e  rown in Californ
3d80: 69 61 2e 0a 3c 2f 70 3e 0a 0a 3c 74 63 6c 3e 63  ia..</p>..<tcl>c
3d90: 6f 64 65 20 7b 0a 53 45 4c 45 43 54 20 70 72 69  ode {.SELECT pri
3da0: 63 65 20 46 52 4f 4d 20 46 72 75 69 74 73 46 6f  ce FROM FruitsFo
3db0: 72 53 61 6c 65 20 57 48 45 52 45 20 66 72 75 69  rSale WHERE frui
3dc0: 74 3d 27 4f 72 61 6e 67 65 27 20 4f 52 20 73 74  t='Orange' OR st
3dd0: 61 74 65 3d 27 43 41 27 3b 0a 7d 3c 2f 74 63 6c  ate='CA';.}</tcl
3de0: 3e 0a 0a 3c 70 3e 0a 57 68 65 6e 20 63 6f 6e 66  >..<p>.When conf
3df0: 72 6f 6e 74 65 64 20 77 69 74 68 20 4f 52 2d 63  ronted with OR-c
3e00: 6f 6e 6e 65 63 74 65 64 20 74 65 72 6d 73 20 69  onnected terms i
3e10: 6e 20 61 20 57 48 45 52 45 20 63 6c 61 75 73 65  n a WHERE clause
3e20: 2c 20 53 51 4c 69 74 65 20 0a 65 78 61 6d 69 6e  , SQLite .examin
3e30: 65 73 20 65 61 63 68 20 4f 52 20 74 65 72 6d 20  es each OR term 
3e40: 73 65 70 61 72 61 74 65 6c 79 20 61 6e 64 20 74  separately and t
3e50: 72 69 65 73 20 74 6f 20 75 73 65 20 61 6e 20 69  ries to use an i
3e60: 6e 64 65 78 20 74 6f 0a 66 69 6e 64 20 74 68 65  ndex to.find the
3e70: 20 72 6f 77 69 64 73 20 61 73 73 6f 63 69 61 74   rowids associat
3e80: 65 64 20 77 69 74 68 20 65 61 63 68 20 74 65 72  ed with each ter
3e90: 6d 2e 0a 49 74 20 74 68 65 6e 20 74 61 6b 65 73  m..It then takes
3ea0: 20 74 68 65 20 75 6e 69 6f 6e 20 6f 66 20 74 68   the union of th
3eb0: 65 20 72 65 73 75 6c 74 69 6e 67 20 72 6f 77 69  e resulting rowi
3ec0: 64 20 73 65 74 73 20 74 6f 20 66 69 6e 64 0a 74  d sets to find.t
3ed0: 68 65 20 65 6e 64 20 72 65 73 75 6c 74 2e 20 20  he end result.  
3ee0: 54 68 65 20 66 6f 6c 6c 6f 77 69 6e 67 20 66 69  The following fi
3ef0: 67 75 72 65 20 69 6c 6c 75 73 74 72 61 74 65 73  gure illustrates
3f00: 20 74 68 69 73 20 70 72 6f 63 65 73 73 3a 0a 3c   this process:.<
3f10: 2f 70 3e 0a 0a 3c 74 63 6c 3e 66 69 67 75 72 65  /p>..<tcl>figure
3f20: 20 31 35 20 23 66 69 67 31 35 20 6f 72 71 75 65   15 #fig15 orque
3f30: 72 79 2e 67 69 66 20 7b 51 75 65 72 79 20 57 69  ry.gif {Query Wi
3f40: 74 68 20 4f 52 20 43 6f 6e 73 74 72 61 69 6e 74  th OR Constraint
3f50: 73 7d 3c 2f 74 63 6c 3e 0a 0a 3c 70 3e 0a 54 68  s}</tcl>..<p>.Th
3f60: 65 20 64 69 61 67 72 61 6d 20 61 62 6f 76 65 20  e diagram above 
3f70: 69 6d 70 6c 69 65 73 20 74 68 61 74 20 53 51 4c  implies that SQL
3f80: 69 74 65 20 63 6f 6d 70 75 74 65 73 20 61 6c 6c  ite computes all
3f90: 20 6f 66 20 74 68 65 20 72 6f 77 69 64 73 20 66   of the rowids f
3fa0: 69 72 73 74 0a 61 6e 64 20 74 68 65 6e 20 63 6f  irst.and then co
3fb0: 6d 62 69 6e 65 73 20 74 68 65 6d 20 77 69 74 68  mbines them with
3fc0: 20 61 20 75 6e 69 6f 6e 20 6f 70 65 72 61 74 69   a union operati
3fd0: 6f 6e 20 62 65 66 6f 72 65 20 73 74 61 72 74 69  on before starti
3fe0: 6e 67 20 74 6f 20 64 6f 0a 72 6f 77 69 64 20 6c  ng to do.rowid l
3ff0: 6f 6f 6b 75 70 73 20 6f 6e 20 74 68 65 20 6f 72  ookups on the or
4000: 69 67 69 6e 61 6c 20 74 61 62 6c 65 2e 20 20 49  iginal table.  I
4010: 6e 20 72 65 61 6c 69 74 79 2c 20 74 68 65 20 72  n reality, the r
4020: 6f 77 69 64 20 6c 6f 6f 6b 75 70 73 0a 61 72 65  owid lookups.are
4030: 20 69 6e 74 65 72 73 70 65 72 73 65 64 20 77 69   interspersed wi
4040: 74 68 20 72 6f 77 69 64 20 63 6f 6d 70 75 74 61  th rowid computa
4050: 74 69 6f 6e 73 2e 20 20 53 51 4c 69 74 65 20 75  tions.  SQLite u
4060: 73 65 73 20 6f 6e 65 20 69 6e 64 65 78 20 61 74  ses one index at
4070: 0a 61 20 74 69 6d 65 20 74 6f 20 66 69 6e 64 20  .a time to find 
4080: 72 6f 77 69 64 73 20 77 68 69 6c 65 20 72 65 6d  rowids while rem
4090: 65 6d 62 65 72 69 6e 67 20 77 68 69 63 68 20 72  embering which r
40a0: 6f 77 69 64 73 20 69 74 20 68 61 73 20 73 65 65  owids it has see
40b0: 6e 0a 62 65 66 6f 72 65 20 73 6f 20 61 73 20 74  n.before so as t
40c0: 6f 20 61 76 6f 69 64 20 64 75 70 6c 69 63 61 74  o avoid duplicat
40d0: 65 73 2e 20 20 54 68 61 74 20 69 73 20 6a 75 73  es.  That is jus
40e0: 74 20 61 6e 20 69 6d 70 6c 65 6d 65 6e 74 61 74  t an implementat
40f0: 69 6f 6e 0a 64 65 74 61 69 6c 2c 20 74 68 6f 75  ion.detail, thou
4100: 67 68 2e 20 20 54 68 65 20 64 69 61 67 72 61 6d  gh.  The diagram
4110: 2c 20 77 68 69 6c 65 20 6e 6f 74 20 31 30 30 25  , while not 100%
4120: 20 61 63 63 75 72 61 74 65 2c 20 70 72 6f 76 69   accurate, provi
4130: 64 65 73 20 61 20 67 6f 6f 64 0a 6f 76 65 72 76  des a good.overv
4140: 69 65 77 20 6f 66 20 77 68 61 74 20 69 73 20 68  iew of what is h
4150: 61 70 70 65 6e 69 6e 67 2e 0a 3c 2f 70 3e 0a 0a  appening..</p>..
4160: 3c 70 3e 0a 49 6e 20 6f 72 64 65 72 20 66 6f 72  <p>.In order for
4170: 20 74 68 65 20 4f 52 2d 62 79 2d 55 4e 49 4f 4e   the OR-by-UNION
4180: 20 74 65 63 68 6e 69 71 75 65 20 73 68 6f 77 6e   technique shown
4190: 20 61 62 6f 76 65 20 74 6f 20 62 65 20 75 73 65   above to be use
41a0: 66 75 6c 2c 20 74 68 65 72 65 0a 6d 75 73 74 20  ful, there.must 
41b0: 62 65 20 61 6e 20 69 6e 64 65 78 20 61 76 61 69  be an index avai
41c0: 6c 61 62 6c 65 20 74 68 61 74 20 68 65 6c 70 73  lable that helps
41d0: 20 72 65 73 6f 6c 76 65 20 65 76 65 72 79 20 4f   resolve every O
41e0: 52 2d 63 6f 6e 6e 65 63 74 65 64 20 74 65 72 6d  R-connected term
41f0: 0a 69 6e 20 74 68 65 20 57 48 45 52 45 20 63 6c  .in the WHERE cl
4200: 61 75 73 65 2e 20 20 49 66 20 65 76 65 6e 20 61  ause.  If even a
4210: 20 73 69 6e 67 6c 65 20 4f 52 2d 63 6f 6e 6e 65   single OR-conne
4220: 63 74 65 64 20 74 65 72 6d 20 69 73 20 6e 6f 74  cted term is not
4230: 20 69 6e 64 65 78 65 64 2c 0a 74 68 65 6e 20 61   indexed,.then a
4240: 20 66 75 6c 6c 20 74 61 62 6c 65 20 73 63 61 6e   full table scan
4250: 20 77 6f 75 6c 64 20 68 61 76 65 20 74 6f 20 62   would have to b
4260: 65 20 64 6f 6e 65 20 69 6e 20 6f 72 64 65 72 20  e done in order 
4270: 74 6f 20 66 69 6e 64 20 74 68 65 20 72 6f 77 69  to find the rowi
4280: 64 73 0a 67 65 6e 65 72 61 74 65 64 20 62 79 20  ds.generated by 
4290: 74 68 65 20 6f 6e 65 20 74 65 72 6d 2c 20 61 6e  the one term, an
42a0: 64 20 69 66 20 53 51 4c 69 74 65 20 68 61 73 20  d if SQLite has 
42b0: 74 6f 20 64 6f 20 61 20 66 75 6c 6c 20 74 61 62  to do a full tab
42c0: 6c 65 20 73 63 61 6e 2c 20 69 74 0a 6d 69 67 68  le scan, it.migh
42d0: 74 20 61 73 20 77 65 6c 6c 20 64 6f 20 69 74 20  t as well do it 
42e0: 6f 6e 20 74 68 65 20 6f 72 69 67 69 6e 61 6c 20  on the original 
42f0: 74 61 62 6c 65 20 61 6e 64 20 67 65 74 20 61 6c  table and get al
4300: 6c 20 6f 66 20 74 68 65 20 72 65 73 75 6c 74 73  l of the results
4310: 20 69 6e 0a 61 20 73 69 6e 67 6c 65 20 70 61 73   in.a single pas
4320: 73 20 77 69 74 68 6f 75 74 20 68 61 76 69 6e 67  s without having
4330: 20 74 6f 20 6d 65 73 73 20 77 69 74 68 20 75 6e   to mess with un
4340: 69 6f 6e 20 6f 70 65 72 61 74 69 6f 6e 73 20 61  ion operations a
4350: 6e 64 20 66 6f 6c 6c 6f 77 2d 6f 6e 0a 62 69 6e  nd follow-on.bin
4360: 61 72 79 20 73 65 61 72 63 68 65 73 2e 0a 3c 2f  ary searches..</
4370: 70 3e 0a 0a 3c 70 3e 0a 4f 6e 65 20 63 61 6e 20  p>..<p>.One can 
4380: 73 65 65 20 68 6f 77 20 74 68 65 20 4f 52 2d 62  see how the OR-b
4390: 79 2d 55 4e 49 4f 4e 20 74 65 63 68 6e 69 71 75  y-UNION techniqu
43a0: 65 20 63 6f 75 6c 64 20 61 6c 73 6f 20 62 65 20  e could also be 
43b0: 6c 65 76 65 72 61 67 65 64 20 74 6f 0a 75 73 65  leveraged to.use
43c0: 20 6d 75 6c 74 69 70 6c 65 20 69 6e 64 69 63 65   multiple indice
43d0: 73 20 6f 6e 20 71 75 65 72 79 20 77 68 65 72 65  s on query where
43e0: 20 74 68 65 20 57 48 45 52 45 20 63 6c 61 75 73   the WHERE claus
43f0: 65 20 68 61 73 20 74 65 72 6d 73 20 63 6f 6e 6e  e has terms conn
4400: 65 63 74 65 64 0a 62 79 20 41 4e 44 2c 20 62 79  ected.by AND, by
4410: 20 75 73 69 6e 67 20 61 6e 20 69 6e 74 65 72 73   using an inters
4420: 65 63 74 20 6f 70 65 72 61 74 6f 72 20 69 6e 20  ect operator in 
4430: 70 6c 61 63 65 20 6f 66 20 75 6e 69 6f 6e 2e 20  place of union. 
4440: 20 4d 61 6e 79 20 53 51 4c 0a 64 61 74 61 62 61   Many SQL.databa
4450: 73 65 20 65 6e 67 69 6e 65 73 20 77 69 6c 6c 20  se engines will 
4460: 64 6f 20 6a 75 73 74 20 74 68 61 74 2e 20 20 42  do just that.  B
4470: 75 74 20 74 68 65 20 70 65 72 66 6f 72 6d 61 6e  ut the performan
4480: 63 65 20 67 61 69 6e 20 6f 76 65 72 20 75 73 69  ce gain over usi
4490: 6e 67 0a 6a 75 73 74 20 61 20 73 69 6e 67 6c 65  ng.just a single
44a0: 20 69 6e 64 65 78 20 69 73 20 73 6c 69 67 68 74   index is slight
44b0: 20 61 6e 64 20 73 6f 20 53 51 4c 69 74 65 20 64   and so SQLite d
44c0: 6f 65 73 20 6e 6f 74 20 69 6d 70 6c 65 6d 65 6e  oes not implemen
44d0: 74 20 74 68 61 74 20 74 65 63 68 6e 69 71 75 65  t that technique
44e0: 0a 61 74 20 74 68 69 73 20 74 69 6d 65 2e 20 20  .at this time.  
44f0: 48 6f 77 65 76 65 72 2c 20 61 20 66 75 74 75 72  However, a futur
4500: 65 20 76 65 72 73 69 6f 6e 20 53 51 4c 69 74 65  e version SQLite
4510: 20 6d 69 67 68 74 20 62 65 20 65 6e 68 61 6e 63   might be enhanc
4520: 65 64 20 74 6f 20 73 75 70 70 6f 72 74 0a 41 4e  ed to support.AN
4530: 44 2d 62 79 2d 49 4e 54 45 52 53 45 43 54 2e 0a  D-by-INTERSECT..
4540: 3c 2f 70 3e 0a 0a 0a 3c 68 32 3e 32 2e 30 20 53  </p>...<h2>2.0 S
4550: 6f 72 74 69 6e 67 3c 2f 68 32 3e 0a 0a 3c 70 3e  orting</h2>..<p>
4560: 0a 53 51 4c 69 74 65 20 28 6c 69 6b 65 20 61 6c  .SQLite (like al
4570: 6c 20 6f 74 68 65 72 20 53 51 4c 20 64 61 74 61  l other SQL data
4580: 62 61 73 65 20 65 6e 67 69 6e 65 73 29 20 63 61  base engines) ca
4590: 6e 20 61 6c 73 6f 20 75 73 65 20 69 6e 64 69 63  n also use indic
45a0: 65 73 20 74 6f 0a 73 61 74 69 73 66 79 20 74 68  es to.satisfy th
45b0: 65 20 4f 52 44 45 52 20 42 59 20 63 6c 61 75 73  e ORDER BY claus
45c0: 65 73 20 69 6e 20 61 20 71 75 65 72 79 2c 20 69  es in a query, i
45d0: 6e 20 61 64 64 69 74 69 6f 6e 20 74 6f 20 65 78  n addition to ex
45e0: 70 65 64 69 74 69 6e 67 0a 6c 6f 6f 6b 75 70 2e  pediting.lookup.
45f0: 20 20 49 6e 20 6f 74 68 65 72 20 77 6f 72 64 73    In other words
4600: 2c 20 69 6e 64 69 63 65 73 20 63 61 6e 20 62 65  , indices can be
4610: 20 75 73 65 64 20 74 6f 20 73 70 65 65 64 20 75   used to speed u
4620: 70 20 73 6f 72 74 69 6e 67 20 61 73 0a 77 65 6c  p sorting as.wel
4630: 6c 20 61 73 20 73 65 61 72 63 68 69 6e 67 2e 0a  l as searching..
4640: 3c 2f 70 3e 0a 0a 3c 70 3e 0a 57 68 65 6e 20 6e  </p>..<p>.When n
4650: 6f 20 61 70 70 72 6f 70 72 69 61 74 65 20 69 6e  o appropriate in
4660: 64 69 63 65 73 20 61 72 65 20 61 76 61 69 6c 61  dices are availa
4670: 62 6c 65 2c 20 61 20 71 75 65 72 79 20 77 69 74  ble, a query wit
4680: 68 20 61 6e 20 4f 52 44 45 52 20 42 59 0a 63 6c  h an ORDER BY.cl
4690: 61 75 73 65 20 6d 75 73 74 20 62 65 20 73 6f 72  ause must be sor
46a0: 74 65 64 20 61 73 20 61 20 73 65 70 61 72 61 74  ted as a separat
46b0: 65 20 73 74 65 70 2e 20 20 43 6f 6e 73 69 64 65  e step.  Conside
46c0: 72 20 74 68 69 73 20 71 75 65 72 79 3a 0a 3c 2f  r this query:.</
46d0: 70 3e 0a 0a 3c 74 63 6c 3e 63 6f 64 65 20 7b 53  p>..<tcl>code {S
46e0: 45 4c 45 43 54 20 2a 20 46 52 4f 4d 20 66 72 75  ELECT * FROM fru
46f0: 69 74 73 66 6f 72 73 61 6c 65 20 4f 52 44 45 52  itsforsale ORDER
4700: 20 42 59 20 66 72 75 69 74 3b 7d 3c 2f 74 63 6c   BY fruit;}</tcl
4710: 3e 0a 0a 3c 70 3e 0a 53 51 4c 69 74 65 20 70 72  >..<p>.SQLite pr
4720: 6f 63 65 73 73 65 73 20 74 68 69 73 20 62 79 20  ocesses this by 
4730: 67 61 74 68 65 72 20 61 6c 6c 20 74 68 65 20 6f  gather all the o
4740: 75 74 70 75 74 20 6f 66 20 71 75 65 72 79 20 61  utput of query a
4750: 6e 64 20 74 68 65 6e 0a 72 75 6e 6e 69 6e 67 20  nd then.running 
4760: 74 68 61 74 20 6f 75 74 70 75 74 20 74 68 72 6f  that output thro
4770: 75 67 68 20 61 20 73 6f 72 74 65 72 2e 0a 3c 2f  ugh a sorter..</
4780: 70 3e 0a 0a 3c 74 63 6c 3e 66 69 67 75 72 65 20  p>..<tcl>figure 
4790: 31 36 20 23 66 69 67 31 36 20 6f 62 66 72 75 69  16 #fig16 obfrui
47a0: 74 6e 6f 69 64 78 2e 67 69 66 20 7b 53 6f 72 74  tnoidx.gif {Sort
47b0: 69 6e 67 20 57 69 74 68 6f 75 74 20 41 6e 20 49  ing Without An I
47c0: 6e 64 65 78 7d 3c 2f 74 63 6c 3e 0a 0a 3c 70 3e  ndex}</tcl>..<p>
47d0: 0a 49 66 20 74 68 65 20 6e 75 6d 62 65 72 20 6f  .If the number o
47e0: 66 20 6f 75 74 70 75 74 20 72 6f 77 73 20 69 73  f output rows is
47f0: 20 4b 2c 20 74 68 65 6e 20 74 68 65 20 74 69 6d   K, then the tim
4800: 65 20 6e 65 65 64 65 64 20 74 6f 20 73 6f 72 74  e needed to sort
4810: 20 69 73 0a 70 72 6f 70 6f 72 74 69 6f 6e 61 6c   is.proportional
4820: 20 74 6f 20 4b 6c 6f 67 4b 2e 20 20 49 66 20 4b   to KlogK.  If K
4830: 20 69 73 20 73 6d 61 6c 6c 2c 20 74 68 65 20 73   is small, the s
4840: 6f 72 74 69 6e 67 20 74 69 6d 65 20 69 73 20 75  orting time is u
4850: 73 75 61 6c 6c 79 0a 6e 6f 74 20 61 20 66 61 63  sually.not a fac
4860: 74 6f 72 2c 20 62 75 74 20 69 6e 20 61 20 71 75  tor, but in a qu
4870: 65 72 79 20 73 75 63 68 20 61 73 20 74 68 65 20  ery such as the 
4880: 61 62 6f 76 65 20 77 68 65 72 65 20 4b 3d 3d 4e  above where K==N
4890: 2c 20 74 68 65 20 74 69 6d 65 0a 6e 65 65 64 65  , the time.neede
48a0: 64 20 74 6f 20 73 6f 72 74 20 63 61 6e 20 62 65  d to sort can be
48b0: 20 6d 75 63 68 20 67 72 65 61 74 65 72 20 74 68   much greater th
48c0: 61 6e 20 74 68 65 20 74 69 6d 65 20 6e 65 65 64  an the time need
48d0: 65 64 20 74 6f 20 64 6f 20 61 0a 66 75 6c 6c 20  ed to do a.full 
48e0: 74 61 62 6c 65 20 73 63 61 6e 2e 20 20 46 75 72  table scan.  Fur
48f0: 74 68 65 72 6d 6f 72 65 2c 20 74 68 65 20 65 6e  thermore, the en
4900: 74 69 72 65 20 6f 75 74 70 75 74 20 69 73 20 61  tire output is a
4910: 63 63 75 6d 75 6c 61 74 65 64 20 69 6e 0a 74 65  ccumulated in.te
4920: 6d 70 6f 72 61 72 79 20 73 74 6f 72 61 67 65 20  mporary storage 
4930: 28 77 68 69 63 68 20 6d 69 67 68 74 20 62 65 20  (which might be 
4940: 65 69 74 68 65 72 20 69 6e 20 6d 61 69 6e 20 6d  either in main m
4950: 65 6d 6f 72 79 20 6f 72 20 6f 6e 20 64 69 73 6b  emory or on disk
4960: 2c 0a 64 65 70 65 6e 64 69 6e 67 20 6f 6e 20 76  ,.depending on v
4970: 61 72 69 6f 75 73 20 63 6f 6d 70 69 6c 65 2d 74  arious compile-t
4980: 69 6d 65 20 61 6e 64 20 72 75 6e 2d 74 69 6d 65  ime and run-time
4990: 20 73 65 74 74 69 6e 67 73 29 0a 77 68 69 63 68   settings).which
49a0: 20 63 61 6e 20 6d 65 61 6e 20 74 68 61 74 20 61   can mean that a
49b0: 20 6c 6f 74 20 6f 66 20 74 65 6d 70 6f 72 61 72   lot of temporar
49c0: 79 20 73 74 6f 72 61 67 65 20 69 73 20 72 65 71  y storage is req
49d0: 75 69 72 65 64 20 74 6f 20 63 6f 6d 70 6c 65 74  uired to complet
49e0: 65 0a 74 68 65 20 71 75 65 72 79 2e 0a 3c 2f 70  e.the query..</p
49f0: 3e 0a 0a 3c 68 33 3e 32 2e 31 20 53 6f 72 74 69  >..<h3>2.1 Sorti
4a00: 6e 67 20 42 79 20 52 6f 77 69 64 3c 2f 68 33 3e  ng By Rowid</h3>
4a10: 0a 0a 3c 70 3e 0a 42 65 63 61 75 73 65 20 73 6f  ..<p>.Because so
4a20: 72 74 69 6e 67 20 63 61 6e 20 62 65 20 65 78 70  rting can be exp
4a30: 65 6e 73 69 76 65 2c 20 53 51 4c 69 74 65 20 77  ensive, SQLite w
4a40: 6f 72 6b 73 20 68 61 72 64 20 74 6f 20 63 6f 6e  orks hard to con
4a50: 76 65 72 74 20 4f 52 44 45 52 20 42 59 0a 63 6c  vert ORDER BY.cl
4a60: 61 75 73 65 73 20 69 6e 74 6f 20 6e 6f 2d 6f 70  auses into no-op
4a70: 73 2e 20 20 49 66 20 53 51 4c 69 74 65 20 64 65  s.  If SQLite de
4a80: 74 65 72 6d 69 6e 65 73 20 74 68 61 74 20 6f 75  termines that ou
4a90: 74 70 75 74 20 77 69 6c 6c 0a 6e 61 74 75 72 61  tput will.natura
4aa0: 6c 6c 79 20 61 70 70 65 61 72 20 69 6e 20 74 68  lly appear in th
4ab0: 65 20 6f 72 64 65 72 20 73 70 65 63 69 66 69 65  e order specifie
4ac0: 64 2c 20 74 68 65 6e 20 6e 6f 20 73 6f 72 74 69  d, then no sorti
4ad0: 6e 67 20 69 73 20 64 6f 6e 65 2e 0a 53 6f 2c 20  ng is done..So, 
4ae0: 66 6f 72 20 65 78 61 6d 70 6c 65 2c 20 69 66 20  for example, if 
4af0: 79 6f 75 20 72 65 71 75 65 73 74 20 74 68 65 20  you request the 
4b00: 6f 75 74 70 75 74 20 69 6e 20 72 6f 77 69 64 20  output in rowid 
4b10: 6f 72 64 65 72 2c 20 6e 6f 20 73 6f 72 74 69 6e  order, no sortin
4b20: 67 0a 77 69 6c 6c 20 62 65 20 64 6f 6e 65 3a 0a  g.will be done:.
4b30: 3c 2f 70 3e 0a 0a 3c 74 63 6c 3e 0a 63 6f 64 65  </p>..<tcl>.code
4b40: 20 7b 53 45 4c 45 43 54 20 2a 20 46 52 4f 4d 20   {SELECT * FROM 
4b50: 66 72 75 69 74 73 66 6f 72 73 61 6c 65 20 4f 52  fruitsforsale OR
4b60: 44 45 52 20 42 59 20 72 6f 77 69 64 3b 7d 0a 66  DER BY rowid;}.f
4b70: 69 67 75 72 65 20 31 37 20 23 66 69 67 31 37 20  igure 17 #fig17 
4b80: 6f 62 72 6f 77 69 64 2e 67 69 66 20 7b 53 6f 72  obrowid.gif {Sor
4b90: 74 69 6e 67 20 42 79 20 52 6f 77 69 64 7d 0a 3c  ting By Rowid}.<
4ba0: 2f 74 63 6c 3e 0a 0a 3c 70 3e 0a 59 6f 75 20 63  /tcl>..<p>.You c
4bb0: 61 6e 20 61 6c 73 6f 20 72 65 71 75 65 73 74 20  an also request 
4bc0: 61 20 72 65 76 65 72 73 65 2d 6f 72 64 65 72 20  a reverse-order 
4bd0: 73 6f 72 74 20 6c 69 6b 65 20 74 68 69 73 3a 0a  sort like this:.
4be0: 3c 2f 70 3e 0a 0a 3c 74 63 6c 3e 63 6f 64 65 20  </p>..<tcl>code 
4bf0: 7b 53 45 4c 45 43 54 20 2a 20 46 52 4f 4d 20 66  {SELECT * FROM f
4c00: 72 75 69 74 73 66 6f 72 73 61 6c 65 20 4f 52 44  ruitsforsale ORD
4c10: 45 52 20 42 59 20 72 6f 77 69 64 20 44 45 53 43  ER BY rowid DESC
4c20: 3b 7d 3c 2f 74 63 6c 3e 0a 0a 3c 70 3e 0a 53 51  ;}</tcl>..<p>.SQ
4c30: 4c 69 74 65 20 77 69 6c 6c 20 73 74 69 6c 6c 20  Lite will still 
4c40: 6f 6d 69 74 20 74 68 65 20 73 6f 72 74 69 6e 67  omit the sorting
4c50: 20 73 74 65 70 2e 20 20 42 75 74 20 69 6e 20 6f   step.  But in o
4c60: 72 64 65 72 20 66 6f 72 20 6f 75 74 70 75 74 20  rder for output 
4c70: 74 6f 0a 61 70 70 65 61 72 20 69 6e 20 74 68 65  to.appear in the
4c80: 20 63 6f 72 72 65 63 74 20 6f 72 64 65 72 2c 20   correct order, 
4c90: 53 51 4c 69 74 65 20 77 69 6c 6c 20 64 6f 20 74  SQLite will do t
4ca0: 68 65 20 74 61 62 6c 65 20 73 63 61 6e 20 73 74  he table scan st
4cb0: 61 72 74 69 6e 67 20 61 74 0a 74 68 65 20 65 6e  arting at.the en
4cc0: 64 20 61 6e 64 20 77 6f 72 6b 69 6e 67 20 74 6f  d and working to
4cd0: 77 61 72 64 20 74 68 65 20 62 65 67 69 6e 6e 69  ward the beginni
4ce0: 6e 67 2c 20 72 61 74 68 65 72 20 74 68 61 6e 20  ng, rather than 
4cf0: 73 74 61 72 74 69 6e 67 20 61 74 20 74 68 65 0a  starting at the.
4d00: 62 65 67 69 6e 6e 69 6e 67 20 61 6e 64 20 77 6f  beginning and wo
4d10: 72 6b 69 6e 67 20 74 6f 77 61 72 64 20 74 68 65  rking toward the
4d20: 20 65 6e 64 20 61 73 20 73 68 6f 77 6e 20 69 6e   end as shown in
4d30: 20 0a 3c 61 20 68 72 65 66 3d 22 23 66 69 67 31   .<a href="#fig1
4d40: 37 22 3e 66 69 67 75 72 65 20 31 37 3c 2f 61 3e  7">figure 17</a>
4d50: 2e 0a 3c 2f 70 3e 0a 0a 3c 68 33 3e 32 2e 32 20  ..</p>..<h3>2.2 
4d60: 53 6f 72 74 69 6e 67 20 42 79 20 49 6e 64 65 78  Sorting By Index
4d70: 3c 2f 68 33 3e 0a 0a 3c 70 3e 0a 4f 66 20 63 6f  </h3>..<p>.Of co
4d80: 75 72 73 65 2c 20 6f 72 64 65 72 69 6e 67 20 74  urse, ordering t
4d90: 68 65 20 6f 75 74 70 75 74 20 6f 66 20 61 20 71  he output of a q
4da0: 75 65 72 79 20 62 79 20 72 6f 77 69 64 20 69 73  uery by rowid is
4db0: 20 73 65 6c 64 6f 6d 20 75 73 65 66 75 6c 2e 0a   seldom useful..
4dc0: 55 73 75 61 6c 6c 79 20 6f 6e 65 20 77 61 6e 74  Usually one want
4dd0: 73 20 74 6f 20 6f 72 64 65 72 20 74 68 65 20 6f  s to order the o
4de0: 75 74 70 75 74 20 62 79 20 73 6f 6d 65 20 6f 74  utput by some ot
4df0: 68 65 72 20 63 6f 6c 75 6d 6e 2e 0a 3c 2f 70 3e  her column..</p>
4e00: 0a 0a 3c 70 3e 0a 49 66 20 61 6e 20 69 6e 64 65  ..<p>.If an inde
4e10: 78 20 69 73 20 61 76 61 69 6c 61 62 6c 65 20 6f  x is available o
4e20: 6e 20 74 68 65 20 4f 52 44 45 52 20 42 59 20 63  n the ORDER BY c
4e30: 6f 6c 75 6d 6e 2c 20 74 68 61 74 20 69 6e 64 65  olumn, that inde
4e40: 78 20 63 61 6e 20 62 65 20 75 73 65 64 0a 66 6f  x can be used.fo
4e50: 72 20 73 6f 72 74 69 6e 67 2e 20 20 43 6f 6e 73  r sorting.  Cons
4e60: 69 64 65 72 20 74 68 65 20 72 65 71 75 65 73 74  ider the request
4e70: 20 66 6f 72 20 61 6c 6c 20 69 74 65 6d 73 20 73   for all items s
4e80: 6f 72 74 65 64 20 62 79 20 22 66 72 75 69 74 22  orted by "fruit"
4e90: 3a 0a 3c 2f 70 3e 0a 0a 3c 74 63 6c 3e 63 6f 64  :.</p>..<tcl>cod
4ea0: 65 20 7b 53 45 4c 45 43 54 20 2a 20 46 52 4f 4d  e {SELECT * FROM
4eb0: 20 66 72 75 69 74 73 66 6f 72 73 61 6c 65 20 4f   fruitsforsale O
4ec0: 52 44 45 52 20 42 59 20 66 72 75 69 74 3b 7d 3c  RDER BY fruit;}<
4ed0: 2f 74 63 6c 3e 0a 0a 3c 74 63 6c 3e 66 69 67 75  /tcl>..<tcl>figu
4ee0: 72 65 20 31 38 20 23 66 69 67 31 38 20 6f 62 66  re 18 #fig18 obf
4ef0: 72 75 69 74 69 64 78 31 2e 67 69 66 20 7b 53 6f  ruitidx1.gif {So
4f00: 72 74 69 6e 67 20 57 69 74 68 20 41 6e 20 49 6e  rting With An In
4f10: 64 65 78 7d 3c 2f 74 63 6c 3e 0a 0a 3c 70 3e 0a  dex}</tcl>..<p>.
4f20: 54 68 65 20 49 64 78 31 20 69 6e 64 65 78 20 69  The Idx1 index i
4f30: 73 20 73 63 61 6e 6e 65 64 20 66 72 6f 6d 20 74  s scanned from t
4f40: 6f 70 20 74 6f 20 62 6f 74 74 6f 6d 20 28 6f 72  op to bottom (or
4f50: 20 66 72 6f 6d 20 62 6f 74 74 6f 6d 20 74 6f 20   from bottom to 
4f60: 74 6f 70 20 69 66 0a 22 4f 52 44 45 52 20 42 59  top if."ORDER BY
4f70: 20 66 72 75 69 74 20 44 45 53 43 22 20 69 73 20   fruit DESC" is 
4f80: 75 73 65 64 29 20 69 6e 20 6f 72 64 65 72 20 74  used) in order t
4f90: 6f 20 66 69 6e 64 20 74 68 65 20 72 6f 77 69 64  o find the rowid
4fa0: 73 20 66 6f 72 20 65 61 63 68 20 69 74 65 6d 0a  s for each item.
4fb0: 69 6e 20 6f 72 64 65 72 20 62 79 20 66 72 75 69  in order by frui
4fc0: 74 2e 20 20 54 68 65 6e 20 66 6f 72 20 65 61 63  t.  Then for eac
4fd0: 68 20 72 6f 77 69 64 2c 20 61 20 62 69 6e 61 72  h rowid, a binar
4fe0: 79 20 73 65 61 72 63 68 20 69 73 20 64 6f 6e 65  y search is done
4ff0: 20 74 6f 20 6c 6f 6f 6b 75 70 0a 61 6e 64 20 6f   to lookup.and o
5000: 75 74 70 75 74 20 74 68 61 74 20 72 6f 77 2e 20  utput that row. 
5010: 20 49 6e 20 74 68 69 73 20 77 61 79 2c 20 74 68   In this way, th
5020: 65 20 6f 75 74 70 75 74 20 61 70 70 65 61 72 73  e output appears
5030: 20 69 6e 20 74 68 65 20 72 65 71 75 65 73 74 65   in the requeste
5040: 64 20 6f 72 64 65 72 0a 77 69 74 68 20 74 68 65  d order.with the
5050: 20 6e 65 65 64 20 74 6f 20 67 61 74 68 65 72 20   need to gather 
5060: 74 68 65 6e 20 65 6e 74 69 72 65 20 6f 75 74 70  then entire outp
5070: 75 74 20 61 6e 64 20 73 6f 72 74 20 69 74 20 75  ut and sort it u
5080: 73 69 6e 67 20 61 20 73 65 70 61 72 61 74 65 20  sing a separate 
5090: 73 74 65 70 2e 0a 3c 2f 70 3e 0a 0a 3c 70 3e 0a  step..</p>..<p>.
50a0: 42 75 74 20 64 6f 65 73 20 74 68 69 73 20 72 65  But does this re
50b0: 61 6c 6c 79 20 73 61 76 65 20 74 69 6d 65 3f 20  ally save time? 
50c0: 20 54 68 65 20 6e 75 6d 62 65 72 20 6f 66 20 73   The number of s
50d0: 74 65 70 73 20 69 6e 20 74 68 65 20 0a 3c 61 20  teps in the .<a 
50e0: 68 72 65 66 3d 22 23 66 69 67 31 36 22 3e 6f 72  href="#fig16">or
50f0: 69 67 69 6e 61 6c 20 69 6e 64 65 78 6c 65 73 73  iginal indexless
5100: 20 73 6f 72 74 3c 2f 61 3e 20 69 73 20 70 72 6f   sort</a> is pro
5110: 70 6f 72 74 69 6f 6e 61 6c 20 74 6f 20 4e 6c 6f  portional to Nlo
5120: 67 4e 20 73 69 6e 63 65 0a 74 68 61 74 20 69 73  gN since.that is
5130: 20 68 6f 77 20 6d 75 63 68 20 74 69 6d 65 20 69   how much time i
5140: 74 20 74 61 6b 65 73 20 74 6f 20 73 6f 72 74 20  t takes to sort 
5150: 4e 20 72 6f 77 73 2e 20 20 42 75 74 20 77 68 65  N rows.  But whe
5160: 6e 20 77 65 20 75 73 65 20 49 64 78 31 20 61 73  n we use Idx1 as
5170: 0a 73 68 6f 77 6e 20 68 65 72 65 2c 20 77 65 20  .shown here, we 
5180: 68 61 76 65 20 74 6f 20 64 6f 20 4e 20 72 6f 77  have to do N row
5190: 69 64 20 6c 6f 6f 6b 75 70 73 20 77 68 69 63 68  id lookups which
51a0: 20 74 61 6b 65 20 6c 6f 67 4e 20 74 69 6d 65 20   take logN time 
51b0: 65 61 63 68 2c 20 73 6f 0a 74 68 65 20 74 6f 74  each, so.the tot
51c0: 61 6c 20 74 69 6d 65 20 6f 66 20 4e 6c 6f 67 4e  al time of NlogN
51d0: 20 69 73 20 74 68 65 20 73 61 6d 65 21 0a 3c 2f   is the same!.</
51e0: 70 3e 0a 0a 3c 70 3e 0a 53 51 4c 69 74 65 20 75  p>..<p>.SQLite u
51f0: 73 65 73 20 61 20 63 6f 73 74 2d 62 61 73 65 64  ses a cost-based
5200: 20 71 75 65 72 79 20 70 6c 61 6e 6e 65 72 2e 20   query planner. 
5210: 20 57 68 65 6e 20 74 68 65 72 65 20 61 72 65 20   When there are 
5220: 74 77 6f 20 6f 72 20 6d 6f 72 65 20 77 61 79 73  two or more ways
5230: 0a 6f 66 20 73 6f 6c 76 69 6e 67 20 74 68 65 20  .of solving the 
5240: 73 61 6d 65 20 71 75 65 72 79 2c 20 53 51 4c 69  same query, SQLi
5250: 74 65 20 74 72 69 65 73 20 74 6f 20 65 73 74 69  te tries to esti
5260: 6d 61 74 65 20 74 68 65 20 74 6f 74 61 6c 20 61  mate the total a
5270: 6d 6f 75 6e 74 20 6f 66 0a 74 69 6d 65 20 6e 65  mount of.time ne
5280: 65 64 65 64 20 74 6f 20 72 75 6e 20 74 68 65 20  eded to run the 
5290: 71 75 65 72 79 20 75 73 69 6e 67 20 65 61 63 68  query using each
52a0: 20 70 6c 61 6e 2c 20 61 6e 64 20 74 68 65 6e 20   plan, and then 
52b0: 75 73 65 73 20 74 68 65 20 70 6c 61 6e 20 77 69  uses the plan wi
52c0: 74 68 0a 74 68 65 20 6c 6f 77 65 73 74 20 65 73  th.the lowest es
52d0: 74 69 6d 61 74 65 64 20 63 6f 73 74 2e 20 20 41  timated cost.  A
52e0: 20 63 6f 73 74 20 69 73 20 63 6f 6d 70 75 74 65   cost is compute
52f0: 64 20 6d 6f 73 74 6c 79 20 66 72 6f 6d 20 74 68  d mostly from th
5300: 65 20 65 73 74 69 6d 61 74 65 64 0a 74 69 6d 65  e estimated.time
5310: 2c 20 61 6e 64 20 73 6f 20 74 68 69 73 20 63 61  , and so this ca
5320: 73 65 20 63 6f 75 6c 64 20 67 6f 20 65 69 74 68  se could go eith
5330: 65 72 20 77 61 79 20 64 65 70 65 6e 64 69 6e 67  er way depending
5340: 20 6f 6e 20 74 68 65 20 74 61 62 6c 65 20 73 69   on the table si
5350: 7a 65 20 61 6e 64 0a 77 68 61 74 20 57 48 45 52  ze and.what WHER
5360: 45 20 63 6c 61 75 73 65 20 63 6f 6e 73 74 72 61  E clause constra
5370: 69 6e 74 73 20 77 65 72 65 20 61 76 61 69 6c 61  ints were availa
5380: 62 6c 65 2c 20 61 6e 64 20 73 6f 20 66 6f 72 74  ble, and so fort
5390: 68 2e 20 20 42 75 74 20 67 65 6e 65 72 61 6c 6c  h.  But generall
53a0: 79 0a 73 70 65 61 6b 69 6e 67 2c 20 74 68 65 20  y.speaking, the 
53b0: 69 6e 64 65 78 65 64 20 73 6f 72 74 20 77 6f 75  indexed sort wou
53c0: 6c 64 20 70 72 6f 62 61 62 6c 79 20 62 65 20 63  ld probably be c
53d0: 68 6f 73 65 6e 2c 20 69 66 20 66 6f 72 20 6e 6f  hosen, if for no
53e0: 20 6f 74 68 65 72 0a 72 65 61 73 6f 6e 2c 20 62   other.reason, b
53f0: 65 63 61 75 73 65 20 69 74 20 64 6f 65 73 20 6e  ecause it does n
5400: 6f 74 20 6e 65 65 64 20 74 6f 20 61 63 63 75 6d  ot need to accum
5410: 75 6c 61 74 65 20 74 68 65 20 65 6e 74 69 72 65  ulate the entire
5420: 20 72 65 73 75 6c 74 20 73 65 74 20 69 6e 0a 74   result set in.t
5430: 65 6d 70 6f 72 61 72 79 20 62 65 66 6f 72 65 20  emporary before 
5440: 73 6f 72 74 69 6e 67 20 61 6e 64 20 74 68 75 73  sorting and thus
5450: 20 75 73 65 73 20 6d 75 63 68 20 6c 65 73 73 20   uses much less 
5460: 74 65 6d 70 6f 72 61 72 79 20 73 74 6f 72 61 67  temporary storag
5470: 65 2e 0a 3c 2f 70 3e 0a 0a 3c 68 33 3e 32 2e 33  e..</p>..<h3>2.3
5480: 20 53 6f 72 74 69 6e 67 20 42 79 20 43 6f 76 65   Sorting By Cove
5490: 72 69 6e 67 20 49 6e 64 65 78 3c 2f 68 33 3e 0a  ring Index</h3>.
54a0: 0a 3c 70 3e 0a 49 66 20 61 20 63 6f 76 65 72 69  .<p>.If a coveri
54b0: 6e 67 20 69 6e 64 65 78 20 63 61 6e 20 62 65 20  ng index can be 
54c0: 75 73 65 64 20 66 6f 72 20 61 20 71 75 65 72 79  used for a query
54d0: 2c 20 74 68 65 6e 20 74 68 65 20 6d 75 6c 74 69  , then the multi
54e0: 70 6c 65 20 72 6f 77 69 64 20 6c 6f 6f 6b 73 0a  ple rowid looks.
54f0: 63 61 6e 20 62 65 20 61 76 6f 69 64 65 64 20 61  can be avoided a
5500: 6e 64 20 74 68 65 20 63 6f 73 74 20 6f 66 20 74  nd the cost of t
5510: 68 65 20 71 75 65 72 79 20 64 72 6f 70 73 20 64  he query drops d
5520: 72 61 6d 61 74 69 63 61 6c 6c 79 2e 0a 3c 2f 70  ramatically..</p
5530: 3e 0a 0a 3c 74 63 6c 3e 0a 66 69 67 75 72 65 20  >..<tcl>.figure 
5540: 31 39 20 23 66 69 67 31 39 20 6f 62 66 72 75 69  19 #fig19 obfrui
5550: 74 69 64 78 34 2e 67 69 66 20 7b 53 6f 72 74 69  tidx4.gif {Sorti
5560: 6e 67 20 57 69 74 68 20 41 20 43 6f 76 65 72 69  ng With A Coveri
5570: 6e 67 20 49 6e 64 65 78 7d 0a 3c 2f 74 63 6c 3e  ng Index}.</tcl>
5580: 0a 0a 3c 70 3e 0a 57 69 74 68 20 61 20 63 6f 76  ..<p>.With a cov
5590: 65 72 69 6e 67 20 69 6e 64 65 78 2c 20 53 51 4c  ering index, SQL
55a0: 69 74 65 20 63 61 6e 20 73 69 6d 70 6c 79 20 77  ite can simply w
55b0: 61 6c 6b 20 74 68 65 20 69 6e 64 65 78 20 66 72  alk the index fr
55c0: 6f 6d 20 6f 6e 65 20 65 6e 64 20 74 6f 20 74 68  om one end to th
55d0: 65 0a 6f 74 68 65 72 20 61 6e 64 20 64 65 6c 69  e.other and deli
55e0: 76 65 72 20 74 68 65 20 6f 75 74 70 75 74 20 69  ver the output i
55f0: 6e 20 74 69 6d 65 20 70 72 6f 70 6f 72 74 69 6f  n time proportio
5600: 6e 61 6c 20 74 6f 20 4e 20 61 6e 64 20 77 69 74  nal to N and wit
5610: 68 6f 75 74 20 68 61 76 69 6e 67 0a 61 6c 6c 6f  hout having.allo
5620: 63 61 74 65 20 61 20 6c 61 72 67 65 20 62 75 66  cate a large buf
5630: 66 65 72 20 74 6f 20 68 6f 6c 64 20 74 68 65 20  fer to hold the 
5640: 72 65 73 75 6c 74 20 73 65 74 2e 0a 3c 2f 70 3e  result set..</p>
5650: 0a 0a 3c 68 32 3e 54 6f 20 42 65 20 43 6f 6e 74  ..<h2>To Be Cont
5660: 69 6e 75 65 64 2e 2e 2e 3c 2f 68 32 3e 0a 0a 3c  inued...</h2>..<
5670: 70 3e 41 64 64 69 74 69 6f 6e 61 6c 20 74 6f 70  p>Additional top
5680: 69 63 73 20 74 6f 20 64 69 73 63 75 73 73 20 69  ics to discuss i
5690: 6e 63 6c 75 64 65 3a 3c 2f 62 3e 3c 2f 70 3e 0a  nclude:</b></p>.
56a0: 0a 3c 70 3e 3c 75 6c 3e 0a 3c 6c 69 3e 53 65 61  .<p><ul>.<li>Sea
56b0: 72 63 68 20 61 6e 64 20 73 6f 72 74 69 6e 67 20  rch and sorting 
56c0: 61 74 20 74 68 65 20 73 61 6d 65 20 74 69 6d 65  at the same time
56d0: 0a 3c 6c 69 3e 48 6f 77 20 74 6f 20 63 6f 6e 73  .<li>How to cons
56e0: 74 72 75 63 74 20 61 20 67 6f 6f 64 20 69 6e 64  truct a good ind
56f0: 65 78 0a 3c 6c 69 3e 4a 6f 69 6e 73 20 61 6e 64  ex.<li>Joins and
5700: 20 6a 6f 69 6e 2d 6f 72 64 65 72 0a 3c 6c 69 3e   join-order.<li>
5710: 41 75 74 6f 6d 61 74 69 63 20 74 72 61 6e 73 69  Automatic transi
5720: 65 6e 74 20 69 6e 64 69 63 65 73 0a 3c 6c 69 3e  ent indices.<li>
5730: 48 6f 77 20 74 6f 20 64 65 74 65 72 6d 69 6e 65  How to determine
5740: 20 77 68 61 74 20 71 75 65 72 79 20 70 6c 61 6e   what query plan
5750: 20 53 51 4c 69 74 65 20 69 73 20 75 73 69 6e 67   SQLite is using
5760: 0a 3c 6c 69 3e 41 75 74 6f 6d 61 74 69 63 20 64  .<li>Automatic d
5770: 65 74 65 63 74 69 6f 6e 20 6f 66 20 69 6e 65 66  etection of inef
5780: 66 69 63 69 65 6e 74 20 71 75 65 72 79 20 70 6c  ficient query pl
5790: 61 6e 73 0a 3c 6c 69 3e 54 65 63 68 6e 69 71 75  ans.<li>Techniqu
57a0: 65 73 20 66 6f 72 20 69 6e 66 6c 75 63 69 6e 67  es for influcing
57b0: 20 77 68 61 74 20 71 75 65 72 79 20 70 6c 61 6e   what query plan
57c0: 20 53 51 4c 69 74 65 20 63 68 6f 6f 73 65 73 0a   SQLite chooses.
57d0: 3c 2f 75 6c 3e 0a 3c 2f 70 3e 0a                 </ul>.</p>.