/ Hex Artifact Content
Login

Artifact 8a61a6d731cbe612217edf9eece6197f37c9489e:


0000: 2f 2a 0a 2a 2a 20 32 30 31 31 20 4a 75 6c 79 20  /*.** 2011 July 
0010: 39 0a 2a 2a 0a 2a 2a 20 54 68 65 20 61 75 74 68  9.**.** The auth
0020: 6f 72 20 64 69 73 63 6c 61 69 6d 73 20 63 6f 70  or disclaims cop
0030: 79 72 69 67 68 74 20 74 6f 20 74 68 69 73 20 73  yright to this s
0040: 6f 75 72 63 65 20 63 6f 64 65 2e 20 20 49 6e 20  ource code.  In 
0050: 70 6c 61 63 65 20 6f 66 0a 2a 2a 20 61 20 6c 65  place of.** a le
0060: 67 61 6c 20 6e 6f 74 69 63 65 2c 20 68 65 72 65  gal notice, here
0070: 20 69 73 20 61 20 62 6c 65 73 73 69 6e 67 3a 0a   is a blessing:.
0080: 2a 2a 0a 2a 2a 20 20 20 20 4d 61 79 20 79 6f 75  **.**    May you
0090: 20 64 6f 20 67 6f 6f 64 20 61 6e 64 20 6e 6f 74   do good and not
00a0: 20 65 76 69 6c 2e 0a 2a 2a 20 20 20 20 4d 61 79   evil..**    May
00b0: 20 79 6f 75 20 66 69 6e 64 20 66 6f 72 67 69 76   you find forgiv
00c0: 65 6e 65 73 73 20 66 6f 72 20 79 6f 75 72 73 65  eness for yourse
00d0: 6c 66 20 61 6e 64 20 66 6f 72 67 69 76 65 20 6f  lf and forgive o
00e0: 74 68 65 72 73 2e 0a 2a 2a 20 20 20 20 4d 61 79  thers..**    May
00f0: 20 79 6f 75 20 73 68 61 72 65 20 66 72 65 65 6c   you share freel
0100: 79 2c 20 6e 65 76 65 72 20 74 61 6b 69 6e 67 20  y, never taking 
0110: 6d 6f 72 65 20 74 68 61 6e 20 79 6f 75 20 67 69  more than you gi
0120: 76 65 2e 0a 2a 2a 0a 2a 2a 2a 2a 2a 2a 2a 2a 2a  ve..**.*********
0130: 2a 2a 2a 2a 2a 2a 2a 2a 2a 2a 2a 2a 2a 2a 2a 2a  ****************
0140: 2a 2a 2a 2a 2a 2a 2a 2a 2a 2a 2a 2a 2a 2a 2a 2a  ****************
0150: 2a 2a 2a 2a 2a 2a 2a 2a 2a 2a 2a 2a 2a 2a 2a 2a  ****************
0160: 2a 2a 2a 2a 2a 2a 2a 2a 2a 2a 2a 2a 2a 2a 2a 2a  ****************
0170: 0a 2a 2a 20 54 68 69 73 20 66 69 6c 65 20 63 6f  .** This file co
0180: 6e 74 61 69 6e 73 20 63 6f 64 65 20 66 6f 72 20  ntains code for 
0190: 74 68 65 20 56 64 62 65 53 6f 72 74 65 72 20 6f  the VdbeSorter o
01a0: 62 6a 65 63 74 2c 20 75 73 65 64 20 69 6e 20 63  bject, used in c
01b0: 6f 6e 63 65 72 74 20 77 69 74 68 0a 2a 2a 20 61  oncert with.** a
01c0: 20 56 64 62 65 43 75 72 73 6f 72 20 74 6f 20 73   VdbeCursor to s
01d0: 6f 72 74 20 6c 61 72 67 65 20 6e 75 6d 62 65 72  ort large number
01e0: 73 20 6f 66 20 6b 65 79 73 20 28 61 73 20 6d 61  s of keys (as ma
01f0: 79 20 62 65 20 72 65 71 75 69 72 65 64 2c 20 66  y be required, f
0200: 6f 72 0a 2a 2a 20 65 78 61 6d 70 6c 65 2c 20 62  or.** example, b
0210: 79 20 43 52 45 41 54 45 20 49 4e 44 45 58 20 73  y CREATE INDEX s
0220: 74 61 74 65 6d 65 6e 74 73 20 6f 6e 20 74 61 62  tatements on tab
0230: 6c 65 73 20 74 6f 6f 20 6c 61 72 67 65 20 74 6f  les too large to
0240: 20 66 69 74 20 69 6e 20 6d 61 69 6e 0a 2a 2a 20   fit in main.** 
0250: 6d 65 6d 6f 72 79 29 2e 0a 2a 2f 0a 0a 23 69 6e  memory)..*/..#in
0260: 63 6c 75 64 65 20 22 73 71 6c 69 74 65 49 6e 74  clude "sqliteInt
0270: 2e 68 22 0a 23 69 6e 63 6c 75 64 65 20 22 76 64  .h".#include "vd
0280: 62 65 49 6e 74 2e 68 22 0a 0a 23 69 66 6e 64 65  beInt.h"..#ifnde
0290: 66 20 53 51 4c 49 54 45 5f 4f 4d 49 54 5f 4d 45  f SQLITE_OMIT_ME
02a0: 52 47 45 5f 53 4f 52 54 0a 0a 74 79 70 65 64 65  RGE_SORT..typede
02b0: 66 20 73 74 72 75 63 74 20 56 64 62 65 53 6f 72  f struct VdbeSor
02c0: 74 65 72 49 74 65 72 20 56 64 62 65 53 6f 72 74  terIter VdbeSort
02d0: 65 72 49 74 65 72 3b 0a 0a 2f 2a 0a 2a 2a 20 4e  erIter;../*.** N
02e0: 4f 54 45 53 20 4f 4e 20 44 41 54 41 20 53 54 52  OTES ON DATA STR
02f0: 55 43 54 55 52 45 20 55 53 45 44 20 46 4f 52 20  UCTURE USED FOR 
0300: 4e 2d 57 41 59 20 4d 45 52 47 45 53 3a 0a 2a 2a  N-WAY MERGES:.**
0310: 0a 2a 2a 20 41 73 20 6b 65 79 73 20 61 72 65 20  .** As keys are 
0320: 61 64 64 65 64 20 74 6f 20 74 68 65 20 73 6f 72  added to the sor
0330: 74 65 72 2c 20 74 68 65 79 20 61 72 65 20 77 72  ter, they are wr
0340: 69 74 74 65 6e 20 74 6f 20 64 69 73 6b 20 69 6e  itten to disk in
0350: 20 61 20 73 65 72 69 65 73 0a 2a 2a 20 6f 66 20   a series.** of 
0360: 73 6f 72 74 65 64 20 70 61 63 6b 65 64 2d 6d 65  sorted packed-me
0370: 6d 6f 72 79 2d 61 72 72 61 79 73 20 28 50 4d 41  mory-arrays (PMA
0380: 73 29 2e 20 54 68 65 20 73 69 7a 65 20 6f 66 20  s). The size of 
0390: 65 61 63 68 20 50 4d 41 20 69 73 20 72 6f 75 67  each PMA is roug
03a0: 68 6c 79 0a 2a 2a 20 74 68 65 20 73 61 6d 65 20  hly.** the same 
03b0: 61 73 20 74 68 65 20 63 61 63 68 65 2d 73 69 7a  as the cache-siz
03c0: 65 20 61 6c 6c 6f 77 65 64 20 66 6f 72 20 74 65  e allowed for te
03d0: 6d 70 6f 72 61 72 79 20 64 61 74 61 62 61 73 65  mporary database
03e0: 73 2e 20 49 6e 20 6f 72 64 65 72 0a 2a 2a 20 74  s. In order.** t
03f0: 6f 20 61 6c 6c 6f 77 20 74 68 65 20 63 61 6c 6c  o allow the call
0400: 65 72 20 74 6f 20 65 78 74 72 61 63 74 20 6b 65  er to extract ke
0410: 79 73 20 66 72 6f 6d 20 74 68 65 20 73 6f 72 74  ys from the sort
0420: 65 72 20 69 6e 20 73 6f 72 74 65 64 20 6f 72 64  er in sorted ord
0430: 65 72 2c 0a 2a 2a 20 61 6c 6c 20 50 4d 41 73 20  er,.** all PMAs 
0440: 63 75 72 72 65 6e 74 6c 79 20 73 74 6f 72 65 64  currently stored
0450: 20 6f 6e 20 64 69 73 6b 20 6d 75 73 74 20 62 65   on disk must be
0460: 20 6d 65 72 67 65 64 20 74 6f 67 65 74 68 65 72   merged together
0470: 2e 20 54 68 69 73 20 63 6f 6d 6d 65 6e 74 0a 2a  . This comment.*
0480: 2a 20 64 65 73 63 72 69 62 65 73 20 74 68 65 20  * describes the 
0490: 64 61 74 61 20 73 74 72 75 63 74 75 72 65 20 75  data structure u
04a0: 73 65 64 20 74 6f 20 64 6f 20 73 6f 2e 20 54 68  sed to do so. Th
04b0: 65 20 73 74 72 75 63 74 75 72 65 20 73 75 70 70  e structure supp
04c0: 6f 72 74 73 20 0a 2a 2a 20 6d 65 72 67 69 6e 67  orts .** merging
04d0: 20 61 6e 79 20 6e 75 6d 62 65 72 20 6f 66 20 61   any number of a
04e0: 72 72 61 79 73 20 69 6e 20 61 20 73 69 6e 67 6c  rrays in a singl
04f0: 65 20 70 61 73 73 20 77 69 74 68 20 6e 6f 20 72  e pass with no r
0500: 65 64 75 6e 64 61 6e 74 20 63 6f 6d 70 61 72 69  edundant compari
0510: 73 6f 6e 20 0a 2a 2a 20 6f 70 65 72 61 74 69 6f  son .** operatio
0520: 6e 73 2e 0a 2a 2a 0a 2a 2a 20 54 68 65 20 61 49  ns..**.** The aI
0530: 74 65 72 5b 5d 20 61 72 72 61 79 20 63 6f 6e 74  ter[] array cont
0540: 61 69 6e 73 20 61 6e 20 69 74 65 72 61 74 6f 72  ains an iterator
0550: 20 66 6f 72 20 65 61 63 68 20 6f 66 20 74 68 65   for each of the
0560: 20 50 4d 41 73 20 62 65 69 6e 67 20 6d 65 72 67   PMAs being merg
0570: 65 64 2e 0a 2a 2a 20 41 6e 20 61 49 74 65 72 5b  ed..** An aIter[
0580: 5d 20 69 74 65 72 61 74 6f 72 20 65 69 74 68 65  ] iterator eithe
0590: 72 20 70 6f 69 6e 74 73 20 74 6f 20 61 20 76 61  r points to a va
05a0: 6c 69 64 20 6b 65 79 20 6f 72 20 65 6c 73 65 20  lid key or else 
05b0: 69 73 20 61 74 20 45 4f 46 2e 20 46 6f 72 20 0a  is at EOF. For .
05c0: 2a 2a 20 74 68 65 20 70 75 72 70 6f 73 65 73 20  ** the purposes 
05d0: 6f 66 20 74 68 65 20 70 61 72 61 67 72 61 70 68  of the paragraph
05e0: 73 20 62 65 6c 6f 77 2c 20 77 65 20 61 73 73 75  s below, we assu
05f0: 6d 65 20 74 68 61 74 20 74 68 65 20 61 72 72 61  me that the arra
0600: 79 20 69 73 20 61 63 74 75 61 6c 6c 79 20 0a 2a  y is actually .*
0610: 2a 20 4e 20 65 6c 65 6d 65 6e 74 73 20 69 6e 20  * N elements in 
0620: 73 69 7a 65 2c 20 77 68 65 72 65 20 4e 20 69 73  size, where N is
0630: 20 74 68 65 20 73 6d 61 6c 6c 65 73 74 20 70 6f   the smallest po
0640: 77 65 72 20 6f 66 20 32 20 67 72 65 61 74 65 72  wer of 2 greater
0650: 20 74 6f 20 6f 72 20 65 71 75 61 6c 20 0a 2a 2a   to or equal .**
0660: 20 74 6f 20 74 68 65 20 6e 75 6d 62 65 72 20 6f   to the number o
0670: 66 20 69 74 65 72 61 74 6f 72 73 20 62 65 69 6e  f iterators bein
0680: 67 20 6d 65 72 67 65 64 2e 20 54 68 65 20 65 78  g merged. The ex
0690: 74 72 61 20 61 49 74 65 72 5b 5d 20 65 6c 65 6d  tra aIter[] elem
06a0: 65 6e 74 73 20 61 72 65 20 0a 2a 2a 20 74 72 65  ents are .** tre
06b0: 61 74 65 64 20 61 73 20 69 66 20 74 68 65 79 20  ated as if they 
06c0: 61 72 65 20 65 6d 70 74 79 20 28 61 6c 77 61 79  are empty (alway
06d0: 73 20 61 74 20 45 4f 46 29 2e 0a 2a 2a 0a 2a 2a  s at EOF)..**.**
06e0: 20 54 68 65 20 61 54 72 65 65 5b 5d 20 61 72 72   The aTree[] arr
06f0: 61 79 20 69 73 20 61 6c 73 6f 20 4e 20 65 6c 65  ay is also N ele
0700: 6d 65 6e 74 73 20 69 6e 20 73 69 7a 65 2e 20 54  ments in size. T
0710: 68 65 20 76 61 6c 75 65 20 6f 66 20 4e 20 69 73  he value of N is
0720: 20 73 74 6f 72 65 64 20 69 6e 0a 2a 2a 20 74 68   stored in.** th
0730: 65 20 56 64 62 65 53 6f 72 74 65 72 2e 6e 54 72  e VdbeSorter.nTr
0740: 65 65 20 76 61 72 69 61 62 6c 65 2e 0a 2a 2a 0a  ee variable..**.
0750: 2a 2a 20 54 68 65 20 66 69 6e 61 6c 20 28 4e 2f  ** The final (N/
0760: 32 29 20 65 6c 65 6d 65 6e 74 73 20 6f 66 20 61  2) elements of a
0770: 54 72 65 65 5b 5d 20 63 6f 6e 74 61 69 6e 20 74  Tree[] contain t
0780: 68 65 20 72 65 73 75 6c 74 73 20 6f 66 20 63 6f  he results of co
0790: 6d 70 61 72 69 6e 67 0a 2a 2a 20 70 61 69 72 73  mparing.** pairs
07a0: 20 6f 66 20 69 74 65 72 61 74 6f 72 20 6b 65 79   of iterator key
07b0: 73 20 74 6f 67 65 74 68 65 72 2e 20 45 6c 65 6d  s together. Elem
07c0: 65 6e 74 20 69 20 63 6f 6e 74 61 69 6e 73 20 74  ent i contains t
07d0: 68 65 20 72 65 73 75 6c 74 20 6f 66 20 0a 2a 2a  he result of .**
07e0: 20 63 6f 6d 70 61 72 69 6e 67 20 61 49 74 65 72   comparing aIter
07f0: 5b 32 2a 69 2d 4e 5d 20 61 6e 64 20 61 49 74 65  [2*i-N] and aIte
0800: 72 5b 32 2a 69 2d 4e 2b 31 5d 2e 20 57 68 69 63  r[2*i-N+1]. Whic
0810: 68 65 76 65 72 20 6b 65 79 20 69 73 20 73 6d 61  hever key is sma
0820: 6c 6c 65 72 2c 20 74 68 65 0a 2a 2a 20 61 54 72  ller, the.** aTr
0830: 65 65 20 65 6c 65 6d 65 6e 74 20 69 73 20 73 65  ee element is se
0840: 74 20 74 6f 20 74 68 65 20 69 6e 64 65 78 20 6f  t to the index o
0850: 66 20 69 74 2e 20 0a 2a 2a 0a 2a 2a 20 46 6f 72  f it. .**.** For
0860: 20 74 68 65 20 70 75 72 70 6f 73 65 73 20 6f 66   the purposes of
0870: 20 74 68 69 73 20 63 6f 6d 70 61 72 69 73 6f 6e   this comparison
0880: 2c 20 45 4f 46 20 69 73 20 63 6f 6e 73 69 64 65  , EOF is conside
0890: 72 65 64 20 67 72 65 61 74 65 72 20 74 68 61 6e  red greater than
08a0: 20 61 6e 79 0a 2a 2a 20 6f 74 68 65 72 20 6b 65   any.** other ke
08b0: 79 20 76 61 6c 75 65 2e 20 49 66 20 74 68 65 20  y value. If the 
08c0: 6b 65 79 73 20 61 72 65 20 65 71 75 61 6c 20 28  keys are equal (
08d0: 6f 6e 6c 79 20 70 6f 73 73 69 62 6c 65 20 77 69  only possible wi
08e0: 74 68 20 74 77 6f 20 45 4f 46 0a 2a 2a 20 76 61  th two EOF.** va
08f0: 6c 75 65 73 29 2c 20 69 74 20 64 6f 65 73 6e 27  lues), it doesn'
0900: 74 20 6d 61 74 74 65 72 20 77 68 69 63 68 20 69  t matter which i
0910: 6e 64 65 78 20 69 73 20 73 74 6f 72 65 64 2e 0a  ndex is stored..
0920: 2a 2a 0a 2a 2a 20 54 68 65 20 28 4e 2f 34 29 20  **.** The (N/4) 
0930: 65 6c 65 6d 65 6e 74 73 20 6f 66 20 61 54 72 65  elements of aTre
0940: 65 5b 5d 20 74 68 61 74 20 70 72 65 63 65 65 64  e[] that preceed
0950: 20 74 68 65 20 66 69 6e 61 6c 20 28 4e 2f 32 29   the final (N/2)
0960: 20 64 65 73 63 72 69 62 65 64 20 0a 2a 2a 20 61   described .** a
0970: 62 6f 76 65 20 63 6f 6e 74 61 69 6e 73 20 74 68  bove contains th
0980: 65 20 69 6e 64 65 78 20 6f 66 20 74 68 65 20 73  e index of the s
0990: 6d 61 6c 6c 65 73 74 20 6f 66 20 65 61 63 68 20  mallest of each 
09a0: 62 6c 6f 63 6b 20 6f 66 20 34 20 69 74 65 72 61  block of 4 itera
09b0: 74 6f 72 73 2e 0a 2a 2a 20 41 6e 64 20 73 6f 20  tors..** And so 
09c0: 6f 6e 2e 20 53 6f 20 74 68 61 74 20 61 54 72 65  on. So that aTre
09d0: 65 5b 31 5d 20 63 6f 6e 74 61 69 6e 73 20 74 68  e[1] contains th
09e0: 65 20 69 6e 64 65 78 20 6f 66 20 74 68 65 20 69  e index of the i
09f0: 74 65 72 61 74 6f 72 20 74 68 61 74 20 0a 2a 2a  terator that .**
0a00: 20 63 75 72 72 65 6e 74 6c 79 20 70 6f 69 6e 74   currently point
0a10: 73 20 74 6f 20 74 68 65 20 73 6d 61 6c 6c 65 73  s to the smalles
0a20: 74 20 6b 65 79 20 76 61 6c 75 65 2e 20 61 54 72  t key value. aTr
0a30: 65 65 5b 30 5d 20 69 73 20 75 6e 75 73 65 64 2e  ee[0] is unused.
0a40: 0a 2a 2a 0a 2a 2a 20 45 78 61 6d 70 6c 65 3a 0a  .**.** Example:.
0a50: 2a 2a 0a 2a 2a 20 20 20 20 20 61 49 74 65 72 5b  **.**     aIter[
0a60: 30 5d 20 2d 3e 20 42 61 6e 61 6e 61 0a 2a 2a 20  0] -> Banana.** 
0a70: 20 20 20 20 61 49 74 65 72 5b 31 5d 20 2d 3e 20      aIter[1] -> 
0a80: 46 65 69 6a 6f 61 0a 2a 2a 20 20 20 20 20 61 49  Feijoa.**     aI
0a90: 74 65 72 5b 32 5d 20 2d 3e 20 45 6c 64 65 72 62  ter[2] -> Elderb
0aa0: 65 72 72 79 0a 2a 2a 20 20 20 20 20 61 49 74 65  erry.**     aIte
0ab0: 72 5b 33 5d 20 2d 3e 20 43 75 72 72 61 6e 74 0a  r[3] -> Currant.
0ac0: 2a 2a 20 20 20 20 20 61 49 74 65 72 5b 34 5d 20  **     aIter[4] 
0ad0: 2d 3e 20 47 72 61 70 65 66 72 75 69 74 0a 2a 2a  -> Grapefruit.**
0ae0: 20 20 20 20 20 61 49 74 65 72 5b 35 5d 20 2d 3e       aIter[5] ->
0af0: 20 41 70 70 6c 65 0a 2a 2a 20 20 20 20 20 61 49   Apple.**     aI
0b00: 74 65 72 5b 36 5d 20 2d 3e 20 44 75 72 69 61 6e  ter[6] -> Durian
0b10: 0a 2a 2a 20 20 20 20 20 61 49 74 65 72 5b 37 5d  .**     aIter[7]
0b20: 20 2d 3e 20 45 4f 46 0a 2a 2a 0a 2a 2a 20 20 20   -> EOF.**.**   
0b30: 20 20 61 54 72 65 65 5b 5d 20 3d 20 7b 20 58 2c    aTree[] = { X,
0b40: 20 35 20 20 20 30 2c 20 35 20 20 20 20 30 2c 20   5   0, 5    0, 
0b50: 33 2c 20 35 2c 20 36 20 7d 0a 2a 2a 0a 2a 2a 20  3, 5, 6 }.**.** 
0b60: 54 68 65 20 63 75 72 72 65 6e 74 20 65 6c 65 6d  The current elem
0b70: 65 6e 74 20 69 73 20 22 41 70 70 6c 65 22 20 28  ent is "Apple" (
0b80: 74 68 65 20 76 61 6c 75 65 20 6f 66 20 74 68 65  the value of the
0b90: 20 6b 65 79 20 69 6e 64 69 63 61 74 65 64 20 62   key indicated b
0ba0: 79 20 0a 2a 2a 20 69 74 65 72 61 74 6f 72 20 35  y .** iterator 5
0bb0: 29 2e 20 57 68 65 6e 20 74 68 65 20 4e 65 78 74  ). When the Next
0bc0: 28 29 20 6f 70 65 72 61 74 69 6f 6e 20 69 73 20  () operation is 
0bd0: 69 6e 76 6f 6b 65 64 2c 20 69 74 65 72 61 74 6f  invoked, iterato
0be0: 72 20 35 20 77 69 6c 6c 0a 2a 2a 20 62 65 20 61  r 5 will.** be a
0bf0: 64 76 61 6e 63 65 64 20 74 6f 20 74 68 65 20 6e  dvanced to the n
0c00: 65 78 74 20 6b 65 79 20 69 6e 20 69 74 73 20 73  ext key in its s
0c10: 65 67 6d 65 6e 74 2e 20 53 61 79 20 74 68 65 20  egment. Say the 
0c20: 6e 65 78 74 20 6b 65 79 20 69 73 0a 2a 2a 20 22  next key is.** "
0c30: 45 67 67 70 6c 61 6e 74 22 3a 0a 2a 2a 0a 2a 2a  Eggplant":.**.**
0c40: 20 20 20 20 20 61 49 74 65 72 5b 35 5d 20 2d 3e       aIter[5] ->
0c50: 20 45 67 67 70 6c 61 6e 74 0a 2a 2a 0a 2a 2a 20   Eggplant.**.** 
0c60: 54 68 65 20 63 6f 6e 74 65 6e 74 73 20 6f 66 20  The contents of 
0c70: 61 54 72 65 65 5b 5d 20 61 72 65 20 75 70 64 61  aTree[] are upda
0c80: 74 65 64 20 66 69 72 73 74 20 62 79 20 63 6f 6d  ted first by com
0c90: 70 61 72 69 6e 67 20 74 68 65 20 6e 65 77 20 69  paring the new i
0ca0: 74 65 72 61 74 6f 72 0a 2a 2a 20 35 20 6b 65 79  terator.** 5 key
0cb0: 20 74 6f 20 74 68 65 20 63 75 72 72 65 6e 74 20   to the current 
0cc0: 6b 65 79 20 6f 66 20 69 74 65 72 61 74 6f 72 20  key of iterator 
0cd0: 34 20 28 73 74 69 6c 6c 20 22 47 72 61 70 65 66  4 (still "Grapef
0ce0: 72 75 69 74 22 29 2e 20 54 68 65 20 69 74 65 72  ruit"). The iter
0cf0: 61 74 6f 72 0a 2a 2a 20 35 20 76 61 6c 75 65 20  ator.** 5 value 
0d00: 69 73 20 73 74 69 6c 6c 20 73 6d 61 6c 6c 65 72  is still smaller
0d10: 2c 20 73 6f 20 61 54 72 65 65 5b 36 5d 20 69 73  , so aTree[6] is
0d20: 20 73 65 74 20 74 6f 20 35 2e 20 41 6e 64 20 73   set to 5. And s
0d30: 6f 20 6f 6e 20 75 70 20 74 68 65 20 74 72 65 65  o on up the tree
0d40: 2e 0a 2a 2a 20 54 68 65 20 76 61 6c 75 65 20 6f  ..** The value o
0d50: 66 20 69 74 65 72 61 74 6f 72 20 36 20 2d 20 22  f iterator 6 - "
0d60: 44 75 72 69 61 6e 22 20 2d 20 69 73 20 6e 6f 77  Durian" - is now
0d70: 20 73 6d 61 6c 6c 65 72 20 74 68 61 6e 20 74 68   smaller than th
0d80: 61 74 20 6f 66 20 69 74 65 72 61 74 6f 72 0a 2a  at of iterator.*
0d90: 2a 20 35 2c 20 73 6f 20 61 54 72 65 65 5b 33 5d  * 5, so aTree[3]
0da0: 20 69 73 20 73 65 74 20 74 6f 20 36 2e 20 4b 65   is set to 6. Ke
0db0: 79 20 30 20 69 73 20 73 6d 61 6c 6c 65 72 20 74  y 0 is smaller t
0dc0: 68 61 6e 20 6b 65 79 20 36 20 28 42 61 6e 61 6e  han key 6 (Banan
0dd0: 61 3c 44 75 72 69 61 6e 29 2c 0a 2a 2a 20 73 6f  a<Durian),.** so
0de0: 20 74 68 65 20 76 61 6c 75 65 20 77 72 69 74 74   the value writt
0df0: 65 6e 20 69 6e 74 6f 20 65 6c 65 6d 65 6e 74 20  en into element 
0e00: 31 20 6f 66 20 74 68 65 20 61 72 72 61 79 20 69  1 of the array i
0e10: 73 20 30 2e 20 41 73 20 66 6f 6c 6c 6f 77 73 3a  s 0. As follows:
0e20: 0a 2a 2a 0a 2a 2a 20 20 20 20 20 61 54 72 65 65  .**.**     aTree
0e30: 5b 5d 20 3d 20 7b 20 58 2c 20 30 20 20 20 30 2c  [] = { X, 0   0,
0e40: 20 36 20 20 20 20 30 2c 20 33 2c 20 35 2c 20 36   6    0, 3, 5, 6
0e50: 20 7d 0a 2a 2a 0a 2a 2a 20 49 6e 20 6f 74 68 65   }.**.** In othe
0e60: 72 20 77 6f 72 64 73 2c 20 65 61 63 68 20 74 69  r words, each ti
0e70: 6d 65 20 77 65 20 61 64 76 61 6e 63 65 20 74 6f  me we advance to
0e80: 20 74 68 65 20 6e 65 78 74 20 73 6f 72 74 65 72   the next sorter
0e90: 20 65 6c 65 6d 65 6e 74 2c 20 6c 6f 67 32 28 4e   element, log2(N
0ea0: 29 0a 2a 2a 20 6b 65 79 20 63 6f 6d 70 61 72 69  ).** key compari
0eb0: 73 6f 6e 20 6f 70 65 72 61 74 69 6f 6e 73 20 61  son operations a
0ec0: 72 65 20 72 65 71 75 69 72 65 64 2c 20 77 68 65  re required, whe
0ed0: 72 65 20 4e 20 69 73 20 74 68 65 20 6e 75 6d 62  re N is the numb
0ee0: 65 72 20 6f 66 20 73 65 67 6d 65 6e 74 73 0a 2a  er of segments.*
0ef0: 2a 20 62 65 69 6e 67 20 6d 65 72 67 65 64 20 28  * being merged (
0f00: 72 6f 75 6e 64 65 64 20 75 70 20 74 6f 20 74 68  rounded up to th
0f10: 65 20 6e 65 78 74 20 70 6f 77 65 72 20 6f 66 20  e next power of 
0f20: 32 29 2e 0a 2a 2f 0a 73 74 72 75 63 74 20 56 64  2)..*/.struct Vd
0f30: 62 65 53 6f 72 74 65 72 20 7b 0a 20 20 69 6e 74  beSorter {.  int
0f40: 20 6e 57 6f 72 6b 69 6e 67 3b 20 20 20 20 20 20   nWorking;      
0f50: 20 20 20 20 20 20 20 20 20 20 20 20 20 2f 2a 20               /* 
0f60: 53 74 61 72 74 20 61 20 6e 65 77 20 62 2d 74 72  Start a new b-tr
0f70: 65 65 20 61 66 74 65 72 20 74 68 69 73 20 6d 61  ee after this ma
0f80: 6e 79 20 70 61 67 65 73 20 2a 2f 0a 20 20 69 6e  ny pages */.  in
0f90: 74 20 6e 42 74 72 65 65 3b 20 20 20 20 20 20 20  t nBtree;       
0fa0: 20 20 20 20 20 20 20 20 20 20 20 20 20 20 2f 2a                /*
0fb0: 20 43 75 72 72 65 6e 74 20 73 69 7a 65 20 6f 66   Current size of
0fc0: 20 62 2d 74 72 65 65 20 63 6f 6e 74 65 6e 74 73   b-tree contents
0fd0: 20 61 73 20 50 4d 41 20 2a 2f 0a 20 20 69 6e 74   as PMA */.  int
0fe0: 20 6e 54 72 65 65 3b 20 20 20 20 20 20 20 20 20   nTree;         
0ff0: 20 20 20 20 20 20 20 20 20 20 20 20 20 2f 2a 20               /* 
1000: 55 73 65 64 20 73 69 7a 65 20 6f 66 20 61 54 72  Used size of aTr
1010: 65 65 2f 61 49 74 65 72 20 28 70 6f 77 65 72 20  ee/aIter (power 
1020: 6f 66 20 32 29 20 2a 2f 0a 20 20 56 64 62 65 53  of 2) */.  VdbeS
1030: 6f 72 74 65 72 49 74 65 72 20 2a 61 49 74 65 72  orterIter *aIter
1040: 3b 20 20 20 20 20 20 20 20 20 20 2f 2a 20 41 72  ;          /* Ar
1050: 72 61 79 20 6f 66 20 69 74 65 72 61 74 6f 72 73  ray of iterators
1060: 20 74 6f 20 6d 65 72 67 65 20 2a 2f 0a 20 20 69   to merge */.  i
1070: 6e 74 20 2a 61 54 72 65 65 3b 20 20 20 20 20 20  nt *aTree;      
1080: 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20 2f                 /
1090: 2a 20 43 75 72 72 65 6e 74 20 73 74 61 74 65 20  * Current state 
10a0: 6f 66 20 69 6e 63 72 65 6d 65 6e 74 61 6c 20 6d  of incremental m
10b0: 65 72 67 65 20 2a 2f 0a 20 20 69 36 34 20 69 57  erge */.  i64 iW
10c0: 72 69 74 65 4f 66 66 3b 20 20 20 20 20 20 20 20  riteOff;        
10d0: 20 20 20 20 20 20 20 20 20 20 2f 2a 20 43 75 72            /* Cur
10e0: 72 65 6e 74 20 77 72 69 74 65 20 6f 66 66 73 65  rent write offse
10f0: 74 20 77 69 74 68 69 6e 20 66 69 6c 65 20 70 54  t within file pT
1100: 65 6d 70 31 20 2a 2f 0a 20 20 69 36 34 20 69 52  emp1 */.  i64 iR
1110: 65 61 64 4f 66 66 3b 20 20 20 20 20 20 20 20 20  eadOff;         
1120: 20 20 20 20 20 20 20 20 20 20 2f 2a 20 43 75 72            /* Cur
1130: 72 65 6e 74 20 72 65 61 64 20 6f 66 66 73 65 74  rent read offset
1140: 20 77 69 74 68 69 6e 20 66 69 6c 65 20 70 54 65   within file pTe
1150: 6d 70 31 20 2a 2f 0a 20 20 73 71 6c 69 74 65 33  mp1 */.  sqlite3
1160: 5f 66 69 6c 65 20 2a 70 54 65 6d 70 31 3b 20 20  _file *pTemp1;  
1170: 20 20 20 20 20 20 20 20 20 2f 2a 20 50 4d 41 20           /* PMA 
1180: 66 69 6c 65 20 31 20 2a 2f 0a 20 20 69 6e 74 20  file 1 */.  int 
1190: 6e 50 4d 41 3b 20 20 20 20 20 20 20 20 20 20 20  nPMA;           
11a0: 20 20 20 20 20 20 20 20 20 20 20 20 2f 2a 20 4e              /* N
11b0: 75 6d 62 65 72 20 6f 66 20 50 4d 41 73 20 73 74  umber of PMAs st
11c0: 6f 72 65 64 20 69 6e 20 70 54 65 6d 70 31 20 2a  ored in pTemp1 *
11d0: 2f 0a 7d 3b 0a 0a 2f 2a 0a 2a 2a 20 54 68 65 20  /.};../*.** The 
11e0: 66 6f 6c 6c 6f 77 69 6e 67 20 74 79 70 65 20 69  following type i
11f0: 73 20 61 6e 20 69 74 65 72 61 74 6f 72 20 66 6f  s an iterator fo
1200: 72 20 61 20 50 4d 41 2e 20 49 74 20 63 61 63 68  r a PMA. It cach
1210: 65 73 20 74 68 65 20 63 75 72 72 65 6e 74 20 6b  es the current k
1220: 65 79 20 69 6e 20 0a 2a 2a 20 76 61 72 69 61 62  ey in .** variab
1230: 6c 65 73 20 6e 4b 65 79 2f 61 4b 65 79 2e 20 49  les nKey/aKey. I
1240: 66 20 74 68 65 20 69 74 65 72 61 74 6f 72 20 69  f the iterator i
1250: 73 20 61 74 20 45 4f 46 2c 20 70 46 69 6c 65 3d  s at EOF, pFile=
1260: 3d 30 2e 0a 2a 2f 0a 73 74 72 75 63 74 20 56 64  =0..*/.struct Vd
1270: 62 65 53 6f 72 74 65 72 49 74 65 72 20 7b 0a 20  beSorterIter {. 
1280: 20 69 36 34 20 69 52 65 61 64 4f 66 66 3b 20 20   i64 iReadOff;  
1290: 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20                  
12a0: 20 2f 2a 20 43 75 72 72 65 6e 74 20 72 65 61 64   /* Current read
12b0: 20 6f 66 66 73 65 74 20 2a 2f 0a 20 20 69 36 34   offset */.  i64
12c0: 20 69 45 6f 66 3b 20 20 20 20 20 20 20 20 20 20   iEof;          
12d0: 20 20 20 20 20 20 20 20 20 20 20 20 20 2f 2a 20               /* 
12e0: 31 20 62 79 74 65 20 70 61 73 74 20 45 4f 46 20  1 byte past EOF 
12f0: 66 6f 72 20 74 68 69 73 20 69 74 65 72 61 74 6f  for this iterato
1300: 72 20 2a 2f 0a 20 20 73 71 6c 69 74 65 33 5f 66  r */.  sqlite3_f
1310: 69 6c 65 20 2a 70 46 69 6c 65 3b 20 20 20 20 20  ile *pFile;     
1320: 20 20 20 20 20 20 20 2f 2a 20 46 69 6c 65 20 69         /* File i
1330: 74 65 72 61 74 6f 72 20 69 73 20 72 65 61 64 69  terator is readi
1340: 6e 67 20 66 72 6f 6d 20 2a 2f 0a 20 20 69 6e 74  ng from */.  int
1350: 20 6e 41 6c 6c 6f 63 3b 20 20 20 20 20 20 20 20   nAlloc;        
1360: 20 20 20 20 20 20 20 20 20 20 20 20 20 2f 2a 20               /* 
1370: 42 79 74 65 73 20 6f 66 20 73 70 61 63 65 20 61  Bytes of space a
1380: 74 20 61 41 6c 6c 6f 63 20 2a 2f 0a 20 20 75 38  t aAlloc */.  u8
1390: 20 2a 61 41 6c 6c 6f 63 3b 20 20 20 20 20 20 20   *aAlloc;       
13a0: 20 20 20 20 20 20 20 20 20 20 20 20 20 20 2f 2a                /*
13b0: 20 41 6c 6c 6f 63 61 74 65 64 20 73 70 61 63 65   Allocated space
13c0: 20 2a 2f 0a 20 20 69 6e 74 20 6e 4b 65 79 3b 20   */.  int nKey; 
13d0: 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20                  
13e0: 20 20 20 20 20 20 2f 2a 20 4e 75 6d 62 65 72 20        /* Number 
13f0: 6f 66 20 62 79 74 65 73 20 69 6e 20 6b 65 79 20  of bytes in key 
1400: 2a 2f 0a 20 20 75 38 20 2a 61 4b 65 79 3b 20 20  */.  u8 *aKey;  
1410: 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20                  
1420: 20 20 20 20 20 2f 2a 20 50 6f 69 6e 74 65 72 20       /* Pointer 
1430: 74 6f 20 63 75 72 72 65 6e 74 20 6b 65 79 20 2a  to current key *
1440: 2f 0a 7d 3b 0a 0a 2f 2a 20 4d 69 6e 69 6d 75 6d  /.};../* Minimum
1450: 20 61 6c 6c 6f 77 61 62 6c 65 20 76 61 6c 75 65   allowable value
1460: 20 66 6f 72 20 74 68 65 20 56 64 62 65 53 6f 72   for the VdbeSor
1470: 74 65 72 2e 6e 57 6f 72 6b 69 6e 67 20 76 61 72  ter.nWorking var
1480: 69 61 62 6c 65 20 2a 2f 0a 23 64 65 66 69 6e 65  iable */.#define
1490: 20 53 4f 52 54 45 52 5f 4d 49 4e 5f 57 4f 52 4b   SORTER_MIN_WORK
14a0: 49 4e 47 20 31 30 0a 0a 2f 2a 20 4d 61 78 69 6d  ING 10../* Maxim
14b0: 75 6d 20 6e 75 6d 62 65 72 20 6f 66 20 73 65 67  um number of seg
14c0: 6d 65 6e 74 73 20 74 6f 20 6d 65 72 67 65 20 69  ments to merge i
14d0: 6e 20 61 20 73 69 6e 67 6c 65 20 70 61 73 73 2e  n a single pass.
14e0: 20 2a 2f 0a 23 64 65 66 69 6e 65 20 53 4f 52 54   */.#define SORT
14f0: 45 52 5f 4d 41 58 5f 4d 45 52 47 45 5f 43 4f 55  ER_MAX_MERGE_COU
1500: 4e 54 20 31 36 0a 0a 2f 2a 0a 2a 2a 20 46 72 65  NT 16../*.** Fre
1510: 65 20 61 6c 6c 20 6d 65 6d 6f 72 79 20 62 65 6c  e all memory bel
1520: 6f 6e 67 69 6e 67 20 74 6f 20 74 68 65 20 56 64  onging to the Vd
1530: 62 65 53 6f 72 74 65 72 49 74 65 72 20 6f 62 6a  beSorterIter obj
1540: 65 63 74 20 70 61 73 73 65 64 20 61 73 20 74 68  ect passed as th
1550: 65 20 73 65 63 6f 6e 64 0a 2a 2a 20 61 72 67 75  e second.** argu
1560: 6d 65 6e 74 2e 20 41 6c 6c 20 73 74 72 75 63 74  ment. All struct
1570: 75 72 65 20 66 69 65 6c 64 73 20 61 72 65 20 73  ure fields are s
1580: 65 74 20 74 6f 20 7a 65 72 6f 20 62 65 66 6f 72  et to zero befor
1590: 65 20 72 65 74 75 72 6e 69 6e 67 2e 0a 2a 2f 0a  e returning..*/.
15a0: 73 74 61 74 69 63 20 76 6f 69 64 20 76 64 62 65  static void vdbe
15b0: 53 6f 72 74 65 72 49 74 65 72 5a 65 72 6f 28 73  SorterIterZero(s
15c0: 71 6c 69 74 65 33 20 2a 64 62 2c 20 56 64 62 65  qlite3 *db, Vdbe
15d0: 53 6f 72 74 65 72 49 74 65 72 20 2a 70 49 74 65  SorterIter *pIte
15e0: 72 29 7b 0a 20 20 73 71 6c 69 74 65 33 44 62 46  r){.  sqlite3DbF
15f0: 72 65 65 28 64 62 2c 20 70 49 74 65 72 2d 3e 61  ree(db, pIter->a
1600: 41 6c 6c 6f 63 29 3b 0a 20 20 6d 65 6d 73 65 74  Alloc);.  memset
1610: 28 70 49 74 65 72 2c 20 30 2c 20 73 69 7a 65 6f  (pIter, 0, sizeo
1620: 66 28 56 64 62 65 53 6f 72 74 65 72 49 74 65 72  f(VdbeSorterIter
1630: 29 29 3b 0a 7d 0a 0a 2f 2a 0a 2a 2a 20 41 64 76  ));.}../*.** Adv
1640: 61 6e 63 65 20 69 74 65 72 61 74 6f 72 20 70 49  ance iterator pI
1650: 74 65 72 20 74 6f 20 74 68 65 20 6e 65 78 74 20  ter to the next 
1660: 6b 65 79 20 69 6e 20 69 74 73 20 50 4d 41 2e 20  key in its PMA. 
1670: 52 65 74 75 72 6e 20 53 51 4c 49 54 45 5f 4f 4b  Return SQLITE_OK
1680: 20 69 66 0a 2a 2a 20 6e 6f 20 65 72 72 6f 72 20   if.** no error 
1690: 6f 63 63 75 72 73 2c 20 6f 72 20 61 6e 20 53 51  occurs, or an SQ
16a0: 4c 69 74 65 20 65 72 72 6f 72 20 63 6f 64 65 20  Lite error code 
16b0: 69 66 20 6f 6e 65 20 64 6f 65 73 2e 0a 2a 2f 0a  if one does..*/.
16c0: 73 74 61 74 69 63 20 69 6e 74 20 76 64 62 65 53  static int vdbeS
16d0: 6f 72 74 65 72 49 74 65 72 4e 65 78 74 28 0a 20  orterIterNext(. 
16e0: 20 73 71 6c 69 74 65 33 20 2a 64 62 2c 20 20 20   sqlite3 *db,   
16f0: 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20                  
1700: 20 2f 2a 20 44 61 74 61 62 61 73 65 20 68 61 6e   /* Database han
1710: 64 6c 65 20 28 66 6f 72 20 73 71 6c 69 74 65 33  dle (for sqlite3
1720: 44 62 4d 61 6c 6c 6f 63 28 29 20 29 20 2a 2f 0a  DbMalloc() ) */.
1730: 20 20 56 64 62 65 53 6f 72 74 65 72 49 74 65 72    VdbeSorterIter
1740: 20 2a 70 49 74 65 72 20 20 20 20 20 20 20 20 20   *pIter         
1750: 20 20 2f 2a 20 49 74 65 72 61 74 6f 72 20 74 6f    /* Iterator to
1760: 20 61 64 76 61 6e 63 65 20 2a 2f 0a 29 7b 0a 20   advance */.){. 
1770: 20 69 6e 74 20 72 63 3b 20 20 20 20 20 20 20 20   int rc;        
1780: 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20                  
1790: 20 2f 2a 20 52 65 74 75 72 6e 20 43 6f 64 65 20   /* Return Code 
17a0: 2a 2f 0a 20 20 69 6e 74 20 6e 52 65 61 64 3b 20  */.  int nRead; 
17b0: 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20                  
17c0: 20 20 20 20 20 2f 2a 20 4e 75 6d 62 65 72 20 6f       /* Number o
17d0: 66 20 62 79 74 65 73 20 72 65 61 64 20 2a 2f 0a  f bytes read */.
17e0: 20 20 69 6e 74 20 6e 52 65 63 3b 20 20 20 20 20    int nRec;     
17f0: 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20                  
1800: 20 20 2f 2a 20 53 69 7a 65 20 6f 66 20 72 65 63    /* Size of rec
1810: 6f 72 64 20 69 6e 20 62 79 74 65 73 20 2a 2f 0a  ord in bytes */.
1820: 20 20 69 6e 74 20 69 4f 66 66 3b 20 20 20 20 20    int iOff;     
1830: 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20                  
1840: 20 20 2f 2a 20 53 69 7a 65 20 6f 66 20 73 65 72    /* Size of ser
1850: 69 61 6c 69 7a 65 64 20 73 69 7a 65 20 76 61 72  ialized size var
1860: 69 6e 74 20 69 6e 20 62 79 74 65 73 20 2a 2f 0a  int in bytes */.
1870: 0a 20 20 6e 52 65 61 64 20 3d 20 70 49 74 65 72  .  nRead = pIter
1880: 2d 3e 69 45 6f 66 20 2d 20 70 49 74 65 72 2d 3e  ->iEof - pIter->
1890: 69 52 65 61 64 4f 66 66 3b 0a 20 20 69 66 28 20  iReadOff;.  if( 
18a0: 6e 52 65 61 64 3e 35 20 29 20 6e 52 65 61 64 20  nRead>5 ) nRead 
18b0: 3d 20 35 3b 0a 20 20 69 66 28 20 6e 52 65 61 64  = 5;.  if( nRead
18c0: 3c 3d 30 20 29 7b 0a 20 20 20 20 2f 2a 20 54 68  <=0 ){.    /* Th
18d0: 69 73 20 69 73 20 61 6e 20 45 4f 46 20 63 6f 6e  is is an EOF con
18e0: 64 69 74 69 6f 6e 20 2a 2f 0a 20 20 20 20 76 64  dition */.    vd
18f0: 62 65 53 6f 72 74 65 72 49 74 65 72 5a 65 72 6f  beSorterIterZero
1900: 28 64 62 2c 20 70 49 74 65 72 29 3b 0a 20 20 20  (db, pIter);.   
1910: 20 72 65 74 75 72 6e 20 53 51 4c 49 54 45 5f 4f   return SQLITE_O
1920: 4b 3b 0a 20 20 7d 0a 0a 20 20 72 63 20 3d 20 73  K;.  }..  rc = s
1930: 71 6c 69 74 65 33 4f 73 52 65 61 64 28 70 49 74  qlite3OsRead(pIt
1940: 65 72 2d 3e 70 46 69 6c 65 2c 20 70 49 74 65 72  er->pFile, pIter
1950: 2d 3e 61 41 6c 6c 6f 63 2c 20 6e 52 65 61 64 2c  ->aAlloc, nRead,
1960: 20 70 49 74 65 72 2d 3e 69 52 65 61 64 4f 66 66   pIter->iReadOff
1970: 29 3b 0a 20 20 69 4f 66 66 20 3d 20 67 65 74 56  );.  iOff = getV
1980: 61 72 69 6e 74 33 32 28 70 49 74 65 72 2d 3e 61  arint32(pIter->a
1990: 41 6c 6c 6f 63 2c 20 6e 52 65 63 29 3b 0a 0a 20  Alloc, nRec);.. 
19a0: 20 69 66 28 20 72 63 3d 3d 53 51 4c 49 54 45 5f   if( rc==SQLITE_
19b0: 4f 4b 20 26 26 20 28 69 4f 66 66 2b 6e 52 65 63  OK && (iOff+nRec
19c0: 29 3e 6e 52 65 61 64 20 29 7b 0a 20 20 20 20 69  )>nRead ){.    i
19d0: 6e 74 20 6e 52 65 61 64 32 3b 20 20 20 20 20 20  nt nRead2;      
19e0: 20 20 20 20 20 20 20 20 20 20 20 20 20 2f 2a 20               /* 
19f0: 4e 75 6d 62 65 72 20 6f 66 20 65 78 74 72 61 20  Number of extra 
1a00: 62 79 74 65 73 20 74 6f 20 72 65 61 64 20 2a 2f  bytes to read */
1a10: 0a 20 20 20 20 69 66 28 20 28 69 4f 66 66 2b 6e  .    if( (iOff+n
1a20: 52 65 63 29 3e 70 49 74 65 72 2d 3e 6e 41 6c 6c  Rec)>pIter->nAll
1a30: 6f 63 20 29 7b 0a 20 20 20 20 20 20 69 6e 74 20  oc ){.      int 
1a40: 6e 4e 65 77 20 3d 20 70 49 74 65 72 2d 3e 6e 41  nNew = pIter->nA
1a50: 6c 6c 6f 63 2a 32 3b 0a 20 20 20 20 20 20 77 68  lloc*2;.      wh
1a60: 69 6c 65 28 20 28 69 4f 66 66 2b 6e 52 65 63 29  ile( (iOff+nRec)
1a70: 3e 6e 4e 65 77 20 29 20 6e 4e 65 77 20 3d 20 6e  >nNew ) nNew = n
1a80: 4e 65 77 2a 32 3b 0a 20 20 20 20 20 20 70 49 74  New*2;.      pIt
1a90: 65 72 2d 3e 61 41 6c 6c 6f 63 20 3d 20 73 71 6c  er->aAlloc = sql
1aa0: 69 74 65 33 44 62 52 65 61 6c 6c 6f 63 4f 72 46  ite3DbReallocOrF
1ab0: 72 65 65 28 64 62 2c 20 70 49 74 65 72 2d 3e 61  ree(db, pIter->a
1ac0: 41 6c 6c 6f 63 2c 20 6e 4e 65 77 29 3b 0a 20 20  Alloc, nNew);.  
1ad0: 20 20 20 20 69 66 28 20 21 70 49 74 65 72 2d 3e      if( !pIter->
1ae0: 61 41 6c 6c 6f 63 20 29 20 72 65 74 75 72 6e 20  aAlloc ) return 
1af0: 53 51 4c 49 54 45 5f 4e 4f 4d 45 4d 3b 0a 20 20  SQLITE_NOMEM;.  
1b00: 20 20 20 20 70 49 74 65 72 2d 3e 6e 41 6c 6c 6f      pIter->nAllo
1b10: 63 20 3d 20 6e 4e 65 77 3b 0a 20 20 20 20 7d 0a  c = nNew;.    }.
1b20: 0a 20 20 20 20 6e 52 65 61 64 32 20 3d 20 69 4f  .    nRead2 = iO
1b30: 66 66 20 2b 20 6e 52 65 63 20 2d 20 6e 52 65 61  ff + nRec - nRea
1b40: 64 3b 0a 20 20 20 20 72 63 20 3d 20 73 71 6c 69  d;.    rc = sqli
1b50: 74 65 33 4f 73 52 65 61 64 28 0a 20 20 20 20 20  te3OsRead(.     
1b60: 20 20 20 70 49 74 65 72 2d 3e 70 46 69 6c 65 2c     pIter->pFile,
1b70: 20 26 70 49 74 65 72 2d 3e 61 41 6c 6c 6f 63 5b   &pIter->aAlloc[
1b80: 6e 52 65 61 64 5d 2c 20 6e 52 65 61 64 32 2c 20  nRead], nRead2, 
1b90: 70 49 74 65 72 2d 3e 69 52 65 61 64 4f 66 66 2b  pIter->iReadOff+
1ba0: 6e 52 65 61 64 0a 20 20 20 20 29 3b 0a 20 20 7d  nRead.    );.  }
1bb0: 0a 0a 20 20 61 73 73 65 72 74 28 20 6e 52 65 63  ..  assert( nRec
1bc0: 3e 30 20 7c 7c 20 72 63 21 3d 53 51 4c 49 54 45  >0 || rc!=SQLITE
1bd0: 5f 4f 4b 20 29 3b 0a 20 20 70 49 74 65 72 2d 3e  _OK );.  pIter->
1be0: 69 52 65 61 64 4f 66 66 20 2b 3d 20 69 4f 66 66  iReadOff += iOff
1bf0: 2b 6e 52 65 63 3b 0a 20 20 70 49 74 65 72 2d 3e  +nRec;.  pIter->
1c00: 6e 4b 65 79 20 3d 20 6e 52 65 63 3b 0a 20 20 70  nKey = nRec;.  p
1c10: 49 74 65 72 2d 3e 61 4b 65 79 20 3d 20 26 70 49  Iter->aKey = &pI
1c20: 74 65 72 2d 3e 61 41 6c 6c 6f 63 5b 69 4f 66 66  ter->aAlloc[iOff
1c30: 5d 3b 0a 20 20 72 65 74 75 72 6e 20 72 63 3b 0a  ];.  return rc;.
1c40: 7d 0a 0a 2f 2a 0a 2a 2a 20 57 72 69 74 65 20 61  }../*.** Write a
1c50: 20 73 69 6e 67 6c 65 20 76 61 72 69 6e 74 2c 20   single varint, 
1c60: 76 61 6c 75 65 20 69 56 61 6c 2c 20 74 6f 20 66  value iVal, to f
1c70: 69 6c 65 2d 64 65 73 63 72 69 70 74 6f 72 20 70  ile-descriptor p
1c80: 46 69 6c 65 2e 20 52 65 74 75 72 6e 0a 2a 2a 20  File. Return.** 
1c90: 53 51 4c 49 54 45 5f 4f 4b 20 69 66 20 73 75 63  SQLITE_OK if suc
1ca0: 63 65 73 73 66 75 6c 2c 20 6f 72 20 61 6e 20 53  cessful, or an S
1cb0: 51 4c 69 74 65 20 65 72 72 6f 72 20 63 6f 64 65  QLite error code
1cc0: 20 69 66 20 73 6f 6d 65 20 65 72 72 6f 72 20 6f   if some error o
1cd0: 63 63 75 72 73 2e 0a 2a 2a 0a 2a 2a 20 54 68 65  ccurs..**.** The
1ce0: 20 76 61 6c 75 65 20 6f 66 20 2a 70 69 4f 66 66   value of *piOff
1cf0: 73 65 74 20 77 68 65 6e 20 74 68 69 73 20 66 75  set when this fu
1d00: 6e 63 74 69 6f 6e 20 69 73 20 63 61 6c 6c 65 64  nction is called
1d10: 20 69 73 20 75 73 65 64 20 61 73 20 74 68 65 20   is used as the 
1d20: 62 79 74 65 0a 2a 2a 20 6f 66 66 73 65 74 20 69  byte.** offset i
1d30: 6e 20 66 69 6c 65 20 70 46 69 6c 65 20 74 6f 20  n file pFile to 
1d40: 77 72 69 74 65 20 74 6f 2e 20 42 65 66 6f 72 65  write to. Before
1d50: 20 72 65 74 75 72 6e 69 6e 67 2c 20 2a 70 69 4f   returning, *piO
1d60: 66 66 73 65 74 20 69 73 20 0a 2a 2a 20 69 6e 63  ffset is .** inc
1d70: 72 65 6d 65 6e 74 65 64 20 62 79 20 74 68 65 20  remented by the 
1d80: 6e 75 6d 62 65 72 20 6f 66 20 62 79 74 65 73 20  number of bytes 
1d90: 77 72 69 74 74 65 6e 2e 0a 2a 2f 0a 73 74 61 74  written..*/.stat
1da0: 69 63 20 69 6e 74 20 76 64 62 65 53 6f 72 74 65  ic int vdbeSorte
1db0: 72 57 72 69 74 65 56 61 72 69 6e 74 28 0a 20 20  rWriteVarint(.  
1dc0: 73 71 6c 69 74 65 33 5f 66 69 6c 65 20 2a 70 46  sqlite3_file *pF
1dd0: 69 6c 65 2c 20 20 20 20 20 20 20 20 20 20 20 20  ile,            
1de0: 2f 2a 20 46 69 6c 65 20 74 6f 20 77 72 69 74 65  /* File to write
1df0: 20 74 6f 20 2a 2f 0a 20 20 69 36 34 20 69 56 61   to */.  i64 iVa
1e00: 6c 2c 20 20 20 20 20 20 20 20 20 20 20 20 20 20  l,              
1e10: 20 20 20 20 20 20 20 20 20 2f 2a 20 56 61 6c 75           /* Valu
1e20: 65 20 74 6f 20 77 72 69 74 65 20 61 73 20 61 20  e to write as a 
1e30: 76 61 72 69 6e 74 20 2a 2f 0a 20 20 69 36 34 20  varint */.  i64 
1e40: 2a 70 69 4f 66 66 73 65 74 20 20 20 20 20 20 20  *piOffset       
1e50: 20 20 20 20 20 20 20 20 20 20 20 20 2f 2a 20 49              /* I
1e60: 4e 2f 4f 55 54 3a 20 57 72 69 74 65 20 6f 66 66  N/OUT: Write off
1e70: 73 65 74 20 69 6e 20 66 69 6c 65 20 70 46 69 6c  set in file pFil
1e80: 65 20 2a 2f 0a 29 7b 0a 20 20 75 38 20 61 56 61  e */.){.  u8 aVa
1e90: 72 69 6e 74 5b 39 5d 3b 20 20 20 20 20 20 20 20  rint[9];        
1ea0: 20 20 20 20 20 20 20 20 20 20 2f 2a 20 42 75 66            /* Buf
1eb0: 66 65 72 20 6c 61 72 67 65 20 65 6e 6f 75 67 68  fer large enough
1ec0: 20 66 6f 72 20 61 20 76 61 72 69 6e 74 20 2a 2f   for a varint */
1ed0: 0a 20 20 69 6e 74 20 6e 56 61 72 69 6e 74 3b 20  .  int nVarint; 
1ee0: 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20                  
1ef0: 20 20 20 2f 2a 20 4e 75 6d 62 65 72 20 6f 66 20     /* Number of 
1f00: 75 73 65 64 20 62 79 74 65 73 20 69 6e 20 76 61  used bytes in va
1f10: 72 69 6e 74 20 2a 2f 0a 20 20 69 6e 74 20 72 63  rint */.  int rc
1f20: 3b 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20  ;               
1f30: 20 20 20 20 20 20 20 20 20 20 2f 2a 20 52 65 73            /* Res
1f40: 75 6c 74 20 6f 66 20 77 72 69 74 65 28 29 20 63  ult of write() c
1f50: 61 6c 6c 20 2a 2f 0a 0a 20 20 6e 56 61 72 69 6e  all */..  nVarin
1f60: 74 20 3d 20 73 71 6c 69 74 65 33 50 75 74 56 61  t = sqlite3PutVa
1f70: 72 69 6e 74 28 61 56 61 72 69 6e 74 2c 20 69 56  rint(aVarint, iV
1f80: 61 6c 29 3b 0a 20 20 72 63 20 3d 20 73 71 6c 69  al);.  rc = sqli
1f90: 74 65 33 4f 73 57 72 69 74 65 28 70 46 69 6c 65  te3OsWrite(pFile
1fa0: 2c 20 61 56 61 72 69 6e 74 2c 20 6e 56 61 72 69  , aVarint, nVari
1fb0: 6e 74 2c 20 2a 70 69 4f 66 66 73 65 74 29 3b 0a  nt, *piOffset);.
1fc0: 20 20 2a 70 69 4f 66 66 73 65 74 20 2b 3d 20 6e    *piOffset += n
1fd0: 56 61 72 69 6e 74 3b 0a 0a 20 20 72 65 74 75 72  Varint;..  retur
1fe0: 6e 20 72 63 3b 0a 7d 0a 0a 2f 2a 0a 2a 2a 20 52  n rc;.}../*.** R
1ff0: 65 61 64 20 61 20 73 69 6e 67 6c 65 20 76 61 72  ead a single var
2000: 69 6e 74 20 66 72 6f 6d 20 66 69 6c 65 2d 64 65  int from file-de
2010: 73 63 72 69 70 74 6f 72 20 70 46 69 6c 65 2e 20  scriptor pFile. 
2020: 52 65 74 75 72 6e 20 53 51 4c 49 54 45 5f 4f 4b  Return SQLITE_OK
2030: 20 69 66 0a 2a 2a 20 73 75 63 63 65 73 73 66 75   if.** successfu
2040: 6c 2c 20 6f 72 20 61 6e 20 53 51 4c 69 74 65 20  l, or an SQLite 
2050: 65 72 72 6f 72 20 63 6f 64 65 20 69 66 20 73 6f  error code if so
2060: 6d 65 20 65 72 72 6f 72 20 6f 63 63 75 72 73 2e  me error occurs.
2070: 0a 2a 2a 0a 2a 2a 20 54 68 65 20 76 61 6c 75 65  .**.** The value
2080: 20 6f 66 20 2a 70 69 4f 66 66 73 65 74 20 77 68   of *piOffset wh
2090: 65 6e 20 74 68 69 73 20 66 75 6e 63 74 69 6f 6e  en this function
20a0: 20 69 73 20 63 61 6c 6c 65 64 20 69 73 20 75 73   is called is us
20b0: 65 64 20 61 73 20 74 68 65 0a 2a 2a 20 62 79 74  ed as the.** byt
20c0: 65 20 6f 66 66 73 65 74 20 69 6e 20 66 69 6c 65  e offset in file
20d0: 20 70 46 69 6c 65 20 66 72 6f 6d 20 77 68 65 6e   pFile from when
20e0: 63 65 20 74 6f 20 72 65 61 64 20 74 68 65 20 76  ce to read the v
20f0: 61 72 69 6e 74 2e 20 49 66 20 73 75 63 63 65 73  arint. If succes
2100: 73 66 75 6c 0a 2a 2a 20 28 69 2e 65 2e 20 69 66  sful.** (i.e. if
2110: 20 6e 6f 20 49 4f 20 65 72 72 6f 72 20 6f 63 63   no IO error occ
2120: 75 72 73 29 2c 20 74 68 65 6e 20 2a 70 69 4f 66  urs), then *piOf
2130: 66 73 65 74 20 69 73 20 73 65 74 20 74 6f 20 74  fset is set to t
2140: 68 65 20 6f 66 66 73 65 74 20 6f 66 0a 2a 2a 20  he offset of.** 
2150: 74 68 65 20 66 69 72 73 74 20 62 79 74 65 20 70  the first byte p
2160: 61 73 74 20 74 68 65 20 65 6e 64 20 6f 66 20 74  ast the end of t
2170: 68 65 20 76 61 72 69 6e 74 20 62 65 66 6f 72 65  he varint before
2180: 20 72 65 74 75 72 6e 69 6e 67 2e 20 2a 70 69 56   returning. *piV
2190: 61 6c 20 69 73 0a 2a 2a 20 73 65 74 20 74 6f 20  al is.** set to 
21a0: 74 68 65 20 69 6e 74 65 67 65 72 20 76 61 6c 75  the integer valu
21b0: 65 20 72 65 61 64 2e 20 49 66 20 61 6e 20 65 72  e read. If an er
21c0: 72 6f 72 20 6f 63 63 75 72 73 2c 20 74 68 65 20  ror occurs, the 
21d0: 66 69 6e 61 6c 20 76 61 6c 75 65 73 20 6f 66 0a  final values of.
21e0: 2a 2a 20 62 6f 74 68 20 2a 70 69 4f 66 66 73 65  ** both *piOffse
21f0: 74 20 61 6e 64 20 2a 70 69 56 61 6c 20 61 72 65  t and *piVal are
2200: 20 75 6e 64 65 66 69 6e 65 64 2e 0a 2a 2f 0a 73   undefined..*/.s
2210: 74 61 74 69 63 20 69 6e 74 20 76 64 62 65 53 6f  tatic int vdbeSo
2220: 72 74 65 72 52 65 61 64 56 61 72 69 6e 74 28 0a  rterReadVarint(.
2230: 20 20 73 71 6c 69 74 65 33 5f 66 69 6c 65 20 2a    sqlite3_file *
2240: 70 46 69 6c 65 2c 20 20 20 20 20 20 20 20 20 20  pFile,          
2250: 20 20 2f 2a 20 46 69 6c 65 20 74 6f 20 72 65 61    /* File to rea
2260: 64 20 66 72 6f 6d 20 2a 2f 0a 20 20 69 36 34 20  d from */.  i64 
2270: 69 45 6f 66 2c 20 20 20 20 20 20 20 20 20 20 20  iEof,           
2280: 20 20 20 20 20 20 20 20 20 20 20 20 2f 2a 20 54              /* T
2290: 6f 74 61 6c 20 6e 75 6d 62 65 72 20 6f 66 20 62  otal number of b
22a0: 79 74 65 73 20 69 6e 20 66 69 6c 65 20 2a 2f 0a  ytes in file */.
22b0: 20 20 69 36 34 20 2a 70 69 4f 66 66 73 65 74 2c    i64 *piOffset,
22c0: 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20                  
22d0: 20 20 2f 2a 20 49 4e 2f 4f 55 54 3a 20 52 65 61    /* IN/OUT: Rea
22e0: 64 20 6f 66 66 73 65 74 20 69 6e 20 70 46 69 6c  d offset in pFil
22f0: 65 20 2a 2f 0a 20 20 69 36 34 20 2a 70 69 56 61  e */.  i64 *piVa
2300: 6c 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20  l               
2310: 20 20 20 20 20 20 20 2f 2a 20 4f 55 54 3a 20 56         /* OUT: V
2320: 61 6c 75 65 20 72 65 61 64 20 66 72 6f 6d 20 66  alue read from f
2330: 69 6c 65 20 2a 2f 0a 29 7b 0a 20 20 75 38 20 61  ile */.){.  u8 a
2340: 56 61 72 69 6e 74 5b 39 5d 3b 20 20 20 20 20 20  Varint[9];      
2350: 20 20 20 20 20 20 20 20 20 20 20 20 2f 2a 20 42              /* B
2360: 75 66 66 65 72 20 6c 61 72 67 65 20 65 6e 6f 75  uffer large enou
2370: 67 68 20 66 6f 72 20 61 20 76 61 72 69 6e 74 20  gh for a varint 
2380: 2a 2f 0a 20 20 69 36 34 20 69 4f 66 66 20 3d 20  */.  i64 iOff = 
2390: 2a 70 69 4f 66 66 73 65 74 3b 20 20 20 20 20 20  *piOffset;      
23a0: 20 20 20 20 20 2f 2a 20 4f 66 66 73 65 74 20 69       /* Offset i
23b0: 6e 20 66 69 6c 65 20 74 6f 20 72 65 61 64 20 66  n file to read f
23c0: 72 6f 6d 20 2a 2f 0a 20 20 69 6e 74 20 6e 52 65  rom */.  int nRe
23d0: 61 64 20 3d 20 39 3b 20 20 20 20 20 20 20 20 20  ad = 9;         
23e0: 20 20 20 20 20 20 20 20 20 2f 2a 20 4e 75 6d 62           /* Numb
23f0: 65 72 20 6f 66 20 62 79 74 65 73 20 74 6f 20 72  er of bytes to r
2400: 65 61 64 20 66 72 6f 6d 20 66 69 6c 65 20 2a 2f  ead from file */
2410: 0a 20 20 69 6e 74 20 72 63 3b 20 20 20 20 20 20  .  int rc;      
2420: 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20                  
2430: 20 20 20 2f 2a 20 52 65 74 75 72 6e 20 63 6f 64     /* Return cod
2440: 65 20 2a 2f 0a 0a 20 20 61 73 73 65 72 74 28 20  e */..  assert( 
2450: 69 45 6f 66 3e 69 4f 66 66 20 29 3b 0a 20 20 69  iEof>iOff );.  i
2460: 66 28 20 28 69 45 6f 66 2d 69 4f 66 66 29 3c 6e  f( (iEof-iOff)<n
2470: 52 65 61 64 20 29 7b 0a 20 20 20 20 6e 52 65 61  Read ){.    nRea
2480: 64 20 3d 20 69 45 6f 66 2d 69 4f 66 66 3b 0a 20  d = iEof-iOff;. 
2490: 20 7d 0a 0a 20 20 72 63 20 3d 20 73 71 6c 69 74   }..  rc = sqlit
24a0: 65 33 4f 73 52 65 61 64 28 70 46 69 6c 65 2c 20  e3OsRead(pFile, 
24b0: 61 56 61 72 69 6e 74 2c 20 6e 52 65 61 64 2c 20  aVarint, nRead, 
24c0: 69 4f 66 66 29 3b 0a 20 20 69 66 28 20 72 63 3d  iOff);.  if( rc=
24d0: 3d 53 51 4c 49 54 45 5f 4f 4b 20 29 7b 0a 20 20  =SQLITE_OK ){.  
24e0: 20 20 2a 70 69 4f 66 66 73 65 74 20 2b 3d 20 67    *piOffset += g
24f0: 65 74 56 61 72 69 6e 74 28 61 56 61 72 69 6e 74  etVarint(aVarint
2500: 2c 20 28 75 36 34 20 2a 29 70 69 56 61 6c 29 3b  , (u64 *)piVal);
2510: 0a 20 20 7d 0a 0a 20 20 72 65 74 75 72 6e 20 72  .  }..  return r
2520: 63 3b 0a 7d 0a 0a 2f 2a 0a 2a 2a 20 49 6e 69 74  c;.}../*.** Init
2530: 69 61 6c 69 7a 65 20 69 74 65 72 61 74 6f 72 20  ialize iterator 
2540: 70 49 74 65 72 20 74 6f 20 73 63 61 6e 20 74 68  pIter to scan th
2550: 72 6f 75 67 68 20 74 68 65 20 50 4d 41 20 73 74  rough the PMA st
2560: 6f 72 65 64 20 69 6e 20 66 69 6c 65 20 70 46 69  ored in file pFi
2570: 6c 65 0a 2a 2a 20 73 74 61 72 74 69 6e 67 20 61  le.** starting a
2580: 74 20 6f 66 66 73 65 74 20 69 53 74 61 72 74 20  t offset iStart 
2590: 61 6e 64 20 65 6e 64 69 6e 67 20 61 74 20 6f 66  and ending at of
25a0: 66 73 65 74 20 69 45 6f 66 2d 31 2e 20 54 68 69  fset iEof-1. Thi
25b0: 73 20 66 75 6e 63 74 69 6f 6e 20 0a 2a 2a 20 6c  s function .** l
25c0: 65 61 76 65 73 20 74 68 65 20 69 74 65 72 61 74  eaves the iterat
25d0: 6f 72 20 70 6f 69 6e 74 69 6e 67 20 74 6f 20 74  or pointing to t
25e0: 68 65 20 66 69 72 73 74 20 6b 65 79 20 69 6e 20  he first key in 
25f0: 74 68 65 20 50 4d 41 20 28 6f 72 20 45 4f 46 20  the PMA (or EOF 
2600: 69 66 20 74 68 65 20 0a 2a 2a 20 50 4d 41 20 69  if the .** PMA i
2610: 73 20 65 6d 70 74 79 29 2e 0a 2a 2f 0a 73 74 61  s empty)..*/.sta
2620: 74 69 63 20 69 6e 74 20 76 64 62 65 53 6f 72 74  tic int vdbeSort
2630: 65 72 49 74 65 72 49 6e 69 74 28 0a 20 20 73 71  erIterInit(.  sq
2640: 6c 69 74 65 33 20 2a 64 62 2c 20 20 20 20 20 20  lite3 *db,      
2650: 20 20 20 20 20 20 20 20 20 20 20 20 20 20 2f 2a                /*
2660: 20 44 61 74 61 62 61 73 65 20 68 61 6e 64 6c 65   Database handle
2670: 20 2a 2f 0a 20 20 56 64 62 65 53 6f 72 74 65 72   */.  VdbeSorter
2680: 20 2a 70 53 6f 72 74 65 72 2c 20 20 20 20 20 20   *pSorter,      
2690: 20 20 20 20 20 20 2f 2a 20 53 6f 72 74 65 72 20        /* Sorter 
26a0: 6f 62 6a 65 63 74 20 2a 2f 0a 20 20 69 36 34 20  object */.  i64 
26b0: 69 53 74 61 72 74 2c 20 20 20 20 20 20 20 20 20  iStart,         
26c0: 20 20 20 20 20 20 20 20 20 20 20 20 2f 2a 20 53              /* S
26d0: 74 61 72 74 20 6f 66 66 73 65 74 20 69 6e 20 70  tart offset in p
26e0: 46 69 6c 65 20 2a 2f 0a 20 20 56 64 62 65 53 6f  File */.  VdbeSo
26f0: 72 74 65 72 49 74 65 72 20 2a 70 49 74 65 72 2c  rterIter *pIter,
2700: 20 20 20 20 20 20 20 20 20 20 2f 2a 20 49 74 65            /* Ite
2710: 72 61 74 6f 72 20 74 6f 20 70 6f 70 75 6c 61 74  rator to populat
2720: 65 20 2a 2f 0a 20 20 69 36 34 20 2a 70 6e 42 79  e */.  i64 *pnBy
2730: 74 65 20 20 20 20 20 20 20 20 20 20 20 20 20 20  te              
2740: 20 20 20 20 20 20 20 2f 2a 20 49 4e 2f 4f 55 54         /* IN/OUT
2750: 3a 20 49 6e 63 72 65 6d 65 6e 74 20 74 68 69 73  : Increment this
2760: 20 76 61 6c 75 65 20 62 79 20 50 4d 41 20 73 69   value by PMA si
2770: 7a 65 20 2a 2f 0a 29 7b 0a 20 20 69 6e 74 20 72  ze */.){.  int r
2780: 63 3b 0a 0a 20 20 61 73 73 65 72 74 28 20 70 53  c;..  assert( pS
2790: 6f 72 74 65 72 2d 3e 69 57 72 69 74 65 4f 66 66  orter->iWriteOff
27a0: 3e 69 53 74 61 72 74 20 29 3b 0a 20 20 61 73 73  >iStart );.  ass
27b0: 65 72 74 28 20 70 49 74 65 72 2d 3e 61 41 6c 6c  ert( pIter->aAll
27c0: 6f 63 3d 3d 30 20 29 3b 0a 20 20 70 49 74 65 72  oc==0 );.  pIter
27d0: 2d 3e 70 46 69 6c 65 20 3d 20 70 53 6f 72 74 65  ->pFile = pSorte
27e0: 72 2d 3e 70 54 65 6d 70 31 3b 0a 20 20 70 49 74  r->pTemp1;.  pIt
27f0: 65 72 2d 3e 69 52 65 61 64 4f 66 66 20 3d 20 69  er->iReadOff = i
2800: 53 74 61 72 74 3b 0a 20 20 70 49 74 65 72 2d 3e  Start;.  pIter->
2810: 6e 41 6c 6c 6f 63 20 3d 20 31 32 38 3b 0a 20 20  nAlloc = 128;.  
2820: 70 49 74 65 72 2d 3e 61 41 6c 6c 6f 63 20 3d 20  pIter->aAlloc = 
2830: 28 75 38 20 2a 29 73 71 6c 69 74 65 33 44 62 4d  (u8 *)sqlite3DbM
2840: 61 6c 6c 6f 63 52 61 77 28 64 62 2c 20 70 49 74  allocRaw(db, pIt
2850: 65 72 2d 3e 6e 41 6c 6c 6f 63 29 3b 0a 20 20 69  er->nAlloc);.  i
2860: 66 28 20 21 70 49 74 65 72 2d 3e 61 41 6c 6c 6f  f( !pIter->aAllo
2870: 63 20 29 7b 0a 20 20 20 20 72 63 20 3d 20 53 51  c ){.    rc = SQ
2880: 4c 49 54 45 5f 4e 4f 4d 45 4d 3b 0a 20 20 7d 65  LITE_NOMEM;.  }e
2890: 6c 73 65 7b 0a 20 20 20 20 69 36 34 20 69 45 6f  lse{.    i64 iEo
28a0: 66 20 3d 20 70 53 6f 72 74 65 72 2d 3e 69 57 72  f = pSorter->iWr
28b0: 69 74 65 4f 66 66 3b 20 20 20 20 20 2f 2a 20 45  iteOff;     /* E
28c0: 4f 46 20 6f 66 20 66 69 6c 65 20 70 53 6f 72 74  OF of file pSort
28d0: 65 72 2d 3e 70 54 65 6d 70 31 20 2a 2f 0a 20 20  er->pTemp1 */.  
28e0: 20 20 69 36 34 20 6e 42 79 74 65 3b 20 20 20 20    i64 nByte;    
28f0: 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20                  
2900: 20 20 20 20 20 2f 2a 20 54 6f 74 61 6c 20 73 69       /* Total si
2910: 7a 65 20 6f 66 20 50 4d 41 20 69 6e 20 62 79 74  ze of PMA in byt
2920: 65 73 20 2a 2f 0a 20 20 20 20 72 63 20 3d 20 76  es */.    rc = v
2930: 64 62 65 53 6f 72 74 65 72 52 65 61 64 56 61 72  dbeSorterReadVar
2940: 69 6e 74 28 70 53 6f 72 74 65 72 2d 3e 70 54 65  int(pSorter->pTe
2950: 6d 70 31 2c 20 69 45 6f 66 2c 20 26 70 49 74 65  mp1, iEof, &pIte
2960: 72 2d 3e 69 52 65 61 64 4f 66 66 2c 20 26 6e 42  r->iReadOff, &nB
2970: 79 74 65 29 3b 0a 20 20 20 20 2a 70 6e 42 79 74  yte);.    *pnByt
2980: 65 20 2b 3d 20 6e 42 79 74 65 3b 0a 20 20 20 20  e += nByte;.    
2990: 70 49 74 65 72 2d 3e 69 45 6f 66 20 3d 20 70 49  pIter->iEof = pI
29a0: 74 65 72 2d 3e 69 52 65 61 64 4f 66 66 20 2b 20  ter->iReadOff + 
29b0: 6e 42 79 74 65 3b 0a 20 20 7d 0a 20 20 69 66 28  nByte;.  }.  if(
29c0: 20 72 63 3d 3d 53 51 4c 49 54 45 5f 4f 4b 20 29   rc==SQLITE_OK )
29d0: 7b 0a 20 20 20 20 72 63 20 3d 20 76 64 62 65 53  {.    rc = vdbeS
29e0: 6f 72 74 65 72 49 74 65 72 4e 65 78 74 28 64 62  orterIterNext(db
29f0: 2c 20 70 49 74 65 72 29 3b 0a 20 20 7d 0a 20 20  , pIter);.  }.  
2a00: 72 65 74 75 72 6e 20 72 63 3b 0a 7d 0a 0a 2f 2a  return rc;.}../*
2a10: 0a 2a 2a 20 54 68 69 73 20 66 75 6e 63 74 69 6f  .** This functio
2a20: 6e 20 69 73 20 63 61 6c 6c 65 64 20 74 6f 20 63  n is called to c
2a30: 6f 6d 70 61 72 65 20 74 77 6f 20 69 74 65 72 61  ompare two itera
2a40: 74 6f 72 20 6b 65 79 73 20 77 68 65 6e 20 6d 65  tor keys when me
2a50: 72 67 69 6e 67 20 0a 2a 2a 20 6d 75 6c 74 69 70  rging .** multip
2a60: 6c 65 20 62 2d 74 72 65 65 20 73 65 67 6d 65 6e  le b-tree segmen
2a70: 74 73 2e 20 50 61 72 61 6d 65 74 65 72 20 69 4f  ts. Parameter iO
2a80: 75 74 20 69 73 20 74 68 65 20 69 6e 64 65 78 20  ut is the index 
2a90: 6f 66 20 74 68 65 20 61 54 72 65 65 5b 5d 20 0a  of the aTree[] .
2aa0: 2a 2a 20 76 61 6c 75 65 20 74 6f 20 72 65 63 61  ** value to reca
2ab0: 6c 63 75 6c 61 74 65 2e 0a 2a 2f 0a 73 74 61 74  lculate..*/.stat
2ac0: 69 63 20 69 6e 74 20 76 64 62 65 53 6f 72 74 65  ic int vdbeSorte
2ad0: 72 44 6f 43 6f 6d 70 61 72 65 28 56 64 62 65 43  rDoCompare(VdbeC
2ae0: 75 72 73 6f 72 20 2a 70 43 73 72 2c 20 69 6e 74  ursor *pCsr, int
2af0: 20 69 4f 75 74 29 7b 0a 20 20 56 64 62 65 53 6f   iOut){.  VdbeSo
2b00: 72 74 65 72 20 2a 70 53 6f 72 74 65 72 20 3d 20  rter *pSorter = 
2b10: 70 43 73 72 2d 3e 70 53 6f 72 74 65 72 3b 0a 20  pCsr->pSorter;. 
2b20: 20 69 6e 74 20 69 31 3b 0a 20 20 69 6e 74 20 69   int i1;.  int i
2b30: 32 3b 0a 20 20 69 6e 74 20 69 52 65 73 3b 0a 20  2;.  int iRes;. 
2b40: 20 56 64 62 65 53 6f 72 74 65 72 49 74 65 72 20   VdbeSorterIter 
2b50: 2a 70 31 3b 0a 20 20 56 64 62 65 53 6f 72 74 65  *p1;.  VdbeSorte
2b60: 72 49 74 65 72 20 2a 70 32 3b 0a 0a 20 20 61 73  rIter *p2;..  as
2b70: 73 65 72 74 28 20 69 4f 75 74 3c 70 53 6f 72 74  sert( iOut<pSort
2b80: 65 72 2d 3e 6e 54 72 65 65 20 26 26 20 69 4f 75  er->nTree && iOu
2b90: 74 3e 30 20 29 3b 0a 0a 20 20 69 66 28 20 69 4f  t>0 );..  if( iO
2ba0: 75 74 3e 3d 28 70 53 6f 72 74 65 72 2d 3e 6e 54  ut>=(pSorter->nT
2bb0: 72 65 65 2f 32 29 20 29 7b 0a 20 20 20 20 69 31  ree/2) ){.    i1
2bc0: 20 3d 20 28 69 4f 75 74 20 2d 20 70 53 6f 72 74   = (iOut - pSort
2bd0: 65 72 2d 3e 6e 54 72 65 65 2f 32 29 20 2a 20 32  er->nTree/2) * 2
2be0: 3b 0a 20 20 20 20 69 32 20 3d 20 69 31 20 2b 20  ;.    i2 = i1 + 
2bf0: 31 3b 0a 20 20 7d 65 6c 73 65 7b 0a 20 20 20 20  1;.  }else{.    
2c00: 69 31 20 3d 20 70 53 6f 72 74 65 72 2d 3e 61 54  i1 = pSorter->aT
2c10: 72 65 65 5b 69 4f 75 74 2a 32 5d 3b 0a 20 20 20  ree[iOut*2];.   
2c20: 20 69 32 20 3d 20 70 53 6f 72 74 65 72 2d 3e 61   i2 = pSorter->a
2c30: 54 72 65 65 5b 69 4f 75 74 2a 32 2b 31 5d 3b 0a  Tree[iOut*2+1];.
2c40: 20 20 7d 0a 0a 20 20 70 31 20 3d 20 26 70 53 6f    }..  p1 = &pSo
2c50: 72 74 65 72 2d 3e 61 49 74 65 72 5b 69 31 5d 3b  rter->aIter[i1];
2c60: 0a 20 20 70 32 20 3d 20 26 70 53 6f 72 74 65 72  .  p2 = &pSorter
2c70: 2d 3e 61 49 74 65 72 5b 69 32 5d 3b 0a 0a 20 20  ->aIter[i2];..  
2c80: 69 66 28 20 70 31 2d 3e 70 46 69 6c 65 3d 3d 30  if( p1->pFile==0
2c90: 20 29 7b 0a 20 20 20 20 69 52 65 73 20 3d 20 69   ){.    iRes = i
2ca0: 32 3b 0a 20 20 7d 65 6c 73 65 20 69 66 28 20 70  2;.  }else if( p
2cb0: 32 2d 3e 70 46 69 6c 65 3d 3d 30 20 29 7b 0a 20  2->pFile==0 ){. 
2cc0: 20 20 20 69 52 65 73 20 3d 20 69 31 3b 0a 20 20     iRes = i1;.  
2cd0: 7d 65 6c 73 65 7b 0a 20 20 20 20 63 68 61 72 20  }else{.    char 
2ce0: 61 53 70 61 63 65 5b 31 35 30 5d 3b 0a 20 20 20  aSpace[150];.   
2cf0: 20 55 6e 70 61 63 6b 65 64 52 65 63 6f 72 64 20   UnpackedRecord 
2d00: 2a 72 31 3b 0a 0a 20 20 20 20 72 31 20 3d 20 73  *r1;..    r1 = s
2d10: 71 6c 69 74 65 33 56 64 62 65 52 65 63 6f 72 64  qlite3VdbeRecord
2d20: 55 6e 70 61 63 6b 28 0a 20 20 20 20 20 20 20 20  Unpack(.        
2d30: 70 43 73 72 2d 3e 70 4b 65 79 49 6e 66 6f 2c 20  pCsr->pKeyInfo, 
2d40: 70 31 2d 3e 6e 4b 65 79 2c 20 70 31 2d 3e 61 4b  p1->nKey, p1->aK
2d50: 65 79 2c 20 61 53 70 61 63 65 2c 20 73 69 7a 65  ey, aSpace, size
2d60: 6f 66 28 61 53 70 61 63 65 29 0a 20 20 20 20 29  of(aSpace).    )
2d70: 3b 0a 20 20 20 20 69 66 28 20 72 31 3d 3d 30 20  ;.    if( r1==0 
2d80: 29 20 72 65 74 75 72 6e 20 53 51 4c 49 54 45 5f  ) return SQLITE_
2d90: 4e 4f 4d 45 4d 3b 0a 0a 20 20 20 20 69 66 28 20  NOMEM;..    if( 
2da0: 73 71 6c 69 74 65 33 56 64 62 65 52 65 63 6f 72  sqlite3VdbeRecor
2db0: 64 43 6f 6d 70 61 72 65 28 70 32 2d 3e 6e 4b 65  dCompare(p2->nKe
2dc0: 79 2c 20 70 32 2d 3e 61 4b 65 79 2c 20 72 31 29  y, p2->aKey, r1)
2dd0: 3e 3d 30 20 29 7b 0a 20 20 20 20 20 20 69 52 65  >=0 ){.      iRe
2de0: 73 20 3d 20 69 31 3b 0a 20 20 20 20 7d 65 6c 73  s = i1;.    }els
2df0: 65 7b 0a 20 20 20 20 20 20 69 52 65 73 20 3d 20  e{.      iRes = 
2e00: 69 32 3b 0a 20 20 20 20 7d 0a 20 20 20 20 73 71  i2;.    }.    sq
2e10: 6c 69 74 65 33 56 64 62 65 44 65 6c 65 74 65 55  lite3VdbeDeleteU
2e20: 6e 70 61 63 6b 65 64 52 65 63 6f 72 64 28 72 31  npackedRecord(r1
2e30: 29 3b 0a 20 20 7d 0a 0a 20 20 70 53 6f 72 74 65  );.  }..  pSorte
2e40: 72 2d 3e 61 54 72 65 65 5b 69 4f 75 74 5d 20 3d  r->aTree[iOut] =
2e50: 20 69 52 65 73 3b 0a 20 20 72 65 74 75 72 6e 20   iRes;.  return 
2e60: 53 51 4c 49 54 45 5f 4f 4b 3b 0a 7d 0a 0a 2f 2a  SQLITE_OK;.}../*
2e70: 0a 2a 2a 20 49 6e 69 74 69 61 6c 69 7a 65 20 74  .** Initialize t
2e80: 68 65 20 74 65 6d 70 6f 72 61 72 79 20 69 6e 64  he temporary ind
2e90: 65 78 20 63 75 72 73 6f 72 20 6a 75 73 74 20 6f  ex cursor just o
2ea0: 70 65 6e 65 64 20 61 73 20 61 20 73 6f 72 74 65  pened as a sorte
2eb0: 72 20 63 75 72 73 6f 72 2e 0a 2a 2f 0a 69 6e 74  r cursor..*/.int
2ec0: 20 73 71 6c 69 74 65 33 56 64 62 65 53 6f 72 74   sqlite3VdbeSort
2ed0: 65 72 49 6e 69 74 28 73 71 6c 69 74 65 33 20 2a  erInit(sqlite3 *
2ee0: 64 62 2c 20 56 64 62 65 43 75 72 73 6f 72 20 2a  db, VdbeCursor *
2ef0: 70 43 73 72 29 7b 0a 20 20 61 73 73 65 72 74 28  pCsr){.  assert(
2f00: 20 70 43 73 72 2d 3e 70 4b 65 79 49 6e 66 6f 20   pCsr->pKeyInfo 
2f10: 26 26 20 70 43 73 72 2d 3e 70 42 74 20 29 3b 0a  && pCsr->pBt );.
2f20: 20 20 70 43 73 72 2d 3e 70 53 6f 72 74 65 72 20    pCsr->pSorter 
2f30: 3d 20 73 71 6c 69 74 65 33 44 62 4d 61 6c 6c 6f  = sqlite3DbMallo
2f40: 63 5a 65 72 6f 28 64 62 2c 20 73 69 7a 65 6f 66  cZero(db, sizeof
2f50: 28 56 64 62 65 53 6f 72 74 65 72 29 29 3b 0a 20  (VdbeSorter));. 
2f60: 20 72 65 74 75 72 6e 20 28 70 43 73 72 2d 3e 70   return (pCsr->p
2f70: 53 6f 72 74 65 72 20 3f 20 53 51 4c 49 54 45 5f  Sorter ? SQLITE_
2f80: 4f 4b 20 3a 20 53 51 4c 49 54 45 5f 4e 4f 4d 45  OK : SQLITE_NOME
2f90: 4d 29 3b 0a 7d 0a 0a 2f 2a 0a 2a 2a 20 46 72 65  M);.}../*.** Fre
2fa0: 65 20 61 6e 79 20 63 75 72 73 6f 72 20 63 6f 6d  e any cursor com
2fb0: 70 6f 6e 65 6e 74 73 20 61 6c 6c 6f 63 61 74 65  ponents allocate
2fc0: 64 20 62 79 20 73 71 6c 69 74 65 33 56 64 62 65  d by sqlite3Vdbe
2fd0: 53 6f 72 74 65 72 58 58 58 20 72 6f 75 74 69 6e  SorterXXX routin
2fe0: 65 73 2e 0a 2a 2f 0a 76 6f 69 64 20 73 71 6c 69  es..*/.void sqli
2ff0: 74 65 33 56 64 62 65 53 6f 72 74 65 72 43 6c 6f  te3VdbeSorterClo
3000: 73 65 28 73 71 6c 69 74 65 33 20 2a 64 62 2c 20  se(sqlite3 *db, 
3010: 56 64 62 65 43 75 72 73 6f 72 20 2a 70 43 73 72  VdbeCursor *pCsr
3020: 29 7b 0a 20 20 56 64 62 65 53 6f 72 74 65 72 20  ){.  VdbeSorter 
3030: 2a 70 53 6f 72 74 65 72 20 3d 20 70 43 73 72 2d  *pSorter = pCsr-
3040: 3e 70 53 6f 72 74 65 72 3b 0a 20 20 69 66 28 20  >pSorter;.  if( 
3050: 70 53 6f 72 74 65 72 20 29 7b 0a 20 20 20 20 69  pSorter ){.    i
3060: 66 28 20 70 53 6f 72 74 65 72 2d 3e 61 49 74 65  f( pSorter->aIte
3070: 72 20 29 7b 0a 20 20 20 20 20 20 69 6e 74 20 69  r ){.      int i
3080: 3b 0a 20 20 20 20 20 20 66 6f 72 28 69 3d 30 3b  ;.      for(i=0;
3090: 20 69 3c 70 53 6f 72 74 65 72 2d 3e 6e 54 72 65   i<pSorter->nTre
30a0: 65 3b 20 69 2b 2b 29 7b 0a 20 20 20 20 20 20 20  e; i++){.       
30b0: 20 76 64 62 65 53 6f 72 74 65 72 49 74 65 72 5a   vdbeSorterIterZ
30c0: 65 72 6f 28 64 62 2c 20 26 70 53 6f 72 74 65 72  ero(db, &pSorter
30d0: 2d 3e 61 49 74 65 72 5b 69 5d 29 3b 0a 20 20 20  ->aIter[i]);.   
30e0: 20 20 20 7d 0a 20 20 20 20 20 20 73 71 6c 69 74     }.      sqlit
30f0: 65 33 44 62 46 72 65 65 28 64 62 2c 20 70 53 6f  e3DbFree(db, pSo
3100: 72 74 65 72 2d 3e 61 49 74 65 72 29 3b 0a 20 20  rter->aIter);.  
3110: 20 20 7d 0a 20 20 20 20 69 66 28 20 70 53 6f 72    }.    if( pSor
3120: 74 65 72 2d 3e 70 54 65 6d 70 31 20 29 7b 0a 20  ter->pTemp1 ){. 
3130: 20 20 20 20 20 73 71 6c 69 74 65 33 4f 73 43 6c       sqlite3OsCl
3140: 6f 73 65 46 72 65 65 28 70 53 6f 72 74 65 72 2d  oseFree(pSorter-
3150: 3e 70 54 65 6d 70 31 29 3b 0a 20 20 20 20 7d 0a  >pTemp1);.    }.
3160: 20 20 20 20 73 71 6c 69 74 65 33 44 62 46 72 65      sqlite3DbFre
3170: 65 28 64 62 2c 20 70 53 6f 72 74 65 72 29 3b 0a  e(db, pSorter);.
3180: 20 20 20 20 70 43 73 72 2d 3e 70 53 6f 72 74 65      pCsr->pSorte
3190: 72 20 3d 20 30 3b 0a 20 20 7d 0a 7d 0a 0a 2f 2a  r = 0;.  }.}../*
31a0: 0a 2a 2a 20 41 6c 6c 6f 63 61 74 65 20 73 70 61  .** Allocate spa
31b0: 63 65 20 66 6f 72 20 61 20 66 69 6c 65 2d 68 61  ce for a file-ha
31c0: 6e 64 6c 65 20 61 6e 64 20 6f 70 65 6e 20 61 20  ndle and open a 
31d0: 74 65 6d 70 6f 72 61 72 79 20 66 69 6c 65 2e 20  temporary file. 
31e0: 49 66 20 73 75 63 63 65 73 73 66 75 6c 2c 0a 2a  If successful,.*
31f0: 2a 20 73 65 74 20 2a 70 70 46 69 6c 65 20 74 6f  * set *ppFile to
3200: 20 70 6f 69 6e 74 20 74 6f 20 74 68 65 20 6d 61   point to the ma
3210: 6c 6c 6f 63 27 64 20 66 69 6c 65 2d 68 61 6e 64  lloc'd file-hand
3220: 6c 65 20 61 6e 64 20 72 65 74 75 72 6e 20 53 51  le and return SQ
3230: 4c 49 54 45 5f 4f 4b 2e 0a 2a 2a 20 4f 74 68 65  LITE_OK..** Othe
3240: 72 77 69 73 65 2c 20 73 65 74 20 2a 70 70 46 69  rwise, set *ppFi
3250: 6c 65 20 74 6f 20 30 20 61 6e 64 20 72 65 74 75  le to 0 and retu
3260: 72 6e 20 61 6e 20 53 51 4c 69 74 65 20 65 72 72  rn an SQLite err
3270: 6f 72 20 63 6f 64 65 2e 0a 2a 2f 0a 73 74 61 74  or code..*/.stat
3280: 69 63 20 69 6e 74 20 76 64 62 65 53 6f 72 74 65  ic int vdbeSorte
3290: 72 4f 70 65 6e 54 65 6d 70 46 69 6c 65 28 73 71  rOpenTempFile(sq
32a0: 6c 69 74 65 33 20 2a 64 62 2c 20 73 71 6c 69 74  lite3 *db, sqlit
32b0: 65 33 5f 66 69 6c 65 20 2a 2a 70 70 46 69 6c 65  e3_file **ppFile
32c0: 29 7b 0a 20 20 69 6e 74 20 64 75 6d 6d 79 3b 0a  ){.  int dummy;.
32d0: 20 20 72 65 74 75 72 6e 20 73 71 6c 69 74 65 33    return sqlite3
32e0: 4f 73 4f 70 65 6e 4d 61 6c 6c 6f 63 28 64 62 2d  OsOpenMalloc(db-
32f0: 3e 70 56 66 73 2c 20 30 2c 20 70 70 46 69 6c 65  >pVfs, 0, ppFile
3300: 2c 0a 20 20 20 20 20 20 53 51 4c 49 54 45 5f 4f  ,.      SQLITE_O
3310: 50 45 4e 5f 54 45 4d 50 5f 4a 4f 55 52 4e 41 4c  PEN_TEMP_JOURNAL
3320: 20 7c 0a 20 20 20 20 20 20 53 51 4c 49 54 45 5f   |.      SQLITE_
3330: 4f 50 45 4e 5f 52 45 41 44 57 52 49 54 45 20 20  OPEN_READWRITE  
3340: 20 20 7c 20 53 51 4c 49 54 45 5f 4f 50 45 4e 5f    | SQLITE_OPEN_
3350: 43 52 45 41 54 45 20 7c 0a 20 20 20 20 20 20 53  CREATE |.      S
3360: 51 4c 49 54 45 5f 4f 50 45 4e 5f 45 58 43 4c 55  QLITE_OPEN_EXCLU
3370: 53 49 56 45 20 20 20 20 7c 20 53 51 4c 49 54 45  SIVE    | SQLITE
3380: 5f 4f 50 45 4e 5f 44 45 4c 45 54 45 4f 4e 43 4c  _OPEN_DELETEONCL
3390: 4f 53 45 2c 20 26 64 75 6d 6d 79 0a 20 20 29 3b  OSE, &dummy.  );
33a0: 0a 7d 0a 0a 0a 2f 2a 0a 2a 2a 20 57 72 69 74 65  .}.../*.** Write
33b0: 20 74 68 65 20 63 75 72 72 65 6e 74 20 63 6f 6e   the current con
33c0: 74 65 6e 74 73 20 6f 66 20 74 68 65 20 62 2d 74  tents of the b-t
33d0: 72 65 65 20 74 6f 20 61 20 50 4d 41 2e 20 52 65  ree to a PMA. Re
33e0: 74 75 72 6e 20 53 51 4c 49 54 45 5f 4f 4b 0a 2a  turn SQLITE_OK.*
33f0: 2a 20 69 66 20 73 75 63 63 65 73 73 66 75 6c 2c  * if successful,
3400: 20 6f 72 20 61 6e 20 53 51 4c 69 74 65 20 65 72   or an SQLite er
3410: 72 6f 72 20 63 6f 64 65 20 6f 74 68 65 72 77 69  ror code otherwi
3420: 73 65 2e 0a 2a 2a 0a 2a 2a 20 54 68 65 20 66 6f  se..**.** The fo
3430: 72 6d 61 74 20 6f 66 20 61 20 50 4d 41 20 69 73  rmat of a PMA is
3440: 3a 0a 2a 2a 0a 2a 2a 20 20 20 20 20 2a 20 41 20  :.**.**     * A 
3450: 76 61 72 69 6e 74 2e 20 54 68 69 73 20 76 61 72  varint. This var
3460: 69 6e 74 20 63 6f 6e 74 61 69 6e 73 20 74 68 65  int contains the
3470: 20 74 6f 74 61 6c 20 6e 75 6d 62 65 72 20 6f 66   total number of
3480: 20 62 79 74 65 73 20 6f 66 20 63 6f 6e 74 65 6e   bytes of conten
3490: 74 0a 2a 2a 20 20 20 20 20 20 20 69 6e 20 74 68  t.**       in th
34a0: 65 20 50 4d 41 20 28 6e 6f 74 20 69 6e 63 6c 75  e PMA (not inclu
34b0: 64 69 6e 67 20 74 68 65 20 76 61 72 69 6e 74 20  ding the varint 
34c0: 69 74 73 65 6c 66 29 2e 0a 2a 2a 0a 2a 2a 20 20  itself)..**.**  
34d0: 20 20 20 2a 20 4f 6e 65 20 6f 72 20 6d 6f 72 65     * One or more
34e0: 20 72 65 63 6f 72 64 73 20 70 61 63 6b 65 64 20   records packed 
34f0: 65 6e 64 2d 74 6f 2d 65 6e 64 20 69 6e 20 6f 72  end-to-end in or
3500: 64 65 72 20 6f 66 20 61 73 63 65 6e 64 69 6e 67  der of ascending
3510: 20 6b 65 79 73 2e 20 0a 2a 2a 20 20 20 20 20 20   keys. .**      
3520: 20 45 61 63 68 20 72 65 63 6f 72 64 20 63 6f 6e   Each record con
3530: 73 69 73 74 73 20 6f 66 20 61 20 76 61 72 69 6e  sists of a varin
3540: 74 20 66 6f 6c 6c 6f 77 65 64 20 62 79 20 61 20  t followed by a 
3550: 62 6c 6f 62 20 6f 66 20 64 61 74 61 20 28 74 68  blob of data (th
3560: 65 20 0a 2a 2a 20 20 20 20 20 20 20 6b 65 79 29  e .**       key)
3570: 2e 20 54 68 65 20 76 61 72 69 6e 74 20 69 73 20  . The varint is 
3580: 74 68 65 20 6e 75 6d 62 65 72 20 6f 66 20 62 79  the number of by
3590: 74 65 73 20 69 6e 20 74 68 65 20 62 6c 6f 62 20  tes in the blob 
35a0: 6f 66 20 64 61 74 61 2e 0a 2a 2f 0a 73 74 61 74  of data..*/.stat
35b0: 69 63 20 69 6e 74 20 76 64 62 65 53 6f 72 74 65  ic int vdbeSorte
35c0: 72 42 74 72 65 65 54 6f 50 4d 41 28 73 71 6c 69  rBtreeToPMA(sqli
35d0: 74 65 33 20 2a 64 62 2c 20 56 64 62 65 43 75 72  te3 *db, VdbeCur
35e0: 73 6f 72 20 2a 70 43 73 72 29 7b 0a 20 20 69 6e  sor *pCsr){.  in
35f0: 74 20 72 63 20 3d 20 53 51 4c 49 54 45 5f 4f 4b  t rc = SQLITE_OK
3600: 3b 20 20 20 20 20 20 20 20 20 20 20 20 20 2f 2a  ;             /*
3610: 20 52 65 74 75 72 6e 20 63 6f 64 65 20 2a 2f 0a   Return code */.
3620: 20 20 56 64 62 65 53 6f 72 74 65 72 20 2a 70 53    VdbeSorter *pS
3630: 6f 72 74 65 72 20 3d 20 70 43 73 72 2d 3e 70 53  orter = pCsr->pS
3640: 6f 72 74 65 72 3b 0a 20 20 69 6e 74 20 72 65 73  orter;.  int res
3650: 20 3d 20 30 3b 0a 0a 20 20 2f 2a 20 73 71 6c 69   = 0;..  /* sqli
3660: 74 65 33 42 74 72 65 65 46 69 72 73 74 28 29 20  te3BtreeFirst() 
3670: 63 61 6e 6e 6f 74 20 66 61 69 6c 20 62 65 63 61  cannot fail beca
3680: 75 73 65 20 73 6f 72 74 65 72 20 62 74 72 65 65  use sorter btree
3690: 73 20 61 72 65 20 61 6c 77 61 79 73 20 68 65 6c  s are always hel
36a0: 64 0a 20 20 2a 2a 20 69 6e 20 6d 65 6d 6f 72 79  d.  ** in memory
36b0: 20 61 6e 64 20 73 6f 20 61 6e 20 49 2f 4f 20 65   and so an I/O e
36c0: 72 72 6f 72 20 69 73 20 6e 6f 74 20 70 6f 73 73  rror is not poss
36d0: 69 62 6c 65 2e 20 2a 2f 0a 20 20 72 63 20 3d 20  ible. */.  rc = 
36e0: 73 71 6c 69 74 65 33 42 74 72 65 65 46 69 72 73  sqlite3BtreeFirs
36f0: 74 28 70 43 73 72 2d 3e 70 43 75 72 73 6f 72 2c  t(pCsr->pCursor,
3700: 20 26 72 65 73 29 3b 0a 20 20 69 66 28 20 4e 45   &res);.  if( NE
3710: 56 45 52 28 72 63 21 3d 53 51 4c 49 54 45 5f 4f  VER(rc!=SQLITE_O
3720: 4b 29 20 7c 7c 20 72 65 73 20 29 20 72 65 74 75  K) || res ) retu
3730: 72 6e 20 72 63 3b 0a 20 20 61 73 73 65 72 74 28  rn rc;.  assert(
3740: 20 70 53 6f 72 74 65 72 2d 3e 6e 42 74 72 65 65   pSorter->nBtree
3750: 3e 30 20 29 3b 0a 0a 20 20 2f 2a 20 49 66 20 74  >0 );..  /* If t
3760: 68 65 20 66 69 72 73 74 20 74 65 6d 70 6f 72 61  he first tempora
3770: 72 79 20 50 4d 41 20 66 69 6c 65 20 68 61 73 20  ry PMA file has 
3780: 6e 6f 74 20 62 65 65 6e 20 6f 70 65 6e 65 64 2c  not been opened,
3790: 20 6f 70 65 6e 20 69 74 20 6e 6f 77 2e 20 2a 2f   open it now. */
37a0: 0a 20 20 69 66 28 20 70 53 6f 72 74 65 72 2d 3e  .  if( pSorter->
37b0: 70 54 65 6d 70 31 3d 3d 30 20 29 7b 0a 20 20 20  pTemp1==0 ){.   
37c0: 20 72 63 20 3d 20 76 64 62 65 53 6f 72 74 65 72   rc = vdbeSorter
37d0: 4f 70 65 6e 54 65 6d 70 46 69 6c 65 28 64 62 2c  OpenTempFile(db,
37e0: 20 26 70 53 6f 72 74 65 72 2d 3e 70 54 65 6d 70   &pSorter->pTemp
37f0: 31 29 3b 0a 20 20 20 20 61 73 73 65 72 74 28 20  1);.    assert( 
3800: 72 63 21 3d 53 51 4c 49 54 45 5f 4f 4b 20 7c 7c  rc!=SQLITE_OK ||
3810: 20 70 53 6f 72 74 65 72 2d 3e 70 54 65 6d 70 31   pSorter->pTemp1
3820: 20 29 3b 0a 20 20 20 20 61 73 73 65 72 74 28 20   );.    assert( 
3830: 70 53 6f 72 74 65 72 2d 3e 69 57 72 69 74 65 4f  pSorter->iWriteO
3840: 66 66 3d 3d 30 20 29 3b 0a 20 20 20 20 61 73 73  ff==0 );.    ass
3850: 65 72 74 28 20 70 53 6f 72 74 65 72 2d 3e 6e 50  ert( pSorter->nP
3860: 4d 41 3d 3d 30 20 29 3b 0a 20 20 7d 0a 0a 20 20  MA==0 );.  }..  
3870: 69 66 28 20 72 63 3d 3d 53 51 4c 49 54 45 5f 4f  if( rc==SQLITE_O
3880: 4b 20 29 7b 0a 20 20 20 20 69 36 34 20 69 57 72  K ){.    i64 iWr
3890: 69 74 65 4f 66 66 20 3d 20 70 53 6f 72 74 65 72  iteOff = pSorter
38a0: 2d 3e 69 57 72 69 74 65 4f 66 66 3b 0a 20 20 20  ->iWriteOff;.   
38b0: 20 76 6f 69 64 20 2a 61 4d 61 6c 6c 6f 63 20 3d   void *aMalloc =
38c0: 20 30 3b 20 20 20 20 20 20 20 20 20 20 20 20 2f   0;            /
38d0: 2a 20 41 72 72 61 79 20 75 73 65 64 20 74 6f 20  * Array used to 
38e0: 68 6f 6c 64 20 61 20 73 69 6e 67 6c 65 20 72 65  hold a single re
38f0: 63 6f 72 64 20 2a 2f 0a 20 20 20 20 69 6e 74 20  cord */.    int 
3900: 6e 4d 61 6c 6c 6f 63 20 3d 20 30 3b 20 20 20 20  nMalloc = 0;    
3910: 20 20 20 20 20 20 20 20 20 20 2f 2a 20 41 6c 6c            /* All
3920: 6f 63 61 74 65 64 20 73 69 7a 65 20 6f 66 20 61  ocated size of a
3930: 4d 61 6c 6c 6f 63 5b 5d 20 69 6e 20 62 79 74 65  Malloc[] in byte
3940: 73 20 2a 2f 0a 0a 20 20 20 20 70 53 6f 72 74 65  s */..    pSorte
3950: 72 2d 3e 6e 50 4d 41 2b 2b 3b 0a 20 20 20 20 66  r->nPMA++;.    f
3960: 6f 72 28 0a 20 20 20 20 20 20 72 63 20 3d 20 76  or(.      rc = v
3970: 64 62 65 53 6f 72 74 65 72 57 72 69 74 65 56 61  dbeSorterWriteVa
3980: 72 69 6e 74 28 70 53 6f 72 74 65 72 2d 3e 70 54  rint(pSorter->pT
3990: 65 6d 70 31 2c 20 70 53 6f 72 74 65 72 2d 3e 6e  emp1, pSorter->n
39a0: 42 74 72 65 65 2c 20 26 69 57 72 69 74 65 4f 66  Btree, &iWriteOf
39b0: 66 29 3b 0a 20 20 20 20 20 20 72 63 3d 3d 53 51  f);.      rc==SQ
39c0: 4c 49 54 45 5f 4f 4b 20 26 26 20 72 65 73 3d 3d  LITE_OK && res==
39d0: 30 3b 0a 20 20 20 20 20 20 72 63 20 3d 20 73 71  0;.      rc = sq
39e0: 6c 69 74 65 33 42 74 72 65 65 4e 65 78 74 28 70  lite3BtreeNext(p
39f0: 43 73 72 2d 3e 70 43 75 72 73 6f 72 2c 20 26 72  Csr->pCursor, &r
3a00: 65 73 29 0a 20 20 20 20 29 7b 0a 20 20 20 20 20  es).    ){.     
3a10: 20 69 36 34 20 6e 4b 65 79 3b 20 20 20 20 20 20   i64 nKey;      
3a20: 20 20 20 20 20 20 20 20 20 20 20 20 20 2f 2a 20               /* 
3a30: 53 69 7a 65 20 6f 66 20 74 68 69 73 20 6b 65 79  Size of this key
3a40: 20 69 6e 20 62 79 74 65 73 20 2a 2f 0a 0a 20 20   in bytes */..  
3a50: 20 20 20 20 2f 2a 20 57 72 69 74 65 20 74 68 65      /* Write the
3a60: 20 73 69 7a 65 20 6f 66 20 74 68 65 20 72 65 63   size of the rec
3a70: 6f 72 64 20 69 6e 20 62 79 74 65 73 20 74 6f 20  ord in bytes to 
3a80: 74 68 65 20 6f 75 74 70 75 74 20 66 69 6c 65 20  the output file 
3a90: 2a 2f 0a 20 20 20 20 20 20 28 76 6f 69 64 29 73  */.      (void)s
3aa0: 71 6c 69 74 65 33 42 74 72 65 65 4b 65 79 53 69  qlite3BtreeKeySi
3ab0: 7a 65 28 70 43 73 72 2d 3e 70 43 75 72 73 6f 72  ze(pCsr->pCursor
3ac0: 2c 20 26 6e 4b 65 79 29 3b 0a 20 20 20 20 20 20  , &nKey);.      
3ad0: 72 63 20 3d 20 76 64 62 65 53 6f 72 74 65 72 57  rc = vdbeSorterW
3ae0: 72 69 74 65 56 61 72 69 6e 74 28 70 53 6f 72 74  riteVarint(pSort
3af0: 65 72 2d 3e 70 54 65 6d 70 31 2c 20 6e 4b 65 79  er->pTemp1, nKey
3b00: 2c 20 26 69 57 72 69 74 65 4f 66 66 29 3b 0a 0a  , &iWriteOff);..
3b10: 20 20 20 20 20 20 2f 2a 20 4d 61 6b 65 20 73 75        /* Make su
3b20: 72 65 20 74 68 65 20 61 4d 61 6c 6c 6f 63 5b 5d  re the aMalloc[]
3b30: 20 62 75 66 66 65 72 20 69 73 20 6c 61 72 67 65   buffer is large
3b40: 20 65 6e 6f 75 67 68 20 66 6f 72 20 74 68 65 20   enough for the 
3b50: 72 65 63 6f 72 64 20 2a 2f 0a 20 20 20 20 20 20  record */.      
3b60: 69 66 28 20 72 63 3d 3d 53 51 4c 49 54 45 5f 4f  if( rc==SQLITE_O
3b70: 4b 20 26 26 20 6e 4b 65 79 3e 6e 4d 61 6c 6c 6f  K && nKey>nMallo
3b80: 63 20 29 7b 0a 20 20 20 20 20 20 20 20 61 4d 61  c ){.        aMa
3b90: 6c 6c 6f 63 20 3d 20 73 71 6c 69 74 65 33 44 62  lloc = sqlite3Db
3ba0: 52 65 61 6c 6c 6f 63 4f 72 46 72 65 65 28 64 62  ReallocOrFree(db
3bb0: 2c 20 61 4d 61 6c 6c 6f 63 2c 20 6e 4b 65 79 29  , aMalloc, nKey)
3bc0: 3b 0a 20 20 20 20 20 20 20 20 69 66 28 20 21 61  ;.        if( !a
3bd0: 4d 61 6c 6c 6f 63 20 29 7b 20 0a 20 20 20 20 20  Malloc ){ .     
3be0: 20 20 20 20 20 72 63 20 3d 20 53 51 4c 49 54 45       rc = SQLITE
3bf0: 5f 4e 4f 4d 45 4d 3b 20 0a 20 20 20 20 20 20 20  _NOMEM; .       
3c00: 20 7d 65 6c 73 65 7b 0a 20 20 20 20 20 20 20 20   }else{.        
3c10: 20 20 6e 4d 61 6c 6c 6f 63 20 3d 20 6e 4b 65 79    nMalloc = nKey
3c20: 3b 0a 20 20 20 20 20 20 20 20 7d 0a 20 20 20 20  ;.        }.    
3c30: 20 20 7d 0a 0a 20 20 20 20 20 20 2f 2a 20 57 72    }..      /* Wr
3c40: 69 74 65 20 74 68 65 20 72 65 63 6f 72 64 20 69  ite the record i
3c50: 74 73 65 6c 66 20 74 6f 20 74 68 65 20 6f 75 74  tself to the out
3c60: 70 75 74 20 66 69 6c 65 20 2a 2f 0a 20 20 20 20  put file */.    
3c70: 20 20 69 66 28 20 72 63 3d 3d 53 51 4c 49 54 45    if( rc==SQLITE
3c80: 5f 4f 4b 20 29 7b 0a 20 20 20 20 20 20 20 20 2f  _OK ){.        /
3c90: 2a 20 73 71 6c 69 74 65 33 42 74 72 65 65 4b 65  * sqlite3BtreeKe
3ca0: 79 28 29 20 63 61 6e 6e 6f 74 20 66 61 69 6c 20  y() cannot fail 
3cb0: 62 65 63 61 75 73 65 20 73 6f 72 74 65 72 20 62  because sorter b
3cc0: 74 72 65 65 73 20 68 65 6c 64 20 69 6e 20 6d 65  trees held in me
3cd0: 6d 6f 72 79 20 2a 2f 0a 20 20 20 20 20 20 20 20  mory */.        
3ce0: 72 63 20 3d 20 73 71 6c 69 74 65 33 42 74 72 65  rc = sqlite3Btre
3cf0: 65 4b 65 79 28 70 43 73 72 2d 3e 70 43 75 72 73  eKey(pCsr->pCurs
3d00: 6f 72 2c 20 30 2c 20 6e 4b 65 79 2c 20 61 4d 61  or, 0, nKey, aMa
3d10: 6c 6c 6f 63 29 3b 0a 20 20 20 20 20 20 20 20 69  lloc);.        i
3d20: 66 28 20 41 4c 57 41 59 53 28 72 63 3d 3d 53 51  f( ALWAYS(rc==SQ
3d30: 4c 49 54 45 5f 4f 4b 29 20 29 7b 0a 20 20 20 20  LITE_OK) ){.    
3d40: 20 20 20 20 20 20 72 63 20 3d 20 73 71 6c 69 74        rc = sqlit
3d50: 65 33 4f 73 57 72 69 74 65 28 70 53 6f 72 74 65  e3OsWrite(pSorte
3d60: 72 2d 3e 70 54 65 6d 70 31 2c 20 61 4d 61 6c 6c  r->pTemp1, aMall
3d70: 6f 63 2c 20 6e 4b 65 79 2c 20 69 57 72 69 74 65  oc, nKey, iWrite
3d80: 4f 66 66 29 3b 0a 20 20 20 20 20 20 20 20 20 20  Off);.          
3d90: 69 57 72 69 74 65 4f 66 66 20 2b 3d 20 6e 4b 65  iWriteOff += nKe
3da0: 79 3b 0a 20 20 20 20 20 20 20 20 7d 0a 20 20 20  y;.        }.   
3db0: 20 20 20 7d 0a 0a 20 20 20 20 20 20 69 66 28 20     }..      if( 
3dc0: 72 63 21 3d 53 51 4c 49 54 45 5f 4f 4b 20 29 20  rc!=SQLITE_OK ) 
3dd0: 62 72 65 61 6b 3b 0a 20 20 20 20 7d 0a 0a 20 20  break;.    }..  
3de0: 20 20 2f 2a 20 54 68 69 73 20 61 73 73 65 72 74    /* This assert
3df0: 20 76 65 72 69 66 69 65 73 20 74 68 61 74 20 75   verifies that u
3e00: 6e 6c 65 73 73 20 61 6e 20 65 72 72 6f 72 20 68  nless an error h
3e10: 61 73 20 6f 63 63 75 72 72 65 64 2c 20 74 68 65  as occurred, the
3e20: 20 73 69 7a 65 20 6f 66 20 0a 20 20 20 20 2a 2a   size of .    **
3e30: 20 74 68 65 20 50 4d 41 20 6f 6e 20 64 69 73 6b   the PMA on disk
3e40: 20 69 73 20 74 68 65 20 73 61 6d 65 20 61 73 20   is the same as 
3e50: 74 68 65 20 65 78 70 65 63 74 65 64 20 73 69 7a  the expected siz
3e60: 65 20 73 74 6f 72 65 64 20 69 6e 0a 20 20 20 20  e stored in.    
3e70: 2a 2a 20 70 53 6f 72 74 65 72 2d 3e 6e 42 74 72  ** pSorter->nBtr
3e80: 65 65 2e 20 2a 2f 20 0a 20 20 20 20 61 73 73 65  ee. */ .    asse
3e90: 72 74 28 20 72 63 21 3d 53 51 4c 49 54 45 5f 4f  rt( rc!=SQLITE_O
3ea0: 4b 20 7c 7c 20 70 53 6f 72 74 65 72 2d 3e 6e 42  K || pSorter->nB
3eb0: 74 72 65 65 3d 3d 28 0a 20 20 20 20 20 20 20 20  tree==(.        
3ec0: 20 20 69 57 72 69 74 65 4f 66 66 2d 70 53 6f 72    iWriteOff-pSor
3ed0: 74 65 72 2d 3e 69 57 72 69 74 65 4f 66 66 2d 73  ter->iWriteOff-s
3ee0: 71 6c 69 74 65 33 56 61 72 69 6e 74 4c 65 6e 28  qlite3VarintLen(
3ef0: 70 53 6f 72 74 65 72 2d 3e 6e 42 74 72 65 65 29  pSorter->nBtree)
3f00: 0a 20 20 20 20 29 29 3b 0a 0a 20 20 20 20 70 53  .    ));..    pS
3f10: 6f 72 74 65 72 2d 3e 69 57 72 69 74 65 4f 66 66  orter->iWriteOff
3f20: 20 3d 20 69 57 72 69 74 65 4f 66 66 3b 0a 20 20   = iWriteOff;.  
3f30: 20 20 73 71 6c 69 74 65 33 44 62 46 72 65 65 28    sqlite3DbFree(
3f40: 64 62 2c 20 61 4d 61 6c 6c 6f 63 29 3b 0a 20 20  db, aMalloc);.  
3f50: 7d 0a 0a 20 20 70 53 6f 72 74 65 72 2d 3e 6e 42  }..  pSorter->nB
3f60: 74 72 65 65 20 3d 20 30 3b 0a 20 20 72 65 74 75  tree = 0;.  retu
3f70: 72 6e 20 72 63 3b 0a 7d 0a 0a 2f 2a 0a 2a 2a 20  rn rc;.}../*.** 
3f80: 54 68 69 73 20 66 75 6e 63 74 69 6f 6e 20 69 73  This function is
3f90: 20 63 61 6c 6c 65 64 20 6f 6e 20 61 20 73 6f 72   called on a sor
3fa0: 74 65 72 20 63 75 72 73 6f 72 20 62 79 20 74 68  ter cursor by th
3fb0: 65 20 56 44 42 45 20 62 65 66 6f 72 65 20 65 61  e VDBE before ea
3fc0: 63 68 20 72 6f 77 20 0a 2a 2a 20 69 73 20 69 6e  ch row .** is in
3fd0: 73 65 72 74 65 64 20 69 6e 74 6f 20 56 64 62 65  serted into Vdbe
3fe0: 43 75 72 73 6f 72 2e 70 43 73 72 2e 20 41 72 67  Cursor.pCsr. Arg
3ff0: 75 6d 65 6e 74 20 6e 4b 65 79 20 69 73 20 74 68  ument nKey is th
4000: 65 20 73 69 7a 65 20 6f 66 20 74 68 65 20 6b 65  e size of the ke
4010: 79 2c 20 69 6e 0a 2a 2a 20 62 79 74 65 73 2c 20  y, in.** bytes, 
4020: 61 62 6f 75 74 20 74 6f 20 62 65 20 69 6e 73 65  about to be inse
4030: 72 74 65 64 2e 0a 2a 2a 0a 2a 2a 20 49 66 20 69  rted..**.** If i
4040: 74 20 69 73 20 64 65 74 65 72 6d 69 6e 65 64 20  t is determined 
4050: 74 68 61 74 20 74 68 65 20 74 65 6d 70 6f 72 61  that the tempora
4060: 72 79 20 62 2d 74 72 65 65 20 61 63 63 65 73 73  ry b-tree access
4070: 65 64 20 76 69 61 20 56 64 62 65 43 75 72 73 6f  ed via VdbeCurso
4080: 72 2e 70 43 73 72 0a 2a 2a 20 69 73 20 6c 61 72  r.pCsr.** is lar
4090: 67 65 20 65 6e 6f 75 67 68 2c 20 69 74 73 20 63  ge enough, its c
40a0: 6f 6e 74 65 6e 74 73 20 61 72 65 20 77 72 69 74  ontents are writ
40b0: 74 65 6e 20 74 6f 20 61 20 73 6f 72 74 65 64 20  ten to a sorted 
40c0: 50 4d 41 20 6f 6e 20 64 69 73 6b 20 61 6e 64 20  PMA on disk and 
40d0: 74 68 65 0a 2a 2a 20 74 72 65 65 20 65 6d 70 74  the.** tree empt
40e0: 69 65 64 2e 20 54 68 69 73 20 70 72 65 76 65 6e  ied. This preven
40f0: 74 73 20 74 68 65 20 62 2d 74 72 65 65 20 28 77  ts the b-tree (w
4100: 68 69 63 68 20 6d 75 73 74 20 62 65 20 73 6d 61  hich must be sma
4110: 6c 6c 20 65 6e 6f 75 67 68 20 74 6f 0a 2a 2a 20  ll enough to.** 
4120: 66 69 74 20 65 6e 74 69 72 65 6c 79 20 69 6e 20  fit entirely in 
4130: 74 68 65 20 63 61 63 68 65 20 69 6e 20 6f 72 64  the cache in ord
4140: 65 72 20 74 6f 20 73 75 70 70 6f 72 74 20 65 66  er to support ef
4150: 66 69 63 69 65 6e 74 20 69 6e 73 65 72 74 73 29  ficient inserts)
4160: 20 66 72 6f 6d 0a 2a 2a 20 67 72 6f 77 69 6e 67   from.** growing
4170: 20 74 6f 6f 20 6c 61 72 67 65 2e 0a 2a 2a 0a 2a   too large..**.*
4180: 2a 20 41 6e 20 53 51 4c 69 74 65 20 65 72 72 6f  * An SQLite erro
4190: 72 20 63 6f 64 65 20 69 73 20 72 65 74 75 72 6e  r code is return
41a0: 65 64 20 69 66 20 61 6e 20 65 72 72 6f 72 20 6f  ed if an error o
41b0: 63 63 75 72 73 2e 20 4f 74 68 65 72 77 69 73 65  ccurs. Otherwise
41c0: 2c 20 53 51 4c 49 54 45 5f 4f 4b 2e 0a 2a 2f 0a  , SQLITE_OK..*/.
41d0: 69 6e 74 20 73 71 6c 69 74 65 33 56 64 62 65 53  int sqlite3VdbeS
41e0: 6f 72 74 65 72 57 72 69 74 65 28 73 71 6c 69 74  orterWrite(sqlit
41f0: 65 33 20 2a 64 62 2c 20 56 64 62 65 43 75 72 73  e3 *db, VdbeCurs
4200: 6f 72 20 2a 70 43 73 72 2c 20 69 6e 74 20 6e 4b  or *pCsr, int nK
4210: 65 79 29 7b 0a 20 20 69 6e 74 20 72 63 20 3d 20  ey){.  int rc = 
4220: 53 51 4c 49 54 45 5f 4f 4b 3b 20 20 20 20 20 20  SQLITE_OK;      
4230: 20 20 20 20 20 20 20 2f 2a 20 52 65 74 75 72 6e         /* Return
4240: 20 63 6f 64 65 20 2a 2f 0a 20 20 56 64 62 65 53   code */.  VdbeS
4250: 6f 72 74 65 72 20 2a 70 53 6f 72 74 65 72 20 3d  orter *pSorter =
4260: 20 70 43 73 72 2d 3e 70 53 6f 72 74 65 72 3b 0a   pCsr->pSorter;.
4270: 20 20 69 66 28 20 70 53 6f 72 74 65 72 20 29 7b    if( pSorter ){
4280: 0a 20 20 20 20 50 61 67 65 72 20 2a 70 50 61 67  .    Pager *pPag
4290: 65 72 20 3d 20 73 71 6c 69 74 65 33 42 74 72 65  er = sqlite3Btre
42a0: 65 50 61 67 65 72 28 70 43 73 72 2d 3e 70 42 74  ePager(pCsr->pBt
42b0: 29 3b 0a 20 20 20 20 69 6e 74 20 6e 50 61 67 65  );.    int nPage
42c0: 3b 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20  ;               
42d0: 20 20 20 20 20 2f 2a 20 43 75 72 72 65 6e 74 20       /* Current 
42e0: 73 69 7a 65 20 6f 66 20 74 65 6d 70 6f 72 61 72  size of temporar
42f0: 79 20 66 69 6c 65 20 69 6e 20 70 61 67 65 73 20  y file in pages 
4300: 2a 2f 0a 0a 20 20 20 20 2f 2a 20 53 6f 72 74 65  */..    /* Sorte
4310: 72 73 20 6e 65 76 65 72 20 73 70 69 6c 6c 20 74  rs never spill t
4320: 6f 20 64 69 73 6b 20 2a 2f 0a 20 20 20 20 61 73  o disk */.    as
4330: 73 65 72 74 28 20 73 71 6c 69 74 65 33 50 61 67  sert( sqlite3Pag
4340: 65 72 46 69 6c 65 28 70 50 61 67 65 72 29 2d 3e  erFile(pPager)->
4350: 70 4d 65 74 68 6f 64 73 3d 3d 30 20 29 3b 0a 0a  pMethods==0 );..
4360: 20 20 20 20 2f 2a 20 44 65 74 65 72 6d 69 6e 65      /* Determine
4370: 20 68 6f 77 20 6d 61 6e 79 20 70 61 67 65 73 20   how many pages 
4380: 74 68 65 20 74 65 6d 70 6f 72 61 72 79 20 62 2d  the temporary b-
4390: 74 72 65 65 20 68 61 73 20 67 72 6f 77 6e 20 74  tree has grown t
43a0: 6f 20 2a 2f 0a 20 20 20 20 73 71 6c 69 74 65 33  o */.    sqlite3
43b0: 50 61 67 65 72 50 61 67 65 63 6f 75 6e 74 28 70  PagerPagecount(p
43c0: 50 61 67 65 72 2c 20 26 6e 50 61 67 65 29 3b 0a  Pager, &nPage);.
43d0: 0a 20 20 20 20 2f 2a 20 49 66 20 70 53 6f 72 74  .    /* If pSort
43e0: 65 72 2d 3e 6e 57 6f 72 6b 69 6e 67 20 69 73 20  er->nWorking is 
43f0: 73 74 69 6c 6c 20 7a 65 72 6f 2c 20 62 75 74 20  still zero, but 
4400: 74 68 65 20 74 65 6d 70 6f 72 61 72 79 20 66 69  the temporary fi
4410: 6c 65 20 68 61 73 20 62 65 65 6e 0a 20 20 20 20  le has been.    
4420: 2a 2a 20 63 72 65 61 74 65 64 20 69 6e 20 74 68  ** created in th
4430: 65 20 66 69 6c 65 2d 73 79 73 74 65 6d 2c 20 74  e file-system, t
4440: 68 65 6e 20 74 68 65 20 6d 6f 73 74 20 72 65 63  hen the most rec
4450: 65 6e 74 20 69 6e 73 65 72 74 20 69 6e 74 6f 20  ent insert into 
4460: 74 68 65 0a 20 20 20 20 2a 2a 20 63 75 72 72 65  the.    ** curre
4470: 6e 74 20 62 2d 74 72 65 65 20 73 65 67 6d 65 6e  nt b-tree segmen
4480: 74 20 70 72 6f 62 61 62 6c 79 20 63 61 75 73 65  t probably cause
4490: 64 20 74 68 65 20 63 61 63 68 65 20 74 6f 20 6f  d the cache to o
44a0: 76 65 72 66 6c 6f 77 20 28 69 74 20 69 73 0a 20  verflow (it is. 
44b0: 20 20 20 2a 2a 20 61 6c 73 6f 20 70 6f 73 73 69     ** also possi
44c0: 62 6c 65 20 74 68 61 74 20 73 71 6c 69 74 65 33  ble that sqlite3
44d0: 5f 72 65 6c 65 61 73 65 5f 6d 65 6d 6f 72 79 28  _release_memory(
44e0: 29 20 77 61 73 20 63 61 6c 6c 65 64 29 2e 20 53  ) was called). S
44f0: 6f 20 73 65 74 20 74 68 65 0a 20 20 20 20 2a 2a  o set the.    **
4500: 20 73 69 7a 65 20 6f 66 20 74 68 65 20 77 6f 72   size of the wor
4510: 6b 69 6e 67 20 73 65 74 20 74 6f 20 61 20 6c 69  king set to a li
4520: 74 74 6c 65 20 6c 65 73 73 20 74 68 61 6e 20 74  ttle less than t
4530: 68 65 20 63 75 72 72 65 6e 74 20 73 69 7a 65 20  he current size 
4540: 6f 66 20 74 68 65 20 0a 20 20 20 20 2a 2a 20 66  of the .    ** f
4550: 69 6c 65 20 69 6e 20 70 61 67 65 73 2e 20 20 2a  ile in pages.  *
4560: 2f 0a 20 20 20 20 69 66 28 20 70 53 6f 72 74 65  /.    if( pSorte
4570: 72 2d 3e 6e 57 6f 72 6b 69 6e 67 3d 3d 30 20 26  r->nWorking==0 &
4580: 26 20 73 71 6c 69 74 65 33 50 61 67 65 72 55 6e  & sqlite3PagerUn
4590: 64 65 72 53 74 72 65 73 73 28 70 50 61 67 65 72  derStress(pPager
45a0: 29 20 29 7b 0a 20 20 20 20 20 20 70 53 6f 72 74  ) ){.      pSort
45b0: 65 72 2d 3e 6e 57 6f 72 6b 69 6e 67 20 3d 20 6e  er->nWorking = n
45c0: 50 61 67 65 2d 35 3b 0a 20 20 20 20 20 20 69 66  Page-5;.      if
45d0: 28 20 70 53 6f 72 74 65 72 2d 3e 6e 57 6f 72 6b  ( pSorter->nWork
45e0: 69 6e 67 3c 53 4f 52 54 45 52 5f 4d 49 4e 5f 57  ing<SORTER_MIN_W
45f0: 4f 52 4b 49 4e 47 20 29 7b 0a 20 20 20 20 20 20  ORKING ){.      
4600: 20 20 70 53 6f 72 74 65 72 2d 3e 6e 57 6f 72 6b    pSorter->nWork
4610: 69 6e 67 20 3d 20 53 4f 52 54 45 52 5f 4d 49 4e  ing = SORTER_MIN
4620: 5f 57 4f 52 4b 49 4e 47 3b 0a 20 20 20 20 20 20  _WORKING;.      
4630: 7d 0a 20 20 20 20 7d 0a 0a 20 20 20 20 2f 2a 20  }.    }..    /* 
4640: 49 66 20 74 68 65 20 6e 75 6d 62 65 72 20 6f 66  If the number of
4650: 20 70 61 67 65 73 20 75 73 65 64 20 62 79 20 74   pages used by t
4660: 68 65 20 63 75 72 72 65 6e 74 20 62 2d 74 72 65  he current b-tre
4670: 65 20 73 65 67 6d 65 6e 74 20 69 73 20 67 72 65  e segment is gre
4680: 61 74 65 72 0a 20 20 20 20 2a 2a 20 74 68 61 6e  ater.    ** than
4690: 20 74 68 65 20 73 69 7a 65 20 6f 66 20 74 68 65   the size of the
46a0: 20 77 6f 72 6b 69 6e 67 20 73 65 74 20 28 56 64   working set (Vd
46b0: 62 65 53 6f 72 74 65 72 2e 6e 57 6f 72 6b 69 6e  beSorter.nWorkin
46c0: 67 29 2c 20 73 74 61 72 74 20 61 20 6e 65 77 0a  g), start a new.
46d0: 20 20 20 20 2a 2a 20 73 65 67 6d 65 6e 74 20 62      ** segment b
46e0: 2d 74 72 65 65 2e 20 20 2a 2f 0a 20 20 20 20 69  -tree.  */.    i
46f0: 66 28 20 70 53 6f 72 74 65 72 2d 3e 6e 57 6f 72  f( pSorter->nWor
4700: 6b 69 6e 67 20 26 26 20 6e 50 61 67 65 3e 3d 70  king && nPage>=p
4710: 53 6f 72 74 65 72 2d 3e 6e 57 6f 72 6b 69 6e 67  Sorter->nWorking
4720: 20 29 7b 0a 20 20 20 20 20 20 42 74 43 75 72 73   ){.      BtCurs
4730: 6f 72 20 2a 70 20 3d 20 70 43 73 72 2d 3e 70 43  or *p = pCsr->pC
4740: 75 72 73 6f 72 3b 2f 2a 20 43 75 72 73 6f 72 20  ursor;/* Cursor 
4750: 73 74 72 75 63 74 75 72 65 20 74 6f 20 63 6c 6f  structure to clo
4760: 73 65 20 61 6e 64 20 72 65 6f 70 65 6e 20 2a 2f  se and reopen */
4770: 0a 20 20 20 20 20 20 69 6e 74 20 69 52 6f 6f 74  .      int iRoot
4780: 3b 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20  ;               
4790: 20 20 20 2f 2a 20 52 6f 6f 74 20 70 61 67 65 20     /* Root page 
47a0: 6f 66 20 6e 65 77 20 74 72 65 65 20 2a 2f 0a 0a  of new tree */..
47b0: 20 20 20 20 20 20 2f 2a 20 43 6f 70 79 20 74 68        /* Copy th
47c0: 65 20 63 75 72 72 65 6e 74 20 63 6f 6e 74 65 6e  e current conten
47d0: 74 73 20 6f 66 20 74 68 65 20 62 2d 74 72 65 65  ts of the b-tree
47e0: 20 69 6e 74 6f 20 61 20 50 4d 41 20 69 6e 20 73   into a PMA in s
47f0: 6f 72 74 65 64 20 6f 72 64 65 72 2e 0a 20 20 20  orted order..   
4800: 20 20 20 2a 2a 20 43 6c 6f 73 65 20 74 68 65 20     ** Close the 
4810: 63 75 72 72 65 6e 74 6c 79 20 6f 70 65 6e 20 62  currently open b
4820: 2d 74 72 65 65 20 63 75 72 73 6f 72 2e 20 2a 2f  -tree cursor. */
4830: 0a 20 20 20 20 20 20 72 63 20 3d 20 76 64 62 65  .      rc = vdbe
4840: 53 6f 72 74 65 72 42 74 72 65 65 54 6f 50 4d 41  SorterBtreeToPMA
4850: 28 64 62 2c 20 70 43 73 72 29 3b 0a 20 20 20 20  (db, pCsr);.    
4860: 20 20 73 71 6c 69 74 65 33 42 74 72 65 65 43 6c    sqlite3BtreeCl
4870: 6f 73 65 43 75 72 73 6f 72 28 70 29 3b 0a 0a 20  oseCursor(p);.. 
4880: 20 20 20 20 20 69 66 28 20 72 63 3d 3d 53 51 4c       if( rc==SQL
4890: 49 54 45 5f 4f 4b 20 29 7b 0a 20 20 20 20 20 20  ITE_OK ){.      
48a0: 20 20 72 63 20 3d 20 73 71 6c 69 74 65 33 42 74    rc = sqlite3Bt
48b0: 72 65 65 44 72 6f 70 54 61 62 6c 65 28 70 43 73  reeDropTable(pCs
48c0: 72 2d 3e 70 42 74 2c 20 32 2c 20 30 29 3b 0a 23  r->pBt, 2, 0);.#
48d0: 69 66 64 65 66 20 53 51 4c 49 54 45 5f 44 45 42  ifdef SQLITE_DEB
48e0: 55 47 0a 20 20 20 20 20 20 20 20 73 71 6c 69 74  UG.        sqlit
48f0: 65 33 50 61 67 65 72 50 61 67 65 63 6f 75 6e 74  e3PagerPagecount
4900: 28 70 50 61 67 65 72 2c 20 26 6e 50 61 67 65 29  (pPager, &nPage)
4910: 3b 0a 20 20 20 20 20 20 20 20 61 73 73 65 72 74  ;.        assert
4920: 28 20 72 63 21 3d 53 51 4c 49 54 45 5f 4f 4b 20  ( rc!=SQLITE_OK 
4930: 7c 7c 20 6e 50 61 67 65 3d 3d 31 20 29 3b 0a 23  || nPage==1 );.#
4940: 65 6e 64 69 66 0a 20 20 20 20 20 20 7d 0a 20 20  endif.      }.  
4950: 20 20 20 20 69 66 28 20 72 63 3d 3d 53 51 4c 49      if( rc==SQLI
4960: 54 45 5f 4f 4b 20 29 7b 0a 20 20 20 20 20 20 20  TE_OK ){.       
4970: 20 72 63 20 3d 20 73 71 6c 69 74 65 33 42 74 72   rc = sqlite3Btr
4980: 65 65 43 72 65 61 74 65 54 61 62 6c 65 28 70 43  eeCreateTable(pC
4990: 73 72 2d 3e 70 42 74 2c 20 26 69 52 6f 6f 74 2c  sr->pBt, &iRoot,
49a0: 20 42 54 52 45 45 5f 42 4c 4f 42 4b 45 59 29 3b   BTREE_BLOBKEY);
49b0: 0a 20 20 20 20 20 20 7d 0a 20 20 20 20 20 20 69  .      }.      i
49c0: 66 28 20 72 63 3d 3d 53 51 4c 49 54 45 5f 4f 4b  f( rc==SQLITE_OK
49d0: 20 29 7b 0a 20 20 20 20 20 20 20 20 61 73 73 65   ){.        asse
49e0: 72 74 28 20 69 52 6f 6f 74 3d 3d 32 20 29 3b 0a  rt( iRoot==2 );.
49f0: 20 20 20 20 20 20 20 20 72 63 20 3d 20 73 71 6c          rc = sql
4a00: 69 74 65 33 42 74 72 65 65 43 75 72 73 6f 72 28  ite3BtreeCursor(
4a10: 70 43 73 72 2d 3e 70 42 74 2c 20 69 52 6f 6f 74  pCsr->pBt, iRoot
4a20: 2c 20 31 2c 20 70 43 73 72 2d 3e 70 4b 65 79 49  , 1, pCsr->pKeyI
4a30: 6e 66 6f 2c 20 70 29 3b 0a 20 20 20 20 20 20 7d  nfo, p);.      }
4a40: 0a 20 20 20 20 7d 0a 0a 20 20 20 20 70 53 6f 72  .    }..    pSor
4a50: 74 65 72 2d 3e 6e 42 74 72 65 65 20 2b 3d 20 73  ter->nBtree += s
4a60: 71 6c 69 74 65 33 56 61 72 69 6e 74 4c 65 6e 28  qlite3VarintLen(
4a70: 6e 4b 65 79 29 20 2b 20 6e 4b 65 79 3b 0a 20 20  nKey) + nKey;.  
4a80: 7d 0a 20 20 72 65 74 75 72 6e 20 72 63 3b 0a 7d  }.  return rc;.}
4a90: 0a 0a 2f 2a 0a 2a 2a 20 48 65 6c 70 65 72 20 66  ../*.** Helper f
4aa0: 75 6e 63 74 69 6f 6e 20 66 6f 72 20 73 71 6c 69  unction for sqli
4ab0: 74 65 33 56 64 62 65 53 6f 72 74 65 72 52 65 77  te3VdbeSorterRew
4ac0: 69 6e 64 28 29 2e 20 0a 2a 2f 0a 73 74 61 74 69  ind(). .*/.stati
4ad0: 63 20 69 6e 74 20 76 64 62 65 53 6f 72 74 65 72  c int vdbeSorter
4ae0: 49 6e 69 74 4d 65 72 67 65 28 0a 20 20 73 71 6c  InitMerge(.  sql
4af0: 69 74 65 33 20 2a 64 62 2c 20 20 20 20 20 20 20  ite3 *db,       
4b00: 20 20 20 20 20 20 20 20 20 20 20 20 20 2f 2a 20               /* 
4b10: 44 61 74 61 62 61 73 65 20 68 61 6e 64 6c 65 20  Database handle 
4b20: 2a 2f 0a 20 20 56 64 62 65 43 75 72 73 6f 72 20  */.  VdbeCursor 
4b30: 2a 70 43 73 72 2c 20 20 20 20 20 20 20 20 20 20  *pCsr,          
4b40: 20 20 20 20 20 2f 2a 20 43 75 72 73 6f 72 20 68       /* Cursor h
4b50: 61 6e 64 6c 65 20 66 6f 72 20 74 68 69 73 20 73  andle for this s
4b60: 6f 72 74 65 72 20 2a 2f 0a 20 20 69 36 34 20 2a  orter */.  i64 *
4b70: 70 6e 42 79 74 65 20 20 20 20 20 20 20 20 20 20  pnByte          
4b80: 20 20 20 20 20 20 20 20 20 20 20 2f 2a 20 53 75             /* Su
4b90: 6d 20 6f 66 20 62 79 74 65 73 20 69 6e 20 61 6c  m of bytes in al
4ba0: 6c 20 6f 70 65 6e 65 64 20 50 4d 41 73 20 2a 2f  l opened PMAs */
4bb0: 0a 29 7b 0a 20 20 56 64 62 65 53 6f 72 74 65 72  .){.  VdbeSorter
4bc0: 20 2a 70 53 6f 72 74 65 72 20 3d 20 70 43 73 72   *pSorter = pCsr
4bd0: 2d 3e 70 53 6f 72 74 65 72 3b 0a 20 20 69 6e 74  ->pSorter;.  int
4be0: 20 72 63 20 3d 20 53 51 4c 49 54 45 5f 4f 4b 3b   rc = SQLITE_OK;
4bf0: 20 20 20 20 20 20 20 20 20 20 20 20 20 2f 2a 20               /* 
4c00: 52 65 74 75 72 6e 20 63 6f 64 65 20 2a 2f 0a 20  Return code */. 
4c10: 20 69 6e 74 20 69 3b 20 20 20 20 20 20 20 20 20   int i;         
4c20: 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20                  
4c30: 20 2f 2a 20 55 73 65 64 20 74 6f 20 69 74 65 72   /* Used to iter
4c40: 61 74 6f 72 20 74 68 72 6f 75 67 68 20 61 49 74  ator through aIt
4c50: 65 72 5b 5d 20 2a 2f 0a 20 20 69 36 34 20 6e 42  er[] */.  i64 nB
4c60: 79 74 65 20 3d 20 30 3b 20 20 20 20 20 20 20 20  yte = 0;        
4c70: 20 20 20 20 20 20 20 20 20 20 2f 2a 20 54 6f 74            /* Tot
4c80: 61 6c 20 62 79 74 65 73 20 69 6e 20 61 6c 6c 20  al bytes in all 
4c90: 6f 70 65 6e 65 64 20 50 4d 41 73 20 2a 2f 0a 0a  opened PMAs */..
4ca0: 20 20 2f 2a 20 49 6e 69 74 69 61 6c 69 7a 65 20    /* Initialize 
4cb0: 74 68 65 20 69 74 65 72 61 74 6f 72 73 2e 20 2a  the iterators. *
4cc0: 2f 0a 20 20 66 6f 72 28 69 3d 30 3b 20 72 63 3d  /.  for(i=0; rc=
4cd0: 3d 53 51 4c 49 54 45 5f 4f 4b 20 26 26 20 69 3c  =SQLITE_OK && i<
4ce0: 53 4f 52 54 45 52 5f 4d 41 58 5f 4d 45 52 47 45  SORTER_MAX_MERGE
4cf0: 5f 43 4f 55 4e 54 3b 20 69 2b 2b 29 7b 0a 20 20  _COUNT; i++){.  
4d00: 20 20 56 64 62 65 53 6f 72 74 65 72 49 74 65 72    VdbeSorterIter
4d10: 20 2a 70 49 74 65 72 20 3d 20 26 70 53 6f 72 74   *pIter = &pSort
4d20: 65 72 2d 3e 61 49 74 65 72 5b 69 5d 3b 0a 20 20  er->aIter[i];.  
4d30: 20 20 72 63 20 3d 20 76 64 62 65 53 6f 72 74 65    rc = vdbeSorte
4d40: 72 49 74 65 72 49 6e 69 74 28 64 62 2c 20 70 53  rIterInit(db, pS
4d50: 6f 72 74 65 72 2c 20 70 53 6f 72 74 65 72 2d 3e  orter, pSorter->
4d60: 69 52 65 61 64 4f 66 66 2c 20 70 49 74 65 72 2c  iReadOff, pIter,
4d70: 20 26 6e 42 79 74 65 29 3b 0a 20 20 20 20 70 53   &nByte);.    pS
4d80: 6f 72 74 65 72 2d 3e 69 52 65 61 64 4f 66 66 20  orter->iReadOff 
4d90: 3d 20 70 49 74 65 72 2d 3e 69 45 6f 66 3b 0a 20  = pIter->iEof;. 
4da0: 20 20 20 61 73 73 65 72 74 28 20 70 53 6f 72 74     assert( pSort
4db0: 65 72 2d 3e 69 52 65 61 64 4f 66 66 3c 3d 70 53  er->iReadOff<=pS
4dc0: 6f 72 74 65 72 2d 3e 69 57 72 69 74 65 4f 66 66  orter->iWriteOff
4dd0: 20 7c 7c 20 72 63 21 3d 53 51 4c 49 54 45 5f 4f   || rc!=SQLITE_O
4de0: 4b 20 29 3b 0a 20 20 20 20 69 66 28 20 70 53 6f  K );.    if( pSo
4df0: 72 74 65 72 2d 3e 69 52 65 61 64 4f 66 66 3e 3d  rter->iReadOff>=
4e00: 70 53 6f 72 74 65 72 2d 3e 69 57 72 69 74 65 4f  pSorter->iWriteO
4e10: 66 66 20 29 20 62 72 65 61 6b 3b 0a 20 20 7d 0a  ff ) break;.  }.
4e20: 0a 20 20 2f 2a 20 49 6e 69 74 69 61 6c 69 7a 65  .  /* Initialize
4e30: 20 74 68 65 20 61 54 72 65 65 5b 5d 20 61 72 72   the aTree[] arr
4e40: 61 79 2e 20 2a 2f 0a 20 20 66 6f 72 28 69 3d 70  ay. */.  for(i=p
4e50: 53 6f 72 74 65 72 2d 3e 6e 54 72 65 65 2d 31 3b  Sorter->nTree-1;
4e60: 20 72 63 3d 3d 53 51 4c 49 54 45 5f 4f 4b 20 26   rc==SQLITE_OK &
4e70: 26 20 69 3e 30 3b 20 69 2d 2d 29 7b 0a 20 20 20  & i>0; i--){.   
4e80: 20 72 63 20 3d 20 76 64 62 65 53 6f 72 74 65 72   rc = vdbeSorter
4e90: 44 6f 43 6f 6d 70 61 72 65 28 70 43 73 72 2c 20  DoCompare(pCsr, 
4ea0: 69 29 3b 0a 20 20 7d 0a 0a 20 20 2a 70 6e 42 79  i);.  }..  *pnBy
4eb0: 74 65 20 3d 20 6e 42 79 74 65 3b 0a 20 20 72 65  te = nByte;.  re
4ec0: 74 75 72 6e 20 72 63 3b 0a 7d 0a 0a 2f 2a 0a 2a  turn rc;.}../*.*
4ed0: 2a 20 4f 6e 63 65 20 74 68 65 20 73 6f 72 74 65  * Once the sorte
4ee0: 72 20 68 61 73 20 62 65 65 6e 20 70 6f 70 75 6c  r has been popul
4ef0: 61 74 65 64 2c 20 74 68 69 73 20 66 75 6e 63 74  ated, this funct
4f00: 69 6f 6e 20 69 73 20 63 61 6c 6c 65 64 20 74 6f  ion is called to
4f10: 20 70 72 65 70 61 72 65 0a 2a 2a 20 66 6f 72 20   prepare.** for 
4f20: 69 74 65 72 61 74 69 6e 67 20 74 68 72 6f 75 67  iterating throug
4f30: 68 20 69 74 73 20 63 6f 6e 74 65 6e 74 73 20 69  h its contents i
4f40: 6e 20 73 6f 72 74 65 64 20 6f 72 64 65 72 2e 0a  n sorted order..
4f50: 2a 2f 0a 69 6e 74 20 73 71 6c 69 74 65 33 56 64  */.int sqlite3Vd
4f60: 62 65 53 6f 72 74 65 72 52 65 77 69 6e 64 28 73  beSorterRewind(s
4f70: 71 6c 69 74 65 33 20 2a 64 62 2c 20 56 64 62 65  qlite3 *db, Vdbe
4f80: 43 75 72 73 6f 72 20 2a 70 43 73 72 2c 20 69 6e  Cursor *pCsr, in
4f90: 74 20 2a 70 62 45 6f 66 29 7b 0a 20 20 56 64 62  t *pbEof){.  Vdb
4fa0: 65 53 6f 72 74 65 72 20 2a 70 53 6f 72 74 65 72  eSorter *pSorter
4fb0: 20 3d 20 70 43 73 72 2d 3e 70 53 6f 72 74 65 72   = pCsr->pSorter
4fc0: 3b 0a 20 20 69 6e 74 20 72 63 3b 20 20 20 20 20  ;.  int rc;     
4fd0: 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20                  
4fe0: 20 20 20 20 2f 2a 20 52 65 74 75 72 6e 20 63 6f      /* Return co
4ff0: 64 65 20 2a 2f 0a 20 20 73 71 6c 69 74 65 33 5f  de */.  sqlite3_
5000: 66 69 6c 65 20 2a 70 54 65 6d 70 32 20 3d 20 30  file *pTemp2 = 0
5010: 3b 20 20 20 20 20 20 20 2f 2a 20 53 65 63 6f 6e  ;       /* Secon
5020: 64 20 74 65 6d 70 20 66 69 6c 65 20 74 6f 20 75  d temp file to u
5030: 73 65 20 2a 2f 0a 20 20 69 36 34 20 69 57 72 69  se */.  i64 iWri
5040: 74 65 32 20 3d 20 30 3b 20 20 20 20 20 20 20 20  te2 = 0;        
5050: 20 20 20 20 20 20 20 20 2f 2a 20 57 72 69 74 65          /* Write
5060: 20 6f 66 66 73 65 74 20 66 6f 72 20 70 54 65 6d   offset for pTem
5070: 70 32 20 2a 2f 0a 20 20 69 6e 74 20 6e 49 74 65  p2 */.  int nIte
5080: 72 3b 20 20 20 20 20 20 20 20 20 20 20 20 20 20  r;              
5090: 20 20 20 20 20 20 20 20 2f 2a 20 4e 75 6d 62 65          /* Numbe
50a0: 72 20 6f 66 20 69 74 65 72 61 74 6f 72 73 20 75  r of iterators u
50b0: 73 65 64 20 2a 2f 0a 20 20 69 6e 74 20 6e 42 79  sed */.  int nBy
50c0: 74 65 3b 20 20 20 20 20 20 20 20 20 20 20 20 20  te;             
50d0: 20 20 20 20 20 20 20 20 20 2f 2a 20 42 79 74 65           /* Byte
50e0: 73 20 6f 66 20 73 70 61 63 65 20 72 65 71 75 69  s of space requi
50f0: 72 65 64 20 66 6f 72 20 61 49 74 65 72 2f 61 54  red for aIter/aT
5100: 72 65 65 20 2a 2f 0a 20 20 69 6e 74 20 4e 20 3d  ree */.  int N =
5110: 20 32 3b 20 20 20 20 20 20 20 20 20 20 20 20 20   2;             
5120: 20 20 20 20 20 20 20 20 20 2f 2a 20 50 6f 77 65           /* Powe
5130: 72 20 6f 66 20 32 20 3e 3d 20 6e 49 74 65 72 20  r of 2 >= nIter 
5140: 2a 2f 0a 0a 20 20 61 73 73 65 72 74 28 20 70 53  */..  assert( pS
5150: 6f 72 74 65 72 20 29 3b 0a 0a 20 20 2f 2a 20 57  orter );..  /* W
5160: 72 69 74 65 20 74 68 65 20 63 75 72 72 65 6e 74  rite the current
5170: 20 62 2d 74 72 65 65 20 74 6f 20 61 20 50 4d 41   b-tree to a PMA
5180: 2e 20 43 6c 6f 73 65 20 74 68 65 20 62 2d 74 72  . Close the b-tr
5190: 65 65 20 63 75 72 73 6f 72 2e 20 2a 2f 0a 20 20  ee cursor. */.  
51a0: 72 63 20 3d 20 76 64 62 65 53 6f 72 74 65 72 42  rc = vdbeSorterB
51b0: 74 72 65 65 54 6f 50 4d 41 28 64 62 2c 20 70 43  treeToPMA(db, pC
51c0: 73 72 29 3b 0a 20 20 73 71 6c 69 74 65 33 42 74  sr);.  sqlite3Bt
51d0: 72 65 65 43 6c 6f 73 65 43 75 72 73 6f 72 28 70  reeCloseCursor(p
51e0: 43 73 72 2d 3e 70 43 75 72 73 6f 72 29 3b 0a 20  Csr->pCursor);. 
51f0: 20 69 66 28 20 72 63 21 3d 53 51 4c 49 54 45 5f   if( rc!=SQLITE_
5200: 4f 4b 20 29 20 72 65 74 75 72 6e 20 72 63 3b 0a  OK ) return rc;.
5210: 20 20 69 66 28 20 70 53 6f 72 74 65 72 2d 3e 6e    if( pSorter->n
5220: 50 4d 41 3d 3d 30 20 29 7b 0a 20 20 20 20 2a 70  PMA==0 ){.    *p
5230: 62 45 6f 66 20 3d 20 31 3b 0a 20 20 20 20 72 65  bEof = 1;.    re
5240: 74 75 72 6e 20 53 51 4c 49 54 45 5f 4f 4b 3b 0a  turn SQLITE_OK;.
5250: 20 20 7d 0a 0a 20 20 2f 2a 20 41 6c 6c 6f 63 61    }..  /* Alloca
5260: 74 65 20 73 70 61 63 65 20 66 6f 72 20 61 49 74  te space for aIt
5270: 65 72 5b 5d 20 61 6e 64 20 61 54 72 65 65 5b 5d  er[] and aTree[]
5280: 2e 20 2a 2f 0a 20 20 6e 49 74 65 72 20 3d 20 70  . */.  nIter = p
5290: 53 6f 72 74 65 72 2d 3e 6e 50 4d 41 3b 0a 20 20  Sorter->nPMA;.  
52a0: 69 66 28 20 6e 49 74 65 72 3e 53 4f 52 54 45 52  if( nIter>SORTER
52b0: 5f 4d 41 58 5f 4d 45 52 47 45 5f 43 4f 55 4e 54  _MAX_MERGE_COUNT
52c0: 20 29 20 6e 49 74 65 72 20 3d 20 53 4f 52 54 45   ) nIter = SORTE
52d0: 52 5f 4d 41 58 5f 4d 45 52 47 45 5f 43 4f 55 4e  R_MAX_MERGE_COUN
52e0: 54 3b 0a 20 20 61 73 73 65 72 74 28 20 6e 49 74  T;.  assert( nIt
52f0: 65 72 3e 30 20 29 3b 0a 20 20 77 68 69 6c 65 28  er>0 );.  while(
5300: 20 4e 3c 6e 49 74 65 72 20 29 20 4e 20 2b 3d 20   N<nIter ) N += 
5310: 4e 3b 0a 20 20 6e 42 79 74 65 20 3d 20 4e 20 2a  N;.  nByte = N *
5320: 20 28 73 69 7a 65 6f 66 28 69 6e 74 29 20 2b 20   (sizeof(int) + 
5330: 73 69 7a 65 6f 66 28 56 64 62 65 53 6f 72 74 65  sizeof(VdbeSorte
5340: 72 49 74 65 72 29 29 3b 0a 20 20 70 53 6f 72 74  rIter));.  pSort
5350: 65 72 2d 3e 61 49 74 65 72 20 3d 20 28 56 64 62  er->aIter = (Vdb
5360: 65 53 6f 72 74 65 72 49 74 65 72 20 2a 29 73 71  eSorterIter *)sq
5370: 6c 69 74 65 33 44 62 4d 61 6c 6c 6f 63 5a 65 72  lite3DbMallocZer
5380: 6f 28 64 62 2c 20 6e 42 79 74 65 29 3b 0a 20 20  o(db, nByte);.  
5390: 69 66 28 20 21 70 53 6f 72 74 65 72 2d 3e 61 49  if( !pSorter->aI
53a0: 74 65 72 20 29 20 72 65 74 75 72 6e 20 53 51 4c  ter ) return SQL
53b0: 49 54 45 5f 4e 4f 4d 45 4d 3b 0a 20 20 70 53 6f  ITE_NOMEM;.  pSo
53c0: 72 74 65 72 2d 3e 61 54 72 65 65 20 3d 20 28 69  rter->aTree = (i
53d0: 6e 74 20 2a 29 26 70 53 6f 72 74 65 72 2d 3e 61  nt *)&pSorter->a
53e0: 49 74 65 72 5b 4e 5d 3b 0a 20 20 70 53 6f 72 74  Iter[N];.  pSort
53f0: 65 72 2d 3e 6e 54 72 65 65 20 3d 20 4e 3b 0a 0a  er->nTree = N;..
5400: 20 20 64 6f 20 7b 0a 20 20 20 20 69 6e 74 20 69    do {.    int i
5410: 4e 65 77 3b 20 20 20 20 20 20 20 20 20 20 20 20  New;            
5420: 20 20 20 20 20 20 20 20 20 2f 2a 20 49 6e 64 65           /* Inde
5430: 78 20 6f 66 20 6e 65 77 2c 20 6d 65 72 67 65 64  x of new, merged
5440: 2c 20 50 4d 41 20 2a 2f 0a 0a 20 20 20 20 66 6f  , PMA */..    fo
5450: 72 28 69 4e 65 77 3d 30 3b 20 0a 20 20 20 20 20  r(iNew=0; .     
5460: 20 20 20 72 63 3d 3d 53 51 4c 49 54 45 5f 4f 4b     rc==SQLITE_OK
5470: 20 26 26 20 69 4e 65 77 2a 53 4f 52 54 45 52 5f   && iNew*SORTER_
5480: 4d 41 58 5f 4d 45 52 47 45 5f 43 4f 55 4e 54 3c  MAX_MERGE_COUNT<
5490: 70 53 6f 72 74 65 72 2d 3e 6e 50 4d 41 3b 20 0a  pSorter->nPMA; .
54a0: 20 20 20 20 20 20 20 20 69 4e 65 77 2b 2b 0a 20          iNew++. 
54b0: 20 20 20 29 7b 0a 20 20 20 20 20 20 69 36 34 20     ){.      i64 
54c0: 6e 57 72 69 74 65 3b 20 20 20 20 20 20 20 20 20  nWrite;         
54d0: 20 20 20 20 20 20 20 20 2f 2a 20 4e 75 6d 62 65          /* Numbe
54e0: 72 20 6f 66 20 62 79 74 65 73 20 69 6e 20 6e 65  r of bytes in ne
54f0: 77 20 50 4d 41 20 2a 2f 0a 0a 20 20 20 20 20 20  w PMA */..      
5500: 2f 2a 20 49 66 20 74 68 65 72 65 20 61 72 65 20  /* If there are 
5510: 53 4f 52 54 45 52 5f 4d 41 58 5f 4d 45 52 47 45  SORTER_MAX_MERGE
5520: 5f 43 4f 55 4e 54 20 6f 72 20 6c 65 73 73 20 50  _COUNT or less P
5530: 4d 41 73 20 69 6e 20 66 69 6c 65 20 70 54 65 6d  MAs in file pTem
5540: 70 31 2c 0a 20 20 20 20 20 20 2a 2a 20 69 6e 69  p1,.      ** ini
5550: 74 69 61 6c 69 7a 65 20 61 6e 20 69 74 65 72 61  tialize an itera
5560: 74 6f 72 20 66 6f 72 20 65 61 63 68 20 6f 66 20  tor for each of 
5570: 74 68 65 6d 20 61 6e 64 20 62 72 65 61 6b 20 6f  them and break o
5580: 75 74 20 6f 66 20 74 68 65 20 6c 6f 6f 70 2e 0a  ut of the loop..
5590: 20 20 20 20 20 20 2a 2a 20 54 68 65 73 65 20 69        ** These i
55a0: 74 65 72 61 74 6f 72 73 20 77 69 6c 6c 20 62 65  terators will be
55b0: 20 69 6e 63 72 65 6d 65 6e 74 61 6c 6c 79 20 6d   incrementally m
55c0: 65 72 67 65 64 20 61 73 20 74 68 65 20 56 44 42  erged as the VDB
55d0: 45 20 6c 61 79 65 72 20 63 61 6c 6c 73 0a 20 20  E layer calls.  
55e0: 20 20 20 20 2a 2a 20 73 71 6c 69 74 65 33 56 64      ** sqlite3Vd
55f0: 62 65 53 6f 72 74 65 72 4e 65 78 74 28 29 2e 0a  beSorterNext()..
5600: 20 20 20 20 20 20 2a 2a 0a 20 20 20 20 20 20 2a        **.      *
5610: 2a 20 4f 74 68 65 72 77 69 73 65 2c 20 69 66 20  * Otherwise, if 
5620: 70 54 65 6d 70 31 20 63 6f 6e 74 61 69 6e 73 20  pTemp1 contains 
5630: 6d 6f 72 65 20 74 68 61 6e 20 53 4f 52 54 45 52  more than SORTER
5640: 5f 4d 41 58 5f 4d 45 52 47 45 5f 43 4f 55 4e 54  _MAX_MERGE_COUNT
5650: 20 50 4d 41 73 2c 0a 20 20 20 20 20 20 2a 2a 20   PMAs,.      ** 
5660: 69 6e 69 74 69 61 6c 69 7a 65 20 69 6e 74 65 72  initialize inter
5670: 61 74 6f 72 73 20 66 6f 72 20 53 4f 52 54 45 52  ators for SORTER
5680: 5f 4d 41 58 5f 4d 45 52 47 45 5f 43 4f 55 4e 54  _MAX_MERGE_COUNT
5690: 20 6f 66 20 74 68 65 6d 2e 20 54 68 65 73 65 20   of them. These 
56a0: 50 4d 41 73 0a 20 20 20 20 20 20 2a 2a 20 61 72  PMAs.      ** ar
56b0: 65 20 6d 65 72 67 65 64 20 69 6e 74 6f 20 61 20  e merged into a 
56c0: 73 69 6e 67 6c 65 20 50 4d 41 20 74 68 61 74 20  single PMA that 
56d0: 69 73 20 77 72 69 74 74 65 6e 20 74 6f 20 66 69  is written to fi
56e0: 6c 65 20 70 54 65 6d 70 32 2e 0a 20 20 20 20 20  le pTemp2..     
56f0: 20 2a 2f 0a 20 20 20 20 20 20 72 63 20 3d 20 76   */.      rc = v
5700: 64 62 65 53 6f 72 74 65 72 49 6e 69 74 4d 65 72  dbeSorterInitMer
5710: 67 65 28 64 62 2c 20 70 43 73 72 2c 20 26 6e 57  ge(db, pCsr, &nW
5720: 72 69 74 65 29 3b 0a 20 20 20 20 20 20 61 73 73  rite);.      ass
5730: 65 72 74 28 20 72 63 21 3d 53 51 4c 49 54 45 5f  ert( rc!=SQLITE_
5740: 4f 4b 20 7c 7c 20 70 53 6f 72 74 65 72 2d 3e 61  OK || pSorter->a
5750: 49 74 65 72 5b 20 70 53 6f 72 74 65 72 2d 3e 61  Iter[ pSorter->a
5760: 54 72 65 65 5b 31 5d 20 5d 2e 70 46 69 6c 65 20  Tree[1] ].pFile 
5770: 29 3b 0a 20 20 20 20 20 20 69 66 28 20 72 63 21  );.      if( rc!
5780: 3d 53 51 4c 49 54 45 5f 4f 4b 20 7c 7c 20 70 53  =SQLITE_OK || pS
5790: 6f 72 74 65 72 2d 3e 6e 50 4d 41 3c 3d 53 4f 52  orter->nPMA<=SOR
57a0: 54 45 52 5f 4d 41 58 5f 4d 45 52 47 45 5f 43 4f  TER_MAX_MERGE_CO
57b0: 55 4e 54 20 29 7b 0a 20 20 20 20 20 20 20 20 62  UNT ){.        b
57c0: 72 65 61 6b 3b 0a 20 20 20 20 20 20 7d 0a 0a 20  reak;.      }.. 
57d0: 20 20 20 20 20 2f 2a 20 4f 70 65 6e 20 74 68 65       /* Open the
57e0: 20 73 65 63 6f 6e 64 20 74 65 6d 70 20 66 69 6c   second temp fil
57f0: 65 2c 20 69 66 20 69 74 20 69 73 20 6e 6f 74 20  e, if it is not 
5800: 61 6c 72 65 61 64 79 20 6f 70 65 6e 2e 20 2a 2f  already open. */
5810: 0a 20 20 20 20 20 20 69 66 28 20 70 54 65 6d 70  .      if( pTemp
5820: 32 3d 3d 30 20 29 7b 0a 20 20 20 20 20 20 20 20  2==0 ){.        
5830: 61 73 73 65 72 74 28 20 69 57 72 69 74 65 32 3d  assert( iWrite2=
5840: 3d 30 20 29 3b 0a 20 20 20 20 20 20 20 20 72 63  =0 );.        rc
5850: 20 3d 20 76 64 62 65 53 6f 72 74 65 72 4f 70 65   = vdbeSorterOpe
5860: 6e 54 65 6d 70 46 69 6c 65 28 64 62 2c 20 26 70  nTempFile(db, &p
5870: 54 65 6d 70 32 29 3b 0a 20 20 20 20 20 20 7d 0a  Temp2);.      }.
5880: 0a 20 20 20 20 20 20 69 66 28 20 72 63 3d 3d 53  .      if( rc==S
5890: 51 4c 49 54 45 5f 4f 4b 20 29 7b 0a 20 20 20 20  QLITE_OK ){.    
58a0: 20 20 20 20 72 63 20 3d 20 76 64 62 65 53 6f 72      rc = vdbeSor
58b0: 74 65 72 57 72 69 74 65 56 61 72 69 6e 74 28 70  terWriteVarint(p
58c0: 54 65 6d 70 32 2c 20 6e 57 72 69 74 65 2c 20 26  Temp2, nWrite, &
58d0: 69 57 72 69 74 65 32 29 3b 0a 20 20 20 20 20 20  iWrite2);.      
58e0: 7d 0a 0a 20 20 20 20 20 20 69 66 28 20 72 63 3d  }..      if( rc=
58f0: 3d 53 51 4c 49 54 45 5f 4f 4b 20 29 7b 0a 20 20  =SQLITE_OK ){.  
5900: 20 20 20 20 20 20 69 6e 74 20 62 45 6f 66 20 3d        int bEof =
5910: 20 30 3b 0a 20 20 20 20 20 20 20 20 77 68 69 6c   0;.        whil
5920: 65 28 20 72 63 3d 3d 53 51 4c 49 54 45 5f 4f 4b  e( rc==SQLITE_OK
5930: 20 26 26 20 62 45 6f 66 3d 3d 30 20 29 7b 0a 20   && bEof==0 ){. 
5940: 20 20 20 20 20 20 20 20 20 69 6e 74 20 6e 54 6f           int nTo
5950: 57 72 69 74 65 3b 0a 20 20 20 20 20 20 20 20 20  Write;.         
5960: 20 56 64 62 65 53 6f 72 74 65 72 49 74 65 72 20   VdbeSorterIter 
5970: 2a 70 49 74 65 72 20 3d 20 26 70 53 6f 72 74 65  *pIter = &pSorte
5980: 72 2d 3e 61 49 74 65 72 5b 20 70 53 6f 72 74 65  r->aIter[ pSorte
5990: 72 2d 3e 61 54 72 65 65 5b 31 5d 20 5d 3b 0a 20  r->aTree[1] ];. 
59a0: 20 20 20 20 20 20 20 20 20 61 73 73 65 72 74 28           assert(
59b0: 20 70 49 74 65 72 2d 3e 70 46 69 6c 65 20 29 3b   pIter->pFile );
59c0: 0a 20 20 20 20 20 20 20 20 20 20 6e 54 6f 57 72  .          nToWr
59d0: 69 74 65 20 3d 20 70 49 74 65 72 2d 3e 6e 4b 65  ite = pIter->nKe
59e0: 79 20 2b 20 73 71 6c 69 74 65 33 56 61 72 69 6e  y + sqlite3Varin
59f0: 74 4c 65 6e 28 70 49 74 65 72 2d 3e 6e 4b 65 79  tLen(pIter->nKey
5a00: 29 3b 0a 20 20 20 20 20 20 20 20 20 20 72 63 20  );.          rc 
5a10: 3d 20 73 71 6c 69 74 65 33 4f 73 57 72 69 74 65  = sqlite3OsWrite
5a20: 28 70 54 65 6d 70 32 2c 20 70 49 74 65 72 2d 3e  (pTemp2, pIter->
5a30: 61 41 6c 6c 6f 63 2c 20 6e 54 6f 57 72 69 74 65  aAlloc, nToWrite
5a40: 2c 20 69 57 72 69 74 65 32 29 3b 0a 20 20 20 20  , iWrite2);.    
5a50: 20 20 20 20 20 20 69 57 72 69 74 65 32 20 2b 3d        iWrite2 +=
5a60: 20 6e 54 6f 57 72 69 74 65 3b 0a 20 20 20 20 20   nToWrite;.     
5a70: 20 20 20 20 20 69 66 28 20 72 63 3d 3d 53 51 4c       if( rc==SQL
5a80: 49 54 45 5f 4f 4b 20 29 7b 0a 20 20 20 20 20 20  ITE_OK ){.      
5a90: 20 20 20 20 20 20 72 63 20 3d 20 73 71 6c 69 74        rc = sqlit
5aa0: 65 33 56 64 62 65 53 6f 72 74 65 72 4e 65 78 74  e3VdbeSorterNext
5ab0: 28 64 62 2c 20 70 43 73 72 2c 20 26 62 45 6f 66  (db, pCsr, &bEof
5ac0: 29 3b 0a 20 20 20 20 20 20 20 20 20 20 7d 0a 20  );.          }. 
5ad0: 20 20 20 20 20 20 20 7d 0a 20 20 20 20 20 20 7d         }.      }
5ae0: 0a 20 20 20 20 7d 0a 0a 20 20 20 20 69 66 28 20  .    }..    if( 
5af0: 70 53 6f 72 74 65 72 2d 3e 6e 50 4d 41 3c 3d 53  pSorter->nPMA<=S
5b00: 4f 52 54 45 52 5f 4d 41 58 5f 4d 45 52 47 45 5f  ORTER_MAX_MERGE_
5b10: 43 4f 55 4e 54 20 29 7b 0a 20 20 20 20 20 20 62  COUNT ){.      b
5b20: 72 65 61 6b 3b 0a 20 20 20 20 7d 65 6c 73 65 7b  reak;.    }else{
5b30: 0a 20 20 20 20 20 20 73 71 6c 69 74 65 33 5f 66  .      sqlite3_f
5b40: 69 6c 65 20 2a 70 54 6d 70 20 3d 20 70 53 6f 72  ile *pTmp = pSor
5b50: 74 65 72 2d 3e 70 54 65 6d 70 31 3b 0a 20 20 20  ter->pTemp1;.   
5b60: 20 20 20 70 53 6f 72 74 65 72 2d 3e 6e 50 4d 41     pSorter->nPMA
5b70: 20 3d 20 69 4e 65 77 3b 0a 20 20 20 20 20 20 70   = iNew;.      p
5b80: 53 6f 72 74 65 72 2d 3e 70 54 65 6d 70 31 20 3d  Sorter->pTemp1 =
5b90: 20 70 54 65 6d 70 32 3b 0a 20 20 20 20 20 20 70   pTemp2;.      p
5ba0: 54 65 6d 70 32 20 3d 20 70 54 6d 70 3b 0a 20 20  Temp2 = pTmp;.  
5bb0: 20 20 20 20 70 53 6f 72 74 65 72 2d 3e 69 57 72      pSorter->iWr
5bc0: 69 74 65 4f 66 66 20 3d 20 69 57 72 69 74 65 32  iteOff = iWrite2
5bd0: 3b 0a 20 20 20 20 20 20 70 53 6f 72 74 65 72 2d  ;.      pSorter-
5be0: 3e 69 52 65 61 64 4f 66 66 20 3d 20 30 3b 0a 20  >iReadOff = 0;. 
5bf0: 20 20 20 20 20 69 57 72 69 74 65 32 20 3d 20 30       iWrite2 = 0
5c00: 3b 0a 20 20 20 20 7d 0a 20 20 7d 77 68 69 6c 65  ;.    }.  }while
5c10: 28 20 72 63 3d 3d 53 51 4c 49 54 45 5f 4f 4b 20  ( rc==SQLITE_OK 
5c20: 29 3b 0a 0a 20 20 69 66 28 20 70 54 65 6d 70 32  );..  if( pTemp2
5c30: 20 29 7b 0a 20 20 20 20 73 71 6c 69 74 65 33 4f   ){.    sqlite3O
5c40: 73 43 6c 6f 73 65 46 72 65 65 28 70 54 65 6d 70  sCloseFree(pTemp
5c50: 32 29 3b 0a 20 20 7d 0a 20 20 2a 70 62 45 6f 66  2);.  }.  *pbEof
5c60: 20 3d 20 28 70 53 6f 72 74 65 72 2d 3e 61 49 74   = (pSorter->aIt
5c70: 65 72 5b 70 53 6f 72 74 65 72 2d 3e 61 54 72 65  er[pSorter->aTre
5c80: 65 5b 31 5d 5d 2e 70 46 69 6c 65 3d 3d 30 29 3b  e[1]].pFile==0);
5c90: 0a 20 20 72 65 74 75 72 6e 20 72 63 3b 0a 7d 0a  .  return rc;.}.
5ca0: 0a 2f 2a 0a 2a 2a 20 41 64 76 61 6e 63 65 20 74  ./*.** Advance t
5cb0: 6f 20 74 68 65 20 6e 65 78 74 20 65 6c 65 6d 65  o the next eleme
5cc0: 6e 74 20 69 6e 20 74 68 65 20 73 6f 72 74 65 72  nt in the sorter
5cd0: 2e 0a 2a 2f 0a 69 6e 74 20 73 71 6c 69 74 65 33  ..*/.int sqlite3
5ce0: 56 64 62 65 53 6f 72 74 65 72 4e 65 78 74 28 73  VdbeSorterNext(s
5cf0: 71 6c 69 74 65 33 20 2a 64 62 2c 20 56 64 62 65  qlite3 *db, Vdbe
5d00: 43 75 72 73 6f 72 20 2a 70 43 73 72 2c 20 69 6e  Cursor *pCsr, in
5d10: 74 20 2a 70 62 45 6f 66 29 7b 0a 20 20 56 64 62  t *pbEof){.  Vdb
5d20: 65 53 6f 72 74 65 72 20 2a 70 53 6f 72 74 65 72  eSorter *pSorter
5d30: 20 3d 20 70 43 73 72 2d 3e 70 53 6f 72 74 65 72   = pCsr->pSorter
5d40: 3b 0a 20 20 69 6e 74 20 69 50 72 65 76 20 3d 20  ;.  int iPrev = 
5d50: 70 53 6f 72 74 65 72 2d 3e 61 54 72 65 65 5b 31  pSorter->aTree[1
5d60: 5d 3b 20 20 2f 2a 20 49 6e 64 65 78 20 6f 66 20  ];  /* Index of 
5d70: 69 74 65 72 61 74 6f 72 20 74 6f 20 61 64 76 61  iterator to adva
5d80: 6e 63 65 20 2a 2f 0a 20 20 69 6e 74 20 69 3b 20  nce */.  int i; 
5d90: 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20                  
5da0: 20 20 20 20 20 20 20 20 20 2f 2a 20 49 6e 64 65           /* Inde
5db0: 78 20 6f 66 20 61 54 72 65 65 5b 5d 20 74 6f 20  x of aTree[] to 
5dc0: 72 65 63 61 6c 63 75 6c 61 74 65 20 2a 2f 0a 20  recalculate */. 
5dd0: 20 69 6e 74 20 72 63 3b 20 20 20 20 20 20 20 20   int rc;        
5de0: 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20                  
5df0: 20 2f 2a 20 52 65 74 75 72 6e 20 63 6f 64 65 20   /* Return code 
5e00: 2a 2f 0a 0a 20 20 72 63 20 3d 20 76 64 62 65 53  */..  rc = vdbeS
5e10: 6f 72 74 65 72 49 74 65 72 4e 65 78 74 28 64 62  orterIterNext(db
5e20: 2c 20 26 70 53 6f 72 74 65 72 2d 3e 61 49 74 65  , &pSorter->aIte
5e30: 72 5b 69 50 72 65 76 5d 29 3b 0a 20 20 66 6f 72  r[iPrev]);.  for
5e40: 28 69 3d 28 70 53 6f 72 74 65 72 2d 3e 6e 54 72  (i=(pSorter->nTr
5e50: 65 65 2b 69 50 72 65 76 29 2f 32 3b 20 72 63 3d  ee+iPrev)/2; rc=
5e60: 3d 53 51 4c 49 54 45 5f 4f 4b 20 26 26 20 69 3e  =SQLITE_OK && i>
5e70: 30 3b 20 69 3d 69 2f 32 29 7b 0a 20 20 20 20 72  0; i=i/2){.    r
5e80: 63 20 3d 20 76 64 62 65 53 6f 72 74 65 72 44 6f  c = vdbeSorterDo
5e90: 43 6f 6d 70 61 72 65 28 70 43 73 72 2c 20 69 29  Compare(pCsr, i)
5ea0: 3b 0a 20 20 7d 0a 0a 20 20 2a 70 62 45 6f 66 20  ;.  }..  *pbEof 
5eb0: 3d 20 28 70 53 6f 72 74 65 72 2d 3e 61 49 74 65  = (pSorter->aIte
5ec0: 72 5b 70 53 6f 72 74 65 72 2d 3e 61 54 72 65 65  r[pSorter->aTree
5ed0: 5b 31 5d 5d 2e 70 46 69 6c 65 3d 3d 30 29 3b 0a  [1]].pFile==0);.
5ee0: 20 20 72 65 74 75 72 6e 20 72 63 3b 0a 7d 0a 0a    return rc;.}..
5ef0: 2f 2a 0a 2a 2a 20 43 6f 70 79 20 74 68 65 20 63  /*.** Copy the c
5f00: 75 72 72 65 6e 74 20 73 6f 72 74 65 72 20 6b 65  urrent sorter ke
5f10: 79 20 69 6e 74 6f 20 74 68 65 20 6d 65 6d 6f 72  y into the memor
5f20: 79 20 63 65 6c 6c 20 70 4f 75 74 2e 0a 2a 2f 0a  y cell pOut..*/.
5f30: 69 6e 74 20 73 71 6c 69 74 65 33 56 64 62 65 53  int sqlite3VdbeS
5f40: 6f 72 74 65 72 52 6f 77 6b 65 79 28 56 64 62 65  orterRowkey(Vdbe
5f50: 43 75 72 73 6f 72 20 2a 70 43 73 72 2c 20 4d 65  Cursor *pCsr, Me
5f60: 6d 20 2a 70 4f 75 74 29 7b 0a 20 20 56 64 62 65  m *pOut){.  Vdbe
5f70: 53 6f 72 74 65 72 20 2a 70 53 6f 72 74 65 72 20  Sorter *pSorter 
5f80: 3d 20 70 43 73 72 2d 3e 70 53 6f 72 74 65 72 3b  = pCsr->pSorter;
5f90: 0a 20 20 56 64 62 65 53 6f 72 74 65 72 49 74 65  .  VdbeSorterIte
5fa0: 72 20 2a 70 49 74 65 72 3b 0a 0a 20 20 70 49 74  r *pIter;..  pIt
5fb0: 65 72 20 3d 20 26 70 53 6f 72 74 65 72 2d 3e 61  er = &pSorter->a
5fc0: 49 74 65 72 5b 20 70 53 6f 72 74 65 72 2d 3e 61  Iter[ pSorter->a
5fd0: 54 72 65 65 5b 31 5d 20 5d 3b 0a 0a 20 20 2f 2a  Tree[1] ];..  /*
5fe0: 20 43 6f 76 65 72 61 67 65 20 74 65 73 74 69 6e   Coverage testin
5ff0: 67 20 6e 6f 74 65 3a 20 41 73 20 74 68 69 6e 67  g note: As thing
6000: 73 20 61 72 65 20 63 75 72 72 65 6e 74 6c 79 2c  s are currently,
6010: 20 74 68 69 73 20 63 61 6c 6c 20 77 69 6c 6c 20   this call will 
6020: 61 6c 77 61 79 73 0a 20 20 2a 2a 20 73 75 63 63  always.  ** succ
6030: 65 65 64 2e 20 54 68 69 73 20 69 73 20 62 65 63  eed. This is bec
6040: 61 75 73 65 20 74 68 65 20 6d 65 6d 6f 72 79 20  ause the memory 
6050: 63 65 6c 6c 20 70 61 73 73 65 64 20 62 79 20 74  cell passed by t
6060: 68 65 20 56 44 42 45 20 6c 61 79 65 72 20 0a 20  he VDBE layer . 
6070: 20 2a 2a 20 68 61 70 70 65 6e 73 20 74 6f 20 62   ** happens to b
6080: 65 20 74 68 65 20 73 61 6d 65 20 6f 6e 65 20 61  e the same one a
6090: 73 20 77 61 73 20 75 73 65 64 20 74 6f 20 61 73  s was used to as
60a0: 73 65 6d 62 6c 65 20 74 68 65 20 6b 65 79 73 20  semble the keys 
60b0: 62 65 66 6f 72 65 20 74 68 65 79 0a 20 20 2a 2a  before they.  **
60c0: 20 77 65 72 65 20 70 61 73 73 65 64 20 74 6f 20   were passed to 
60d0: 74 68 65 20 73 6f 72 74 65 72 20 2d 20 6d 65 61  the sorter - mea
60e0: 6e 69 6e 67 20 69 74 20 69 73 20 61 6c 77 61 79  ning it is alway
60f0: 73 20 6c 61 72 67 65 20 65 6e 6f 75 67 68 20 66  s large enough f
6100: 6f 72 20 74 68 65 0a 20 20 2a 2a 20 6c 61 72 67  or the.  ** larg
6110: 65 73 74 20 6b 65 79 2e 20 42 75 74 20 74 68 69  est key. But thi
6120: 73 20 63 6f 75 6c 64 20 63 68 61 6e 67 65 20 76  s could change v
6130: 65 72 79 20 65 61 73 69 6c 79 2c 20 73 6f 20 77  ery easily, so w
6140: 65 20 6c 65 61 76 65 20 74 68 65 20 63 61 6c 6c  e leave the call
6150: 0a 20 20 2a 2a 20 74 6f 20 73 71 6c 69 74 65 33  .  ** to sqlite3
6160: 56 64 62 65 4d 65 6d 47 72 6f 77 28 29 20 69 6e  VdbeMemGrow() in
6170: 2e 20 2a 2f 0a 20 20 69 66 28 20 4e 45 56 45 52  . */.  if( NEVER
6180: 28 73 71 6c 69 74 65 33 56 64 62 65 4d 65 6d 47  (sqlite3VdbeMemG
6190: 72 6f 77 28 70 4f 75 74 2c 20 70 49 74 65 72 2d  row(pOut, pIter-
61a0: 3e 6e 4b 65 79 2c 20 30 29 29 20 29 7b 0a 20 20  >nKey, 0)) ){.  
61b0: 20 20 72 65 74 75 72 6e 20 53 51 4c 49 54 45 5f    return SQLITE_
61c0: 4e 4f 4d 45 4d 3b 0a 20 20 7d 0a 20 20 70 4f 75  NOMEM;.  }.  pOu
61d0: 74 2d 3e 6e 20 3d 20 70 49 74 65 72 2d 3e 6e 4b  t->n = pIter->nK
61e0: 65 79 3b 0a 20 20 4d 65 6d 53 65 74 54 79 70 65  ey;.  MemSetType
61f0: 46 6c 61 67 28 70 4f 75 74 2c 20 4d 45 4d 5f 42  Flag(pOut, MEM_B
6200: 6c 6f 62 29 3b 0a 20 20 6d 65 6d 63 70 79 28 70  lob);.  memcpy(p
6210: 4f 75 74 2d 3e 7a 2c 20 70 49 74 65 72 2d 3e 61  Out->z, pIter->a
6220: 4b 65 79 2c 20 70 49 74 65 72 2d 3e 6e 4b 65 79  Key, pIter->nKey
6230: 29 3b 0a 0a 20 20 72 65 74 75 72 6e 20 53 51 4c  );..  return SQL
6240: 49 54 45 5f 4f 4b 3b 0a 7d 0a 0a 23 65 6e 64 69  ITE_OK;.}..#endi
6250: 66 20 2f 2a 20 23 69 66 6e 64 65 66 20 53 51 4c  f /* #ifndef SQL
6260: 49 54 45 5f 4f 4d 49 54 5f 4d 45 52 47 45 5f 53  ITE_OMIT_MERGE_S
6270: 4f 52 54 20 2a 2f 0a                             ORT */.