Documentation Source Text

Hex Artifact Content
Login

Artifact 0aa8bc0abb95e38a430b001cd94f7b004f1c936e:


0000: 3c 74 69 74 6c 65 3e 51 75 65 72 79 20 50 6c 61  <title>Query Pla
0010: 6e 6e 69 6e 67 3c 2f 74 69 74 6c 65 3e 0a 3c 74  nning</title>.<t
0020: 63 6c 3e 0a 68 64 5f 6b 65 79 77 6f 72 64 73 20  cl>.hd_keywords 
0030: 7b 69 6e 64 65 78 69 6e 67 7d 20 7b 69 6e 64 65  {indexing} {inde
0040: 78 69 6e 67 20 74 75 74 6f 72 69 61 6c 7d 0a 70  xing tutorial}.p
0050: 72 6f 63 20 66 69 67 75 72 65 20 7b 66 69 67 6e  roc figure {fign
0060: 75 6d 20 74 61 67 20 69 6d 67 20 74 69 74 6c 65  um tag img title
0070: 7d 20 7b 0a 20 20 68 64 5f 70 75 74 73 20 22 3c  } {.  hd_puts "<
0080: 70 3e 3c 63 65 6e 74 65 72 3e 5c 6e 22 0a 20 20  p><center>\n".  
0090: 68 64 5f 70 75 74 73 20 22 3c 69 6d 67 20 73 72  hd_puts "<img sr
00a0: 63 3d 5c 22 69 6d 61 67 65 73 2f 71 70 2f 24 69  c=\"images/qp/$i
00b0: 6d 67 5c 22 20 61 6c 74 3d 5c 22 66 69 67 75 72  mg\" alt=\"figur
00c0: 65 20 24 66 69 67 6e 75 6d 5c 22 3e 3c 62 72 3e  e $fignum\"><br>
00d0: 5c 6e 22 0a 20 20 68 64 5f 70 75 74 73 20 22 46  \n".  hd_puts "F
00e0: 69 67 75 72 65 20 24 66 69 67 6e 75 6d 3a 20 24  igure $fignum: $
00f0: 74 69 74 6c 65 5c 6e 22 0a 20 20 68 64 5f 70 75  title\n".  hd_pu
0100: 74 73 20 22 3c 2f 63 65 6e 74 65 72 3e 3c 2f 70  ts "</center></p
0110: 3e 5c 6e 22 0a 7d 0a 70 72 6f 63 20 63 6f 64 65  >\n".}.proc code
0120: 20 7b 74 78 74 7d 20 7b 0a 20 20 68 64 5f 70 75   {txt} {.  hd_pu
0130: 74 73 20 22 3c 63 65 6e 74 65 72 3e 3c 74 61 62  ts "<center><tab
0140: 6c 65 3e 3c 74 72 3e 3c 74 64 3e 3c 70 72 65 3e  le><tr><td><pre>
0150: 5c 6e 22 0a 20 20 72 65 67 73 75 62 20 7b 5e 5b  \n".  regsub {^[
0160: 20 5c 6e 5d 2a 5c 6e 7d 20 24 74 78 74 20 7b 7d   \n]*\n} $txt {}
0170: 20 74 78 74 0a 20 20 68 64 5f 70 75 74 73 20 5b   txt.  hd_puts [
0180: 73 74 72 69 6e 67 20 74 72 69 6d 72 69 67 68 74  string trimright
0190: 20 24 74 78 74 5d 5c 6e 0a 20 20 68 64 5f 70 75   $txt]\n.  hd_pu
01a0: 74 73 20 22 3c 2f 70 72 65 3e 3c 2f 74 61 62 6c  ts "</pre></tabl
01b0: 65 3e 3c 2f 63 65 6e 74 65 72 3e 5c 6e 22 0a 7d  e></center>\n".}
01c0: 0a 3c 2f 74 63 6c 3e 0a 3c 68 31 20 61 6c 69 67  .</tcl>.<h1 alig
01d0: 6e 3d 22 63 65 6e 74 65 72 22 3e 51 75 65 72 79  n="center">Query
01e0: 20 50 6c 61 6e 6e 69 6e 67 3c 2f 68 31 3e 0a 0a   Planning</h1>..
01f0: 3c 70 3e 0a 54 68 65 20 62 65 73 74 20 66 65 61  <p>.The best fea
0200: 74 75 72 65 20 6f 66 20 53 51 4c 20 28 69 6e 20  ture of SQL (in 
0210: 3c 75 3e 61 6c 6c 3c 2f 75 3e 20 69 74 73 20 69  <u>all</u> its i
0220: 6d 70 6c 65 6d 65 6e 74 61 74 69 6f 6e 73 2c 20  mplementations, 
0230: 6e 6f 74 20 6a 75 73 74 20 53 51 4c 69 74 65 29  not just SQLite)
0240: 0a 69 73 20 74 68 61 74 20 69 74 20 69 73 20 61  .is that it is a
0250: 20 3c 69 3e 64 65 63 6c 61 72 61 74 69 76 65 3c   <i>declarative<
0260: 2f 69 3e 20 6c 61 6e 67 75 61 67 65 2c 20 6e 6f  /i> language, no
0270: 74 20 61 20 3c 69 3e 70 72 6f 63 65 64 75 72 61  t a <i>procedura
0280: 6c 3c 2f 69 3e 0a 6c 61 6e 67 75 61 67 65 2e 20  l</i>.language. 
0290: 20 57 68 65 6e 20 70 72 6f 67 72 61 6d 6d 69 6e   When programmin
02a0: 67 20 69 6e 20 53 51 4c 20 79 6f 75 20 74 65 6c  g in SQL you tel
02b0: 6c 20 74 68 65 20 73 79 73 74 65 6d 20 3c 69 3e  l the system <i>
02c0: 77 68 61 74 3c 2f 69 3e 20 79 6f 75 0a 77 61 6e  what</i> you.wan
02d0: 74 20 74 6f 20 63 6f 6d 70 75 74 65 2c 20 6e 6f  t to compute, no
02e0: 74 20 3c 69 3e 68 6f 77 3c 2f 69 3e 20 74 6f 20  t <i>how</i> to 
02f0: 63 6f 6d 70 75 74 65 20 69 74 2e 20 20 54 68 65  compute it.  The
0300: 20 74 61 73 6b 20 6f 66 20 66 69 67 75 72 69 6e   task of figurin
0310: 67 20 6f 75 74 0a 74 68 65 20 3c 69 3e 68 6f 77  g out.the <i>how
0320: 3c 2f 69 3e 20 69 73 20 64 65 6c 65 67 61 74 65  </i> is delegate
0330: 64 20 74 6f 20 74 68 65 20 3c 69 3e 71 75 65 72  d to the <i>quer
0340: 79 20 70 6c 61 6e 6e 65 72 3c 2f 69 3e 20 73 75  y planner</i> su
0350: 62 73 79 73 74 65 6d 20 77 69 74 68 69 6e 20 0a  bsystem within .
0360: 74 68 65 20 53 51 4c 20 64 61 74 61 62 61 73 65  the SQL database
0370: 20 65 6e 67 69 6e 65 2e 0a 52 65 6c 69 65 76 69   engine..Relievi
0380: 6e 67 20 74 68 65 20 70 72 6f 67 72 61 6d 6d 65  ng the programme
0390: 72 20 66 72 6f 6d 20 74 68 65 20 63 68 6f 72 65  r from the chore
03a0: 20 6f 66 20 64 65 73 69 67 6e 69 6e 67 20 73 70   of designing sp
03b0: 65 63 69 66 69 63 0a 71 75 65 72 79 20 61 6c 67  ecific.query alg
03c0: 6f 72 69 74 68 6d 73 20 72 65 64 75 63 65 73 20  orithms reduces 
03d0: 74 68 65 20 77 6f 72 6b 6c 6f 61 64 20 6f 6e 20  the workload on 
03e0: 74 68 65 20 70 72 6f 67 72 61 6d 6d 65 72 20 61  the programmer a
03f0: 6e 64 20 0a 72 65 64 75 63 65 73 20 74 68 65 20  nd .reduces the 
0400: 6e 75 6d 62 65 72 20 6f 66 20 6f 70 70 6f 72 74  number of opport
0410: 75 6e 69 74 69 65 73 20 66 6f 72 20 74 68 65 0a  unities for the.
0420: 70 72 6f 67 72 61 6d 6d 65 72 20 74 6f 20 6d 61  programmer to ma
0430: 6b 65 20 6d 69 73 74 61 6b 65 73 2e 0a 3c 2f 70  ke mistakes..</p
0440: 3e 0a 0a 3c 70 3e 0a 4d 6f 73 74 20 6f 66 20 74  >..<p>.Most of t
0450: 68 65 20 74 69 6d 65 2c 20 74 68 65 20 71 75 65  he time, the que
0460: 72 79 20 70 6c 61 6e 6e 65 72 20 69 6e 20 53 51  ry planner in SQ
0470: 4c 69 74 65 20 64 6f 65 73 20 61 20 67 6f 6f 64  Lite does a good
0480: 20 6a 6f 62 20 6f 6e 20 69 74 73 0a 6f 77 6e 20   job on its.own 
0490: 61 6e 64 20 77 69 74 68 6f 75 74 20 6f 75 74 73  and without outs
04a0: 69 64 65 20 68 65 6c 70 2e 0a 48 6f 77 65 76 65  ide help..Howeve
04b0: 72 2c 20 74 68 65 20 71 75 65 72 79 20 70 6c 61  r, the query pla
04c0: 6e 6e 65 72 20 6e 65 65 64 73 20 69 6e 64 69 63  nner needs indic
04d0: 65 73 20 74 6f 0a 77 6f 72 6b 20 77 69 74 68 20  es to.work with 
04e0: 61 6e 64 20 69 74 20 75 73 75 61 6c 6c 79 20 66  and it usually f
04f0: 61 6c 6c 73 20 74 6f 20 74 68 65 20 70 72 6f 67  alls to the prog
0500: 72 61 6d 6d 65 72 20 74 6f 20 61 64 64 20 69 6e  rammer to add in
0510: 64 69 63 65 73 20 74 6f 20 74 68 65 0a 73 63 68  dices to the.sch
0520: 65 6d 61 20 74 68 61 74 20 61 72 65 20 73 75 66  ema that are suf
0530: 66 69 63 69 65 6e 74 20 66 6f 72 20 74 68 65 20  ficient for the 
0540: 71 75 65 72 79 20 70 6c 61 6e 6e 65 72 20 74 6f  query planner to
0550: 20 61 63 63 6f 6d 70 6c 69 73 68 20 69 74 73 20   accomplish its 
0560: 74 61 73 6b 2e 0a 3c 2f 70 3e 0a 0a 3c 70 3e 0a  task..</p>..<p>.
0570: 54 68 69 73 20 64 6f 63 75 6d 65 6e 74 20 69 73  This document is
0580: 20 69 6e 74 65 6e 64 65 64 20 74 6f 20 70 72 6f   intended to pro
0590: 76 69 64 65 20 70 72 6f 67 72 61 6d 6d 65 72 73  vide programmers
05a0: 20 77 68 6f 20 61 72 65 20 6e 65 77 20 74 6f 20   who are new to 
05b0: 53 51 4c 0a 77 69 74 68 20 62 61 63 6b 67 72 6f  SQL.with backgro
05c0: 75 6e 64 20 69 6e 66 6f 72 6d 61 74 69 6f 6e 20  und information 
05d0: 74 6f 20 68 65 6c 70 20 74 68 65 6d 20 75 6e 64  to help them und
05e0: 65 72 73 74 61 6e 64 0a 77 68 61 74 20 69 73 20  erstand.what is 
05f0: 67 6f 69 6e 67 20 6f 6e 20 62 65 68 69 6e 64 20  going on behind 
0600: 74 68 65 20 73 63 65 6e 65 73 20 77 69 74 68 20  the scenes with 
0610: 53 51 4c 69 74 65 2c 20 77 68 69 63 68 20 69 6e  SQLite, which in
0620: 20 74 75 72 6e 20 73 68 6f 75 6c 64 20 6d 61 6b   turn should mak
0630: 65 0a 69 74 20 65 61 73 69 65 72 20 66 6f 72 20  e.it easier for 
0640: 70 72 6f 67 72 61 6d 6d 65 72 73 20 74 6f 20 63  programmers to c
0650: 72 65 61 74 65 20 74 68 65 20 69 6e 64 69 63 65  reate the indice
0660: 73 20 74 68 61 74 20 77 69 6c 6c 20 68 65 6c 70  s that will help
0670: 20 74 68 65 20 53 51 4c 69 74 65 0a 71 75 65 72   the SQLite.quer
0680: 79 20 70 6c 61 6e 6e 65 72 20 74 6f 20 70 69 63  y planner to pic
0690: 6b 20 74 68 65 20 62 65 73 74 20 70 6c 61 6e 73  k the best plans
06a0: 2e 0a 3c 2f 70 3e 0a 0a 3c 74 63 6c 3e 68 64 5f  ..</p>..<tcl>hd_
06b0: 66 72 61 67 6d 65 6e 74 20 73 65 61 72 63 68 69  fragment searchi
06c0: 6e 67 20 73 74 72 61 74 65 67 69 65 73 3c 2f 74  ng strategies</t
06d0: 63 6c 3e 0a 3c 68 32 3e 31 2e 30 20 53 65 61 72  cl>.<h2>1.0 Sear
06e0: 63 68 69 6e 67 3c 2f 68 32 3e 0a 0a 3c 68 33 3e  ching</h2>..<h3>
06f0: 31 2e 31 20 54 61 62 6c 65 73 20 57 69 74 68 6f  1.1 Tables Witho
0700: 75 74 20 49 6e 64 69 63 65 73 3c 2f 68 33 3e 0a  ut Indices</h3>.
0710: 0a 3c 70 3e 0a 4d 6f 73 74 20 74 61 62 6c 65 73  .<p>.Most tables
0720: 20 69 6e 20 53 51 4c 69 74 65 20 63 6f 6e 73 69   in SQLite consi
0730: 73 74 20 6f 66 20 7a 65 72 6f 20 6f 72 20 6d 6f  st of zero or mo
0740: 72 65 20 72 6f 77 73 20 77 69 74 68 20 61 20 75  re rows with a u
0750: 6e 69 71 75 65 20 69 6e 74 65 67 65 72 0a 6b 65  nique integer.ke
0760: 79 20 28 74 68 65 20 5b 72 6f 77 69 64 5d 20 6f  y (the [rowid] o
0770: 72 20 5b 49 4e 54 45 47 45 52 20 50 52 49 4d 41  r [INTEGER PRIMA
0780: 52 59 20 4b 45 59 5d 29 20 66 6f 6c 6c 6f 77 65  RY KEY]) followe
0790: 64 20 62 79 20 63 6f 6e 74 65 6e 74 2e 20 20 0a  d by content.  .
07a0: 28 54 68 65 20 65 78 63 65 70 74 69 6f 6e 20 69  (The exception i
07b0: 73 20 5b 57 49 54 48 4f 55 54 20 52 4f 57 49 44  s [WITHOUT ROWID
07c0: 5d 20 74 61 62 6c 65 73 2e 29 0a 54 68 65 20 72  ] tables.).The r
07d0: 6f 77 73 0a 61 72 65 20 6c 6f 67 69 63 61 6c 6c  ows.are logicall
07e0: 79 20 73 74 6f 72 65 64 20 69 6e 20 6f 72 64 65  y stored in orde
07f0: 72 20 6f 66 20 69 6e 63 72 65 61 73 69 6e 67 20  r of increasing 
0800: 72 6f 77 69 64 2e 20 20 41 73 20 61 6e 20 65 78  rowid.  As an ex
0810: 61 6d 70 6c 65 2c 20 74 68 69 73 0a 61 72 74 69  ample, this.arti
0820: 63 6c 65 20 75 73 65 73 20 61 20 74 61 62 6c 65  cle uses a table
0830: 20 6e 61 6d 65 64 20 22 46 72 75 69 74 73 46 6f   named "FruitsFo
0840: 72 53 61 6c 65 22 20 77 68 69 63 68 20 72 65 6c  rSale" which rel
0850: 61 74 65 73 20 76 61 72 69 6f 75 73 20 66 72 75  ates various fru
0860: 69 74 73 20 0a 74 6f 20 74 68 65 20 73 74 61 74  its .to the stat
0870: 65 0a 77 68 65 72 65 20 74 68 65 79 20 61 72 65  e.where they are
0880: 20 67 72 6f 77 6e 20 61 6e 64 20 74 68 65 69 72   grown and their
0890: 20 75 6e 69 74 20 70 72 69 63 65 20 61 74 20 6d   unit price at m
08a0: 61 72 6b 65 74 2e 20 20 54 68 65 20 73 63 68 65  arket.  The sche
08b0: 6d 61 20 69 73 20 74 68 69 73 3a 0a 3c 2f 70 3e  ma is this:.</p>
08c0: 0a 0a 3c 74 63 6c 3e 63 6f 64 65 20 7b 0a 43 52  ..<tcl>code {.CR
08d0: 45 41 54 45 20 54 41 42 4c 45 20 46 72 75 69 74  EATE TABLE Fruit
08e0: 73 46 6f 72 53 61 6c 65 28 0a 20 20 46 72 75 69  sForSale(.  Frui
08f0: 74 20 54 45 58 54 2c 0a 20 20 53 74 61 74 65 20  t TEXT,.  State 
0900: 54 45 58 54 2c 0a 20 20 50 72 69 63 65 20 52 45  TEXT,.  Price RE
0910: 41 4c 0a 29 3b 0a 7d 3c 2f 74 63 6c 3e 0a 0a 3c  AL.);.}</tcl>..<
0920: 70 3e 0a 57 69 74 68 20 73 6f 6d 65 20 28 61 72  p>.With some (ar
0930: 62 69 74 72 61 72 79 29 20 64 61 74 61 2c 20 73  bitrary) data, s
0940: 75 63 68 20 61 20 74 61 62 6c 65 20 6d 69 67 68  uch a table migh
0950: 74 20 62 65 20 6c 6f 67 69 63 61 6c 6c 79 20 73  t be logically s
0960: 74 6f 72 65 64 20 6f 6e 20 64 69 73 6b 0a 61 73  tored on disk.as
0970: 20 73 68 6f 77 6e 20 69 6e 20 66 69 67 75 72 65   shown in figure
0980: 20 31 3a 0a 3c 2f 70 3e 0a 0a 3c 74 63 6c 3e 66   1:.</p>..<tcl>f
0990: 69 67 75 72 65 20 31 20 23 66 69 67 31 20 74 61  igure 1 #fig1 ta
09a0: 62 2e 67 69 66 20 7b 4c 6f 67 69 63 61 6c 20 4c  b.gif {Logical L
09b0: 61 79 6f 75 74 20 4f 66 20 54 61 62 6c 65 20 22  ayout Of Table "
09c0: 46 72 75 69 74 73 46 6f 72 53 61 6c 65 22 7d 3c  FruitsForSale"}<
09d0: 2f 74 63 6c 3e 0a 0a 3c 70 3e 0a 54 68 65 20 6b  /tcl>..<p>.The k
09e0: 65 79 20 66 65 61 74 75 72 65 73 20 74 6f 20 6e  ey features to n
09f0: 6f 74 69 63 65 20 69 6e 20 74 68 69 73 20 65 78  otice in this ex
0a00: 61 6d 70 6c 65 20 69 73 20 74 68 61 74 20 74 68  ample is that th
0a10: 65 20 72 6f 77 69 64 73 20 61 72 65 20 6e 6f 74  e rowids are not
0a20: 0a 63 6f 6e 73 65 63 75 74 69 76 65 20 62 75 74  .consecutive but
0a30: 20 74 68 65 79 20 61 72 65 20 6f 72 64 65 72 65   they are ordere
0a40: 64 2e 20 20 53 51 4c 69 74 65 20 75 73 75 61 6c  d.  SQLite usual
0a50: 6c 79 20 63 72 65 61 74 65 73 20 72 6f 77 69 64  ly creates rowid
0a60: 73 20 62 65 67 69 6e 6e 69 6e 67 0a 77 69 74 68  s beginning.with
0a70: 20 6f 6e 65 20 61 6e 64 20 69 6e 63 72 65 61 73   one and increas
0a80: 69 6e 67 20 62 79 20 6f 6e 65 20 77 69 74 68 20  ing by one with 
0a90: 65 61 63 68 20 61 64 64 65 64 20 72 6f 77 2e 20  each added row. 
0aa0: 20 42 75 74 20 69 66 20 72 6f 77 73 20 61 72 65   But if rows are
0ab0: 20 0a 64 65 6c 65 74 65 64 2c 20 67 61 70 73 20   .deleted, gaps 
0ac0: 63 61 6e 20 61 70 70 65 61 72 20 69 6e 20 74 68  can appear in th
0ad0: 65 20 73 65 71 75 65 6e 63 65 2e 20 20 41 6e 64  e sequence.  And
0ae0: 20 74 68 65 20 61 70 70 6c 69 63 61 74 69 6f 6e   the application
0af0: 20 63 61 6e 20 63 6f 6e 74 72 6f 6c 0a 74 68 65   can control.the
0b00: 20 72 6f 77 69 64 20 61 73 73 69 67 6e 65 64 20   rowid assigned 
0b10: 69 66 20 64 65 73 69 72 65 64 2c 20 73 6f 20 74  if desired, so t
0b20: 68 61 74 20 72 6f 77 73 20 61 72 65 20 6e 6f 74  hat rows are not
0b30: 20 6e 65 63 65 73 73 61 72 69 6c 79 20 69 6e 73   necessarily ins
0b40: 65 72 74 65 64 20 0a 61 74 20 74 68 65 20 62 6f  erted .at the bo
0b50: 74 74 6f 6d 2e 20 20 42 75 74 20 72 65 67 61 72  ttom.  But regar
0b60: 64 6c 65 73 73 20 6f 66 20 77 68 61 74 20 68 61  dless of what ha
0b70: 70 70 65 6e 73 2c 20 74 68 65 20 72 6f 77 69 64  ppens, the rowid
0b80: 73 20 61 72 65 20 61 6c 77 61 79 73 20 0a 75 6e  s are always .un
0b90: 69 71 75 65 20 61 6e 64 20 69 6e 20 73 74 72 69  ique and in stri
0ba0: 63 74 6c 79 20 61 73 63 65 6e 64 69 6e 67 20 6f  ctly ascending o
0bb0: 72 64 65 72 2e 0a 3c 2f 70 3e 0a 0a 3c 70 3e 0a  rder..</p>..<p>.
0bc0: 4e 6f 77 20 73 75 70 70 6f 73 65 20 79 6f 75 20  Now suppose you 
0bd0: 77 61 6e 74 20 74 6f 20 6c 6f 6f 6b 20 75 70 20  want to look up 
0be0: 74 68 65 20 70 72 69 63 65 20 6f 66 20 70 65 61  the price of pea
0bf0: 63 68 65 73 2e 20 20 54 68 65 20 71 75 65 72 79  ches.  The query
0c00: 20 77 6f 75 6c 64 0a 62 65 20 61 73 20 66 6f 6c   would.be as fol
0c10: 6c 6f 77 73 3a 0a 3c 2f 70 3e 0a 0a 3c 74 63 6c  lows:.</p>..<tcl
0c20: 3e 63 6f 64 65 20 7b 0a 53 45 4c 45 43 54 20 70  >code {.SELECT p
0c30: 72 69 63 65 20 46 52 4f 4d 20 66 72 75 69 74 73  rice FROM fruits
0c40: 66 6f 72 73 61 6c 65 20 57 48 45 52 45 20 66 72  forsale WHERE fr
0c50: 75 69 74 3d 27 50 65 61 63 68 27 3b 0a 7d 3c 2f  uit='Peach';.}</
0c60: 74 63 6c 3e 0a 0a 3c 70 3e 0a 49 6e 20 6f 72 64  tcl>..<p>.In ord
0c70: 65 72 20 74 6f 20 73 61 74 69 73 66 79 20 74 68  er to satisfy th
0c80: 69 73 20 71 75 65 72 79 2c 20 53 51 4c 69 74 65  is query, SQLite
0c90: 20 68 61 73 20 74 6f 20 72 65 61 64 20 65 76 65   has to read eve
0ca0: 72 79 20 72 6f 77 20 6f 75 74 20 6f 66 20 74 68  ry row out of th
0cb0: 65 0a 74 61 62 6c 65 2c 20 63 68 65 63 6b 20 74  e.table, check t
0cc0: 6f 20 73 65 65 20 69 66 20 74 68 65 20 22 66 72  o see if the "fr
0cd0: 75 69 74 22 20 63 6f 6c 75 6d 6e 20 68 61 73 20  uit" column has 
0ce0: 74 68 65 20 76 61 6c 75 65 20 6f 66 20 22 50 65  the value of "Pe
0cf0: 61 63 68 22 20 61 6e 64 20 69 66 0a 73 6f 2c 20  ach" and if.so, 
0d00: 6f 75 74 70 75 74 20 74 68 65 20 22 70 72 69 63  output the "pric
0d10: 65 22 20 63 6f 6c 75 6d 6e 20 66 72 6f 6d 20 74  e" column from t
0d20: 68 61 74 20 72 6f 77 2e 20 20 54 68 65 20 70 72  hat row.  The pr
0d30: 6f 63 65 73 73 20 69 73 20 69 6c 6c 75 73 74 72  ocess is illustr
0d40: 61 74 65 64 0a 62 79 20 3c 61 20 68 72 65 66 3d  ated.by <a href=
0d50: 22 23 66 69 67 32 22 3e 66 69 67 75 72 65 20 32  "#fig2">figure 2
0d60: 3c 2f 61 3e 20 62 65 6c 6f 77 2e 0a 54 68 69 73  </a> below..This
0d70: 20 69 73 20 63 61 6c 6c 65 64 20 61 20 3c 69 3e   is called a <i>
0d80: 66 75 6c 6c 20 74 61 62 6c 65 20 73 63 61 6e 3c  full table scan<
0d90: 2f 69 3e 20 73 69 6e 63 65 20 74 68 65 20 65 6e  /i> since the en
0da0: 74 69 72 65 20 63 6f 6e 74 65 6e 74 20 6f 66 20  tire content of 
0db0: 74 68 65 0a 74 61 62 6c 65 20 6d 75 73 74 20 62  the.table must b
0dc0: 65 20 72 65 61 64 20 61 6e 64 20 65 78 61 6d 69  e read and exami
0dd0: 6e 65 64 20 69 6e 20 6f 72 64 65 72 20 74 6f 20  ned in order to 
0de0: 66 69 6e 64 20 74 68 65 20 6f 6e 65 20 72 6f 77  find the one row
0df0: 20 6f 66 20 69 6e 74 65 72 65 73 74 2e 0a 57 69   of interest..Wi
0e00: 74 68 20 61 20 74 61 62 6c 65 20 6f 66 20 6f 6e  th a table of on
0e10: 6c 79 20 37 20 72 6f 77 73 2c 20 74 68 69 73 20  ly 7 rows, this 
0e20: 69 73 20 6e 6f 74 20 61 20 62 69 67 20 64 65 61  is not a big dea
0e30: 6c 2c 20 62 75 74 20 69 66 20 79 6f 75 72 20 74  l, but if your t
0e40: 61 62 6c 65 0a 63 6f 6e 74 61 69 6e 65 64 20 37  able.contained 7
0e50: 20 6d 69 6c 6c 69 6f 6e 20 72 6f 77 73 2c 20 61   million rows, a
0e60: 20 66 75 6c 6c 20 74 61 62 6c 65 20 73 63 61 6e   full table scan
0e70: 20 6d 69 67 68 74 20 72 65 61 64 20 6d 65 67 61   might read mega
0e80: 62 79 74 65 73 20 6f 66 20 63 6f 6e 74 65 6e 74  bytes of content
0e90: 20 69 6e 20 6f 72 64 65 72 20 74 6f 20 66 69 6e   in order to fin
0ea0: 64 20 61 20 73 69 6e 67 6c 65 20 38 2d 62 79 74  d a single 8-byt
0eb0: 65 20 6e 75 6d 62 65 72 2e 20 20 46 6f 72 20 74  e number.  For t
0ec0: 68 61 74 20 72 65 61 73 6f 6e 2c 20 6f 6e 65 20  hat reason, one 
0ed0: 6e 6f 72 6d 61 6c 6c 79 0a 74 72 69 65 73 20 74  normally.tries t
0ee0: 6f 20 61 76 6f 69 64 20 66 75 6c 6c 20 74 61 62  o avoid full tab
0ef0: 6c 65 20 73 63 61 6e 73 2e 0a 3c 2f 70 3e 0a 0a  le scans..</p>..
0f00: 3c 74 63 6c 3e 66 69 67 75 72 65 20 32 20 23 66  <tcl>figure 2 #f
0f10: 69 67 32 20 66 75 6c 6c 73 63 61 6e 2e 67 69 66  ig2 fullscan.gif
0f20: 20 7b 46 75 6c 6c 20 54 61 62 6c 65 20 53 63 61   {Full Table Sca
0f30: 6e 7d 3c 2f 74 63 6c 3e 0a 0a 3c 68 33 3e 31 2e  n}</tcl>..<h3>1.
0f40: 32 20 4c 6f 6f 6b 75 70 20 42 79 20 52 6f 77 69  2 Lookup By Rowi
0f50: 64 3c 2f 68 33 3e 0a 0a 3c 70 3e 0a 4f 6e 65 20  d</h3>..<p>.One 
0f60: 74 65 63 68 6e 69 71 75 65 20 66 6f 72 20 61 76  technique for av
0f70: 6f 69 64 69 6e 67 20 61 20 66 75 6c 6c 20 74 61  oiding a full ta
0f80: 62 6c 65 20 73 63 61 6e 20 69 73 20 74 6f 20 64  ble scan is to d
0f90: 6f 20 6c 6f 6f 6b 75 70 73 20 62 79 0a 72 6f 77  o lookups by.row
0fa0: 69 64 20 28 6f 72 20 62 79 20 74 68 65 20 65 71  id (or by the eq
0fb0: 75 69 76 61 6c 65 6e 74 20 49 4e 54 45 47 45 52  uivalent INTEGER
0fc0: 20 50 52 49 4d 41 52 59 20 4b 45 59 29 2e 20 20   PRIMARY KEY).  
0fd0: 20 54 6f 20 6c 6f 6f 6b 75 70 20 74 68 65 0a 70   To lookup the.p
0fe0: 72 69 63 65 20 6f 66 20 70 65 61 63 68 65 73 2c  rice of peaches,
0ff0: 20 6f 6e 65 20 77 6f 75 6c 64 20 71 75 65 72 79   one would query
1000: 20 66 6f 72 20 74 68 65 20 65 6e 74 72 79 20 77   for the entry w
1010: 69 74 68 20 61 20 72 6f 77 69 64 20 6f 66 20 34  ith a rowid of 4
1020: 3a 0a 3c 2f 70 3e 0a 0a 3c 74 63 6c 3e 63 6f 64  :.</p>..<tcl>cod
1030: 65 20 7b 0a 53 45 4c 45 43 54 20 70 72 69 63 65  e {.SELECT price
1040: 20 46 52 4f 4d 20 66 72 75 69 74 73 66 6f 72 73   FROM fruitsfors
1050: 61 6c 65 20 57 48 45 52 45 20 72 6f 77 69 64 3d  ale WHERE rowid=
1060: 34 3b 0a 7d 3c 2f 74 63 6c 3e 0a 0a 3c 70 3e 0a  4;.}</tcl>..<p>.
1070: 53 69 6e 63 65 20 74 68 65 20 69 6e 66 6f 72 6d  Since the inform
1080: 61 74 69 6f 6e 20 69 73 20 73 74 6f 72 65 64 20  ation is stored 
1090: 69 6e 20 74 68 65 20 74 61 62 6c 65 20 69 6e 20  in the table in 
10a0: 72 6f 77 69 64 20 6f 72 64 65 72 2c 20 53 51 4c  rowid order, SQL
10b0: 69 74 65 0a 63 61 6e 20 66 69 6e 64 20 74 68 65  ite.can find the
10c0: 20 63 6f 72 72 65 63 74 20 72 6f 77 20 75 73 69   correct row usi
10d0: 6e 67 20 64 6f 69 6e 67 20 61 20 62 69 6e 61 72  ng doing a binar
10e0: 79 20 73 65 61 72 63 68 20 6f 6e 20 74 68 65 20  y search on the 
10f0: 72 6f 77 69 64 2e 0a 49 66 20 74 68 65 20 74 61  rowid..If the ta
1100: 62 6c 65 20 63 6f 6e 74 61 69 6e 73 20 4e 20 65  ble contains N e
1110: 6c 65 6d 65 6e 74 2c 20 74 68 65 20 74 69 6d 65  lement, the time
1120: 20 72 65 71 75 69 72 65 64 20 74 6f 20 6c 6f 6f   required to loo
1130: 6b 20 75 70 20 74 68 65 0a 64 65 73 69 72 65 64  k up the.desired
1140: 20 72 6f 77 20 69 73 20 70 72 6f 70 6f 72 74 69   row is proporti
1150: 6f 6e 61 6c 20 74 6f 20 6c 6f 67 4e 20 72 61 74  onal to logN rat
1160: 68 65 72 20 74 68 61 6e 20 62 65 69 6e 67 20 70  her than being p
1170: 72 6f 70 6f 72 74 69 6f 6e 61 6c 0a 74 6f 20 4e  roportional.to N
1180: 20 61 73 20 69 6e 20 61 20 66 75 6c 6c 20 74 61   as in a full ta
1190: 62 6c 65 20 73 63 61 6e 2e 20 20 49 66 20 74 68  ble scan.  If th
11a0: 65 20 74 61 62 6c 65 20 63 6f 6e 74 61 69 6e 73  e table contains
11b0: 20 31 30 20 6d 69 6c 6c 69 6f 6e 20 65 6c 65 6d   10 million elem
11c0: 65 6e 74 73 2c 0a 74 68 61 74 20 6d 65 61 6e 73  ents,.that means
11d0: 20 74 68 65 20 71 75 65 72 79 20 77 69 6c 6c 20   the query will 
11e0: 62 65 20 6f 6e 20 74 68 65 20 6f 72 64 65 72 20  be on the order 
11f0: 6f 66 20 4e 2f 6c 6f 67 4e 20 6f 72 20 61 62 6f  of N/logN or abo
1200: 75 74 20 31 20 6d 69 6c 6c 69 6f 6e 0a 74 69 6d  ut 1 million.tim
1210: 65 73 20 66 61 73 74 65 72 21 0a 3c 2f 70 3e 0a  es faster!.</p>.
1220: 0a 3c 74 63 6c 3e 66 69 67 75 72 65 20 33 20 23  .<tcl>figure 3 #
1230: 66 69 67 33 20 72 6f 77 69 64 6c 75 2e 67 69 66  fig3 rowidlu.gif
1240: 20 7b 4c 6f 6f 6b 75 70 20 42 79 20 52 6f 77 69   {Lookup By Rowi
1250: 64 7d 3c 2f 74 63 6c 3e 0a 0a 3c 68 33 3e 31 2e  d}</tcl>..<h3>1.
1260: 33 20 4c 6f 6f 6b 75 70 20 42 79 20 49 6e 64 65  3 Lookup By Inde
1270: 78 3c 2f 68 33 3e 0a 3c 70 3e 0a 54 68 65 20 70  x</h3>.<p>.The p
1280: 72 6f 62 6c 65 6d 20 77 69 74 68 20 6c 6f 6f 6b  roblem with look
1290: 69 6e 67 20 75 70 20 69 6e 66 6f 72 6d 61 74 69  ing up informati
12a0: 6f 6e 20 62 79 20 72 6f 77 69 64 20 69 73 20 74  on by rowid is t
12b0: 68 61 74 20 79 6f 75 20 70 72 6f 62 61 62 6c 79  hat you probably
12c0: 0a 64 6f 20 6e 6f 74 20 63 61 72 65 20 77 68 61  .do not care wha
12d0: 74 20 74 68 65 20 70 72 69 63 65 20 6f 66 20 22  t the price of "
12e0: 69 74 65 6d 20 34 22 20 69 73 20 2d 20 79 6f 75  item 4" is - you
12f0: 20 77 61 6e 74 20 74 6f 20 6b 6e 6f 77 20 74 68   want to know th
1300: 65 20 70 72 69 63 65 0a 6f 66 20 70 65 61 63 68  e price.of peach
1310: 65 73 2e 20 20 41 6e 64 20 73 6f 20 61 20 72 6f  es.  And so a ro
1320: 77 69 64 20 6c 6f 6f 6b 75 70 20 69 73 20 6e 6f  wid lookup is no
1330: 74 20 68 65 6c 70 66 75 6c 2e 0a 3c 2f 70 3e 0a  t helpful..</p>.
1340: 0a 3c 70 3e 0a 54 6f 20 6d 61 6b 65 20 74 68 65  .<p>.To make the
1350: 20 6f 72 69 67 69 6e 61 6c 20 71 75 65 72 79 20   original query 
1360: 6d 6f 72 65 20 65 66 66 69 63 69 65 6e 74 2c 20  more efficient, 
1370: 77 65 20 63 61 6e 20 61 64 64 20 61 6e 20 69 6e  we can add an in
1380: 64 65 78 20 6f 6e 20 74 68 65 0a 22 66 72 75 69  dex on the."frui
1390: 74 22 20 63 6f 6c 75 6d 6e 20 6f 66 20 74 68 65  t" column of the
13a0: 20 22 66 72 75 69 74 73 66 6f 72 73 61 6c 65 22   "fruitsforsale"
13b0: 20 74 61 62 6c 65 20 6c 69 6b 65 20 74 68 69 73   table like this
13c0: 3a 0a 3c 2f 70 3e 0a 0a 3c 74 63 6c 3e 63 6f 64  :.</p>..<tcl>cod
13d0: 65 20 7b 0a 43 52 45 41 54 45 20 49 4e 44 45 58  e {.CREATE INDEX
13e0: 20 69 64 78 31 20 4f 4e 20 66 72 75 69 74 73 66   idx1 ON fruitsf
13f0: 6f 72 73 61 6c 65 28 66 72 75 69 74 29 3b 0a 7d  orsale(fruit);.}
1400: 3c 2f 74 63 6c 3e 0a 0a 3c 70 3e 0a 41 6e 20 69  </tcl>..<p>.An i
1410: 6e 64 65 78 20 69 73 20 61 6e 6f 74 68 65 72 20  ndex is another 
1420: 74 61 62 6c 65 20 73 69 6d 69 6c 61 72 20 74 6f  table similar to
1430: 20 74 68 65 20 6f 72 69 67 69 6e 61 6c 20 22 66   the original "f
1440: 72 75 69 74 73 66 6f 72 73 61 6c 65 22 20 74 61  ruitsforsale" ta
1450: 62 6c 65 0a 62 75 74 20 77 69 74 68 20 74 68 65  ble.but with the
1460: 20 63 6f 6e 74 65 6e 74 20 28 74 68 65 20 66 72   content (the fr
1470: 75 69 74 20 63 6f 6c 75 6d 6e 20 69 6e 20 74 68  uit column in th
1480: 69 73 20 63 61 73 65 29 20 73 74 6f 72 65 64 20  is case) stored 
1490: 69 6e 20 66 72 6f 6e 74 20 6f 66 20 74 68 65 0a  in front of the.
14a0: 72 6f 77 69 64 20 61 6e 64 20 77 69 74 68 20 61  rowid and with a
14b0: 6c 6c 20 72 6f 77 73 20 69 6e 20 63 6f 6e 74 65  ll rows in conte
14c0: 6e 74 20 6f 72 64 65 72 2e 0a 3c 61 20 68 72 65  nt order..<a hre
14d0: 66 3d 22 23 66 69 67 34 22 3e 46 69 67 75 72 65  f="#fig4">Figure
14e0: 20 34 3c 2f 61 3e 20 67 69 76 65 73 20 61 20 6c   4</a> gives a l
14f0: 6f 67 69 63 61 6c 20 76 69 65 77 20 6f 66 20 74  ogical view of t
1500: 68 65 20 49 64 78 31 20 69 6e 64 65 78 2e 0a 54  he Idx1 index..T
1510: 68 65 20 22 66 72 75 69 74 22 20 63 6f 6c 75 6d  he "fruit" colum
1520: 6e 20 69 73 20 74 68 65 20 70 72 69 6d 61 72 79  n is the primary
1530: 20 6b 65 79 20 75 73 65 64 20 74 6f 20 6f 72 64   key used to ord
1540: 65 72 20 74 68 65 20 65 6c 65 6d 65 6e 74 73 20  er the elements 
1550: 6f 66 20 74 68 65 0a 74 61 62 6c 65 20 61 6e 64  of the.table and
1560: 20 74 68 65 20 22 72 6f 77 69 64 22 20 69 73 20   the "rowid" is 
1570: 74 68 65 20 73 65 63 6f 6e 64 61 72 79 20 6b 65  the secondary ke
1580: 79 20 75 73 65 64 20 74 6f 20 62 72 65 61 6b 20  y used to break 
1590: 74 68 65 20 74 69 65 20 77 68 65 6e 0a 74 77 6f  the tie when.two
15a0: 20 6f 72 20 6d 6f 72 65 20 72 6f 77 73 20 68 61   or more rows ha
15b0: 76 65 20 74 68 65 20 73 61 6d 65 20 22 66 72 75  ve the same "fru
15c0: 69 74 22 2e 20 20 49 6e 20 74 68 65 20 65 78 61  it".  In the exa
15d0: 6d 70 6c 65 2c 20 74 68 65 20 72 6f 77 69 64 0a  mple, the rowid.
15e0: 68 61 73 20 74 6f 20 62 65 20 75 73 65 64 20 61  has to be used a
15f0: 73 20 61 20 74 69 65 2d 62 72 65 61 6b 65 72 20  s a tie-breaker 
1600: 66 6f 72 20 74 68 65 20 22 4f 72 61 6e 67 65 22  for the "Orange"
1610: 20 72 6f 77 73 2e 0a 4e 6f 74 69 63 65 20 74 68   rows..Notice th
1620: 61 74 20 73 69 6e 63 65 20 74 68 65 20 72 6f 77  at since the row
1630: 69 64 0a 69 73 20 61 6c 77 61 79 73 20 75 6e 69  id.is always uni
1640: 71 75 65 20 6f 76 65 72 20 61 6c 6c 20 65 6c 65  que over all ele
1650: 6d 65 6e 74 73 20 6f 66 20 74 68 65 20 6f 72 69  ments of the ori
1660: 67 69 6e 61 6c 20 74 61 62 6c 65 2c 20 74 68 65  ginal table, the
1670: 20 63 6f 6d 70 6f 73 69 74 65 20 6b 65 79 0a 6f   composite key.o
1680: 66 20 22 66 72 75 69 74 22 20 66 6f 6c 6c 6f 77  f "fruit" follow
1690: 65 64 20 62 79 20 22 72 6f 77 69 64 22 20 77 69  ed by "rowid" wi
16a0: 6c 6c 20 62 65 20 75 6e 69 71 75 65 20 6f 76 65  ll be unique ove
16b0: 72 20 61 6c 6c 20 65 6c 65 6d 65 6e 74 73 20 6f  r all elements o
16c0: 66 20 74 68 65 20 69 6e 64 65 78 2e 0a 3c 2f 70  f the index..</p
16d0: 3e 0a 0a 3c 74 63 6c 3e 66 69 67 75 72 65 20 34  >..<tcl>figure 4
16e0: 20 23 66 69 67 34 20 69 64 78 31 2e 67 69 66 20   #fig4 idx1.gif 
16f0: 7b 41 6e 20 49 6e 64 65 78 20 4f 6e 20 54 68 65  {An Index On The
1700: 20 46 72 75 69 74 20 43 6f 6c 75 6d 6e 7d 3c 2f   Fruit Column}</
1710: 74 63 6c 3e 0a 0a 3c 70 3e 0a 57 69 74 68 20 74  tcl>..<p>.With t
1720: 68 65 20 6e 65 77 20 69 6e 64 65 78 20 69 6e 20  he new index in 
1730: 70 6c 61 63 65 2c 20 77 65 20 63 61 6e 20 64 65  place, we can de
1740: 76 69 73 65 20 61 6e 20 61 6c 74 65 72 6e 61 74  vise an alternat
1750: 69 76 65 20 70 6c 61 6e 20 66 6f 72 20 74 68 65  ive plan for the
1760: 0a 6f 72 69 67 69 6e 61 6c 20 22 50 72 69 63 65  .original "Price
1770: 20 6f 66 20 50 65 61 63 68 65 73 22 20 71 75 65   of Peaches" que
1780: 72 79 2e 0a 3c 2f 70 3e 0a 0a 3c 74 63 6c 3e 63  ry..</p>..<tcl>c
1790: 6f 64 65 20 7b 0a 53 45 4c 45 43 54 20 70 72 69  ode {.SELECT pri
17a0: 63 65 20 46 52 4f 4d 20 66 72 75 69 74 73 66 6f  ce FROM fruitsfo
17b0: 72 73 61 6c 65 20 57 48 45 52 45 20 66 72 75 69  rsale WHERE frui
17c0: 74 3d 27 50 65 61 63 68 27 3b 0a 7d 3c 2f 74 63  t='Peach';.}</tc
17d0: 6c 3e 0a 0a 3c 70 3e 0a 54 68 65 20 71 75 65 72  l>..<p>.The quer
17e0: 79 20 73 74 61 72 74 73 20 62 79 20 64 6f 69 6e  y starts by doin
17f0: 67 20 61 20 62 69 6e 61 72 79 20 73 65 61 72 63  g a binary searc
1800: 68 20 6f 6e 20 74 68 65 20 49 64 78 31 20 69 6e  h on the Idx1 in
1810: 64 65 78 20 66 6f 72 20 65 6e 74 72 69 65 73 0a  dex for entries.
1820: 74 68 61 74 20 68 61 76 65 20 66 72 75 69 74 3d  that have fruit=
1830: 27 50 65 61 63 68 27 2e 20 20 53 51 4c 69 74 65  'Peach'.  SQLite
1840: 20 63 61 6e 20 64 6f 20 74 68 69 73 20 62 69 6e   can do this bin
1850: 61 72 79 20 73 65 61 72 63 68 20 6f 6e 20 74 68  ary search on th
1860: 65 20 49 64 78 31 20 69 6e 64 65 78 0a 62 75 74  e Idx1 index.but
1870: 20 6e 6f 74 20 6f 6e 20 74 68 65 20 6f 72 69 67   not on the orig
1880: 69 6e 61 6c 20 46 72 75 69 74 73 46 6f 72 53 61  inal FruitsForSa
1890: 6c 65 20 74 61 62 6c 65 20 62 65 63 61 75 73 65  le table because
18a0: 20 74 68 65 20 72 6f 77 73 20 69 6e 20 49 64 78   the rows in Idx
18b0: 31 20 61 72 65 20 73 6f 72 74 65 64 0a 62 79 20  1 are sorted.by 
18c0: 74 68 65 20 22 66 72 75 69 74 22 20 63 6f 6c 75  the "fruit" colu
18d0: 6d 6e 2e 20 20 48 61 76 69 6e 67 20 66 6f 75 6e  mn.  Having foun
18e0: 64 20 61 20 72 6f 77 20 69 6e 20 74 68 65 20 49  d a row in the I
18f0: 64 78 31 20 69 6e 64 65 78 20 74 68 61 74 20 68  dx1 index that h
1900: 61 73 0a 66 72 75 69 74 3d 27 50 65 61 63 68 27  as.fruit='Peach'
1910: 2c 20 74 68 65 20 64 61 74 61 62 61 73 65 20 65  , the database e
1920: 6e 67 69 6e 65 20 63 61 6e 20 65 78 74 72 61 63  ngine can extrac
1930: 74 20 74 68 65 20 72 6f 77 69 64 20 66 6f 72 20  t the rowid for 
1940: 74 68 61 74 20 72 6f 77 2c 0a 74 68 65 6e 20 64  that row,.then d
1950: 6f 20 61 20 73 65 70 61 72 61 74 65 20 62 69 6e  o a separate bin
1960: 61 72 79 20 73 65 61 72 63 68 20 6f 6e 20 74 68  ary search on th
1970: 65 20 6f 72 69 67 69 6e 61 6c 20 46 72 75 69 74  e original Fruit
1980: 73 46 6f 72 53 61 6c 65 20 74 61 62 6c 65 20 74  sForSale table t
1990: 6f 20 66 69 6e 64 20 74 68 65 0a 6f 72 69 67 69  o find the.origi
19a0: 6e 61 6c 20 72 6f 77 20 74 68 61 74 20 63 6f 6e  nal row that con
19b0: 74 61 69 6e 73 20 66 72 75 69 74 3d 27 50 65 61  tains fruit='Pea
19c0: 63 68 27 2e 20 20 46 72 6f 6d 20 74 68 65 20 72  ch'.  From the r
19d0: 6f 77 20 69 6e 20 74 68 65 20 46 72 75 69 74 73  ow in the Fruits
19e0: 46 6f 72 53 61 6c 65 20 74 61 62 6c 65 2c 0a 53  ForSale table,.S
19f0: 51 4c 69 74 65 20 63 61 6e 20 65 78 74 72 61 63  QLite can extrac
1a00: 74 20 74 68 65 20 76 61 6c 75 65 20 6f 66 20 74  t the value of t
1a10: 68 65 20 70 72 69 63 65 20 63 6f 6c 75 6d 6e 2e  he price column.
1a20: 0a 54 68 69 73 20 70 72 6f 63 65 64 75 72 65 20  .This procedure 
1a30: 69 73 20 69 6c 6c 75 73 74 72 61 74 65 64 20 62  is illustrated b
1a40: 79 20 3c 61 20 68 72 65 66 3d 22 23 66 69 67 35  y <a href="#fig5
1a50: 22 3e 66 69 67 75 72 65 20 35 3c 2f 61 3e 2e 0a  ">figure 5</a>..
1a60: 3c 2f 70 3e 0a 0a 3c 74 63 6c 3e 66 69 67 75 72  </p>..<tcl>figur
1a70: 65 20 35 20 23 66 69 67 35 20 69 64 78 31 6c 75  e 5 #fig5 idx1lu
1a80: 31 2e 67 69 66 20 7b 49 6e 64 65 78 65 64 20 4c  1.gif {Indexed L
1a90: 6f 6f 6b 75 70 20 46 6f 72 20 54 68 65 20 50 72  ookup For The Pr
1aa0: 69 63 65 20 4f 66 20 50 65 61 63 68 65 73 7d 3c  ice Of Peaches}<
1ab0: 2f 74 63 6c 3e 0a 0a 3c 70 3e 0a 53 51 4c 69 74  /tcl>..<p>.SQLit
1ac0: 65 20 68 61 73 20 74 6f 20 64 6f 20 74 77 6f 20  e has to do two 
1ad0: 62 69 6e 61 72 79 20 73 65 61 72 63 68 65 73 20  binary searches 
1ae0: 74 6f 20 66 69 6e 64 20 74 68 65 20 70 72 69 63  to find the pric
1af0: 65 20 6f 66 20 70 65 61 63 68 65 73 20 75 73 69  e of peaches usi
1b00: 6e 67 0a 74 68 65 20 6d 65 74 68 6f 64 20 73 68  ng.the method sh
1b10: 6f 77 20 61 62 6f 76 65 2e 20 20 42 75 74 20 66  ow above.  But f
1b20: 6f 72 20 61 20 74 61 62 6c 65 20 77 69 74 68 20  or a table with 
1b30: 61 20 6c 61 72 67 65 20 6e 75 6d 62 65 72 20 6f  a large number o
1b40: 66 20 72 6f 77 73 2c 20 74 68 69 73 0a 69 73 20  f rows, this.is 
1b50: 73 74 69 6c 6c 20 6d 75 63 68 20 66 61 73 74 65  still much faste
1b60: 72 20 74 68 61 6e 20 64 6f 69 6e 67 20 61 20 66  r than doing a f
1b70: 75 6c 6c 20 74 61 62 6c 65 20 73 63 61 6e 2e 0a  ull table scan..
1b80: 3c 2f 70 3e 0a 0a 3c 68 33 3e 31 2e 34 20 4d 75  </p>..<h3>1.4 Mu
1b90: 6c 74 69 70 6c 65 20 52 65 73 75 6c 74 20 52 6f  ltiple Result Ro
1ba0: 77 73 3c 2f 68 33 3e 0a 0a 3c 70 3e 0a 49 6e 20  ws</h3>..<p>.In 
1bb0: 74 68 65 20 70 72 65 76 69 6f 75 73 20 71 75 65  the previous que
1bc0: 72 79 20 74 68 65 20 66 72 75 69 74 3d 27 50 65  ry the fruit='Pe
1bd0: 61 63 68 27 20 63 6f 6e 73 74 72 61 69 6e 74 20  ach' constraint 
1be0: 6e 61 72 72 6f 77 65 64 20 74 68 65 20 72 65 73  narrowed the res
1bf0: 75 6c 74 0a 64 6f 77 6e 20 74 6f 20 61 20 73 69  ult.down to a si
1c00: 6e 67 6c 65 20 72 6f 77 2e 20 20 42 75 74 20 74  ngle row.  But t
1c10: 68 65 20 73 61 6d 65 20 74 65 63 68 6e 69 71 75  he same techniqu
1c20: 65 20 77 6f 72 6b 73 20 65 76 65 6e 20 69 66 20  e works even if 
1c30: 6d 75 6c 74 69 70 6c 65 0a 72 6f 77 73 20 61 72  multiple.rows ar
1c40: 65 20 6f 62 74 61 69 6e 65 64 2e 20 20 53 75 70  e obtained.  Sup
1c50: 70 6f 73 65 20 77 65 20 6c 6f 6f 6b 65 64 20 75  pose we looked u
1c60: 70 20 74 68 65 20 70 72 69 63 65 20 6f 66 20 4f  p the price of O
1c70: 72 61 6e 67 65 73 20 69 6e 73 74 65 61 64 20 6f  ranges instead o
1c80: 66 0a 50 65 61 63 68 65 73 3a 0a 3c 2f 70 3e 0a  f.Peaches:.</p>.
1c90: 0a 3c 74 63 6c 3e 0a 63 6f 64 65 20 7b 53 45 4c  .<tcl>.code {SEL
1ca0: 45 43 54 20 70 72 69 63 65 20 46 52 4f 4d 20 66  ECT price FROM f
1cb0: 72 75 69 74 73 66 6f 72 73 61 6c 65 20 57 48 45  ruitsforsale WHE
1cc0: 52 45 20 66 72 75 69 74 3d 27 4f 72 61 6e 67 65  RE fruit='Orange
1cd0: 27 7d 0a 66 69 67 75 72 65 20 36 20 23 66 69 67  '}.figure 6 #fig
1ce0: 36 20 69 64 78 31 6c 75 32 2e 67 69 66 20 7b 49  6 idx1lu2.gif {I
1cf0: 6e 64 65 78 65 64 20 4c 6f 6f 6b 75 70 20 46 6f  ndexed Lookup Fo
1d00: 72 20 54 68 65 20 50 72 69 63 65 20 4f 66 20 4f  r The Price Of O
1d10: 72 61 6e 67 65 73 7d 0a 3c 2f 74 63 6c 3e 0a 0a  ranges}.</tcl>..
1d20: 3c 70 3e 0a 49 6e 20 74 68 69 73 20 63 61 73 65  <p>.In this case
1d30: 2c 20 53 51 4c 69 74 65 20 73 74 69 6c 6c 20 64  , SQLite still d
1d40: 6f 65 73 20 61 20 73 69 6e 67 6c 65 20 62 69 6e  oes a single bin
1d50: 61 72 79 20 73 65 61 72 63 68 20 74 6f 20 66 69  ary search to fi
1d60: 6e 64 20 74 68 65 20 66 69 72 73 74 0a 65 6e 74  nd the first.ent
1d70: 72 79 20 6f 66 20 74 68 65 20 69 6e 64 65 78 20  ry of the index 
1d80: 77 68 65 72 65 20 66 72 75 69 74 3d 27 4f 72 61  where fruit='Ora
1d90: 6e 67 65 27 2e 20 20 54 68 65 6e 20 69 74 20 65  nge'.  Then it e
1da0: 78 74 72 61 63 74 73 20 74 68 65 20 72 6f 77 69  xtracts the rowi
1db0: 64 20 66 72 6f 6d 0a 74 68 65 20 69 6e 64 65 78  d from.the index
1dc0: 20 61 6e 64 20 75 73 65 73 20 74 68 61 74 20 72   and uses that r
1dd0: 6f 77 69 64 20 74 6f 20 6c 6f 6f 6b 75 70 20 74  owid to lookup t
1de0: 68 65 20 6f 72 69 67 69 6e 61 6c 20 74 61 62 6c  he original tabl
1df0: 65 20 65 6e 74 72 79 20 76 69 61 0a 62 69 6e 61  e entry via.bina
1e00: 72 79 20 73 65 61 72 63 68 20 61 6e 64 20 6f 75  ry search and ou
1e10: 74 70 75 74 20 74 68 65 20 70 72 69 63 65 20 66  tput the price f
1e20: 72 6f 6d 20 74 68 65 20 6f 72 69 67 69 6e 61 6c  rom the original
1e30: 20 74 61 62 6c 65 2e 20 20 42 75 74 20 69 6e 73   table.  But ins
1e40: 74 65 61 64 0a 6f 66 20 71 75 69 74 74 69 6e 67  tead.of quitting
1e50: 2c 20 74 68 65 20 64 61 74 61 62 61 73 65 20 65  , the database e
1e60: 6e 67 69 6e 65 20 74 68 65 6e 20 61 64 76 61 6e  ngine then advan
1e70: 63 65 73 20 74 6f 20 74 68 65 20 6e 65 78 74 20  ces to the next 
1e80: 72 6f 77 20 6f 66 20 69 6e 64 65 78 0a 74 6f 20  row of index.to 
1e90: 72 65 70 65 61 74 20 74 68 65 20 70 72 6f 63 65  repeat the proce
1ea0: 73 73 20 66 6f 72 20 6e 65 78 74 20 66 72 75 69  ss for next frui
1eb0: 74 3d 27 4f 72 61 6e 67 65 27 20 65 6e 74 72 79  t='Orange' entry
1ec0: 2e 20 20 41 64 76 61 6e 63 69 6e 67 20 74 6f 20  .  Advancing to 
1ed0: 74 68 65 0a 6e 65 78 74 20 72 6f 77 20 6f 66 20  the.next row of 
1ee0: 61 6e 20 69 6e 64 65 78 20 28 6f 72 20 74 61 62  an index (or tab
1ef0: 6c 65 29 20 69 73 20 6d 75 63 68 20 6c 65 73 73  le) is much less
1f00: 20 63 6f 73 74 6c 79 20 74 68 61 6e 20 64 6f 69   costly than doi
1f10: 6e 67 20 61 20 62 69 6e 61 72 79 0a 73 65 61 72  ng a binary.sear
1f20: 63 68 20 73 69 6e 63 65 20 74 68 65 20 6e 65 78  ch since the nex
1f30: 74 20 72 6f 77 20 69 73 20 6f 66 74 65 6e 20 6c  t row is often l
1f40: 6f 63 61 74 65 64 20 6f 6e 20 74 68 65 20 73 61  ocated on the sa
1f50: 6d 65 20 64 61 74 61 62 61 73 65 20 70 61 67 65  me database page
1f60: 20 61 73 0a 74 68 65 20 63 75 72 72 65 6e 74 20   as.the current 
1f70: 72 6f 77 2e 20 20 49 6e 20 66 61 63 74 2c 20 74  row.  In fact, t
1f80: 68 65 20 63 6f 73 74 20 6f 66 20 61 64 76 61 6e  he cost of advan
1f90: 63 69 6e 67 20 74 6f 20 74 68 65 20 6e 65 78 74  cing to the next
1fa0: 20 72 6f 77 20 69 73 20 73 6f 0a 63 68 65 61 70   row is so.cheap
1fb0: 20 69 6e 20 63 6f 6d 70 61 72 69 73 6f 6e 20 74   in comparison t
1fc0: 6f 20 61 20 62 69 6e 61 72 79 20 73 65 61 72 63  o a binary searc
1fd0: 68 20 74 68 61 74 20 77 65 20 75 73 75 61 6c 6c  h that we usuall
1fe0: 79 20 69 67 6e 6f 72 65 20 69 74 2e 20 20 53 6f  y ignore it.  So
1ff0: 0a 6f 75 72 20 65 73 74 69 6d 61 74 65 20 66 6f  .our estimate fo
2000: 72 20 74 68 65 20 74 6f 74 61 6c 20 63 6f 73 74  r the total cost
2010: 20 6f 66 20 74 68 69 73 20 71 75 65 72 79 20 69   of this query i
2020: 73 20 33 20 62 69 6e 61 72 79 20 73 65 61 72 63  s 3 binary searc
2030: 68 65 73 2e 0a 49 66 20 74 68 65 20 6e 75 6d 62  hes..If the numb
2040: 65 72 20 6f 66 20 72 6f 77 73 20 6f 66 20 6f 75  er of rows of ou
2050: 74 70 75 74 20 69 73 20 4b 20 61 6e 64 20 74 68  tput is K and th
2060: 65 20 6e 75 6d 62 65 72 20 6f 66 20 72 6f 77 73  e number of rows
2070: 20 69 6e 20 74 68 65 20 74 61 62 6c 65 0a 69 73   in the table.is
2080: 20 4e 2c 20 74 68 65 6e 20 69 6e 20 67 65 6e 65   N, then in gene
2090: 72 61 6c 20 74 68 65 20 63 6f 73 74 20 6f 66 20  ral the cost of 
20a0: 64 6f 69 6e 67 20 74 68 65 20 71 75 65 72 79 20  doing the query 
20b0: 69 73 20 70 72 6f 70 6f 72 74 69 6f 6e 61 6c 0a  is proportional.
20c0: 74 6f 20 28 4b 2b 31 29 2a 6c 6f 67 4e 2e 0a 3c  to (K+1)*logN..<
20d0: 2f 70 3e 0a 0a 3c 68 33 3e 31 2e 35 20 4d 75 6c  /p>..<h3>1.5 Mul
20e0: 74 69 70 6c 65 20 41 4e 44 2d 43 6f 6e 6e 65 63  tiple AND-Connec
20f0: 74 65 64 20 57 48 45 52 45 2d 43 6c 61 75 73 65  ted WHERE-Clause
2100: 20 54 65 72 6d 73 3c 2f 68 33 3e 0a 0a 3c 70 3e   Terms</h3>..<p>
2110: 0a 4e 65 78 74 2c 20 73 75 70 70 6f 73 65 20 74  .Next, suppose t
2120: 68 61 74 20 79 6f 75 20 77 61 6e 74 20 74 6f 20  hat you want to 
2130: 6c 6f 6f 6b 20 75 70 20 74 68 65 20 70 72 69 63  look up the pric
2140: 65 20 6f 66 20 6e 6f 74 20 6a 75 73 74 20 61 6e  e of not just an
2150: 79 20 6f 72 61 6e 67 65 2c 0a 62 75 74 20 73 70  y orange,.but sp
2160: 65 63 69 66 69 63 61 6c 6c 79 20 43 61 6c 69 66  ecifically Calif
2170: 6f 72 6e 69 61 2d 67 72 6f 77 6e 20 6f 72 61 6e  ornia-grown oran
2180: 67 65 73 2e 20 20 54 68 65 20 61 70 70 72 6f 70  ges.  The approp
2190: 72 69 61 74 65 20 71 75 65 72 79 20 77 6f 75 6c  riate query woul
21a0: 64 0a 62 65 20 61 73 20 66 6f 6c 6c 6f 77 73 3a  d.be as follows:
21b0: 0a 3c 2f 70 3e 0a 0a 3c 74 63 6c 3e 0a 63 6f 64  .</p>..<tcl>.cod
21c0: 65 20 7b 53 45 4c 45 43 54 20 70 72 69 63 65 20  e {SELECT price 
21d0: 46 52 4f 4d 20 66 72 75 69 74 73 66 6f 72 73 61  FROM fruitsforsa
21e0: 6c 65 20 57 48 45 52 45 20 66 72 75 69 74 3d 27  le WHERE fruit='
21f0: 4f 72 61 6e 67 65 27 20 41 4e 44 20 73 74 61 74  Orange' AND stat
2200: 65 3d 27 43 41 27 7d 0a 66 69 67 75 72 65 20 37  e='CA'}.figure 7
2210: 20 23 66 69 67 37 20 69 64 78 31 6c 75 33 2e 67   #fig7 idx1lu3.g
2220: 69 66 20 7b 49 6e 64 65 78 65 64 20 4c 6f 6f 6b  if {Indexed Look
2230: 75 70 20 4f 66 20 43 61 6c 69 66 6f 72 6e 69 61  up Of California
2240: 20 4f 72 61 6e 67 65 73 7d 0a 3c 2f 74 63 6c 3e   Oranges}.</tcl>
2250: 0a 0a 3c 70 3e 0a 4f 6e 65 20 61 70 70 72 6f 61  ..<p>.One approa
2260: 63 68 20 74 6f 20 74 68 69 73 20 71 75 65 72 79  ch to this query
2270: 20 69 73 20 74 6f 20 75 73 65 20 74 68 65 20 66   is to use the f
2280: 72 75 69 74 3d 27 4f 72 61 6e 67 65 27 20 74 65  ruit='Orange' te
2290: 72 6d 20 6f 66 20 74 68 65 20 57 48 45 52 45 0a  rm of the WHERE.
22a0: 63 6c 61 75 73 65 20 74 6f 20 66 69 6e 64 20 61  clause to find a
22b0: 6c 6c 20 72 6f 77 73 20 64 65 61 6c 69 6e 67 20  ll rows dealing 
22c0: 77 69 74 68 20 6f 72 61 6e 67 65 73 2c 20 74 68  with oranges, th
22d0: 65 6e 20 66 69 6c 74 65 72 20 74 68 6f 73 65 20  en filter those 
22e0: 72 6f 77 73 0a 62 79 20 72 65 6a 65 63 74 69 6e  rows.by rejectin
22f0: 67 20 61 6e 79 20 74 68 61 74 20 61 72 65 20 66  g any that are f
2300: 72 6f 6d 20 73 74 61 74 65 73 20 6f 74 68 65 72  rom states other
2310: 20 74 68 61 6e 20 43 61 6c 69 66 6f 72 6e 69 61   than California
2320: 2e 20 20 54 68 69 73 0a 70 72 6f 63 65 73 73 20  .  This.process 
2330: 69 73 20 73 68 6f 77 6e 20 62 79 20 3c 61 20 68  is shown by <a h
2340: 72 65 66 3d 22 23 66 69 67 37 22 3e 66 69 67 75  ref="#fig7">figu
2350: 72 65 20 37 3c 2f 61 3e 20 61 62 6f 76 65 2e 20  re 7</a> above. 
2360: 20 54 68 69 73 20 69 73 20 61 20 70 65 72 66 65   This is a perfe
2370: 63 74 6c 79 0a 72 65 61 73 6f 6e 61 62 6c 65 20  ctly.reasonable 
2380: 61 70 70 72 6f 61 63 68 20 69 6e 20 6d 6f 73 74  approach in most
2390: 20 63 61 73 65 73 2e 20 20 59 65 73 2c 20 74 68   cases.  Yes, th
23a0: 65 20 64 61 74 61 62 61 73 65 20 65 6e 67 69 6e  e database engin
23b0: 65 20 64 69 64 20 68 61 76 65 0a 74 6f 20 64 6f  e did have.to do
23c0: 20 61 6e 20 65 78 74 72 61 20 62 69 6e 61 72 79   an extra binary
23d0: 20 73 65 61 72 63 68 20 66 6f 72 20 74 68 65 20   search for the 
23e0: 46 6c 6f 72 69 64 61 20 6f 72 61 6e 67 65 20 72  Florida orange r
23f0: 6f 77 20 74 68 61 74 20 77 61 73 0a 6c 61 74 65  ow that was.late
2400: 72 20 72 65 6a 65 63 74 65 64 2c 20 73 6f 20 69  r rejected, so i
2410: 74 20 77 61 73 20 6e 6f 74 20 61 73 20 65 66 66  t was not as eff
2420: 69 63 69 65 6e 74 20 61 73 20 77 65 20 6d 69 67  icient as we mig
2430: 68 74 20 68 6f 70 65 2c 20 74 68 6f 75 67 68 0a  ht hope, though.
2440: 66 6f 72 20 6d 61 6e 79 20 61 70 70 6c 69 63 61  for many applica
2450: 74 69 6f 6e 73 20 69 74 20 69 73 20 65 66 66 69  tions it is effi
2460: 63 69 65 6e 74 20 65 6e 6f 75 67 68 2e 20 20 0a  cient enough.  .
2470: 3c 2f 70 3e 0a 0a 3c 70 3e 0a 53 75 70 70 6f 73  </p>..<p>.Suppos
2480: 65 20 74 68 61 74 20 69 6e 20 61 64 64 69 74 69  e that in additi
2490: 6f 6e 20 74 6f 20 74 68 65 20 69 6e 64 65 78 20  on to the index 
24a0: 6f 6e 20 22 66 72 75 69 74 22 20 74 68 65 72 65  on "fruit" there
24b0: 20 77 61 73 20 61 6c 73 6f 0a 61 6e 20 69 6e 64   was also.an ind
24c0: 65 78 20 6f 6e 20 22 73 74 61 74 65 22 2e 0a 3c  ex on "state"..<
24d0: 2f 70 3e 0a 0a 3c 74 63 6c 3e 0a 63 6f 64 65 20  /p>..<tcl>.code 
24e0: 7b 43 52 45 41 54 45 20 49 4e 44 45 58 20 49 64  {CREATE INDEX Id
24f0: 78 32 20 4f 4e 20 66 72 75 69 74 73 66 6f 72 73  x2 ON fruitsfors
2500: 61 6c 65 28 73 74 61 74 65 29 3b 7d 0a 66 69 67  ale(state);}.fig
2510: 75 72 65 20 38 20 23 66 69 67 38 20 69 64 78 32  ure 8 #fig8 idx2
2520: 2e 67 69 66 20 7b 49 6e 64 65 78 20 4f 6e 20 54  .gif {Index On T
2530: 68 65 20 53 74 61 74 65 20 43 6f 6c 75 6d 6e 7d  he State Column}
2540: 0a 3c 2f 74 63 6c 3e 0a 0a 3c 70 3e 0a 54 68 65  .</tcl>..<p>.The
2550: 20 22 73 74 61 74 65 22 20 69 6e 64 65 78 20 77   "state" index w
2560: 6f 72 6b 73 20 6a 75 73 74 20 6c 69 6b 65 20 74  orks just like t
2570: 68 65 20 22 66 72 75 69 74 22 20 69 6e 64 65 78  he "fruit" index
2580: 20 69 6e 20 74 68 61 74 20 69 74 20 69 73 20 61   in that it is a
2590: 0a 6e 65 77 20 74 61 62 6c 65 20 77 69 74 68 20  .new table with 
25a0: 61 6e 20 65 78 74 72 61 20 63 6f 6c 75 6d 6e 20  an extra column 
25b0: 69 6e 20 66 72 6f 6e 74 20 6f 66 20 74 68 65 20  in front of the 
25c0: 72 6f 77 69 64 20 61 6e 64 20 73 6f 72 74 65 64  rowid and sorted
25d0: 20 62 79 0a 74 68 61 74 20 65 78 74 72 61 20 63   by.that extra c
25e0: 6f 6c 75 6d 6e 20 61 73 20 74 68 65 20 70 72 69  olumn as the pri
25f0: 6d 61 72 79 20 6b 65 79 2e 20 20 54 68 65 20 6f  mary key.  The o
2600: 6e 6c 79 20 64 69 66 66 65 72 65 6e 63 65 20 69  nly difference i
2610: 73 20 74 68 61 74 0a 69 6e 20 49 64 78 32 2c 20  s that.in Idx2, 
2620: 74 68 65 20 66 69 72 73 74 20 63 6f 6c 75 6d 6e  the first column
2630: 20 69 73 20 22 73 74 61 74 65 22 20 69 6e 73 74   is "state" inst
2640: 65 61 64 20 6f 66 20 22 66 72 75 69 74 22 20 61  ead of "fruit" a
2650: 73 20 69 74 20 69 73 20 77 69 74 68 0a 49 64 78  s it is with.Idx
2660: 31 2e 20 20 49 6e 20 6f 75 72 20 65 78 61 6d 70  1.  In our examp
2670: 6c 65 20 64 61 74 61 20 73 65 74 2c 20 74 68 65  le data set, the
2680: 20 69 73 20 6d 6f 72 65 20 72 65 64 75 6e 64 61   is more redunda
2690: 6e 63 79 20 69 6e 20 74 68 65 20 22 73 74 61 74  ncy in the "stat
26a0: 65 22 0a 63 6f 6c 75 6d 6e 20 61 6e 64 20 73 6f  e".column and so
26b0: 20 74 68 65 79 20 61 72 65 20 6d 6f 72 65 20 64   they are more d
26c0: 75 70 6c 69 63 61 74 65 20 65 6e 74 72 69 65 73  uplicate entries
26d0: 2e 20 20 54 68 65 20 74 69 65 73 20 61 72 65 20  .  The ties are 
26e0: 73 74 69 6c 6c 0a 72 65 73 6f 6c 76 65 64 20 75  still.resolved u
26f0: 73 69 6e 67 20 74 68 65 20 72 6f 77 69 64 2e 0a  sing the rowid..
2700: 3c 2f 70 3e 0a 0a 3c 70 3e 0a 55 73 69 6e 67 20  </p>..<p>.Using 
2710: 74 68 65 20 6e 65 77 20 49 64 78 32 20 69 6e 64  the new Idx2 ind
2720: 65 78 20 6f 6e 20 22 73 74 61 74 65 22 2c 20 53  ex on "state", S
2730: 51 4c 69 74 65 20 68 61 73 20 61 6e 6f 74 68 65  QLite has anothe
2740: 72 20 6f 70 74 69 6f 6e 20 66 6f 72 0a 6c 6f 6f  r option for.loo
2750: 6b 75 70 20 75 70 20 74 68 65 20 70 72 69 63 65  kup up the price
2760: 20 6f 66 20 43 61 6c 69 66 6f 72 6e 69 61 20 6f   of California o
2770: 72 61 6e 67 65 73 3a 20 20 69 74 20 63 61 6e 20  ranges:  it can 
2780: 6c 6f 6f 6b 20 75 70 20 65 76 65 72 79 20 72 6f  look up every ro
2790: 77 0a 74 68 61 74 20 63 6f 6e 74 61 69 6e 73 20  w.that contains 
27a0: 66 72 75 69 74 20 66 72 6f 6d 20 43 61 6c 69 66  fruit from Calif
27b0: 6f 72 6e 69 61 20 61 6e 64 20 66 69 6c 74 65 72  ornia and filter
27c0: 20 6f 75 74 20 74 68 6f 73 65 20 72 6f 77 73 20   out those rows 
27d0: 74 68 61 74 0a 61 72 65 20 6e 6f 74 20 6f 72 61  that.are not ora
27e0: 6e 67 65 73 2e 0a 3c 2f 70 3e 0a 0a 3c 74 63 6c  nges..</p>..<tcl
27f0: 3e 66 69 67 75 72 65 20 39 20 23 66 69 67 39 20  >figure 9 #fig9 
2800: 69 64 78 32 6c 75 31 2e 67 69 66 20 7b 49 6e 64  idx2lu1.gif {Ind
2810: 65 78 65 64 20 4c 6f 6f 6b 75 70 20 4f 66 20 43  exed Lookup Of C
2820: 61 6c 69 66 6f 72 6e 69 61 20 4f 72 61 6e 67 65  alifornia Orange
2830: 73 7d 3c 2f 74 63 6c 3e 0a 0a 3c 70 3e 0a 55 73  s}</tcl>..<p>.Us
2840: 69 6e 67 20 49 64 78 32 20 69 6e 73 74 65 61 64  ing Idx2 instead
2850: 20 6f 66 20 49 64 78 31 20 63 61 75 73 65 73 20   of Idx1 causes 
2860: 53 51 4c 69 74 65 20 74 6f 20 65 78 61 6d 69 6e  SQLite to examin
2870: 65 20 61 20 64 69 66 66 65 72 65 6e 74 20 73 65  e a different se
2880: 74 20 6f 66 0a 72 6f 77 73 2c 20 62 75 74 20 69  t of.rows, but i
2890: 74 20 67 65 74 73 20 74 68 65 20 73 61 6d 65 20  t gets the same 
28a0: 61 6e 73 77 65 72 20 69 6e 20 74 68 65 20 65 6e  answer in the en
28b0: 64 20 28 77 68 69 63 68 20 69 73 20 76 65 72 79  d (which is very
28c0: 20 69 6d 70 6f 72 74 61 6e 74 20 2d 0a 72 65 6d   important -.rem
28d0: 65 6d 62 65 72 20 74 68 61 74 20 69 6e 64 69 63  ember that indic
28e0: 65 73 20 73 68 6f 75 6c 64 20 6e 65 76 65 72 20  es should never 
28f0: 63 68 61 6e 67 65 20 74 68 65 20 61 6e 73 77 65  change the answe
2900: 72 2c 20 6f 6e 6c 79 20 68 65 6c 70 20 53 51 4c  r, only help SQL
2910: 69 74 65 20 74 6f 0a 67 65 74 20 74 6f 20 74 68  ite to.get to th
2920: 65 20 61 6e 73 77 65 72 20 6d 6f 72 65 20 71 75  e answer more qu
2930: 69 63 6b 6c 79 29 20 61 6e 64 20 69 74 20 64 6f  ickly) and it do
2940: 65 73 20 74 68 65 20 73 61 6d 65 20 61 6d 6f 75  es the same amou
2950: 6e 74 20 6f 66 20 77 6f 72 6b 2e 0a 53 6f 20 74  nt of work..So t
2960: 68 65 20 49 64 78 32 20 69 6e 64 65 78 20 64 69  he Idx2 index di
2970: 64 20 6e 6f 74 20 68 65 6c 70 20 70 65 72 66 6f  d not help perfo
2980: 72 6d 61 6e 63 65 20 69 6e 20 74 68 69 73 20 63  rmance in this c
2990: 61 73 65 2e 0a 3c 2f 70 3e 0a 0a 3c 70 3e 0a 54  ase..</p>..<p>.T
29a0: 68 65 20 6c 61 73 74 20 74 77 6f 20 71 75 65 72  he last two quer
29b0: 69 65 73 20 74 61 6b 65 20 74 68 65 20 73 61 6d  ies take the sam
29c0: 65 20 61 6d 6f 75 6e 74 20 6f 66 20 74 69 6d 65  e amount of time
29d0: 2c 20 69 6e 20 6f 75 72 20 65 78 61 6d 70 6c 65  , in our example
29e0: 2e 0a 53 6f 20 77 68 69 63 68 20 69 6e 64 65 78  ..So which index
29f0: 2c 20 49 64 78 31 20 6f 72 20 49 64 78 32 2c 20  , Idx1 or Idx2, 
2a00: 77 69 6c 6c 20 53 51 4c 69 74 65 20 63 68 6f 6f  will SQLite choo
2a10: 73 65 3f 20 20 49 66 20 74 68 65 0a 5b 41 4e 41  se?  If the.[ANA
2a20: 4c 59 5a 45 5d 20 63 6f 6d 6d 61 6e 64 20 68 61  LYZE] command ha
2a30: 73 20 62 65 65 6e 20 72 75 6e 20 6f 6e 20 74 68  s been run on th
2a40: 65 20 64 61 74 61 62 61 73 65 2c 20 73 6f 20 74  e database, so t
2a50: 68 61 74 20 53 51 4c 69 74 65 20 68 61 73 0a 68  hat SQLite has.h
2a60: 61 64 20 61 6e 20 6f 70 70 6f 72 74 75 6e 69 74  ad an opportunit
2a70: 79 20 74 6f 20 67 61 74 68 65 72 20 73 74 61 74  y to gather stat
2a80: 69 73 74 69 63 73 20 61 62 6f 75 74 20 74 68 65  istics about the
2a90: 20 61 76 61 69 6c 61 62 6c 65 20 69 6e 64 69 63   available indic
2aa0: 65 73 2c 0a 74 68 65 6e 20 53 51 4c 69 74 65 20  es,.then SQLite 
2ab0: 77 69 6c 6c 20 6b 6e 6f 77 20 74 68 61 74 20 74  will know that t
2ac0: 68 65 20 49 64 78 31 20 69 6e 64 65 78 20 75 73  he Idx1 index us
2ad0: 75 61 6c 6c 79 20 6e 61 72 72 6f 77 73 20 74 68  ually narrows th
2ae0: 65 20 73 65 61 72 63 68 0a 64 6f 77 6e 20 74 6f  e search.down to
2af0: 20 61 20 73 69 6e 67 6c 65 20 69 74 65 6d 20 28   a single item (
2b00: 6f 75 72 20 65 78 61 6d 70 6c 65 20 6f 66 20 66  our example of f
2b10: 72 75 69 74 3d 27 4f 72 61 6e 67 65 27 20 69 73  ruit='Orange' is
2b20: 20 74 68 65 20 65 78 63 65 70 74 69 6f 6e 0a 74   the exception.t
2b30: 6f 20 74 68 69 73 20 72 75 6c 65 29 20 77 68 65  o this rule) whe
2b40: 72 65 61 73 20 74 68 65 20 49 64 78 32 20 69 6e  reas the Idx2 in
2b50: 64 65 78 20 77 69 6c 6c 20 6e 6f 72 6d 61 6c 6c  dex will normall
2b60: 79 20 6f 6e 6c 79 20 6e 61 72 72 6f 77 20 74 68  y only narrow th
2b70: 65 20 0a 73 65 61 72 63 68 20 64 6f 77 6e 20 74  e .search down t
2b80: 6f 20 74 77 6f 20 72 6f 77 73 2e 20 20 53 6f 2c  o two rows.  So,
2b90: 20 69 66 20 61 6c 6c 20 65 6c 73 65 20 69 73 20   if all else is 
2ba0: 65 71 75 61 6c 2c 20 53 51 4c 69 74 65 20 77 69  equal, SQLite wi
2bb0: 6c 6c 0a 63 68 6f 6f 73 65 20 49 64 78 31 20 77  ll.choose Idx1 w
2bc0: 69 74 68 20 74 68 65 20 68 6f 70 65 20 6f 66 20  ith the hope of 
2bd0: 6e 61 72 72 6f 77 69 6e 67 20 74 68 65 20 73 65  narrowing the se
2be0: 61 72 63 68 20 74 6f 20 61 73 20 73 6d 61 6c 6c  arch to as small
2bf0: 0a 61 20 6e 75 6d 62 65 72 20 6f 66 20 72 6f 77  .a number of row
2c00: 73 20 61 73 20 70 6f 73 73 69 62 6c 65 2e 20 20  s as possible.  
2c10: 54 68 69 73 20 63 68 6f 69 63 65 20 69 73 20 6f  This choice is o
2c20: 6e 6c 79 20 70 6f 73 73 69 62 6c 65 20 62 65 63  nly possible bec
2c30: 61 75 73 65 0a 6f 66 20 74 68 65 20 73 74 61 74  ause.of the stat
2c40: 69 73 74 69 63 73 20 70 72 6f 76 69 64 65 64 20  istics provided 
2c50: 62 79 20 5b 41 4e 41 4c 59 5a 45 5d 2e 20 20 49  by [ANALYZE].  I
2c60: 66 20 5b 41 4e 41 4c 59 5a 45 5d 20 68 61 73 20  f [ANALYZE] has 
2c70: 6e 6f 74 20 62 65 65 6e 0a 72 75 6e 20 74 68 65  not been.run the
2c80: 6e 20 74 68 65 20 63 68 6f 69 63 65 20 6f 66 20  n the choice of 
2c90: 77 68 69 63 68 20 69 6e 64 65 78 20 74 6f 20 75  which index to u
2ca0: 73 65 20 69 73 20 61 72 62 69 74 72 61 72 79 2e  se is arbitrary.
2cb0: 0a 3c 2f 70 3e 0a 0a 3c 68 33 3e 31 2e 36 20 4d  .</p>..<h3>1.6 M
2cc0: 75 6c 74 69 2d 43 6f 6c 75 6d 6e 20 49 6e 64 69  ulti-Column Indi
2cd0: 63 65 73 3c 2f 68 33 3e 0a 0a 3c 70 3e 0a 54 6f  ces</h3>..<p>.To
2ce0: 20 67 65 74 20 74 68 65 20 6d 61 78 69 6d 75 6d   get the maximum
2cf0: 20 70 65 72 66 6f 72 6d 61 6e 63 65 20 6f 75 74   performance out
2d00: 20 6f 66 20 61 20 71 75 65 72 79 20 77 69 74 68   of a query with
2d10: 20 6d 75 6c 74 69 70 6c 65 20 41 4e 44 2d 63 6f   multiple AND-co
2d20: 6e 6e 65 63 74 65 64 0a 74 65 72 6d 73 20 69 6e  nnected.terms in
2d30: 20 74 68 65 20 57 48 45 52 45 20 63 6c 61 75 73   the WHERE claus
2d40: 65 2c 20 79 6f 75 20 72 65 61 6c 6c 79 20 77 61  e, you really wa
2d50: 6e 74 20 61 20 6d 75 6c 74 69 2d 63 6f 6c 75 6d  nt a multi-colum
2d60: 6e 20 69 6e 64 65 78 20 77 69 74 68 0a 63 6f 6c  n index with.col
2d70: 75 6d 6e 73 20 66 6f 72 20 65 61 63 68 20 6f 66  umns for each of
2d80: 20 74 68 65 20 41 4e 44 20 74 65 72 6d 73 2e 20   the AND terms. 
2d90: 20 49 6e 20 74 68 69 73 20 63 61 73 65 20 77 65   In this case we
2da0: 20 63 72 65 61 74 65 20 61 20 6e 65 77 20 69 6e   create a new in
2db0: 64 65 78 0a 6f 6e 20 74 68 65 20 22 66 72 75 69  dex.on the "frui
2dc0: 74 22 20 61 6e 64 20 22 73 74 61 74 65 22 20 63  t" and "state" c
2dd0: 6f 6c 75 6d 6e 73 20 6f 66 20 46 72 75 69 74 73  olumns of Fruits
2de0: 46 6f 72 53 61 6c 65 3a 0a 3c 2f 70 3e 0a 0a 3c  ForSale:.</p>..<
2df0: 74 63 6c 3e 0a 63 6f 64 65 20 7b 43 52 45 41 54  tcl>.code {CREAT
2e00: 45 20 49 4e 44 45 58 20 49 64 78 33 20 4f 4e 20  E INDEX Idx3 ON 
2e10: 46 72 75 69 74 73 46 6f 72 53 61 6c 65 28 66 72  FruitsForSale(fr
2e20: 75 69 74 2c 20 73 74 61 74 65 29 3b 7d 0a 66 69  uit, state);}.fi
2e30: 67 75 72 65 20 31 20 23 66 69 67 31 30 20 69 64  gure 1 #fig10 id
2e40: 78 33 2e 67 69 66 20 7b 41 20 54 77 6f 2d 43 6f  x3.gif {A Two-Co
2e50: 6c 75 6d 6e 20 49 6e 64 65 78 7d 0a 3c 2f 74 63  lumn Index}.</tc
2e60: 6c 3e 0a 0a 3c 70 3e 0a 41 20 6d 75 6c 74 69 2d  l>..<p>.A multi-
2e70: 63 6f 6c 75 6d 6e 20 69 6e 64 65 78 20 66 6f 6c  column index fol
2e80: 6c 6f 77 73 20 74 68 65 20 73 61 6d 65 20 70 61  lows the same pa
2e90: 74 74 65 72 6e 20 61 73 20 61 20 73 69 6e 67 6c  ttern as a singl
2ea0: 65 2d 63 6f 6c 75 6d 6e 20 69 6e 64 65 78 3b 0a  e-column index;.
2eb0: 74 68 65 20 69 6e 64 65 78 65 64 20 63 6f 6c 75  the indexed colu
2ec0: 6d 6e 73 20 61 72 65 20 61 64 64 65 64 20 69 6e  mns are added in
2ed0: 20 66 72 6f 6e 74 20 6f 66 20 74 68 65 20 72 6f   front of the ro
2ee0: 77 69 64 2e 20 20 54 68 65 20 6f 6e 6c 79 20 64  wid.  The only d
2ef0: 69 66 66 65 72 65 6e 63 65 0a 69 73 20 74 68 61  ifference.is tha
2f00: 74 20 6e 6f 77 20 6d 75 6c 74 69 70 6c 65 20 63  t now multiple c
2f10: 6f 6c 75 6d 6e 73 20 61 72 65 20 61 64 64 65 64  olumns are added
2f20: 2e 20 20 54 68 65 20 6c 65 66 74 2d 6d 6f 73 74  .  The left-most
2f30: 20 63 6f 6c 75 6d 6e 20 69 73 20 74 68 65 0a 70   column is the.p
2f40: 72 69 6d 61 72 79 20 6b 65 79 20 75 73 65 64 20  rimary key used 
2f50: 66 6f 72 20 6f 72 64 65 72 69 6e 67 20 74 68 65  for ordering the
2f60: 20 72 6f 77 73 20 69 6e 20 74 68 65 20 69 6e 64   rows in the ind
2f70: 65 78 2e 20 20 54 68 65 20 73 65 63 6f 6e 64 20  ex.  The second 
2f80: 63 6f 6c 75 6d 6e 20 69 73 0a 75 73 65 64 20 74  column is.used t
2f90: 6f 20 62 72 65 61 6b 20 74 69 65 73 20 69 6e 20  o break ties in 
2fa0: 74 68 65 20 6c 65 66 74 2d 6d 6f 73 74 20 63 6f  the left-most co
2fb0: 6c 75 6d 6e 2e 20 20 49 66 20 74 68 65 72 65 20  lumn.  If there 
2fc0: 77 65 72 65 20 61 20 74 68 69 72 64 20 63 6f 6c  were a third col
2fd0: 75 6d 6e 2c 0a 69 74 20 77 6f 75 6c 64 20 62 65  umn,.it would be
2fe0: 20 75 73 65 64 20 74 6f 20 62 72 65 61 6b 20 74   used to break t
2ff0: 69 65 73 20 66 6f 72 20 74 68 65 20 66 69 72 73  ies for the firs
3000: 74 20 74 77 6f 20 63 6f 6c 75 6d 6e 73 2e 20 20  t two columns.  
3010: 41 6e 64 20 73 6f 20 66 6f 72 74 68 20 66 6f 72  And so forth for
3020: 0a 61 6c 6c 20 63 6f 6c 75 6d 6e 73 20 69 6e 20  .all columns in 
3030: 74 68 65 20 69 6e 64 65 78 2e 20 20 42 65 63 61  the index.  Beca
3040: 75 73 65 20 72 6f 77 69 64 20 69 73 20 67 75 61  use rowid is gua
3050: 72 61 6e 74 65 65 64 0a 74 6f 20 62 65 20 75 6e  ranteed.to be un
3060: 69 71 75 65 2c 20 65 76 65 72 79 20 72 6f 77 20  ique, every row 
3070: 6f 66 20 74 68 65 20 69 6e 64 65 78 20 77 69 6c  of the index wil
3080: 6c 20 62 65 20 75 6e 69 71 75 65 20 65 76 65 6e  l be unique even
3090: 20 69 66 20 61 6c 6c 20 6f 66 20 74 68 65 0a 63   if all of the.c
30a0: 6f 6e 74 65 6e 74 20 63 6f 6c 75 6d 6e 73 20 66  ontent columns f
30b0: 6f 72 20 74 77 6f 20 72 6f 77 73 20 61 72 65 20  or two rows are 
30c0: 74 68 65 20 73 61 6d 65 2e 20 20 54 68 61 74 20  the same.  That 
30d0: 63 61 73 65 20 64 6f 65 73 20 6e 6f 74 20 68 61  case does not ha
30e0: 70 70 65 6e 0a 69 6e 20 6f 75 72 20 73 61 6d 70  ppen.in our samp
30f0: 6c 65 20 64 61 74 61 2c 20 62 75 74 20 74 68 65  le data, but the
3100: 72 65 20 69 73 20 6f 6e 65 20 63 61 73 65 20 28  re is one case (
3110: 66 72 75 69 74 3d 27 4f 72 61 6e 67 65 27 29 20  fruit='Orange') 
3120: 77 68 65 72 65 20 74 68 65 72 65 0a 69 73 20 61  where there.is a
3130: 20 74 69 65 20 6f 6e 20 74 68 65 20 66 69 72 73   tie on the firs
3140: 74 20 63 6f 6c 75 6d 6e 20 77 68 69 63 68 20 6d  t column which m
3150: 75 73 74 20 62 65 20 62 72 6f 6b 65 6e 20 62 79  ust be broken by
3160: 20 74 68 65 20 73 65 63 6f 6e 64 20 63 6f 6c 75   the second colu
3170: 6d 6e 2e 0a 3c 2f 70 3e 0a 0a 3c 70 3e 0a 47 69  mn..</p>..<p>.Gi
3180: 76 65 6e 20 74 68 65 20 6e 65 77 20 6d 75 6c 74  ven the new mult
3190: 69 2d 63 6f 6c 75 6d 6e 20 49 64 78 33 20 69 6e  i-column Idx3 in
31a0: 64 65 78 2c 20 69 74 20 69 73 20 6e 6f 77 20 70  dex, it is now p
31b0: 6f 73 73 69 62 6c 65 20 66 6f 72 20 53 51 4c 69  ossible for SQLi
31c0: 74 65 0a 74 6f 20 66 69 6e 64 20 74 68 65 20 70  te.to find the p
31d0: 72 69 63 65 20 6f 66 20 43 61 6c 69 66 6f 72 6e  rice of Californ
31e0: 69 61 20 6f 72 61 6e 67 65 73 20 75 73 69 6e 67  ia oranges using
31f0: 20 6f 6e 6c 79 20 32 20 62 69 6e 61 72 79 20 73   only 2 binary s
3200: 65 61 72 63 68 65 73 3a 0a 3c 2f 70 3e 0a 0a 3c  earches:.</p>..<
3210: 74 63 6c 3e 0a 63 6f 64 65 20 7b 53 45 4c 45 43  tcl>.code {SELEC
3220: 54 20 70 72 69 63 65 20 46 52 4f 4d 20 66 72 75  T price FROM fru
3230: 69 74 73 66 6f 72 73 61 6c 65 20 57 48 45 52 45  itsforsale WHERE
3240: 20 66 72 75 69 74 3d 27 4f 72 61 6e 67 65 27 20   fruit='Orange' 
3250: 41 4e 44 20 73 74 61 74 65 3d 27 43 41 27 7d 0a  AND state='CA'}.
3260: 66 69 67 75 72 65 20 31 31 20 23 66 69 67 31 31  figure 11 #fig11
3270: 20 69 64 78 33 6c 75 31 2e 67 69 66 20 7b 4c 6f   idx3lu1.gif {Lo
3280: 6f 6b 75 70 20 55 73 69 6e 67 20 41 20 54 77 6f  okup Using A Two
3290: 2d 43 6f 6c 75 6d 6e 20 49 6e 64 65 78 7d 0a 3c  -Column Index}.<
32a0: 2f 74 63 6c 3e 0a 0a 3c 70 3e 0a 57 69 74 68 20  /tcl>..<p>.With 
32b0: 74 68 65 20 49 64 78 33 20 69 6e 64 65 78 20 6f  the Idx3 index o
32c0: 6e 20 62 6f 74 68 20 63 6f 6c 75 6d 6e 73 20 74  n both columns t
32d0: 68 61 74 20 61 72 65 20 63 6f 6e 73 74 72 61 69  hat are constrai
32e0: 6e 65 64 20 62 79 20 74 68 65 20 57 48 45 52 45  ned by the WHERE
32f0: 20 63 6c 61 75 73 65 2c 0a 53 51 4c 69 74 65 20   clause,.SQLite 
3300: 63 61 6e 20 64 6f 20 61 20 73 69 6e 67 6c 65 20  can do a single 
3310: 62 69 6e 61 72 79 20 73 65 61 72 63 68 20 61 67  binary search ag
3320: 61 69 6e 73 74 20 49 64 78 33 20 74 6f 20 66 69  ainst Idx3 to fi
3330: 6e 64 20 74 68 65 20 6f 6e 65 20 72 6f 77 69 64  nd the one rowid
3340: 0a 66 6f 72 20 43 61 6c 69 66 6f 72 6e 69 61 20  .for California 
3350: 6f 72 61 6e 67 65 73 2c 20 74 68 65 6e 20 64 6f  oranges, then do
3360: 20 61 20 73 69 6e 67 6c 65 20 62 69 6e 61 72 79   a single binary
3370: 20 73 65 61 72 63 68 20 74 6f 20 66 69 6e 64 20   search to find 
3380: 74 68 65 20 70 72 69 63 65 0a 66 6f 72 20 74 68  the price.for th
3390: 61 74 20 69 74 65 6d 20 69 6e 20 74 68 65 20 6f  at item in the o
33a0: 72 69 67 69 6e 61 6c 20 74 61 62 6c 65 2e 20 20  riginal table.  
33b0: 54 68 65 72 65 20 61 72 65 20 6e 6f 20 64 65 61  There are no dea
33c0: 64 2d 65 6e 64 73 20 61 6e 64 20 6e 6f 0a 77 61  d-ends and no.wa
33d0: 73 74 65 64 20 62 69 6e 61 72 79 20 73 65 61 72  sted binary sear
33e0: 63 68 65 73 2e 20 20 54 68 69 73 20 69 73 20 61  ches.  This is a
33f0: 20 6d 6f 72 65 20 65 66 66 69 63 69 65 6e 74 20   more efficient 
3400: 71 75 65 72 79 2e 0a 3c 2f 70 3e 0a 0a 3c 70 3e  query..</p>..<p>
3410: 0a 4e 6f 74 65 20 74 68 61 74 20 49 64 78 33 20  .Note that Idx3 
3420: 63 6f 6e 74 61 69 6e 73 20 61 6c 6c 20 74 68 65  contains all the
3430: 20 73 61 6d 65 20 69 6e 66 6f 72 6d 61 74 69 6f   same informatio
3440: 6e 20 61 73 20 74 68 65 20 6f 72 69 67 69 6e 61  n as the origina
3450: 6c 20 0a 3c 61 20 68 72 65 66 3d 22 23 66 69 67  l .<a href="#fig
3460: 33 22 3e 49 64 78 31 3c 2f 61 3e 2e 20 20 41 6e  3">Idx1</a>.  An
3470: 64 20 73 6f 20 69 66 20 77 65 20 68 61 76 65 20  d so if we have 
3480: 49 64 78 33 2c 20 77 65 20 64 6f 20 6e 6f 74 20  Idx3, we do not 
3490: 72 65 61 6c 6c 79 20 6e 65 65 64 20 49 64 78 31  really need Idx1
34a0: 0a 61 6e 79 20 6d 6f 72 65 2e 20 20 54 68 65 20  .any more.  The 
34b0: 22 70 72 69 63 65 20 6f 66 20 70 65 61 63 68 65  "price of peache
34c0: 73 22 20 71 75 65 72 79 20 63 61 6e 20 62 65 20  s" query can be 
34d0: 73 61 74 69 73 66 69 65 64 20 75 73 69 6e 67 20  satisfied using 
34e0: 49 64 78 33 0a 62 79 20 73 69 6d 70 6c 79 20 69  Idx3.by simply i
34f0: 67 6e 6f 72 69 6e 67 20 74 68 65 20 22 73 74 61  gnoring the "sta
3500: 74 65 22 20 63 6f 6c 75 6d 6e 20 6f 66 20 49 64  te" column of Id
3510: 78 33 3a 0a 3c 2f 70 3e 0a 0a 3c 74 63 6c 3e 0a  x3:.</p>..<tcl>.
3520: 63 6f 64 65 20 7b 53 45 4c 45 43 54 20 70 72 69  code {SELECT pri
3530: 63 65 20 46 52 4f 4d 20 66 72 75 69 74 73 66 6f  ce FROM fruitsfo
3540: 72 73 61 6c 65 20 57 48 45 52 45 20 66 72 75 69  rsale WHERE frui
3550: 74 3d 27 50 65 61 63 68 27 7d 0a 66 69 67 75 72  t='Peach'}.figur
3560: 65 20 31 32 20 23 66 69 67 31 32 20 69 64 78 33  e 12 #fig12 idx3
3570: 6c 75 32 2e 67 69 66 20 7b 53 69 6e 67 6c 65 2d  lu2.gif {Single-
3580: 43 6f 6c 75 6d 6e 20 4c 6f 6f 6b 75 70 20 4f 6e  Column Lookup On
3590: 20 41 20 4d 75 6c 74 69 2d 43 6f 6c 75 6d 6e 20   A Multi-Column 
35a0: 49 6e 64 65 78 7d 0a 3c 2f 74 63 6c 3e 0a 0a 3c  Index}.</tcl>..<
35b0: 70 3e 0a 48 65 6e 63 65 2c 20 61 20 67 6f 6f 64  p>.Hence, a good
35c0: 20 72 75 6c 65 20 6f 66 20 74 68 75 6d 62 20 69   rule of thumb i
35d0: 73 20 74 68 61 74 20 79 6f 75 72 20 64 61 74 61  s that your data
35e0: 62 61 73 65 20 73 63 68 65 6d 61 20 73 68 6f 75  base schema shou
35f0: 6c 64 20 6e 65 76 65 72 0a 63 6f 6e 74 61 69 6e  ld never.contain
3600: 20 74 77 6f 20 69 6e 64 69 63 65 73 20 77 68 65   two indices whe
3610: 72 65 20 6f 6e 65 20 69 6e 64 65 78 20 69 73 20  re one index is 
3620: 61 20 70 72 65 66 69 78 20 6f 66 20 74 68 65 20  a prefix of the 
3630: 6f 74 68 65 72 2e 20 20 44 72 6f 70 20 74 68 65  other.  Drop the
3640: 0a 69 6e 64 65 78 20 77 69 74 68 20 66 65 77 65  .index with fewe
3650: 72 20 63 6f 6c 75 6d 6e 73 2e 20 20 53 51 4c 69  r columns.  SQLi
3660: 74 65 20 77 69 6c 6c 20 73 74 69 6c 6c 20 62 65  te will still be
3670: 20 61 62 6c 65 20 74 6f 20 64 6f 20 65 66 66 69   able to do effi
3680: 63 69 65 6e 74 0a 6c 6f 6f 6b 75 70 73 20 77 69  cient.lookups wi
3690: 74 68 20 74 68 65 20 6c 6f 6e 67 65 72 20 69 6e  th the longer in
36a0: 64 65 78 2e 0a 3c 2f 70 3e 0a 0a 3c 74 63 6c 3e  dex..</p>..<tcl>
36b0: 68 64 5f 66 72 61 67 6d 65 6e 74 20 63 6f 76 69  hd_fragment covi
36c0: 64 78 20 7b 63 6f 76 65 72 69 6e 67 20 69 6e 64  dx {covering ind
36d0: 65 78 7d 20 7b 63 6f 76 65 72 69 6e 67 20 69 6e  ex} {covering in
36e0: 64 69 63 65 73 7d 3c 2f 74 63 6c 3e 0a 3c 68 33  dices}</tcl>.<h3
36f0: 3e 31 2e 37 20 43 6f 76 65 72 69 6e 67 20 49 6e  >1.7 Covering In
3700: 64 69 63 65 73 3c 2f 68 33 3e 0a 0a 3c 70 3e 0a  dices</h3>..<p>.
3710: 54 68 65 20 22 70 72 69 63 65 20 6f 66 20 43 61  The "price of Ca
3720: 6c 69 66 6f 72 6e 69 61 20 6f 72 61 6e 67 65 73  lifornia oranges
3730: 22 20 71 75 65 72 79 20 77 61 73 20 6d 61 64 65  " query was made
3740: 20 6d 6f 72 65 20 65 66 66 69 63 69 65 6e 74 20   more efficient 
3750: 74 68 72 6f 75 67 68 0a 74 68 65 20 75 73 65 20  through.the use 
3760: 6f 66 20 61 20 74 77 6f 2d 63 6f 6c 75 6d 6e 20  of a two-column 
3770: 69 6e 64 65 78 2e 20 20 42 75 74 20 53 51 4c 69  index.  But SQLi
3780: 74 65 20 63 61 6e 20 64 6f 20 65 76 65 6e 20 62  te can do even b
3790: 65 74 74 65 72 20 77 69 74 68 20 61 0a 74 68 72  etter with a.thr
37a0: 65 65 2d 63 6f 6c 75 6d 6e 20 69 6e 64 65 78 20  ee-column index 
37b0: 74 68 61 74 20 61 6c 73 6f 20 69 6e 63 6c 75 64  that also includ
37c0: 65 73 20 74 68 65 20 22 70 72 69 63 65 22 20 63  es the "price" c
37d0: 6f 6c 75 6d 6e 3a 0a 3c 2f 70 3e 0a 0a 3c 74 63  olumn:.</p>..<tc
37e0: 6c 3e 0a 63 6f 64 65 20 7b 43 52 45 41 54 45 20  l>.code {CREATE 
37f0: 49 4e 44 45 58 20 49 64 78 34 20 4f 4e 20 46 72  INDEX Idx4 ON Fr
3800: 75 69 74 73 46 6f 72 53 61 6c 65 28 66 72 75 69  uitsForSale(frui
3810: 74 2c 20 73 74 61 74 65 2c 20 70 72 69 63 65 29  t, state, price)
3820: 3b 7d 0a 66 69 67 75 72 65 20 31 33 20 23 66 69  ;}.figure 13 #fi
3830: 67 31 33 20 69 64 78 34 2e 67 69 66 20 7b 41 20  g13 idx4.gif {A 
3840: 43 6f 76 65 72 69 6e 67 20 49 6e 64 65 78 7d 0a  Covering Index}.
3850: 3c 2f 74 63 6c 3e 0a 0a 3c 70 3e 0a 54 68 69 73  </tcl>..<p>.This
3860: 20 6e 65 77 20 69 6e 64 65 78 20 63 6f 6e 74 61   new index conta
3870: 69 6e 73 20 61 6c 6c 20 74 68 65 20 63 6f 6c 75  ins all the colu
3880: 6d 6e 73 20 6f 66 20 74 68 65 20 6f 72 69 67 69  mns of the origi
3890: 6e 61 6c 20 46 72 75 69 74 73 46 6f 72 53 61 6c  nal FruitsForSal
38a0: 65 20 74 61 62 6c 65 20 74 68 61 74 0a 61 72 65  e table that.are
38b0: 20 75 73 65 64 20 62 79 20 74 68 65 20 71 75 65   used by the que
38c0: 72 79 20 2d 20 62 6f 74 68 20 74 68 65 20 73 65  ry - both the se
38d0: 61 72 63 68 20 74 65 72 6d 73 20 61 6e 64 20 74  arch terms and t
38e0: 68 65 20 6f 75 74 70 75 74 2e 20 20 57 65 20 63  he output.  We c
38f0: 61 6c 6c 0a 74 68 69 73 20 61 20 22 63 6f 76 65  all.this a "cove
3900: 72 69 6e 67 20 69 6e 64 65 78 22 2e 20 20 42 65  ring index".  Be
3910: 63 61 75 73 65 20 61 6c 6c 20 6f 66 20 74 68 65  cause all of the
3920: 20 69 6e 66 6f 72 6d 61 74 69 6f 6e 20 6e 65 65   information nee
3930: 64 65 64 20 69 73 20 69 6e 0a 74 68 65 20 63 6f  ded is in.the co
3940: 76 65 72 69 6e 67 20 69 6e 64 65 78 2c 20 53 51  vering index, SQ
3950: 4c 69 74 65 20 6e 65 76 65 72 20 6e 65 65 64 73  Lite never needs
3960: 20 74 6f 20 63 6f 6e 73 75 6c 74 20 74 68 65 20   to consult the 
3970: 6f 72 69 67 69 6e 61 6c 20 74 61 62 6c 65 0a 69  original table.i
3980: 6e 20 6f 72 64 65 72 20 74 6f 20 66 69 6e 64 20  n order to find 
3990: 74 68 65 20 70 72 69 63 65 2e 0a 3c 2f 70 3e 0a  the price..</p>.
39a0: 0a 3c 74 63 6c 3e 0a 63 6f 64 65 20 7b 53 45 4c  .<tcl>.code {SEL
39b0: 45 43 54 20 70 72 69 63 65 20 46 52 4f 4d 20 66  ECT price FROM f
39c0: 72 75 69 74 73 66 6f 72 73 61 6c 65 20 57 48 45  ruitsforsale WHE
39d0: 52 45 20 66 72 75 69 74 3d 27 4f 72 61 6e 67 65  RE fruit='Orange
39e0: 27 20 41 4e 44 20 73 74 61 74 65 3d 27 43 41 27  ' AND state='CA'
39f0: 3b 7d 0a 66 69 67 75 72 65 20 31 34 20 23 66 69  ;}.figure 14 #fi
3a00: 67 31 34 20 69 64 78 34 6c 75 31 2e 67 69 66 20  g14 idx4lu1.gif 
3a10: 7b 51 75 65 72 79 20 55 73 69 6e 67 20 41 20 43  {Query Using A C
3a20: 6f 76 65 72 69 6e 67 20 49 6e 64 65 78 7d 0a 3c  overing Index}.<
3a30: 2f 74 63 6c 3e 0a 0a 3c 70 3e 0a 48 65 6e 63 65  /tcl>..<p>.Hence
3a40: 2c 20 62 79 20 61 64 64 69 6e 67 20 65 78 74 72  , by adding extr
3a50: 61 20 22 6f 75 74 70 75 74 22 20 63 6f 6c 75 6d  a "output" colum
3a60: 6e 73 20 6f 6e 74 6f 20 74 68 65 20 65 6e 64 20  ns onto the end 
3a70: 6f 66 20 61 6e 20 69 6e 64 65 78 2c 20 6f 6e 65  of an index, one
3a80: 0a 63 61 6e 20 61 76 6f 69 64 20 68 61 76 69 6e  .can avoid havin
3a90: 67 20 74 6f 20 72 65 66 65 72 65 6e 63 65 20 74  g to reference t
3aa0: 68 65 20 6f 72 69 67 69 6e 61 6c 20 74 61 62 6c  he original tabl
3ab0: 65 20 61 6e 64 20 74 68 65 72 65 62 79 0a 63 75  e and thereby.cu
3ac0: 74 20 74 68 65 20 6e 75 6d 62 65 72 20 6f 66 20  t the number of 
3ad0: 62 69 6e 61 72 79 20 73 65 61 72 63 68 65 73 20  binary searches 
3ae0: 66 6f 72 20 61 20 71 75 65 72 79 20 69 6e 20 68  for a query in h
3af0: 61 6c 66 2e 20 20 54 68 69 73 20 69 73 20 61 0a  alf.  This is a.
3b00: 63 6f 6e 73 74 61 6e 74 2d 66 61 63 74 6f 72 20  constant-factor 
3b10: 69 6d 70 72 6f 76 65 6d 65 6e 74 20 69 6e 20 70  improvement in p
3b20: 65 72 66 6f 72 6d 61 6e 63 65 20 28 72 6f 75 67  erformance (roug
3b30: 68 6c 79 20 61 20 64 6f 75 62 6c 69 6e 67 20 6f  hly a doubling o
3b40: 66 0a 74 68 65 20 73 70 65 65 64 29 2e 20 20 42  f.the speed).  B
3b50: 75 74 20 6f 6e 20 74 68 65 20 6f 74 68 65 72 20  ut on the other 
3b60: 68 61 6e 64 2c 20 69 74 20 69 73 20 61 6c 73 6f  hand, it is also
3b70: 20 6a 75 73 74 20 61 20 72 65 66 69 6e 65 6d 65   just a refineme
3b80: 6e 74 3b 0a 41 20 74 77 6f 2d 66 6f 6c 64 20 70  nt;.A two-fold p
3b90: 65 72 66 6f 72 6d 61 6e 63 65 20 69 6e 63 72 65  erformance incre
3ba0: 61 73 65 20 69 73 20 6e 6f 74 20 6e 65 61 72 6c  ase is not nearl
3bb0: 79 20 61 73 20 64 72 61 6d 61 74 69 63 20 61 73  y as dramatic as
3bc0: 20 74 68 65 0a 6f 6e 65 2d 6d 69 6c 6c 69 6f 6e   the.one-million
3bd0: 2d 66 6f 6c 64 20 69 6e 63 72 65 61 73 65 20 73  -fold increase s
3be0: 65 65 6e 20 77 68 65 6e 20 74 68 65 20 74 61 62  een when the tab
3bf0: 6c 65 20 77 61 73 20 66 69 72 73 74 20 69 6e 64  le was first ind
3c00: 65 78 65 64 2e 0a 41 6e 64 20 66 6f 72 20 6d 6f  exed..And for mo
3c10: 73 74 20 71 75 65 72 69 65 73 2c 20 74 68 65 20  st queries, the 
3c20: 64 69 66 66 65 72 65 6e 63 65 20 62 65 74 77 65  difference betwe
3c30: 65 6e 20 31 20 6d 69 63 72 6f 73 65 63 6f 6e 64  en 1 microsecond
3c40: 20 61 6e 64 0a 32 20 6d 69 63 72 6f 73 65 63 6f   and.2 microseco
3c50: 6e 64 73 20 69 73 20 75 6e 6c 69 6b 65 6c 79 20  nds is unlikely 
3c60: 74 6f 20 62 65 20 6e 6f 74 69 63 65 64 2e 0a 3c  to be noticed..<
3c70: 2f 70 3e 0a 0a 3c 74 63 6c 3e 68 64 5f 66 72 61  /p>..<tcl>hd_fra
3c80: 67 6d 65 6e 74 20 6f 72 5f 69 6e 5f 77 68 65 72  gment or_in_wher
3c90: 65 20 6f 72 2d 63 6f 6e 6e 65 63 74 65 64 2d 74  e or-connected-t
3ca0: 65 72 6d 73 3c 2f 74 63 6c 3e 0a 3c 68 33 3e 31  erms</tcl>.<h3>1
3cb0: 2e 38 20 4f 52 2d 43 6f 6e 6e 65 63 74 65 64 20  .8 OR-Connected 
3cc0: 54 65 72 6d 73 20 49 6e 20 54 68 65 20 57 48 45  Terms In The WHE
3cd0: 52 45 20 43 6c 61 75 73 65 3c 2f 68 33 3e 0a 0a  RE Clause</h3>..
3ce0: 3c 70 3e 0a 4d 75 6c 74 69 2d 63 6f 6c 75 6d 6e  <p>.Multi-column
3cf0: 20 69 6e 64 69 63 65 73 20 6f 6e 6c 79 20 77 6f   indices only wo
3d00: 72 6b 20 69 66 20 74 68 65 20 63 6f 6e 73 74 72  rk if the constr
3d10: 61 69 6e 74 20 74 65 72 6d 73 20 69 6e 20 74 68  aint terms in th
3d20: 65 20 57 48 45 52 45 0a 63 6c 61 75 73 65 20 6f  e WHERE.clause o
3d30: 66 20 74 68 65 20 71 75 65 72 79 20 61 72 65 20  f the query are 
3d40: 63 6f 6e 6e 65 63 74 65 64 20 62 79 20 41 4e 44  connected by AND
3d50: 2e 0a 53 6f 20 49 64 78 33 20 61 6e 64 20 49 64  ..So Idx3 and Id
3d60: 78 34 20 61 72 65 20 68 65 6c 70 66 75 6c 20 77  x4 are helpful w
3d70: 68 65 6e 20 74 68 65 20 73 65 61 72 63 68 20 69  hen the search i
3d80: 73 20 66 6f 72 20 69 74 65 6d 73 20 74 68 61 74  s for items that
3d90: 0a 61 72 65 20 62 6f 74 68 20 4f 72 61 6e 67 65  .are both Orange
3da0: 73 20 61 6e 64 20 67 72 6f 77 6e 20 69 6e 20 43  s and grown in C
3db0: 61 6c 69 66 6f 72 6e 69 61 2c 20 62 75 74 20 6e  alifornia, but n
3dc0: 65 69 74 68 65 72 20 69 6e 64 65 78 20 77 6f 75  either index wou
3dd0: 6c 64 0a 62 65 20 74 68 61 74 20 75 73 65 66 75  ld.be that usefu
3de0: 6c 20 69 66 20 77 65 20 77 61 6e 74 65 64 20 61  l if we wanted a
3df0: 6c 6c 20 69 74 65 6d 73 20 74 68 61 74 20 77 65  ll items that we
3e00: 72 65 20 65 69 74 68 65 72 20 6f 72 61 6e 67 65  re either orange
3e10: 73 0a 3c 69 3e 6f 72 3c 2f 69 3e 20 61 72 65 20  s.<i>or</i> are 
3e20: 67 72 6f 77 6e 20 69 6e 20 43 61 6c 69 66 6f 72  grown in Califor
3e30: 6e 69 61 2e 0a 3c 2f 70 3e 0a 0a 3c 74 63 6c 3e  nia..</p>..<tcl>
3e40: 63 6f 64 65 20 7b 0a 53 45 4c 45 43 54 20 70 72  code {.SELECT pr
3e50: 69 63 65 20 46 52 4f 4d 20 46 72 75 69 74 73 46  ice FROM FruitsF
3e60: 6f 72 53 61 6c 65 20 57 48 45 52 45 20 66 72 75  orSale WHERE fru
3e70: 69 74 3d 27 4f 72 61 6e 67 65 27 20 4f 52 20 73  it='Orange' OR s
3e80: 74 61 74 65 3d 27 43 41 27 3b 0a 7d 3c 2f 74 63  tate='CA';.}</tc
3e90: 6c 3e 0a 0a 3c 70 3e 0a 57 68 65 6e 20 63 6f 6e  l>..<p>.When con
3ea0: 66 72 6f 6e 74 65 64 20 77 69 74 68 20 4f 52 2d  fronted with OR-
3eb0: 63 6f 6e 6e 65 63 74 65 64 20 74 65 72 6d 73 20  connected terms 
3ec0: 69 6e 20 61 20 57 48 45 52 45 20 63 6c 61 75 73  in a WHERE claus
3ed0: 65 2c 20 53 51 4c 69 74 65 20 0a 65 78 61 6d 69  e, SQLite .exami
3ee0: 6e 65 73 20 65 61 63 68 20 4f 52 20 74 65 72 6d  nes each OR term
3ef0: 20 73 65 70 61 72 61 74 65 6c 79 20 61 6e 64 20   separately and 
3f00: 74 72 69 65 73 20 74 6f 20 75 73 65 20 61 6e 20  tries to use an 
3f10: 69 6e 64 65 78 20 74 6f 0a 66 69 6e 64 20 74 68  index to.find th
3f20: 65 20 72 6f 77 69 64 73 20 61 73 73 6f 63 69 61  e rowids associa
3f30: 74 65 64 20 77 69 74 68 20 65 61 63 68 20 74 65  ted with each te
3f40: 72 6d 2e 0a 49 74 20 74 68 65 6e 20 74 61 6b 65  rm..It then take
3f50: 73 20 74 68 65 20 75 6e 69 6f 6e 20 6f 66 20 74  s the union of t
3f60: 68 65 20 72 65 73 75 6c 74 69 6e 67 20 72 6f 77  he resulting row
3f70: 69 64 20 73 65 74 73 20 74 6f 20 66 69 6e 64 0a  id sets to find.
3f80: 74 68 65 20 65 6e 64 20 72 65 73 75 6c 74 2e 20  the end result. 
3f90: 20 54 68 65 20 66 6f 6c 6c 6f 77 69 6e 67 20 66   The following f
3fa0: 69 67 75 72 65 20 69 6c 6c 75 73 74 72 61 74 65  igure illustrate
3fb0: 73 20 74 68 69 73 20 70 72 6f 63 65 73 73 3a 0a  s this process:.
3fc0: 3c 2f 70 3e 0a 0a 3c 74 63 6c 3e 66 69 67 75 72  </p>..<tcl>figur
3fd0: 65 20 31 35 20 23 66 69 67 31 35 20 6f 72 71 75  e 15 #fig15 orqu
3fe0: 65 72 79 2e 67 69 66 20 7b 51 75 65 72 79 20 57  ery.gif {Query W
3ff0: 69 74 68 20 4f 52 20 43 6f 6e 73 74 72 61 69 6e  ith OR Constrain
4000: 74 73 7d 3c 2f 74 63 6c 3e 0a 0a 3c 70 3e 0a 54  ts}</tcl>..<p>.T
4010: 68 65 20 64 69 61 67 72 61 6d 20 61 62 6f 76 65  he diagram above
4020: 20 69 6d 70 6c 69 65 73 20 74 68 61 74 20 53 51   implies that SQ
4030: 4c 69 74 65 20 63 6f 6d 70 75 74 65 73 20 61 6c  Lite computes al
4040: 6c 20 6f 66 20 74 68 65 20 72 6f 77 69 64 73 20  l of the rowids 
4050: 66 69 72 73 74 0a 61 6e 64 20 74 68 65 6e 20 63  first.and then c
4060: 6f 6d 62 69 6e 65 73 20 74 68 65 6d 20 77 69 74  ombines them wit
4070: 68 20 61 20 75 6e 69 6f 6e 20 6f 70 65 72 61 74  h a union operat
4080: 69 6f 6e 20 62 65 66 6f 72 65 20 73 74 61 72 74  ion before start
4090: 69 6e 67 20 74 6f 20 64 6f 0a 72 6f 77 69 64 20  ing to do.rowid 
40a0: 6c 6f 6f 6b 75 70 73 20 6f 6e 20 74 68 65 20 6f  lookups on the o
40b0: 72 69 67 69 6e 61 6c 20 74 61 62 6c 65 2e 20 20  riginal table.  
40c0: 49 6e 20 72 65 61 6c 69 74 79 2c 20 74 68 65 20  In reality, the 
40d0: 72 6f 77 69 64 20 6c 6f 6f 6b 75 70 73 0a 61 72  rowid lookups.ar
40e0: 65 20 69 6e 74 65 72 73 70 65 72 73 65 64 20 77  e interspersed w
40f0: 69 74 68 20 72 6f 77 69 64 20 63 6f 6d 70 75 74  ith rowid comput
4100: 61 74 69 6f 6e 73 2e 20 20 53 51 4c 69 74 65 20  ations.  SQLite 
4110: 75 73 65 73 20 6f 6e 65 20 69 6e 64 65 78 20 61  uses one index a
4120: 74 0a 61 20 74 69 6d 65 20 74 6f 20 66 69 6e 64  t.a time to find
4130: 20 72 6f 77 69 64 73 20 77 68 69 6c 65 20 72 65   rowids while re
4140: 6d 65 6d 62 65 72 69 6e 67 20 77 68 69 63 68 20  membering which 
4150: 72 6f 77 69 64 73 20 69 74 20 68 61 73 20 73 65  rowids it has se
4160: 65 6e 0a 62 65 66 6f 72 65 20 73 6f 20 61 73 20  en.before so as 
4170: 74 6f 20 61 76 6f 69 64 20 64 75 70 6c 69 63 61  to avoid duplica
4180: 74 65 73 2e 20 20 54 68 61 74 20 69 73 20 6a 75  tes.  That is ju
4190: 73 74 20 61 6e 20 69 6d 70 6c 65 6d 65 6e 74 61  st an implementa
41a0: 74 69 6f 6e 0a 64 65 74 61 69 6c 2c 20 74 68 6f  tion.detail, tho
41b0: 75 67 68 2e 20 20 54 68 65 20 64 69 61 67 72 61  ugh.  The diagra
41c0: 6d 2c 20 77 68 69 6c 65 20 6e 6f 74 20 31 30 30  m, while not 100
41d0: 25 20 61 63 63 75 72 61 74 65 2c 20 70 72 6f 76  % accurate, prov
41e0: 69 64 65 73 20 61 20 67 6f 6f 64 0a 6f 76 65 72  ides a good.over
41f0: 76 69 65 77 20 6f 66 20 77 68 61 74 20 69 73 20  view of what is 
4200: 68 61 70 70 65 6e 69 6e 67 2e 0a 3c 2f 70 3e 0a  happening..</p>.
4210: 0a 3c 70 3e 0a 49 6e 20 6f 72 64 65 72 20 66 6f  .<p>.In order fo
4220: 72 20 74 68 65 20 4f 52 2d 62 79 2d 55 4e 49 4f  r the OR-by-UNIO
4230: 4e 20 74 65 63 68 6e 69 71 75 65 20 73 68 6f 77  N technique show
4240: 6e 20 61 62 6f 76 65 20 74 6f 20 62 65 20 75 73  n above to be us
4250: 65 66 75 6c 2c 20 74 68 65 72 65 0a 6d 75 73 74  eful, there.must
4260: 20 62 65 20 61 6e 20 69 6e 64 65 78 20 61 76 61   be an index ava
4270: 69 6c 61 62 6c 65 20 74 68 61 74 20 68 65 6c 70  ilable that help
4280: 73 20 72 65 73 6f 6c 76 65 20 65 76 65 72 79 20  s resolve every 
4290: 4f 52 2d 63 6f 6e 6e 65 63 74 65 64 20 74 65 72  OR-connected ter
42a0: 6d 0a 69 6e 20 74 68 65 20 57 48 45 52 45 20 63  m.in the WHERE c
42b0: 6c 61 75 73 65 2e 20 20 49 66 20 65 76 65 6e 20  lause.  If even 
42c0: 61 20 73 69 6e 67 6c 65 20 4f 52 2d 63 6f 6e 6e  a single OR-conn
42d0: 65 63 74 65 64 20 74 65 72 6d 20 69 73 20 6e 6f  ected term is no
42e0: 74 20 69 6e 64 65 78 65 64 2c 0a 74 68 65 6e 20  t indexed,.then 
42f0: 61 20 66 75 6c 6c 20 74 61 62 6c 65 20 73 63 61  a full table sca
4300: 6e 20 77 6f 75 6c 64 20 68 61 76 65 20 74 6f 20  n would have to 
4310: 62 65 20 64 6f 6e 65 20 69 6e 20 6f 72 64 65 72  be done in order
4320: 20 74 6f 20 66 69 6e 64 20 74 68 65 20 72 6f 77   to find the row
4330: 69 64 73 0a 67 65 6e 65 72 61 74 65 64 20 62 79  ids.generated by
4340: 20 74 68 65 20 6f 6e 65 20 74 65 72 6d 2c 20 61   the one term, a
4350: 6e 64 20 69 66 20 53 51 4c 69 74 65 20 68 61 73  nd if SQLite has
4360: 20 74 6f 20 64 6f 20 61 20 66 75 6c 6c 20 74 61   to do a full ta
4370: 62 6c 65 20 73 63 61 6e 2c 20 69 74 0a 6d 69 67  ble scan, it.mig
4380: 68 74 20 61 73 20 77 65 6c 6c 20 64 6f 20 69 74  ht as well do it
4390: 20 6f 6e 20 74 68 65 20 6f 72 69 67 69 6e 61 6c   on the original
43a0: 20 74 61 62 6c 65 20 61 6e 64 20 67 65 74 20 61   table and get a
43b0: 6c 6c 20 6f 66 20 74 68 65 20 72 65 73 75 6c 74  ll of the result
43c0: 73 20 69 6e 0a 61 20 73 69 6e 67 6c 65 20 70 61  s in.a single pa
43d0: 73 73 20 77 69 74 68 6f 75 74 20 68 61 76 69 6e  ss without havin
43e0: 67 20 74 6f 20 6d 65 73 73 20 77 69 74 68 20 75  g to mess with u
43f0: 6e 69 6f 6e 20 6f 70 65 72 61 74 69 6f 6e 73 20  nion operations 
4400: 61 6e 64 20 66 6f 6c 6c 6f 77 2d 6f 6e 0a 62 69  and follow-on.bi
4410: 6e 61 72 79 20 73 65 61 72 63 68 65 73 2e 0a 3c  nary searches..<
4420: 2f 70 3e 0a 0a 3c 70 3e 0a 4f 6e 65 20 63 61 6e  /p>..<p>.One can
4430: 20 73 65 65 20 68 6f 77 20 74 68 65 20 4f 52 2d   see how the OR-
4440: 62 79 2d 55 4e 49 4f 4e 20 74 65 63 68 6e 69 71  by-UNION techniq
4450: 75 65 20 63 6f 75 6c 64 20 61 6c 73 6f 20 62 65  ue could also be
4460: 20 6c 65 76 65 72 61 67 65 64 20 74 6f 0a 75 73   leveraged to.us
4470: 65 20 6d 75 6c 74 69 70 6c 65 20 69 6e 64 69 63  e multiple indic
4480: 65 73 20 6f 6e 20 71 75 65 72 69 65 73 20 77 68  es on queries wh
4490: 65 72 65 20 74 68 65 20 57 48 45 52 45 20 63 6c  ere the WHERE cl
44a0: 61 75 73 65 20 68 61 73 20 74 65 72 6d 73 20 63  ause has terms c
44b0: 6f 6e 6e 65 63 74 65 64 0a 62 79 20 41 4e 44 2c  onnected.by AND,
44c0: 20 62 79 20 75 73 69 6e 67 20 61 6e 20 69 6e 74   by using an int
44d0: 65 72 73 65 63 74 20 6f 70 65 72 61 74 6f 72 20  ersect operator 
44e0: 69 6e 20 70 6c 61 63 65 20 6f 66 20 75 6e 69 6f  in place of unio
44f0: 6e 2e 20 20 4d 61 6e 79 20 53 51 4c 0a 64 61 74  n.  Many SQL.dat
4500: 61 62 61 73 65 20 65 6e 67 69 6e 65 73 20 77 69  abase engines wi
4510: 6c 6c 20 64 6f 20 6a 75 73 74 20 74 68 61 74 2e  ll do just that.
4520: 20 20 42 75 74 20 74 68 65 20 70 65 72 66 6f 72    But the perfor
4530: 6d 61 6e 63 65 20 67 61 69 6e 20 6f 76 65 72 20  mance gain over 
4540: 75 73 69 6e 67 0a 6a 75 73 74 20 61 20 73 69 6e  using.just a sin
4550: 67 6c 65 20 69 6e 64 65 78 20 69 73 20 73 6c 69  gle index is sli
4560: 67 68 74 20 61 6e 64 20 73 6f 20 53 51 4c 69 74  ght and so SQLit
4570: 65 20 64 6f 65 73 20 6e 6f 74 20 69 6d 70 6c 65  e does not imple
4580: 6d 65 6e 74 20 74 68 61 74 20 74 65 63 68 6e 69  ment that techni
4590: 71 75 65 0a 61 74 20 74 68 69 73 20 74 69 6d 65  que.at this time
45a0: 2e 20 20 48 6f 77 65 76 65 72 2c 20 61 20 66 75  .  However, a fu
45b0: 74 75 72 65 20 76 65 72 73 69 6f 6e 20 53 51 4c  ture version SQL
45c0: 69 74 65 20 6d 69 67 68 74 20 62 65 20 65 6e 68  ite might be enh
45d0: 61 6e 63 65 64 20 74 6f 20 73 75 70 70 6f 72 74  anced to support
45e0: 0a 41 4e 44 2d 62 79 2d 49 4e 54 45 52 53 45 43  .AND-by-INTERSEC
45f0: 54 2e 0a 3c 2f 70 3e 0a 0a 3c 74 63 6c 3e 68 64  T..</p>..<tcl>hd
4600: 5f 66 72 61 67 6d 65 6e 74 20 73 6f 72 74 69 6e  _fragment sortin
4610: 67 20 73 6f 72 74 69 6e 67 3c 2f 74 63 6c 3e 0a  g sorting</tcl>.
4620: 3c 68 32 3e 32 2e 30 20 53 6f 72 74 69 6e 67 3c  <h2>2.0 Sorting<
4630: 2f 68 32 3e 0a 0a 3c 70 3e 0a 53 51 4c 69 74 65  /h2>..<p>.SQLite
4640: 20 28 6c 69 6b 65 20 61 6c 6c 20 6f 74 68 65 72   (like all other
4650: 20 53 51 4c 20 64 61 74 61 62 61 73 65 20 65 6e   SQL database en
4660: 67 69 6e 65 73 29 20 63 61 6e 20 61 6c 73 6f 20  gines) can also 
4670: 75 73 65 20 69 6e 64 69 63 65 73 20 74 6f 0a 73  use indices to.s
4680: 61 74 69 73 66 79 20 74 68 65 20 4f 52 44 45 52  atisfy the ORDER
4690: 20 42 59 20 63 6c 61 75 73 65 73 20 69 6e 20 61   BY clauses in a
46a0: 20 71 75 65 72 79 2c 20 69 6e 20 61 64 64 69 74   query, in addit
46b0: 69 6f 6e 20 74 6f 20 65 78 70 65 64 69 74 69 6e  ion to expeditin
46c0: 67 0a 6c 6f 6f 6b 75 70 2e 20 20 49 6e 20 6f 74  g.lookup.  In ot
46d0: 68 65 72 20 77 6f 72 64 73 2c 20 69 6e 64 69 63  her words, indic
46e0: 65 73 20 63 61 6e 20 62 65 20 75 73 65 64 20 74  es can be used t
46f0: 6f 20 73 70 65 65 64 20 75 70 20 73 6f 72 74 69  o speed up sorti
4700: 6e 67 20 61 73 0a 77 65 6c 6c 20 61 73 20 73 65  ng as.well as se
4710: 61 72 63 68 69 6e 67 2e 0a 3c 2f 70 3e 0a 0a 3c  arching..</p>..<
4720: 70 3e 0a 57 68 65 6e 20 6e 6f 20 61 70 70 72 6f  p>.When no appro
4730: 70 72 69 61 74 65 20 69 6e 64 69 63 65 73 20 61  priate indices a
4740: 72 65 20 61 76 61 69 6c 61 62 6c 65 2c 20 61 20  re available, a 
4750: 71 75 65 72 79 20 77 69 74 68 20 61 6e 20 4f 52  query with an OR
4760: 44 45 52 20 42 59 0a 63 6c 61 75 73 65 20 6d 75  DER BY.clause mu
4770: 73 74 20 62 65 20 73 6f 72 74 65 64 20 61 73 20  st be sorted as 
4780: 61 20 73 65 70 61 72 61 74 65 20 73 74 65 70 2e  a separate step.
4790: 20 20 43 6f 6e 73 69 64 65 72 20 74 68 69 73 20    Consider this 
47a0: 71 75 65 72 79 3a 0a 3c 2f 70 3e 0a 0a 3c 74 63  query:.</p>..<tc
47b0: 6c 3e 63 6f 64 65 20 7b 53 45 4c 45 43 54 20 2a  l>code {SELECT *
47c0: 20 46 52 4f 4d 20 66 72 75 69 74 73 66 6f 72 73   FROM fruitsfors
47d0: 61 6c 65 20 4f 52 44 45 52 20 42 59 20 66 72 75  ale ORDER BY fru
47e0: 69 74 3b 7d 3c 2f 74 63 6c 3e 0a 0a 3c 70 3e 0a  it;}</tcl>..<p>.
47f0: 53 51 4c 69 74 65 20 70 72 6f 63 65 73 73 65 73  SQLite processes
4800: 20 74 68 69 73 20 62 79 20 67 61 74 68 65 72 69   this by gatheri
4810: 6e 67 20 61 6c 6c 20 74 68 65 20 6f 75 74 70 75  ng all the outpu
4820: 74 20 6f 66 20 71 75 65 72 79 20 61 6e 64 20 74  t of query and t
4830: 68 65 6e 0a 72 75 6e 6e 69 6e 67 20 74 68 61 74  hen.running that
4840: 20 6f 75 74 70 75 74 20 74 68 72 6f 75 67 68 20   output through 
4850: 61 20 73 6f 72 74 65 72 2e 0a 3c 2f 70 3e 0a 0a  a sorter..</p>..
4860: 3c 74 63 6c 3e 66 69 67 75 72 65 20 31 36 20 23  <tcl>figure 16 #
4870: 66 69 67 31 36 20 6f 62 66 72 75 69 74 6e 6f 69  fig16 obfruitnoi
4880: 64 78 2e 67 69 66 20 7b 53 6f 72 74 69 6e 67 20  dx.gif {Sorting 
4890: 57 69 74 68 6f 75 74 20 41 6e 20 49 6e 64 65 78  Without An Index
48a0: 7d 3c 2f 74 63 6c 3e 0a 0a 3c 70 3e 0a 49 66 20  }</tcl>..<p>.If 
48b0: 74 68 65 20 6e 75 6d 62 65 72 20 6f 66 20 6f 75  the number of ou
48c0: 74 70 75 74 20 72 6f 77 73 20 69 73 20 4b 2c 20  tput rows is K, 
48d0: 74 68 65 6e 20 74 68 65 20 74 69 6d 65 20 6e 65  then the time ne
48e0: 65 64 65 64 20 74 6f 20 73 6f 72 74 20 69 73 0a  eded to sort is.
48f0: 70 72 6f 70 6f 72 74 69 6f 6e 61 6c 20 74 6f 20  proportional to 
4900: 4b 6c 6f 67 4b 2e 20 20 49 66 20 4b 20 69 73 20  KlogK.  If K is 
4910: 73 6d 61 6c 6c 2c 20 74 68 65 20 73 6f 72 74 69  small, the sorti
4920: 6e 67 20 74 69 6d 65 20 69 73 20 75 73 75 61 6c  ng time is usual
4930: 6c 79 0a 6e 6f 74 20 61 20 66 61 63 74 6f 72 2c  ly.not a factor,
4940: 20 62 75 74 20 69 6e 20 61 20 71 75 65 72 79 20   but in a query 
4950: 73 75 63 68 20 61 73 20 74 68 65 20 61 62 6f 76  such as the abov
4960: 65 20 77 68 65 72 65 20 4b 3d 3d 4e 2c 20 74 68  e where K==N, th
4970: 65 20 74 69 6d 65 0a 6e 65 65 64 65 64 20 74 6f  e time.needed to
4980: 20 73 6f 72 74 20 63 61 6e 20 62 65 20 6d 75 63   sort can be muc
4990: 68 20 67 72 65 61 74 65 72 20 74 68 61 6e 20 74  h greater than t
49a0: 68 65 20 74 69 6d 65 20 6e 65 65 64 65 64 20 74  he time needed t
49b0: 6f 20 64 6f 20 61 0a 66 75 6c 6c 20 74 61 62 6c  o do a.full tabl
49c0: 65 20 73 63 61 6e 2e 20 20 46 75 72 74 68 65 72  e scan.  Further
49d0: 6d 6f 72 65 2c 20 74 68 65 20 65 6e 74 69 72 65  more, the entire
49e0: 20 6f 75 74 70 75 74 20 69 73 20 61 63 63 75 6d   output is accum
49f0: 75 6c 61 74 65 64 20 69 6e 0a 74 65 6d 70 6f 72  ulated in.tempor
4a00: 61 72 79 20 73 74 6f 72 61 67 65 20 28 77 68 69  ary storage (whi
4a10: 63 68 20 6d 69 67 68 74 20 62 65 20 65 69 74 68  ch might be eith
4a20: 65 72 20 69 6e 20 6d 61 69 6e 20 6d 65 6d 6f 72  er in main memor
4a30: 79 20 6f 72 20 6f 6e 20 64 69 73 6b 2c 0a 64 65  y or on disk,.de
4a40: 70 65 6e 64 69 6e 67 20 6f 6e 20 76 61 72 69 6f  pending on vario
4a50: 75 73 20 63 6f 6d 70 69 6c 65 2d 74 69 6d 65 20  us compile-time 
4a60: 61 6e 64 20 72 75 6e 2d 74 69 6d 65 20 73 65 74  and run-time set
4a70: 74 69 6e 67 73 29 0a 77 68 69 63 68 20 63 61 6e  tings).which can
4a80: 20 6d 65 61 6e 20 74 68 61 74 20 61 20 6c 6f 74   mean that a lot
4a90: 20 6f 66 20 74 65 6d 70 6f 72 61 72 79 20 73 74   of temporary st
4aa0: 6f 72 61 67 65 20 69 73 20 72 65 71 75 69 72 65  orage is require
4ab0: 64 20 74 6f 20 63 6f 6d 70 6c 65 74 65 0a 74 68  d to complete.th
4ac0: 65 20 71 75 65 72 79 2e 0a 3c 2f 70 3e 0a 0a 3c  e query..</p>..<
4ad0: 68 33 3e 32 2e 31 20 53 6f 72 74 69 6e 67 20 42  h3>2.1 Sorting B
4ae0: 79 20 52 6f 77 69 64 3c 2f 68 33 3e 0a 0a 3c 70  y Rowid</h3>..<p
4af0: 3e 0a 42 65 63 61 75 73 65 20 73 6f 72 74 69 6e  >.Because sortin
4b00: 67 20 63 61 6e 20 62 65 20 65 78 70 65 6e 73 69  g can be expensi
4b10: 76 65 2c 20 53 51 4c 69 74 65 20 77 6f 72 6b 73  ve, SQLite works
4b20: 20 68 61 72 64 20 74 6f 20 63 6f 6e 76 65 72 74   hard to convert
4b30: 20 4f 52 44 45 52 20 42 59 0a 63 6c 61 75 73 65   ORDER BY.clause
4b40: 73 20 69 6e 74 6f 20 6e 6f 2d 6f 70 73 2e 20 20  s into no-ops.  
4b50: 49 66 20 53 51 4c 69 74 65 20 64 65 74 65 72 6d  If SQLite determ
4b60: 69 6e 65 73 20 74 68 61 74 20 6f 75 74 70 75 74  ines that output
4b70: 20 77 69 6c 6c 0a 6e 61 74 75 72 61 6c 6c 79 20   will.naturally 
4b80: 61 70 70 65 61 72 20 69 6e 20 74 68 65 20 6f 72  appear in the or
4b90: 64 65 72 20 73 70 65 63 69 66 69 65 64 2c 20 74  der specified, t
4ba0: 68 65 6e 20 6e 6f 20 73 6f 72 74 69 6e 67 20 69  hen no sorting i
4bb0: 73 20 64 6f 6e 65 2e 0a 53 6f 2c 20 66 6f 72 20  s done..So, for 
4bc0: 65 78 61 6d 70 6c 65 2c 20 69 66 20 79 6f 75 20  example, if you 
4bd0: 72 65 71 75 65 73 74 20 74 68 65 20 6f 75 74 70  request the outp
4be0: 75 74 20 69 6e 20 72 6f 77 69 64 20 6f 72 64 65  ut in rowid orde
4bf0: 72 2c 20 6e 6f 20 73 6f 72 74 69 6e 67 0a 77 69  r, no sorting.wi
4c00: 6c 6c 20 62 65 20 64 6f 6e 65 3a 0a 3c 2f 70 3e  ll be done:.</p>
4c10: 0a 0a 3c 74 63 6c 3e 0a 63 6f 64 65 20 7b 53 45  ..<tcl>.code {SE
4c20: 4c 45 43 54 20 2a 20 46 52 4f 4d 20 66 72 75 69  LECT * FROM frui
4c30: 74 73 66 6f 72 73 61 6c 65 20 4f 52 44 45 52 20  tsforsale ORDER 
4c40: 42 59 20 72 6f 77 69 64 3b 7d 0a 66 69 67 75 72  BY rowid;}.figur
4c50: 65 20 31 37 20 23 66 69 67 31 37 20 6f 62 72 6f  e 17 #fig17 obro
4c60: 77 69 64 2e 67 69 66 20 7b 53 6f 72 74 69 6e 67  wid.gif {Sorting
4c70: 20 42 79 20 52 6f 77 69 64 7d 0a 3c 2f 74 63 6c   By Rowid}.</tcl
4c80: 3e 0a 0a 3c 70 3e 0a 59 6f 75 20 63 61 6e 20 61  >..<p>.You can a
4c90: 6c 73 6f 20 72 65 71 75 65 73 74 20 61 20 72 65  lso request a re
4ca0: 76 65 72 73 65 2d 6f 72 64 65 72 20 73 6f 72 74  verse-order sort
4cb0: 20 6c 69 6b 65 20 74 68 69 73 3a 0a 3c 2f 70 3e   like this:.</p>
4cc0: 0a 0a 3c 74 63 6c 3e 63 6f 64 65 20 7b 53 45 4c  ..<tcl>code {SEL
4cd0: 45 43 54 20 2a 20 46 52 4f 4d 20 66 72 75 69 74  ECT * FROM fruit
4ce0: 73 66 6f 72 73 61 6c 65 20 4f 52 44 45 52 20 42  sforsale ORDER B
4cf0: 59 20 72 6f 77 69 64 20 44 45 53 43 3b 7d 3c 2f  Y rowid DESC;}</
4d00: 74 63 6c 3e 0a 0a 3c 70 3e 0a 53 51 4c 69 74 65  tcl>..<p>.SQLite
4d10: 20 77 69 6c 6c 20 73 74 69 6c 6c 20 6f 6d 69 74   will still omit
4d20: 20 74 68 65 20 73 6f 72 74 69 6e 67 20 73 74 65   the sorting ste
4d30: 70 2e 20 20 42 75 74 20 69 6e 20 6f 72 64 65 72  p.  But in order
4d40: 20 66 6f 72 20 6f 75 74 70 75 74 20 74 6f 0a 61   for output to.a
4d50: 70 70 65 61 72 20 69 6e 20 74 68 65 20 63 6f 72  ppear in the cor
4d60: 72 65 63 74 20 6f 72 64 65 72 2c 20 53 51 4c 69  rect order, SQLi
4d70: 74 65 20 77 69 6c 6c 20 64 6f 20 74 68 65 20 74  te will do the t
4d80: 61 62 6c 65 20 73 63 61 6e 20 73 74 61 72 74 69  able scan starti
4d90: 6e 67 20 61 74 0a 74 68 65 20 65 6e 64 20 61 6e  ng at.the end an
4da0: 64 20 77 6f 72 6b 69 6e 67 20 74 6f 77 61 72 64  d working toward
4db0: 20 74 68 65 20 62 65 67 69 6e 6e 69 6e 67 2c 20   the beginning, 
4dc0: 72 61 74 68 65 72 20 74 68 61 6e 20 73 74 61 72  rather than star
4dd0: 74 69 6e 67 20 61 74 20 74 68 65 0a 62 65 67 69  ting at the.begi
4de0: 6e 6e 69 6e 67 20 61 6e 64 20 77 6f 72 6b 69 6e  nning and workin
4df0: 67 20 74 6f 77 61 72 64 20 74 68 65 20 65 6e 64  g toward the end
4e00: 20 61 73 20 73 68 6f 77 6e 20 69 6e 20 0a 3c 61   as shown in .<a
4e10: 20 68 72 65 66 3d 22 23 66 69 67 31 37 22 3e 66   href="#fig17">f
4e20: 69 67 75 72 65 20 31 37 3c 2f 61 3e 2e 0a 3c 2f  igure 17</a>..</
4e30: 70 3e 0a 0a 3c 68 33 3e 32 2e 32 20 53 6f 72 74  p>..<h3>2.2 Sort
4e40: 69 6e 67 20 42 79 20 49 6e 64 65 78 3c 2f 68 33  ing By Index</h3
4e50: 3e 0a 0a 3c 70 3e 0a 4f 66 20 63 6f 75 72 73 65  >..<p>.Of course
4e60: 2c 20 6f 72 64 65 72 69 6e 67 20 74 68 65 20 6f  , ordering the o
4e70: 75 74 70 75 74 20 6f 66 20 61 20 71 75 65 72 79  utput of a query
4e80: 20 62 79 20 72 6f 77 69 64 20 69 73 20 73 65 6c   by rowid is sel
4e90: 64 6f 6d 20 75 73 65 66 75 6c 2e 0a 55 73 75 61  dom useful..Usua
4ea0: 6c 6c 79 20 6f 6e 65 20 77 61 6e 74 73 20 74 6f  lly one wants to
4eb0: 20 6f 72 64 65 72 20 74 68 65 20 6f 75 74 70 75   order the outpu
4ec0: 74 20 62 79 20 73 6f 6d 65 20 6f 74 68 65 72 20  t by some other 
4ed0: 63 6f 6c 75 6d 6e 2e 0a 3c 2f 70 3e 0a 0a 3c 70  column..</p>..<p
4ee0: 3e 0a 49 66 20 61 6e 20 69 6e 64 65 78 20 69 73  >.If an index is
4ef0: 20 61 76 61 69 6c 61 62 6c 65 20 6f 6e 20 74 68   available on th
4f00: 65 20 4f 52 44 45 52 20 42 59 20 63 6f 6c 75 6d  e ORDER BY colum
4f10: 6e 2c 20 74 68 61 74 20 69 6e 64 65 78 20 63 61  n, that index ca
4f20: 6e 20 62 65 20 75 73 65 64 0a 66 6f 72 20 73 6f  n be used.for so
4f30: 72 74 69 6e 67 2e 20 20 43 6f 6e 73 69 64 65 72  rting.  Consider
4f40: 20 74 68 65 20 72 65 71 75 65 73 74 20 66 6f 72   the request for
4f50: 20 61 6c 6c 20 69 74 65 6d 73 20 73 6f 72 74 65   all items sorte
4f60: 64 20 62 79 20 22 66 72 75 69 74 22 3a 0a 3c 2f  d by "fruit":.</
4f70: 70 3e 0a 0a 3c 74 63 6c 3e 63 6f 64 65 20 7b 53  p>..<tcl>code {S
4f80: 45 4c 45 43 54 20 2a 20 46 52 4f 4d 20 66 72 75  ELECT * FROM fru
4f90: 69 74 73 66 6f 72 73 61 6c 65 20 4f 52 44 45 52  itsforsale ORDER
4fa0: 20 42 59 20 66 72 75 69 74 3b 7d 3c 2f 74 63 6c   BY fruit;}</tcl
4fb0: 3e 0a 0a 3c 74 63 6c 3e 66 69 67 75 72 65 20 31  >..<tcl>figure 1
4fc0: 38 20 23 66 69 67 31 38 20 6f 62 66 72 75 69 74  8 #fig18 obfruit
4fd0: 69 64 78 31 2e 67 69 66 20 7b 53 6f 72 74 69 6e  idx1.gif {Sortin
4fe0: 67 20 57 69 74 68 20 41 6e 20 49 6e 64 65 78 7d  g With An Index}
4ff0: 3c 2f 74 63 6c 3e 0a 0a 3c 70 3e 0a 54 68 65 20  </tcl>..<p>.The 
5000: 49 64 78 31 20 69 6e 64 65 78 20 69 73 20 73 63  Idx1 index is sc
5010: 61 6e 6e 65 64 20 66 72 6f 6d 20 74 6f 70 20 74  anned from top t
5020: 6f 20 62 6f 74 74 6f 6d 20 28 6f 72 20 66 72 6f  o bottom (or fro
5030: 6d 20 62 6f 74 74 6f 6d 20 74 6f 20 74 6f 70 20  m bottom to top 
5040: 69 66 0a 22 4f 52 44 45 52 20 42 59 20 66 72 75  if."ORDER BY fru
5050: 69 74 20 44 45 53 43 22 20 69 73 20 75 73 65 64  it DESC" is used
5060: 29 20 69 6e 20 6f 72 64 65 72 20 74 6f 20 66 69  ) in order to fi
5070: 6e 64 20 74 68 65 20 72 6f 77 69 64 73 20 66 6f  nd the rowids fo
5080: 72 20 65 61 63 68 20 69 74 65 6d 0a 69 6e 20 6f  r each item.in o
5090: 72 64 65 72 20 62 79 20 66 72 75 69 74 2e 20 20  rder by fruit.  
50a0: 54 68 65 6e 20 66 6f 72 20 65 61 63 68 20 72 6f  Then for each ro
50b0: 77 69 64 2c 20 61 20 62 69 6e 61 72 79 20 73 65  wid, a binary se
50c0: 61 72 63 68 20 69 73 20 64 6f 6e 65 20 74 6f 20  arch is done to 
50d0: 6c 6f 6f 6b 75 70 0a 61 6e 64 20 6f 75 74 70 75  lookup.and outpu
50e0: 74 20 74 68 61 74 20 72 6f 77 2e 20 20 49 6e 20  t that row.  In 
50f0: 74 68 69 73 20 77 61 79 2c 20 74 68 65 20 6f 75  this way, the ou
5100: 74 70 75 74 20 61 70 70 65 61 72 73 20 69 6e 20  tput appears in 
5110: 74 68 65 20 72 65 71 75 65 73 74 65 64 20 6f 72  the requested or
5120: 64 65 72 0a 77 69 74 68 20 74 68 65 20 6e 65 65  der.with the nee
5130: 64 20 74 6f 20 67 61 74 68 65 72 20 74 68 65 6e  d to gather then
5140: 20 65 6e 74 69 72 65 20 6f 75 74 70 75 74 20 61   entire output a
5150: 6e 64 20 73 6f 72 74 20 69 74 20 75 73 69 6e 67  nd sort it using
5160: 20 61 20 73 65 70 61 72 61 74 65 20 73 74 65 70   a separate step
5170: 2e 0a 3c 2f 70 3e 0a 0a 3c 70 3e 0a 42 75 74 20  ..</p>..<p>.But 
5180: 64 6f 65 73 20 74 68 69 73 20 72 65 61 6c 6c 79  does this really
5190: 20 73 61 76 65 20 74 69 6d 65 3f 20 20 54 68 65   save time?  The
51a0: 20 6e 75 6d 62 65 72 20 6f 66 20 73 74 65 70 73   number of steps
51b0: 20 69 6e 20 74 68 65 20 0a 3c 61 20 68 72 65 66   in the .<a href
51c0: 3d 22 23 66 69 67 31 36 22 3e 6f 72 69 67 69 6e  ="#fig16">origin
51d0: 61 6c 20 69 6e 64 65 78 6c 65 73 73 20 73 6f 72  al indexless sor
51e0: 74 3c 2f 61 3e 20 69 73 20 70 72 6f 70 6f 72 74  t</a> is proport
51f0: 69 6f 6e 61 6c 20 74 6f 20 4e 6c 6f 67 4e 20 73  ional to NlogN s
5200: 69 6e 63 65 0a 74 68 61 74 20 69 73 20 68 6f 77  ince.that is how
5210: 20 6d 75 63 68 20 74 69 6d 65 20 69 74 20 74 61   much time it ta
5220: 6b 65 73 20 74 6f 20 73 6f 72 74 20 4e 20 72 6f  kes to sort N ro
5230: 77 73 2e 20 20 42 75 74 20 77 68 65 6e 20 77 65  ws.  But when we
5240: 20 75 73 65 20 49 64 78 31 20 61 73 0a 73 68 6f   use Idx1 as.sho
5250: 77 6e 20 68 65 72 65 2c 20 77 65 20 68 61 76 65  wn here, we have
5260: 20 74 6f 20 64 6f 20 4e 20 72 6f 77 69 64 20 6c   to do N rowid l
5270: 6f 6f 6b 75 70 73 20 77 68 69 63 68 20 74 61 6b  ookups which tak
5280: 65 20 6c 6f 67 4e 20 74 69 6d 65 20 65 61 63 68  e logN time each
5290: 2c 20 73 6f 0a 74 68 65 20 74 6f 74 61 6c 20 74  , so.the total t
52a0: 69 6d 65 20 6f 66 20 4e 6c 6f 67 4e 20 69 73 20  ime of NlogN is 
52b0: 74 68 65 20 73 61 6d 65 21 0a 3c 2f 70 3e 0a 0a  the same!.</p>..
52c0: 3c 70 3e 0a 53 51 4c 69 74 65 20 75 73 65 73 20  <p>.SQLite uses 
52d0: 61 20 63 6f 73 74 2d 62 61 73 65 64 20 71 75 65  a cost-based que
52e0: 72 79 20 70 6c 61 6e 6e 65 72 2e 20 20 57 68 65  ry planner.  Whe
52f0: 6e 20 74 68 65 72 65 20 61 72 65 20 74 77 6f 20  n there are two 
5300: 6f 72 20 6d 6f 72 65 20 77 61 79 73 0a 6f 66 20  or more ways.of 
5310: 73 6f 6c 76 69 6e 67 20 74 68 65 20 73 61 6d 65  solving the same
5320: 20 71 75 65 72 79 2c 20 53 51 4c 69 74 65 20 74   query, SQLite t
5330: 72 69 65 73 20 74 6f 20 65 73 74 69 6d 61 74 65  ries to estimate
5340: 20 74 68 65 20 74 6f 74 61 6c 20 61 6d 6f 75 6e   the total amoun
5350: 74 20 6f 66 0a 74 69 6d 65 20 6e 65 65 64 65 64  t of.time needed
5360: 20 74 6f 20 72 75 6e 20 74 68 65 20 71 75 65 72   to run the quer
5370: 79 20 75 73 69 6e 67 20 65 61 63 68 20 70 6c 61  y using each pla
5380: 6e 2c 20 61 6e 64 20 74 68 65 6e 20 75 73 65 73  n, and then uses
5390: 20 74 68 65 20 70 6c 61 6e 20 77 69 74 68 0a 74   the plan with.t
53a0: 68 65 20 6c 6f 77 65 73 74 20 65 73 74 69 6d 61  he lowest estima
53b0: 74 65 64 20 63 6f 73 74 2e 20 20 41 20 63 6f 73  ted cost.  A cos
53c0: 74 20 69 73 20 63 6f 6d 70 75 74 65 64 20 6d 6f  t is computed mo
53d0: 73 74 6c 79 20 66 72 6f 6d 20 74 68 65 20 65 73  stly from the es
53e0: 74 69 6d 61 74 65 64 0a 74 69 6d 65 2c 20 61 6e  timated.time, an
53f0: 64 20 73 6f 20 74 68 69 73 20 63 61 73 65 20 63  d so this case c
5400: 6f 75 6c 64 20 67 6f 20 65 69 74 68 65 72 20 77  ould go either w
5410: 61 79 20 64 65 70 65 6e 64 69 6e 67 20 6f 6e 20  ay depending on 
5420: 74 68 65 20 74 61 62 6c 65 20 73 69 7a 65 20 61  the table size a
5430: 6e 64 0a 77 68 61 74 20 57 48 45 52 45 20 63 6c  nd.what WHERE cl
5440: 61 75 73 65 20 63 6f 6e 73 74 72 61 69 6e 74 73  ause constraints
5450: 20 77 65 72 65 20 61 76 61 69 6c 61 62 6c 65 2c   were available,
5460: 20 61 6e 64 20 73 6f 20 66 6f 72 74 68 2e 20 20   and so forth.  
5470: 42 75 74 20 67 65 6e 65 72 61 6c 6c 79 0a 73 70  But generally.sp
5480: 65 61 6b 69 6e 67 2c 20 74 68 65 20 69 6e 64 65  eaking, the inde
5490: 78 65 64 20 73 6f 72 74 20 77 6f 75 6c 64 20 70  xed sort would p
54a0: 72 6f 62 61 62 6c 79 20 62 65 20 63 68 6f 73 65  robably be chose
54b0: 6e 2c 20 69 66 20 66 6f 72 20 6e 6f 20 6f 74 68  n, if for no oth
54c0: 65 72 0a 72 65 61 73 6f 6e 2c 20 62 65 63 61 75  er.reason, becau
54d0: 73 65 20 69 74 20 64 6f 65 73 20 6e 6f 74 20 6e  se it does not n
54e0: 65 65 64 20 74 6f 20 61 63 63 75 6d 75 6c 61 74  eed to accumulat
54f0: 65 20 74 68 65 20 65 6e 74 69 72 65 20 72 65 73  e the entire res
5500: 75 6c 74 20 73 65 74 20 69 6e 0a 74 65 6d 70 6f  ult set in.tempo
5510: 72 61 72 79 20 73 74 6f 72 61 67 65 20 62 65 66  rary storage bef
5520: 6f 72 65 20 73 6f 72 74 69 6e 67 20 61 6e 64 20  ore sorting and 
5530: 74 68 75 73 20 75 73 65 73 20 6d 75 63 68 20 6c  thus uses much l
5540: 65 73 73 20 74 65 6d 70 6f 72 61 72 79 20 73 74  ess temporary st
5550: 6f 72 61 67 65 2e 0a 3c 2f 70 3e 0a 0a 3c 68 33  orage..</p>..<h3
5560: 3e 32 2e 33 20 53 6f 72 74 69 6e 67 20 42 79 20  >2.3 Sorting By 
5570: 43 6f 76 65 72 69 6e 67 20 49 6e 64 65 78 3c 2f  Covering Index</
5580: 68 33 3e 0a 0a 3c 70 3e 0a 49 66 20 61 20 63 6f  h3>..<p>.If a co
5590: 76 65 72 69 6e 67 20 69 6e 64 65 78 20 63 61 6e  vering index can
55a0: 20 62 65 20 75 73 65 64 20 66 6f 72 20 61 20 71   be used for a q
55b0: 75 65 72 79 2c 20 74 68 65 6e 20 74 68 65 20 6d  uery, then the m
55c0: 75 6c 74 69 70 6c 65 20 72 6f 77 69 64 20 6c 6f  ultiple rowid lo
55d0: 6f 6b 75 70 73 0a 63 61 6e 20 62 65 20 61 76 6f  okups.can be avo
55e0: 69 64 65 64 20 61 6e 64 20 74 68 65 20 63 6f 73  ided and the cos
55f0: 74 20 6f 66 20 74 68 65 20 71 75 65 72 79 20 64  t of the query d
5600: 72 6f 70 73 20 64 72 61 6d 61 74 69 63 61 6c 6c  rops dramaticall
5610: 79 2e 0a 3c 2f 70 3e 0a 0a 3c 74 63 6c 3e 0a 66  y..</p>..<tcl>.f
5620: 69 67 75 72 65 20 31 39 20 23 66 69 67 31 39 20  igure 19 #fig19 
5630: 6f 62 66 72 75 69 74 69 64 78 34 2e 67 69 66 20  obfruitidx4.gif 
5640: 7b 53 6f 72 74 69 6e 67 20 57 69 74 68 20 41 20  {Sorting With A 
5650: 43 6f 76 65 72 69 6e 67 20 49 6e 64 65 78 7d 0a  Covering Index}.
5660: 3c 2f 74 63 6c 3e 0a 0a 3c 70 3e 0a 57 69 74 68  </tcl>..<p>.With
5670: 20 61 20 63 6f 76 65 72 69 6e 67 20 69 6e 64 65   a covering inde
5680: 78 2c 20 53 51 4c 69 74 65 20 63 61 6e 20 73 69  x, SQLite can si
5690: 6d 70 6c 79 20 77 61 6c 6b 20 74 68 65 20 69 6e  mply walk the in
56a0: 64 65 78 20 66 72 6f 6d 20 6f 6e 65 20 65 6e 64  dex from one end
56b0: 20 74 6f 20 74 68 65 0a 6f 74 68 65 72 20 61 6e   to the.other an
56c0: 64 20 64 65 6c 69 76 65 72 20 74 68 65 20 6f 75  d deliver the ou
56d0: 74 70 75 74 20 69 6e 20 74 69 6d 65 20 70 72 6f  tput in time pro
56e0: 70 6f 72 74 69 6f 6e 61 6c 20 74 6f 20 4e 20 61  portional to N a
56f0: 6e 64 20 77 69 74 68 6f 75 74 20 68 61 76 69 6e  nd without havin
5700: 67 0a 61 6c 6c 6f 63 61 74 65 20 61 20 6c 61 72  g.allocate a lar
5710: 67 65 20 62 75 66 66 65 72 20 74 6f 20 68 6f 6c  ge buffer to hol
5720: 64 20 74 68 65 20 72 65 73 75 6c 74 20 73 65 74  d the result set
5730: 2e 0a 3c 2f 70 3e 0a 0a 3c 68 32 3e 33 2e 30 20  ..</p>..<h2>3.0 
5740: 53 65 61 72 63 68 69 6e 67 20 41 6e 64 20 53 6f  Searching And So
5750: 72 74 69 6e 67 20 41 74 20 54 68 65 20 53 61 6d  rting At The Sam
5760: 65 20 54 69 6d 65 3c 2f 68 32 3e 0a 0a 3c 70 3e  e Time</h2>..<p>
5770: 0a 54 68 65 20 70 72 65 76 69 6f 75 73 20 64 69  .The previous di
5780: 73 63 75 73 73 69 6f 6e 20 68 61 73 20 74 72 65  scussion has tre
5790: 61 74 65 64 20 73 65 61 72 63 68 69 6e 67 20 61  ated searching a
57a0: 6e 64 20 73 6f 72 74 69 6e 67 20 61 73 20 73 65  nd sorting as se
57b0: 70 61 72 61 74 65 0a 74 6f 70 69 63 73 2e 20 20  parate.topics.  
57c0: 42 75 74 20 69 6e 20 70 72 61 63 74 69 63 65 2c  But in practice,
57d0: 20 69 74 20 69 73 20 6f 66 74 65 6e 20 74 68 65   it is often the
57e0: 20 63 61 73 65 20 74 68 61 74 20 6f 6e 65 20 77   case that one w
57f0: 61 6e 74 73 20 74 6f 20 73 65 61 72 63 68 0a 61  ants to search.a
5800: 6e 64 20 73 6f 72 74 20 61 74 20 74 68 65 20 73  nd sort at the s
5810: 61 6d 65 20 74 69 6d 65 2e 20 20 46 6f 72 74 75  ame time.  Fortu
5820: 6e 61 74 65 6c 79 2c 20 69 74 20 69 73 20 70 6f  nately, it is po
5830: 73 73 69 62 6c 65 20 74 6f 20 64 6f 20 74 68 69  ssible to do thi
5840: 73 0a 75 73 69 6e 67 20 61 20 73 69 6e 67 6c 65  s.using a single
5850: 20 69 6e 64 65 78 2e 0a 3c 2f 70 3e 0a 0a 3c 68   index..</p>..<h
5860: 33 3e 33 2e 31 20 53 65 61 72 63 68 69 6e 67 20  3>3.1 Searching 
5870: 41 6e 64 20 53 6f 72 74 69 6e 67 20 57 69 74 68  And Sorting With
5880: 20 41 20 4d 75 6c 74 69 2d 43 6f 6c 75 6d 6e 20   A Multi-Column 
5890: 49 6e 64 65 78 3c 2f 68 33 3e 0a 0a 3c 70 3e 0a  Index</h3>..<p>.
58a0: 53 75 70 70 6f 73 65 20 77 65 20 77 61 6e 74 20  Suppose we want 
58b0: 74 6f 20 66 69 6e 64 20 74 68 65 20 70 72 69 63  to find the pric
58c0: 65 73 20 6f 66 20 61 6c 6c 20 6b 69 6e 64 73 20  es of all kinds 
58d0: 6f 66 20 6f 72 61 6e 67 65 73 20 73 6f 72 74 65  of oranges sorte
58e0: 64 20 69 6e 0a 6f 72 64 65 72 20 6f 66 20 74 68  d in.order of th
58f0: 65 20 73 74 61 74 65 20 77 68 65 72 65 20 74 68  e state where th
5900: 65 79 20 61 72 65 20 67 72 6f 77 6e 2e 20 20 54  ey are grown.  T
5910: 68 65 20 71 75 65 72 79 20 69 73 20 74 68 69 73  he query is this
5920: 3a 0a 3c 2f 70 3e 0a 0a 3c 74 63 6c 3e 0a 63 6f  :.</p>..<tcl>.co
5930: 64 65 20 7b 53 45 4c 45 43 54 20 70 72 69 63 65  de {SELECT price
5940: 20 46 52 4f 4d 20 66 72 75 69 74 66 6f 72 73 61   FROM fruitforsa
5950: 6c 65 20 57 48 45 52 45 20 66 72 75 69 74 3d 27  le WHERE fruit='
5960: 4f 72 61 6e 67 65 27 20 4f 52 44 45 52 20 42 59  Orange' ORDER BY
5970: 20 73 74 61 74 65 7d 0a 3c 2f 74 63 6c 3e 0a 0a   state}.</tcl>..
5980: 3c 70 3e 0a 54 68 65 20 71 75 65 72 79 20 63 6f  <p>.The query co
5990: 6e 74 61 69 6e 73 20 62 6f 74 68 20 61 20 73 65  ntains both a se
59a0: 61 72 63 68 20 72 65 73 74 72 69 63 74 69 6f 6e  arch restriction
59b0: 20 69 6e 20 74 68 65 20 57 48 45 52 45 20 63 6c   in the WHERE cl
59c0: 61 75 73 65 0a 61 6e 64 20 61 20 73 6f 72 74 20  ause.and a sort 
59d0: 6f 72 64 65 72 20 69 6e 20 74 68 65 20 4f 52 44  order in the ORD
59e0: 45 52 20 42 59 20 63 6c 61 75 73 65 2e 20 20 42  ER BY clause.  B
59f0: 6f 74 68 20 74 68 65 20 73 65 61 72 63 68 20 61  oth the search a
5a00: 6e 64 20 74 68 65 20 73 6f 72 74 0a 63 61 6e 20  nd the sort.can 
5a10: 62 65 20 61 63 63 6f 6d 70 6c 69 73 68 65 64 20  be accomplished 
5a20: 61 74 20 74 68 65 20 73 61 6d 65 20 74 69 6d 65  at the same time
5a30: 20 75 73 69 6e 67 20 74 68 65 20 74 77 6f 2d 63   using the two-c
5a40: 6f 6c 75 6d 6e 20 69 6e 64 65 78 20 49 64 78 33  olumn index Idx3
5a50: 2e 0a 3c 2f 70 3e 0a 0a 3c 74 63 6c 3e 0a 66 69  ..</p>..<tcl>.fi
5a60: 67 75 72 65 20 32 30 20 23 66 69 67 32 30 20 66  gure 20 #fig20 f
5a70: 72 75 69 74 6f 62 73 74 61 74 65 30 2e 67 69 66  ruitobstate0.gif
5a80: 20 7b 53 65 61 72 63 68 20 41 6e 64 20 53 6f 72   {Search And Sor
5a90: 74 20 42 79 20 4d 75 6c 74 69 2d 43 6f 6c 75 6d  t By Multi-Colum
5aa0: 6e 20 49 6e 64 65 78 7d 0a 3c 2f 74 63 6c 3e 0a  n Index}.</tcl>.
5ab0: 0a 3c 70 3e 0a 54 68 65 20 71 75 65 72 79 20 64  .<p>.The query d
5ac0: 6f 65 73 20 61 20 62 69 6e 61 72 79 20 73 65 61  oes a binary sea
5ad0: 72 63 68 20 6f 6e 20 74 68 65 20 69 6e 64 65 78  rch on the index
5ae0: 20 74 6f 20 66 69 6e 64 20 74 68 65 20 73 75 62   to find the sub
5af0: 73 65 74 20 6f 66 20 72 6f 77 73 0a 74 68 61 74  set of rows.that
5b00: 20 68 61 76 65 20 66 72 75 69 74 3d 27 4f 72 61   have fruit='Ora
5b10: 6e 67 65 27 2e 20 20 28 42 65 63 61 75 73 65 20  nge'.  (Because 
5b20: 74 68 65 20 66 72 75 69 74 20 63 6f 6c 75 6d 6e  the fruit column
5b30: 20 69 73 20 74 68 65 20 6c 65 66 74 2d 6d 6f 73   is the left-mos
5b40: 74 20 63 6f 6c 75 6d 6e 0a 6f 66 20 74 68 65 20  t column.of the 
5b50: 69 6e 64 65 78 20 61 6e 64 20 74 68 65 20 72 6f  index and the ro
5b60: 77 73 20 6f 66 20 74 68 65 20 69 6e 64 65 78 20  ws of the index 
5b70: 61 72 65 20 69 6e 20 73 6f 72 74 65 64 20 6f 72  are in sorted or
5b80: 64 65 72 2c 20 61 6c 6c 20 73 75 63 68 20 0a 72  der, all such .r
5b90: 6f 77 73 20 77 69 6c 6c 20 62 65 20 61 64 6a 61  ows will be adja
5ba0: 63 65 6e 74 2e 29 20 20 54 68 65 6e 20 69 74 20  cent.)  Then it 
5bb0: 73 63 61 6e 73 20 74 68 65 20 6d 61 74 63 68 69  scans the matchi
5bc0: 6e 67 20 69 6e 64 65 78 20 72 6f 77 73 20 66 72  ng index rows fr
5bd0: 6f 6d 20 74 6f 70 20 74 6f 0a 62 6f 74 74 6f 6d  om top to.bottom
5be0: 20 74 6f 20 67 65 74 20 74 68 65 20 72 6f 77 69   to get the rowi
5bf0: 64 73 20 66 6f 72 20 74 68 65 20 6f 72 69 67 69  ds for the origi
5c00: 6e 61 6c 20 74 61 62 6c 65 2c 20 61 6e 64 20 66  nal table, and f
5c10: 6f 72 20 65 61 63 68 20 72 6f 77 69 64 20 64 6f  or each rowid do
5c20: 65 73 0a 61 20 62 69 6e 61 72 79 20 73 65 61 72  es.a binary sear
5c30: 63 68 20 6f 6e 20 74 68 65 20 6f 72 69 67 69 6e  ch on the origin
5c40: 61 6c 20 74 61 62 6c 65 20 74 6f 20 66 69 6e 64  al table to find
5c50: 20 74 68 65 20 70 72 69 63 65 2e 0a 3c 2f 70 3e   the price..</p>
5c60: 0a 0a 3c 70 3e 0a 59 6f 75 20 77 69 6c 6c 20 6e  ..<p>.You will n
5c70: 6f 74 69 63 65 20 74 68 61 74 20 74 68 65 72 65  otice that there
5c80: 20 69 73 20 6e 6f 20 22 73 6f 72 74 22 20 62 6f   is no "sort" bo
5c90: 78 20 61 6e 79 77 68 65 72 65 20 69 6e 20 74 68  x anywhere in th
5ca0: 65 20 61 62 6f 76 65 20 64 69 61 67 72 61 6d 2e  e above diagram.
5cb0: 0a 54 68 65 20 4f 52 44 45 52 20 42 59 20 63 6c  .The ORDER BY cl
5cc0: 61 75 73 65 20 6f 66 20 74 68 65 20 71 75 65 72  ause of the quer
5cd0: 79 20 68 61 73 20 62 65 63 6f 6d 65 20 61 20 6e  y has become a n
5ce0: 6f 2d 6f 70 2e 20 20 4e 6f 20 73 6f 72 74 69 6e  o-op.  No sortin
5cf0: 67 20 68 61 73 20 74 6f 20 62 65 0a 64 6f 6e 65  g has to be.done
5d00: 20 68 65 72 65 20 62 65 63 61 75 73 65 20 74 68   here because th
5d10: 65 20 6f 75 74 70 75 74 20 6f 72 64 65 72 20 69  e output order i
5d20: 73 20 62 79 20 74 68 65 20 73 74 61 74 65 20 63  s by the state c
5d30: 6f 6c 75 6d 6e 20 61 6e 64 20 74 68 65 20 73 74  olumn and the st
5d40: 61 74 65 0a 63 6f 6c 75 6d 6e 20 61 6c 73 6f 20  ate.column also 
5d50: 68 61 70 70 65 6e 73 20 74 6f 20 62 65 20 74 68  happens to be th
5d60: 65 20 66 69 72 73 74 20 63 6f 6c 75 6d 6e 20 61  e first column a
5d70: 66 74 65 72 20 74 68 65 20 66 72 75 69 74 20 63  fter the fruit c
5d80: 6f 6c 75 6d 6e 20 69 6e 20 74 68 65 0a 69 6e 64  olumn in the.ind
5d90: 65 78 2e 20 20 53 6f 2c 20 69 66 20 77 65 20 73  ex.  So, if we s
5da0: 63 61 6e 20 65 6e 74 72 69 65 73 20 6f 66 20 74  can entries of t
5db0: 68 65 20 69 6e 64 65 78 20 74 68 61 74 20 68 61  he index that ha
5dc0: 76 65 20 74 68 65 20 73 61 6d 65 20 76 61 6c 75  ve the same valu
5dd0: 65 20 66 6f 72 0a 74 68 65 20 66 72 75 69 74 20  e for.the fruit 
5de0: 63 6f 6c 75 6d 6e 20 66 72 6f 6d 20 74 6f 70 20  column from top 
5df0: 74 6f 20 62 6f 74 74 6f 6d 2c 20 74 68 6f 73 65  to bottom, those
5e00: 20 69 6e 64 65 78 20 65 6e 74 72 69 65 73 20 61   index entries a
5e10: 72 65 20 67 75 61 72 61 6e 74 65 65 64 20 74 6f  re guaranteed to
5e20: 0a 62 65 20 6f 72 64 65 72 65 64 20 62 79 20 74  .be ordered by t
5e30: 68 65 20 73 74 61 74 65 20 63 6f 6c 75 6d 6e 2e  he state column.
5e40: 0a 3c 2f 70 3e 0a 0a 3c 74 63 6c 3e 68 64 5f 66  .</p>..<tcl>hd_f
5e50: 72 61 67 6d 65 6e 74 20 7b 73 72 63 68 73 6f 72  ragment {srchsor
5e60: 74 63 6f 76 69 64 78 7d 3c 2f 74 63 6c 3e 0a 3c  tcovidx}</tcl>.<
5e70: 68 33 3e 33 2e 32 20 53 65 61 72 63 68 69 6e 67  h3>3.2 Searching
5e80: 20 41 6e 64 20 53 6f 72 74 69 6e 67 20 57 69 74   And Sorting Wit
5e90: 68 20 41 20 43 6f 76 65 72 69 6e 67 20 49 6e 64  h A Covering Ind
5ea0: 65 78 3c 2f 68 33 3e 0a 0a 3c 70 3e 0a 41 20 5b  ex</h3>..<p>.A [
5eb0: 63 6f 76 65 72 69 6e 67 20 69 6e 64 65 78 5d 20  covering index] 
5ec0: 63 61 6e 20 61 6c 73 6f 20 62 65 20 75 73 65 64  can also be used
5ed0: 20 74 6f 20 73 65 61 72 63 68 20 61 6e 64 20 73   to search and s
5ee0: 6f 72 74 20 61 74 20 74 68 65 20 73 61 6d 65 20  ort at the same 
5ef0: 74 69 6d 65 2e 0a 43 6f 6e 73 69 64 65 72 20 74  time..Consider t
5f00: 68 65 20 66 6f 6c 6c 6f 77 69 6e 67 3a 0a 3c 2f  he following:.</
5f10: 70 3e 0a 0a 3c 74 63 6c 3e 0a 63 6f 64 65 20 7b  p>..<tcl>.code {
5f20: 53 45 4c 45 43 54 20 2a 20 46 52 4f 4d 20 66 72  SELECT * FROM fr
5f30: 75 69 74 66 6f 72 73 61 6c 65 20 57 48 45 52 45  uitforsale WHERE
5f40: 20 66 72 75 69 74 3d 27 4f 72 61 6e 67 65 27 20   fruit='Orange' 
5f50: 4f 52 44 45 52 20 42 59 20 73 74 61 74 65 7d 0a  ORDER BY state}.
5f60: 66 69 67 75 72 65 20 32 31 20 23 66 69 67 32 31  figure 21 #fig21
5f70: 20 66 72 75 69 74 6f 62 73 74 61 74 65 2e 67 69   fruitobstate.gi
5f80: 66 20 7b 53 65 61 72 63 68 20 41 6e 64 20 53 6f  f {Search And So
5f90: 72 74 20 42 79 20 43 6f 76 65 72 69 6e 67 20 49  rt By Covering I
5fa0: 6e 64 65 78 7d 0a 3c 2f 74 63 6c 3e 0a 0a 3c 70  ndex}.</tcl>..<p
5fb0: 3e 0a 41 73 20 62 65 66 6f 72 65 2c 20 53 51 4c  >.As before, SQL
5fc0: 69 74 65 20 64 6f 65 73 20 73 69 6e 67 6c 65 20  ite does single 
5fd0: 62 69 6e 61 72 79 20 73 65 61 72 63 68 0a 66 6f  binary search.fo
5fe0: 72 20 74 68 65 20 72 61 6e 67 65 20 6f 66 20 72  r the range of r
5ff0: 6f 77 73 20 69 6e 20 74 68 65 20 63 6f 76 65 72  ows in the cover
6000: 69 6e 67 0a 69 6e 64 65 78 20 74 68 61 74 20 73  ing.index that s
6010: 61 74 69 73 66 79 20 74 68 65 20 57 48 45 52 45  atisfy the WHERE
6020: 20 63 6c 61 75 73 65 2c 20 74 68 65 20 73 63 61   clause, the sca
6030: 6e 73 20 74 68 61 74 20 72 61 6e 67 65 20 66 72  ns that range fr
6040: 6f 6d 20 74 6f 70 20 74 6f 20 0a 62 6f 74 74 6f  om top to .botto
6050: 6d 20 74 6f 20 67 65 74 20 74 68 65 20 64 65 73  m to get the des
6060: 69 72 65 64 20 72 65 73 75 6c 74 73 2e 20 20 0a  ired results.  .
6070: 54 68 65 20 72 6f 77 73 20 74 68 61 74 20 73 61  The rows that sa
6080: 74 69 73 66 79 20 74 68 65 20 57 48 45 52 45 20  tisfy the WHERE 
6090: 63 6c 61 75 73 65 20 61 72 65 20 67 75 61 72 61  clause are guara
60a0: 6e 74 65 65 64 20 74 6f 20 62 65 20 61 64 6a 61  nteed to be adja
60b0: 63 65 6e 74 0a 73 69 6e 63 65 20 74 68 65 20 57  cent.since the W
60c0: 48 45 52 45 20 63 6c 61 75 73 65 20 69 73 20 61  HERE clause is a
60d0: 6e 20 65 71 75 61 6c 69 74 79 20 63 6f 6e 73 74  n equality const
60e0: 72 61 69 6e 74 20 6f 6e 20 74 68 65 20 6c 65 66  raint on the lef
60f0: 74 2d 6d 6f 73 74 0a 63 6f 6c 75 6d 6e 20 6f 66  t-most.column of
6100: 20 74 68 65 20 69 6e 64 65 78 2e 20 20 41 6e 64   the index.  And
6110: 20 62 79 20 73 63 61 6e 6e 69 6e 67 20 74 68 65   by scanning the
6120: 20 6d 61 74 63 68 69 6e 67 20 69 6e 64 65 78 20   matching index 
6130: 72 6f 77 73 20 66 72 6f 6d 0a 74 6f 70 20 74 6f  rows from.top to
6140: 20 62 6f 74 74 6f 6d 2c 20 74 68 65 20 6f 75 74   bottom, the out
6150: 70 75 74 20 69 73 20 67 75 61 72 61 6e 74 65 65  put is guarantee
6160: 64 20 74 6f 20 62 65 20 6f 72 64 65 72 65 64 20  d to be ordered 
6170: 62 79 20 73 74 61 74 65 20 73 69 6e 63 65 20 74  by state since t
6180: 68 65 0a 73 74 61 74 65 20 63 6f 6c 75 6d 6e 20  he.state column 
6190: 69 73 20 74 68 65 20 76 65 72 79 20 6e 65 78 74  is the very next
61a0: 20 63 6f 6c 75 6d 6e 20 74 6f 20 74 68 65 20 72   column to the r
61b0: 69 67 68 74 20 6f 66 20 74 68 65 20 66 72 75 69  ight of the frui
61c0: 74 20 63 6f 6c 75 6d 6e 2e 0a 41 6e 64 20 73 6f  t column..And so
61d0: 20 74 68 65 20 72 65 73 75 6c 74 69 6e 67 20 71   the resulting q
61e0: 75 65 72 79 20 69 73 20 76 65 72 79 20 65 66 66  uery is very eff
61f0: 69 63 69 65 6e 74 2e 0a 3c 2f 70 3e 0a 0a 3c 70  icient..</p>..<p
6200: 3e 0a 53 51 4c 69 74 65 20 63 61 6e 20 70 75 6c  >.SQLite can pul
6210: 6c 20 61 20 73 69 6d 69 6c 61 72 20 74 72 69 63  l a similar tric
6220: 6b 20 66 6f 72 20 61 20 64 65 73 63 65 6e 64 69  k for a descendi
6230: 6e 67 20 4f 52 44 45 52 20 42 59 3a 0a 3c 2f 70  ng ORDER BY:.</p
6240: 3e 0a 0a 3c 74 63 6c 3e 0a 63 6f 64 65 20 7b 53  >..<tcl>.code {S
6250: 45 4c 45 43 54 20 2a 20 46 52 4f 4d 20 66 72 75  ELECT * FROM fru
6260: 69 74 66 6f 72 73 61 6c 65 20 57 48 45 52 45 20  itforsale WHERE 
6270: 66 72 75 69 74 3d 27 4f 72 61 6e 67 65 27 20 4f  fruit='Orange' O
6280: 52 44 45 52 20 42 59 20 73 74 61 74 65 20 44 45  RDER BY state DE
6290: 53 43 7d 0a 3c 2f 74 63 6c 3e 0a 0a 3c 70 3e 0a  SC}.</tcl>..<p>.
62a0: 54 68 65 20 73 61 6d 65 20 62 61 73 69 63 20 61  The same basic a
62b0: 6c 67 6f 72 69 74 68 6d 20 69 73 20 66 6f 6c 6c  lgorithm is foll
62c0: 6f 77 65 64 2c 20 65 78 63 65 70 74 20 74 68 69  owed, except thi
62d0: 73 20 74 69 6d 65 20 74 68 65 20 6d 61 74 63 68  s time the match
62e0: 69 6e 67 20 72 6f 77 73 0a 6f 66 20 74 68 65 20  ing rows.of the 
62f0: 69 6e 64 65 78 20 61 72 65 20 73 63 61 6e 6e 65  index are scanne
6300: 64 20 66 72 6f 6d 20 62 6f 74 74 6f 6d 20 74 6f  d from bottom to
6310: 20 74 6f 70 20 69 6e 73 74 65 61 64 20 6f 66 20   top instead of 
6320: 66 72 6f 6d 20 74 6f 70 20 74 6f 20 62 6f 74 74  from top to bott
6330: 6f 6d 2c 0a 73 6f 20 74 68 61 74 20 74 68 65 20  om,.so that the 
6340: 73 74 61 74 65 73 20 77 69 6c 6c 20 61 70 70 65  states will appe
6350: 61 72 20 69 6e 20 64 65 73 63 65 6e 64 69 6e 67  ar in descending
6360: 20 6f 72 64 65 72 2e 0a 3c 2f 70 3e 0a 0a 3c 74   order..</p>..<t
6370: 63 6c 3e 68 64 5f 66 72 61 67 6d 65 6e 74 20 7b  cl>hd_fragment {
6380: 70 61 72 74 69 61 6c 73 6f 72 74 7d 20 7b 70 61  partialsort} {pa
6390: 72 74 69 61 6c 20 73 6f 72 74 69 6e 67 20 62 79  rtial sorting by
63a0: 20 69 6e 64 65 78 7d 20 7b 62 6c 6f 63 6b 20 73   index} {block s
63b0: 6f 72 74 69 6e 67 7d 3c 2f 74 63 6c 3e 0a 3c 68  orting}</tcl>.<h
63c0: 33 3e 33 2e 32 20 50 61 72 74 69 61 6c 20 53 6f  3>3.2 Partial So
63d0: 72 74 69 6e 67 20 55 73 69 6e 67 20 41 6e 20 49  rting Using An I
63e0: 6e 64 65 78 20 28 61 2e 6b 2e 61 2e 20 42 6c 6f  ndex (a.k.a. Blo
63f0: 63 6b 20 53 6f 72 74 69 6e 67 29 3c 2f 68 33 3e  ck Sorting)</h3>
6400: 0a 0a 3c 70 3e 0a 53 6f 6d 65 74 69 6d 65 73 20  ..<p>.Sometimes 
6410: 6f 6e 6c 79 20 70 61 72 74 20 6f 66 20 61 6e 20  only part of an 
6420: 4f 52 44 45 52 20 42 59 20 63 6c 61 75 73 65 20  ORDER BY clause 
6430: 63 61 6e 20 62 65 20 73 61 74 69 73 66 69 65 64  can be satisfied
6440: 20 75 73 69 6e 67 20 69 6e 64 65 78 65 73 2e 0a   using indexes..
6450: 43 6f 6e 73 69 64 65 72 2c 20 66 6f 72 20 65 78  Consider, for ex
6460: 61 6d 70 6c 65 2c 20 74 68 65 20 66 6f 6c 6c 6f  ample, the follo
6470: 77 69 6e 67 20 71 75 65 72 79 3a 0a 3c 2f 70 3e  wing query:.</p>
6480: 0a 0a 3c 74 63 6c 3e 0a 63 6f 64 65 20 7b 53 45  ..<tcl>.code {SE
6490: 4c 45 43 54 20 2a 20 46 52 4f 4d 20 66 72 75 69  LECT * FROM frui
64a0: 74 66 6f 72 73 61 6c 65 20 4f 52 44 45 52 20 42  tforsale ORDER B
64b0: 59 20 66 72 75 69 74 2c 20 70 72 69 63 65 7d 0a  Y fruit, price}.
64c0: 3c 2f 74 63 6c 3e 0a 0a 3c 70 3e 0a 49 66 20 74  </tcl>..<p>.If t
64d0: 68 65 20 63 6f 76 65 72 69 6e 67 20 69 6e 64 65  he covering inde
64e0: 78 20 69 73 20 75 73 65 64 20 66 6f 72 20 74 68  x is used for th
64f0: 65 20 73 63 61 6e 2c 20 74 68 65 20 22 66 72 75  e scan, the "fru
6500: 69 74 22 20 63 6f 6c 75 6d 6e 20 77 69 6c 6c 20  it" column will 
6510: 61 70 70 65 61 72 0a 6e 61 74 75 72 61 6c 6c 79  appear.naturally
6520: 20 69 6e 20 74 68 65 20 63 6f 72 72 65 63 74 20   in the correct 
6530: 6f 72 64 65 72 2c 20 62 75 74 20 77 68 65 6e 20  order, but when 
6540: 74 68 65 72 65 20 61 72 65 20 74 77 6f 20 6f 72  there are two or
6550: 20 6d 6f 72 65 20 72 6f 77 73 20 77 69 74 68 0a   more rows with.
6560: 74 68 65 20 73 61 6d 65 20 66 72 75 69 74 2c 20  the same fruit, 
6570: 74 68 65 20 70 72 69 63 65 20 6d 69 67 68 74 20  the price might 
6580: 62 65 20 6f 75 74 20 6f 66 20 6f 72 64 65 72 2e  be out of order.
6590: 20 20 57 68 65 6e 20 74 68 69 73 20 6f 63 63 75    When this occu
65a0: 72 73 2c 20 53 51 4c 69 74 65 0a 64 6f 65 73 20  rs, SQLite.does 
65b0: 6d 61 6e 79 20 73 6d 61 6c 6c 20 73 6f 72 74 73  many small sorts
65c0: 2c 20 6f 6e 65 20 73 6f 72 74 20 66 6f 72 20 65  , one sort for e
65d0: 61 63 68 20 64 69 73 74 69 6e 63 74 20 76 61 6c  ach distinct val
65e0: 75 65 20 6f 66 20 66 72 75 69 74 2c 20 72 61 74  ue of fruit, rat
65f0: 68 65 72 0a 74 68 61 6e 20 6f 6e 65 20 6c 61 72  her.than one lar
6600: 67 65 20 73 6f 72 74 2e 20 20 46 69 67 75 72 65  ge sort.  Figure
6610: 20 32 32 20 62 65 6c 6f 77 20 69 6c 6c 75 73 74   22 below illust
6620: 72 61 74 65 73 20 74 68 65 20 63 6f 6e 63 65 70  rates the concep
6630: 74 2e 0a 3c 2f 70 3e 0a 0a 3c 74 63 6c 3e 0a 66  t..</p>..<tcl>.f
6640: 69 67 75 72 65 20 32 32 20 23 66 69 67 32 32 20  igure 22 #fig22 
6650: 70 61 72 74 69 61 6c 2d 73 6f 72 74 2e 67 69 66  partial-sort.gif
6660: 20 7b 50 61 72 74 69 61 6c 20 53 6f 72 74 20 42   {Partial Sort B
6670: 79 20 49 6e 64 65 78 7d 0a 3c 2f 74 63 6c 3e 0a  y Index}.</tcl>.
6680: 0a 3c 70 3e 0a 49 6e 20 74 68 65 20 65 78 61 6d  .<p>.In the exam
6690: 70 6c 65 2c 20 69 6e 73 74 65 61 64 20 6f 66 20  ple, instead of 
66a0: 61 20 73 69 6e 67 6c 65 20 73 6f 72 74 20 6f 66  a single sort of
66b0: 20 37 20 65 6c 65 6d 65 6e 74 73 2c 20 74 68 65   7 elements, the
66c0: 72 65 0a 61 72 65 20 35 20 73 6f 72 74 73 20 6f  re.are 5 sorts o
66d0: 66 20 6f 6e 65 2d 65 6c 65 6d 65 6e 74 20 65 61  f one-element ea
66e0: 63 68 20 61 6e 64 20 31 20 73 6f 72 74 20 6f 66  ch and 1 sort of
66f0: 20 32 20 65 6c 65 6d 65 6e 74 73 20 66 6f 72 20   2 elements for 
6700: 74 68 65 0a 63 61 73 65 20 6f 66 20 66 72 75 69  the.case of frui
6710: 74 3d 3d 27 4f 72 61 6e 67 65 27 2e 0a 0a 3c 70  t=='Orange'...<p
6720: 3e 0a 54 68 65 20 61 64 76 61 6e 74 61 67 65 73  >.The advantages
6730: 20 6f 66 20 64 6f 69 6e 67 20 6d 61 6e 79 20 73   of doing many s
6740: 6d 61 6c 6c 65 72 20 73 6f 72 74 73 20 69 6e 73  maller sorts ins
6750: 74 65 61 64 20 6f 66 20 61 20 73 69 6e 67 6c 65  tead of a single
6760: 20 6c 61 72 67 65 20 73 6f 72 74 0a 61 72 65 3a   large sort.are:
6770: 0a 3c 6f 6c 3e 0a 3c 6c 69 3e 4d 75 6c 74 69 70  .<ol>.<li>Multip
6780: 6c 65 20 73 6d 61 6c 6c 20 73 6f 72 74 73 20 63  le small sorts c
6790: 6f 6c 6c 65 63 74 69 76 65 6c 79 20 75 73 65 20  ollectively use 
67a0: 66 65 77 65 72 20 43 50 55 20 63 79 63 6c 65 73  fewer CPU cycles
67b0: 20 74 68 61 6e 20 61 20 73 69 6e 67 6c 65 0a 20   than a single. 
67c0: 20 20 20 6c 61 72 67 65 20 73 6f 72 74 2e 0a 3c     large sort..<
67d0: 6c 69 3e 45 61 63 68 20 73 6d 61 6c 6c 20 73 6f  li>Each small so
67e0: 72 74 20 69 73 20 72 75 6e 20 69 6e 64 65 70 65  rt is run indepe
67f0: 6e 64 65 6e 74 6c 79 2c 20 6d 65 61 6e 69 6e 67  ndently, meaning
6800: 20 74 68 61 74 20 6d 75 63 68 20 6c 65 73 73 20   that much less 
6810: 69 6e 66 6f 72 6d 61 74 69 6f 6e 0a 20 20 20 20  information.    
6820: 6e 65 65 64 73 20 74 6f 20 62 65 20 6b 65 70 74  needs to be kept
6830: 20 69 6e 20 74 65 6d 70 6f 72 61 72 79 20 73 74   in temporary st
6840: 6f 72 61 67 65 20 61 74 20 61 6e 79 20 6f 6e 65  orage at any one
6850: 20 74 69 6d 65 2e 0a 3c 6c 69 3e 54 68 6f 73 65   time..<li>Those
6860: 20 63 6f 6c 75 6d 6e 73 20 6f 66 20 74 68 65 20   columns of the 
6870: 4f 52 44 45 52 20 42 59 20 74 68 61 74 20 61 72  ORDER BY that ar
6880: 65 20 61 6c 72 65 61 64 79 20 69 6e 20 74 68 65  e already in the
6890: 20 63 6f 72 72 65 63 74 20 6f 72 64 65 72 0a 20   correct order. 
68a0: 20 20 20 64 75 65 20 74 6f 20 69 6e 64 65 78 65     due to indexe
68b0: 73 20 63 61 6e 20 62 65 20 6f 6d 69 74 74 65 64  s can be omitted
68c0: 20 66 72 6f 6d 20 74 68 65 20 73 6f 72 74 20 6b   from the sort k
68d0: 65 79 2c 20 66 75 72 74 68 65 72 20 72 65 64 75  ey, further redu
68e0: 63 69 6e 67 0a 20 20 20 20 73 74 6f 72 61 67 65  cing.    storage
68f0: 20 72 65 71 75 69 72 65 6d 65 6e 74 73 20 61 6e   requirements an
6900: 64 20 43 50 55 20 74 69 6d 65 2e 0a 3c 6c 69 3e  d CPU time..<li>
6910: 4f 75 74 70 75 74 20 72 6f 77 73 20 63 61 6e 20  Output rows can 
6920: 62 65 20 72 65 74 75 72 6e 65 64 20 74 6f 20 74  be returned to t
6930: 68 65 20 61 70 70 6c 69 63 61 74 69 6f 6e 20 61  he application a
6940: 73 20 65 61 63 68 20 73 6d 61 6c 6c 20 73 6f 72  s each small sor
6950: 74 0a 20 20 20 20 63 6f 6d 70 6c 65 74 65 73 2c  t.    completes,
6960: 20 61 6e 64 20 77 65 6c 6c 20 62 65 66 6f 72 65   and well before
6970: 20 74 68 65 20 74 61 62 6c 65 20 73 63 61 6e 20   the table scan 
6980: 69 73 20 63 6f 6d 70 6c 65 74 65 2e 0a 3c 6c 69  is complete..<li
6990: 3e 49 66 20 61 20 4c 49 4d 49 54 20 63 6c 61 75  >If a LIMIT clau
69a0: 73 65 20 69 73 20 70 72 65 73 65 6e 74 2c 20 69  se is present, i
69b0: 74 20 6d 69 67 68 74 20 62 65 20 70 6f 73 73 69  t might be possi
69c0: 62 6c 65 20 74 6f 20 61 76 6f 69 64 20 73 63 61  ble to avoid sca
69d0: 6e 6e 69 6e 67 0a 20 20 20 20 74 68 65 20 65 6e  nning.    the en
69e0: 74 69 72 65 20 74 61 62 6c 65 2e 0a 3c 2f 6f 6c  tire table..</ol
69f0: 3e 0a 42 65 63 61 75 73 65 20 6f 66 20 74 68 65  >.Because of the
6a00: 73 65 20 61 64 76 61 6e 74 61 67 65 73 2c 20 53  se advantages, S
6a10: 51 4c 69 74 65 20 61 6c 77 61 79 73 20 74 72 69  QLite always tri
6a20: 65 73 20 74 6f 20 64 6f 20 61 20 70 61 72 74 69  es to do a parti
6a30: 61 6c 20 73 6f 72 74 20 75 73 69 6e 67 20 61 6e  al sort using an
6a40: 0a 69 6e 64 65 78 20 65 76 65 6e 20 69 66 20 61  .index even if a
6a50: 20 63 6f 6d 70 6c 65 74 65 20 73 6f 72 74 20 62   complete sort b
6a60: 79 20 69 6e 64 65 78 20 69 73 20 6e 6f 74 20 70  y index is not p
6a70: 6f 73 73 69 62 6c 65 2e 3c 2f 70 3e 0a 0a 3c 68  ossible.</p>..<h
6a80: 32 3e 34 2e 30 20 57 49 54 48 4f 55 54 20 52 4f  2>4.0 WITHOUT RO
6a90: 57 49 44 20 74 61 62 6c 65 73 3c 2f 68 32 3e 0a  WID tables</h2>.
6aa0: 0a 3c 70 3e 0a 54 68 65 20 62 61 73 69 63 20 70  .<p>.The basic p
6ab0: 72 69 6e 63 69 70 61 6c 73 20 64 65 73 63 72 69  rincipals descri
6ac0: 62 65 64 20 61 62 6f 76 65 20 61 70 70 6c 79 20  bed above apply 
6ad0: 74 6f 20 62 6f 74 68 20 6f 72 64 69 6e 61 72 79  to both ordinary
6ae0: 20 72 6f 77 69 64 20 74 61 62 6c 65 73 0a 61 6e   rowid tables.an
6af0: 64 20 5b 57 49 54 48 4f 55 54 20 52 4f 57 49 44  d [WITHOUT ROWID
6b00: 5d 20 74 61 62 6c 65 73 2e 0a 54 68 65 20 6f 6e  ] tables..The on
6b10: 6c 79 20 64 69 66 66 65 72 65 6e 63 65 20 69 73  ly difference is
6b20: 20 74 68 61 74 20 74 68 65 20 72 6f 77 69 64 20   that the rowid 
6b30: 63 6f 6c 75 6d 6e 20 74 68 61 74 20 73 65 72 76  column that serv
6b40: 65 73 20 61 73 20 74 68 65 20 6b 65 79 20 66 6f  es as the key fo
6b50: 72 0a 74 61 62 6c 65 73 20 61 6e 64 20 74 68 61  r.tables and tha
6b60: 74 20 61 70 70 65 61 72 73 20 61 73 20 74 68 65  t appears as the
6b70: 20 72 69 67 68 74 2d 6d 6f 73 74 20 74 65 72 6d   right-most term
6b80: 20 69 6e 20 69 6e 64 65 78 65 73 20 69 73 20 72   in indexes is r
6b90: 65 70 6c 61 63 65 64 20 62 79 0a 74 68 65 20 50  eplaced by.the P
6ba0: 52 49 4d 41 52 59 20 4b 45 59 2e 0a 3c 2f 70 3e  RIMARY KEY..</p>
6bb0: 0a                                               .