/ Hex Artifact Content
Login

Artifact 345235345a414bf387f1254fe3695bb566bf66d7:


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 74 79 70 65 64 65  beInt.h"..typede
0290: 66 20 73 74 72 75 63 74 20 56 64 62 65 53 6f 72  f struct VdbeSor
02a0: 74 65 72 49 74 65 72 20 56 64 62 65 53 6f 72 74  terIter VdbeSort
02b0: 65 72 49 74 65 72 3b 0a 0a 2f 2a 0a 2a 2a 20 41  erIter;../*.** A
02c0: 73 20 6b 65 79 73 20 61 72 65 20 61 64 64 65 64  s keys are added
02d0: 20 74 6f 20 74 68 65 20 73 6f 72 74 65 72 2c 20   to the sorter, 
02e0: 74 68 65 79 20 61 72 65 20 77 72 69 74 74 65 6e  they are written
02f0: 20 74 6f 20 64 69 73 6b 20 69 6e 20 61 20 73 65   to disk in a se
0300: 72 69 65 73 0a 2a 2a 20 6f 66 20 73 6f 72 74 65  ries.** of sorte
0310: 64 20 70 61 63 6b 65 64 2d 6d 65 6d 6f 72 79 2d  d packed-memory-
0320: 61 72 72 61 79 73 20 28 50 4d 41 73 29 2e 20 54  arrays (PMAs). T
0330: 68 65 20 73 69 7a 65 20 6f 66 20 65 61 63 68 20  he size of each 
0340: 50 4d 41 20 69 73 20 72 6f 75 67 68 6c 79 0a 2a  PMA is roughly.*
0350: 2a 20 74 68 65 20 73 61 6d 65 20 61 73 20 74 68  * the same as th
0360: 65 20 63 61 63 68 65 2d 73 69 7a 65 20 61 6c 6c  e cache-size all
0370: 6f 77 65 64 20 66 6f 72 20 74 65 6d 70 6f 72 61  owed for tempora
0380: 72 79 20 64 61 74 61 62 61 73 65 73 2e 20 49 6e  ry databases. In
0390: 20 6f 72 64 65 72 0a 2a 2a 20 74 6f 20 61 6c 6c   order.** to all
03a0: 6f 77 20 74 68 65 20 63 61 6c 6c 65 72 20 74 6f  ow the caller to
03b0: 20 65 78 74 72 61 63 74 20 6b 65 79 73 20 66 72   extract keys fr
03c0: 6f 6d 20 74 68 65 20 73 6f 72 74 65 72 20 69 6e  om the sorter in
03d0: 20 73 6f 72 74 65 64 20 6f 72 64 65 72 2c 0a 2a   sorted order,.*
03e0: 2a 20 61 6c 6c 20 50 4d 41 73 20 63 75 72 72 65  * all PMAs curre
03f0: 6e 74 6c 79 20 73 74 6f 72 65 64 20 6f 6e 20 64  ntly stored on d
0400: 69 73 6b 20 6d 75 73 74 20 62 65 20 6d 65 72 67  isk must be merg
0410: 65 64 20 74 6f 67 65 74 68 65 72 2e 20 54 68 69  ed together. Thi
0420: 73 20 63 6f 6d 6d 65 6e 74 0a 2a 2a 20 64 65 73  s comment.** des
0430: 63 72 69 62 65 73 20 74 68 65 20 64 61 74 61 20  cribes the data 
0440: 73 74 72 75 63 74 75 72 65 20 75 73 65 64 20 74  structure used t
0450: 6f 20 64 6f 20 73 6f 2e 20 54 68 65 20 73 74 72  o do so. The str
0460: 75 63 74 75 72 65 20 73 75 70 70 6f 72 74 73 20  ucture supports 
0470: 0a 2a 2a 20 6d 65 72 67 69 6e 67 20 61 6e 79 20  .** merging any 
0480: 6e 75 6d 62 65 72 20 6f 66 20 61 72 72 61 79 73  number of arrays
0490: 20 69 6e 20 61 20 73 69 6e 67 6c 65 20 70 61 73   in a single pas
04a0: 73 20 77 69 74 68 20 6e 6f 20 72 65 64 75 6e 64  s with no redund
04b0: 61 6e 74 20 63 6f 6d 70 61 72 69 73 6f 6e 20 0a  ant comparison .
04c0: 2a 2a 20 6f 70 65 72 61 74 69 6f 6e 73 2e 0a 2a  ** operations..*
04d0: 2a 0a 2a 2a 20 54 68 65 20 61 49 74 65 72 5b 5d  *.** The aIter[]
04e0: 20 61 72 72 61 79 20 63 6f 6e 74 61 69 6e 73 20   array contains 
04f0: 61 6e 20 69 74 65 72 61 74 6f 72 20 66 6f 72 20  an iterator for 
0500: 65 61 63 68 20 6f 66 20 74 68 65 20 50 4d 41 73  each of the PMAs
0510: 20 62 65 69 6e 67 20 6d 65 72 67 65 64 2e 0a 2a   being merged..*
0520: 2a 20 41 6e 20 61 49 74 65 72 5b 5d 20 69 74 65  * An aIter[] ite
0530: 72 61 74 6f 72 20 65 69 74 68 65 72 20 70 6f 69  rator either poi
0540: 6e 74 73 20 74 6f 20 61 20 76 61 6c 69 64 20 6b  nts to a valid k
0550: 65 79 20 6f 72 20 65 6c 73 65 20 69 73 20 61 74  ey or else is at
0560: 20 45 4f 46 2e 20 46 6f 72 20 0a 2a 2a 20 74 68   EOF. For .** th
0570: 65 20 70 75 72 70 6f 73 65 73 20 6f 66 20 74 68  e purposes of th
0580: 65 20 70 61 72 61 67 72 61 70 68 73 20 62 65 6c  e paragraphs bel
0590: 6f 77 2c 20 77 65 20 61 73 73 75 6d 65 20 74 68  ow, we assume th
05a0: 61 74 20 74 68 65 20 61 72 72 61 79 20 69 73 20  at the array is 
05b0: 61 63 74 75 61 6c 6c 79 20 0a 2a 2a 20 4e 20 65  actually .** N e
05c0: 6c 65 6d 65 6e 74 73 20 69 6e 20 73 69 7a 65 2c  lements in size,
05d0: 20 77 68 65 72 65 20 4e 20 69 73 20 74 68 65 20   where N is the 
05e0: 73 6d 61 6c 6c 65 73 74 20 70 6f 77 65 72 20 6f  smallest power o
05f0: 66 20 32 20 67 72 65 61 74 65 72 20 74 6f 20 6f  f 2 greater to o
0600: 72 20 65 71 75 61 6c 20 0a 2a 2a 20 74 6f 20 74  r equal .** to t
0610: 68 65 20 6e 75 6d 62 65 72 20 6f 66 20 69 74 65  he number of ite
0620: 72 61 74 6f 72 73 20 62 65 69 6e 67 20 6d 65 72  rators being mer
0630: 67 65 64 2e 20 54 68 65 20 65 78 74 72 61 20 61  ged. The extra a
0640: 49 74 65 72 5b 5d 20 65 6c 65 6d 65 6e 74 73 20  Iter[] elements 
0650: 61 72 65 20 0a 2a 2a 20 74 72 65 61 74 65 64 20  are .** treated 
0660: 61 73 20 69 66 20 74 68 65 79 20 61 72 65 20 65  as if they are e
0670: 6d 70 74 79 20 28 61 6c 77 61 79 73 20 61 74 20  mpty (always at 
0680: 45 4f 46 29 2e 0a 2a 2a 0a 2a 2a 20 54 68 65 20  EOF)..**.** The 
0690: 61 54 72 65 65 5b 5d 20 61 72 72 61 79 20 69 73  aTree[] array is
06a0: 20 61 6c 73 6f 20 4e 20 65 6c 65 6d 65 6e 74 73   also N elements
06b0: 20 69 6e 20 73 69 7a 65 2e 20 54 68 65 20 76 61   in size. The va
06c0: 6c 75 65 20 6f 66 20 4e 20 69 73 20 73 74 6f 72  lue of N is stor
06d0: 65 64 20 69 6e 0a 2a 2a 20 74 68 65 20 56 64 62  ed in.** the Vdb
06e0: 65 53 6f 72 74 65 72 2e 6e 54 72 65 65 20 76 61  eSorter.nTree va
06f0: 72 69 61 62 6c 65 2e 0a 2a 2a 0a 2a 2a 20 54 68  riable..**.** Th
0700: 65 20 66 69 6e 61 6c 20 28 4e 2f 32 29 20 65 6c  e final (N/2) el
0710: 65 6d 65 6e 74 73 20 6f 66 20 61 54 72 65 65 5b  ements of aTree[
0720: 5d 20 63 6f 6e 74 61 69 6e 20 74 68 65 20 72 65  ] contain the re
0730: 73 75 6c 74 73 20 6f 66 20 63 6f 6d 70 61 72 69  sults of compari
0740: 6e 67 0a 2a 2a 20 70 61 69 72 73 20 6f 66 20 69  ng.** pairs of i
0750: 74 65 72 61 74 6f 72 20 6b 65 79 73 20 74 6f 67  terator keys tog
0760: 65 74 68 65 72 2e 20 45 6c 65 6d 65 6e 74 20 69  ether. Element i
0770: 20 63 6f 6e 74 61 69 6e 73 20 74 68 65 20 72 65   contains the re
0780: 73 75 6c 74 20 6f 66 20 0a 2a 2a 20 63 6f 6d 70  sult of .** comp
0790: 61 72 69 6e 67 20 61 49 74 65 72 5b 32 2a 69 2d  aring aIter[2*i-
07a0: 4e 5d 20 61 6e 64 20 61 49 74 65 72 5b 32 2a 69  N] and aIter[2*i
07b0: 2d 4e 2b 31 5d 2e 20 57 68 69 63 68 65 76 65 72  -N+1]. Whichever
07c0: 20 6b 65 79 20 69 73 20 73 6d 61 6c 6c 65 72 2c   key is smaller,
07d0: 20 74 68 65 0a 2a 2a 20 61 54 72 65 65 20 65 6c   the.** aTree el
07e0: 65 6d 65 6e 74 20 69 73 20 73 65 74 20 74 6f 20  ement is set to 
07f0: 74 68 65 20 69 6e 64 65 78 20 6f 66 20 69 74 2e  the index of it.
0800: 20 0a 2a 2a 0a 2a 2a 20 46 6f 72 20 74 68 65 20   .**.** For the 
0810: 70 75 72 70 6f 73 65 73 20 6f 66 20 74 68 69 73  purposes of this
0820: 20 63 6f 6d 70 61 72 69 73 6f 6e 2c 20 45 4f 46   comparison, EOF
0830: 20 69 73 20 63 6f 6e 73 69 64 65 72 65 64 20 67   is considered g
0840: 72 65 61 74 65 72 20 74 68 61 6e 20 61 6e 79 0a  reater than any.
0850: 2a 2a 20 6f 74 68 65 72 20 6b 65 79 20 76 61 6c  ** other key val
0860: 75 65 2e 20 49 66 20 74 68 65 20 6b 65 79 73 20  ue. If the keys 
0870: 61 72 65 20 65 71 75 61 6c 20 28 6f 6e 6c 79 20  are equal (only 
0880: 70 6f 73 73 69 62 6c 65 20 77 69 74 68 20 74 77  possible with tw
0890: 6f 20 45 4f 46 0a 2a 2a 20 76 61 6c 75 65 73 29  o EOF.** values)
08a0: 2c 20 69 74 20 64 6f 65 73 6e 27 74 20 6d 61 74  , it doesn't mat
08b0: 74 65 72 20 77 68 69 63 68 20 69 6e 64 65 78 20  ter which index 
08c0: 69 73 20 73 74 6f 72 65 64 2e 0a 2a 2a 0a 2a 2a  is stored..**.**
08d0: 20 54 68 65 20 28 4e 2f 34 29 20 65 6c 65 6d 65   The (N/4) eleme
08e0: 6e 74 73 20 6f 66 20 61 54 72 65 65 5b 5d 20 74  nts of aTree[] t
08f0: 68 61 74 20 70 72 65 63 65 65 64 20 74 68 65 20  hat preceed the 
0900: 66 69 6e 61 6c 20 28 4e 2f 32 29 20 64 65 73 63  final (N/2) desc
0910: 72 69 62 65 64 20 0a 2a 2a 20 61 62 6f 76 65 20  ribed .** above 
0920: 63 6f 6e 74 61 69 6e 73 20 74 68 65 20 69 6e 64  contains the ind
0930: 65 78 20 6f 66 20 74 68 65 20 73 6d 61 6c 6c 65  ex of the smalle
0940: 73 74 20 6f 66 20 65 61 63 68 20 62 6c 6f 63 6b  st of each block
0950: 20 6f 66 20 34 20 69 74 65 72 61 74 6f 72 73 2e   of 4 iterators.
0960: 0a 2a 2a 20 41 6e 64 20 73 6f 20 6f 6e 2e 20 53  .** And so on. S
0970: 6f 20 74 68 61 74 20 61 54 72 65 65 5b 31 5d 20  o that aTree[1] 
0980: 63 6f 6e 74 61 69 6e 73 20 74 68 65 20 69 6e 64  contains the ind
0990: 65 78 20 6f 66 20 74 68 65 20 69 74 65 72 61 74  ex of the iterat
09a0: 6f 72 20 74 68 61 74 20 0a 2a 2a 20 63 75 72 72  or that .** curr
09b0: 65 6e 74 6c 79 20 70 6f 69 6e 74 73 20 74 6f 20  ently points to 
09c0: 74 68 65 20 73 6d 61 6c 6c 65 73 74 20 6b 65 79  the smallest key
09d0: 20 76 61 6c 75 65 2e 20 61 54 72 65 65 5b 30 5d   value. aTree[0]
09e0: 20 69 73 20 75 6e 75 73 65 64 2e 0a 2a 2a 0a 2a   is unused..**.*
09f0: 2a 20 45 78 61 6d 70 6c 65 3a 0a 2a 2a 0a 2a 2a  * Example:.**.**
0a00: 20 20 20 20 20 61 49 74 65 72 5b 30 5d 20 2d 3e       aIter[0] ->
0a10: 20 42 61 6e 61 6e 61 0a 2a 2a 20 20 20 20 20 61   Banana.**     a
0a20: 49 74 65 72 5b 31 5d 20 2d 3e 20 46 65 69 6a 6f  Iter[1] -> Feijo
0a30: 61 0a 2a 2a 20 20 20 20 20 61 49 74 65 72 5b 32  a.**     aIter[2
0a40: 5d 20 2d 3e 20 45 6c 64 65 72 62 65 72 72 79 0a  ] -> Elderberry.
0a50: 2a 2a 20 20 20 20 20 61 49 74 65 72 5b 33 5d 20  **     aIter[3] 
0a60: 2d 3e 20 43 75 72 72 61 6e 74 0a 2a 2a 20 20 20  -> Currant.**   
0a70: 20 20 61 49 74 65 72 5b 34 5d 20 2d 3e 20 47 72    aIter[4] -> Gr
0a80: 61 70 65 66 72 75 69 74 0a 2a 2a 20 20 20 20 20  apefruit.**     
0a90: 61 49 74 65 72 5b 35 5d 20 2d 3e 20 41 70 70 6c  aIter[5] -> Appl
0aa0: 65 0a 2a 2a 20 20 20 20 20 61 49 74 65 72 5b 36  e.**     aIter[6
0ab0: 5d 20 2d 3e 20 44 75 72 69 61 6e 0a 2a 2a 20 20  ] -> Durian.**  
0ac0: 20 20 20 61 49 74 65 72 5b 37 5d 20 2d 3e 20 45     aIter[7] -> E
0ad0: 4f 46 0a 2a 2a 0a 2a 2a 20 20 20 20 20 61 54 72  OF.**.**     aTr
0ae0: 65 65 5b 5d 20 3d 20 7b 20 58 2c 20 35 20 20 20  ee[] = { X, 5   
0af0: 30 2c 20 35 20 20 20 20 30 2c 20 33 2c 20 35 2c  0, 5    0, 3, 5,
0b00: 20 36 20 7d 0a 2a 2a 0a 2a 2a 20 54 68 65 20 63   6 }.**.** The c
0b10: 75 72 72 65 6e 74 20 65 6c 65 6d 65 6e 74 20 69  urrent element i
0b20: 73 20 22 41 70 70 6c 65 22 20 28 74 68 65 20 76  s "Apple" (the v
0b30: 61 6c 75 65 20 6f 66 20 74 68 65 20 6b 65 79 20  alue of the key 
0b40: 69 6e 64 69 63 61 74 65 64 20 62 79 20 0a 2a 2a  indicated by .**
0b50: 20 69 74 65 72 61 74 6f 72 20 35 29 2e 20 57 68   iterator 5). Wh
0b60: 65 6e 20 74 68 65 20 4e 65 78 74 28 29 20 6f 70  en the Next() op
0b70: 65 72 61 74 69 6f 6e 20 69 73 20 69 6e 76 6f 6b  eration is invok
0b80: 65 64 2c 20 69 74 65 72 61 74 6f 72 20 35 20 77  ed, iterator 5 w
0b90: 69 6c 6c 0a 2a 2a 20 62 65 20 61 64 76 61 6e 63  ill.** be advanc
0ba0: 65 64 20 74 6f 20 74 68 65 20 6e 65 78 74 20 6b  ed to the next k
0bb0: 65 79 20 69 6e 20 69 74 73 20 73 65 67 6d 65 6e  ey in its segmen
0bc0: 74 2e 20 53 61 79 20 74 68 65 20 6e 65 78 74 20  t. Say the next 
0bd0: 6b 65 79 20 69 73 0a 2a 2a 20 22 45 67 67 70 6c  key is.** "Eggpl
0be0: 61 6e 74 22 3a 0a 2a 2a 0a 2a 2a 20 20 20 20 20  ant":.**.**     
0bf0: 61 49 74 65 72 5b 35 5d 20 2d 3e 20 45 67 67 70  aIter[5] -> Eggp
0c00: 6c 61 6e 74 0a 2a 2a 0a 2a 2a 20 54 68 65 20 63  lant.**.** The c
0c10: 6f 6e 74 65 6e 74 73 20 6f 66 20 61 54 72 65 65  ontents of aTree
0c20: 5b 5d 20 61 72 65 20 75 70 64 61 74 65 64 20 66  [] are updated f
0c30: 69 72 73 74 20 62 79 20 63 6f 6d 70 61 72 69 6e  irst by comparin
0c40: 67 20 74 68 65 20 6e 65 77 20 69 74 65 72 61 74  g the new iterat
0c50: 6f 72 0a 2a 2a 20 35 20 6b 65 79 20 74 6f 20 74  or.** 5 key to t
0c60: 68 65 20 63 75 72 72 65 6e 74 20 6b 65 79 20 6f  he current key o
0c70: 66 20 69 74 65 72 61 74 6f 72 20 34 20 28 73 74  f iterator 4 (st
0c80: 69 6c 6c 20 22 47 72 61 70 65 66 72 75 69 74 22  ill "Grapefruit"
0c90: 29 2e 20 54 68 65 20 69 74 65 72 61 74 6f 72 0a  ). The iterator.
0ca0: 2a 2a 20 35 20 76 61 6c 75 65 20 69 73 20 73 74  ** 5 value is st
0cb0: 69 6c 6c 20 73 6d 61 6c 6c 65 72 2c 20 73 6f 20  ill smaller, so 
0cc0: 61 54 72 65 65 5b 36 5d 20 69 73 20 73 65 74 20  aTree[6] is set 
0cd0: 74 6f 20 35 2e 20 41 6e 64 20 73 6f 20 6f 6e 20  to 5. And so on 
0ce0: 75 70 20 74 68 65 20 74 72 65 65 2e 0a 2a 2a 20  up the tree..** 
0cf0: 54 68 65 20 76 61 6c 75 65 20 6f 66 20 69 74 65  The value of ite
0d00: 72 61 74 6f 72 20 36 20 2d 20 22 44 75 72 69 61  rator 6 - "Duria
0d10: 6e 22 20 2d 20 69 73 20 6e 6f 77 20 73 6d 61 6c  n" - is now smal
0d20: 6c 65 72 20 74 68 61 6e 20 74 68 61 74 20 6f 66  ler than that of
0d30: 20 69 74 65 72 61 74 6f 72 0a 2a 2a 20 35 2c 20   iterator.** 5, 
0d40: 73 6f 20 61 54 72 65 65 5b 33 5d 20 69 73 20 73  so aTree[3] is s
0d50: 65 74 20 74 6f 20 36 2e 20 4b 65 79 20 30 20 69  et to 6. Key 0 i
0d60: 73 20 73 6d 61 6c 6c 65 72 20 74 68 61 6e 20 6b  s smaller than k
0d70: 65 79 20 36 20 28 42 61 6e 61 6e 61 3c 44 75 72  ey 6 (Banana<Dur
0d80: 69 61 6e 29 2c 0a 2a 2a 20 73 6f 20 74 68 65 20  ian),.** so the 
0d90: 76 61 6c 75 65 20 77 72 69 74 74 65 6e 20 69 6e  value written in
0da0: 74 6f 20 65 6c 65 6d 65 6e 74 20 31 20 6f 66 20  to element 1 of 
0db0: 74 68 65 20 61 72 72 61 79 20 69 73 20 30 2e 20  the array is 0. 
0dc0: 41 73 20 66 6f 6c 6c 6f 77 73 3a 0a 2a 2a 0a 2a  As follows:.**.*
0dd0: 2a 20 20 20 20 20 61 54 72 65 65 5b 5d 20 3d 20  *     aTree[] = 
0de0: 7b 20 58 2c 20 30 20 20 20 30 2c 20 36 20 20 20  { X, 0   0, 6   
0df0: 20 30 2c 20 33 2c 20 35 2c 20 36 20 7d 0a 2a 2a   0, 3, 5, 6 }.**
0e00: 0a 2a 2a 20 49 6e 20 6f 74 68 65 72 20 77 6f 72  .** In other wor
0e10: 64 73 2c 20 65 61 63 68 20 74 69 6d 65 20 77 65  ds, each time we
0e20: 20 61 64 76 61 6e 63 65 20 74 6f 20 74 68 65 20   advance to the 
0e30: 6e 65 78 74 20 73 6f 72 74 65 72 20 65 6c 65 6d  next sorter elem
0e40: 65 6e 74 2c 20 6c 6f 67 32 28 4e 29 0a 2a 2a 20  ent, log2(N).** 
0e50: 6b 65 79 20 63 6f 6d 70 61 72 69 73 6f 6e 20 6f  key comparison o
0e60: 70 65 72 61 74 69 6f 6e 73 20 61 72 65 20 72 65  perations are re
0e70: 71 75 69 72 65 64 2c 20 77 68 65 72 65 20 4e 20  quired, where N 
0e80: 69 73 20 74 68 65 20 6e 75 6d 62 65 72 20 6f 66  is the number of
0e90: 20 73 65 67 6d 65 6e 74 73 0a 2a 2a 20 62 65 69   segments.** bei
0ea0: 6e 67 20 6d 65 72 67 65 64 20 28 72 6f 75 6e 64  ng merged (round
0eb0: 65 64 20 75 70 20 74 6f 20 74 68 65 20 6e 65 78  ed up to the nex
0ec0: 74 20 70 6f 77 65 72 20 6f 66 20 32 29 2e 0a 2a  t power of 2)..*
0ed0: 2f 0a 73 74 72 75 63 74 20 56 64 62 65 53 6f 72  /.struct VdbeSor
0ee0: 74 65 72 20 7b 0a 20 20 69 6e 74 20 6e 57 6f 72  ter {.  int nWor
0ef0: 6b 69 6e 67 3b 20 20 20 20 20 20 20 20 20 20 20  king;           
0f00: 20 20 20 20 20 20 20 20 2f 2a 20 53 74 61 72 74          /* Start
0f10: 20 61 20 6e 65 77 20 62 2d 74 72 65 65 20 61 66   a new b-tree af
0f20: 74 65 72 20 74 68 69 73 20 6d 61 6e 79 20 70 61  ter this many pa
0f30: 67 65 73 20 2a 2f 0a 20 20 69 6e 74 20 6e 42 74  ges */.  int nBt
0f40: 72 65 65 3b 20 20 20 20 20 20 20 20 20 20 20 20  ree;            
0f50: 20 20 20 20 20 20 20 20 20 2f 2a 20 43 75 72 72           /* Curr
0f60: 65 6e 74 20 73 69 7a 65 20 6f 66 20 62 2d 74 72  ent size of b-tr
0f70: 65 65 20 63 6f 6e 74 65 6e 74 73 20 61 73 20 50  ee contents as P
0f80: 4d 41 20 2a 2f 0a 20 20 69 6e 74 20 6e 54 72 65  MA */.  int nTre
0f90: 65 3b 20 20 20 20 20 20 20 20 20 20 20 20 20 20  e;              
0fa0: 20 20 20 20 20 20 20 20 2f 2a 20 55 73 65 64 20          /* Used 
0fb0: 73 69 7a 65 20 6f 66 20 61 54 72 65 65 2f 61 49  size of aTree/aI
0fc0: 74 65 72 20 28 70 6f 77 65 72 20 6f 66 20 32 29  ter (power of 2)
0fd0: 20 2a 2f 0a 20 20 56 64 62 65 53 6f 72 74 65 72   */.  VdbeSorter
0fe0: 49 74 65 72 20 2a 61 49 74 65 72 3b 20 20 20 20  Iter *aIter;    
0ff0: 20 20 20 20 20 20 2f 2a 20 41 72 72 61 79 20 6f        /* Array o
1000: 66 20 69 74 65 72 61 74 6f 72 73 20 74 6f 20 6d  f iterators to m
1010: 65 72 67 65 20 2a 2f 0a 20 20 69 6e 74 20 2a 61  erge */.  int *a
1020: 54 72 65 65 3b 20 20 20 20 20 20 20 20 20 20 20  Tree;           
1030: 20 20 20 20 20 20 20 20 20 20 2f 2a 20 43 75 72            /* Cur
1040: 72 65 6e 74 20 73 74 61 74 65 20 6f 66 20 69 6e  rent state of in
1050: 63 72 65 6d 65 6e 74 61 6c 20 6d 65 72 67 65 20  cremental merge 
1060: 2a 2f 0a 20 20 69 36 34 20 69 57 72 69 74 65 4f  */.  i64 iWriteO
1070: 66 66 3b 20 20 20 20 20 20 20 20 20 20 20 20 20  ff;             
1080: 20 20 20 20 20 2f 2a 20 43 75 72 72 65 6e 74 20       /* Current 
1090: 77 72 69 74 65 20 6f 66 66 73 65 74 20 77 69 74  write offset wit
10a0: 68 69 6e 20 66 69 6c 65 20 70 54 65 6d 70 31 20  hin file pTemp1 
10b0: 2a 2f 0a 20 20 69 36 34 20 69 52 65 61 64 4f 66  */.  i64 iReadOf
10c0: 66 3b 20 20 20 20 20 20 20 20 20 20 20 20 20 20  f;              
10d0: 20 20 20 20 20 2f 2a 20 43 75 72 72 65 6e 74 20       /* Current 
10e0: 72 65 61 64 20 6f 66 66 73 65 74 20 77 69 74 68  read offset with
10f0: 69 6e 20 66 69 6c 65 20 70 54 65 6d 70 31 20 2a  in file pTemp1 *
1100: 2f 0a 20 20 73 71 6c 69 74 65 33 5f 66 69 6c 65  /.  sqlite3_file
1110: 20 2a 70 54 65 6d 70 31 3b 20 20 20 20 20 20 20   *pTemp1;       
1120: 20 20 20 20 2f 2a 20 50 4d 41 20 66 69 6c 65 20      /* PMA file 
1130: 31 20 2a 2f 0a 20 20 69 6e 74 20 6e 50 4d 41 3b  1 */.  int nPMA;
1140: 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20                  
1150: 20 20 20 20 20 20 20 2f 2a 20 4e 75 6d 62 65 72         /* Number
1160: 20 6f 66 20 50 4d 41 73 20 73 74 6f 72 65 64 20   of PMAs stored 
1170: 69 6e 20 70 54 65 6d 70 31 20 2a 2f 0a 7d 3b 0a  in pTemp1 */.};.
1180: 0a 2f 2a 0a 2a 2a 20 54 68 65 20 66 6f 6c 6c 6f  ./*.** The follo
1190: 77 69 6e 67 20 74 79 70 65 20 69 73 20 61 6e 20  wing type is an 
11a0: 69 74 65 72 61 74 6f 72 20 66 6f 72 20 61 20 50  iterator for a P
11b0: 4d 41 2e 20 49 74 20 63 61 63 68 65 73 20 74 68  MA. It caches th
11c0: 65 20 63 75 72 72 65 6e 74 20 6b 65 79 20 69 6e  e current key in
11d0: 20 0a 2a 2a 20 76 61 72 69 61 62 6c 65 73 20 6e   .** variables n
11e0: 4b 65 79 2f 61 4b 65 79 2e 20 49 66 20 74 68 65  Key/aKey. If the
11f0: 20 69 74 65 72 61 74 6f 72 20 69 73 20 61 74 20   iterator is at 
1200: 45 4f 46 2c 20 70 46 69 6c 65 3d 3d 30 2e 0a 2a  EOF, pFile==0..*
1210: 2f 0a 73 74 72 75 63 74 20 56 64 62 65 53 6f 72  /.struct VdbeSor
1220: 74 65 72 49 74 65 72 20 7b 0a 20 20 69 36 34 20  terIter {.  i64 
1230: 69 52 65 61 64 4f 66 66 3b 20 20 20 20 20 20 20  iReadOff;       
1240: 20 20 20 20 20 20 20 20 20 20 20 20 2f 2a 20 43              /* C
1250: 75 72 72 65 6e 74 20 72 65 61 64 20 6f 66 66 73  urrent read offs
1260: 65 74 20 2a 2f 0a 20 20 69 36 34 20 69 45 6f 66  et */.  i64 iEof
1270: 3b 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20  ;               
1280: 20 20 20 20 20 20 20 20 2f 2a 20 31 20 62 79 74          /* 1 byt
1290: 65 20 70 61 73 74 20 45 4f 46 20 66 6f 72 20 74  e past EOF for t
12a0: 68 69 73 20 69 74 65 72 61 74 6f 72 20 2a 2f 0a  his iterator */.
12b0: 20 20 73 71 6c 69 74 65 33 5f 66 69 6c 65 20 2a    sqlite3_file *
12c0: 70 46 69 6c 65 3b 20 20 20 20 20 20 20 20 20 20  pFile;          
12d0: 20 20 2f 2a 20 46 69 6c 65 20 69 74 65 72 61 74    /* File iterat
12e0: 6f 72 20 69 73 20 72 65 61 64 69 6e 67 20 66 72  or is reading fr
12f0: 6f 6d 20 2a 2f 0a 20 20 69 6e 74 20 6e 41 6c 6c  om */.  int nAll
1300: 6f 63 3b 20 20 20 20 20 20 20 20 20 20 20 20 20  oc;             
1310: 20 20 20 20 20 20 20 20 2f 2a 20 42 79 74 65 73          /* Bytes
1320: 20 6f 66 20 73 70 61 63 65 20 61 74 20 61 41 6c   of space at aAl
1330: 6c 6f 63 20 2a 2f 0a 20 20 75 38 20 2a 61 41 6c  loc */.  u8 *aAl
1340: 6c 6f 63 3b 20 20 20 20 20 20 20 20 20 20 20 20  loc;            
1350: 20 20 20 20 20 20 20 20 20 2f 2a 20 41 6c 6c 6f           /* Allo
1360: 63 61 74 65 64 20 73 70 61 63 65 20 2a 2f 0a 20  cated space */. 
1370: 20 69 6e 74 20 6e 4b 65 79 3b 20 20 20 20 20 20   int nKey;      
1380: 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20                  
1390: 20 2f 2a 20 4e 75 6d 62 65 72 20 6f 66 20 62 79   /* Number of by
13a0: 74 65 73 20 69 6e 20 6b 65 79 20 2a 2f 0a 20 20  tes in key */.  
13b0: 75 38 20 2a 61 4b 65 79 3b 20 20 20 20 20 20 20  u8 *aKey;       
13c0: 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20                  
13d0: 2f 2a 20 50 6f 69 6e 74 65 72 20 74 6f 20 63 75  /* Pointer to cu
13e0: 72 72 65 6e 74 20 6b 65 79 20 2a 2f 0a 7d 3b 0a  rrent key */.};.
13f0: 0a 2f 2a 20 4d 69 6e 69 6d 75 6d 20 61 6c 6c 6f  ./* Minimum allo
1400: 77 61 62 6c 65 20 76 61 6c 75 65 20 66 6f 72 20  wable value for 
1410: 74 68 65 20 56 64 62 65 53 6f 72 74 65 72 2e 6e  the VdbeSorter.n
1420: 57 6f 72 6b 69 6e 67 20 76 61 72 69 61 62 6c 65  Working variable
1430: 20 2a 2f 0a 23 64 65 66 69 6e 65 20 53 4f 52 54   */.#define SORT
1440: 45 52 5f 4d 49 4e 5f 53 45 47 4d 45 4e 54 5f 53  ER_MIN_SEGMENT_S
1450: 49 5a 45 20 31 30 0a 0a 2f 2a 20 4d 61 78 69 6d  IZE 10../* Maxim
1460: 75 6d 20 6e 75 6d 62 65 72 20 6f 66 20 73 65 67  um number of seg
1470: 6d 65 6e 74 73 20 74 6f 20 6d 65 72 67 65 20 69  ments to merge i
1480: 6e 20 61 20 73 69 6e 67 6c 65 20 70 61 73 73 2e  n a single pass.
1490: 20 2a 2f 0a 23 64 65 66 69 6e 65 20 53 4f 52 54   */.#define SORT
14a0: 45 52 5f 4d 41 58 5f 4d 45 52 47 45 5f 43 4f 55  ER_MAX_MERGE_COU
14b0: 4e 54 20 31 36 0a 0a 2f 2a 0a 2a 2a 20 46 72 65  NT 16../*.** Fre
14c0: 65 20 61 6c 6c 20 6d 65 6d 6f 72 79 20 62 65 6c  e all memory bel
14d0: 6f 6e 67 69 6e 67 20 74 6f 20 74 68 65 20 56 64  onging to the Vd
14e0: 62 65 53 6f 72 74 65 72 49 74 65 72 20 6f 62 6a  beSorterIter obj
14f0: 65 63 74 20 70 61 73 73 65 64 20 61 73 20 74 68  ect passed as th
1500: 65 20 73 65 63 6f 6e 64 0a 2a 2a 20 61 72 67 75  e second.** argu
1510: 6d 65 6e 74 2e 20 41 6c 6c 20 73 74 72 75 63 74  ment. All struct
1520: 75 72 65 20 66 69 65 6c 64 73 20 61 72 65 20 73  ure fields are s
1530: 65 74 20 74 6f 20 7a 65 72 6f 20 62 65 66 6f 72  et to zero befor
1540: 65 20 72 65 74 75 72 6e 69 6e 67 2e 0a 2a 2f 0a  e returning..*/.
1550: 73 74 61 74 69 63 20 76 6f 69 64 20 76 64 62 65  static void vdbe
1560: 53 6f 72 74 65 72 49 74 65 72 5a 65 72 6f 28 73  SorterIterZero(s
1570: 71 6c 69 74 65 33 20 2a 64 62 2c 20 56 64 62 65  qlite3 *db, Vdbe
1580: 53 6f 72 74 65 72 49 74 65 72 20 2a 70 49 74 65  SorterIter *pIte
1590: 72 29 7b 0a 20 20 73 71 6c 69 74 65 33 44 62 46  r){.  sqlite3DbF
15a0: 72 65 65 28 64 62 2c 20 70 49 74 65 72 2d 3e 61  ree(db, pIter->a
15b0: 41 6c 6c 6f 63 29 3b 0a 20 20 6d 65 6d 73 65 74  Alloc);.  memset
15c0: 28 70 49 74 65 72 2c 20 30 2c 20 73 69 7a 65 6f  (pIter, 0, sizeo
15d0: 66 28 56 64 62 65 53 6f 72 74 65 72 49 74 65 72  f(VdbeSorterIter
15e0: 29 29 3b 0a 7d 0a 0a 2f 2a 0a 2a 2a 20 41 64 76  ));.}../*.** Adv
15f0: 61 6e 63 65 20 69 74 65 72 61 74 6f 72 20 70 49  ance iterator pI
1600: 74 65 72 20 74 6f 20 74 68 65 20 6e 65 78 74 20  ter to the next 
1610: 6b 65 79 20 69 6e 20 69 74 73 20 50 4d 41 2e 0a  key in its PMA..
1620: 2a 2f 0a 73 74 61 74 69 63 20 69 6e 74 20 76 64  */.static int vd
1630: 62 65 53 6f 72 74 65 72 49 74 65 72 4e 65 78 74  beSorterIterNext
1640: 28 0a 20 20 73 71 6c 69 74 65 33 20 2a 64 62 2c  (.  sqlite3 *db,
1650: 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20                  
1660: 20 20 20 20 2f 2a 20 44 61 74 61 62 61 73 65 20      /* Database 
1670: 68 61 6e 64 6c 65 20 28 66 6f 72 20 73 71 6c 69  handle (for sqli
1680: 74 65 33 44 62 4d 61 6c 6c 6f 63 28 29 20 29 20  te3DbMalloc() ) 
1690: 2a 2f 0a 20 20 56 64 62 65 53 6f 72 74 65 72 49  */.  VdbeSorterI
16a0: 74 65 72 20 2a 70 49 74 65 72 20 20 20 20 20 20  ter *pIter      
16b0: 20 20 20 20 20 2f 2a 20 49 74 65 72 61 74 6f 72       /* Iterator
16c0: 20 74 6f 20 61 64 76 61 6e 63 65 20 2a 2f 0a 29   to advance */.)
16d0: 7b 0a 20 20 69 6e 74 20 72 63 3b 0a 20 20 69 6e  {.  int rc;.  in
16e0: 74 20 6e 52 65 61 64 3b 0a 20 20 69 6e 74 20 6e  t nRead;.  int n
16f0: 52 65 63 3b 0a 20 20 69 6e 74 20 69 4f 66 66 3b  Rec;.  int iOff;
1700: 0a 0a 20 20 6e 52 65 61 64 20 3d 20 70 49 74 65  ..  nRead = pIte
1710: 72 2d 3e 69 45 6f 66 20 2d 20 70 49 74 65 72 2d  r->iEof - pIter-
1720: 3e 69 52 65 61 64 4f 66 66 3b 0a 20 20 69 66 28  >iReadOff;.  if(
1730: 20 6e 52 65 61 64 3e 35 20 29 20 6e 52 65 61 64   nRead>5 ) nRead
1740: 20 3d 20 35 3b 0a 20 20 69 66 28 20 6e 52 65 61   = 5;.  if( nRea
1750: 64 3c 3d 30 20 29 7b 0a 20 20 20 20 76 64 62 65  d<=0 ){.    vdbe
1760: 53 6f 72 74 65 72 49 74 65 72 5a 65 72 6f 28 64  SorterIterZero(d
1770: 62 2c 20 70 49 74 65 72 29 3b 0a 20 20 20 20 72  b, pIter);.    r
1780: 65 74 75 72 6e 20 53 51 4c 49 54 45 5f 4f 4b 3b  eturn SQLITE_OK;
1790: 0a 20 20 7d 0a 0a 20 20 72 63 20 3d 20 73 71 6c  .  }..  rc = sql
17a0: 69 74 65 33 4f 73 52 65 61 64 28 70 49 74 65 72  ite3OsRead(pIter
17b0: 2d 3e 70 46 69 6c 65 2c 20 70 49 74 65 72 2d 3e  ->pFile, pIter->
17c0: 61 41 6c 6c 6f 63 2c 20 6e 52 65 61 64 2c 20 70  aAlloc, nRead, p
17d0: 49 74 65 72 2d 3e 69 52 65 61 64 4f 66 66 29 3b  Iter->iReadOff);
17e0: 0a 20 20 69 4f 66 66 20 3d 20 67 65 74 56 61 72  .  iOff = getVar
17f0: 69 6e 74 33 32 28 70 49 74 65 72 2d 3e 61 41 6c  int32(pIter->aAl
1800: 6c 6f 63 2c 20 6e 52 65 63 29 3b 0a 0a 20 20 69  loc, nRec);..  i
1810: 66 28 20 72 63 3d 3d 53 51 4c 49 54 45 5f 4f 4b  f( rc==SQLITE_OK
1820: 20 26 26 20 28 69 4f 66 66 2b 6e 52 65 63 29 3e   && (iOff+nRec)>
1830: 6e 52 65 61 64 20 29 7b 0a 20 20 20 20 69 6e 74  nRead ){.    int
1840: 20 6e 52 65 61 64 32 3b 0a 20 20 20 20 69 66 28   nRead2;.    if(
1850: 20 28 69 4f 66 66 2b 6e 52 65 63 29 3e 70 49 74   (iOff+nRec)>pIt
1860: 65 72 2d 3e 6e 41 6c 6c 6f 63 20 29 7b 0a 20 20  er->nAlloc ){.  
1870: 20 20 20 20 69 6e 74 20 6e 4e 65 77 20 3d 20 70      int nNew = p
1880: 49 74 65 72 2d 3e 6e 41 6c 6c 6f 63 2a 32 3b 0a  Iter->nAlloc*2;.
1890: 20 20 20 20 20 20 77 68 69 6c 65 28 20 28 69 4f        while( (iO
18a0: 66 66 2b 6e 52 65 63 29 3e 6e 4e 65 77 20 29 20  ff+nRec)>nNew ) 
18b0: 6e 4e 65 77 20 3d 20 6e 4e 65 77 2a 32 3b 0a 20  nNew = nNew*2;. 
18c0: 20 20 20 20 20 70 49 74 65 72 2d 3e 61 41 6c 6c       pIter->aAll
18d0: 6f 63 20 3d 20 73 71 6c 69 74 65 33 44 62 52 65  oc = sqlite3DbRe
18e0: 61 6c 6c 6f 63 4f 72 46 72 65 65 28 64 62 2c 20  allocOrFree(db, 
18f0: 70 49 74 65 72 2d 3e 61 41 6c 6c 6f 63 2c 20 6e  pIter->aAlloc, n
1900: 4e 65 77 29 3b 0a 20 20 20 20 20 20 69 66 28 20  New);.      if( 
1910: 21 70 49 74 65 72 2d 3e 61 41 6c 6c 6f 63 20 29  !pIter->aAlloc )
1920: 20 72 65 74 75 72 6e 20 53 51 4c 49 54 45 5f 4e   return SQLITE_N
1930: 4f 4d 45 4d 3b 0a 20 20 20 20 20 20 70 49 74 65  OMEM;.      pIte
1940: 72 2d 3e 6e 41 6c 6c 6f 63 20 3d 20 6e 4e 65 77  r->nAlloc = nNew
1950: 3b 0a 20 20 20 20 7d 0a 0a 20 20 20 20 6e 52 65  ;.    }..    nRe
1960: 61 64 32 20 3d 20 69 4f 66 66 20 2b 20 6e 52 65  ad2 = iOff + nRe
1970: 63 20 2d 20 6e 52 65 61 64 3b 0a 20 20 20 20 72  c - nRead;.    r
1980: 63 20 3d 20 73 71 6c 69 74 65 33 4f 73 52 65 61  c = sqlite3OsRea
1990: 64 28 0a 20 20 20 20 20 20 20 20 70 49 74 65 72  d(.        pIter
19a0: 2d 3e 70 46 69 6c 65 2c 20 26 70 49 74 65 72 2d  ->pFile, &pIter-
19b0: 3e 61 41 6c 6c 6f 63 5b 6e 52 65 61 64 5d 2c 20  >aAlloc[nRead], 
19c0: 6e 52 65 61 64 32 2c 20 70 49 74 65 72 2d 3e 69  nRead2, pIter->i
19d0: 52 65 61 64 4f 66 66 2b 6e 52 65 61 64 0a 20 20  ReadOff+nRead.  
19e0: 20 20 29 3b 0a 20 20 7d 0a 0a 20 20 61 73 73 65    );.  }..  asse
19f0: 72 74 28 20 6e 52 65 63 3e 30 20 7c 7c 20 72 63  rt( nRec>0 || rc
1a00: 21 3d 53 51 4c 49 54 45 5f 4f 4b 20 29 3b 0a 0a  !=SQLITE_OK );..
1a10: 20 20 70 49 74 65 72 2d 3e 69 52 65 61 64 4f 66    pIter->iReadOf
1a20: 66 20 2b 3d 20 69 4f 66 66 2b 6e 52 65 63 3b 0a  f += iOff+nRec;.
1a30: 20 20 70 49 74 65 72 2d 3e 6e 4b 65 79 20 3d 20    pIter->nKey = 
1a40: 6e 52 65 63 3b 0a 20 20 70 49 74 65 72 2d 3e 61  nRec;.  pIter->a
1a50: 4b 65 79 20 3d 20 26 70 49 74 65 72 2d 3e 61 41  Key = &pIter->aA
1a60: 6c 6c 6f 63 5b 69 4f 66 66 5d 3b 0a 20 20 72 65  lloc[iOff];.  re
1a70: 74 75 72 6e 20 72 63 3b 0a 7d 0a 0a 73 74 61 74  turn rc;.}..stat
1a80: 69 63 20 69 6e 74 20 76 64 62 65 53 6f 72 74 65  ic int vdbeSorte
1a90: 72 57 72 69 74 65 56 61 72 69 6e 74 28 0a 20 20  rWriteVarint(.  
1aa0: 73 71 6c 69 74 65 33 5f 66 69 6c 65 20 2a 70 46  sqlite3_file *pF
1ab0: 69 6c 65 2c 20 0a 20 20 69 36 34 20 69 56 61 6c  ile, .  i64 iVal
1ac0: 2c 20 0a 20 20 69 36 34 20 2a 70 69 4f 66 66 73  , .  i64 *piOffs
1ad0: 65 74 0a 29 7b 0a 20 20 75 38 20 61 56 61 72 69  et.){.  u8 aVari
1ae0: 6e 74 5b 39 5d 3b 20 20 20 20 20 20 20 20 20 20  nt[9];          
1af0: 20 20 20 20 20 20 20 20 2f 2a 20 42 75 66 66 65          /* Buffe
1b00: 72 20 6c 61 72 67 65 20 65 6e 6f 75 67 68 20 66  r large enough f
1b10: 6f 72 20 61 20 76 61 72 69 6e 74 20 2a 2f 0a 20  or a varint */. 
1b20: 20 69 6e 74 20 6e 56 61 72 69 6e 74 3b 20 20 20   int nVarint;   
1b30: 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20                  
1b40: 20 2f 2a 20 4e 75 6d 62 65 72 20 6f 66 20 75 73   /* Number of us
1b50: 65 64 20 62 79 74 65 73 20 69 6e 20 76 61 72 69  ed bytes in vari
1b60: 6e 74 20 2a 2f 0a 20 20 69 6e 74 20 72 63 3b 20  nt */.  int rc; 
1b70: 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20                  
1b80: 20 20 20 20 20 20 20 20 2f 2a 20 52 65 73 75 6c          /* Resul
1b90: 74 20 6f 66 20 77 72 69 74 65 28 29 20 63 61 6c  t of write() cal
1ba0: 6c 20 2a 2f 0a 0a 20 20 6e 56 61 72 69 6e 74 20  l */..  nVarint 
1bb0: 3d 20 73 71 6c 69 74 65 33 50 75 74 56 61 72 69  = sqlite3PutVari
1bc0: 6e 74 28 61 56 61 72 69 6e 74 2c 20 69 56 61 6c  nt(aVarint, iVal
1bd0: 29 3b 0a 20 20 72 63 20 3d 20 73 71 6c 69 74 65  );.  rc = sqlite
1be0: 33 4f 73 57 72 69 74 65 28 70 46 69 6c 65 2c 20  3OsWrite(pFile, 
1bf0: 61 56 61 72 69 6e 74 2c 20 6e 56 61 72 69 6e 74  aVarint, nVarint
1c00: 2c 20 2a 70 69 4f 66 66 73 65 74 29 3b 0a 20 20  , *piOffset);.  
1c10: 2a 70 69 4f 66 66 73 65 74 20 2b 3d 20 6e 56 61  *piOffset += nVa
1c20: 72 69 6e 74 3b 0a 0a 20 20 72 65 74 75 72 6e 20  rint;..  return 
1c30: 72 63 3b 0a 7d 0a 0a 73 74 61 74 69 63 20 69 6e  rc;.}..static in
1c40: 74 20 76 64 62 65 53 6f 72 74 65 72 52 65 61 64  t vdbeSorterRead
1c50: 56 61 72 69 6e 74 28 0a 20 20 73 71 6c 69 74 65  Varint(.  sqlite
1c60: 33 5f 66 69 6c 65 20 2a 70 46 69 6c 65 2c 20 0a  3_file *pFile, .
1c70: 20 20 69 36 34 20 69 45 6f 66 2c 20 20 20 20 20    i64 iEof,     
1c80: 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20                  
1c90: 20 20 2f 2a 20 54 6f 74 61 6c 20 6e 75 6d 62 65    /* Total numbe
1ca0: 72 20 6f 66 20 62 79 74 65 73 20 69 6e 20 66 69  r of bytes in fi
1cb0: 6c 65 20 2a 2f 0a 20 20 69 36 34 20 2a 70 69 4f  le */.  i64 *piO
1cc0: 66 66 73 65 74 2c 20 20 20 20 20 20 20 20 20 20  ffset,          
1cd0: 20 20 20 20 20 20 20 20 2f 2a 20 49 4e 2f 4f 55          /* IN/OU
1ce0: 54 3a 20 52 65 61 64 20 6f 66 66 73 65 74 20 2a  T: Read offset *
1cf0: 2f 0a 20 20 69 36 34 20 2a 70 69 56 61 6c 20 20  /.  i64 *piVal  
1d00: 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20                  
1d10: 20 20 20 20 2f 2a 20 4f 55 54 3a 20 56 61 6c 75      /* OUT: Valu
1d20: 65 20 72 65 61 64 20 66 72 6f 6d 20 66 69 6c 65  e read from file
1d30: 20 2a 2f 0a 29 7b 0a 20 20 75 38 20 61 56 61 72   */.){.  u8 aVar
1d40: 69 6e 74 5b 39 5d 3b 20 20 20 20 20 20 20 20 20  int[9];         
1d50: 20 20 20 20 20 20 20 20 20 2f 2a 20 42 75 66 66           /* Buff
1d60: 65 72 20 6c 61 72 67 65 20 65 6e 6f 75 67 68 20  er large enough 
1d70: 66 6f 72 20 61 20 76 61 72 69 6e 74 20 2a 2f 0a  for a varint */.
1d80: 20 20 69 36 34 20 69 4f 66 66 20 3d 20 2a 70 69    i64 iOff = *pi
1d90: 4f 66 66 73 65 74 3b 20 20 20 20 20 20 20 20 20  Offset;         
1da0: 20 20 2f 2a 20 4f 66 66 73 65 74 20 69 6e 20 66    /* Offset in f
1db0: 69 6c 65 20 74 6f 20 72 65 61 64 20 66 72 6f 6d  ile to read from
1dc0: 20 2a 2f 0a 20 20 69 6e 74 20 6e 52 65 61 64 20   */.  int nRead 
1dd0: 3d 20 39 3b 20 20 20 20 20 20 20 20 20 20 20 20  = 9;            
1de0: 20 20 20 20 20 20 2f 2a 20 4e 75 6d 62 65 72 20        /* Number 
1df0: 6f 66 20 62 79 74 65 73 20 74 6f 20 72 65 61 64  of bytes to read
1e00: 20 66 72 6f 6d 20 66 69 6c 65 20 2a 2f 0a 20 20   from file */.  
1e10: 69 6e 74 20 72 63 3b 20 20 20 20 20 20 20 20 20  int rc;         
1e20: 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20                  
1e30: 2f 2a 20 52 65 74 75 72 6e 20 63 6f 64 65 20 2a  /* Return code *
1e40: 2f 0a 0a 20 20 61 73 73 65 72 74 28 20 69 45 6f  /..  assert( iEo
1e50: 66 3e 69 4f 66 66 20 29 3b 0a 20 20 69 66 28 20  f>iOff );.  if( 
1e60: 28 69 45 6f 66 2d 69 4f 66 66 29 3c 6e 52 65 61  (iEof-iOff)<nRea
1e70: 64 20 29 7b 0a 20 20 20 20 6e 52 65 61 64 20 3d  d ){.    nRead =
1e80: 20 69 45 6f 66 2d 69 4f 66 66 3b 0a 20 20 7d 0a   iEof-iOff;.  }.
1e90: 0a 20 20 72 63 20 3d 20 73 71 6c 69 74 65 33 4f  .  rc = sqlite3O
1ea0: 73 52 65 61 64 28 70 46 69 6c 65 2c 20 61 56 61  sRead(pFile, aVa
1eb0: 72 69 6e 74 2c 20 6e 52 65 61 64 2c 20 69 4f 66  rint, nRead, iOf
1ec0: 66 29 3b 0a 20 20 69 66 28 20 72 63 3d 3d 53 51  f);.  if( rc==SQ
1ed0: 4c 49 54 45 5f 4f 4b 20 29 7b 0a 20 20 20 20 2a  LITE_OK ){.    *
1ee0: 70 69 4f 66 66 73 65 74 20 2b 3d 20 67 65 74 56  piOffset += getV
1ef0: 61 72 69 6e 74 28 61 56 61 72 69 6e 74 2c 20 28  arint(aVarint, (
1f00: 75 36 34 20 2a 29 70 69 56 61 6c 29 3b 0a 20 20  u64 *)piVal);.  
1f10: 7d 0a 0a 20 20 72 65 74 75 72 6e 20 72 63 3b 0a  }..  return rc;.
1f20: 7d 0a 0a 2f 2a 0a 2a 2a 20 49 6e 69 74 69 61 6c  }../*.** Initial
1f30: 69 7a 65 20 69 74 65 72 61 74 6f 72 20 70 49 74  ize iterator pIt
1f40: 65 72 20 74 6f 20 73 63 61 6e 20 74 68 72 6f 75  er to scan throu
1f50: 67 68 20 74 68 65 20 50 4d 41 20 73 74 6f 72 65  gh the PMA store
1f60: 64 20 69 6e 20 66 69 6c 65 20 70 46 69 6c 65 0a  d in file pFile.
1f70: 2a 2a 20 73 74 61 72 74 69 6e 67 20 61 74 20 6f  ** starting at o
1f80: 66 66 73 65 74 20 69 53 74 61 72 74 20 61 6e 64  ffset iStart and
1f90: 20 65 6e 64 69 6e 67 20 61 74 20 6f 66 66 73 65   ending at offse
1fa0: 74 20 69 45 6f 66 2d 31 2e 20 54 68 69 73 20 66  t iEof-1. This f
1fb0: 75 6e 63 74 69 6f 6e 20 0a 2a 2a 20 6c 65 61 76  unction .** leav
1fc0: 65 73 20 74 68 65 20 69 74 65 72 61 74 6f 72 20  es the iterator 
1fd0: 70 6f 69 6e 74 69 6e 67 20 74 6f 20 74 68 65 20  pointing to the 
1fe0: 66 69 72 73 74 20 6b 65 79 20 69 6e 20 74 68 65  first key in the
1ff0: 20 50 4d 41 20 28 6f 72 20 45 4f 46 20 69 66 20   PMA (or EOF if 
2000: 74 68 65 20 0a 2a 2a 20 50 4d 41 20 69 73 20 65  the .** PMA is e
2010: 6d 70 74 79 29 2e 0a 2a 2f 0a 73 74 61 74 69 63  mpty)..*/.static
2020: 20 69 6e 74 20 76 64 62 65 53 6f 72 74 65 72 49   int vdbeSorterI
2030: 74 65 72 49 6e 69 74 28 0a 20 20 73 71 6c 69 74  terInit(.  sqlit
2040: 65 33 20 2a 64 62 2c 20 20 20 20 20 20 20 20 20  e3 *db,         
2050: 20 20 20 20 20 20 20 20 20 20 20 2f 2a 20 44 61             /* Da
2060: 74 61 62 61 73 65 20 68 61 6e 64 6c 65 20 2a 2f  tabase handle */
2070: 0a 20 20 56 64 62 65 53 6f 72 74 65 72 20 2a 70  .  VdbeSorter *p
2080: 53 6f 72 74 65 72 2c 20 20 20 20 20 20 20 20 20  Sorter,         
2090: 20 20 20 2f 2a 20 53 6f 72 74 65 72 20 6f 62 6a     /* Sorter obj
20a0: 65 63 74 20 2a 2f 0a 20 20 69 36 34 20 69 53 74  ect */.  i64 iSt
20b0: 61 72 74 2c 20 20 20 20 20 20 20 20 20 20 20 20  art,            
20c0: 20 20 20 20 20 20 20 20 20 2f 2a 20 53 74 61 72           /* Star
20d0: 74 20 6f 66 66 73 65 74 20 69 6e 20 70 46 69 6c  t offset in pFil
20e0: 65 20 2a 2f 0a 20 20 56 64 62 65 53 6f 72 74 65  e */.  VdbeSorte
20f0: 72 49 74 65 72 20 2a 70 49 74 65 72 2c 20 20 20  rIter *pIter,   
2100: 20 20 20 20 20 20 20 2f 2a 20 49 74 65 72 61 74         /* Iterat
2110: 6f 72 20 74 6f 20 70 6f 70 75 6c 61 74 65 20 2a  or to populate *
2120: 2f 0a 20 20 69 36 34 20 2a 70 6e 42 79 74 65 20  /.  i64 *pnByte 
2130: 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20                  
2140: 20 20 20 20 2f 2a 20 49 4e 2f 4f 55 54 3a 20 49      /* IN/OUT: I
2150: 6e 63 72 65 6d 65 6e 74 20 74 68 69 73 20 76 61  ncrement this va
2160: 6c 75 65 20 62 79 20 50 4d 41 20 73 69 7a 65 20  lue by PMA size 
2170: 2a 2f 0a 29 7b 0a 20 20 69 6e 74 20 72 63 3b 0a  */.){.  int rc;.
2180: 20 20 69 36 34 20 69 45 6f 66 20 3d 20 70 53 6f    i64 iEof = pSo
2190: 72 74 65 72 2d 3e 69 57 72 69 74 65 4f 66 66 3b  rter->iWriteOff;
21a0: 0a 0a 20 20 61 73 73 65 72 74 28 20 69 45 6f 66  ..  assert( iEof
21b0: 3e 69 53 74 61 72 74 20 29 3b 0a 20 20 61 73 73  >iStart );.  ass
21c0: 65 72 74 28 20 70 49 74 65 72 2d 3e 61 41 6c 6c  ert( pIter->aAll
21d0: 6f 63 3d 3d 30 20 29 3b 0a 20 20 70 49 74 65 72  oc==0 );.  pIter
21e0: 2d 3e 70 46 69 6c 65 20 3d 20 70 53 6f 72 74 65  ->pFile = pSorte
21f0: 72 2d 3e 70 54 65 6d 70 31 3b 0a 20 20 70 49 74  r->pTemp1;.  pIt
2200: 65 72 2d 3e 69 52 65 61 64 4f 66 66 20 3d 20 69  er->iReadOff = i
2210: 53 74 61 72 74 3b 0a 20 20 70 49 74 65 72 2d 3e  Start;.  pIter->
2220: 6e 41 6c 6c 6f 63 20 3d 20 31 32 38 3b 0a 20 20  nAlloc = 128;.  
2230: 70 49 74 65 72 2d 3e 61 41 6c 6c 6f 63 20 3d 20  pIter->aAlloc = 
2240: 28 75 38 20 2a 29 73 71 6c 69 74 65 33 44 62 4d  (u8 *)sqlite3DbM
2250: 61 6c 6c 6f 63 52 61 77 28 64 62 2c 20 70 49 74  allocRaw(db, pIt
2260: 65 72 2d 3e 6e 41 6c 6c 6f 63 29 3b 0a 20 20 69  er->nAlloc);.  i
2270: 66 28 20 21 70 49 74 65 72 2d 3e 61 41 6c 6c 6f  f( !pIter->aAllo
2280: 63 20 29 7b 0a 20 20 20 20 72 63 20 3d 20 53 51  c ){.    rc = SQ
2290: 4c 49 54 45 5f 4e 4f 4d 45 4d 3b 0a 20 20 7d 65  LITE_NOMEM;.  }e
22a0: 6c 73 65 7b 0a 20 20 20 20 69 36 34 20 6e 42 79  lse{.    i64 nBy
22b0: 74 65 3b 0a 20 20 20 20 72 63 20 3d 20 76 64 62  te;.    rc = vdb
22c0: 65 53 6f 72 74 65 72 52 65 61 64 56 61 72 69 6e  eSorterReadVarin
22d0: 74 28 70 53 6f 72 74 65 72 2d 3e 70 54 65 6d 70  t(pSorter->pTemp
22e0: 31 2c 20 69 45 6f 66 2c 20 26 70 49 74 65 72 2d  1, iEof, &pIter-
22f0: 3e 69 52 65 61 64 4f 66 66 2c 20 26 6e 42 79 74  >iReadOff, &nByt
2300: 65 29 3b 0a 20 20 20 20 2a 70 6e 42 79 74 65 20  e);.    *pnByte 
2310: 2b 3d 20 6e 42 79 74 65 3b 0a 20 20 20 20 70 49  += nByte;.    pI
2320: 74 65 72 2d 3e 69 45 6f 66 20 3d 20 70 49 74 65  ter->iEof = pIte
2330: 72 2d 3e 69 52 65 61 64 4f 66 66 20 2b 20 6e 42  r->iReadOff + nB
2340: 79 74 65 3b 0a 20 20 7d 0a 20 20 69 66 28 20 72  yte;.  }.  if( r
2350: 63 3d 3d 53 51 4c 49 54 45 5f 4f 4b 20 29 7b 0a  c==SQLITE_OK ){.
2360: 20 20 20 20 72 63 20 3d 20 76 64 62 65 53 6f 72      rc = vdbeSor
2370: 74 65 72 49 74 65 72 4e 65 78 74 28 64 62 2c 20  terIterNext(db, 
2380: 70 49 74 65 72 29 3b 0a 20 20 7d 0a 20 20 72 65  pIter);.  }.  re
2390: 74 75 72 6e 20 72 63 3b 0a 7d 0a 0a 2f 2a 0a 2a  turn rc;.}../*.*
23a0: 2a 20 54 68 69 73 20 66 75 6e 63 74 69 6f 6e 20  * This function 
23b0: 69 73 20 63 61 6c 6c 65 64 20 74 6f 20 63 6f 6d  is called to com
23c0: 70 61 72 65 20 74 77 6f 20 69 74 65 72 61 74 6f  pare two iterato
23d0: 72 20 6b 65 79 73 20 77 68 65 6e 20 6d 65 72 67  r keys when merg
23e0: 69 6e 67 20 0a 2a 2a 20 6d 75 6c 74 69 70 6c 65  ing .** multiple
23f0: 20 62 2d 74 72 65 65 20 73 65 67 6d 65 6e 74 73   b-tree segments
2400: 2e 20 50 61 72 61 6d 65 74 65 72 20 69 4f 75 74  . Parameter iOut
2410: 20 69 73 20 74 68 65 20 69 6e 64 65 78 20 6f 66   is the index of
2420: 20 74 68 65 20 61 54 72 65 65 5b 5d 20 0a 2a 2a   the aTree[] .**
2430: 20 76 61 6c 75 65 20 74 6f 20 72 65 63 61 6c 63   value to recalc
2440: 75 6c 61 74 65 2e 0a 2a 2f 0a 73 74 61 74 69 63  ulate..*/.static
2450: 20 69 6e 74 20 76 64 62 65 53 6f 72 74 65 72 44   int vdbeSorterD
2460: 6f 43 6f 6d 70 61 72 65 28 56 64 62 65 43 75 72  oCompare(VdbeCur
2470: 73 6f 72 20 2a 70 43 73 72 2c 20 69 6e 74 20 69  sor *pCsr, int i
2480: 4f 75 74 29 7b 0a 20 20 56 64 62 65 53 6f 72 74  Out){.  VdbeSort
2490: 65 72 20 2a 70 53 6f 72 74 65 72 20 3d 20 70 43  er *pSorter = pC
24a0: 73 72 2d 3e 70 53 6f 72 74 65 72 3b 0a 20 20 69  sr->pSorter;.  i
24b0: 6e 74 20 69 31 3b 0a 20 20 69 6e 74 20 69 32 3b  nt i1;.  int i2;
24c0: 0a 20 20 69 6e 74 20 69 52 65 73 3b 0a 20 20 56  .  int iRes;.  V
24d0: 64 62 65 53 6f 72 74 65 72 49 74 65 72 20 2a 70  dbeSorterIter *p
24e0: 31 3b 0a 20 20 56 64 62 65 53 6f 72 74 65 72 49  1;.  VdbeSorterI
24f0: 74 65 72 20 2a 70 32 3b 0a 0a 20 20 61 73 73 65  ter *p2;..  asse
2500: 72 74 28 20 69 4f 75 74 3c 70 53 6f 72 74 65 72  rt( iOut<pSorter
2510: 2d 3e 6e 54 72 65 65 20 26 26 20 69 4f 75 74 3e  ->nTree && iOut>
2520: 30 20 29 3b 0a 0a 20 20 69 66 28 20 69 4f 75 74  0 );..  if( iOut
2530: 3e 3d 28 70 53 6f 72 74 65 72 2d 3e 6e 54 72 65  >=(pSorter->nTre
2540: 65 2f 32 29 20 29 7b 0a 20 20 20 20 69 31 20 3d  e/2) ){.    i1 =
2550: 20 28 69 4f 75 74 20 2d 20 70 53 6f 72 74 65 72   (iOut - pSorter
2560: 2d 3e 6e 54 72 65 65 2f 32 29 20 2a 20 32 3b 0a  ->nTree/2) * 2;.
2570: 20 20 20 20 69 32 20 3d 20 69 31 20 2b 20 31 3b      i2 = i1 + 1;
2580: 0a 20 20 7d 65 6c 73 65 7b 0a 20 20 20 20 69 31  .  }else{.    i1
2590: 20 3d 20 70 53 6f 72 74 65 72 2d 3e 61 54 72 65   = pSorter->aTre
25a0: 65 5b 69 4f 75 74 2a 32 5d 3b 0a 20 20 20 20 69  e[iOut*2];.    i
25b0: 32 20 3d 20 70 53 6f 72 74 65 72 2d 3e 61 54 72  2 = pSorter->aTr
25c0: 65 65 5b 69 4f 75 74 2a 32 2b 31 5d 3b 0a 20 20  ee[iOut*2+1];.  
25d0: 7d 0a 0a 20 20 70 31 20 3d 20 26 70 53 6f 72 74  }..  p1 = &pSort
25e0: 65 72 2d 3e 61 49 74 65 72 5b 69 31 5d 3b 0a 20  er->aIter[i1];. 
25f0: 20 70 32 20 3d 20 26 70 53 6f 72 74 65 72 2d 3e   p2 = &pSorter->
2600: 61 49 74 65 72 5b 69 32 5d 3b 0a 0a 20 20 69 66  aIter[i2];..  if
2610: 28 20 70 31 2d 3e 70 46 69 6c 65 3d 3d 30 20 29  ( p1->pFile==0 )
2620: 7b 0a 20 20 20 20 69 52 65 73 20 3d 20 69 32 3b  {.    iRes = i2;
2630: 0a 20 20 7d 65 6c 73 65 20 69 66 28 20 70 32 2d  .  }else if( p2-
2640: 3e 70 46 69 6c 65 3d 3d 30 20 29 7b 0a 20 20 20  >pFile==0 ){.   
2650: 20 69 52 65 73 20 3d 20 69 31 3b 0a 20 20 7d 65   iRes = i1;.  }e
2660: 6c 73 65 7b 0a 20 20 20 20 63 68 61 72 20 61 53  lse{.    char aS
2670: 70 61 63 65 5b 31 35 30 5d 3b 0a 20 20 20 20 55  pace[150];.    U
2680: 6e 70 61 63 6b 65 64 52 65 63 6f 72 64 20 2a 72  npackedRecord *r
2690: 31 3b 0a 0a 20 20 20 20 72 31 20 3d 20 73 71 6c  1;..    r1 = sql
26a0: 69 74 65 33 56 64 62 65 52 65 63 6f 72 64 55 6e  ite3VdbeRecordUn
26b0: 70 61 63 6b 28 0a 20 20 20 20 20 20 20 20 70 43  pack(.        pC
26c0: 73 72 2d 3e 70 4b 65 79 49 6e 66 6f 2c 20 70 31  sr->pKeyInfo, p1
26d0: 2d 3e 6e 4b 65 79 2c 20 70 31 2d 3e 61 4b 65 79  ->nKey, p1->aKey
26e0: 2c 20 61 53 70 61 63 65 2c 20 73 69 7a 65 6f 66  , aSpace, sizeof
26f0: 28 61 53 70 61 63 65 29 0a 20 20 20 20 29 3b 0a  (aSpace).    );.
2700: 20 20 20 20 69 66 28 20 72 31 3d 3d 30 20 29 20      if( r1==0 ) 
2710: 72 65 74 75 72 6e 20 53 51 4c 49 54 45 5f 4e 4f  return SQLITE_NO
2720: 4d 45 4d 3b 0a 0a 20 20 20 20 69 66 28 20 73 71  MEM;..    if( sq
2730: 6c 69 74 65 33 56 64 62 65 52 65 63 6f 72 64 43  lite3VdbeRecordC
2740: 6f 6d 70 61 72 65 28 70 32 2d 3e 6e 4b 65 79 2c  ompare(p2->nKey,
2750: 20 70 32 2d 3e 61 4b 65 79 2c 20 72 31 29 3e 3d   p2->aKey, r1)>=
2760: 30 20 29 7b 0a 20 20 20 20 20 20 69 52 65 73 20  0 ){.      iRes 
2770: 3d 20 69 31 3b 0a 20 20 20 20 7d 65 6c 73 65 7b  = i1;.    }else{
2780: 0a 20 20 20 20 20 20 69 52 65 73 20 3d 20 69 32  .      iRes = i2
2790: 3b 0a 20 20 20 20 7d 0a 20 20 20 20 73 71 6c 69  ;.    }.    sqli
27a0: 74 65 33 56 64 62 65 44 65 6c 65 74 65 55 6e 70  te3VdbeDeleteUnp
27b0: 61 63 6b 65 64 52 65 63 6f 72 64 28 72 31 29 3b  ackedRecord(r1);
27c0: 0a 20 20 7d 0a 0a 20 20 70 53 6f 72 74 65 72 2d  .  }..  pSorter-
27d0: 3e 61 54 72 65 65 5b 69 4f 75 74 5d 20 3d 20 69  >aTree[iOut] = i
27e0: 52 65 73 3b 0a 20 20 72 65 74 75 72 6e 20 53 51  Res;.  return SQ
27f0: 4c 49 54 45 5f 4f 4b 3b 0a 7d 0a 0a 2f 2a 0a 2a  LITE_OK;.}../*.*
2800: 2a 20 49 6e 69 74 69 61 6c 69 7a 65 20 74 68 65  * Initialize the
2810: 20 74 65 6d 70 6f 72 61 72 79 20 69 6e 64 65 78   temporary index
2820: 20 63 75 72 73 6f 72 20 6a 75 73 74 20 6f 70 65   cursor just ope
2830: 6e 65 64 20 61 73 20 61 20 73 6f 72 74 65 72 20  ned as a sorter 
2840: 63 75 72 73 6f 72 2e 0a 2a 2f 0a 69 6e 74 20 73  cursor..*/.int s
2850: 71 6c 69 74 65 33 56 64 62 65 53 6f 72 74 65 72  qlite3VdbeSorter
2860: 49 6e 69 74 28 73 71 6c 69 74 65 33 20 2a 64 62  Init(sqlite3 *db
2870: 2c 20 56 64 62 65 43 75 72 73 6f 72 20 2a 70 43  , VdbeCursor *pC
2880: 73 72 29 7b 0a 20 20 56 64 62 65 53 6f 72 74 65  sr){.  VdbeSorte
2890: 72 20 2a 70 53 6f 72 74 65 72 3b 20 20 20 20 20  r *pSorter;     
28a0: 20 20 20 20 20 20 20 2f 2a 20 41 6c 6c 6f 63 61         /* Alloca
28b0: 74 65 64 20 73 6f 72 74 65 72 20 6f 62 6a 65 63  ted sorter objec
28c0: 74 20 2a 2f 0a 0a 20 20 2f 2a 20 43 75 72 73 6f  t */..  /* Curso
28d0: 72 20 6d 75 73 74 20 62 65 20 61 20 74 65 6d 70  r must be a temp
28e0: 20 63 75 72 73 6f 72 20 61 6e 64 20 6e 6f 74 20   cursor and not 
28f0: 6f 70 65 6e 20 6f 6e 20 61 6e 20 69 6e 74 6b 65  open on an intke
2900: 79 20 74 61 62 6c 65 20 2a 2f 0a 20 20 61 73 73  y table */.  ass
2910: 65 72 74 28 20 70 43 73 72 2d 3e 70 4b 65 79 49  ert( pCsr->pKeyI
2920: 6e 66 6f 20 26 26 20 70 43 73 72 2d 3e 70 42 74  nfo && pCsr->pBt
2930: 20 29 3b 0a 0a 20 20 70 53 6f 72 74 65 72 20 3d   );..  pSorter =
2940: 20 73 71 6c 69 74 65 33 44 62 4d 61 6c 6c 6f 63   sqlite3DbMalloc
2950: 5a 65 72 6f 28 64 62 2c 20 73 69 7a 65 6f 66 28  Zero(db, sizeof(
2960: 56 64 62 65 53 6f 72 74 65 72 29 29 3b 0a 20 20  VdbeSorter));.  
2970: 69 66 28 20 21 70 53 6f 72 74 65 72 20 29 20 72  if( !pSorter ) r
2980: 65 74 75 72 6e 20 53 51 4c 49 54 45 5f 4e 4f 4d  eturn SQLITE_NOM
2990: 45 4d 3b 0a 20 20 70 43 73 72 2d 3e 70 53 6f 72  EM;.  pCsr->pSor
29a0: 74 65 72 20 3d 20 70 53 6f 72 74 65 72 3b 0a 20  ter = pSorter;. 
29b0: 20 72 65 74 75 72 6e 20 53 51 4c 49 54 45 5f 4f   return SQLITE_O
29c0: 4b 3b 0a 7d 0a 0a 2f 2a 0a 2a 2a 20 46 72 65 65  K;.}../*.** Free
29d0: 20 61 6e 79 20 63 75 72 73 6f 72 20 63 6f 6d 70   any cursor comp
29e0: 6f 6e 65 6e 74 73 20 61 6c 6c 6f 63 61 74 65 64  onents allocated
29f0: 20 62 79 20 73 71 6c 69 74 65 33 56 64 62 65 53   by sqlite3VdbeS
2a00: 6f 72 74 65 72 58 58 58 20 72 6f 75 74 69 6e 65  orterXXX routine
2a10: 73 2e 0a 2a 2f 0a 76 6f 69 64 20 73 71 6c 69 74  s..*/.void sqlit
2a20: 65 33 56 64 62 65 53 6f 72 74 65 72 43 6c 6f 73  e3VdbeSorterClos
2a30: 65 28 73 71 6c 69 74 65 33 20 2a 64 62 2c 20 56  e(sqlite3 *db, V
2a40: 64 62 65 43 75 72 73 6f 72 20 2a 70 43 73 72 29  dbeCursor *pCsr)
2a50: 7b 0a 20 20 56 64 62 65 53 6f 72 74 65 72 20 2a  {.  VdbeSorter *
2a60: 70 53 6f 72 74 65 72 20 3d 20 70 43 73 72 2d 3e  pSorter = pCsr->
2a70: 70 53 6f 72 74 65 72 3b 0a 20 20 69 66 28 20 70  pSorter;.  if( p
2a80: 53 6f 72 74 65 72 20 29 7b 0a 20 20 20 20 69 66  Sorter ){.    if
2a90: 28 20 70 53 6f 72 74 65 72 2d 3e 61 49 74 65 72  ( pSorter->aIter
2aa0: 20 29 7b 0a 20 20 20 20 20 20 69 6e 74 20 69 3b   ){.      int i;
2ab0: 0a 20 20 20 20 20 20 66 6f 72 28 69 3d 30 3b 20  .      for(i=0; 
2ac0: 69 3c 70 53 6f 72 74 65 72 2d 3e 6e 54 72 65 65  i<pSorter->nTree
2ad0: 3b 20 69 2b 2b 29 7b 0a 20 20 20 20 20 20 20 20  ; i++){.        
2ae0: 76 64 62 65 53 6f 72 74 65 72 49 74 65 72 5a 65  vdbeSorterIterZe
2af0: 72 6f 28 64 62 2c 20 26 70 53 6f 72 74 65 72 2d  ro(db, &pSorter-
2b00: 3e 61 49 74 65 72 5b 69 5d 29 3b 0a 20 20 20 20  >aIter[i]);.    
2b10: 20 20 7d 0a 20 20 20 20 20 20 73 71 6c 69 74 65    }.      sqlite
2b20: 33 44 62 46 72 65 65 28 64 62 2c 20 70 53 6f 72  3DbFree(db, pSor
2b30: 74 65 72 2d 3e 61 49 74 65 72 29 3b 0a 20 20 20  ter->aIter);.   
2b40: 20 7d 0a 20 20 20 20 69 66 28 20 70 53 6f 72 74   }.    if( pSort
2b50: 65 72 2d 3e 70 54 65 6d 70 31 20 29 7b 0a 20 20  er->pTemp1 ){.  
2b60: 20 20 20 20 73 71 6c 69 74 65 33 4f 73 43 6c 6f      sqlite3OsClo
2b70: 73 65 46 72 65 65 28 70 53 6f 72 74 65 72 2d 3e  seFree(pSorter->
2b80: 70 54 65 6d 70 31 29 3b 0a 20 20 20 20 7d 0a 20  pTemp1);.    }. 
2b90: 20 20 20 73 71 6c 69 74 65 33 44 62 46 72 65 65     sqlite3DbFree
2ba0: 28 64 62 2c 20 70 53 6f 72 74 65 72 29 3b 0a 20  (db, pSorter);. 
2bb0: 20 20 20 70 43 73 72 2d 3e 70 53 6f 72 74 65 72     pCsr->pSorter
2bc0: 20 3d 20 30 3b 0a 20 20 7d 0a 7d 0a 0a 2f 2a 0a   = 0;.  }.}../*.
2bd0: 2a 2a 20 41 6c 6c 6f 63 61 74 65 20 73 70 61 63  ** Allocate spac
2be0: 65 20 66 6f 72 20 61 20 66 69 6c 65 2d 68 61 6e  e for a file-han
2bf0: 64 6c 65 20 61 6e 64 20 6f 70 65 6e 20 61 20 74  dle and open a t
2c00: 65 6d 70 6f 72 61 72 79 20 66 69 6c 65 2e 20 49  emporary file. I
2c10: 66 20 73 75 63 63 65 73 73 66 75 6c 2c 0a 2a 2a  f successful,.**
2c20: 20 73 65 74 20 2a 70 70 46 69 6c 65 20 74 6f 20   set *ppFile to 
2c30: 70 6f 69 6e 74 20 74 6f 20 74 68 65 20 6d 61 6c  point to the mal
2c40: 6c 6f 63 27 64 20 66 69 6c 65 2d 68 61 6e 64 6c  loc'd file-handl
2c50: 65 20 61 6e 64 20 72 65 74 75 72 6e 20 53 51 4c  e and return SQL
2c60: 49 54 45 5f 4f 4b 2e 0a 2a 2a 20 4f 74 68 65 72  ITE_OK..** Other
2c70: 77 69 73 65 2c 20 73 65 74 20 2a 70 70 46 69 6c  wise, set *ppFil
2c80: 65 20 74 6f 20 30 20 61 6e 64 20 72 65 74 75 72  e to 0 and retur
2c90: 6e 20 61 6e 20 53 51 4c 69 74 65 20 65 72 72 6f  n an SQLite erro
2ca0: 72 20 63 6f 64 65 2e 0a 2a 2f 0a 73 74 61 74 69  r code..*/.stati
2cb0: 63 20 69 6e 74 20 76 64 62 65 53 6f 72 74 65 72  c int vdbeSorter
2cc0: 4f 70 65 6e 54 65 6d 70 46 69 6c 65 28 73 71 6c  OpenTempFile(sql
2cd0: 69 74 65 33 20 2a 64 62 2c 20 73 71 6c 69 74 65  ite3 *db, sqlite
2ce0: 33 5f 66 69 6c 65 20 2a 2a 70 70 46 69 6c 65 29  3_file **ppFile)
2cf0: 7b 0a 20 20 69 6e 74 20 64 75 6d 6d 79 3b 0a 20  {.  int dummy;. 
2d00: 20 72 65 74 75 72 6e 20 73 71 6c 69 74 65 33 4f   return sqlite3O
2d10: 73 4f 70 65 6e 4d 61 6c 6c 6f 63 28 64 62 2d 3e  sOpenMalloc(db->
2d20: 70 56 66 73 2c 20 30 2c 20 70 70 46 69 6c 65 2c  pVfs, 0, ppFile,
2d30: 0a 20 20 20 20 20 20 53 51 4c 49 54 45 5f 4f 50  .      SQLITE_OP
2d40: 45 4e 5f 54 45 4d 50 5f 44 42 20 20 20 7c 0a 20  EN_TEMP_DB   |. 
2d50: 20 20 20 20 20 53 51 4c 49 54 45 5f 4f 50 45 4e       SQLITE_OPEN
2d60: 5f 52 45 41 44 57 52 49 54 45 20 7c 20 53 51 4c  _READWRITE | SQL
2d70: 49 54 45 5f 4f 50 45 4e 5f 43 52 45 41 54 45 20  ITE_OPEN_CREATE 
2d80: 7c 0a 20 20 20 20 20 20 53 51 4c 49 54 45 5f 4f  |.      SQLITE_O
2d90: 50 45 4e 5f 45 58 43 4c 55 53 49 56 45 20 7c 20  PEN_EXCLUSIVE | 
2da0: 53 51 4c 49 54 45 5f 4f 50 45 4e 5f 44 45 4c 45  SQLITE_OPEN_DELE
2db0: 54 45 4f 4e 43 4c 4f 53 45 2c 20 26 64 75 6d 6d  TEONCLOSE, &dumm
2dc0: 79 0a 20 20 29 3b 0a 7d 0a 0a 0a 2f 2a 0a 2a 2a  y.  );.}.../*.**
2dd0: 20 57 72 69 74 65 20 74 68 65 20 63 75 72 72 65   Write the curre
2de0: 6e 74 20 63 6f 6e 74 65 6e 74 73 20 6f 66 20 74  nt contents of t
2df0: 68 65 20 62 2d 74 72 65 65 20 74 6f 20 61 20 50  he b-tree to a P
2e00: 4d 41 2e 20 52 65 74 75 72 6e 20 53 51 4c 49 54  MA. Return SQLIT
2e10: 45 5f 4f 4b 0a 2a 2a 20 69 66 20 73 75 63 63 65  E_OK.** if succe
2e20: 73 73 66 75 6c 2c 20 6f 72 20 61 6e 20 53 51 4c  ssful, or an SQL
2e30: 69 74 65 20 65 72 72 6f 72 20 63 6f 64 65 20 6f  ite error code o
2e40: 74 68 65 72 77 69 73 65 2e 0a 2a 2f 0a 73 74 61  therwise..*/.sta
2e50: 74 69 63 20 69 6e 74 20 76 64 62 65 53 6f 72 74  tic int vdbeSort
2e60: 65 72 42 74 72 65 65 54 6f 50 4d 41 28 73 71 6c  erBtreeToPMA(sql
2e70: 69 74 65 33 20 2a 64 62 2c 20 56 64 62 65 43 75  ite3 *db, VdbeCu
2e80: 72 73 6f 72 20 2a 70 43 73 72 29 7b 0a 20 20 69  rsor *pCsr){.  i
2e90: 6e 74 20 72 63 20 3d 20 53 51 4c 49 54 45 5f 4f  nt rc = SQLITE_O
2ea0: 4b 3b 20 20 20 20 20 20 20 20 20 20 20 20 20 2f  K;             /
2eb0: 2a 20 52 65 74 75 72 6e 20 63 6f 64 65 20 2a 2f  * Return code */
2ec0: 0a 20 20 56 64 62 65 53 6f 72 74 65 72 20 2a 70  .  VdbeSorter *p
2ed0: 53 6f 72 74 65 72 20 3d 20 70 43 73 72 2d 3e 70  Sorter = pCsr->p
2ee0: 53 6f 72 74 65 72 3b 0a 20 20 69 36 34 20 69 57  Sorter;.  i64 iW
2ef0: 72 69 74 65 4f 66 66 20 3d 20 70 53 6f 72 74 65  riteOff = pSorte
2f00: 72 2d 3e 69 57 72 69 74 65 4f 66 66 3b 0a 20 20  r->iWriteOff;.  
2f10: 69 6e 74 20 72 65 73 20 3d 20 30 3b 0a 20 20 76  int res = 0;.  v
2f20: 6f 69 64 20 2a 61 4d 61 6c 6c 6f 63 20 3d 20 30  oid *aMalloc = 0
2f30: 3b 0a 20 20 69 6e 74 20 6e 4d 61 6c 6c 6f 63 20  ;.  int nMalloc 
2f40: 3d 20 30 3b 0a 0a 20 20 72 63 20 3d 20 73 71 6c  = 0;..  rc = sql
2f50: 69 74 65 33 42 74 72 65 65 46 69 72 73 74 28 70  ite3BtreeFirst(p
2f60: 43 73 72 2d 3e 70 43 75 72 73 6f 72 2c 20 26 72  Csr->pCursor, &r
2f70: 65 73 29 3b 0a 20 20 69 66 28 20 72 63 21 3d 53  es);.  if( rc!=S
2f80: 51 4c 49 54 45 5f 4f 4b 20 7c 7c 20 72 65 73 20  QLITE_OK || res 
2f90: 29 20 72 65 74 75 72 6e 20 72 63 3b 0a 0a 20 20  ) return rc;..  
2fa0: 2f 2a 20 49 66 20 74 68 65 20 66 69 72 73 74 20  /* If the first 
2fb0: 74 65 6d 70 6f 72 61 72 79 20 50 4d 41 20 66 69  temporary PMA fi
2fc0: 6c 65 20 68 61 73 20 6e 6f 74 20 62 65 65 6e 20  le has not been 
2fd0: 6f 70 65 6e 65 64 2c 20 6f 70 65 6e 20 69 74 20  opened, open it 
2fe0: 6e 6f 77 2e 20 2a 2f 0a 20 20 69 66 28 20 70 53  now. */.  if( pS
2ff0: 6f 72 74 65 72 2d 3e 70 54 65 6d 70 31 3d 3d 30  orter->pTemp1==0
3000: 20 29 7b 0a 20 20 20 20 72 63 20 3d 20 76 64 62   ){.    rc = vdb
3010: 65 53 6f 72 74 65 72 4f 70 65 6e 54 65 6d 70 46  eSorterOpenTempF
3020: 69 6c 65 28 64 62 2c 20 26 70 53 6f 72 74 65 72  ile(db, &pSorter
3030: 2d 3e 70 54 65 6d 70 31 29 3b 0a 20 20 20 20 61  ->pTemp1);.    a
3040: 73 73 65 72 74 28 20 72 63 21 3d 53 51 4c 49 54  ssert( rc!=SQLIT
3050: 45 5f 4f 4b 20 7c 7c 20 70 53 6f 72 74 65 72 2d  E_OK || pSorter-
3060: 3e 70 54 65 6d 70 31 20 29 3b 0a 20 20 20 20 61  >pTemp1 );.    a
3070: 73 73 65 72 74 28 20 70 53 6f 72 74 65 72 2d 3e  ssert( pSorter->
3080: 69 57 72 69 74 65 4f 66 66 3d 3d 30 20 29 3b 0a  iWriteOff==0 );.
3090: 20 20 20 20 61 73 73 65 72 74 28 20 70 53 6f 72      assert( pSor
30a0: 74 65 72 2d 3e 6e 50 4d 41 3d 3d 30 20 29 3b 0a  ter->nPMA==0 );.
30b0: 20 20 7d 0a 0a 20 20 69 66 28 20 72 63 3d 3d 53    }..  if( rc==S
30c0: 51 4c 49 54 45 5f 4f 4b 20 29 7b 0a 0a 20 20 20  QLITE_OK ){..   
30d0: 20 70 53 6f 72 74 65 72 2d 3e 6e 50 4d 41 2b 2b   pSorter->nPMA++
30e0: 3b 0a 0a 20 20 20 20 2f 2a 20 57 72 69 74 65 20  ;..    /* Write 
30f0: 61 20 76 61 72 69 6e 74 20 63 6f 6e 74 61 69 6e  a varint contain
3100: 67 20 74 68 65 20 73 69 7a 65 20 6f 66 20 74 68  g the size of th
3110: 65 20 50 4d 41 20 69 6e 20 62 79 74 65 73 20 69  e PMA in bytes i
3120: 6e 74 6f 20 74 68 65 20 66 69 6c 65 2e 20 2a 2f  nto the file. */
3130: 0a 20 20 20 20 61 73 73 65 72 74 28 20 70 53 6f  .    assert( pSo
3140: 72 74 65 72 2d 3e 6e 42 74 72 65 65 3e 30 20 29  rter->nBtree>0 )
3150: 3b 0a 0a 20 20 20 20 66 6f 72 28 0a 20 20 20 20  ;..    for(.    
3160: 20 20 72 63 20 3d 20 76 64 62 65 53 6f 72 74 65    rc = vdbeSorte
3170: 72 57 72 69 74 65 56 61 72 69 6e 74 28 70 53 6f  rWriteVarint(pSo
3180: 72 74 65 72 2d 3e 70 54 65 6d 70 31 2c 20 70 53  rter->pTemp1, pS
3190: 6f 72 74 65 72 2d 3e 6e 42 74 72 65 65 2c 20 26  orter->nBtree, &
31a0: 69 57 72 69 74 65 4f 66 66 29 3b 0a 20 20 20 20  iWriteOff);.    
31b0: 20 20 72 63 3d 3d 53 51 4c 49 54 45 5f 4f 4b 20    rc==SQLITE_OK 
31c0: 26 26 20 72 65 73 3d 3d 30 3b 0a 20 20 20 20 20  && res==0;.     
31d0: 20 72 63 20 3d 20 73 71 6c 69 74 65 33 42 74 72   rc = sqlite3Btr
31e0: 65 65 4e 65 78 74 28 70 43 73 72 2d 3e 70 43 75  eeNext(pCsr->pCu
31f0: 72 73 6f 72 2c 20 26 72 65 73 29 0a 20 20 20 20  rsor, &res).    
3200: 29 7b 0a 20 20 20 20 20 20 69 36 34 20 6e 4b 65  ){.      i64 nKe
3210: 79 3b 20 20 20 20 20 20 20 20 20 20 20 20 20 20  y;              
3220: 20 20 20 20 20 2f 2a 20 53 69 7a 65 20 6f 66 20       /* Size of 
3230: 74 68 69 73 20 6b 65 79 20 69 6e 20 62 79 74 65  this key in byte
3240: 73 20 2a 2f 0a 0a 20 20 20 20 20 20 2f 2a 20 57  s */..      /* W
3250: 72 69 74 65 20 74 68 65 20 73 69 7a 65 20 6f 66  rite the size of
3260: 20 74 68 65 20 72 65 63 6f 72 64 20 69 6e 20 62   the record in b
3270: 79 74 65 73 20 74 6f 20 74 68 65 20 6f 75 74 70  ytes to the outp
3280: 75 74 20 66 69 6c 65 20 2a 2f 0a 20 20 20 20 20  ut file */.     
3290: 20 28 76 6f 69 64 29 73 71 6c 69 74 65 33 42 74   (void)sqlite3Bt
32a0: 72 65 65 4b 65 79 53 69 7a 65 28 70 43 73 72 2d  reeKeySize(pCsr-
32b0: 3e 70 43 75 72 73 6f 72 2c 20 26 6e 4b 65 79 29  >pCursor, &nKey)
32c0: 3b 0a 20 20 20 20 20 20 72 63 20 3d 20 76 64 62  ;.      rc = vdb
32d0: 65 53 6f 72 74 65 72 57 72 69 74 65 56 61 72 69  eSorterWriteVari
32e0: 6e 74 28 70 53 6f 72 74 65 72 2d 3e 70 54 65 6d  nt(pSorter->pTem
32f0: 70 31 2c 20 6e 4b 65 79 2c 20 26 69 57 72 69 74  p1, nKey, &iWrit
3300: 65 4f 66 66 29 3b 0a 0a 20 20 20 20 20 20 2f 2a  eOff);..      /*
3310: 20 4d 61 6b 65 20 73 75 72 65 20 74 68 65 20 61   Make sure the a
3320: 4d 61 6c 6c 6f 63 5b 5d 20 62 75 66 66 65 72 20  Malloc[] buffer 
3330: 69 73 20 6c 61 72 67 65 20 65 6e 6f 75 67 68 20  is large enough 
3340: 66 6f 72 20 74 68 65 20 72 65 63 6f 72 64 20 2a  for the record *
3350: 2f 0a 20 20 20 20 20 20 69 66 28 20 72 63 3d 3d  /.      if( rc==
3360: 53 51 4c 49 54 45 5f 4f 4b 20 26 26 20 6e 4b 65  SQLITE_OK && nKe
3370: 79 3e 6e 4d 61 6c 6c 6f 63 20 29 7b 0a 20 20 20  y>nMalloc ){.   
3380: 20 20 20 20 20 61 4d 61 6c 6c 6f 63 20 3d 20 73       aMalloc = s
3390: 71 6c 69 74 65 33 44 62 52 65 61 6c 6c 6f 63 4f  qlite3DbReallocO
33a0: 72 46 72 65 65 28 64 62 2c 20 61 4d 61 6c 6c 6f  rFree(db, aMallo
33b0: 63 2c 20 6e 4b 65 79 29 3b 0a 20 20 20 20 20 20  c, nKey);.      
33c0: 20 20 69 66 28 20 21 61 4d 61 6c 6c 6f 63 20 29    if( !aMalloc )
33d0: 7b 0a 20 20 20 20 20 20 20 20 20 20 72 63 20 3d  {.          rc =
33e0: 20 53 51 4c 49 54 45 5f 4e 4f 4d 45 4d 3b 0a 20   SQLITE_NOMEM;. 
33f0: 20 20 20 20 20 20 20 7d 0a 20 20 20 20 20 20 7d         }.      }
3400: 0a 0a 20 20 20 20 20 20 2f 2a 20 57 72 69 74 65  ..      /* Write
3410: 20 74 68 65 20 72 65 63 6f 72 64 20 69 74 73 65   the record itse
3420: 6c 66 20 74 6f 20 74 68 65 20 6f 75 74 70 75 74  lf to the output
3430: 20 66 69 6c 65 20 2a 2f 0a 20 20 20 20 20 20 69   file */.      i
3440: 66 28 20 72 63 3d 3d 53 51 4c 49 54 45 5f 4f 4b  f( rc==SQLITE_OK
3450: 20 29 7b 0a 20 20 20 20 20 20 20 20 72 63 20 3d   ){.        rc =
3460: 20 73 71 6c 69 74 65 33 42 74 72 65 65 4b 65 79   sqlite3BtreeKey
3470: 28 70 43 73 72 2d 3e 70 43 75 72 73 6f 72 2c 20  (pCsr->pCursor, 
3480: 30 2c 20 6e 4b 65 79 2c 20 61 4d 61 6c 6c 6f 63  0, nKey, aMalloc
3490: 29 3b 0a 20 20 20 20 20 20 20 20 69 66 28 20 72  );.        if( r
34a0: 63 3d 3d 53 51 4c 49 54 45 5f 4f 4b 20 29 7b 0a  c==SQLITE_OK ){.
34b0: 20 20 20 20 20 20 20 20 20 20 72 63 20 3d 20 73            rc = s
34c0: 71 6c 69 74 65 33 4f 73 57 72 69 74 65 28 70 53  qlite3OsWrite(pS
34d0: 6f 72 74 65 72 2d 3e 70 54 65 6d 70 31 2c 20 61  orter->pTemp1, a
34e0: 4d 61 6c 6c 6f 63 2c 20 6e 4b 65 79 2c 20 69 57  Malloc, nKey, iW
34f0: 72 69 74 65 4f 66 66 29 3b 0a 20 20 20 20 20 20  riteOff);.      
3500: 20 20 20 20 69 57 72 69 74 65 4f 66 66 20 2b 3d      iWriteOff +=
3510: 20 6e 4b 65 79 3b 0a 20 20 20 20 20 20 20 20 7d   nKey;.        }
3520: 0a 20 20 20 20 20 20 7d 0a 0a 20 20 20 20 7d 0a  .      }..    }.
3530: 0a 20 20 20 20 61 73 73 65 72 74 28 20 70 53 6f  .    assert( pSo
3540: 72 74 65 72 2d 3e 6e 42 74 72 65 65 3d 3d 28 0a  rter->nBtree==(.
3550: 20 20 20 20 20 20 20 20 20 20 69 57 72 69 74 65            iWrite
3560: 4f 66 66 2d 70 53 6f 72 74 65 72 2d 3e 69 57 72  Off-pSorter->iWr
3570: 69 74 65 4f 66 66 2d 73 71 6c 69 74 65 33 56 61  iteOff-sqlite3Va
3580: 72 69 6e 74 4c 65 6e 28 70 53 6f 72 74 65 72 2d  rintLen(pSorter-
3590: 3e 6e 42 74 72 65 65 29 0a 20 20 20 20 29 29 3b  >nBtree).    ));
35a0: 0a 20 20 20 20 70 53 6f 72 74 65 72 2d 3e 69 57  .    pSorter->iW
35b0: 72 69 74 65 4f 66 66 20 3d 20 69 57 72 69 74 65  riteOff = iWrite
35c0: 4f 66 66 3b 0a 20 20 20 20 73 71 6c 69 74 65 33  Off;.    sqlite3
35d0: 44 62 46 72 65 65 28 64 62 2c 20 61 4d 61 6c 6c  DbFree(db, aMall
35e0: 6f 63 29 3b 0a 20 20 7d 0a 0a 20 20 70 53 6f 72  oc);.  }..  pSor
35f0: 74 65 72 2d 3e 6e 42 74 72 65 65 20 3d 20 30 3b  ter->nBtree = 0;
3600: 0a 20 20 72 65 74 75 72 6e 20 72 63 3b 0a 7d 0a  .  return rc;.}.
3610: 0a 2f 2a 0a 2a 2a 20 54 68 69 73 20 66 75 6e 63  ./*.** This func
3620: 74 69 6f 6e 20 69 73 20 63 61 6c 6c 65 64 20 6f  tion is called o
3630: 6e 20 61 20 73 6f 72 74 65 72 20 63 75 72 73 6f  n a sorter curso
3640: 72 20 62 65 66 6f 72 65 20 65 61 63 68 20 72 6f  r before each ro
3650: 77 20 69 73 20 69 6e 73 65 72 74 65 64 2e 0a 2a  w is inserted..*
3660: 2a 20 49 66 20 74 68 65 20 63 75 72 72 65 6e 74  * If the current
3670: 20 62 2d 74 72 65 65 20 62 65 69 6e 67 20 63 6f   b-tree being co
3680: 6e 73 74 72 75 63 74 65 64 20 69 73 20 61 6c 72  nstructed is alr
3690: 65 61 64 79 20 63 6f 6e 73 69 64 65 72 65 64 20  eady considered 
36a0: 22 66 75 6c 6c 22 2c 0a 2a 2a 20 61 20 6e 65 77  "full",.** a new
36b0: 20 74 72 65 65 20 69 73 20 73 74 61 72 74 65 64   tree is started
36c0: 2e 0a 2a 2f 0a 69 6e 74 20 73 71 6c 69 74 65 33  ..*/.int sqlite3
36d0: 56 64 62 65 53 6f 72 74 65 72 57 72 69 74 65 28  VdbeSorterWrite(
36e0: 73 71 6c 69 74 65 33 20 2a 64 62 2c 20 56 64 62  sqlite3 *db, Vdb
36f0: 65 43 75 72 73 6f 72 20 2a 70 43 73 72 2c 20 69  eCursor *pCsr, i
3700: 6e 74 20 6e 4b 65 79 29 7b 0a 20 20 69 6e 74 20  nt nKey){.  int 
3710: 72 63 20 3d 20 53 51 4c 49 54 45 5f 4f 4b 3b 20  rc = SQLITE_OK; 
3720: 20 20 20 20 20 20 20 20 20 20 20 20 2f 2a 20 52              /* R
3730: 65 74 75 72 6e 20 63 6f 64 65 20 2a 2f 0a 20 20  eturn code */.  
3740: 56 64 62 65 53 6f 72 74 65 72 20 2a 70 53 6f 72  VdbeSorter *pSor
3750: 74 65 72 20 3d 20 70 43 73 72 2d 3e 70 53 6f 72  ter = pCsr->pSor
3760: 74 65 72 3b 0a 20 20 69 66 28 20 70 53 6f 72 74  ter;.  if( pSort
3770: 65 72 20 29 7b 0a 20 20 20 20 50 61 67 65 72 20  er ){.    Pager 
3780: 2a 70 50 61 67 65 72 20 3d 20 73 71 6c 69 74 65  *pPager = sqlite
3790: 33 42 74 72 65 65 50 61 67 65 72 28 70 43 73 72  3BtreePager(pCsr
37a0: 2d 3e 70 42 74 29 3b 0a 20 20 20 20 69 6e 74 20  ->pBt);.    int 
37b0: 6e 50 61 67 65 3b 20 20 20 20 20 20 20 20 20 20  nPage;          
37c0: 20 20 20 20 20 20 20 20 20 20 2f 2a 20 43 75 72            /* Cur
37d0: 72 65 6e 74 20 73 69 7a 65 20 6f 66 20 74 65 6d  rent size of tem
37e0: 70 6f 72 61 72 79 20 66 69 6c 65 20 69 6e 20 70  porary file in p
37f0: 61 67 65 73 20 2a 2f 0a 0a 20 20 20 20 73 71 6c  ages */..    sql
3800: 69 74 65 33 50 61 67 65 72 50 61 67 65 63 6f 75  ite3PagerPagecou
3810: 6e 74 28 70 50 61 67 65 72 2c 20 26 6e 50 61 67  nt(pPager, &nPag
3820: 65 29 3b 0a 0a 20 20 20 20 2f 2a 20 49 66 20 70  e);..    /* If p
3830: 53 6f 72 74 65 72 2d 3e 6e 57 6f 72 6b 69 6e 67  Sorter->nWorking
3840: 20 69 73 20 73 74 69 6c 6c 20 7a 65 72 6f 2c 20   is still zero, 
3850: 62 75 74 20 74 68 65 20 74 65 6d 70 6f 72 61 72  but the temporar
3860: 79 20 66 69 6c 65 20 68 61 73 20 62 65 65 6e 0a  y file has been.
3870: 20 20 20 20 2a 2a 20 63 72 65 61 74 65 64 20 69      ** created i
3880: 6e 20 74 68 65 20 66 69 6c 65 2d 73 79 73 74 65  n the file-syste
3890: 6d 2c 20 74 68 65 6e 20 74 68 65 20 6d 6f 73 74  m, then the most
38a0: 20 72 65 63 65 6e 74 20 69 6e 73 65 72 74 20 69   recent insert i
38b0: 6e 74 6f 20 74 68 65 0a 20 20 20 20 2a 2a 20 63  nto the.    ** c
38c0: 75 72 72 65 6e 74 20 62 2d 74 72 65 65 20 73 65  urrent b-tree se
38d0: 67 6d 65 6e 74 20 70 72 6f 62 61 62 6c 79 20 63  gment probably c
38e0: 61 75 73 65 64 20 74 68 65 20 63 61 63 68 65 20  aused the cache 
38f0: 74 6f 20 6f 76 65 72 66 6c 6f 77 20 28 69 74 20  to overflow (it 
3900: 69 73 0a 20 20 20 20 2a 2a 20 61 6c 73 6f 20 70  is.    ** also p
3910: 6f 73 73 69 62 6c 65 20 74 68 61 74 20 73 71 6c  ossible that sql
3920: 69 74 65 33 5f 72 65 6c 65 61 73 65 5f 6d 65 6d  ite3_release_mem
3930: 6f 72 79 28 29 20 77 61 73 20 63 61 6c 6c 65 64  ory() was called
3940: 29 2e 20 53 6f 20 73 65 74 20 74 68 65 0a 20 20  ). So set the.  
3950: 20 20 2a 2a 20 73 69 7a 65 20 6f 66 20 74 68 65    ** size of the
3960: 20 77 6f 72 6b 69 6e 67 20 73 65 74 20 74 6f 20   working set to 
3970: 61 20 6c 69 74 74 6c 65 20 6c 65 73 73 20 74 68  a little less th
3980: 61 6e 20 74 68 65 20 63 75 72 72 65 6e 74 20 73  an the current s
3990: 69 7a 65 20 6f 66 20 74 68 65 20 0a 20 20 20 20  ize of the .    
39a0: 2a 2a 20 66 69 6c 65 20 69 6e 20 70 61 67 65 73  ** file in pages
39b0: 2e 20 20 2a 2f 0a 20 20 20 20 69 66 28 20 70 53  .  */.    if( pS
39c0: 6f 72 74 65 72 2d 3e 6e 57 6f 72 6b 69 6e 67 3d  orter->nWorking=
39d0: 3d 30 20 26 26 20 73 71 6c 69 74 65 33 50 61 67  =0 && sqlite3Pag
39e0: 65 72 46 69 6c 65 28 70 50 61 67 65 72 29 2d 3e  erFile(pPager)->
39f0: 70 4d 65 74 68 6f 64 73 20 29 7b 0a 20 20 20 20  pMethods ){.    
3a00: 20 20 70 53 6f 72 74 65 72 2d 3e 6e 57 6f 72 6b    pSorter->nWork
3a10: 69 6e 67 20 3d 20 6e 50 61 67 65 2d 35 3b 0a 20  ing = nPage-5;. 
3a20: 20 20 20 20 20 69 66 28 20 70 53 6f 72 74 65 72       if( pSorter
3a30: 2d 3e 6e 57 6f 72 6b 69 6e 67 3c 53 4f 52 54 45  ->nWorking<SORTE
3a40: 52 5f 4d 49 4e 5f 53 45 47 4d 45 4e 54 5f 53 49  R_MIN_SEGMENT_SI
3a50: 5a 45 20 29 7b 0a 20 20 20 20 20 20 20 20 70 53  ZE ){.        pS
3a60: 6f 72 74 65 72 2d 3e 6e 57 6f 72 6b 69 6e 67 20  orter->nWorking 
3a70: 3d 20 53 4f 52 54 45 52 5f 4d 49 4e 5f 53 45 47  = SORTER_MIN_SEG
3a80: 4d 45 4e 54 5f 53 49 5a 45 3b 0a 20 20 20 20 20  MENT_SIZE;.     
3a90: 20 7d 0a 20 20 20 20 7d 0a 0a 20 20 20 20 2f 2a   }.    }..    /*
3aa0: 20 49 66 20 74 68 65 20 6e 75 6d 62 65 72 20 6f   If the number o
3ab0: 66 20 70 61 67 65 73 20 75 73 65 64 20 62 79 20  f pages used by 
3ac0: 74 68 65 20 63 75 72 72 65 6e 74 20 62 2d 74 72  the current b-tr
3ad0: 65 65 20 73 65 67 6d 65 6e 74 20 69 73 20 67 72  ee segment is gr
3ae0: 65 61 74 65 72 0a 20 20 20 20 2a 2a 20 74 68 61  eater.    ** tha
3af0: 6e 20 74 68 65 20 73 69 7a 65 20 6f 66 20 74 68  n the size of th
3b00: 65 20 77 6f 72 6b 69 6e 67 20 73 65 74 20 28 56  e working set (V
3b10: 64 62 65 53 6f 72 74 65 72 2e 6e 57 6f 72 6b 69  dbeSorter.nWorki
3b20: 6e 67 29 2c 20 73 74 61 72 74 20 61 20 6e 65 77  ng), start a new
3b30: 0a 20 20 20 20 2a 2a 20 73 65 67 6d 65 6e 74 20  .    ** segment 
3b40: 62 2d 74 72 65 65 2e 20 20 2a 2f 0a 20 20 20 20  b-tree.  */.    
3b50: 69 66 28 20 70 53 6f 72 74 65 72 2d 3e 6e 57 6f  if( pSorter->nWo
3b60: 72 6b 69 6e 67 20 26 26 20 6e 50 61 67 65 3e 3d  rking && nPage>=
3b70: 70 53 6f 72 74 65 72 2d 3e 6e 57 6f 72 6b 69 6e  pSorter->nWorkin
3b80: 67 20 29 7b 0a 20 20 20 20 20 20 42 74 43 75 72  g ){.      BtCur
3b90: 73 6f 72 20 2a 70 20 3d 20 70 43 73 72 2d 3e 70  sor *p = pCsr->p
3ba0: 43 75 72 73 6f 72 3b 2f 2a 20 43 75 72 73 6f 72  Cursor;/* Cursor
3bb0: 20 73 74 72 75 63 74 75 72 65 20 74 6f 20 63 6c   structure to cl
3bc0: 6f 73 65 20 61 6e 64 20 72 65 6f 70 65 6e 20 2a  ose and reopen *
3bd0: 2f 0a 20 20 20 20 20 20 69 6e 74 20 69 52 6f 6f  /.      int iRoo
3be0: 74 3b 20 20 20 20 20 20 20 20 20 20 20 20 20 20  t;              
3bf0: 20 20 20 20 2f 2a 20 52 6f 6f 74 20 70 61 67 65      /* Root page
3c00: 20 6f 66 20 6e 65 77 20 74 72 65 65 20 2a 2f 0a   of new tree */.
3c10: 0a 20 20 20 20 20 20 2f 2a 20 43 6f 70 79 20 74  .      /* Copy t
3c20: 68 65 20 63 75 72 72 65 6e 74 20 63 6f 6e 74 65  he current conte
3c30: 6e 74 73 20 6f 66 20 74 68 65 20 62 2d 74 72 65  nts of the b-tre
3c40: 65 20 69 6e 74 6f 20 61 20 50 4d 41 20 69 6e 20  e into a PMA in 
3c50: 73 6f 72 74 65 64 20 6f 72 64 65 72 2e 0a 20 20  sorted order..  
3c60: 20 20 20 20 2a 2a 20 43 6c 6f 73 65 20 74 68 65      ** Close the
3c70: 20 63 75 72 72 65 6e 74 6c 79 20 6f 70 65 6e 20   currently open 
3c80: 62 2d 74 72 65 65 20 63 75 72 73 6f 72 2e 20 2a  b-tree cursor. *
3c90: 2f 0a 20 20 20 20 20 20 72 63 20 3d 20 76 64 62  /.      rc = vdb
3ca0: 65 53 6f 72 74 65 72 42 74 72 65 65 54 6f 50 4d  eSorterBtreeToPM
3cb0: 41 28 64 62 2c 20 70 43 73 72 29 3b 0a 20 20 20  A(db, pCsr);.   
3cc0: 20 20 20 73 71 6c 69 74 65 33 42 74 72 65 65 43     sqlite3BtreeC
3cd0: 6c 6f 73 65 43 75 72 73 6f 72 28 70 29 3b 0a 0a  loseCursor(p);..
3ce0: 20 20 20 20 20 20 69 66 28 20 72 63 3d 3d 53 51        if( rc==SQ
3cf0: 4c 49 54 45 5f 4f 4b 20 29 7b 0a 20 20 20 20 20  LITE_OK ){.     
3d00: 20 20 20 72 63 20 3d 20 73 71 6c 69 74 65 33 42     rc = sqlite3B
3d10: 74 72 65 65 44 72 6f 70 54 61 62 6c 65 28 70 43  treeDropTable(pC
3d20: 73 72 2d 3e 70 42 74 2c 20 32 2c 20 30 29 3b 0a  sr->pBt, 2, 0);.
3d30: 23 69 66 64 65 66 20 53 51 4c 49 54 45 5f 44 45  #ifdef SQLITE_DE
3d40: 42 55 47 0a 20 20 20 20 20 20 20 20 73 71 6c 69  BUG.        sqli
3d50: 74 65 33 50 61 67 65 72 50 61 67 65 63 6f 75 6e  te3PagerPagecoun
3d60: 74 28 70 50 61 67 65 72 2c 20 26 6e 50 61 67 65  t(pPager, &nPage
3d70: 29 3b 0a 20 20 20 20 20 20 20 20 61 73 73 65 72  );.        asser
3d80: 74 28 20 72 63 21 3d 53 51 4c 49 54 45 5f 4f 4b  t( rc!=SQLITE_OK
3d90: 20 7c 7c 20 6e 50 61 67 65 3d 3d 31 20 29 3b 0a   || nPage==1 );.
3da0: 23 65 6e 64 69 66 0a 20 20 20 20 20 20 7d 0a 20  #endif.      }. 
3db0: 20 20 20 20 20 69 66 28 20 72 63 3d 3d 53 51 4c       if( rc==SQL
3dc0: 49 54 45 5f 4f 4b 20 29 7b 0a 20 20 20 20 20 20  ITE_OK ){.      
3dd0: 20 20 72 63 20 3d 20 73 71 6c 69 74 65 33 42 74    rc = sqlite3Bt
3de0: 72 65 65 43 72 65 61 74 65 54 61 62 6c 65 28 70  reeCreateTable(p
3df0: 43 73 72 2d 3e 70 42 74 2c 20 26 69 52 6f 6f 74  Csr->pBt, &iRoot
3e00: 2c 20 42 54 52 45 45 5f 42 4c 4f 42 4b 45 59 29  , BTREE_BLOBKEY)
3e10: 3b 0a 20 20 20 20 20 20 7d 0a 20 20 20 20 20 20  ;.      }.      
3e20: 69 66 28 20 72 63 3d 3d 53 51 4c 49 54 45 5f 4f  if( rc==SQLITE_O
3e30: 4b 20 29 7b 0a 20 20 20 20 20 20 20 20 61 73 73  K ){.        ass
3e40: 65 72 74 28 20 69 52 6f 6f 74 3d 3d 32 20 29 3b  ert( iRoot==2 );
3e50: 0a 20 20 20 20 20 20 20 20 72 63 20 3d 20 73 71  .        rc = sq
3e60: 6c 69 74 65 33 42 74 72 65 65 43 75 72 73 6f 72  lite3BtreeCursor
3e70: 28 70 43 73 72 2d 3e 70 42 74 2c 20 69 52 6f 6f  (pCsr->pBt, iRoo
3e80: 74 2c 20 31 2c 20 70 43 73 72 2d 3e 70 4b 65 79  t, 1, pCsr->pKey
3e90: 49 6e 66 6f 2c 20 70 29 3b 0a 20 20 20 20 20 20  Info, p);.      
3ea0: 7d 0a 20 20 20 20 7d 0a 0a 20 20 20 20 70 53 6f  }.    }..    pSo
3eb0: 72 74 65 72 2d 3e 6e 42 74 72 65 65 20 2b 3d 20  rter->nBtree += 
3ec0: 73 71 6c 69 74 65 33 56 61 72 69 6e 74 4c 65 6e  sqlite3VarintLen
3ed0: 28 6e 4b 65 79 29 20 2b 20 6e 4b 65 79 3b 0a 20  (nKey) + nKey;. 
3ee0: 20 7d 0a 20 20 72 65 74 75 72 6e 20 72 63 3b 0a   }.  return rc;.
3ef0: 7d 0a 0a 2f 2a 0a 2a 2a 20 48 65 6c 70 65 72 20  }../*.** Helper 
3f00: 66 75 6e 63 74 69 6f 6e 20 66 6f 72 20 73 71 6c  function for sql
3f10: 69 74 65 33 56 64 62 65 53 6f 72 74 65 72 52 65  ite3VdbeSorterRe
3f20: 77 69 6e 64 28 29 2e 0a 2a 2f 0a 73 74 61 74 69  wind()..*/.stati
3f30: 63 20 69 6e 74 20 76 64 62 65 53 6f 72 74 65 72  c int vdbeSorter
3f40: 49 6e 69 74 4d 65 72 67 65 28 0a 20 20 73 71 6c  InitMerge(.  sql
3f50: 69 74 65 33 20 2a 64 62 2c 0a 20 20 56 64 62 65  ite3 *db,.  Vdbe
3f60: 43 75 72 73 6f 72 20 2a 70 43 73 72 2c 0a 20 20  Cursor *pCsr,.  
3f70: 69 6e 74 20 69 46 69 72 73 74 2c 0a 20 20 69 36  int iFirst,.  i6
3f80: 34 20 2a 70 6e 42 79 74 65 20 20 20 20 20 20 20  4 *pnByte       
3f90: 20 20 20 20 20 20 20 20 20 20 20 20 20 20 2f 2a                /*
3fa0: 20 53 75 6d 20 6f 66 20 62 79 74 65 73 20 69 6e   Sum of bytes in
3fb0: 20 61 6c 6c 20 6f 70 65 6e 65 64 20 50 4d 41 73   all opened PMAs
3fc0: 20 2a 2f 0a 29 7b 0a 20 20 56 64 62 65 53 6f 72   */.){.  VdbeSor
3fd0: 74 65 72 20 2a 70 53 6f 72 74 65 72 20 3d 20 70  ter *pSorter = p
3fe0: 43 73 72 2d 3e 70 53 6f 72 74 65 72 3b 0a 20 20  Csr->pSorter;.  
3ff0: 69 6e 74 20 72 63 20 3d 20 53 51 4c 49 54 45 5f  int rc = SQLITE_
4000: 4f 4b 3b 0a 20 20 69 6e 74 20 69 3b 0a 20 20 69  OK;.  int i;.  i
4010: 36 34 20 6e 42 79 74 65 20 3d 20 30 3b 0a 0a 20  64 nByte = 0;.. 
4020: 20 2f 2a 20 49 6e 69 74 69 61 6c 69 7a 65 20 61   /* Initialize a
4030: 73 20 6d 61 6e 79 20 69 74 65 72 61 74 6f 72 73  s many iterators
4040: 20 61 73 20 70 6f 73 73 69 62 6c 65 2e 20 2a 2f   as possible. */
4050: 0a 20 20 66 6f 72 28 69 3d 69 46 69 72 73 74 3b  .  for(i=iFirst;
4060: 20 0a 20 20 20 20 20 20 72 63 3d 3d 53 51 4c 49   .      rc==SQLI
4070: 54 45 5f 4f 4b 20 26 26 20 69 3c 70 53 6f 72 74  TE_OK && i<pSort
4080: 65 72 2d 3e 6e 50 4d 41 20 26 26 20 28 69 2d 69  er->nPMA && (i-i
4090: 46 69 72 73 74 29 3c 53 4f 52 54 45 52 5f 4d 41  First)<SORTER_MA
40a0: 58 5f 4d 45 52 47 45 5f 43 4f 55 4e 54 3b 20 0a  X_MERGE_COUNT; .
40b0: 20 20 20 20 20 20 69 2b 2b 0a 20 20 29 7b 0a 20        i++.  ){. 
40c0: 20 20 20 56 64 62 65 53 6f 72 74 65 72 49 74 65     VdbeSorterIte
40d0: 72 20 2a 70 49 74 65 72 20 3d 20 26 70 53 6f 72  r *pIter = &pSor
40e0: 74 65 72 2d 3e 61 49 74 65 72 5b 69 20 2d 20 69  ter->aIter[i - i
40f0: 46 69 72 73 74 5d 3b 0a 20 20 20 20 72 63 20 3d  First];.    rc =
4100: 20 76 64 62 65 53 6f 72 74 65 72 49 74 65 72 49   vdbeSorterIterI
4110: 6e 69 74 28 64 62 2c 20 70 53 6f 72 74 65 72 2c  nit(db, pSorter,
4120: 20 70 53 6f 72 74 65 72 2d 3e 69 52 65 61 64 4f   pSorter->iReadO
4130: 66 66 2c 20 70 49 74 65 72 2c 20 26 6e 42 79 74  ff, pIter, &nByt
4140: 65 29 3b 0a 20 20 20 20 70 53 6f 72 74 65 72 2d  e);.    pSorter-
4150: 3e 69 52 65 61 64 4f 66 66 20 3d 20 70 49 74 65  >iReadOff = pIte
4160: 72 2d 3e 69 45 6f 66 3b 0a 20 20 7d 0a 20 20 61  r->iEof;.  }.  a
4170: 73 73 65 72 74 28 20 69 3e 69 46 69 72 73 74 20  ssert( i>iFirst 
4180: 29 3b 0a 0a 20 20 2f 2a 20 50 6f 70 75 6c 61 74  );..  /* Populat
4190: 65 20 74 68 65 20 61 54 72 65 65 5b 5d 20 61 72  e the aTree[] ar
41a0: 72 61 79 2e 20 2a 2f 0a 20 20 66 6f 72 28 69 3d  ray. */.  for(i=
41b0: 70 53 6f 72 74 65 72 2d 3e 6e 54 72 65 65 2d 31  pSorter->nTree-1
41c0: 3b 20 72 63 3d 3d 53 51 4c 49 54 45 5f 4f 4b 20  ; rc==SQLITE_OK 
41d0: 26 26 20 69 3e 30 3b 20 69 2d 2d 29 7b 0a 20 20  && i>0; i--){.  
41e0: 20 20 72 63 20 3d 20 76 64 62 65 53 6f 72 74 65    rc = vdbeSorte
41f0: 72 44 6f 43 6f 6d 70 61 72 65 28 70 43 73 72 2c  rDoCompare(pCsr,
4200: 20 69 29 3b 0a 20 20 7d 0a 0a 20 20 2a 70 6e 42   i);.  }..  *pnB
4210: 79 74 65 20 3d 20 6e 42 79 74 65 3b 0a 20 20 72  yte = nByte;.  r
4220: 65 74 75 72 6e 20 72 63 3b 0a 7d 0a 0a 2f 2a 0a  eturn rc;.}../*.
4230: 2a 2a 20 4f 6e 63 65 20 74 68 65 20 73 6f 72 74  ** Once the sort
4240: 65 72 20 68 61 73 20 62 65 65 6e 20 70 6f 70 75  er has been popu
4250: 6c 61 74 65 64 2c 20 74 68 69 73 20 66 75 6e 63  lated, this func
4260: 74 69 6f 6e 20 69 73 20 63 61 6c 6c 65 64 20 74  tion is called t
4270: 6f 20 70 72 65 70 61 72 65 0a 2a 2a 20 66 6f 72  o prepare.** for
4280: 20 69 74 65 72 61 74 69 6e 67 20 74 68 72 6f 75   iterating throu
4290: 67 68 20 69 74 73 20 63 6f 6e 74 65 6e 74 73 20  gh its contents 
42a0: 69 6e 20 73 6f 72 74 65 64 20 6f 72 64 65 72 2e  in sorted order.
42b0: 0a 2a 2f 0a 69 6e 74 20 73 71 6c 69 74 65 33 56  .*/.int sqlite3V
42c0: 64 62 65 53 6f 72 74 65 72 52 65 77 69 6e 64 28  dbeSorterRewind(
42d0: 73 71 6c 69 74 65 33 20 2a 64 62 2c 20 56 64 62  sqlite3 *db, Vdb
42e0: 65 43 75 72 73 6f 72 20 2a 70 43 73 72 2c 20 69  eCursor *pCsr, i
42f0: 6e 74 20 2a 70 62 45 6f 66 29 7b 0a 20 20 56 64  nt *pbEof){.  Vd
4300: 62 65 53 6f 72 74 65 72 20 2a 70 53 6f 72 74 65  beSorter *pSorte
4310: 72 20 3d 20 70 43 73 72 2d 3e 70 53 6f 72 74 65  r = pCsr->pSorte
4320: 72 3b 0a 20 20 69 6e 74 20 72 63 3b 20 20 20 20  r;.  int rc;    
4330: 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20                  
4340: 20 20 20 20 20 2f 2a 20 52 65 74 75 72 6e 20 63       /* Return c
4350: 6f 64 65 20 2a 2f 0a 20 20 73 71 6c 69 74 65 33  ode */.  sqlite3
4360: 5f 66 69 6c 65 20 2a 70 54 65 6d 70 32 20 3d 20  _file *pTemp2 = 
4370: 30 3b 20 20 20 20 20 20 20 2f 2a 20 53 65 63 6f  0;       /* Seco
4380: 6e 64 20 74 65 6d 70 20 66 69 6c 65 20 74 6f 20  nd temp file to 
4390: 75 73 65 20 2a 2f 0a 20 20 69 36 34 20 69 57 72  use */.  i64 iWr
43a0: 69 74 65 32 20 3d 20 30 3b 20 20 20 20 20 20 20  ite2 = 0;       
43b0: 20 20 20 20 20 20 20 20 20 2f 2a 20 57 72 69 74           /* Writ
43c0: 65 20 6f 66 66 73 65 74 20 66 6f 72 20 70 54 65  e offset for pTe
43d0: 6d 70 32 20 2a 2f 0a 20 20 69 6e 74 20 6e 49 74  mp2 */.  int nIt
43e0: 65 72 3b 20 20 20 20 20 20 20 20 20 20 20 20 20  er;             
43f0: 20 20 20 20 20 20 20 20 20 2f 2a 20 4e 75 6d 62           /* Numb
4400: 65 72 20 6f 66 20 69 74 65 72 61 74 6f 72 73 20  er of iterators 
4410: 75 73 65 64 20 2a 2f 0a 20 20 69 6e 74 20 6e 42  used */.  int nB
4420: 79 74 65 3b 20 20 20 20 20 20 20 20 20 20 20 20  yte;            
4430: 20 20 20 20 20 20 20 20 20 20 2f 2a 20 42 79 74            /* Byt
4440: 65 73 20 6f 66 20 73 70 61 63 65 20 72 65 71 75  es of space requ
4450: 69 72 65 64 20 66 6f 72 20 61 49 74 65 72 2f 61  ired for aIter/a
4460: 54 72 65 65 20 2a 2f 0a 20 20 69 6e 74 20 4e 20  Tree */.  int N 
4470: 3d 20 32 3b 20 20 20 20 20 20 20 20 20 20 20 20  = 2;            
4480: 20 20 20 20 20 20 20 20 20 20 2f 2a 20 50 6f 77            /* Pow
4490: 65 72 20 6f 66 20 32 20 3e 3d 20 6e 49 74 65 72  er of 2 >= nIter
44a0: 20 2a 2f 0a 0a 20 20 61 73 73 65 72 74 28 20 70   */..  assert( p
44b0: 53 6f 72 74 65 72 20 29 3b 0a 0a 20 20 2f 2a 20  Sorter );..  /* 
44c0: 57 72 69 74 65 20 74 68 65 20 63 75 72 72 65 6e  Write the curren
44d0: 74 20 62 2d 74 72 65 65 20 74 6f 20 61 20 50 4d  t b-tree to a PM
44e0: 41 2e 20 43 6c 6f 73 65 20 74 68 65 20 62 2d 74  A. Close the b-t
44f0: 72 65 65 20 63 75 72 73 6f 72 2e 20 2a 2f 0a 20  ree cursor. */. 
4500: 20 72 63 20 3d 20 76 64 62 65 53 6f 72 74 65 72   rc = vdbeSorter
4510: 42 74 72 65 65 54 6f 50 4d 41 28 64 62 2c 20 70  BtreeToPMA(db, p
4520: 43 73 72 29 3b 0a 20 20 73 71 6c 69 74 65 33 42  Csr);.  sqlite3B
4530: 74 72 65 65 43 6c 6f 73 65 43 75 72 73 6f 72 28  treeCloseCursor(
4540: 70 43 73 72 2d 3e 70 43 75 72 73 6f 72 29 3b 0a  pCsr->pCursor);.
4550: 20 20 69 66 28 20 72 63 21 3d 53 51 4c 49 54 45    if( rc!=SQLITE
4560: 5f 4f 4b 20 29 20 72 65 74 75 72 6e 20 72 63 3b  _OK ) return rc;
4570: 0a 20 20 69 66 28 20 70 53 6f 72 74 65 72 2d 3e  .  if( pSorter->
4580: 6e 50 4d 41 3d 3d 30 20 29 7b 0a 20 20 20 20 2a  nPMA==0 ){.    *
4590: 70 62 45 6f 66 20 3d 20 31 3b 0a 20 20 20 20 72  pbEof = 1;.    r
45a0: 65 74 75 72 6e 20 53 51 4c 49 54 45 5f 4f 4b 3b  eturn SQLITE_OK;
45b0: 0a 20 20 7d 0a 0a 20 20 2f 2a 20 41 6c 6c 6f 63  .  }..  /* Alloc
45c0: 61 74 65 20 73 70 61 63 65 20 66 6f 72 20 61 49  ate space for aI
45d0: 74 65 72 5b 5d 20 61 6e 64 20 61 54 72 65 65 5b  ter[] and aTree[
45e0: 5d 2e 20 2a 2f 0a 20 20 6e 49 74 65 72 20 3d 20  ]. */.  nIter = 
45f0: 70 53 6f 72 74 65 72 2d 3e 6e 50 4d 41 3b 0a 20  pSorter->nPMA;. 
4600: 20 69 66 28 20 6e 49 74 65 72 3e 53 4f 52 54 45   if( nIter>SORTE
4610: 52 5f 4d 41 58 5f 4d 45 52 47 45 5f 43 4f 55 4e  R_MAX_MERGE_COUN
4620: 54 20 29 20 6e 49 74 65 72 20 3d 20 53 4f 52 54  T ) nIter = SORT
4630: 45 52 5f 4d 41 58 5f 4d 45 52 47 45 5f 43 4f 55  ER_MAX_MERGE_COU
4640: 4e 54 3b 0a 20 20 61 73 73 65 72 74 28 20 6e 49  NT;.  assert( nI
4650: 74 65 72 3e 30 20 29 3b 0a 20 20 77 68 69 6c 65  ter>0 );.  while
4660: 28 20 4e 3c 6e 49 74 65 72 20 29 20 4e 20 2b 3d  ( N<nIter ) N +=
4670: 20 4e 3b 0a 20 20 6e 42 79 74 65 20 3d 20 4e 20   N;.  nByte = N 
4680: 2a 20 28 73 69 7a 65 6f 66 28 69 6e 74 29 20 2b  * (sizeof(int) +
4690: 20 73 69 7a 65 6f 66 28 56 64 62 65 53 6f 72 74   sizeof(VdbeSort
46a0: 65 72 49 74 65 72 29 29 3b 0a 20 20 70 53 6f 72  erIter));.  pSor
46b0: 74 65 72 2d 3e 61 49 74 65 72 20 3d 20 28 56 64  ter->aIter = (Vd
46c0: 62 65 53 6f 72 74 65 72 49 74 65 72 20 2a 29 73  beSorterIter *)s
46d0: 71 6c 69 74 65 33 44 62 4d 61 6c 6c 6f 63 5a 65  qlite3DbMallocZe
46e0: 72 6f 28 64 62 2c 20 6e 42 79 74 65 29 3b 0a 20  ro(db, nByte);. 
46f0: 20 69 66 28 20 21 70 53 6f 72 74 65 72 2d 3e 61   if( !pSorter->a
4700: 49 74 65 72 20 29 20 72 65 74 75 72 6e 20 53 51  Iter ) return SQ
4710: 4c 49 54 45 5f 4e 4f 4d 45 4d 3b 0a 20 20 70 53  LITE_NOMEM;.  pS
4720: 6f 72 74 65 72 2d 3e 61 54 72 65 65 20 3d 20 28  orter->aTree = (
4730: 69 6e 74 20 2a 29 26 70 53 6f 72 74 65 72 2d 3e  int *)&pSorter->
4740: 61 49 74 65 72 5b 4e 5d 3b 0a 20 20 70 53 6f 72  aIter[N];.  pSor
4750: 74 65 72 2d 3e 6e 54 72 65 65 20 3d 20 4e 3b 0a  ter->nTree = N;.
4760: 0a 20 20 64 6f 20 7b 0a 20 20 20 20 69 6e 74 20  .  do {.    int 
4770: 69 4e 65 77 3b 20 20 20 20 20 20 20 20 20 20 20  iNew;           
4780: 20 20 20 20 20 20 20 20 20 20 2f 2a 20 49 6e 64            /* Ind
4790: 65 78 20 6f 66 20 6e 65 77 2c 20 6d 65 72 67 65  ex of new, merge
47a0: 64 2c 20 50 4d 41 20 2a 2f 0a 0a 20 20 20 20 66  d, PMA */..    f
47b0: 6f 72 28 69 4e 65 77 3d 30 3b 20 0a 20 20 20 20  or(iNew=0; .    
47c0: 20 20 20 20 72 63 3d 3d 53 51 4c 49 54 45 5f 4f      rc==SQLITE_O
47d0: 4b 20 26 26 20 69 4e 65 77 2a 53 4f 52 54 45 52  K && iNew*SORTER
47e0: 5f 4d 41 58 5f 4d 45 52 47 45 5f 43 4f 55 4e 54  _MAX_MERGE_COUNT
47f0: 3c 70 53 6f 72 74 65 72 2d 3e 6e 50 4d 41 3b 20  <pSorter->nPMA; 
4800: 0a 20 20 20 20 20 20 20 20 69 4e 65 77 2b 2b 0a  .        iNew++.
4810: 20 20 20 20 29 7b 0a 20 20 20 20 20 20 69 36 34      ){.      i64
4820: 20 6e 57 72 69 74 65 3b 20 20 20 20 20 20 20 20   nWrite;        
4830: 20 20 20 20 20 20 20 20 20 2f 2a 20 4e 75 6d 62           /* Numb
4840: 65 72 20 6f 66 20 62 79 74 65 73 20 69 6e 20 6e  er of bytes in n
4850: 65 77 20 50 4d 41 20 2a 2f 0a 0a 20 20 20 20 20  ew PMA */..     
4860: 20 2f 2a 20 49 66 20 74 68 65 72 65 20 61 72 65   /* If there are
4870: 20 53 4f 52 54 45 52 5f 4d 41 58 5f 4d 45 52 47   SORTER_MAX_MERG
4880: 45 5f 43 4f 55 4e 54 20 6f 72 20 6c 65 73 73 20  E_COUNT or less 
4890: 50 4d 41 73 20 69 6e 20 66 69 6c 65 20 70 54 65  PMAs in file pTe
48a0: 6d 70 31 2c 0a 20 20 20 20 20 20 2a 2a 20 69 6e  mp1,.      ** in
48b0: 69 74 69 61 6c 69 7a 65 20 61 6e 20 69 74 65 72  itialize an iter
48c0: 61 74 6f 72 20 66 6f 72 20 65 61 63 68 20 6f 66  ator for each of
48d0: 20 74 68 65 6d 20 61 6e 64 20 62 72 65 61 6b 20   them and break 
48e0: 6f 75 74 20 6f 66 20 74 68 65 20 6c 6f 6f 70 2e  out of the loop.
48f0: 0a 20 20 20 20 20 20 2a 2a 20 54 68 65 73 65 20  .      ** These 
4900: 69 74 65 72 61 74 6f 72 73 20 77 69 6c 6c 20 62  iterators will b
4910: 65 20 69 6e 63 72 65 6d 65 6e 74 61 6c 6c 79 20  e incrementally 
4920: 6d 65 72 67 65 64 20 61 73 20 74 68 65 20 56 44  merged as the VD
4930: 42 45 20 6c 61 79 65 72 20 63 61 6c 6c 73 0a 20  BE layer calls. 
4940: 20 20 20 20 20 2a 2a 20 73 71 6c 69 74 65 33 56       ** sqlite3V
4950: 64 62 65 53 6f 72 74 65 72 4e 65 78 74 28 29 2e  dbeSorterNext().
4960: 0a 20 20 20 20 20 20 2a 2a 0a 20 20 20 20 20 20  .      **.      
4970: 2a 2a 20 4f 74 68 65 72 77 69 73 65 2c 20 69 66  ** Otherwise, if
4980: 20 70 54 65 6d 70 31 20 63 6f 6e 74 61 69 6e 73   pTemp1 contains
4990: 20 6d 6f 72 65 20 74 68 61 6e 20 53 4f 52 54 45   more than SORTE
49a0: 52 5f 4d 41 58 5f 4d 45 52 47 45 5f 43 4f 55 4e  R_MAX_MERGE_COUN
49b0: 54 20 50 4d 41 73 2c 0a 20 20 20 20 20 20 2a 2a  T PMAs,.      **
49c0: 20 69 6e 69 74 69 61 6c 69 7a 65 20 69 6e 74 65   initialize inte
49d0: 72 61 74 6f 72 73 20 66 6f 72 20 53 4f 52 54 45  rators for SORTE
49e0: 52 5f 4d 41 58 5f 4d 45 52 47 45 5f 43 4f 55 4e  R_MAX_MERGE_COUN
49f0: 54 20 6f 66 20 74 68 65 6d 2e 20 54 68 65 73 65  T of them. These
4a00: 20 50 4d 41 73 0a 20 20 20 20 20 20 2a 2a 20 61   PMAs.      ** a
4a10: 72 65 20 6d 65 72 67 65 64 20 69 6e 74 6f 20 61  re merged into a
4a20: 20 73 69 6e 67 6c 65 20 50 4d 41 20 74 68 61 74   single PMA that
4a30: 20 69 73 20 77 72 69 74 74 65 6e 20 74 6f 20 66   is written to f
4a40: 69 6c 65 20 70 54 65 6d 70 32 2e 0a 20 20 20 20  ile pTemp2..    
4a50: 20 20 2a 2f 0a 20 20 20 20 20 20 72 63 20 3d 20    */.      rc = 
4a60: 76 64 62 65 53 6f 72 74 65 72 49 6e 69 74 4d 65  vdbeSorterInitMe
4a70: 72 67 65 28 64 62 2c 20 70 43 73 72 2c 20 69 4e  rge(db, pCsr, iN
4a80: 65 77 2a 53 4f 52 54 45 52 5f 4d 41 58 5f 4d 45  ew*SORTER_MAX_ME
4a90: 52 47 45 5f 43 4f 55 4e 54 2c 20 26 6e 57 72 69  RGE_COUNT, &nWri
4aa0: 74 65 29 3b 0a 20 20 20 20 20 20 61 73 73 65 72  te);.      asser
4ab0: 74 28 20 72 63 21 3d 53 51 4c 49 54 45 5f 4f 4b  t( rc!=SQLITE_OK
4ac0: 20 7c 7c 20 70 53 6f 72 74 65 72 2d 3e 61 49 74   || pSorter->aIt
4ad0: 65 72 5b 20 70 53 6f 72 74 65 72 2d 3e 61 54 72  er[ pSorter->aTr
4ae0: 65 65 5b 31 5d 20 5d 2e 70 46 69 6c 65 20 29 3b  ee[1] ].pFile );
4af0: 0a 20 20 20 20 20 20 69 66 28 20 72 63 21 3d 53  .      if( rc!=S
4b00: 51 4c 49 54 45 5f 4f 4b 20 7c 7c 20 70 53 6f 72  QLITE_OK || pSor
4b10: 74 65 72 2d 3e 6e 50 4d 41 3c 3d 53 4f 52 54 45  ter->nPMA<=SORTE
4b20: 52 5f 4d 41 58 5f 4d 45 52 47 45 5f 43 4f 55 4e  R_MAX_MERGE_COUN
4b30: 54 20 29 7b 0a 20 20 20 20 20 20 20 20 62 72 65  T ){.        bre
4b40: 61 6b 3b 0a 20 20 20 20 20 20 7d 0a 0a 20 20 20  ak;.      }..   
4b50: 20 20 20 2f 2a 20 4f 70 65 6e 20 74 68 65 20 73     /* Open the s
4b60: 65 63 6f 6e 64 20 74 65 6d 70 20 66 69 6c 65 2c  econd temp file,
4b70: 20 69 66 20 69 74 20 69 73 20 6e 6f 74 20 61 6c   if it is not al
4b80: 72 65 61 64 79 20 6f 70 65 6e 2e 20 2a 2f 0a 20  ready open. */. 
4b90: 20 20 20 20 20 69 66 28 20 70 54 65 6d 70 32 3d       if( pTemp2=
4ba0: 3d 30 20 29 7b 0a 20 20 20 20 20 20 20 20 61 73  =0 ){.        as
4bb0: 73 65 72 74 28 20 69 57 72 69 74 65 32 3d 3d 30  sert( iWrite2==0
4bc0: 20 29 3b 0a 20 20 20 20 20 20 20 20 72 63 20 3d   );.        rc =
4bd0: 20 76 64 62 65 53 6f 72 74 65 72 4f 70 65 6e 54   vdbeSorterOpenT
4be0: 65 6d 70 46 69 6c 65 28 64 62 2c 20 26 70 54 65  empFile(db, &pTe
4bf0: 6d 70 32 29 3b 0a 20 20 20 20 20 20 7d 0a 0a 20  mp2);.      }.. 
4c00: 20 20 20 20 20 69 66 28 20 72 63 3d 3d 53 51 4c       if( rc==SQL
4c10: 49 54 45 5f 4f 4b 20 29 7b 0a 20 20 20 20 20 20  ITE_OK ){.      
4c20: 20 20 72 63 20 3d 20 76 64 62 65 53 6f 72 74 65    rc = vdbeSorte
4c30: 72 57 72 69 74 65 56 61 72 69 6e 74 28 70 54 65  rWriteVarint(pTe
4c40: 6d 70 32 2c 20 6e 57 72 69 74 65 2c 20 26 69 57  mp2, nWrite, &iW
4c50: 72 69 74 65 32 29 3b 0a 20 20 20 20 20 20 7d 0a  rite2);.      }.
4c60: 0a 20 20 20 20 20 20 69 66 28 20 72 63 3d 3d 53  .      if( rc==S
4c70: 51 4c 49 54 45 5f 4f 4b 20 29 7b 0a 20 20 20 20  QLITE_OK ){.    
4c80: 20 20 20 20 69 6e 74 20 62 45 6f 66 20 3d 20 30      int bEof = 0
4c90: 3b 0a 20 20 20 20 20 20 20 20 77 68 69 6c 65 28  ;.        while(
4ca0: 20 72 63 3d 3d 53 51 4c 49 54 45 5f 4f 4b 20 26   rc==SQLITE_OK &
4cb0: 26 20 62 45 6f 66 3d 3d 30 20 29 7b 0a 20 20 20  & bEof==0 ){.   
4cc0: 20 20 20 20 20 20 20 69 6e 74 20 6e 42 79 74 65         int nByte
4cd0: 3b 0a 20 20 20 20 20 20 20 20 20 20 56 64 62 65  ;.          Vdbe
4ce0: 53 6f 72 74 65 72 49 74 65 72 20 2a 70 49 74 65  SorterIter *pIte
4cf0: 72 20 3d 20 26 70 53 6f 72 74 65 72 2d 3e 61 49  r = &pSorter->aI
4d00: 74 65 72 5b 20 70 53 6f 72 74 65 72 2d 3e 61 54  ter[ pSorter->aT
4d10: 72 65 65 5b 31 5d 20 5d 3b 0a 20 20 20 20 20 20  ree[1] ];.      
4d20: 20 20 20 20 61 73 73 65 72 74 28 20 70 49 74 65      assert( pIte
4d30: 72 2d 3e 70 46 69 6c 65 20 29 3b 0a 20 20 20 20  r->pFile );.    
4d40: 20 20 20 20 20 20 6e 42 79 74 65 20 3d 20 70 49        nByte = pI
4d50: 74 65 72 2d 3e 6e 4b 65 79 20 2b 20 73 71 6c 69  ter->nKey + sqli
4d60: 74 65 33 56 61 72 69 6e 74 4c 65 6e 28 70 49 74  te3VarintLen(pIt
4d70: 65 72 2d 3e 6e 4b 65 79 29 3b 0a 20 20 20 20 20  er->nKey);.     
4d80: 20 20 20 20 20 72 63 20 3d 20 73 71 6c 69 74 65       rc = sqlite
4d90: 33 4f 73 57 72 69 74 65 28 70 54 65 6d 70 32 2c  3OsWrite(pTemp2,
4da0: 20 70 49 74 65 72 2d 3e 61 41 6c 6c 6f 63 2c 20   pIter->aAlloc, 
4db0: 6e 42 79 74 65 2c 20 69 57 72 69 74 65 32 29 3b  nByte, iWrite2);
4dc0: 0a 20 20 20 20 20 20 20 20 20 20 69 57 72 69 74  .          iWrit
4dd0: 65 32 20 2b 3d 20 6e 42 79 74 65 3b 0a 20 20 20  e2 += nByte;.   
4de0: 20 20 20 20 20 20 20 69 66 28 20 72 63 3d 3d 53         if( rc==S
4df0: 51 4c 49 54 45 5f 4f 4b 20 29 7b 0a 20 20 20 20  QLITE_OK ){.    
4e00: 20 20 20 20 20 20 20 20 72 63 20 3d 20 73 71 6c          rc = sql
4e10: 69 74 65 33 56 64 62 65 53 6f 72 74 65 72 4e 65  ite3VdbeSorterNe
4e20: 78 74 28 64 62 2c 20 70 43 73 72 2c 20 26 62 45  xt(db, pCsr, &bE
4e30: 6f 66 29 3b 0a 20 20 20 20 20 20 20 20 20 20 7d  of);.          }
4e40: 0a 20 20 20 20 20 20 20 20 7d 0a 20 20 20 20 20  .        }.     
4e50: 20 7d 0a 20 20 20 20 7d 0a 0a 20 20 20 20 69 66   }.    }..    if
4e60: 28 20 70 53 6f 72 74 65 72 2d 3e 6e 50 4d 41 3c  ( pSorter->nPMA<
4e70: 3d 53 4f 52 54 45 52 5f 4d 41 58 5f 4d 45 52 47  =SORTER_MAX_MERG
4e80: 45 5f 43 4f 55 4e 54 20 29 7b 0a 20 20 20 20 20  E_COUNT ){.     
4e90: 20 62 72 65 61 6b 3b 0a 20 20 20 20 7d 65 6c 73   break;.    }els
4ea0: 65 7b 0a 20 20 20 20 20 20 73 71 6c 69 74 65 33  e{.      sqlite3
4eb0: 5f 66 69 6c 65 20 2a 70 54 6d 70 20 3d 20 70 53  _file *pTmp = pS
4ec0: 6f 72 74 65 72 2d 3e 70 54 65 6d 70 31 3b 0a 20  orter->pTemp1;. 
4ed0: 20 20 20 20 20 70 53 6f 72 74 65 72 2d 3e 6e 50       pSorter->nP
4ee0: 4d 41 20 3d 20 69 4e 65 77 3b 0a 20 20 20 20 20  MA = iNew;.     
4ef0: 20 70 53 6f 72 74 65 72 2d 3e 70 54 65 6d 70 31   pSorter->pTemp1
4f00: 20 3d 20 70 54 65 6d 70 32 3b 0a 20 20 20 20 20   = pTemp2;.     
4f10: 20 70 54 65 6d 70 32 20 3d 20 70 54 6d 70 3b 0a   pTemp2 = pTmp;.
4f20: 20 20 20 20 20 20 70 53 6f 72 74 65 72 2d 3e 69        pSorter->i
4f30: 57 72 69 74 65 4f 66 66 20 3d 20 69 57 72 69 74  WriteOff = iWrit
4f40: 65 32 3b 0a 20 20 20 20 20 20 70 53 6f 72 74 65  e2;.      pSorte
4f50: 72 2d 3e 69 52 65 61 64 4f 66 66 20 3d 20 30 3b  r->iReadOff = 0;
4f60: 0a 20 20 20 20 20 20 69 57 72 69 74 65 32 20 3d  .      iWrite2 =
4f70: 20 30 3b 0a 20 20 20 20 7d 0a 20 20 7d 77 68 69   0;.    }.  }whi
4f80: 6c 65 28 20 72 63 3d 3d 53 51 4c 49 54 45 5f 4f  le( rc==SQLITE_O
4f90: 4b 20 29 3b 0a 0a 20 20 69 66 28 20 70 54 65 6d  K );..  if( pTem
4fa0: 70 32 20 29 7b 0a 20 20 20 20 73 71 6c 69 74 65  p2 ){.    sqlite
4fb0: 33 4f 73 43 6c 6f 73 65 46 72 65 65 28 70 54 65  3OsCloseFree(pTe
4fc0: 6d 70 32 29 3b 0a 20 20 7d 0a 20 20 2a 70 62 45  mp2);.  }.  *pbE
4fd0: 6f 66 20 3d 20 28 70 53 6f 72 74 65 72 2d 3e 61  of = (pSorter->a
4fe0: 49 74 65 72 5b 70 53 6f 72 74 65 72 2d 3e 61 54  Iter[pSorter->aT
4ff0: 72 65 65 5b 31 5d 5d 2e 70 46 69 6c 65 3d 3d 30  ree[1]].pFile==0
5000: 29 3b 0a 20 20 72 65 74 75 72 6e 20 72 63 3b 0a  );.  return rc;.
5010: 7d 0a 0a 2f 2a 0a 2a 2a 20 41 64 76 61 6e 63 65  }../*.** Advance
5020: 20 74 6f 20 74 68 65 20 6e 65 78 74 20 65 6c 65   to the next ele
5030: 6d 65 6e 74 20 69 6e 20 74 68 65 20 73 6f 72 74  ment in the sort
5040: 65 72 2e 0a 2a 2f 0a 69 6e 74 20 73 71 6c 69 74  er..*/.int sqlit
5050: 65 33 56 64 62 65 53 6f 72 74 65 72 4e 65 78 74  e3VdbeSorterNext
5060: 28 73 71 6c 69 74 65 33 20 2a 64 62 2c 20 56 64  (sqlite3 *db, Vd
5070: 62 65 43 75 72 73 6f 72 20 2a 70 43 73 72 2c 20  beCursor *pCsr, 
5080: 69 6e 74 20 2a 70 62 45 6f 66 29 7b 0a 20 20 56  int *pbEof){.  V
5090: 64 62 65 53 6f 72 74 65 72 20 2a 70 53 6f 72 74  dbeSorter *pSort
50a0: 65 72 20 3d 20 70 43 73 72 2d 3e 70 53 6f 72 74  er = pCsr->pSort
50b0: 65 72 3b 0a 20 20 69 6e 74 20 69 50 72 65 76 20  er;.  int iPrev 
50c0: 3d 20 70 53 6f 72 74 65 72 2d 3e 61 54 72 65 65  = pSorter->aTree
50d0: 5b 31 5d 3b 20 20 2f 2a 20 49 6e 64 65 78 20 6f  [1];  /* Index o
50e0: 66 20 69 74 65 72 61 74 6f 72 20 74 6f 20 61 64  f iterator to ad
50f0: 76 61 6e 63 65 20 2a 2f 0a 20 20 69 6e 74 20 69  vance */.  int i
5100: 3b 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20  ;               
5110: 20 20 20 20 20 20 20 20 20 20 20 2f 2a 20 49 6e             /* In
5120: 64 65 78 20 6f 66 20 61 54 72 65 65 5b 5d 20 74  dex of aTree[] t
5130: 6f 20 72 65 63 61 6c 63 75 6c 61 74 65 20 2a 2f  o recalculate */
5140: 0a 20 20 69 6e 74 20 72 63 3b 20 20 20 20 20 20  .  int rc;      
5150: 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20                  
5160: 20 20 20 2f 2a 20 52 65 74 75 72 6e 20 63 6f 64     /* Return cod
5170: 65 20 2a 2f 0a 0a 20 20 72 63 20 3d 20 76 64 62  e */..  rc = vdb
5180: 65 53 6f 72 74 65 72 49 74 65 72 4e 65 78 74 28  eSorterIterNext(
5190: 64 62 2c 20 26 70 53 6f 72 74 65 72 2d 3e 61 49  db, &pSorter->aI
51a0: 74 65 72 5b 69 50 72 65 76 5d 29 3b 0a 20 20 66  ter[iPrev]);.  f
51b0: 6f 72 28 69 3d 28 70 53 6f 72 74 65 72 2d 3e 6e  or(i=(pSorter->n
51c0: 54 72 65 65 2b 69 50 72 65 76 29 2f 32 3b 20 72  Tree+iPrev)/2; r
51d0: 63 3d 3d 53 51 4c 49 54 45 5f 4f 4b 20 26 26 20  c==SQLITE_OK && 
51e0: 69 3e 30 3b 20 69 3d 69 2f 32 29 7b 0a 20 20 20  i>0; i=i/2){.   
51f0: 20 72 63 20 3d 20 76 64 62 65 53 6f 72 74 65 72   rc = vdbeSorter
5200: 44 6f 43 6f 6d 70 61 72 65 28 70 43 73 72 2c 20  DoCompare(pCsr, 
5210: 69 29 3b 0a 20 20 7d 0a 0a 20 20 2a 70 62 45 6f  i);.  }..  *pbEo
5220: 66 20 3d 20 28 70 53 6f 72 74 65 72 2d 3e 61 49  f = (pSorter->aI
5230: 74 65 72 5b 70 53 6f 72 74 65 72 2d 3e 61 54 72  ter[pSorter->aTr
5240: 65 65 5b 31 5d 5d 2e 70 46 69 6c 65 3d 3d 30 29  ee[1]].pFile==0)
5250: 3b 0a 20 20 72 65 74 75 72 6e 20 72 63 3b 0a 7d  ;.  return rc;.}
5260: 0a 0a 2f 2a 0a 2a 2a 20 43 6f 70 79 20 74 68 65  ../*.** Copy the
5270: 20 63 75 72 72 65 6e 74 20 73 6f 72 74 65 72 20   current sorter 
5280: 6b 65 79 20 69 6e 74 6f 20 74 68 65 20 6d 65 6d  key into the mem
5290: 6f 72 79 20 63 65 6c 6c 20 70 4f 75 74 2e 0a 2a  ory cell pOut..*
52a0: 2f 0a 69 6e 74 20 73 71 6c 69 74 65 33 56 64 62  /.int sqlite3Vdb
52b0: 65 53 6f 72 74 65 72 52 6f 77 6b 65 79 28 73 71  eSorterRowkey(sq
52c0: 6c 69 74 65 33 20 2a 64 62 2c 20 56 64 62 65 43  lite3 *db, VdbeC
52d0: 75 72 73 6f 72 20 2a 70 43 73 72 2c 20 4d 65 6d  ursor *pCsr, Mem
52e0: 20 2a 70 4f 75 74 29 7b 0a 20 20 56 64 62 65 53   *pOut){.  VdbeS
52f0: 6f 72 74 65 72 20 2a 70 53 6f 72 74 65 72 20 3d  orter *pSorter =
5300: 20 70 43 73 72 2d 3e 70 53 6f 72 74 65 72 3b 0a   pCsr->pSorter;.
5310: 20 20 56 64 62 65 53 6f 72 74 65 72 49 74 65 72    VdbeSorterIter
5320: 20 2a 70 49 74 65 72 3b 0a 0a 20 20 70 49 74 65   *pIter;..  pIte
5330: 72 20 3d 20 26 70 53 6f 72 74 65 72 2d 3e 61 49  r = &pSorter->aI
5340: 74 65 72 5b 20 70 53 6f 72 74 65 72 2d 3e 61 54  ter[ pSorter->aT
5350: 72 65 65 5b 31 5d 20 5d 3b 0a 20 20 69 66 28 20  ree[1] ];.  if( 
5360: 73 71 6c 69 74 65 33 56 64 62 65 4d 65 6d 47 72  sqlite3VdbeMemGr
5370: 6f 77 28 70 4f 75 74 2c 20 70 49 74 65 72 2d 3e  ow(pOut, pIter->
5380: 6e 4b 65 79 2c 20 30 29 20 29 7b 0a 20 20 20 20  nKey, 0) ){.    
5390: 72 65 74 75 72 6e 20 53 51 4c 49 54 45 5f 4e 4f  return SQLITE_NO
53a0: 4d 45 4d 3b 0a 20 20 7d 0a 20 20 70 4f 75 74 2d  MEM;.  }.  pOut-
53b0: 3e 6e 20 3d 20 70 49 74 65 72 2d 3e 6e 4b 65 79  >n = pIter->nKey
53c0: 3b 0a 20 20 4d 65 6d 53 65 74 54 79 70 65 46 6c  ;.  MemSetTypeFl
53d0: 61 67 28 70 4f 75 74 2c 20 4d 45 4d 5f 42 6c 6f  ag(pOut, MEM_Blo
53e0: 62 29 3b 0a 20 20 6d 65 6d 63 70 79 28 70 4f 75  b);.  memcpy(pOu
53f0: 74 2d 3e 7a 2c 20 70 49 74 65 72 2d 3e 61 4b 65  t->z, pIter->aKe
5400: 79 2c 20 70 49 74 65 72 2d 3e 6e 4b 65 79 29 3b  y, pIter->nKey);
5410: 0a 0a 20 20 72 65 74 75 72 6e 20 53 51 4c 49 54  ..  return SQLIT
5420: 45 5f 4f 4b 3b 0a 7d 0a 0a                       E_OK;.}..