/ Hex Artifact Content
Login

Artifact 468d43c057063e54da4f1988b38b4f46d60e7790:


0000: 2f 2a 0a 2a 2a 20 32 30 31 31 20 4a 75 6c 79 20  /*.** 2011 July 
0010: 39 0a 2a 2a 0a 2a 2a 20 54 68 65 20 61 75 74 68  9.**.** The auth
0020: 6f 72 20 64 69 73 63 6c 61 69 6d 73 20 63 6f 70  or disclaims cop
0030: 79 72 69 67 68 74 20 74 6f 20 74 68 69 73 20 73  yright to this s
0040: 6f 75 72 63 65 20 63 6f 64 65 2e 20 20 49 6e 20  ource code.  In 
0050: 70 6c 61 63 65 20 6f 66 0a 2a 2a 20 61 20 6c 65  place of.** a le
0060: 67 61 6c 20 6e 6f 74 69 63 65 2c 20 68 65 72 65  gal notice, here
0070: 20 69 73 20 61 20 62 6c 65 73 73 69 6e 67 3a 0a   is a blessing:.
0080: 2a 2a 0a 2a 2a 20 20 20 20 4d 61 79 20 79 6f 75  **.**    May you
0090: 20 64 6f 20 67 6f 6f 64 20 61 6e 64 20 6e 6f 74   do good and not
00a0: 20 65 76 69 6c 2e 0a 2a 2a 20 20 20 20 4d 61 79   evil..**    May
00b0: 20 79 6f 75 20 66 69 6e 64 20 66 6f 72 67 69 76   you find forgiv
00c0: 65 6e 65 73 73 20 66 6f 72 20 79 6f 75 72 73 65  eness for yourse
00d0: 6c 66 20 61 6e 64 20 66 6f 72 67 69 76 65 20 6f  lf and forgive o
00e0: 74 68 65 72 73 2e 0a 2a 2a 20 20 20 20 4d 61 79  thers..**    May
00f0: 20 79 6f 75 20 73 68 61 72 65 20 66 72 65 65 6c   you share freel
0100: 79 2c 20 6e 65 76 65 72 20 74 61 6b 69 6e 67 20  y, never taking 
0110: 6d 6f 72 65 20 74 68 61 6e 20 79 6f 75 20 67 69  more than you gi
0120: 76 65 2e 0a 2a 2a 0a 2a 2a 2a 2a 2a 2a 2a 2a 2a  ve..**.*********
0130: 2a 2a 2a 2a 2a 2a 2a 2a 2a 2a 2a 2a 2a 2a 2a 2a  ****************
0140: 2a 2a 2a 2a 2a 2a 2a 2a 2a 2a 2a 2a 2a 2a 2a 2a  ****************
0150: 2a 2a 2a 2a 2a 2a 2a 2a 2a 2a 2a 2a 2a 2a 2a 2a  ****************
0160: 2a 2a 2a 2a 2a 2a 2a 2a 2a 2a 2a 2a 2a 2a 2a 2a  ****************
0170: 0a 2a 2a 20 54 68 69 73 20 66 69 6c 65 20 63 6f  .** This file co
0180: 6e 74 61 69 6e 73 20 63 6f 64 65 20 66 6f 72 20  ntains code for 
0190: 74 68 65 20 56 64 62 65 53 6f 72 74 65 72 20 6f  the VdbeSorter o
01a0: 62 6a 65 63 74 2c 20 75 73 65 64 20 69 6e 20 63  bject, used in c
01b0: 6f 6e 63 65 72 74 20 77 69 74 68 0a 2a 2a 20 61  oncert with.** a
01c0: 20 56 64 62 65 43 75 72 73 6f 72 20 74 6f 20 73   VdbeCursor to s
01d0: 6f 72 74 20 6c 61 72 67 65 20 6e 75 6d 62 65 72  ort large number
01e0: 73 20 6f 66 20 6b 65 79 73 20 28 61 73 20 6d 61  s of keys (as ma
01f0: 79 20 62 65 20 72 65 71 75 69 72 65 64 2c 20 66  y be required, f
0200: 6f 72 0a 2a 2a 20 65 78 61 6d 70 6c 65 2c 20 62  or.** example, b
0210: 79 20 43 52 45 41 54 45 20 49 4e 44 45 58 20 73  y CREATE INDEX s
0220: 74 61 74 65 6d 65 6e 74 73 20 6f 6e 20 74 61 62  tatements on tab
0230: 6c 65 73 20 74 6f 6f 20 6c 61 72 67 65 20 74 6f  les too large to
0240: 20 66 69 74 20 69 6e 20 6d 61 69 6e 0a 2a 2a 20   fit in main.** 
0250: 6d 65 6d 6f 72 79 29 2e 0a 2a 2f 0a 0a 23 69 6e  memory)..*/..#in
0260: 63 6c 75 64 65 20 22 73 71 6c 69 74 65 49 6e 74  clude "sqliteInt
0270: 2e 68 22 0a 23 69 6e 63 6c 75 64 65 20 22 76 64  .h".#include "vd
0280: 62 65 49 6e 74 2e 68 22 0a 0a 23 69 66 6e 64 65  beInt.h"..#ifnde
0290: 66 20 53 51 4c 49 54 45 5f 4f 4d 49 54 5f 4d 45  f SQLITE_OMIT_ME
02a0: 52 47 45 5f 53 4f 52 54 0a 0a 74 79 70 65 64 65  RGE_SORT..typede
02b0: 66 20 73 74 72 75 63 74 20 56 64 62 65 53 6f 72  f struct VdbeSor
02c0: 74 65 72 49 74 65 72 20 56 64 62 65 53 6f 72 74  terIter VdbeSort
02d0: 65 72 49 74 65 72 3b 0a 74 79 70 65 64 65 66 20  erIter;.typedef 
02e0: 73 74 72 75 63 74 20 53 6f 72 74 65 72 52 65 63  struct SorterRec
02f0: 6f 72 64 20 53 6f 72 74 65 72 52 65 63 6f 72 64  ord SorterRecord
0300: 3b 0a 0a 2f 2a 0a 2a 2a 20 4e 4f 54 45 53 20 4f  ;../*.** NOTES O
0310: 4e 20 44 41 54 41 20 53 54 52 55 43 54 55 52 45  N DATA STRUCTURE
0320: 20 55 53 45 44 20 46 4f 52 20 4e 2d 57 41 59 20   USED FOR N-WAY 
0330: 4d 45 52 47 45 53 3a 0a 2a 2a 0a 2a 2a 20 41 73  MERGES:.**.** As
0340: 20 6b 65 79 73 20 61 72 65 20 61 64 64 65 64 20   keys are added 
0350: 74 6f 20 74 68 65 20 73 6f 72 74 65 72 2c 20 74  to the sorter, t
0360: 68 65 79 20 61 72 65 20 77 72 69 74 74 65 6e 20  hey are written 
0370: 74 6f 20 64 69 73 6b 20 69 6e 20 61 20 73 65 72  to disk in a ser
0380: 69 65 73 0a 2a 2a 20 6f 66 20 73 6f 72 74 65 64  ies.** of sorted
0390: 20 70 61 63 6b 65 64 2d 6d 65 6d 6f 72 79 2d 61   packed-memory-a
03a0: 72 72 61 79 73 20 28 50 4d 41 73 29 2e 20 54 68  rrays (PMAs). Th
03b0: 65 20 73 69 7a 65 20 6f 66 20 65 61 63 68 20 50  e size of each P
03c0: 4d 41 20 69 73 20 72 6f 75 67 68 6c 79 0a 2a 2a  MA is roughly.**
03d0: 20 74 68 65 20 73 61 6d 65 20 61 73 20 74 68 65   the same as the
03e0: 20 63 61 63 68 65 2d 73 69 7a 65 20 61 6c 6c 6f   cache-size allo
03f0: 77 65 64 20 66 6f 72 20 74 65 6d 70 6f 72 61 72  wed for temporar
0400: 79 20 64 61 74 61 62 61 73 65 73 2e 20 49 6e 20  y databases. In 
0410: 6f 72 64 65 72 0a 2a 2a 20 74 6f 20 61 6c 6c 6f  order.** to allo
0420: 77 20 74 68 65 20 63 61 6c 6c 65 72 20 74 6f 20  w the caller to 
0430: 65 78 74 72 61 63 74 20 6b 65 79 73 20 66 72 6f  extract keys fro
0440: 6d 20 74 68 65 20 73 6f 72 74 65 72 20 69 6e 20  m the sorter in 
0450: 73 6f 72 74 65 64 20 6f 72 64 65 72 2c 0a 2a 2a  sorted order,.**
0460: 20 61 6c 6c 20 50 4d 41 73 20 63 75 72 72 65 6e   all PMAs curren
0470: 74 6c 79 20 73 74 6f 72 65 64 20 6f 6e 20 64 69  tly stored on di
0480: 73 6b 20 6d 75 73 74 20 62 65 20 6d 65 72 67 65  sk must be merge
0490: 64 20 74 6f 67 65 74 68 65 72 2e 20 54 68 69 73  d together. This
04a0: 20 63 6f 6d 6d 65 6e 74 0a 2a 2a 20 64 65 73 63   comment.** desc
04b0: 72 69 62 65 73 20 74 68 65 20 64 61 74 61 20 73  ribes the data s
04c0: 74 72 75 63 74 75 72 65 20 75 73 65 64 20 74 6f  tructure used to
04d0: 20 64 6f 20 73 6f 2e 20 54 68 65 20 73 74 72 75   do so. The stru
04e0: 63 74 75 72 65 20 73 75 70 70 6f 72 74 73 20 0a  cture supports .
04f0: 2a 2a 20 6d 65 72 67 69 6e 67 20 61 6e 79 20 6e  ** merging any n
0500: 75 6d 62 65 72 20 6f 66 20 61 72 72 61 79 73 20  umber of arrays 
0510: 69 6e 20 61 20 73 69 6e 67 6c 65 20 70 61 73 73  in a single pass
0520: 20 77 69 74 68 20 6e 6f 20 72 65 64 75 6e 64 61   with no redunda
0530: 6e 74 20 63 6f 6d 70 61 72 69 73 6f 6e 20 0a 2a  nt comparison .*
0540: 2a 20 6f 70 65 72 61 74 69 6f 6e 73 2e 0a 2a 2a  * operations..**
0550: 0a 2a 2a 20 54 68 65 20 61 49 74 65 72 5b 5d 20  .** The aIter[] 
0560: 61 72 72 61 79 20 63 6f 6e 74 61 69 6e 73 20 61  array contains a
0570: 6e 20 69 74 65 72 61 74 6f 72 20 66 6f 72 20 65  n iterator for e
0580: 61 63 68 20 6f 66 20 74 68 65 20 50 4d 41 73 20  ach of the PMAs 
0590: 62 65 69 6e 67 20 6d 65 72 67 65 64 2e 0a 2a 2a  being merged..**
05a0: 20 41 6e 20 61 49 74 65 72 5b 5d 20 69 74 65 72   An aIter[] iter
05b0: 61 74 6f 72 20 65 69 74 68 65 72 20 70 6f 69 6e  ator either poin
05c0: 74 73 20 74 6f 20 61 20 76 61 6c 69 64 20 6b 65  ts to a valid ke
05d0: 79 20 6f 72 20 65 6c 73 65 20 69 73 20 61 74 20  y or else is at 
05e0: 45 4f 46 2e 20 46 6f 72 20 0a 2a 2a 20 74 68 65  EOF. For .** the
05f0: 20 70 75 72 70 6f 73 65 73 20 6f 66 20 74 68 65   purposes of the
0600: 20 70 61 72 61 67 72 61 70 68 73 20 62 65 6c 6f   paragraphs belo
0610: 77 2c 20 77 65 20 61 73 73 75 6d 65 20 74 68 61  w, we assume tha
0620: 74 20 74 68 65 20 61 72 72 61 79 20 69 73 20 61  t the array is a
0630: 63 74 75 61 6c 6c 79 20 0a 2a 2a 20 4e 20 65 6c  ctually .** N el
0640: 65 6d 65 6e 74 73 20 69 6e 20 73 69 7a 65 2c 20  ements in size, 
0650: 77 68 65 72 65 20 4e 20 69 73 20 74 68 65 20 73  where N is the s
0660: 6d 61 6c 6c 65 73 74 20 70 6f 77 65 72 20 6f 66  mallest power of
0670: 20 32 20 67 72 65 61 74 65 72 20 74 6f 20 6f 72   2 greater to or
0680: 20 65 71 75 61 6c 20 0a 2a 2a 20 74 6f 20 74 68   equal .** to th
0690: 65 20 6e 75 6d 62 65 72 20 6f 66 20 69 74 65 72  e number of iter
06a0: 61 74 6f 72 73 20 62 65 69 6e 67 20 6d 65 72 67  ators being merg
06b0: 65 64 2e 20 54 68 65 20 65 78 74 72 61 20 61 49  ed. The extra aI
06c0: 74 65 72 5b 5d 20 65 6c 65 6d 65 6e 74 73 20 61  ter[] elements a
06d0: 72 65 20 0a 2a 2a 20 74 72 65 61 74 65 64 20 61  re .** treated a
06e0: 73 20 69 66 20 74 68 65 79 20 61 72 65 20 65 6d  s if they are em
06f0: 70 74 79 20 28 61 6c 77 61 79 73 20 61 74 20 45  pty (always at E
0700: 4f 46 29 2e 0a 2a 2a 0a 2a 2a 20 54 68 65 20 61  OF)..**.** The a
0710: 54 72 65 65 5b 5d 20 61 72 72 61 79 20 69 73 20  Tree[] array is 
0720: 61 6c 73 6f 20 4e 20 65 6c 65 6d 65 6e 74 73 20  also N elements 
0730: 69 6e 20 73 69 7a 65 2e 20 54 68 65 20 76 61 6c  in size. The val
0740: 75 65 20 6f 66 20 4e 20 69 73 20 73 74 6f 72 65  ue of N is store
0750: 64 20 69 6e 0a 2a 2a 20 74 68 65 20 56 64 62 65  d in.** the Vdbe
0760: 53 6f 72 74 65 72 2e 6e 54 72 65 65 20 76 61 72  Sorter.nTree var
0770: 69 61 62 6c 65 2e 0a 2a 2a 0a 2a 2a 20 54 68 65  iable..**.** The
0780: 20 66 69 6e 61 6c 20 28 4e 2f 32 29 20 65 6c 65   final (N/2) ele
0790: 6d 65 6e 74 73 20 6f 66 20 61 54 72 65 65 5b 5d  ments of aTree[]
07a0: 20 63 6f 6e 74 61 69 6e 20 74 68 65 20 72 65 73   contain the res
07b0: 75 6c 74 73 20 6f 66 20 63 6f 6d 70 61 72 69 6e  ults of comparin
07c0: 67 0a 2a 2a 20 70 61 69 72 73 20 6f 66 20 69 74  g.** pairs of it
07d0: 65 72 61 74 6f 72 20 6b 65 79 73 20 74 6f 67 65  erator keys toge
07e0: 74 68 65 72 2e 20 45 6c 65 6d 65 6e 74 20 69 20  ther. Element i 
07f0: 63 6f 6e 74 61 69 6e 73 20 74 68 65 20 72 65 73  contains the res
0800: 75 6c 74 20 6f 66 20 0a 2a 2a 20 63 6f 6d 70 61  ult of .** compa
0810: 72 69 6e 67 20 61 49 74 65 72 5b 32 2a 69 2d 4e  ring aIter[2*i-N
0820: 5d 20 61 6e 64 20 61 49 74 65 72 5b 32 2a 69 2d  ] and aIter[2*i-
0830: 4e 2b 31 5d 2e 20 57 68 69 63 68 65 76 65 72 20  N+1]. Whichever 
0840: 6b 65 79 20 69 73 20 73 6d 61 6c 6c 65 72 2c 20  key is smaller, 
0850: 74 68 65 0a 2a 2a 20 61 54 72 65 65 20 65 6c 65  the.** aTree ele
0860: 6d 65 6e 74 20 69 73 20 73 65 74 20 74 6f 20 74  ment is set to t
0870: 68 65 20 69 6e 64 65 78 20 6f 66 20 69 74 2e 20  he index of it. 
0880: 0a 2a 2a 0a 2a 2a 20 46 6f 72 20 74 68 65 20 70  .**.** For the p
0890: 75 72 70 6f 73 65 73 20 6f 66 20 74 68 69 73 20  urposes of this 
08a0: 63 6f 6d 70 61 72 69 73 6f 6e 2c 20 45 4f 46 20  comparison, EOF 
08b0: 69 73 20 63 6f 6e 73 69 64 65 72 65 64 20 67 72  is considered gr
08c0: 65 61 74 65 72 20 74 68 61 6e 20 61 6e 79 0a 2a  eater than any.*
08d0: 2a 20 6f 74 68 65 72 20 6b 65 79 20 76 61 6c 75  * other key valu
08e0: 65 2e 20 49 66 20 74 68 65 20 6b 65 79 73 20 61  e. If the keys a
08f0: 72 65 20 65 71 75 61 6c 20 28 6f 6e 6c 79 20 70  re equal (only p
0900: 6f 73 73 69 62 6c 65 20 77 69 74 68 20 74 77 6f  ossible with two
0910: 20 45 4f 46 0a 2a 2a 20 76 61 6c 75 65 73 29 2c   EOF.** values),
0920: 20 69 74 20 64 6f 65 73 6e 27 74 20 6d 61 74 74   it doesn't matt
0930: 65 72 20 77 68 69 63 68 20 69 6e 64 65 78 20 69  er which index i
0940: 73 20 73 74 6f 72 65 64 2e 0a 2a 2a 0a 2a 2a 20  s stored..**.** 
0950: 54 68 65 20 28 4e 2f 34 29 20 65 6c 65 6d 65 6e  The (N/4) elemen
0960: 74 73 20 6f 66 20 61 54 72 65 65 5b 5d 20 74 68  ts of aTree[] th
0970: 61 74 20 70 72 65 63 65 65 64 20 74 68 65 20 66  at preceed the f
0980: 69 6e 61 6c 20 28 4e 2f 32 29 20 64 65 73 63 72  inal (N/2) descr
0990: 69 62 65 64 20 0a 2a 2a 20 61 62 6f 76 65 20 63  ibed .** above c
09a0: 6f 6e 74 61 69 6e 73 20 74 68 65 20 69 6e 64 65  ontains the inde
09b0: 78 20 6f 66 20 74 68 65 20 73 6d 61 6c 6c 65 73  x of the smalles
09c0: 74 20 6f 66 20 65 61 63 68 20 62 6c 6f 63 6b 20  t of each block 
09d0: 6f 66 20 34 20 69 74 65 72 61 74 6f 72 73 2e 0a  of 4 iterators..
09e0: 2a 2a 20 41 6e 64 20 73 6f 20 6f 6e 2e 20 53 6f  ** And so on. So
09f0: 20 74 68 61 74 20 61 54 72 65 65 5b 31 5d 20 63   that aTree[1] c
0a00: 6f 6e 74 61 69 6e 73 20 74 68 65 20 69 6e 64 65  ontains the inde
0a10: 78 20 6f 66 20 74 68 65 20 69 74 65 72 61 74 6f  x of the iterato
0a20: 72 20 74 68 61 74 20 0a 2a 2a 20 63 75 72 72 65  r that .** curre
0a30: 6e 74 6c 79 20 70 6f 69 6e 74 73 20 74 6f 20 74  ntly points to t
0a40: 68 65 20 73 6d 61 6c 6c 65 73 74 20 6b 65 79 20  he smallest key 
0a50: 76 61 6c 75 65 2e 20 61 54 72 65 65 5b 30 5d 20  value. aTree[0] 
0a60: 69 73 20 75 6e 75 73 65 64 2e 0a 2a 2a 0a 2a 2a  is unused..**.**
0a70: 20 45 78 61 6d 70 6c 65 3a 0a 2a 2a 0a 2a 2a 20   Example:.**.** 
0a80: 20 20 20 20 61 49 74 65 72 5b 30 5d 20 2d 3e 20      aIter[0] -> 
0a90: 42 61 6e 61 6e 61 0a 2a 2a 20 20 20 20 20 61 49  Banana.**     aI
0aa0: 74 65 72 5b 31 5d 20 2d 3e 20 46 65 69 6a 6f 61  ter[1] -> Feijoa
0ab0: 0a 2a 2a 20 20 20 20 20 61 49 74 65 72 5b 32 5d  .**     aIter[2]
0ac0: 20 2d 3e 20 45 6c 64 65 72 62 65 72 72 79 0a 2a   -> Elderberry.*
0ad0: 2a 20 20 20 20 20 61 49 74 65 72 5b 33 5d 20 2d  *     aIter[3] -
0ae0: 3e 20 43 75 72 72 61 6e 74 0a 2a 2a 20 20 20 20  > Currant.**    
0af0: 20 61 49 74 65 72 5b 34 5d 20 2d 3e 20 47 72 61   aIter[4] -> Gra
0b00: 70 65 66 72 75 69 74 0a 2a 2a 20 20 20 20 20 61  pefruit.**     a
0b10: 49 74 65 72 5b 35 5d 20 2d 3e 20 41 70 70 6c 65  Iter[5] -> Apple
0b20: 0a 2a 2a 20 20 20 20 20 61 49 74 65 72 5b 36 5d  .**     aIter[6]
0b30: 20 2d 3e 20 44 75 72 69 61 6e 0a 2a 2a 20 20 20   -> Durian.**   
0b40: 20 20 61 49 74 65 72 5b 37 5d 20 2d 3e 20 45 4f    aIter[7] -> EO
0b50: 46 0a 2a 2a 0a 2a 2a 20 20 20 20 20 61 54 72 65  F.**.**     aTre
0b60: 65 5b 5d 20 3d 20 7b 20 58 2c 20 35 20 20 20 30  e[] = { X, 5   0
0b70: 2c 20 35 20 20 20 20 30 2c 20 33 2c 20 35 2c 20  , 5    0, 3, 5, 
0b80: 36 20 7d 0a 2a 2a 0a 2a 2a 20 54 68 65 20 63 75  6 }.**.** The cu
0b90: 72 72 65 6e 74 20 65 6c 65 6d 65 6e 74 20 69 73  rrent element is
0ba0: 20 22 41 70 70 6c 65 22 20 28 74 68 65 20 76 61   "Apple" (the va
0bb0: 6c 75 65 20 6f 66 20 74 68 65 20 6b 65 79 20 69  lue of the key i
0bc0: 6e 64 69 63 61 74 65 64 20 62 79 20 0a 2a 2a 20  ndicated by .** 
0bd0: 69 74 65 72 61 74 6f 72 20 35 29 2e 20 57 68 65  iterator 5). Whe
0be0: 6e 20 74 68 65 20 4e 65 78 74 28 29 20 6f 70 65  n the Next() ope
0bf0: 72 61 74 69 6f 6e 20 69 73 20 69 6e 76 6f 6b 65  ration is invoke
0c00: 64 2c 20 69 74 65 72 61 74 6f 72 20 35 20 77 69  d, iterator 5 wi
0c10: 6c 6c 0a 2a 2a 20 62 65 20 61 64 76 61 6e 63 65  ll.** be advance
0c20: 64 20 74 6f 20 74 68 65 20 6e 65 78 74 20 6b 65  d to the next ke
0c30: 79 20 69 6e 20 69 74 73 20 73 65 67 6d 65 6e 74  y in its segment
0c40: 2e 20 53 61 79 20 74 68 65 20 6e 65 78 74 20 6b  . Say the next k
0c50: 65 79 20 69 73 0a 2a 2a 20 22 45 67 67 70 6c 61  ey is.** "Eggpla
0c60: 6e 74 22 3a 0a 2a 2a 0a 2a 2a 20 20 20 20 20 61  nt":.**.**     a
0c70: 49 74 65 72 5b 35 5d 20 2d 3e 20 45 67 67 70 6c  Iter[5] -> Eggpl
0c80: 61 6e 74 0a 2a 2a 0a 2a 2a 20 54 68 65 20 63 6f  ant.**.** The co
0c90: 6e 74 65 6e 74 73 20 6f 66 20 61 54 72 65 65 5b  ntents of aTree[
0ca0: 5d 20 61 72 65 20 75 70 64 61 74 65 64 20 66 69  ] are updated fi
0cb0: 72 73 74 20 62 79 20 63 6f 6d 70 61 72 69 6e 67  rst by comparing
0cc0: 20 74 68 65 20 6e 65 77 20 69 74 65 72 61 74 6f   the new iterato
0cd0: 72 0a 2a 2a 20 35 20 6b 65 79 20 74 6f 20 74 68  r.** 5 key to th
0ce0: 65 20 63 75 72 72 65 6e 74 20 6b 65 79 20 6f 66  e current key of
0cf0: 20 69 74 65 72 61 74 6f 72 20 34 20 28 73 74 69   iterator 4 (sti
0d00: 6c 6c 20 22 47 72 61 70 65 66 72 75 69 74 22 29  ll "Grapefruit")
0d10: 2e 20 54 68 65 20 69 74 65 72 61 74 6f 72 0a 2a  . The iterator.*
0d20: 2a 20 35 20 76 61 6c 75 65 20 69 73 20 73 74 69  * 5 value is sti
0d30: 6c 6c 20 73 6d 61 6c 6c 65 72 2c 20 73 6f 20 61  ll smaller, so a
0d40: 54 72 65 65 5b 36 5d 20 69 73 20 73 65 74 20 74  Tree[6] is set t
0d50: 6f 20 35 2e 20 41 6e 64 20 73 6f 20 6f 6e 20 75  o 5. And so on u
0d60: 70 20 74 68 65 20 74 72 65 65 2e 0a 2a 2a 20 54  p the tree..** T
0d70: 68 65 20 76 61 6c 75 65 20 6f 66 20 69 74 65 72  he value of iter
0d80: 61 74 6f 72 20 36 20 2d 20 22 44 75 72 69 61 6e  ator 6 - "Durian
0d90: 22 20 2d 20 69 73 20 6e 6f 77 20 73 6d 61 6c 6c  " - is now small
0da0: 65 72 20 74 68 61 6e 20 74 68 61 74 20 6f 66 20  er than that of 
0db0: 69 74 65 72 61 74 6f 72 0a 2a 2a 20 35 2c 20 73  iterator.** 5, s
0dc0: 6f 20 61 54 72 65 65 5b 33 5d 20 69 73 20 73 65  o aTree[3] is se
0dd0: 74 20 74 6f 20 36 2e 20 4b 65 79 20 30 20 69 73  t to 6. Key 0 is
0de0: 20 73 6d 61 6c 6c 65 72 20 74 68 61 6e 20 6b 65   smaller than ke
0df0: 79 20 36 20 28 42 61 6e 61 6e 61 3c 44 75 72 69  y 6 (Banana<Duri
0e00: 61 6e 29 2c 0a 2a 2a 20 73 6f 20 74 68 65 20 76  an),.** so the v
0e10: 61 6c 75 65 20 77 72 69 74 74 65 6e 20 69 6e 74  alue written int
0e20: 6f 20 65 6c 65 6d 65 6e 74 20 31 20 6f 66 20 74  o element 1 of t
0e30: 68 65 20 61 72 72 61 79 20 69 73 20 30 2e 20 41  he array is 0. A
0e40: 73 20 66 6f 6c 6c 6f 77 73 3a 0a 2a 2a 0a 2a 2a  s follows:.**.**
0e50: 20 20 20 20 20 61 54 72 65 65 5b 5d 20 3d 20 7b       aTree[] = {
0e60: 20 58 2c 20 30 20 20 20 30 2c 20 36 20 20 20 20   X, 0   0, 6    
0e70: 30 2c 20 33 2c 20 35 2c 20 36 20 7d 0a 2a 2a 0a  0, 3, 5, 6 }.**.
0e80: 2a 2a 20 49 6e 20 6f 74 68 65 72 20 77 6f 72 64  ** In other word
0e90: 73 2c 20 65 61 63 68 20 74 69 6d 65 20 77 65 20  s, each time we 
0ea0: 61 64 76 61 6e 63 65 20 74 6f 20 74 68 65 20 6e  advance to the n
0eb0: 65 78 74 20 73 6f 72 74 65 72 20 65 6c 65 6d 65  ext sorter eleme
0ec0: 6e 74 2c 20 6c 6f 67 32 28 4e 29 0a 2a 2a 20 6b  nt, log2(N).** k
0ed0: 65 79 20 63 6f 6d 70 61 72 69 73 6f 6e 20 6f 70  ey comparison op
0ee0: 65 72 61 74 69 6f 6e 73 20 61 72 65 20 72 65 71  erations are req
0ef0: 75 69 72 65 64 2c 20 77 68 65 72 65 20 4e 20 69  uired, where N i
0f00: 73 20 74 68 65 20 6e 75 6d 62 65 72 20 6f 66 20  s the number of 
0f10: 73 65 67 6d 65 6e 74 73 0a 2a 2a 20 62 65 69 6e  segments.** bein
0f20: 67 20 6d 65 72 67 65 64 20 28 72 6f 75 6e 64 65  g merged (rounde
0f30: 64 20 75 70 20 74 6f 20 74 68 65 20 6e 65 78 74  d up to the next
0f40: 20 70 6f 77 65 72 20 6f 66 20 32 29 2e 0a 2a 2f   power of 2)..*/
0f50: 0a 73 74 72 75 63 74 20 56 64 62 65 53 6f 72 74  .struct VdbeSort
0f60: 65 72 20 7b 0a 20 20 69 6e 74 20 6e 49 6e 4d 65  er {.  int nInMe
0f70: 6d 6f 72 79 3b 20 20 20 20 20 20 20 20 20 20 20  mory;           
0f80: 20 20 20 20 20 20 20 2f 2a 20 43 75 72 72 65 6e         /* Curren
0f90: 74 20 73 69 7a 65 20 6f 66 20 70 52 65 63 6f 72  t size of pRecor
0fa0: 64 20 6c 69 73 74 20 61 73 20 50 4d 41 20 2a 2f  d list as PMA */
0fb0: 0a 20 20 69 6e 74 20 6e 54 72 65 65 3b 20 20 20  .  int nTree;   
0fc0: 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20                  
0fd0: 20 20 20 2f 2a 20 55 73 65 64 20 73 69 7a 65 20     /* Used size 
0fe0: 6f 66 20 61 54 72 65 65 2f 61 49 74 65 72 20 28  of aTree/aIter (
0ff0: 70 6f 77 65 72 20 6f 66 20 32 29 20 2a 2f 0a 20  power of 2) */. 
1000: 20 56 64 62 65 53 6f 72 74 65 72 49 74 65 72 20   VdbeSorterIter 
1010: 2a 61 49 74 65 72 3b 20 20 20 20 20 20 20 20 20  *aIter;         
1020: 20 2f 2a 20 41 72 72 61 79 20 6f 66 20 69 74 65   /* Array of ite
1030: 72 61 74 6f 72 73 20 74 6f 20 6d 65 72 67 65 20  rators to merge 
1040: 2a 2f 0a 20 20 69 6e 74 20 2a 61 54 72 65 65 3b  */.  int *aTree;
1050: 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20                  
1060: 20 20 20 20 20 2f 2a 20 43 75 72 72 65 6e 74 20       /* Current 
1070: 73 74 61 74 65 20 6f 66 20 69 6e 63 72 65 6d 65  state of increme
1080: 6e 74 61 6c 20 6d 65 72 67 65 20 2a 2f 0a 20 20  ntal merge */.  
1090: 69 36 34 20 69 57 72 69 74 65 4f 66 66 3b 20 20  i64 iWriteOff;  
10a0: 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20                  
10b0: 2f 2a 20 43 75 72 72 65 6e 74 20 77 72 69 74 65  /* Current write
10c0: 20 6f 66 66 73 65 74 20 77 69 74 68 69 6e 20 66   offset within f
10d0: 69 6c 65 20 70 54 65 6d 70 31 20 2a 2f 0a 20 20  ile pTemp1 */.  
10e0: 69 36 34 20 69 52 65 61 64 4f 66 66 3b 20 20 20  i64 iReadOff;   
10f0: 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20                  
1100: 2f 2a 20 43 75 72 72 65 6e 74 20 72 65 61 64 20  /* Current read 
1110: 6f 66 66 73 65 74 20 77 69 74 68 69 6e 20 66 69  offset within fi
1120: 6c 65 20 70 54 65 6d 70 31 20 2a 2f 0a 20 20 73  le pTemp1 */.  s
1130: 71 6c 69 74 65 33 5f 66 69 6c 65 20 2a 70 54 65  qlite3_file *pTe
1140: 6d 70 31 3b 20 20 20 20 20 20 20 20 20 20 20 2f  mp1;           /
1150: 2a 20 50 4d 41 20 66 69 6c 65 20 31 20 2a 2f 0a  * PMA file 1 */.
1160: 20 20 69 6e 74 20 6e 50 4d 41 3b 20 20 20 20 20    int nPMA;     
1170: 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20                  
1180: 20 20 2f 2a 20 4e 75 6d 62 65 72 20 6f 66 20 50    /* Number of P
1190: 4d 41 73 20 73 74 6f 72 65 64 20 69 6e 20 70 54  MAs stored in pT
11a0: 65 6d 70 31 20 2a 2f 0a 20 20 53 6f 72 74 65 72  emp1 */.  Sorter
11b0: 52 65 63 6f 72 64 20 2a 70 52 65 63 6f 72 64 3b  Record *pRecord;
11c0: 20 20 20 20 20 20 20 20 20 20 2f 2a 20 48 65 61            /* Hea
11d0: 64 20 6f 66 20 69 6e 2d 6d 65 6d 6f 72 79 20 72  d of in-memory r
11e0: 65 63 6f 72 64 20 6c 69 73 74 20 2a 2f 0a 20 20  ecord list */.  
11f0: 69 6e 74 20 6d 6e 50 6d 61 53 69 7a 65 3b 20 20  int mnPmaSize;  
1200: 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20                  
1210: 2f 2a 20 4d 69 6e 69 6d 75 6d 20 50 4d 41 20 73  /* Minimum PMA s
1220: 69 7a 65 2c 20 69 6e 20 62 79 74 65 73 20 2a 2f  ize, in bytes */
1230: 0a 20 20 69 6e 74 20 6d 78 50 6d 61 53 69 7a 65  .  int mxPmaSize
1240: 3b 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20  ;               
1250: 20 20 20 2f 2a 20 4d 61 78 69 6d 75 6d 20 50 4d     /* Maximum PM
1260: 41 20 73 69 7a 65 2c 20 69 6e 20 62 79 74 65 73  A size, in bytes
1270: 2e 20 20 30 3d 3d 6e 6f 20 6c 69 6d 69 74 20 2a  .  0==no limit *
1280: 2f 0a 20 20 55 6e 70 61 63 6b 65 64 52 65 63 6f  /.  UnpackedReco
1290: 72 64 20 2a 70 55 6e 70 61 63 6b 65 64 3b 20 20  rd *pUnpacked;  
12a0: 20 20 20 20 2f 2a 20 55 73 65 64 20 74 6f 20 75      /* Used to u
12b0: 6e 70 61 63 6b 20 6b 65 79 73 20 2a 2f 0a 7d 3b  npack keys */.};
12c0: 0a 0a 2f 2a 0a 2a 2a 20 54 68 65 20 66 6f 6c 6c  ../*.** The foll
12d0: 6f 77 69 6e 67 20 74 79 70 65 20 69 73 20 61 6e  owing type is an
12e0: 20 69 74 65 72 61 74 6f 72 20 66 6f 72 20 61 20   iterator for a 
12f0: 50 4d 41 2e 20 49 74 20 63 61 63 68 65 73 20 74  PMA. It caches t
1300: 68 65 20 63 75 72 72 65 6e 74 20 6b 65 79 20 69  he current key i
1310: 6e 20 0a 2a 2a 20 76 61 72 69 61 62 6c 65 73 20  n .** variables 
1320: 6e 4b 65 79 2f 61 4b 65 79 2e 20 49 66 20 74 68  nKey/aKey. If th
1330: 65 20 69 74 65 72 61 74 6f 72 20 69 73 20 61 74  e iterator is at
1340: 20 45 4f 46 2c 20 70 46 69 6c 65 3d 3d 30 2e 0a   EOF, pFile==0..
1350: 2a 2f 0a 73 74 72 75 63 74 20 56 64 62 65 53 6f  */.struct VdbeSo
1360: 72 74 65 72 49 74 65 72 20 7b 0a 20 20 69 36 34  rterIter {.  i64
1370: 20 69 52 65 61 64 4f 66 66 3b 20 20 20 20 20 20   iReadOff;      
1380: 20 20 20 20 20 20 20 20 20 20 20 20 20 2f 2a 20               /* 
1390: 43 75 72 72 65 6e 74 20 72 65 61 64 20 6f 66 66  Current read off
13a0: 73 65 74 20 2a 2f 0a 20 20 69 36 34 20 69 45 6f  set */.  i64 iEo
13b0: 66 3b 20 20 20 20 20 20 20 20 20 20 20 20 20 20  f;              
13c0: 20 20 20 20 20 20 20 20 20 2f 2a 20 31 20 62 79           /* 1 by
13d0: 74 65 20 70 61 73 74 20 45 4f 46 20 66 6f 72 20  te past EOF for 
13e0: 74 68 69 73 20 69 74 65 72 61 74 6f 72 20 2a 2f  this iterator */
13f0: 0a 20 20 73 71 6c 69 74 65 33 5f 66 69 6c 65 20  .  sqlite3_file 
1400: 2a 70 46 69 6c 65 3b 20 20 20 20 20 20 20 20 20  *pFile;         
1410: 20 20 20 2f 2a 20 46 69 6c 65 20 69 74 65 72 61     /* File itera
1420: 74 6f 72 20 69 73 20 72 65 61 64 69 6e 67 20 66  tor is reading f
1430: 72 6f 6d 20 2a 2f 0a 20 20 69 6e 74 20 6e 41 6c  rom */.  int nAl
1440: 6c 6f 63 3b 20 20 20 20 20 20 20 20 20 20 20 20  loc;            
1450: 20 20 20 20 20 20 20 20 20 2f 2a 20 42 79 74 65           /* Byte
1460: 73 20 6f 66 20 73 70 61 63 65 20 61 74 20 61 41  s of space at aA
1470: 6c 6c 6f 63 20 2a 2f 0a 20 20 75 38 20 2a 61 41  lloc */.  u8 *aA
1480: 6c 6c 6f 63 3b 20 20 20 20 20 20 20 20 20 20 20  lloc;           
1490: 20 20 20 20 20 20 20 20 20 20 2f 2a 20 41 6c 6c            /* All
14a0: 6f 63 61 74 65 64 20 73 70 61 63 65 20 2a 2f 0a  ocated space */.
14b0: 20 20 69 6e 74 20 6e 4b 65 79 3b 20 20 20 20 20    int nKey;     
14c0: 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20                  
14d0: 20 20 2f 2a 20 4e 75 6d 62 65 72 20 6f 66 20 62    /* Number of b
14e0: 79 74 65 73 20 69 6e 20 6b 65 79 20 2a 2f 0a 20  ytes in key */. 
14f0: 20 75 38 20 2a 61 4b 65 79 3b 20 20 20 20 20 20   u8 *aKey;      
1500: 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20                  
1510: 20 2f 2a 20 50 6f 69 6e 74 65 72 20 74 6f 20 63   /* Pointer to c
1520: 75 72 72 65 6e 74 20 6b 65 79 20 2a 2f 0a 7d 3b  urrent key */.};
1530: 0a 0a 2f 2a 0a 2a 2a 20 41 20 73 74 72 75 63 74  ../*.** A struct
1540: 75 72 65 20 74 6f 20 73 74 6f 72 65 20 61 20 73  ure to store a s
1550: 69 6e 67 6c 65 20 72 65 63 6f 72 64 2e 20 41 6c  ingle record. Al
1560: 6c 20 69 6e 2d 6d 65 6d 6f 72 79 20 72 65 63 6f  l in-memory reco
1570: 72 64 73 20 61 72 65 20 63 6f 6e 6e 65 63 74 65  rds are connecte
1580: 64 0a 2a 2a 20 74 6f 67 65 74 68 65 72 20 69 6e  d.** together in
1590: 74 6f 20 61 20 6c 69 6e 6b 65 64 20 6c 69 73 74  to a linked list
15a0: 20 68 65 61 64 65 64 20 61 74 20 56 64 62 65 53   headed at VdbeS
15b0: 6f 72 74 65 72 2e 70 52 65 63 6f 72 64 20 75 73  orter.pRecord us
15c0: 69 6e 67 20 74 68 65 20 0a 2a 2a 20 53 6f 72 74  ing the .** Sort
15d0: 65 72 52 65 63 6f 72 64 2e 70 4e 65 78 74 20 70  erRecord.pNext p
15e0: 6f 69 6e 74 65 72 2e 0a 2a 2f 0a 73 74 72 75 63  ointer..*/.struc
15f0: 74 20 53 6f 72 74 65 72 52 65 63 6f 72 64 20 7b  t SorterRecord {
1600: 0a 20 20 76 6f 69 64 20 2a 70 56 61 6c 3b 0a 20  .  void *pVal;. 
1610: 20 69 6e 74 20 6e 56 61 6c 3b 0a 20 20 53 6f 72   int nVal;.  Sor
1620: 74 65 72 52 65 63 6f 72 64 20 2a 70 4e 65 78 74  terRecord *pNext
1630: 3b 0a 7d 3b 0a 0a 2f 2a 20 4d 69 6e 69 6d 75 6d  ;.};../* Minimum
1640: 20 61 6c 6c 6f 77 61 62 6c 65 20 76 61 6c 75 65   allowable value
1650: 20 66 6f 72 20 74 68 65 20 56 64 62 65 53 6f 72   for the VdbeSor
1660: 74 65 72 2e 6e 57 6f 72 6b 69 6e 67 20 76 61 72  ter.nWorking var
1670: 69 61 62 6c 65 20 2a 2f 0a 23 64 65 66 69 6e 65  iable */.#define
1680: 20 53 4f 52 54 45 52 5f 4d 49 4e 5f 57 4f 52 4b   SORTER_MIN_WORK
1690: 49 4e 47 20 31 30 0a 0a 2f 2a 20 4d 61 78 69 6d  ING 10../* Maxim
16a0: 75 6d 20 6e 75 6d 62 65 72 20 6f 66 20 73 65 67  um number of seg
16b0: 6d 65 6e 74 73 20 74 6f 20 6d 65 72 67 65 20 69  ments to merge i
16c0: 6e 20 61 20 73 69 6e 67 6c 65 20 70 61 73 73 2e  n a single pass.
16d0: 20 2a 2f 0a 23 64 65 66 69 6e 65 20 53 4f 52 54   */.#define SORT
16e0: 45 52 5f 4d 41 58 5f 4d 45 52 47 45 5f 43 4f 55  ER_MAX_MERGE_COU
16f0: 4e 54 20 31 36 0a 0a 2f 2a 0a 2a 2a 20 46 72 65  NT 16../*.** Fre
1700: 65 20 61 6c 6c 20 6d 65 6d 6f 72 79 20 62 65 6c  e all memory bel
1710: 6f 6e 67 69 6e 67 20 74 6f 20 74 68 65 20 56 64  onging to the Vd
1720: 62 65 53 6f 72 74 65 72 49 74 65 72 20 6f 62 6a  beSorterIter obj
1730: 65 63 74 20 70 61 73 73 65 64 20 61 73 20 74 68  ect passed as th
1740: 65 20 73 65 63 6f 6e 64 0a 2a 2a 20 61 72 67 75  e second.** argu
1750: 6d 65 6e 74 2e 20 41 6c 6c 20 73 74 72 75 63 74  ment. All struct
1760: 75 72 65 20 66 69 65 6c 64 73 20 61 72 65 20 73  ure fields are s
1770: 65 74 20 74 6f 20 7a 65 72 6f 20 62 65 66 6f 72  et to zero befor
1780: 65 20 72 65 74 75 72 6e 69 6e 67 2e 0a 2a 2f 0a  e returning..*/.
1790: 73 74 61 74 69 63 20 76 6f 69 64 20 76 64 62 65  static void vdbe
17a0: 53 6f 72 74 65 72 49 74 65 72 5a 65 72 6f 28 73  SorterIterZero(s
17b0: 71 6c 69 74 65 33 20 2a 64 62 2c 20 56 64 62 65  qlite3 *db, Vdbe
17c0: 53 6f 72 74 65 72 49 74 65 72 20 2a 70 49 74 65  SorterIter *pIte
17d0: 72 29 7b 0a 20 20 73 71 6c 69 74 65 33 44 62 46  r){.  sqlite3DbF
17e0: 72 65 65 28 64 62 2c 20 70 49 74 65 72 2d 3e 61  ree(db, pIter->a
17f0: 41 6c 6c 6f 63 29 3b 0a 20 20 6d 65 6d 73 65 74  Alloc);.  memset
1800: 28 70 49 74 65 72 2c 20 30 2c 20 73 69 7a 65 6f  (pIter, 0, sizeo
1810: 66 28 56 64 62 65 53 6f 72 74 65 72 49 74 65 72  f(VdbeSorterIter
1820: 29 29 3b 0a 7d 0a 0a 2f 2a 0a 2a 2a 20 41 64 76  ));.}../*.** Adv
1830: 61 6e 63 65 20 69 74 65 72 61 74 6f 72 20 70 49  ance iterator pI
1840: 74 65 72 20 74 6f 20 74 68 65 20 6e 65 78 74 20  ter to the next 
1850: 6b 65 79 20 69 6e 20 69 74 73 20 50 4d 41 2e 20  key in its PMA. 
1860: 52 65 74 75 72 6e 20 53 51 4c 49 54 45 5f 4f 4b  Return SQLITE_OK
1870: 20 69 66 0a 2a 2a 20 6e 6f 20 65 72 72 6f 72 20   if.** no error 
1880: 6f 63 63 75 72 73 2c 20 6f 72 20 61 6e 20 53 51  occurs, or an SQ
1890: 4c 69 74 65 20 65 72 72 6f 72 20 63 6f 64 65 20  Lite error code 
18a0: 69 66 20 6f 6e 65 20 64 6f 65 73 2e 0a 2a 2f 0a  if one does..*/.
18b0: 73 74 61 74 69 63 20 69 6e 74 20 76 64 62 65 53  static int vdbeS
18c0: 6f 72 74 65 72 49 74 65 72 4e 65 78 74 28 0a 20  orterIterNext(. 
18d0: 20 73 71 6c 69 74 65 33 20 2a 64 62 2c 20 20 20   sqlite3 *db,   
18e0: 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20                  
18f0: 20 2f 2a 20 44 61 74 61 62 61 73 65 20 68 61 6e   /* Database han
1900: 64 6c 65 20 28 66 6f 72 20 73 71 6c 69 74 65 33  dle (for sqlite3
1910: 44 62 4d 61 6c 6c 6f 63 28 29 20 29 20 2a 2f 0a  DbMalloc() ) */.
1920: 20 20 56 64 62 65 53 6f 72 74 65 72 49 74 65 72    VdbeSorterIter
1930: 20 2a 70 49 74 65 72 20 20 20 20 20 20 20 20 20   *pIter         
1940: 20 20 2f 2a 20 49 74 65 72 61 74 6f 72 20 74 6f    /* Iterator to
1950: 20 61 64 76 61 6e 63 65 20 2a 2f 0a 29 7b 0a 20   advance */.){. 
1960: 20 69 6e 74 20 72 63 3b 20 20 20 20 20 20 20 20   int rc;        
1970: 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20                  
1980: 20 2f 2a 20 52 65 74 75 72 6e 20 43 6f 64 65 20   /* Return Code 
1990: 2a 2f 0a 20 20 69 6e 74 20 6e 52 65 61 64 3b 20  */.  int nRead; 
19a0: 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20                  
19b0: 20 20 20 20 20 2f 2a 20 4e 75 6d 62 65 72 20 6f       /* Number o
19c0: 66 20 62 79 74 65 73 20 72 65 61 64 20 2a 2f 0a  f bytes read */.
19d0: 20 20 69 6e 74 20 6e 52 65 63 20 3d 20 30 3b 20    int nRec = 0; 
19e0: 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20                  
19f0: 20 20 2f 2a 20 53 69 7a 65 20 6f 66 20 72 65 63    /* Size of rec
1a00: 6f 72 64 20 69 6e 20 62 79 74 65 73 20 2a 2f 0a  ord in bytes */.
1a10: 20 20 69 6e 74 20 69 4f 66 66 20 3d 20 30 3b 20    int iOff = 0; 
1a20: 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20                  
1a30: 20 20 2f 2a 20 53 69 7a 65 20 6f 66 20 73 65 72    /* Size of ser
1a40: 69 61 6c 69 7a 65 64 20 73 69 7a 65 20 76 61 72  ialized size var
1a50: 69 6e 74 20 69 6e 20 62 79 74 65 73 20 2a 2f 0a  int in bytes */.
1a60: 0a 20 20 61 73 73 65 72 74 28 20 70 49 74 65 72  .  assert( pIter
1a70: 2d 3e 69 45 6f 66 3e 3d 70 49 74 65 72 2d 3e 69  ->iEof>=pIter->i
1a80: 52 65 61 64 4f 66 66 20 29 3b 0a 20 20 69 66 28  ReadOff );.  if(
1a90: 20 70 49 74 65 72 2d 3e 69 45 6f 66 2d 70 49 74   pIter->iEof-pIt
1aa0: 65 72 2d 3e 69 52 65 61 64 4f 66 66 3e 35 20 29  er->iReadOff>5 )
1ab0: 7b 0a 20 20 20 20 6e 52 65 61 64 20 3d 20 35 3b  {.    nRead = 5;
1ac0: 0a 20 20 7d 65 6c 73 65 7b 0a 20 20 20 20 6e 52  .  }else{.    nR
1ad0: 65 61 64 20 3d 20 28 69 6e 74 29 28 70 49 74 65  ead = (int)(pIte
1ae0: 72 2d 3e 69 45 6f 66 20 2d 20 70 49 74 65 72 2d  r->iEof - pIter-
1af0: 3e 69 52 65 61 64 4f 66 66 29 3b 0a 20 20 7d 0a  >iReadOff);.  }.
1b00: 20 20 69 66 28 20 6e 52 65 61 64 3c 3d 30 20 29    if( nRead<=0 )
1b10: 7b 0a 20 20 20 20 2f 2a 20 54 68 69 73 20 69 73  {.    /* This is
1b20: 20 61 6e 20 45 4f 46 20 63 6f 6e 64 69 74 69 6f   an EOF conditio
1b30: 6e 20 2a 2f 0a 20 20 20 20 76 64 62 65 53 6f 72  n */.    vdbeSor
1b40: 74 65 72 49 74 65 72 5a 65 72 6f 28 64 62 2c 20  terIterZero(db, 
1b50: 70 49 74 65 72 29 3b 0a 20 20 20 20 72 65 74 75  pIter);.    retu
1b60: 72 6e 20 53 51 4c 49 54 45 5f 4f 4b 3b 0a 20 20  rn SQLITE_OK;.  
1b70: 7d 0a 0a 20 20 72 63 20 3d 20 73 71 6c 69 74 65  }..  rc = sqlite
1b80: 33 4f 73 52 65 61 64 28 70 49 74 65 72 2d 3e 70  3OsRead(pIter->p
1b90: 46 69 6c 65 2c 20 70 49 74 65 72 2d 3e 61 41 6c  File, pIter->aAl
1ba0: 6c 6f 63 2c 20 6e 52 65 61 64 2c 20 70 49 74 65  loc, nRead, pIte
1bb0: 72 2d 3e 69 52 65 61 64 4f 66 66 29 3b 0a 20 20  r->iReadOff);.  
1bc0: 69 66 28 20 72 63 3d 3d 53 51 4c 49 54 45 5f 4f  if( rc==SQLITE_O
1bd0: 4b 20 29 7b 0a 20 20 20 20 69 4f 66 66 20 3d 20  K ){.    iOff = 
1be0: 67 65 74 56 61 72 69 6e 74 33 32 28 70 49 74 65  getVarint32(pIte
1bf0: 72 2d 3e 61 41 6c 6c 6f 63 2c 20 6e 52 65 63 29  r->aAlloc, nRec)
1c00: 3b 0a 20 20 20 20 69 66 28 20 28 69 4f 66 66 2b  ;.    if( (iOff+
1c10: 6e 52 65 63 29 3e 6e 52 65 61 64 20 29 7b 0a 20  nRec)>nRead ){. 
1c20: 20 20 20 20 20 69 6e 74 20 6e 52 65 61 64 32 3b       int nRead2;
1c30: 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20                  
1c40: 20 20 20 2f 2a 20 4e 75 6d 62 65 72 20 6f 66 20     /* Number of 
1c50: 65 78 74 72 61 20 62 79 74 65 73 20 74 6f 20 72  extra bytes to r
1c60: 65 61 64 20 2a 2f 0a 20 20 20 20 20 20 69 66 28  ead */.      if(
1c70: 20 28 69 4f 66 66 2b 6e 52 65 63 29 3e 70 49 74   (iOff+nRec)>pIt
1c80: 65 72 2d 3e 6e 41 6c 6c 6f 63 20 29 7b 0a 20 20  er->nAlloc ){.  
1c90: 20 20 20 20 20 20 69 6e 74 20 6e 4e 65 77 20 3d        int nNew =
1ca0: 20 70 49 74 65 72 2d 3e 6e 41 6c 6c 6f 63 2a 32   pIter->nAlloc*2
1cb0: 3b 0a 20 20 20 20 20 20 20 20 77 68 69 6c 65 28  ;.        while(
1cc0: 20 28 69 4f 66 66 2b 6e 52 65 63 29 3e 6e 4e 65   (iOff+nRec)>nNe
1cd0: 77 20 29 20 6e 4e 65 77 20 3d 20 6e 4e 65 77 2a  w ) nNew = nNew*
1ce0: 32 3b 0a 20 20 20 20 20 20 20 20 70 49 74 65 72  2;.        pIter
1cf0: 2d 3e 61 41 6c 6c 6f 63 20 3d 20 73 71 6c 69 74  ->aAlloc = sqlit
1d00: 65 33 44 62 52 65 61 6c 6c 6f 63 4f 72 46 72 65  e3DbReallocOrFre
1d10: 65 28 64 62 2c 20 70 49 74 65 72 2d 3e 61 41 6c  e(db, pIter->aAl
1d20: 6c 6f 63 2c 20 6e 4e 65 77 29 3b 0a 20 20 20 20  loc, nNew);.    
1d30: 20 20 20 20 69 66 28 20 21 70 49 74 65 72 2d 3e      if( !pIter->
1d40: 61 41 6c 6c 6f 63 20 29 20 72 65 74 75 72 6e 20  aAlloc ) return 
1d50: 53 51 4c 49 54 45 5f 4e 4f 4d 45 4d 3b 0a 20 20  SQLITE_NOMEM;.  
1d60: 20 20 20 20 20 20 70 49 74 65 72 2d 3e 6e 41 6c        pIter->nAl
1d70: 6c 6f 63 20 3d 20 6e 4e 65 77 3b 0a 20 20 20 20  loc = nNew;.    
1d80: 20 20 7d 0a 20 20 0a 20 20 20 20 20 20 6e 52 65    }.  .      nRe
1d90: 61 64 32 20 3d 20 69 4f 66 66 20 2b 20 6e 52 65  ad2 = iOff + nRe
1da0: 63 20 2d 20 6e 52 65 61 64 3b 0a 20 20 20 20 20  c - nRead;.     
1db0: 20 72 63 20 3d 20 73 71 6c 69 74 65 33 4f 73 52   rc = sqlite3OsR
1dc0: 65 61 64 28 0a 20 20 20 20 20 20 20 20 20 20 70  ead(.          p
1dd0: 49 74 65 72 2d 3e 70 46 69 6c 65 2c 20 26 70 49  Iter->pFile, &pI
1de0: 74 65 72 2d 3e 61 41 6c 6c 6f 63 5b 6e 52 65 61  ter->aAlloc[nRea
1df0: 64 5d 2c 20 6e 52 65 61 64 32 2c 20 70 49 74 65  d], nRead2, pIte
1e00: 72 2d 3e 69 52 65 61 64 4f 66 66 2b 6e 52 65 61  r->iReadOff+nRea
1e10: 64 0a 20 20 20 20 20 20 29 3b 0a 20 20 20 20 7d  d.      );.    }
1e20: 0a 20 20 7d 0a 0a 20 20 61 73 73 65 72 74 28 20  .  }..  assert( 
1e30: 72 63 21 3d 53 51 4c 49 54 45 5f 4f 4b 20 7c 7c  rc!=SQLITE_OK ||
1e40: 20 6e 52 65 63 3e 30 20 29 3b 0a 20 20 70 49 74   nRec>0 );.  pIt
1e50: 65 72 2d 3e 69 52 65 61 64 4f 66 66 20 2b 3d 20  er->iReadOff += 
1e60: 69 4f 66 66 2b 6e 52 65 63 3b 0a 20 20 70 49 74  iOff+nRec;.  pIt
1e70: 65 72 2d 3e 6e 4b 65 79 20 3d 20 6e 52 65 63 3b  er->nKey = nRec;
1e80: 0a 20 20 70 49 74 65 72 2d 3e 61 4b 65 79 20 3d  .  pIter->aKey =
1e90: 20 26 70 49 74 65 72 2d 3e 61 41 6c 6c 6f 63 5b   &pIter->aAlloc[
1ea0: 69 4f 66 66 5d 3b 0a 20 20 72 65 74 75 72 6e 20  iOff];.  return 
1eb0: 72 63 3b 0a 7d 0a 0a 2f 2a 0a 2a 2a 20 57 72 69  rc;.}../*.** Wri
1ec0: 74 65 20 61 20 73 69 6e 67 6c 65 20 76 61 72 69  te a single vari
1ed0: 6e 74 2c 20 76 61 6c 75 65 20 69 56 61 6c 2c 20  nt, value iVal, 
1ee0: 74 6f 20 66 69 6c 65 2d 64 65 73 63 72 69 70 74  to file-descript
1ef0: 6f 72 20 70 46 69 6c 65 2e 20 52 65 74 75 72 6e  or pFile. Return
1f00: 0a 2a 2a 20 53 51 4c 49 54 45 5f 4f 4b 20 69 66  .** SQLITE_OK if
1f10: 20 73 75 63 63 65 73 73 66 75 6c 2c 20 6f 72 20   successful, or 
1f20: 61 6e 20 53 51 4c 69 74 65 20 65 72 72 6f 72 20  an SQLite error 
1f30: 63 6f 64 65 20 69 66 20 73 6f 6d 65 20 65 72 72  code if some err
1f40: 6f 72 20 6f 63 63 75 72 73 2e 0a 2a 2a 0a 2a 2a  or occurs..**.**
1f50: 20 54 68 65 20 76 61 6c 75 65 20 6f 66 20 2a 70   The value of *p
1f60: 69 4f 66 66 73 65 74 20 77 68 65 6e 20 74 68 69  iOffset when thi
1f70: 73 20 66 75 6e 63 74 69 6f 6e 20 69 73 20 63 61  s function is ca
1f80: 6c 6c 65 64 20 69 73 20 75 73 65 64 20 61 73 20  lled is used as 
1f90: 74 68 65 20 62 79 74 65 0a 2a 2a 20 6f 66 66 73  the byte.** offs
1fa0: 65 74 20 69 6e 20 66 69 6c 65 20 70 46 69 6c 65  et in file pFile
1fb0: 20 74 6f 20 77 72 69 74 65 20 74 6f 2e 20 42 65   to write to. Be
1fc0: 66 6f 72 65 20 72 65 74 75 72 6e 69 6e 67 2c 20  fore returning, 
1fd0: 2a 70 69 4f 66 66 73 65 74 20 69 73 20 0a 2a 2a  *piOffset is .**
1fe0: 20 69 6e 63 72 65 6d 65 6e 74 65 64 20 62 79 20   incremented by 
1ff0: 74 68 65 20 6e 75 6d 62 65 72 20 6f 66 20 62 79  the number of by
2000: 74 65 73 20 77 72 69 74 74 65 6e 2e 0a 2a 2f 0a  tes written..*/.
2010: 73 74 61 74 69 63 20 69 6e 74 20 76 64 62 65 53  static int vdbeS
2020: 6f 72 74 65 72 57 72 69 74 65 56 61 72 69 6e 74  orterWriteVarint
2030: 28 0a 20 20 73 71 6c 69 74 65 33 5f 66 69 6c 65  (.  sqlite3_file
2040: 20 2a 70 46 69 6c 65 2c 20 20 20 20 20 20 20 20   *pFile,        
2050: 20 20 20 20 2f 2a 20 46 69 6c 65 20 74 6f 20 77      /* File to w
2060: 72 69 74 65 20 74 6f 20 2a 2f 0a 20 20 69 36 34  rite to */.  i64
2070: 20 69 56 61 6c 2c 20 20 20 20 20 20 20 20 20 20   iVal,          
2080: 20 20 20 20 20 20 20 20 20 20 20 20 20 2f 2a 20               /* 
2090: 56 61 6c 75 65 20 74 6f 20 77 72 69 74 65 20 61  Value to write a
20a0: 73 20 61 20 76 61 72 69 6e 74 20 2a 2f 0a 20 20  s a varint */.  
20b0: 69 36 34 20 2a 70 69 4f 66 66 73 65 74 20 20 20  i64 *piOffset   
20c0: 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20                  
20d0: 2f 2a 20 49 4e 2f 4f 55 54 3a 20 57 72 69 74 65  /* IN/OUT: Write
20e0: 20 6f 66 66 73 65 74 20 69 6e 20 66 69 6c 65 20   offset in file 
20f0: 70 46 69 6c 65 20 2a 2f 0a 29 7b 0a 20 20 75 38  pFile */.){.  u8
2100: 20 61 56 61 72 69 6e 74 5b 39 5d 3b 20 20 20 20   aVarint[9];    
2110: 20 20 20 20 20 20 20 20 20 20 20 20 20 20 2f 2a                /*
2120: 20 42 75 66 66 65 72 20 6c 61 72 67 65 20 65 6e   Buffer large en
2130: 6f 75 67 68 20 66 6f 72 20 61 20 76 61 72 69 6e  ough for a varin
2140: 74 20 2a 2f 0a 20 20 69 6e 74 20 6e 56 61 72 69  t */.  int nVari
2150: 6e 74 3b 20 20 20 20 20 20 20 20 20 20 20 20 20  nt;             
2160: 20 20 20 20 20 20 20 2f 2a 20 4e 75 6d 62 65 72         /* Number
2170: 20 6f 66 20 75 73 65 64 20 62 79 74 65 73 20 69   of used bytes i
2180: 6e 20 76 61 72 69 6e 74 20 2a 2f 0a 20 20 69 6e  n varint */.  in
2190: 74 20 72 63 3b 20 20 20 20 20 20 20 20 20 20 20  t rc;           
21a0: 20 20 20 20 20 20 20 20 20 20 20 20 20 20 2f 2a                /*
21b0: 20 52 65 73 75 6c 74 20 6f 66 20 77 72 69 74 65   Result of write
21c0: 28 29 20 63 61 6c 6c 20 2a 2f 0a 0a 20 20 6e 56  () call */..  nV
21d0: 61 72 69 6e 74 20 3d 20 73 71 6c 69 74 65 33 50  arint = sqlite3P
21e0: 75 74 56 61 72 69 6e 74 28 61 56 61 72 69 6e 74  utVarint(aVarint
21f0: 2c 20 69 56 61 6c 29 3b 0a 20 20 72 63 20 3d 20  , iVal);.  rc = 
2200: 73 71 6c 69 74 65 33 4f 73 57 72 69 74 65 28 70  sqlite3OsWrite(p
2210: 46 69 6c 65 2c 20 61 56 61 72 69 6e 74 2c 20 6e  File, aVarint, n
2220: 56 61 72 69 6e 74 2c 20 2a 70 69 4f 66 66 73 65  Varint, *piOffse
2230: 74 29 3b 0a 20 20 2a 70 69 4f 66 66 73 65 74 20  t);.  *piOffset 
2240: 2b 3d 20 6e 56 61 72 69 6e 74 3b 0a 0a 20 20 72  += nVarint;..  r
2250: 65 74 75 72 6e 20 72 63 3b 0a 7d 0a 0a 2f 2a 0a  eturn rc;.}../*.
2260: 2a 2a 20 52 65 61 64 20 61 20 73 69 6e 67 6c 65  ** Read a single
2270: 20 76 61 72 69 6e 74 20 66 72 6f 6d 20 66 69 6c   varint from fil
2280: 65 2d 64 65 73 63 72 69 70 74 6f 72 20 70 46 69  e-descriptor pFi
2290: 6c 65 2e 20 52 65 74 75 72 6e 20 53 51 4c 49 54  le. Return SQLIT
22a0: 45 5f 4f 4b 20 69 66 0a 2a 2a 20 73 75 63 63 65  E_OK if.** succe
22b0: 73 73 66 75 6c 2c 20 6f 72 20 61 6e 20 53 51 4c  ssful, or an SQL
22c0: 69 74 65 20 65 72 72 6f 72 20 63 6f 64 65 20 69  ite error code i
22d0: 66 20 73 6f 6d 65 20 65 72 72 6f 72 20 6f 63 63  f some error occ
22e0: 75 72 73 2e 0a 2a 2a 0a 2a 2a 20 54 68 65 20 76  urs..**.** The v
22f0: 61 6c 75 65 20 6f 66 20 2a 70 69 4f 66 66 73 65  alue of *piOffse
2300: 74 20 77 68 65 6e 20 74 68 69 73 20 66 75 6e 63  t when this func
2310: 74 69 6f 6e 20 69 73 20 63 61 6c 6c 65 64 20 69  tion is called i
2320: 73 20 75 73 65 64 20 61 73 20 74 68 65 0a 2a 2a  s used as the.**
2330: 20 62 79 74 65 20 6f 66 66 73 65 74 20 69 6e 20   byte offset in 
2340: 66 69 6c 65 20 70 46 69 6c 65 20 66 72 6f 6d 20  file pFile from 
2350: 77 68 65 6e 63 65 20 74 6f 20 72 65 61 64 20 74  whence to read t
2360: 68 65 20 76 61 72 69 6e 74 2e 20 49 66 20 73 75  he varint. If su
2370: 63 63 65 73 73 66 75 6c 0a 2a 2a 20 28 69 2e 65  ccessful.** (i.e
2380: 2e 20 69 66 20 6e 6f 20 49 4f 20 65 72 72 6f 72  . if no IO error
2390: 20 6f 63 63 75 72 73 29 2c 20 74 68 65 6e 20 2a   occurs), then *
23a0: 70 69 4f 66 66 73 65 74 20 69 73 20 73 65 74 20  piOffset is set 
23b0: 74 6f 20 74 68 65 20 6f 66 66 73 65 74 20 6f 66  to the offset of
23c0: 0a 2a 2a 20 74 68 65 20 66 69 72 73 74 20 62 79  .** the first by
23d0: 74 65 20 70 61 73 74 20 74 68 65 20 65 6e 64 20  te past the end 
23e0: 6f 66 20 74 68 65 20 76 61 72 69 6e 74 20 62 65  of the varint be
23f0: 66 6f 72 65 20 72 65 74 75 72 6e 69 6e 67 2e 20  fore returning. 
2400: 2a 70 69 56 61 6c 20 69 73 0a 2a 2a 20 73 65 74  *piVal is.** set
2410: 20 74 6f 20 74 68 65 20 69 6e 74 65 67 65 72 20   to the integer 
2420: 76 61 6c 75 65 20 72 65 61 64 2e 20 49 66 20 61  value read. If a
2430: 6e 20 65 72 72 6f 72 20 6f 63 63 75 72 73 2c 20  n error occurs, 
2440: 74 68 65 20 66 69 6e 61 6c 20 76 61 6c 75 65 73  the final values
2450: 20 6f 66 0a 2a 2a 20 62 6f 74 68 20 2a 70 69 4f   of.** both *piO
2460: 66 66 73 65 74 20 61 6e 64 20 2a 70 69 56 61 6c  ffset and *piVal
2470: 20 61 72 65 20 75 6e 64 65 66 69 6e 65 64 2e 0a   are undefined..
2480: 2a 2f 0a 73 74 61 74 69 63 20 69 6e 74 20 76 64  */.static int vd
2490: 62 65 53 6f 72 74 65 72 52 65 61 64 56 61 72 69  beSorterReadVari
24a0: 6e 74 28 0a 20 20 73 71 6c 69 74 65 33 5f 66 69  nt(.  sqlite3_fi
24b0: 6c 65 20 2a 70 46 69 6c 65 2c 20 20 20 20 20 20  le *pFile,      
24c0: 20 20 20 20 20 20 2f 2a 20 46 69 6c 65 20 74 6f        /* File to
24d0: 20 72 65 61 64 20 66 72 6f 6d 20 2a 2f 0a 20 20   read from */.  
24e0: 69 36 34 20 2a 70 69 4f 66 66 73 65 74 2c 20 20  i64 *piOffset,  
24f0: 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20                  
2500: 2f 2a 20 49 4e 2f 4f 55 54 3a 20 52 65 61 64 20  /* IN/OUT: Read 
2510: 6f 66 66 73 65 74 20 69 6e 20 70 46 69 6c 65 20  offset in pFile 
2520: 2a 2f 0a 20 20 69 36 34 20 2a 70 69 56 61 6c 20  */.  i64 *piVal 
2530: 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20                  
2540: 20 20 20 20 20 2f 2a 20 4f 55 54 3a 20 56 61 6c       /* OUT: Val
2550: 75 65 20 72 65 61 64 20 66 72 6f 6d 20 66 69 6c  ue read from fil
2560: 65 20 2a 2f 0a 29 7b 0a 20 20 75 38 20 61 56 61  e */.){.  u8 aVa
2570: 72 69 6e 74 5b 39 5d 3b 20 20 20 20 20 20 20 20  rint[9];        
2580: 20 20 20 20 20 20 20 20 20 20 2f 2a 20 42 75 66            /* Buf
2590: 66 65 72 20 6c 61 72 67 65 20 65 6e 6f 75 67 68  fer large enough
25a0: 20 66 6f 72 20 61 20 76 61 72 69 6e 74 20 2a 2f   for a varint */
25b0: 0a 20 20 69 36 34 20 69 4f 66 66 20 3d 20 2a 70  .  i64 iOff = *p
25c0: 69 4f 66 66 73 65 74 3b 20 20 20 20 20 20 20 20  iOffset;        
25d0: 20 20 20 2f 2a 20 4f 66 66 73 65 74 20 69 6e 20     /* Offset in 
25e0: 66 69 6c 65 20 74 6f 20 72 65 61 64 20 66 72 6f  file to read fro
25f0: 6d 20 2a 2f 0a 20 20 69 6e 74 20 72 63 3b 20 20  m */.  int rc;  
2600: 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20                  
2610: 20 20 20 20 20 20 20 2f 2a 20 52 65 74 75 72 6e         /* Return
2620: 20 63 6f 64 65 20 2a 2f 0a 0a 20 20 72 63 20 3d   code */..  rc =
2630: 20 73 71 6c 69 74 65 33 4f 73 52 65 61 64 28 70   sqlite3OsRead(p
2640: 46 69 6c 65 2c 20 61 56 61 72 69 6e 74 2c 20 39  File, aVarint, 9
2650: 2c 20 69 4f 66 66 29 3b 0a 20 20 69 66 28 20 72  , iOff);.  if( r
2660: 63 3d 3d 53 51 4c 49 54 45 5f 4f 4b 20 29 7b 0a  c==SQLITE_OK ){.
2670: 20 20 20 20 2a 70 69 4f 66 66 73 65 74 20 2b 3d      *piOffset +=
2680: 20 67 65 74 56 61 72 69 6e 74 28 61 56 61 72 69   getVarint(aVari
2690: 6e 74 2c 20 28 75 36 34 20 2a 29 70 69 56 61 6c  nt, (u64 *)piVal
26a0: 29 3b 0a 20 20 7d 0a 0a 20 20 72 65 74 75 72 6e  );.  }..  return
26b0: 20 72 63 3b 0a 7d 0a 0a 2f 2a 0a 2a 2a 20 49 6e   rc;.}../*.** In
26c0: 69 74 69 61 6c 69 7a 65 20 69 74 65 72 61 74 6f  itialize iterato
26d0: 72 20 70 49 74 65 72 20 74 6f 20 73 63 61 6e 20  r pIter to scan 
26e0: 74 68 72 6f 75 67 68 20 74 68 65 20 50 4d 41 20  through the PMA 
26f0: 73 74 6f 72 65 64 20 69 6e 20 66 69 6c 65 20 70  stored in file p
2700: 46 69 6c 65 0a 2a 2a 20 73 74 61 72 74 69 6e 67  File.** starting
2710: 20 61 74 20 6f 66 66 73 65 74 20 69 53 74 61 72   at offset iStar
2720: 74 20 61 6e 64 20 65 6e 64 69 6e 67 20 61 74 20  t and ending at 
2730: 6f 66 66 73 65 74 20 69 45 6f 66 2d 31 2e 20 54  offset iEof-1. T
2740: 68 69 73 20 66 75 6e 63 74 69 6f 6e 20 0a 2a 2a  his function .**
2750: 20 6c 65 61 76 65 73 20 74 68 65 20 69 74 65 72   leaves the iter
2760: 61 74 6f 72 20 70 6f 69 6e 74 69 6e 67 20 74 6f  ator pointing to
2770: 20 74 68 65 20 66 69 72 73 74 20 6b 65 79 20 69   the first key i
2780: 6e 20 74 68 65 20 50 4d 41 20 28 6f 72 20 45 4f  n the PMA (or EO
2790: 46 20 69 66 20 74 68 65 20 0a 2a 2a 20 50 4d 41  F if the .** PMA
27a0: 20 69 73 20 65 6d 70 74 79 29 2e 0a 2a 2f 0a 73   is empty)..*/.s
27b0: 74 61 74 69 63 20 69 6e 74 20 76 64 62 65 53 6f  tatic int vdbeSo
27c0: 72 74 65 72 49 74 65 72 49 6e 69 74 28 0a 20 20  rterIterInit(.  
27d0: 73 71 6c 69 74 65 33 20 2a 64 62 2c 20 20 20 20  sqlite3 *db,    
27e0: 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20                  
27f0: 2f 2a 20 44 61 74 61 62 61 73 65 20 68 61 6e 64  /* Database hand
2800: 6c 65 20 2a 2f 0a 20 20 56 64 62 65 53 6f 72 74  le */.  VdbeSort
2810: 65 72 20 2a 70 53 6f 72 74 65 72 2c 20 20 20 20  er *pSorter,    
2820: 20 20 20 20 20 20 20 20 2f 2a 20 53 6f 72 74 65          /* Sorte
2830: 72 20 6f 62 6a 65 63 74 20 2a 2f 0a 20 20 69 36  r object */.  i6
2840: 34 20 69 53 74 61 72 74 2c 20 20 20 20 20 20 20  4 iStart,       
2850: 20 20 20 20 20 20 20 20 20 20 20 20 20 20 2f 2a                /*
2860: 20 53 74 61 72 74 20 6f 66 66 73 65 74 20 69 6e   Start offset in
2870: 20 70 46 69 6c 65 20 2a 2f 0a 20 20 56 64 62 65   pFile */.  Vdbe
2880: 53 6f 72 74 65 72 49 74 65 72 20 2a 70 49 74 65  SorterIter *pIte
2890: 72 2c 20 20 20 20 20 20 20 20 20 20 2f 2a 20 49  r,          /* I
28a0: 74 65 72 61 74 6f 72 20 74 6f 20 70 6f 70 75 6c  terator to popul
28b0: 61 74 65 20 2a 2f 0a 20 20 69 36 34 20 2a 70 6e  ate */.  i64 *pn
28c0: 42 79 74 65 20 20 20 20 20 20 20 20 20 20 20 20  Byte            
28d0: 20 20 20 20 20 20 20 20 20 2f 2a 20 49 4e 2f 4f           /* IN/O
28e0: 55 54 3a 20 49 6e 63 72 65 6d 65 6e 74 20 74 68  UT: Increment th
28f0: 69 73 20 76 61 6c 75 65 20 62 79 20 50 4d 41 20  is value by PMA 
2900: 73 69 7a 65 20 2a 2f 0a 29 7b 0a 20 20 69 6e 74  size */.){.  int
2910: 20 72 63 3b 0a 0a 20 20 61 73 73 65 72 74 28 20   rc;..  assert( 
2920: 70 53 6f 72 74 65 72 2d 3e 69 57 72 69 74 65 4f  pSorter->iWriteO
2930: 66 66 3e 69 53 74 61 72 74 20 29 3b 0a 20 20 61  ff>iStart );.  a
2940: 73 73 65 72 74 28 20 70 49 74 65 72 2d 3e 61 41  ssert( pIter->aA
2950: 6c 6c 6f 63 3d 3d 30 20 29 3b 0a 20 20 70 49 74  lloc==0 );.  pIt
2960: 65 72 2d 3e 70 46 69 6c 65 20 3d 20 70 53 6f 72  er->pFile = pSor
2970: 74 65 72 2d 3e 70 54 65 6d 70 31 3b 0a 20 20 70  ter->pTemp1;.  p
2980: 49 74 65 72 2d 3e 69 52 65 61 64 4f 66 66 20 3d  Iter->iReadOff =
2990: 20 69 53 74 61 72 74 3b 0a 20 20 70 49 74 65 72   iStart;.  pIter
29a0: 2d 3e 6e 41 6c 6c 6f 63 20 3d 20 31 32 38 3b 0a  ->nAlloc = 128;.
29b0: 20 20 70 49 74 65 72 2d 3e 61 41 6c 6c 6f 63 20    pIter->aAlloc 
29c0: 3d 20 28 75 38 20 2a 29 73 71 6c 69 74 65 33 44  = (u8 *)sqlite3D
29d0: 62 4d 61 6c 6c 6f 63 52 61 77 28 64 62 2c 20 70  bMallocRaw(db, p
29e0: 49 74 65 72 2d 3e 6e 41 6c 6c 6f 63 29 3b 0a 20  Iter->nAlloc);. 
29f0: 20 69 66 28 20 21 70 49 74 65 72 2d 3e 61 41 6c   if( !pIter->aAl
2a00: 6c 6f 63 20 29 7b 0a 20 20 20 20 72 63 20 3d 20  loc ){.    rc = 
2a10: 53 51 4c 49 54 45 5f 4e 4f 4d 45 4d 3b 0a 20 20  SQLITE_NOMEM;.  
2a20: 7d 65 6c 73 65 7b 0a 20 20 20 20 69 36 34 20 6e  }else{.    i64 n
2a30: 42 79 74 65 3b 20 20 20 20 20 20 20 20 20 20 20  Byte;           
2a40: 20 20 20 20 20 20 20 20 20 20 20 20 20 20 2f 2a                /*
2a50: 20 54 6f 74 61 6c 20 73 69 7a 65 20 6f 66 20 50   Total size of P
2a60: 4d 41 20 69 6e 20 62 79 74 65 73 20 2a 2f 0a 20  MA in bytes */. 
2a70: 20 20 20 72 63 20 3d 20 76 64 62 65 53 6f 72 74     rc = vdbeSort
2a80: 65 72 52 65 61 64 56 61 72 69 6e 74 28 70 53 6f  erReadVarint(pSo
2a90: 72 74 65 72 2d 3e 70 54 65 6d 70 31 2c 20 26 70  rter->pTemp1, &p
2aa0: 49 74 65 72 2d 3e 69 52 65 61 64 4f 66 66 2c 20  Iter->iReadOff, 
2ab0: 26 6e 42 79 74 65 29 3b 0a 20 20 20 20 2a 70 6e  &nByte);.    *pn
2ac0: 42 79 74 65 20 2b 3d 20 6e 42 79 74 65 3b 0a 20  Byte += nByte;. 
2ad0: 20 20 20 70 49 74 65 72 2d 3e 69 45 6f 66 20 3d     pIter->iEof =
2ae0: 20 70 49 74 65 72 2d 3e 69 52 65 61 64 4f 66 66   pIter->iReadOff
2af0: 20 2b 20 6e 42 79 74 65 3b 0a 20 20 7d 0a 20 20   + nByte;.  }.  
2b00: 69 66 28 20 72 63 3d 3d 53 51 4c 49 54 45 5f 4f  if( rc==SQLITE_O
2b10: 4b 20 29 7b 0a 20 20 20 20 72 63 20 3d 20 76 64  K ){.    rc = vd
2b20: 62 65 53 6f 72 74 65 72 49 74 65 72 4e 65 78 74  beSorterIterNext
2b30: 28 64 62 2c 20 70 49 74 65 72 29 3b 0a 20 20 7d  (db, pIter);.  }
2b40: 0a 20 20 72 65 74 75 72 6e 20 72 63 3b 0a 7d 0a  .  return rc;.}.
2b50: 0a 0a 2f 2a 0a 2a 2a 20 43 6f 6d 70 61 72 65 20  ../*.** Compare 
2b60: 6b 65 79 31 20 28 62 75 66 66 65 72 20 70 4b 65  key1 (buffer pKe
2b70: 79 31 2c 20 73 69 7a 65 20 6e 4b 65 79 31 20 62  y1, size nKey1 b
2b80: 79 74 65 73 29 20 77 69 74 68 20 6b 65 79 32 20  ytes) with key2 
2b90: 28 62 75 66 66 65 72 20 70 4b 65 79 32 2c 20 0a  (buffer pKey2, .
2ba0: 2a 2a 20 73 69 7a 65 20 6e 4b 65 79 32 20 62 79  ** size nKey2 by
2bb0: 74 65 73 29 2e 20 20 41 72 67 75 6d 65 6e 74 20  tes).  Argument 
2bc0: 70 4b 65 79 49 6e 66 6f 20 73 75 70 70 6c 69 65  pKeyInfo supplie
2bd0: 73 20 74 68 65 20 63 6f 6c 6c 61 74 69 6f 6e 20  s the collation 
2be0: 66 75 6e 63 74 69 6f 6e 73 0a 2a 2a 20 75 73 65  functions.** use
2bf0: 64 20 62 79 20 74 68 65 20 63 6f 6d 70 61 72 69  d by the compari
2c00: 73 6f 6e 2e 20 49 66 20 61 6e 20 65 72 72 6f 72  son. If an error
2c10: 20 6f 63 63 75 72 73 2c 20 72 65 74 75 72 6e 20   occurs, return 
2c20: 61 6e 20 53 51 4c 69 74 65 20 65 72 72 6f 72 20  an SQLite error 
2c30: 63 6f 64 65 2e 0a 2a 2a 20 4f 74 68 65 72 77 69  code..** Otherwi
2c40: 73 65 2c 20 72 65 74 75 72 6e 20 53 51 4c 49 54  se, return SQLIT
2c50: 45 5f 4f 4b 20 61 6e 64 20 73 65 74 20 2a 70 52  E_OK and set *pR
2c60: 65 73 20 74 6f 20 61 20 6e 65 67 61 74 69 76 65  es to a negative
2c70: 2c 20 7a 65 72 6f 20 6f 72 20 70 6f 73 69 74 69  , zero or positi
2c80: 76 65 0a 2a 2a 20 76 61 6c 75 65 2c 20 64 65 70  ve.** value, dep
2c90: 65 6e 64 69 6e 67 20 6f 6e 20 77 68 65 74 68 65  ending on whethe
2ca0: 72 20 6b 65 79 31 20 69 73 20 73 6d 61 6c 6c 65  r key1 is smalle
2cb0: 72 2c 20 65 71 75 61 6c 20 74 6f 20 6f 72 20 6c  r, equal to or l
2cc0: 61 72 67 65 72 20 74 68 61 6e 20 6b 65 79 32 2e  arger than key2.
2cd0: 0a 2a 2a 0a 2a 2a 20 49 66 20 74 68 65 20 62 4f  .**.** If the bO
2ce0: 6d 69 74 52 6f 77 69 64 20 61 72 67 75 6d 65 6e  mitRowid argumen
2cf0: 74 20 69 73 20 6e 6f 6e 2d 7a 65 72 6f 2c 20 61  t is non-zero, a
2d00: 73 73 75 6d 65 20 62 6f 74 68 20 6b 65 79 73 20  ssume both keys 
2d10: 65 6e 64 20 69 6e 20 61 20 72 6f 77 69 64 0a 2a  end in a rowid.*
2d20: 2a 20 66 69 65 6c 64 2e 20 46 6f 72 20 74 68 65  * field. For the
2d30: 20 70 75 72 70 6f 73 65 73 20 6f 66 20 74 68 65   purposes of the
2d40: 20 63 6f 6d 70 61 72 69 73 6f 6e 2c 20 69 67 6e   comparison, ign
2d50: 6f 72 65 20 69 74 2e 20 41 6c 73 6f 2c 20 69 66  ore it. Also, if
2d60: 20 62 4f 6d 69 74 52 6f 77 69 64 0a 2a 2a 20 69   bOmitRowid.** i
2d70: 73 20 74 72 75 65 20 61 6e 64 20 6b 65 79 31 20  s true and key1 
2d80: 63 6f 6e 74 61 69 6e 73 20 65 76 65 6e 20 61 20  contains even a 
2d90: 73 69 6e 67 6c 65 20 4e 55 4c 4c 20 76 61 6c 75  single NULL valu
2da0: 65 2c 20 69 74 20 69 73 20 63 6f 6e 73 69 64 65  e, it is conside
2db0: 72 65 64 20 74 6f 0a 2a 2a 20 62 65 20 6c 65 73  red to.** be les
2dc0: 73 20 74 68 61 6e 20 6b 65 79 32 2e 20 45 76 65  s than key2. Eve
2dd0: 6e 20 69 66 20 6b 65 79 32 20 61 6c 73 6f 20 63  n if key2 also c
2de0: 6f 6e 74 61 69 6e 73 20 4e 55 4c 4c 20 76 61 6c  ontains NULL val
2df0: 75 65 73 2e 0a 2a 2a 0a 2a 2a 20 49 66 20 70 4b  ues..**.** If pK
2e00: 65 79 32 20 69 73 20 70 61 73 73 65 64 20 61 20  ey2 is passed a 
2e10: 4e 55 4c 4c 20 70 6f 69 6e 74 65 72 2c 20 74 68  NULL pointer, th
2e20: 65 6e 20 69 74 20 69 73 20 61 73 73 75 6d 65 64  en it is assumed
2e30: 20 74 68 61 74 20 74 68 65 20 70 43 73 72 2d 3e   that the pCsr->
2e40: 61 53 70 61 63 65 0a 2a 2a 20 68 61 73 20 62 65  aSpace.** has be
2e50: 65 6e 20 61 6c 6c 6f 63 61 74 65 64 20 61 6e 64  en allocated and
2e60: 20 63 6f 6e 74 61 69 6e 73 20 61 6e 20 75 6e 70   contains an unp
2e70: 61 63 6b 65 64 20 72 65 63 6f 72 64 20 74 68 61  acked record tha
2e80: 74 20 69 73 20 75 73 65 64 20 61 73 20 6b 65 79  t is used as key
2e90: 32 2e 0a 2a 2f 0a 73 74 61 74 69 63 20 76 6f 69  2..*/.static voi
2ea0: 64 20 76 64 62 65 53 6f 72 74 65 72 43 6f 6d 70  d vdbeSorterComp
2eb0: 61 72 65 28 0a 20 20 56 64 62 65 43 75 72 73 6f  are(.  VdbeCurso
2ec0: 72 20 2a 70 43 73 72 2c 20 20 20 20 20 20 20 20  r *pCsr,        
2ed0: 20 20 20 20 20 20 20 2f 2a 20 43 75 72 73 6f 72         /* Cursor
2ee0: 20 6f 62 6a 65 63 74 20 28 66 6f 72 20 70 4b 65   object (for pKe
2ef0: 79 49 6e 66 6f 29 20 2a 2f 0a 20 20 69 6e 74 20  yInfo) */.  int 
2f00: 62 4f 6d 69 74 52 6f 77 69 64 2c 20 20 20 20 20  bOmitRowid,     
2f10: 20 20 20 20 20 20 20 20 20 20 20 20 2f 2a 20 49              /* I
2f20: 67 6e 6f 72 65 20 72 6f 77 69 64 20 66 69 65 6c  gnore rowid fiel
2f30: 64 20 61 74 20 65 6e 64 20 6f 66 20 6b 65 79 73  d at end of keys
2f40: 20 2a 2f 0a 20 20 76 6f 69 64 20 2a 70 4b 65 79   */.  void *pKey
2f50: 31 2c 20 69 6e 74 20 6e 4b 65 79 31 2c 20 20 20  1, int nKey1,   
2f60: 20 20 20 20 20 20 2f 2a 20 4c 65 66 74 20 73 69        /* Left si
2f70: 64 65 20 6f 66 20 63 6f 6d 70 61 72 69 73 6f 6e  de of comparison
2f80: 20 2a 2f 0a 20 20 76 6f 69 64 20 2a 70 4b 65 79   */.  void *pKey
2f90: 32 2c 20 69 6e 74 20 6e 4b 65 79 32 2c 20 20 20  2, int nKey2,   
2fa0: 20 20 20 20 20 20 2f 2a 20 52 69 67 68 74 20 73        /* Right s
2fb0: 69 64 65 20 6f 66 20 63 6f 6d 70 61 72 69 73 6f  ide of compariso
2fc0: 6e 20 2a 2f 0a 20 20 69 6e 74 20 2a 70 52 65 73  n */.  int *pRes
2fd0: 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20                  
2fe0: 20 20 20 20 20 20 20 2f 2a 20 4f 55 54 3a 20 52         /* OUT: R
2ff0: 65 73 75 6c 74 20 6f 66 20 63 6f 6d 70 61 72 69  esult of compari
3000: 73 6f 6e 20 2a 2f 0a 29 7b 0a 20 20 4b 65 79 49  son */.){.  KeyI
3010: 6e 66 6f 20 2a 70 4b 65 79 49 6e 66 6f 20 3d 20  nfo *pKeyInfo = 
3020: 70 43 73 72 2d 3e 70 4b 65 79 49 6e 66 6f 3b 0a  pCsr->pKeyInfo;.
3030: 20 20 56 64 62 65 53 6f 72 74 65 72 20 2a 70 53    VdbeSorter *pS
3040: 6f 72 74 65 72 20 3d 20 70 43 73 72 2d 3e 70 53  orter = pCsr->pS
3050: 6f 72 74 65 72 3b 0a 20 20 55 6e 70 61 63 6b 65  orter;.  Unpacke
3060: 64 52 65 63 6f 72 64 20 2a 72 32 20 3d 20 70 53  dRecord *r2 = pS
3070: 6f 72 74 65 72 2d 3e 70 55 6e 70 61 63 6b 65 64  orter->pUnpacked
3080: 3b 0a 20 20 69 6e 74 20 69 3b 0a 0a 20 20 69 66  ;.  int i;..  if
3090: 28 20 70 4b 65 79 32 20 29 7b 0a 20 20 20 20 73  ( pKey2 ){.    s
30a0: 71 6c 69 74 65 33 56 64 62 65 52 65 63 6f 72 64  qlite3VdbeRecord
30b0: 55 6e 70 61 63 6b 28 70 4b 65 79 49 6e 66 6f 2c  Unpack(pKeyInfo,
30c0: 20 6e 4b 65 79 32 2c 20 70 4b 65 79 32 2c 20 72   nKey2, pKey2, r
30d0: 32 29 3b 0a 20 20 7d 0a 0a 20 20 69 66 28 20 62  2);.  }..  if( b
30e0: 4f 6d 69 74 52 6f 77 69 64 20 29 7b 0a 20 20 20  OmitRowid ){.   
30f0: 20 72 32 2d 3e 6e 46 69 65 6c 64 20 3d 20 70 4b   r2->nField = pK
3100: 65 79 49 6e 66 6f 2d 3e 6e 46 69 65 6c 64 3b 0a  eyInfo->nField;.
3110: 20 20 20 20 61 73 73 65 72 74 28 20 72 32 2d 3e      assert( r2->
3120: 6e 46 69 65 6c 64 3e 30 20 29 3b 0a 20 20 20 20  nField>0 );.    
3130: 66 6f 72 28 69 3d 30 3b 20 69 3c 72 32 2d 3e 6e  for(i=0; i<r2->n
3140: 46 69 65 6c 64 3b 20 69 2b 2b 29 7b 0a 20 20 20  Field; i++){.   
3150: 20 20 20 69 66 28 20 72 32 2d 3e 61 4d 65 6d 5b     if( r2->aMem[
3160: 69 5d 2e 66 6c 61 67 73 20 26 20 4d 45 4d 5f 4e  i].flags & MEM_N
3170: 75 6c 6c 20 29 7b 0a 20 20 20 20 20 20 20 20 2a  ull ){.        *
3180: 70 52 65 73 20 3d 20 2d 31 3b 0a 20 20 20 20 20  pRes = -1;.     
3190: 20 20 20 72 65 74 75 72 6e 3b 0a 20 20 20 20 20     return;.     
31a0: 20 7d 0a 20 20 20 20 7d 0a 20 20 20 20 72 32 2d   }.    }.    r2-
31b0: 3e 66 6c 61 67 73 20 7c 3d 20 55 4e 50 41 43 4b  >flags |= UNPACK
31c0: 45 44 5f 50 52 45 46 49 58 5f 4d 41 54 43 48 3b  ED_PREFIX_MATCH;
31d0: 0a 20 20 7d 0a 0a 20 20 2a 70 52 65 73 20 3d 20  .  }..  *pRes = 
31e0: 73 71 6c 69 74 65 33 56 64 62 65 52 65 63 6f 72  sqlite3VdbeRecor
31f0: 64 43 6f 6d 70 61 72 65 28 6e 4b 65 79 31 2c 20  dCompare(nKey1, 
3200: 70 4b 65 79 31 2c 20 72 32 29 3b 0a 7d 0a 0a 2f  pKey1, r2);.}../
3210: 2a 0a 2a 2a 20 54 68 69 73 20 66 75 6e 63 74 69  *.** This functi
3220: 6f 6e 20 69 73 20 63 61 6c 6c 65 64 20 74 6f 20  on is called to 
3230: 63 6f 6d 70 61 72 65 20 74 77 6f 20 69 74 65 72  compare two iter
3240: 61 74 6f 72 20 6b 65 79 73 20 77 68 65 6e 20 6d  ator keys when m
3250: 65 72 67 69 6e 67 20 0a 2a 2a 20 6d 75 6c 74 69  erging .** multi
3260: 70 6c 65 20 62 2d 74 72 65 65 20 73 65 67 6d 65  ple b-tree segme
3270: 6e 74 73 2e 20 50 61 72 61 6d 65 74 65 72 20 69  nts. Parameter i
3280: 4f 75 74 20 69 73 20 74 68 65 20 69 6e 64 65 78  Out is the index
3290: 20 6f 66 20 74 68 65 20 61 54 72 65 65 5b 5d 20   of the aTree[] 
32a0: 0a 2a 2a 20 76 61 6c 75 65 20 74 6f 20 72 65 63  .** value to rec
32b0: 61 6c 63 75 6c 61 74 65 2e 0a 2a 2f 0a 73 74 61  alculate..*/.sta
32c0: 74 69 63 20 69 6e 74 20 76 64 62 65 53 6f 72 74  tic int vdbeSort
32d0: 65 72 44 6f 43 6f 6d 70 61 72 65 28 56 64 62 65  erDoCompare(Vdbe
32e0: 43 75 72 73 6f 72 20 2a 70 43 73 72 2c 20 69 6e  Cursor *pCsr, in
32f0: 74 20 69 4f 75 74 29 7b 0a 20 20 56 64 62 65 53  t iOut){.  VdbeS
3300: 6f 72 74 65 72 20 2a 70 53 6f 72 74 65 72 20 3d  orter *pSorter =
3310: 20 70 43 73 72 2d 3e 70 53 6f 72 74 65 72 3b 0a   pCsr->pSorter;.
3320: 20 20 69 6e 74 20 69 31 3b 0a 20 20 69 6e 74 20    int i1;.  int 
3330: 69 32 3b 0a 20 20 69 6e 74 20 69 52 65 73 3b 0a  i2;.  int iRes;.
3340: 20 20 56 64 62 65 53 6f 72 74 65 72 49 74 65 72    VdbeSorterIter
3350: 20 2a 70 31 3b 0a 20 20 56 64 62 65 53 6f 72 74   *p1;.  VdbeSort
3360: 65 72 49 74 65 72 20 2a 70 32 3b 0a 0a 20 20 61  erIter *p2;..  a
3370: 73 73 65 72 74 28 20 69 4f 75 74 3c 70 53 6f 72  ssert( iOut<pSor
3380: 74 65 72 2d 3e 6e 54 72 65 65 20 26 26 20 69 4f  ter->nTree && iO
3390: 75 74 3e 30 20 29 3b 0a 0a 20 20 69 66 28 20 69  ut>0 );..  if( i
33a0: 4f 75 74 3e 3d 28 70 53 6f 72 74 65 72 2d 3e 6e  Out>=(pSorter->n
33b0: 54 72 65 65 2f 32 29 20 29 7b 0a 20 20 20 20 69  Tree/2) ){.    i
33c0: 31 20 3d 20 28 69 4f 75 74 20 2d 20 70 53 6f 72  1 = (iOut - pSor
33d0: 74 65 72 2d 3e 6e 54 72 65 65 2f 32 29 20 2a 20  ter->nTree/2) * 
33e0: 32 3b 0a 20 20 20 20 69 32 20 3d 20 69 31 20 2b  2;.    i2 = i1 +
33f0: 20 31 3b 0a 20 20 7d 65 6c 73 65 7b 0a 20 20 20   1;.  }else{.   
3400: 20 69 31 20 3d 20 70 53 6f 72 74 65 72 2d 3e 61   i1 = pSorter->a
3410: 54 72 65 65 5b 69 4f 75 74 2a 32 5d 3b 0a 20 20  Tree[iOut*2];.  
3420: 20 20 69 32 20 3d 20 70 53 6f 72 74 65 72 2d 3e    i2 = pSorter->
3430: 61 54 72 65 65 5b 69 4f 75 74 2a 32 2b 31 5d 3b  aTree[iOut*2+1];
3440: 0a 20 20 7d 0a 0a 20 20 70 31 20 3d 20 26 70 53  .  }..  p1 = &pS
3450: 6f 72 74 65 72 2d 3e 61 49 74 65 72 5b 69 31 5d  orter->aIter[i1]
3460: 3b 0a 20 20 70 32 20 3d 20 26 70 53 6f 72 74 65  ;.  p2 = &pSorte
3470: 72 2d 3e 61 49 74 65 72 5b 69 32 5d 3b 0a 0a 20  r->aIter[i2];.. 
3480: 20 69 66 28 20 70 31 2d 3e 70 46 69 6c 65 3d 3d   if( p1->pFile==
3490: 30 20 29 7b 0a 20 20 20 20 69 52 65 73 20 3d 20  0 ){.    iRes = 
34a0: 69 32 3b 0a 20 20 7d 65 6c 73 65 20 69 66 28 20  i2;.  }else if( 
34b0: 70 32 2d 3e 70 46 69 6c 65 3d 3d 30 20 29 7b 0a  p2->pFile==0 ){.
34c0: 20 20 20 20 69 52 65 73 20 3d 20 69 31 3b 0a 20      iRes = i1;. 
34d0: 20 7d 65 6c 73 65 7b 0a 20 20 20 20 69 6e 74 20   }else{.    int 
34e0: 72 65 73 3b 0a 20 20 20 20 61 73 73 65 72 74 28  res;.    assert(
34f0: 20 70 43 73 72 2d 3e 70 53 6f 72 74 65 72 2d 3e   pCsr->pSorter->
3500: 70 55 6e 70 61 63 6b 65 64 21 3d 30 20 29 3b 20  pUnpacked!=0 ); 
3510: 20 2f 2a 20 61 6c 6c 6f 63 61 74 65 64 20 69 6e   /* allocated in
3520: 20 76 64 62 65 53 6f 72 74 65 72 4d 65 72 67 65   vdbeSorterMerge
3530: 28 29 20 2a 2f 0a 20 20 20 20 76 64 62 65 53 6f  () */.    vdbeSo
3540: 72 74 65 72 43 6f 6d 70 61 72 65 28 0a 20 20 20  rterCompare(.   
3550: 20 20 20 20 20 70 43 73 72 2c 20 30 2c 20 70 31       pCsr, 0, p1
3560: 2d 3e 61 4b 65 79 2c 20 70 31 2d 3e 6e 4b 65 79  ->aKey, p1->nKey
3570: 2c 20 70 32 2d 3e 61 4b 65 79 2c 20 70 32 2d 3e  , p2->aKey, p2->
3580: 6e 4b 65 79 2c 20 26 72 65 73 0a 20 20 20 20 29  nKey, &res.    )
3590: 3b 0a 20 20 20 20 69 66 28 20 72 65 73 3c 3d 30  ;.    if( res<=0
35a0: 20 29 7b 0a 20 20 20 20 20 20 69 52 65 73 20 3d   ){.      iRes =
35b0: 20 69 31 3b 0a 20 20 20 20 7d 65 6c 73 65 7b 0a   i1;.    }else{.
35c0: 20 20 20 20 20 20 69 52 65 73 20 3d 20 69 32 3b        iRes = i2;
35d0: 0a 20 20 20 20 7d 0a 20 20 7d 0a 0a 20 20 70 53  .    }.  }..  pS
35e0: 6f 72 74 65 72 2d 3e 61 54 72 65 65 5b 69 4f 75  orter->aTree[iOu
35f0: 74 5d 20 3d 20 69 52 65 73 3b 0a 20 20 72 65 74  t] = iRes;.  ret
3600: 75 72 6e 20 53 51 4c 49 54 45 5f 4f 4b 3b 0a 7d  urn SQLITE_OK;.}
3610: 0a 0a 2f 2a 0a 2a 2a 20 49 6e 69 74 69 61 6c 69  ../*.** Initiali
3620: 7a 65 20 74 68 65 20 74 65 6d 70 6f 72 61 72 79  ze the temporary
3630: 20 69 6e 64 65 78 20 63 75 72 73 6f 72 20 6a 75   index cursor ju
3640: 73 74 20 6f 70 65 6e 65 64 20 61 73 20 61 20 73  st opened as a s
3650: 6f 72 74 65 72 20 63 75 72 73 6f 72 2e 0a 2a 2f  orter cursor..*/
3660: 0a 69 6e 74 20 73 71 6c 69 74 65 33 56 64 62 65  .int sqlite3Vdbe
3670: 53 6f 72 74 65 72 49 6e 69 74 28 73 71 6c 69 74  SorterInit(sqlit
3680: 65 33 20 2a 64 62 2c 20 56 64 62 65 43 75 72 73  e3 *db, VdbeCurs
3690: 6f 72 20 2a 70 43 73 72 29 7b 0a 20 20 69 6e 74  or *pCsr){.  int
36a0: 20 70 67 73 7a 3b 20 20 20 20 20 20 20 20 20 20   pgsz;          
36b0: 20 20 20 20 20 20 20 20 20 20 20 20 20 2f 2a 20               /* 
36c0: 50 61 67 65 20 73 69 7a 65 20 6f 66 20 6d 61 69  Page size of mai
36d0: 6e 20 64 61 74 61 62 61 73 65 20 2a 2f 0a 20 20  n database */.  
36e0: 69 6e 74 20 6d 78 43 61 63 68 65 3b 20 20 20 20  int mxCache;    
36f0: 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20                  
3700: 2f 2a 20 43 61 63 68 65 20 73 69 7a 65 20 2a 2f  /* Cache size */
3710: 0a 20 20 56 64 62 65 53 6f 72 74 65 72 20 2a 70  .  VdbeSorter *p
3720: 53 6f 72 74 65 72 3b 20 20 20 20 20 20 20 20 20  Sorter;         
3730: 20 20 20 2f 2a 20 54 68 65 20 6e 65 77 20 73 6f     /* The new so
3740: 72 74 65 72 20 2a 2f 0a 20 20 63 68 61 72 20 2a  rter */.  char *
3750: 64 3b 20 20 20 20 20 20 20 20 20 20 20 20 20 20  d;              
3760: 20 20 20 20 20 20 20 20 20 20 2f 2a 20 44 75 6d            /* Dum
3770: 6d 79 20 2a 2f 0a 0a 20 20 61 73 73 65 72 74 28  my */..  assert(
3780: 20 70 43 73 72 2d 3e 70 4b 65 79 49 6e 66 6f 20   pCsr->pKeyInfo 
3790: 26 26 20 70 43 73 72 2d 3e 70 42 74 3d 3d 30 20  && pCsr->pBt==0 
37a0: 29 3b 0a 20 20 70 43 73 72 2d 3e 70 53 6f 72 74  );.  pCsr->pSort
37b0: 65 72 20 3d 20 70 53 6f 72 74 65 72 20 3d 20 73  er = pSorter = s
37c0: 71 6c 69 74 65 33 44 62 4d 61 6c 6c 6f 63 5a 65  qlite3DbMallocZe
37d0: 72 6f 28 64 62 2c 20 73 69 7a 65 6f 66 28 56 64  ro(db, sizeof(Vd
37e0: 62 65 53 6f 72 74 65 72 29 29 3b 0a 20 20 69 66  beSorter));.  if
37f0: 28 20 70 53 6f 72 74 65 72 3d 3d 30 20 29 7b 0a  ( pSorter==0 ){.
3800: 20 20 20 20 72 65 74 75 72 6e 20 53 51 4c 49 54      return SQLIT
3810: 45 5f 4e 4f 4d 45 4d 3b 0a 20 20 7d 0a 20 20 0a  E_NOMEM;.  }.  .
3820: 20 20 70 53 6f 72 74 65 72 2d 3e 70 55 6e 70 61    pSorter->pUnpa
3830: 63 6b 65 64 20 3d 20 73 71 6c 69 74 65 33 56 64  cked = sqlite3Vd
3840: 62 65 41 6c 6c 6f 63 55 6e 70 61 63 6b 65 64 52  beAllocUnpackedR
3850: 65 63 6f 72 64 28 70 43 73 72 2d 3e 70 4b 65 79  ecord(pCsr->pKey
3860: 49 6e 66 6f 2c 20 30 2c 20 30 2c 20 26 64 29 3b  Info, 0, 0, &d);
3870: 0a 20 20 69 66 28 20 70 53 6f 72 74 65 72 2d 3e  .  if( pSorter->
3880: 70 55 6e 70 61 63 6b 65 64 3d 3d 30 20 29 20 72  pUnpacked==0 ) r
3890: 65 74 75 72 6e 20 53 51 4c 49 54 45 5f 4e 4f 4d  eturn SQLITE_NOM
38a0: 45 4d 3b 0a 20 20 61 73 73 65 72 74 28 20 70 53  EM;.  assert( pS
38b0: 6f 72 74 65 72 2d 3e 70 55 6e 70 61 63 6b 65 64  orter->pUnpacked
38c0: 3d 3d 28 55 6e 70 61 63 6b 65 64 52 65 63 6f 72  ==(UnpackedRecor
38d0: 64 20 2a 29 64 20 29 3b 0a 0a 20 20 69 66 28 20  d *)d );..  if( 
38e0: 21 73 71 6c 69 74 65 33 54 65 6d 70 49 6e 4d 65  !sqlite3TempInMe
38f0: 6d 6f 72 79 28 64 62 29 20 29 7b 0a 20 20 20 20  mory(db) ){.    
3900: 70 67 73 7a 20 3d 20 73 71 6c 69 74 65 33 42 74  pgsz = sqlite3Bt
3910: 72 65 65 47 65 74 50 61 67 65 53 69 7a 65 28 64  reeGetPageSize(d
3920: 62 2d 3e 61 44 62 5b 30 5d 2e 70 42 74 29 3b 0a  b->aDb[0].pBt);.
3930: 20 20 20 20 70 53 6f 72 74 65 72 2d 3e 6d 6e 50      pSorter->mnP
3940: 6d 61 53 69 7a 65 20 3d 20 53 4f 52 54 45 52 5f  maSize = SORTER_
3950: 4d 49 4e 5f 57 4f 52 4b 49 4e 47 20 2a 20 70 67  MIN_WORKING * pg
3960: 73 7a 3b 0a 20 20 20 20 6d 78 43 61 63 68 65 20  sz;.    mxCache 
3970: 3d 20 64 62 2d 3e 61 44 62 5b 30 5d 2e 70 53 63  = db->aDb[0].pSc
3980: 68 65 6d 61 2d 3e 63 61 63 68 65 5f 73 69 7a 65  hema->cache_size
3990: 3b 0a 20 20 20 20 69 66 28 20 6d 78 43 61 63 68  ;.    if( mxCach
39a0: 65 3c 53 4f 52 54 45 52 5f 4d 49 4e 5f 57 4f 52  e<SORTER_MIN_WOR
39b0: 4b 49 4e 47 20 29 20 6d 78 43 61 63 68 65 20 3d  KING ) mxCache =
39c0: 20 53 4f 52 54 45 52 5f 4d 49 4e 5f 57 4f 52 4b   SORTER_MIN_WORK
39d0: 49 4e 47 3b 0a 20 20 20 20 70 53 6f 72 74 65 72  ING;.    pSorter
39e0: 2d 3e 6d 78 50 6d 61 53 69 7a 65 20 3d 20 6d 78  ->mxPmaSize = mx
39f0: 43 61 63 68 65 20 2a 20 70 67 73 7a 3b 0a 20 20  Cache * pgsz;.  
3a00: 7d 0a 0a 20 20 72 65 74 75 72 6e 20 53 51 4c 49  }..  return SQLI
3a10: 54 45 5f 4f 4b 3b 0a 7d 0a 0a 2f 2a 0a 2a 2a 20  TE_OK;.}../*.** 
3a20: 46 72 65 65 20 74 68 65 20 6c 69 73 74 20 6f 66  Free the list of
3a30: 20 73 6f 72 74 65 64 20 72 65 63 6f 72 64 73 20   sorted records 
3a40: 73 74 61 72 74 69 6e 67 20 61 74 20 70 52 65 63  starting at pRec
3a50: 6f 72 64 2e 0a 2a 2f 0a 73 74 61 74 69 63 20 76  ord..*/.static v
3a60: 6f 69 64 20 76 64 62 65 53 6f 72 74 65 72 52 65  oid vdbeSorterRe
3a70: 63 6f 72 64 46 72 65 65 28 73 71 6c 69 74 65 33  cordFree(sqlite3
3a80: 20 2a 64 62 2c 20 53 6f 72 74 65 72 52 65 63 6f   *db, SorterReco
3a90: 72 64 20 2a 70 52 65 63 6f 72 64 29 7b 0a 20 20  rd *pRecord){.  
3aa0: 53 6f 72 74 65 72 52 65 63 6f 72 64 20 2a 70 3b  SorterRecord *p;
3ab0: 0a 20 20 53 6f 72 74 65 72 52 65 63 6f 72 64 20  .  SorterRecord 
3ac0: 2a 70 4e 65 78 74 3b 0a 20 20 66 6f 72 28 70 3d  *pNext;.  for(p=
3ad0: 70 52 65 63 6f 72 64 3b 20 70 3b 20 70 3d 70 4e  pRecord; p; p=pN
3ae0: 65 78 74 29 7b 0a 20 20 20 20 70 4e 65 78 74 20  ext){.    pNext 
3af0: 3d 20 70 2d 3e 70 4e 65 78 74 3b 0a 20 20 20 20  = p->pNext;.    
3b00: 73 71 6c 69 74 65 33 44 62 46 72 65 65 28 64 62  sqlite3DbFree(db
3b10: 2c 20 70 29 3b 0a 20 20 7d 0a 7d 0a 0a 2f 2a 0a  , p);.  }.}../*.
3b20: 2a 2a 20 46 72 65 65 20 61 6e 79 20 63 75 72 73  ** Free any curs
3b30: 6f 72 20 63 6f 6d 70 6f 6e 65 6e 74 73 20 61 6c  or components al
3b40: 6c 6f 63 61 74 65 64 20 62 79 20 73 71 6c 69 74  located by sqlit
3b50: 65 33 56 64 62 65 53 6f 72 74 65 72 58 58 58 20  e3VdbeSorterXXX 
3b60: 72 6f 75 74 69 6e 65 73 2e 0a 2a 2f 0a 76 6f 69  routines..*/.voi
3b70: 64 20 73 71 6c 69 74 65 33 56 64 62 65 53 6f 72  d sqlite3VdbeSor
3b80: 74 65 72 43 6c 6f 73 65 28 73 71 6c 69 74 65 33  terClose(sqlite3
3b90: 20 2a 64 62 2c 20 56 64 62 65 43 75 72 73 6f 72   *db, VdbeCursor
3ba0: 20 2a 70 43 73 72 29 7b 0a 20 20 56 64 62 65 53   *pCsr){.  VdbeS
3bb0: 6f 72 74 65 72 20 2a 70 53 6f 72 74 65 72 20 3d  orter *pSorter =
3bc0: 20 70 43 73 72 2d 3e 70 53 6f 72 74 65 72 3b 0a   pCsr->pSorter;.
3bd0: 20 20 69 66 28 20 70 53 6f 72 74 65 72 20 29 7b    if( pSorter ){
3be0: 0a 20 20 20 20 69 66 28 20 70 53 6f 72 74 65 72  .    if( pSorter
3bf0: 2d 3e 61 49 74 65 72 20 29 7b 0a 20 20 20 20 20  ->aIter ){.     
3c00: 20 69 6e 74 20 69 3b 0a 20 20 20 20 20 20 66 6f   int i;.      fo
3c10: 72 28 69 3d 30 3b 20 69 3c 70 53 6f 72 74 65 72  r(i=0; i<pSorter
3c20: 2d 3e 6e 54 72 65 65 3b 20 69 2b 2b 29 7b 0a 20  ->nTree; i++){. 
3c30: 20 20 20 20 20 20 20 76 64 62 65 53 6f 72 74 65         vdbeSorte
3c40: 72 49 74 65 72 5a 65 72 6f 28 64 62 2c 20 26 70  rIterZero(db, &p
3c50: 53 6f 72 74 65 72 2d 3e 61 49 74 65 72 5b 69 5d  Sorter->aIter[i]
3c60: 29 3b 0a 20 20 20 20 20 20 7d 0a 20 20 20 20 20  );.      }.     
3c70: 20 73 71 6c 69 74 65 33 44 62 46 72 65 65 28 64   sqlite3DbFree(d
3c80: 62 2c 20 70 53 6f 72 74 65 72 2d 3e 61 49 74 65  b, pSorter->aIte
3c90: 72 29 3b 0a 20 20 20 20 7d 0a 20 20 20 20 69 66  r);.    }.    if
3ca0: 28 20 70 53 6f 72 74 65 72 2d 3e 70 54 65 6d 70  ( pSorter->pTemp
3cb0: 31 20 29 7b 0a 20 20 20 20 20 20 73 71 6c 69 74  1 ){.      sqlit
3cc0: 65 33 4f 73 43 6c 6f 73 65 46 72 65 65 28 70 53  e3OsCloseFree(pS
3cd0: 6f 72 74 65 72 2d 3e 70 54 65 6d 70 31 29 3b 0a  orter->pTemp1);.
3ce0: 20 20 20 20 7d 0a 20 20 20 20 76 64 62 65 53 6f      }.    vdbeSo
3cf0: 72 74 65 72 52 65 63 6f 72 64 46 72 65 65 28 64  rterRecordFree(d
3d00: 62 2c 20 70 53 6f 72 74 65 72 2d 3e 70 52 65 63  b, pSorter->pRec
3d10: 6f 72 64 29 3b 0a 20 20 20 20 73 71 6c 69 74 65  ord);.    sqlite
3d20: 33 44 62 46 72 65 65 28 64 62 2c 20 70 53 6f 72  3DbFree(db, pSor
3d30: 74 65 72 2d 3e 70 55 6e 70 61 63 6b 65 64 29 3b  ter->pUnpacked);
3d40: 0a 20 20 20 20 73 71 6c 69 74 65 33 44 62 46 72  .    sqlite3DbFr
3d50: 65 65 28 64 62 2c 20 70 53 6f 72 74 65 72 29 3b  ee(db, pSorter);
3d60: 0a 20 20 20 20 70 43 73 72 2d 3e 70 53 6f 72 74  .    pCsr->pSort
3d70: 65 72 20 3d 20 30 3b 0a 20 20 7d 0a 7d 0a 0a 2f  er = 0;.  }.}../
3d80: 2a 0a 2a 2a 20 41 6c 6c 6f 63 61 74 65 20 73 70  *.** Allocate sp
3d90: 61 63 65 20 66 6f 72 20 61 20 66 69 6c 65 2d 68  ace for a file-h
3da0: 61 6e 64 6c 65 20 61 6e 64 20 6f 70 65 6e 20 61  andle and open a
3db0: 20 74 65 6d 70 6f 72 61 72 79 20 66 69 6c 65 2e   temporary file.
3dc0: 20 49 66 20 73 75 63 63 65 73 73 66 75 6c 2c 0a   If successful,.
3dd0: 2a 2a 20 73 65 74 20 2a 70 70 46 69 6c 65 20 74  ** set *ppFile t
3de0: 6f 20 70 6f 69 6e 74 20 74 6f 20 74 68 65 20 6d  o point to the m
3df0: 61 6c 6c 6f 63 27 64 20 66 69 6c 65 2d 68 61 6e  alloc'd file-han
3e00: 64 6c 65 20 61 6e 64 20 72 65 74 75 72 6e 20 53  dle and return S
3e10: 51 4c 49 54 45 5f 4f 4b 2e 0a 2a 2a 20 4f 74 68  QLITE_OK..** Oth
3e20: 65 72 77 69 73 65 2c 20 73 65 74 20 2a 70 70 46  erwise, set *ppF
3e30: 69 6c 65 20 74 6f 20 30 20 61 6e 64 20 72 65 74  ile to 0 and ret
3e40: 75 72 6e 20 61 6e 20 53 51 4c 69 74 65 20 65 72  urn an SQLite er
3e50: 72 6f 72 20 63 6f 64 65 2e 0a 2a 2f 0a 73 74 61  ror code..*/.sta
3e60: 74 69 63 20 69 6e 74 20 76 64 62 65 53 6f 72 74  tic int vdbeSort
3e70: 65 72 4f 70 65 6e 54 65 6d 70 46 69 6c 65 28 73  erOpenTempFile(s
3e80: 71 6c 69 74 65 33 20 2a 64 62 2c 20 73 71 6c 69  qlite3 *db, sqli
3e90: 74 65 33 5f 66 69 6c 65 20 2a 2a 70 70 46 69 6c  te3_file **ppFil
3ea0: 65 29 7b 0a 20 20 69 6e 74 20 64 75 6d 6d 79 3b  e){.  int dummy;
3eb0: 0a 20 20 72 65 74 75 72 6e 20 73 71 6c 69 74 65  .  return sqlite
3ec0: 33 4f 73 4f 70 65 6e 4d 61 6c 6c 6f 63 28 64 62  3OsOpenMalloc(db
3ed0: 2d 3e 70 56 66 73 2c 20 30 2c 20 70 70 46 69 6c  ->pVfs, 0, ppFil
3ee0: 65 2c 0a 20 20 20 20 20 20 53 51 4c 49 54 45 5f  e,.      SQLITE_
3ef0: 4f 50 45 4e 5f 54 45 4d 50 5f 4a 4f 55 52 4e 41  OPEN_TEMP_JOURNA
3f00: 4c 20 7c 0a 20 20 20 20 20 20 53 51 4c 49 54 45  L |.      SQLITE
3f10: 5f 4f 50 45 4e 5f 52 45 41 44 57 52 49 54 45 20  _OPEN_READWRITE 
3f20: 20 20 20 7c 20 53 51 4c 49 54 45 5f 4f 50 45 4e     | SQLITE_OPEN
3f30: 5f 43 52 45 41 54 45 20 7c 0a 20 20 20 20 20 20  _CREATE |.      
3f40: 53 51 4c 49 54 45 5f 4f 50 45 4e 5f 45 58 43 4c  SQLITE_OPEN_EXCL
3f50: 55 53 49 56 45 20 20 20 20 7c 20 53 51 4c 49 54  USIVE    | SQLIT
3f60: 45 5f 4f 50 45 4e 5f 44 45 4c 45 54 45 4f 4e 43  E_OPEN_DELETEONC
3f70: 4c 4f 53 45 2c 20 26 64 75 6d 6d 79 0a 20 20 29  LOSE, &dummy.  )
3f80: 3b 0a 7d 0a 0a 2f 2a 0a 2a 2a 20 4d 65 72 67 65  ;.}../*.** Merge
3f90: 20 74 68 65 20 74 77 6f 20 73 6f 72 74 65 64 20   the two sorted 
3fa0: 6c 69 73 74 73 20 70 31 20 61 6e 64 20 70 32 20  lists p1 and p2 
3fb0: 69 6e 74 6f 20 61 20 73 69 6e 67 6c 65 20 6c 69  into a single li
3fc0: 73 74 2e 0a 2a 2a 20 53 65 74 20 2a 70 70 4f 75  st..** Set *ppOu
3fd0: 74 20 74 6f 20 74 68 65 20 68 65 61 64 20 6f 66  t to the head of
3fe0: 20 74 68 65 20 6e 65 77 20 6c 69 73 74 2e 0a 2a   the new list..*
3ff0: 2f 0a 73 74 61 74 69 63 20 76 6f 69 64 20 76 64  /.static void vd
4000: 62 65 53 6f 72 74 65 72 4d 65 72 67 65 28 0a 20  beSorterMerge(. 
4010: 20 56 64 62 65 43 75 72 73 6f 72 20 2a 70 43 73   VdbeCursor *pCs
4020: 72 2c 20 20 20 20 20 20 20 20 20 20 20 20 20 20  r,              
4030: 20 2f 2a 20 46 6f 72 20 70 4b 65 79 49 6e 66 6f   /* For pKeyInfo
4040: 20 2a 2f 0a 20 20 53 6f 72 74 65 72 52 65 63 6f   */.  SorterReco
4050: 72 64 20 2a 70 31 2c 20 20 20 20 20 20 20 20 20  rd *p1,         
4060: 20 20 20 20 20 20 2f 2a 20 46 69 72 73 74 20 6c        /* First l
4070: 69 73 74 20 74 6f 20 6d 65 72 67 65 20 2a 2f 0a  ist to merge */.
4080: 20 20 53 6f 72 74 65 72 52 65 63 6f 72 64 20 2a    SorterRecord *
4090: 70 32 2c 20 20 20 20 20 20 20 20 20 20 20 20 20  p2,             
40a0: 20 20 2f 2a 20 53 65 63 6f 6e 64 20 6c 69 73 74    /* Second list
40b0: 20 74 6f 20 6d 65 72 67 65 20 2a 2f 0a 20 20 53   to merge */.  S
40c0: 6f 72 74 65 72 52 65 63 6f 72 64 20 2a 2a 70 70  orterRecord **pp
40d0: 4f 75 74 20 20 20 20 20 20 20 20 20 20 20 20 2f  Out            /
40e0: 2a 20 4f 55 54 3a 20 48 65 61 64 20 6f 66 20 6d  * OUT: Head of m
40f0: 65 72 67 65 64 20 6c 69 73 74 20 2a 2f 0a 29 7b  erged list */.){
4100: 0a 20 20 53 6f 72 74 65 72 52 65 63 6f 72 64 20  .  SorterRecord 
4110: 2a 70 46 69 6e 61 6c 20 3d 20 30 3b 0a 20 20 53  *pFinal = 0;.  S
4120: 6f 72 74 65 72 52 65 63 6f 72 64 20 2a 2a 70 70  orterRecord **pp
4130: 20 3d 20 26 70 46 69 6e 61 6c 3b 0a 20 20 76 6f   = &pFinal;.  vo
4140: 69 64 20 2a 70 56 61 6c 32 20 3d 20 70 32 20 3f  id *pVal2 = p2 ?
4150: 20 70 32 2d 3e 70 56 61 6c 20 3a 20 30 3b 0a 0a   p2->pVal : 0;..
4160: 20 20 77 68 69 6c 65 28 20 70 31 20 26 26 20 70    while( p1 && p
4170: 32 20 29 7b 0a 20 20 20 20 69 6e 74 20 72 65 73  2 ){.    int res
4180: 3b 0a 20 20 20 20 76 64 62 65 53 6f 72 74 65 72  ;.    vdbeSorter
4190: 43 6f 6d 70 61 72 65 28 70 43 73 72 2c 20 30 2c  Compare(pCsr, 0,
41a0: 20 70 31 2d 3e 70 56 61 6c 2c 20 70 31 2d 3e 6e   p1->pVal, p1->n
41b0: 56 61 6c 2c 20 70 56 61 6c 32 2c 20 70 32 2d 3e  Val, pVal2, p2->
41c0: 6e 56 61 6c 2c 20 26 72 65 73 29 3b 0a 20 20 20  nVal, &res);.   
41d0: 20 69 66 28 20 72 65 73 3c 3d 30 20 29 7b 0a 20   if( res<=0 ){. 
41e0: 20 20 20 20 20 2a 70 70 20 3d 20 70 31 3b 0a 20       *pp = p1;. 
41f0: 20 20 20 20 20 70 70 20 3d 20 26 70 31 2d 3e 70       pp = &p1->p
4200: 4e 65 78 74 3b 0a 20 20 20 20 20 20 70 31 20 3d  Next;.      p1 =
4210: 20 70 31 2d 3e 70 4e 65 78 74 3b 0a 20 20 20 20   p1->pNext;.    
4220: 20 20 70 56 61 6c 32 20 3d 20 30 3b 0a 20 20 20    pVal2 = 0;.   
4230: 20 7d 65 6c 73 65 7b 0a 20 20 20 20 20 20 2a 70   }else{.      *p
4240: 70 20 3d 20 70 32 3b 0a 20 20 20 20 20 20 20 70  p = p2;.       p
4250: 70 20 3d 20 26 70 32 2d 3e 70 4e 65 78 74 3b 0a  p = &p2->pNext;.
4260: 20 20 20 20 20 20 70 32 20 3d 20 70 32 2d 3e 70        p2 = p2->p
4270: 4e 65 78 74 3b 0a 20 20 20 20 20 20 69 66 28 20  Next;.      if( 
4280: 70 32 3d 3d 30 20 29 20 62 72 65 61 6b 3b 0a 20  p2==0 ) break;. 
4290: 20 20 20 20 20 70 56 61 6c 32 20 3d 20 70 32 2d       pVal2 = p2-
42a0: 3e 70 56 61 6c 3b 0a 20 20 20 20 7d 0a 20 20 7d  >pVal;.    }.  }
42b0: 0a 20 20 2a 70 70 20 3d 20 70 31 20 3f 20 70 31  .  *pp = p1 ? p1
42c0: 20 3a 20 70 32 3b 0a 20 20 2a 70 70 4f 75 74 20   : p2;.  *ppOut 
42d0: 3d 20 70 46 69 6e 61 6c 3b 0a 7d 0a 0a 2f 2a 0a  = pFinal;.}../*.
42e0: 2a 2a 20 53 6f 72 74 20 74 68 65 20 6c 69 6e 6b  ** Sort the link
42f0: 65 64 20 6c 69 73 74 20 6f 66 20 72 65 63 6f 72  ed list of recor
4300: 64 73 20 68 65 61 64 65 64 20 61 74 20 70 43 73  ds headed at pCs
4310: 72 2d 3e 70 52 65 63 6f 72 64 2e 20 52 65 74 75  r->pRecord. Retu
4320: 72 6e 20 53 51 4c 49 54 45 5f 4f 4b 0a 2a 2a 20  rn SQLITE_OK.** 
4330: 69 66 20 73 75 63 63 65 73 73 66 75 6c 2c 20 6f  if successful, o
4340: 72 20 61 6e 20 53 51 4c 69 74 65 20 65 72 72 6f  r an SQLite erro
4350: 72 20 63 6f 64 65 20 28 69 2e 65 2e 20 53 51 4c  r code (i.e. SQL
4360: 49 54 45 5f 4e 4f 4d 45 4d 29 20 69 66 20 61 6e  ITE_NOMEM) if an
4370: 20 65 72 72 6f 72 0a 2a 2a 20 6f 63 63 75 72 73   error.** occurs
4380: 2e 0a 2a 2f 0a 73 74 61 74 69 63 20 69 6e 74 20  ..*/.static int 
4390: 76 64 62 65 53 6f 72 74 65 72 53 6f 72 74 28 56  vdbeSorterSort(V
43a0: 64 62 65 43 75 72 73 6f 72 20 2a 70 43 73 72 29  dbeCursor *pCsr)
43b0: 7b 0a 20 20 69 6e 74 20 69 3b 0a 20 20 53 6f 72  {.  int i;.  Sor
43c0: 74 65 72 52 65 63 6f 72 64 20 2a 2a 61 53 6c 6f  terRecord **aSlo
43d0: 74 3b 0a 20 20 53 6f 72 74 65 72 52 65 63 6f 72  t;.  SorterRecor
43e0: 64 20 2a 70 3b 0a 20 20 56 64 62 65 53 6f 72 74  d *p;.  VdbeSort
43f0: 65 72 20 2a 70 53 6f 72 74 65 72 20 3d 20 70 43  er *pSorter = pC
4400: 73 72 2d 3e 70 53 6f 72 74 65 72 3b 0a 0a 20 20  sr->pSorter;..  
4410: 61 53 6c 6f 74 20 3d 20 28 53 6f 72 74 65 72 52  aSlot = (SorterR
4420: 65 63 6f 72 64 20 2a 2a 29 73 71 6c 69 74 65 33  ecord **)sqlite3
4430: 4d 61 6c 6c 6f 63 5a 65 72 6f 28 36 34 20 2a 20  MallocZero(64 * 
4440: 73 69 7a 65 6f 66 28 53 6f 72 74 65 72 52 65 63  sizeof(SorterRec
4450: 6f 72 64 20 2a 29 29 3b 0a 20 20 69 66 28 20 21  ord *));.  if( !
4460: 61 53 6c 6f 74 20 29 7b 0a 20 20 20 20 72 65 74  aSlot ){.    ret
4470: 75 72 6e 20 53 51 4c 49 54 45 5f 4e 4f 4d 45 4d  urn SQLITE_NOMEM
4480: 3b 0a 20 20 7d 0a 0a 20 20 70 20 3d 20 70 53 6f  ;.  }..  p = pSo
4490: 72 74 65 72 2d 3e 70 52 65 63 6f 72 64 3b 0a 20  rter->pRecord;. 
44a0: 20 77 68 69 6c 65 28 20 70 20 29 7b 0a 20 20 20   while( p ){.   
44b0: 20 53 6f 72 74 65 72 52 65 63 6f 72 64 20 2a 70   SorterRecord *p
44c0: 4e 65 78 74 20 3d 20 70 2d 3e 70 4e 65 78 74 3b  Next = p->pNext;
44d0: 0a 20 20 20 20 70 2d 3e 70 4e 65 78 74 20 3d 20  .    p->pNext = 
44e0: 30 3b 0a 20 20 20 20 66 6f 72 28 69 3d 30 3b 20  0;.    for(i=0; 
44f0: 61 53 6c 6f 74 5b 69 5d 3b 20 69 2b 2b 29 7b 0a  aSlot[i]; i++){.
4500: 20 20 20 20 20 20 76 64 62 65 53 6f 72 74 65 72        vdbeSorter
4510: 4d 65 72 67 65 28 70 43 73 72 2c 20 70 2c 20 61  Merge(pCsr, p, a
4520: 53 6c 6f 74 5b 69 5d 2c 20 26 70 29 3b 0a 20 20  Slot[i], &p);.  
4530: 20 20 20 20 61 53 6c 6f 74 5b 69 5d 20 3d 20 30      aSlot[i] = 0
4540: 3b 0a 20 20 20 20 7d 0a 20 20 20 20 61 53 6c 6f  ;.    }.    aSlo
4550: 74 5b 69 5d 20 3d 20 70 3b 0a 20 20 20 20 70 20  t[i] = p;.    p 
4560: 3d 20 70 4e 65 78 74 3b 0a 20 20 7d 0a 0a 20 20  = pNext;.  }..  
4570: 70 20 3d 20 30 3b 0a 20 20 66 6f 72 28 69 3d 30  p = 0;.  for(i=0
4580: 3b 20 69 3c 36 34 3b 20 69 2b 2b 29 7b 0a 20 20  ; i<64; i++){.  
4590: 20 20 76 64 62 65 53 6f 72 74 65 72 4d 65 72 67    vdbeSorterMerg
45a0: 65 28 70 43 73 72 2c 20 70 2c 20 61 53 6c 6f 74  e(pCsr, p, aSlot
45b0: 5b 69 5d 2c 20 26 70 29 3b 0a 20 20 7d 0a 20 20  [i], &p);.  }.  
45c0: 70 53 6f 72 74 65 72 2d 3e 70 52 65 63 6f 72 64  pSorter->pRecord
45d0: 20 3d 20 70 3b 0a 0a 20 20 73 71 6c 69 74 65 33   = p;..  sqlite3
45e0: 5f 66 72 65 65 28 61 53 6c 6f 74 29 3b 0a 20 20  _free(aSlot);.  
45f0: 72 65 74 75 72 6e 20 53 51 4c 49 54 45 5f 4f 4b  return SQLITE_OK
4600: 3b 0a 7d 0a 0a 0a 2f 2a 0a 2a 2a 20 57 72 69 74  ;.}.../*.** Writ
4610: 65 20 74 68 65 20 63 75 72 72 65 6e 74 20 63 6f  e the current co
4620: 6e 74 65 6e 74 73 20 6f 66 20 74 68 65 20 69 6e  ntents of the in
4630: 2d 6d 65 6d 6f 72 79 20 6c 69 6e 6b 65 64 2d 6c  -memory linked-l
4640: 69 73 74 20 74 6f 20 61 20 50 4d 41 2e 20 52 65  ist to a PMA. Re
4650: 74 75 72 6e 0a 2a 2a 20 53 51 4c 49 54 45 5f 4f  turn.** SQLITE_O
4660: 4b 20 69 66 20 73 75 63 63 65 73 73 66 75 6c 2c  K if successful,
4670: 20 6f 72 20 61 6e 20 53 51 4c 69 74 65 20 65 72   or an SQLite er
4680: 72 6f 72 20 63 6f 64 65 20 6f 74 68 65 72 77 69  ror code otherwi
4690: 73 65 2e 0a 2a 2a 0a 2a 2a 20 54 68 65 20 66 6f  se..**.** The fo
46a0: 72 6d 61 74 20 6f 66 20 61 20 50 4d 41 20 69 73  rmat of a PMA is
46b0: 3a 0a 2a 2a 0a 2a 2a 20 20 20 20 20 2a 20 41 20  :.**.**     * A 
46c0: 76 61 72 69 6e 74 2e 20 54 68 69 73 20 76 61 72  varint. This var
46d0: 69 6e 74 20 63 6f 6e 74 61 69 6e 73 20 74 68 65  int contains the
46e0: 20 74 6f 74 61 6c 20 6e 75 6d 62 65 72 20 6f 66   total number of
46f0: 20 62 79 74 65 73 20 6f 66 20 63 6f 6e 74 65 6e   bytes of conten
4700: 74 0a 2a 2a 20 20 20 20 20 20 20 69 6e 20 74 68  t.**       in th
4710: 65 20 50 4d 41 20 28 6e 6f 74 20 69 6e 63 6c 75  e PMA (not inclu
4720: 64 69 6e 67 20 74 68 65 20 76 61 72 69 6e 74 20  ding the varint 
4730: 69 74 73 65 6c 66 29 2e 0a 2a 2a 0a 2a 2a 20 20  itself)..**.**  
4740: 20 20 20 2a 20 4f 6e 65 20 6f 72 20 6d 6f 72 65     * One or more
4750: 20 72 65 63 6f 72 64 73 20 70 61 63 6b 65 64 20   records packed 
4760: 65 6e 64 2d 74 6f 2d 65 6e 64 20 69 6e 20 6f 72  end-to-end in or
4770: 64 65 72 20 6f 66 20 61 73 63 65 6e 64 69 6e 67  der of ascending
4780: 20 6b 65 79 73 2e 20 0a 2a 2a 20 20 20 20 20 20   keys. .**      
4790: 20 45 61 63 68 20 72 65 63 6f 72 64 20 63 6f 6e   Each record con
47a0: 73 69 73 74 73 20 6f 66 20 61 20 76 61 72 69 6e  sists of a varin
47b0: 74 20 66 6f 6c 6c 6f 77 65 64 20 62 79 20 61 20  t followed by a 
47c0: 62 6c 6f 62 20 6f 66 20 64 61 74 61 20 28 74 68  blob of data (th
47d0: 65 20 0a 2a 2a 20 20 20 20 20 20 20 6b 65 79 29  e .**       key)
47e0: 2e 20 54 68 65 20 76 61 72 69 6e 74 20 69 73 20  . The varint is 
47f0: 74 68 65 20 6e 75 6d 62 65 72 20 6f 66 20 62 79  the number of by
4800: 74 65 73 20 69 6e 20 74 68 65 20 62 6c 6f 62 20  tes in the blob 
4810: 6f 66 20 64 61 74 61 2e 0a 2a 2f 0a 73 74 61 74  of data..*/.stat
4820: 69 63 20 69 6e 74 20 76 64 62 65 53 6f 72 74 65  ic int vdbeSorte
4830: 72 4c 69 73 74 54 6f 50 4d 41 28 73 71 6c 69 74  rListToPMA(sqlit
4840: 65 33 20 2a 64 62 2c 20 56 64 62 65 43 75 72 73  e3 *db, VdbeCurs
4850: 6f 72 20 2a 70 43 73 72 29 7b 0a 20 20 69 6e 74  or *pCsr){.  int
4860: 20 72 63 20 3d 20 53 51 4c 49 54 45 5f 4f 4b 3b   rc = SQLITE_OK;
4870: 20 20 20 20 20 20 20 20 20 20 20 20 20 2f 2a 20               /* 
4880: 52 65 74 75 72 6e 20 63 6f 64 65 20 2a 2f 0a 20  Return code */. 
4890: 20 56 64 62 65 53 6f 72 74 65 72 20 2a 70 53 6f   VdbeSorter *pSo
48a0: 72 74 65 72 20 3d 20 70 43 73 72 2d 3e 70 53 6f  rter = pCsr->pSo
48b0: 72 74 65 72 3b 0a 0a 20 20 69 66 28 20 70 53 6f  rter;..  if( pSo
48c0: 72 74 65 72 2d 3e 6e 49 6e 4d 65 6d 6f 72 79 3d  rter->nInMemory=
48d0: 3d 30 20 29 7b 0a 20 20 20 20 61 73 73 65 72 74  =0 ){.    assert
48e0: 28 20 70 53 6f 72 74 65 72 2d 3e 70 52 65 63 6f  ( pSorter->pReco
48f0: 72 64 3d 3d 30 20 29 3b 0a 20 20 20 20 72 65 74  rd==0 );.    ret
4900: 75 72 6e 20 72 63 3b 0a 20 20 7d 0a 0a 20 20 72  urn rc;.  }..  r
4910: 63 20 3d 20 76 64 62 65 53 6f 72 74 65 72 53 6f  c = vdbeSorterSo
4920: 72 74 28 70 43 73 72 29 3b 0a 0a 20 20 2f 2a 20  rt(pCsr);..  /* 
4930: 49 66 20 74 68 65 20 66 69 72 73 74 20 74 65 6d  If the first tem
4940: 70 6f 72 61 72 79 20 50 4d 41 20 66 69 6c 65 20  porary PMA file 
4950: 68 61 73 20 6e 6f 74 20 62 65 65 6e 20 6f 70 65  has not been ope
4960: 6e 65 64 2c 20 6f 70 65 6e 20 69 74 20 6e 6f 77  ned, open it now
4970: 2e 20 2a 2f 0a 20 20 69 66 28 20 72 63 3d 3d 53  . */.  if( rc==S
4980: 51 4c 49 54 45 5f 4f 4b 20 26 26 20 70 53 6f 72  QLITE_OK && pSor
4990: 74 65 72 2d 3e 70 54 65 6d 70 31 3d 3d 30 20 29  ter->pTemp1==0 )
49a0: 7b 0a 20 20 20 20 72 63 20 3d 20 76 64 62 65 53  {.    rc = vdbeS
49b0: 6f 72 74 65 72 4f 70 65 6e 54 65 6d 70 46 69 6c  orterOpenTempFil
49c0: 65 28 64 62 2c 20 26 70 53 6f 72 74 65 72 2d 3e  e(db, &pSorter->
49d0: 70 54 65 6d 70 31 29 3b 0a 20 20 20 20 61 73 73  pTemp1);.    ass
49e0: 65 72 74 28 20 72 63 21 3d 53 51 4c 49 54 45 5f  ert( rc!=SQLITE_
49f0: 4f 4b 20 7c 7c 20 70 53 6f 72 74 65 72 2d 3e 70  OK || pSorter->p
4a00: 54 65 6d 70 31 20 29 3b 0a 20 20 20 20 61 73 73  Temp1 );.    ass
4a10: 65 72 74 28 20 70 53 6f 72 74 65 72 2d 3e 69 57  ert( pSorter->iW
4a20: 72 69 74 65 4f 66 66 3d 3d 30 20 29 3b 0a 20 20  riteOff==0 );.  
4a30: 20 20 61 73 73 65 72 74 28 20 70 53 6f 72 74 65    assert( pSorte
4a40: 72 2d 3e 6e 50 4d 41 3d 3d 30 20 29 3b 0a 20 20  r->nPMA==0 );.  
4a50: 7d 0a 0a 20 20 69 66 28 20 72 63 3d 3d 53 51 4c  }..  if( rc==SQL
4a60: 49 54 45 5f 4f 4b 20 29 7b 0a 20 20 20 20 69 36  ITE_OK ){.    i6
4a70: 34 20 69 4f 66 66 20 3d 20 70 53 6f 72 74 65 72  4 iOff = pSorter
4a80: 2d 3e 69 57 72 69 74 65 4f 66 66 3b 0a 20 20 20  ->iWriteOff;.   
4a90: 20 53 6f 72 74 65 72 52 65 63 6f 72 64 20 2a 70   SorterRecord *p
4aa0: 3b 0a 20 20 20 20 53 6f 72 74 65 72 52 65 63 6f  ;.    SorterReco
4ab0: 72 64 20 2a 70 4e 65 78 74 20 3d 20 30 3b 0a 20  rd *pNext = 0;. 
4ac0: 20 20 20 73 74 61 74 69 63 20 63 6f 6e 73 74 20     static const 
4ad0: 63 68 61 72 20 65 69 67 68 74 5a 65 72 6f 73 5b  char eightZeros[
4ae0: 38 5d 20 3d 20 7b 20 30 2c 20 30 2c 20 30 2c 20  8] = { 0, 0, 0, 
4af0: 30 2c 20 30 2c 20 30 2c 20 30 2c 20 30 20 7d 3b  0, 0, 0, 0, 0 };
4b00: 0a 0a 20 20 20 20 70 53 6f 72 74 65 72 2d 3e 6e  ..    pSorter->n
4b10: 50 4d 41 2b 2b 3b 0a 20 20 20 20 72 63 20 3d 20  PMA++;.    rc = 
4b20: 76 64 62 65 53 6f 72 74 65 72 57 72 69 74 65 56  vdbeSorterWriteV
4b30: 61 72 69 6e 74 28 70 53 6f 72 74 65 72 2d 3e 70  arint(pSorter->p
4b40: 54 65 6d 70 31 2c 20 70 53 6f 72 74 65 72 2d 3e  Temp1, pSorter->
4b50: 6e 49 6e 4d 65 6d 6f 72 79 2c 20 26 69 4f 66 66  nInMemory, &iOff
4b60: 29 3b 0a 20 20 20 20 66 6f 72 28 70 3d 70 53 6f  );.    for(p=pSo
4b70: 72 74 65 72 2d 3e 70 52 65 63 6f 72 64 3b 20 72  rter->pRecord; r
4b80: 63 3d 3d 53 51 4c 49 54 45 5f 4f 4b 20 26 26 20  c==SQLITE_OK && 
4b90: 70 3b 20 70 3d 70 4e 65 78 74 29 7b 0a 20 20 20  p; p=pNext){.   
4ba0: 20 20 20 70 4e 65 78 74 20 3d 20 70 2d 3e 70 4e     pNext = p->pN
4bb0: 65 78 74 3b 0a 20 20 20 20 20 20 72 63 20 3d 20  ext;.      rc = 
4bc0: 76 64 62 65 53 6f 72 74 65 72 57 72 69 74 65 56  vdbeSorterWriteV
4bd0: 61 72 69 6e 74 28 70 53 6f 72 74 65 72 2d 3e 70  arint(pSorter->p
4be0: 54 65 6d 70 31 2c 20 70 2d 3e 6e 56 61 6c 2c 20  Temp1, p->nVal, 
4bf0: 26 69 4f 66 66 29 3b 0a 0a 20 20 20 20 20 20 69  &iOff);..      i
4c00: 66 28 20 72 63 3d 3d 53 51 4c 49 54 45 5f 4f 4b  f( rc==SQLITE_OK
4c10: 20 29 7b 0a 20 20 20 20 20 20 20 20 72 63 20 3d   ){.        rc =
4c20: 20 73 71 6c 69 74 65 33 4f 73 57 72 69 74 65 28   sqlite3OsWrite(
4c30: 70 53 6f 72 74 65 72 2d 3e 70 54 65 6d 70 31 2c  pSorter->pTemp1,
4c40: 20 70 2d 3e 70 56 61 6c 2c 20 70 2d 3e 6e 56 61   p->pVal, p->nVa
4c50: 6c 2c 20 69 4f 66 66 29 3b 0a 20 20 20 20 20 20  l, iOff);.      
4c60: 20 20 69 4f 66 66 20 2b 3d 20 70 2d 3e 6e 56 61    iOff += p->nVa
4c70: 6c 3b 0a 20 20 20 20 20 20 7d 0a 0a 20 20 20 20  l;.      }..    
4c80: 20 20 73 71 6c 69 74 65 33 44 62 46 72 65 65 28    sqlite3DbFree(
4c90: 64 62 2c 20 70 29 3b 0a 20 20 20 20 7d 0a 0a 20  db, p);.    }.. 
4ca0: 20 20 20 2f 2a 20 54 68 69 73 20 61 73 73 65 72     /* This asser
4cb0: 74 20 76 65 72 69 66 69 65 73 20 74 68 61 74 20  t verifies that 
4cc0: 75 6e 6c 65 73 73 20 61 6e 20 65 72 72 6f 72 20  unless an error 
4cd0: 68 61 73 20 6f 63 63 75 72 72 65 64 2c 20 74 68  has occurred, th
4ce0: 65 20 73 69 7a 65 20 6f 66 20 0a 20 20 20 20 2a  e size of .    *
4cf0: 2a 20 74 68 65 20 50 4d 41 20 6f 6e 20 64 69 73  * the PMA on dis
4d00: 6b 20 69 73 20 74 68 65 20 73 61 6d 65 20 61 73  k is the same as
4d10: 20 74 68 65 20 65 78 70 65 63 74 65 64 20 73 69   the expected si
4d20: 7a 65 20 73 74 6f 72 65 64 20 69 6e 0a 20 20 20  ze stored in.   
4d30: 20 2a 2a 20 70 53 6f 72 74 65 72 2d 3e 6e 49 6e   ** pSorter->nIn
4d40: 4d 65 6d 6f 72 79 2e 20 2a 2f 20 0a 20 20 20 20  Memory. */ .    
4d50: 61 73 73 65 72 74 28 20 72 63 21 3d 53 51 4c 49  assert( rc!=SQLI
4d60: 54 45 5f 4f 4b 20 7c 7c 20 70 53 6f 72 74 65 72  TE_OK || pSorter
4d70: 2d 3e 6e 49 6e 4d 65 6d 6f 72 79 3d 3d 28 0a 20  ->nInMemory==(. 
4d80: 20 20 20 20 20 20 20 20 20 69 4f 66 66 2d 70 53           iOff-pS
4d90: 6f 72 74 65 72 2d 3e 69 57 72 69 74 65 4f 66 66  orter->iWriteOff
4da0: 2d 73 71 6c 69 74 65 33 56 61 72 69 6e 74 4c 65  -sqlite3VarintLe
4db0: 6e 28 70 53 6f 72 74 65 72 2d 3e 6e 49 6e 4d 65  n(pSorter->nInMe
4dc0: 6d 6f 72 79 29 0a 20 20 20 20 29 29 3b 0a 0a 20  mory).    ));.. 
4dd0: 20 20 20 70 53 6f 72 74 65 72 2d 3e 69 57 72 69     pSorter->iWri
4de0: 74 65 4f 66 66 20 3d 20 69 4f 66 66 3b 0a 20 20  teOff = iOff;.  
4df0: 20 20 69 66 28 20 72 63 3d 3d 53 51 4c 49 54 45    if( rc==SQLITE
4e00: 5f 4f 4b 20 29 7b 0a 20 20 20 20 20 20 2f 2a 20  _OK ){.      /* 
4e10: 54 65 72 6d 69 6e 61 74 65 20 65 61 63 68 20 66  Terminate each f
4e20: 69 6c 65 20 77 69 74 68 20 38 20 65 78 74 72 61  ile with 8 extra
4e30: 20 62 79 74 65 73 20 73 6f 20 74 68 61 74 20 66   bytes so that f
4e40: 72 6f 6d 20 61 6e 79 20 6f 66 66 73 65 74 0a 20  rom any offset. 
4e50: 20 20 20 20 20 2a 2a 20 69 6e 20 74 68 65 20 66       ** in the f
4e60: 69 6c 65 20 77 65 20 63 61 6e 20 61 6c 77 61 79  ile we can alway
4e70: 73 20 72 65 61 64 20 39 20 62 79 74 65 73 20 77  s read 9 bytes w
4e80: 69 74 68 6f 75 74 20 61 20 53 48 4f 52 54 5f 52  ithout a SHORT_R
4e90: 45 41 44 20 65 72 72 6f 72 20 2a 2f 0a 20 20 20  EAD error */.   
4ea0: 20 20 20 72 63 20 3d 20 73 71 6c 69 74 65 33 4f     rc = sqlite3O
4eb0: 73 57 72 69 74 65 28 70 53 6f 72 74 65 72 2d 3e  sWrite(pSorter->
4ec0: 70 54 65 6d 70 31 2c 20 65 69 67 68 74 5a 65 72  pTemp1, eightZer
4ed0: 6f 73 2c 20 38 2c 20 69 4f 66 66 29 3b 0a 20 20  os, 8, iOff);.  
4ee0: 20 20 7d 0a 20 20 20 20 70 53 6f 72 74 65 72 2d    }.    pSorter-
4ef0: 3e 70 52 65 63 6f 72 64 20 3d 20 70 3b 0a 20 20  >pRecord = p;.  
4f00: 7d 0a 0a 20 20 72 65 74 75 72 6e 20 72 63 3b 0a  }..  return rc;.
4f10: 7d 0a 0a 2f 2a 0a 2a 2a 20 41 64 64 20 61 20 72  }../*.** Add a r
4f20: 65 63 6f 72 64 20 74 6f 20 74 68 65 20 73 6f 72  ecord to the sor
4f30: 74 65 72 2e 0a 2a 2f 0a 69 6e 74 20 73 71 6c 69  ter..*/.int sqli
4f40: 74 65 33 56 64 62 65 53 6f 72 74 65 72 57 72 69  te3VdbeSorterWri
4f50: 74 65 28 0a 20 20 73 71 6c 69 74 65 33 20 2a 64  te(.  sqlite3 *d
4f60: 62 2c 20 20 20 20 20 20 20 20 20 20 20 20 20 20  b,              
4f70: 20 20 20 20 20 20 2f 2a 20 44 61 74 61 62 61 73        /* Databas
4f80: 65 20 68 61 6e 64 6c 65 20 2a 2f 0a 20 20 56 64  e handle */.  Vd
4f90: 62 65 43 75 72 73 6f 72 20 2a 70 43 73 72 2c 20  beCursor *pCsr, 
4fa0: 20 20 20 20 20 20 20 20 20 20 20 20 20 20 2f 2a                /*
4fb0: 20 53 6f 72 74 65 72 20 63 75 72 73 6f 72 20 2a   Sorter cursor *
4fc0: 2f 0a 20 20 4d 65 6d 20 2a 70 56 61 6c 20 20 20  /.  Mem *pVal   
4fd0: 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20                  
4fe0: 20 20 20 20 2f 2a 20 4d 65 6d 6f 72 79 20 63 65      /* Memory ce
4ff0: 6c 6c 20 63 6f 6e 74 61 69 6e 69 6e 67 20 72 65  ll containing re
5000: 63 6f 72 64 20 2a 2f 0a 29 7b 0a 20 20 56 64 62  cord */.){.  Vdb
5010: 65 53 6f 72 74 65 72 20 2a 70 53 6f 72 74 65 72  eSorter *pSorter
5020: 20 3d 20 70 43 73 72 2d 3e 70 53 6f 72 74 65 72   = pCsr->pSorter
5030: 3b 0a 20 20 69 6e 74 20 72 63 20 3d 20 53 51 4c  ;.  int rc = SQL
5040: 49 54 45 5f 4f 4b 3b 20 20 20 20 20 20 20 20 20  ITE_OK;         
5050: 20 20 20 20 2f 2a 20 52 65 74 75 72 6e 20 43 6f      /* Return Co
5060: 64 65 20 2a 2f 0a 20 20 53 6f 72 74 65 72 52 65  de */.  SorterRe
5070: 63 6f 72 64 20 2a 70 4e 65 77 3b 20 20 20 20 20  cord *pNew;     
5080: 20 20 20 20 20 20 20 20 2f 2a 20 4e 65 77 20 6c          /* New l
5090: 69 73 74 20 65 6c 65 6d 65 6e 74 20 2a 2f 0a 0a  ist element */..
50a0: 20 20 61 73 73 65 72 74 28 20 70 53 6f 72 74 65    assert( pSorte
50b0: 72 20 29 3b 0a 20 20 70 53 6f 72 74 65 72 2d 3e  r );.  pSorter->
50c0: 6e 49 6e 4d 65 6d 6f 72 79 20 2b 3d 20 73 71 6c  nInMemory += sql
50d0: 69 74 65 33 56 61 72 69 6e 74 4c 65 6e 28 70 56  ite3VarintLen(pV
50e0: 61 6c 2d 3e 6e 29 20 2b 20 70 56 61 6c 2d 3e 6e  al->n) + pVal->n
50f0: 3b 0a 0a 20 20 70 4e 65 77 20 3d 20 28 53 6f 72  ;..  pNew = (Sor
5100: 74 65 72 52 65 63 6f 72 64 20 2a 29 73 71 6c 69  terRecord *)sqli
5110: 74 65 33 44 62 4d 61 6c 6c 6f 63 52 61 77 28 64  te3DbMallocRaw(d
5120: 62 2c 20 70 56 61 6c 2d 3e 6e 20 2b 20 73 69 7a  b, pVal->n + siz
5130: 65 6f 66 28 53 6f 72 74 65 72 52 65 63 6f 72 64  eof(SorterRecord
5140: 29 29 3b 0a 20 20 69 66 28 20 70 4e 65 77 3d 3d  ));.  if( pNew==
5150: 30 20 29 7b 0a 20 20 20 20 72 63 20 3d 20 53 51  0 ){.    rc = SQ
5160: 4c 49 54 45 5f 4e 4f 4d 45 4d 3b 0a 20 20 7d 65  LITE_NOMEM;.  }e
5170: 6c 73 65 7b 0a 20 20 20 20 70 4e 65 77 2d 3e 70  lse{.    pNew->p
5180: 56 61 6c 20 3d 20 28 76 6f 69 64 20 2a 29 26 70  Val = (void *)&p
5190: 4e 65 77 5b 31 5d 3b 0a 20 20 20 20 6d 65 6d 63  New[1];.    memc
51a0: 70 79 28 70 4e 65 77 2d 3e 70 56 61 6c 2c 20 70  py(pNew->pVal, p
51b0: 56 61 6c 2d 3e 7a 2c 20 70 56 61 6c 2d 3e 6e 29  Val->z, pVal->n)
51c0: 3b 0a 20 20 20 20 70 4e 65 77 2d 3e 6e 56 61 6c  ;.    pNew->nVal
51d0: 20 3d 20 70 56 61 6c 2d 3e 6e 3b 0a 20 20 20 20   = pVal->n;.    
51e0: 70 4e 65 77 2d 3e 70 4e 65 78 74 20 3d 20 70 53  pNew->pNext = pS
51f0: 6f 72 74 65 72 2d 3e 70 52 65 63 6f 72 64 3b 0a  orter->pRecord;.
5200: 20 20 20 20 70 53 6f 72 74 65 72 2d 3e 70 52 65      pSorter->pRe
5210: 63 6f 72 64 20 3d 20 70 4e 65 77 3b 0a 20 20 7d  cord = pNew;.  }
5220: 0a 0a 20 20 2f 2a 20 53 65 65 20 69 66 20 74 68  ..  /* See if th
5230: 65 20 63 6f 6e 74 65 6e 74 73 20 6f 66 20 74 68  e contents of th
5240: 65 20 73 6f 72 74 65 72 20 73 68 6f 75 6c 64 20  e sorter should 
5250: 6e 6f 77 20 62 65 20 77 72 69 74 74 65 6e 20 6f  now be written o
5260: 75 74 2e 20 54 68 65 79 0a 20 20 2a 2a 20 61 72  ut. They.  ** ar
5270: 65 20 77 72 69 74 74 65 6e 20 6f 75 74 20 77 68  e written out wh
5280: 65 6e 20 65 69 74 68 65 72 20 6f 66 20 74 68 65  en either of the
5290: 20 66 6f 6c 6c 6f 77 69 6e 67 20 61 72 65 20 74   following are t
52a0: 72 75 65 3a 0a 20 20 2a 2a 0a 20 20 2a 2a 20 20  rue:.  **.  **  
52b0: 20 2a 20 54 68 65 20 74 6f 74 61 6c 20 6d 65 6d   * The total mem
52c0: 6f 72 79 20 61 6c 6c 6f 63 61 74 65 64 20 66 6f  ory allocated fo
52d0: 72 20 74 68 65 20 69 6e 2d 6d 65 6d 6f 72 79 20  r the in-memory 
52e0: 6c 69 73 74 20 69 73 20 67 72 65 61 74 65 72 20  list is greater 
52f0: 0a 20 20 2a 2a 20 20 20 20 20 74 68 61 6e 20 28  .  **     than (
5300: 70 61 67 65 2d 73 69 7a 65 20 2a 20 63 61 63 68  page-size * cach
5310: 65 2d 73 69 7a 65 29 2c 20 6f 72 0a 20 20 2a 2a  e-size), or.  **
5320: 0a 20 20 2a 2a 20 20 20 2a 20 54 68 65 20 74 6f  .  **   * The to
5330: 74 61 6c 20 6d 65 6d 6f 72 79 20 61 6c 6c 6f 63  tal memory alloc
5340: 61 74 65 64 20 66 6f 72 20 74 68 65 20 69 6e 2d  ated for the in-
5350: 6d 65 6d 6f 72 79 20 6c 69 73 74 20 69 73 20 67  memory list is g
5360: 72 65 61 74 65 72 20 0a 20 20 2a 2a 20 20 20 20  reater .  **    
5370: 20 74 68 61 6e 20 28 70 61 67 65 2d 73 69 7a 65   than (page-size
5380: 20 2a 20 31 30 29 20 61 6e 64 20 73 71 6c 69 74   * 10) and sqlit
5390: 65 33 48 65 61 70 4e 65 61 72 6c 79 46 75 6c 6c  e3HeapNearlyFull
53a0: 28 29 20 72 65 74 75 72 6e 73 20 74 72 75 65 2e  () returns true.
53b0: 0a 20 20 2a 2f 0a 20 20 69 66 28 20 72 63 3d 3d  .  */.  if( rc==
53c0: 53 51 4c 49 54 45 5f 4f 4b 20 26 26 20 70 53 6f  SQLITE_OK && pSo
53d0: 72 74 65 72 2d 3e 6d 78 50 6d 61 53 69 7a 65 3e  rter->mxPmaSize>
53e0: 30 20 26 26 20 28 0a 20 20 20 20 20 20 20 20 28  0 && (.        (
53f0: 70 53 6f 72 74 65 72 2d 3e 6e 49 6e 4d 65 6d 6f  pSorter->nInMemo
5400: 72 79 3e 70 53 6f 72 74 65 72 2d 3e 6d 78 50 6d  ry>pSorter->mxPm
5410: 61 53 69 7a 65 29 0a 20 20 20 20 20 7c 7c 20 28  aSize).     || (
5420: 70 53 6f 72 74 65 72 2d 3e 6e 49 6e 4d 65 6d 6f  pSorter->nInMemo
5430: 72 79 3e 70 53 6f 72 74 65 72 2d 3e 6d 6e 50 6d  ry>pSorter->mnPm
5440: 61 53 69 7a 65 20 26 26 20 73 71 6c 69 74 65 33  aSize && sqlite3
5450: 48 65 61 70 4e 65 61 72 6c 79 46 75 6c 6c 28 29  HeapNearlyFull()
5460: 29 0a 20 20 29 29 7b 0a 20 20 20 20 72 63 20 3d  ).  )){.    rc =
5470: 20 76 64 62 65 53 6f 72 74 65 72 4c 69 73 74 54   vdbeSorterListT
5480: 6f 50 4d 41 28 64 62 2c 20 70 43 73 72 29 3b 0a  oPMA(db, pCsr);.
5490: 20 20 20 20 70 53 6f 72 74 65 72 2d 3e 6e 49 6e      pSorter->nIn
54a0: 4d 65 6d 6f 72 79 20 3d 20 30 3b 0a 20 20 7d 0a  Memory = 0;.  }.
54b0: 0a 20 20 72 65 74 75 72 6e 20 72 63 3b 0a 7d 0a  .  return rc;.}.
54c0: 0a 2f 2a 0a 2a 2a 20 48 65 6c 70 65 72 20 66 75  ./*.** Helper fu
54d0: 6e 63 74 69 6f 6e 20 66 6f 72 20 73 71 6c 69 74  nction for sqlit
54e0: 65 33 56 64 62 65 53 6f 72 74 65 72 52 65 77 69  e3VdbeSorterRewi
54f0: 6e 64 28 29 2e 20 0a 2a 2f 0a 73 74 61 74 69 63  nd(). .*/.static
5500: 20 69 6e 74 20 76 64 62 65 53 6f 72 74 65 72 49   int vdbeSorterI
5510: 6e 69 74 4d 65 72 67 65 28 0a 20 20 73 71 6c 69  nitMerge(.  sqli
5520: 74 65 33 20 2a 64 62 2c 20 20 20 20 20 20 20 20  te3 *db,        
5530: 20 20 20 20 20 20 20 20 20 20 20 20 2f 2a 20 44              /* D
5540: 61 74 61 62 61 73 65 20 68 61 6e 64 6c 65 20 2a  atabase handle *
5550: 2f 0a 20 20 56 64 62 65 43 75 72 73 6f 72 20 2a  /.  VdbeCursor *
5560: 70 43 73 72 2c 20 20 20 20 20 20 20 20 20 20 20  pCsr,           
5570: 20 20 20 20 2f 2a 20 43 75 72 73 6f 72 20 68 61      /* Cursor ha
5580: 6e 64 6c 65 20 66 6f 72 20 74 68 69 73 20 73 6f  ndle for this so
5590: 72 74 65 72 20 2a 2f 0a 20 20 69 36 34 20 2a 70  rter */.  i64 *p
55a0: 6e 42 79 74 65 20 20 20 20 20 20 20 20 20 20 20  nByte           
55b0: 20 20 20 20 20 20 20 20 20 20 2f 2a 20 53 75 6d            /* Sum
55c0: 20 6f 66 20 62 79 74 65 73 20 69 6e 20 61 6c 6c   of bytes in all
55d0: 20 6f 70 65 6e 65 64 20 50 4d 41 73 20 2a 2f 0a   opened PMAs */.
55e0: 29 7b 0a 20 20 56 64 62 65 53 6f 72 74 65 72 20  ){.  VdbeSorter 
55f0: 2a 70 53 6f 72 74 65 72 20 3d 20 70 43 73 72 2d  *pSorter = pCsr-
5600: 3e 70 53 6f 72 74 65 72 3b 0a 20 20 69 6e 74 20  >pSorter;.  int 
5610: 72 63 20 3d 20 53 51 4c 49 54 45 5f 4f 4b 3b 20  rc = SQLITE_OK; 
5620: 20 20 20 20 20 20 20 20 20 20 20 20 2f 2a 20 52              /* R
5630: 65 74 75 72 6e 20 63 6f 64 65 20 2a 2f 0a 20 20  eturn code */.  
5640: 69 6e 74 20 69 3b 20 20 20 20 20 20 20 20 20 20  int i;          
5650: 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20                  
5660: 2f 2a 20 55 73 65 64 20 74 6f 20 69 74 65 72 61  /* Used to itera
5670: 74 6f 72 20 74 68 72 6f 75 67 68 20 61 49 74 65  tor through aIte
5680: 72 5b 5d 20 2a 2f 0a 20 20 69 36 34 20 6e 42 79  r[] */.  i64 nBy
5690: 74 65 20 3d 20 30 3b 20 20 20 20 20 20 20 20 20  te = 0;         
56a0: 20 20 20 20 20 20 20 20 20 2f 2a 20 54 6f 74 61           /* Tota
56b0: 6c 20 62 79 74 65 73 20 69 6e 20 61 6c 6c 20 6f  l bytes in all o
56c0: 70 65 6e 65 64 20 50 4d 41 73 20 2a 2f 0a 0a 20  pened PMAs */.. 
56d0: 20 2f 2a 20 49 6e 69 74 69 61 6c 69 7a 65 20 74   /* Initialize t
56e0: 68 65 20 69 74 65 72 61 74 6f 72 73 2e 20 2a 2f  he iterators. */
56f0: 0a 20 20 66 6f 72 28 69 3d 30 3b 20 69 3c 53 4f  .  for(i=0; i<SO
5700: 52 54 45 52 5f 4d 41 58 5f 4d 45 52 47 45 5f 43  RTER_MAX_MERGE_C
5710: 4f 55 4e 54 3b 20 69 2b 2b 29 7b 0a 20 20 20 20  OUNT; i++){.    
5720: 56 64 62 65 53 6f 72 74 65 72 49 74 65 72 20 2a  VdbeSorterIter *
5730: 70 49 74 65 72 20 3d 20 26 70 53 6f 72 74 65 72  pIter = &pSorter
5740: 2d 3e 61 49 74 65 72 5b 69 5d 3b 0a 20 20 20 20  ->aIter[i];.    
5750: 72 63 20 3d 20 76 64 62 65 53 6f 72 74 65 72 49  rc = vdbeSorterI
5760: 74 65 72 49 6e 69 74 28 64 62 2c 20 70 53 6f 72  terInit(db, pSor
5770: 74 65 72 2c 20 70 53 6f 72 74 65 72 2d 3e 69 52  ter, pSorter->iR
5780: 65 61 64 4f 66 66 2c 20 70 49 74 65 72 2c 20 26  eadOff, pIter, &
5790: 6e 42 79 74 65 29 3b 0a 20 20 20 20 70 53 6f 72  nByte);.    pSor
57a0: 74 65 72 2d 3e 69 52 65 61 64 4f 66 66 20 3d 20  ter->iReadOff = 
57b0: 70 49 74 65 72 2d 3e 69 45 6f 66 3b 0a 20 20 20  pIter->iEof;.   
57c0: 20 61 73 73 65 72 74 28 20 72 63 21 3d 53 51 4c   assert( rc!=SQL
57d0: 49 54 45 5f 4f 4b 20 7c 7c 20 70 53 6f 72 74 65  ITE_OK || pSorte
57e0: 72 2d 3e 69 52 65 61 64 4f 66 66 3c 3d 70 53 6f  r->iReadOff<=pSo
57f0: 72 74 65 72 2d 3e 69 57 72 69 74 65 4f 66 66 20  rter->iWriteOff 
5800: 29 3b 0a 20 20 20 20 69 66 28 20 72 63 21 3d 53  );.    if( rc!=S
5810: 51 4c 49 54 45 5f 4f 4b 20 7c 7c 20 70 53 6f 72  QLITE_OK || pSor
5820: 74 65 72 2d 3e 69 52 65 61 64 4f 66 66 3e 3d 70  ter->iReadOff>=p
5830: 53 6f 72 74 65 72 2d 3e 69 57 72 69 74 65 4f 66  Sorter->iWriteOf
5840: 66 20 29 20 62 72 65 61 6b 3b 0a 20 20 7d 0a 0a  f ) break;.  }..
5850: 20 20 2f 2a 20 49 6e 69 74 69 61 6c 69 7a 65 20    /* Initialize 
5860: 74 68 65 20 61 54 72 65 65 5b 5d 20 61 72 72 61  the aTree[] arra
5870: 79 2e 20 2a 2f 0a 20 20 66 6f 72 28 69 3d 70 53  y. */.  for(i=pS
5880: 6f 72 74 65 72 2d 3e 6e 54 72 65 65 2d 31 3b 20  orter->nTree-1; 
5890: 72 63 3d 3d 53 51 4c 49 54 45 5f 4f 4b 20 26 26  rc==SQLITE_OK &&
58a0: 20 69 3e 30 3b 20 69 2d 2d 29 7b 0a 20 20 20 20   i>0; i--){.    
58b0: 72 63 20 3d 20 76 64 62 65 53 6f 72 74 65 72 44  rc = vdbeSorterD
58c0: 6f 43 6f 6d 70 61 72 65 28 70 43 73 72 2c 20 69  oCompare(pCsr, i
58d0: 29 3b 0a 20 20 7d 0a 0a 20 20 2a 70 6e 42 79 74  );.  }..  *pnByt
58e0: 65 20 3d 20 6e 42 79 74 65 3b 0a 20 20 72 65 74  e = nByte;.  ret
58f0: 75 72 6e 20 72 63 3b 0a 7d 0a 0a 2f 2a 0a 2a 2a  urn rc;.}../*.**
5900: 20 4f 6e 63 65 20 74 68 65 20 73 6f 72 74 65 72   Once the sorter
5910: 20 68 61 73 20 62 65 65 6e 20 70 6f 70 75 6c 61   has been popula
5920: 74 65 64 2c 20 74 68 69 73 20 66 75 6e 63 74 69  ted, this functi
5930: 6f 6e 20 69 73 20 63 61 6c 6c 65 64 20 74 6f 20  on is called to 
5940: 70 72 65 70 61 72 65 0a 2a 2a 20 66 6f 72 20 69  prepare.** for i
5950: 74 65 72 61 74 69 6e 67 20 74 68 72 6f 75 67 68  terating through
5960: 20 69 74 73 20 63 6f 6e 74 65 6e 74 73 20 69 6e   its contents in
5970: 20 73 6f 72 74 65 64 20 6f 72 64 65 72 2e 0a 2a   sorted order..*
5980: 2f 0a 69 6e 74 20 73 71 6c 69 74 65 33 56 64 62  /.int sqlite3Vdb
5990: 65 53 6f 72 74 65 72 52 65 77 69 6e 64 28 73 71  eSorterRewind(sq
59a0: 6c 69 74 65 33 20 2a 64 62 2c 20 56 64 62 65 43  lite3 *db, VdbeC
59b0: 75 72 73 6f 72 20 2a 70 43 73 72 2c 20 69 6e 74  ursor *pCsr, int
59c0: 20 2a 70 62 45 6f 66 29 7b 0a 20 20 56 64 62 65   *pbEof){.  Vdbe
59d0: 53 6f 72 74 65 72 20 2a 70 53 6f 72 74 65 72 20  Sorter *pSorter 
59e0: 3d 20 70 43 73 72 2d 3e 70 53 6f 72 74 65 72 3b  = pCsr->pSorter;
59f0: 0a 20 20 69 6e 74 20 72 63 3b 20 20 20 20 20 20  .  int rc;      
5a00: 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20                  
5a10: 20 20 20 2f 2a 20 52 65 74 75 72 6e 20 63 6f 64     /* Return cod
5a20: 65 20 2a 2f 0a 20 20 73 71 6c 69 74 65 33 5f 66  e */.  sqlite3_f
5a30: 69 6c 65 20 2a 70 54 65 6d 70 32 20 3d 20 30 3b  ile *pTemp2 = 0;
5a40: 20 20 20 20 20 20 20 2f 2a 20 53 65 63 6f 6e 64         /* Second
5a50: 20 74 65 6d 70 20 66 69 6c 65 20 74 6f 20 75 73   temp file to us
5a60: 65 20 2a 2f 0a 20 20 69 36 34 20 69 57 72 69 74  e */.  i64 iWrit
5a70: 65 32 20 3d 20 30 3b 20 20 20 20 20 20 20 20 20  e2 = 0;         
5a80: 20 20 20 20 20 20 20 2f 2a 20 57 72 69 74 65 20         /* Write 
5a90: 6f 66 66 73 65 74 20 66 6f 72 20 70 54 65 6d 70  offset for pTemp
5aa0: 32 20 2a 2f 0a 20 20 69 6e 74 20 6e 49 74 65 72  2 */.  int nIter
5ab0: 3b 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20  ;               
5ac0: 20 20 20 20 20 20 20 2f 2a 20 4e 75 6d 62 65 72         /* Number
5ad0: 20 6f 66 20 69 74 65 72 61 74 6f 72 73 20 75 73   of iterators us
5ae0: 65 64 20 2a 2f 0a 20 20 69 6e 74 20 6e 42 79 74  ed */.  int nByt
5af0: 65 3b 20 20 20 20 20 20 20 20 20 20 20 20 20 20  e;              
5b00: 20 20 20 20 20 20 20 20 2f 2a 20 42 79 74 65 73          /* Bytes
5b10: 20 6f 66 20 73 70 61 63 65 20 72 65 71 75 69 72   of space requir
5b20: 65 64 20 66 6f 72 20 61 49 74 65 72 2f 61 54 72  ed for aIter/aTr
5b30: 65 65 20 2a 2f 0a 20 20 69 6e 74 20 4e 20 3d 20  ee */.  int N = 
5b40: 32 3b 20 20 20 20 20 20 20 20 20 20 20 20 20 20  2;              
5b50: 20 20 20 20 20 20 20 20 2f 2a 20 50 6f 77 65 72          /* Power
5b60: 20 6f 66 20 32 20 3e 3d 20 6e 49 74 65 72 20 2a   of 2 >= nIter *
5b70: 2f 0a 0a 20 20 61 73 73 65 72 74 28 20 70 53 6f  /..  assert( pSo
5b80: 72 74 65 72 20 29 3b 0a 0a 20 20 2f 2a 20 49 66  rter );..  /* If
5b90: 20 6e 6f 20 64 61 74 61 20 68 61 73 20 62 65 65   no data has bee
5ba0: 6e 20 77 72 69 74 74 65 6e 20 74 6f 20 64 69 73  n written to dis
5bb0: 6b 2c 20 74 68 65 6e 20 64 6f 20 6e 6f 74 20 64  k, then do not d
5bc0: 6f 20 73 6f 20 6e 6f 77 2e 20 49 6e 73 74 65 61  o so now. Instea
5bd0: 64 2c 0a 20 20 2a 2a 20 73 6f 72 74 20 74 68 65  d,.  ** sort the
5be0: 20 56 64 62 65 53 6f 72 74 65 72 2e 70 52 65 63   VdbeSorter.pRec
5bf0: 6f 72 64 20 6c 69 73 74 2e 20 54 68 65 20 76 64  ord list. The vd
5c00: 62 65 20 6c 61 79 65 72 20 77 69 6c 6c 20 72 65  be layer will re
5c10: 61 64 20 64 61 74 61 20 64 69 72 65 63 74 6c 79  ad data directly
5c20: 0a 20 20 2a 2a 20 66 72 6f 6d 20 74 68 65 20 69  .  ** from the i
5c30: 6e 2d 6d 65 6d 6f 72 79 20 6c 69 73 74 2e 20 20  n-memory list.  
5c40: 2a 2f 0a 20 20 69 66 28 20 70 53 6f 72 74 65 72  */.  if( pSorter
5c50: 2d 3e 6e 50 4d 41 3d 3d 30 20 29 7b 0a 20 20 20  ->nPMA==0 ){.   
5c60: 20 2a 70 62 45 6f 66 20 3d 20 21 70 53 6f 72 74   *pbEof = !pSort
5c70: 65 72 2d 3e 70 52 65 63 6f 72 64 3b 0a 20 20 20  er->pRecord;.   
5c80: 20 61 73 73 65 72 74 28 20 70 53 6f 72 74 65 72   assert( pSorter
5c90: 2d 3e 61 54 72 65 65 3d 3d 30 20 29 3b 0a 20 20  ->aTree==0 );.  
5ca0: 20 20 72 65 74 75 72 6e 20 76 64 62 65 53 6f 72    return vdbeSor
5cb0: 74 65 72 53 6f 72 74 28 70 43 73 72 29 3b 0a 20  terSort(pCsr);. 
5cc0: 20 7d 0a 0a 20 20 2f 2a 20 57 72 69 74 65 20 74   }..  /* Write t
5cd0: 68 65 20 63 75 72 72 65 6e 74 20 62 2d 74 72 65  he current b-tre
5ce0: 65 20 74 6f 20 61 20 50 4d 41 2e 20 43 6c 6f 73  e to a PMA. Clos
5cf0: 65 20 74 68 65 20 62 2d 74 72 65 65 20 63 75 72  e the b-tree cur
5d00: 73 6f 72 2e 20 2a 2f 0a 20 20 72 63 20 3d 20 76  sor. */.  rc = v
5d10: 64 62 65 53 6f 72 74 65 72 4c 69 73 74 54 6f 50  dbeSorterListToP
5d20: 4d 41 28 64 62 2c 20 70 43 73 72 29 3b 0a 20 20  MA(db, pCsr);.  
5d30: 69 66 28 20 72 63 21 3d 53 51 4c 49 54 45 5f 4f  if( rc!=SQLITE_O
5d40: 4b 20 29 20 72 65 74 75 72 6e 20 72 63 3b 0a 0a  K ) return rc;..
5d50: 20 20 2f 2a 20 41 6c 6c 6f 63 61 74 65 20 73 70    /* Allocate sp
5d60: 61 63 65 20 66 6f 72 20 61 49 74 65 72 5b 5d 20  ace for aIter[] 
5d70: 61 6e 64 20 61 54 72 65 65 5b 5d 2e 20 2a 2f 0a  and aTree[]. */.
5d80: 20 20 6e 49 74 65 72 20 3d 20 70 53 6f 72 74 65    nIter = pSorte
5d90: 72 2d 3e 6e 50 4d 41 3b 0a 20 20 69 66 28 20 6e  r->nPMA;.  if( n
5da0: 49 74 65 72 3e 53 4f 52 54 45 52 5f 4d 41 58 5f  Iter>SORTER_MAX_
5db0: 4d 45 52 47 45 5f 43 4f 55 4e 54 20 29 20 6e 49  MERGE_COUNT ) nI
5dc0: 74 65 72 20 3d 20 53 4f 52 54 45 52 5f 4d 41 58  ter = SORTER_MAX
5dd0: 5f 4d 45 52 47 45 5f 43 4f 55 4e 54 3b 0a 20 20  _MERGE_COUNT;.  
5de0: 61 73 73 65 72 74 28 20 6e 49 74 65 72 3e 30 20  assert( nIter>0 
5df0: 29 3b 0a 20 20 77 68 69 6c 65 28 20 4e 3c 6e 49  );.  while( N<nI
5e00: 74 65 72 20 29 20 4e 20 2b 3d 20 4e 3b 0a 20 20  ter ) N += N;.  
5e10: 6e 42 79 74 65 20 3d 20 4e 20 2a 20 28 73 69 7a  nByte = N * (siz
5e20: 65 6f 66 28 69 6e 74 29 20 2b 20 73 69 7a 65 6f  eof(int) + sizeo
5e30: 66 28 56 64 62 65 53 6f 72 74 65 72 49 74 65 72  f(VdbeSorterIter
5e40: 29 29 3b 0a 20 20 70 53 6f 72 74 65 72 2d 3e 61  ));.  pSorter->a
5e50: 49 74 65 72 20 3d 20 28 56 64 62 65 53 6f 72 74  Iter = (VdbeSort
5e60: 65 72 49 74 65 72 20 2a 29 73 71 6c 69 74 65 33  erIter *)sqlite3
5e70: 44 62 4d 61 6c 6c 6f 63 5a 65 72 6f 28 64 62 2c  DbMallocZero(db,
5e80: 20 6e 42 79 74 65 29 3b 0a 20 20 69 66 28 20 21   nByte);.  if( !
5e90: 70 53 6f 72 74 65 72 2d 3e 61 49 74 65 72 20 29  pSorter->aIter )
5ea0: 20 72 65 74 75 72 6e 20 53 51 4c 49 54 45 5f 4e   return SQLITE_N
5eb0: 4f 4d 45 4d 3b 0a 20 20 70 53 6f 72 74 65 72 2d  OMEM;.  pSorter-
5ec0: 3e 61 54 72 65 65 20 3d 20 28 69 6e 74 20 2a 29  >aTree = (int *)
5ed0: 26 70 53 6f 72 74 65 72 2d 3e 61 49 74 65 72 5b  &pSorter->aIter[
5ee0: 4e 5d 3b 0a 20 20 70 53 6f 72 74 65 72 2d 3e 6e  N];.  pSorter->n
5ef0: 54 72 65 65 20 3d 20 4e 3b 0a 0a 20 20 64 6f 20  Tree = N;..  do 
5f00: 7b 0a 20 20 20 20 69 6e 74 20 69 4e 65 77 3b 20  {.    int iNew; 
5f10: 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20                  
5f20: 20 20 20 20 2f 2a 20 49 6e 64 65 78 20 6f 66 20      /* Index of 
5f30: 6e 65 77 2c 20 6d 65 72 67 65 64 2c 20 50 4d 41  new, merged, PMA
5f40: 20 2a 2f 0a 0a 20 20 20 20 66 6f 72 28 69 4e 65   */..    for(iNe
5f50: 77 3d 30 3b 20 0a 20 20 20 20 20 20 20 20 72 63  w=0; .        rc
5f60: 3d 3d 53 51 4c 49 54 45 5f 4f 4b 20 26 26 20 69  ==SQLITE_OK && i
5f70: 4e 65 77 2a 53 4f 52 54 45 52 5f 4d 41 58 5f 4d  New*SORTER_MAX_M
5f80: 45 52 47 45 5f 43 4f 55 4e 54 3c 70 53 6f 72 74  ERGE_COUNT<pSort
5f90: 65 72 2d 3e 6e 50 4d 41 3b 20 0a 20 20 20 20 20  er->nPMA; .     
5fa0: 20 20 20 69 4e 65 77 2b 2b 0a 20 20 20 20 29 7b     iNew++.    ){
5fb0: 0a 20 20 20 20 20 20 69 36 34 20 6e 57 72 69 74  .      i64 nWrit
5fc0: 65 3b 20 20 20 20 20 20 20 20 20 20 20 20 20 20  e;              
5fd0: 20 20 20 2f 2a 20 4e 75 6d 62 65 72 20 6f 66 20     /* Number of 
5fe0: 62 79 74 65 73 20 69 6e 20 6e 65 77 20 50 4d 41  bytes in new PMA
5ff0: 20 2a 2f 0a 0a 20 20 20 20 20 20 2f 2a 20 49 66   */..      /* If
6000: 20 74 68 65 72 65 20 61 72 65 20 53 4f 52 54 45   there are SORTE
6010: 52 5f 4d 41 58 5f 4d 45 52 47 45 5f 43 4f 55 4e  R_MAX_MERGE_COUN
6020: 54 20 6f 72 20 6c 65 73 73 20 50 4d 41 73 20 69  T or less PMAs i
6030: 6e 20 66 69 6c 65 20 70 54 65 6d 70 31 2c 0a 20  n file pTemp1,. 
6040: 20 20 20 20 20 2a 2a 20 69 6e 69 74 69 61 6c 69       ** initiali
6050: 7a 65 20 61 6e 20 69 74 65 72 61 74 6f 72 20 66  ze an iterator f
6060: 6f 72 20 65 61 63 68 20 6f 66 20 74 68 65 6d 20  or each of them 
6070: 61 6e 64 20 62 72 65 61 6b 20 6f 75 74 20 6f 66  and break out of
6080: 20 74 68 65 20 6c 6f 6f 70 2e 0a 20 20 20 20 20   the loop..     
6090: 20 2a 2a 20 54 68 65 73 65 20 69 74 65 72 61 74   ** These iterat
60a0: 6f 72 73 20 77 69 6c 6c 20 62 65 20 69 6e 63 72  ors will be incr
60b0: 65 6d 65 6e 74 61 6c 6c 79 20 6d 65 72 67 65 64  ementally merged
60c0: 20 61 73 20 74 68 65 20 56 44 42 45 20 6c 61 79   as the VDBE lay
60d0: 65 72 20 63 61 6c 6c 73 0a 20 20 20 20 20 20 2a  er calls.      *
60e0: 2a 20 73 71 6c 69 74 65 33 56 64 62 65 53 6f 72  * sqlite3VdbeSor
60f0: 74 65 72 4e 65 78 74 28 29 2e 0a 20 20 20 20 20  terNext()..     
6100: 20 2a 2a 0a 20 20 20 20 20 20 2a 2a 20 4f 74 68   **.      ** Oth
6110: 65 72 77 69 73 65 2c 20 69 66 20 70 54 65 6d 70  erwise, if pTemp
6120: 31 20 63 6f 6e 74 61 69 6e 73 20 6d 6f 72 65 20  1 contains more 
6130: 74 68 61 6e 20 53 4f 52 54 45 52 5f 4d 41 58 5f  than SORTER_MAX_
6140: 4d 45 52 47 45 5f 43 4f 55 4e 54 20 50 4d 41 73  MERGE_COUNT PMAs
6150: 2c 0a 20 20 20 20 20 20 2a 2a 20 69 6e 69 74 69  ,.      ** initi
6160: 61 6c 69 7a 65 20 69 6e 74 65 72 61 74 6f 72 73  alize interators
6170: 20 66 6f 72 20 53 4f 52 54 45 52 5f 4d 41 58 5f   for SORTER_MAX_
6180: 4d 45 52 47 45 5f 43 4f 55 4e 54 20 6f 66 20 74  MERGE_COUNT of t
6190: 68 65 6d 2e 20 54 68 65 73 65 20 50 4d 41 73 0a  hem. These PMAs.
61a0: 20 20 20 20 20 20 2a 2a 20 61 72 65 20 6d 65 72        ** are mer
61b0: 67 65 64 20 69 6e 74 6f 20 61 20 73 69 6e 67 6c  ged into a singl
61c0: 65 20 50 4d 41 20 74 68 61 74 20 69 73 20 77 72  e PMA that is wr
61d0: 69 74 74 65 6e 20 74 6f 20 66 69 6c 65 20 70 54  itten to file pT
61e0: 65 6d 70 32 2e 0a 20 20 20 20 20 20 2a 2f 0a 20  emp2..      */. 
61f0: 20 20 20 20 20 72 63 20 3d 20 76 64 62 65 53 6f       rc = vdbeSo
6200: 72 74 65 72 49 6e 69 74 4d 65 72 67 65 28 64 62  rterInitMerge(db
6210: 2c 20 70 43 73 72 2c 20 26 6e 57 72 69 74 65 29  , pCsr, &nWrite)
6220: 3b 0a 20 20 20 20 20 20 61 73 73 65 72 74 28 20  ;.      assert( 
6230: 72 63 21 3d 53 51 4c 49 54 45 5f 4f 4b 20 7c 7c  rc!=SQLITE_OK ||
6240: 20 70 53 6f 72 74 65 72 2d 3e 61 49 74 65 72 5b   pSorter->aIter[
6250: 20 70 53 6f 72 74 65 72 2d 3e 61 54 72 65 65 5b   pSorter->aTree[
6260: 31 5d 20 5d 2e 70 46 69 6c 65 20 29 3b 0a 20 20  1] ].pFile );.  
6270: 20 20 20 20 69 66 28 20 72 63 21 3d 53 51 4c 49      if( rc!=SQLI
6280: 54 45 5f 4f 4b 20 7c 7c 20 70 53 6f 72 74 65 72  TE_OK || pSorter
6290: 2d 3e 6e 50 4d 41 3c 3d 53 4f 52 54 45 52 5f 4d  ->nPMA<=SORTER_M
62a0: 41 58 5f 4d 45 52 47 45 5f 43 4f 55 4e 54 20 29  AX_MERGE_COUNT )
62b0: 7b 0a 20 20 20 20 20 20 20 20 62 72 65 61 6b 3b  {.        break;
62c0: 0a 20 20 20 20 20 20 7d 0a 0a 20 20 20 20 20 20  .      }..      
62d0: 2f 2a 20 4f 70 65 6e 20 74 68 65 20 73 65 63 6f  /* Open the seco
62e0: 6e 64 20 74 65 6d 70 20 66 69 6c 65 2c 20 69 66  nd temp file, if
62f0: 20 69 74 20 69 73 20 6e 6f 74 20 61 6c 72 65 61   it is not alrea
6300: 64 79 20 6f 70 65 6e 2e 20 2a 2f 0a 20 20 20 20  dy open. */.    
6310: 20 20 69 66 28 20 70 54 65 6d 70 32 3d 3d 30 20    if( pTemp2==0 
6320: 29 7b 0a 20 20 20 20 20 20 20 20 61 73 73 65 72  ){.        asser
6330: 74 28 20 69 57 72 69 74 65 32 3d 3d 30 20 29 3b  t( iWrite2==0 );
6340: 0a 20 20 20 20 20 20 20 20 72 63 20 3d 20 76 64  .        rc = vd
6350: 62 65 53 6f 72 74 65 72 4f 70 65 6e 54 65 6d 70  beSorterOpenTemp
6360: 46 69 6c 65 28 64 62 2c 20 26 70 54 65 6d 70 32  File(db, &pTemp2
6370: 29 3b 0a 20 20 20 20 20 20 7d 0a 0a 20 20 20 20  );.      }..    
6380: 20 20 69 66 28 20 72 63 3d 3d 53 51 4c 49 54 45    if( rc==SQLITE
6390: 5f 4f 4b 20 29 7b 0a 20 20 20 20 20 20 20 20 72  _OK ){.        r
63a0: 63 20 3d 20 76 64 62 65 53 6f 72 74 65 72 57 72  c = vdbeSorterWr
63b0: 69 74 65 56 61 72 69 6e 74 28 70 54 65 6d 70 32  iteVarint(pTemp2
63c0: 2c 20 6e 57 72 69 74 65 2c 20 26 69 57 72 69 74  , nWrite, &iWrit
63d0: 65 32 29 3b 0a 20 20 20 20 20 20 7d 0a 0a 20 20  e2);.      }..  
63e0: 20 20 20 20 69 66 28 20 72 63 3d 3d 53 51 4c 49      if( rc==SQLI
63f0: 54 45 5f 4f 4b 20 29 7b 0a 20 20 20 20 20 20 20  TE_OK ){.       
6400: 20 69 6e 74 20 62 45 6f 66 20 3d 20 30 3b 0a 20   int bEof = 0;. 
6410: 20 20 20 20 20 20 20 77 68 69 6c 65 28 20 72 63         while( rc
6420: 3d 3d 53 51 4c 49 54 45 5f 4f 4b 20 26 26 20 62  ==SQLITE_OK && b
6430: 45 6f 66 3d 3d 30 20 29 7b 0a 20 20 20 20 20 20  Eof==0 ){.      
6440: 20 20 20 20 69 6e 74 20 6e 54 6f 57 72 69 74 65      int nToWrite
6450: 3b 0a 20 20 20 20 20 20 20 20 20 20 56 64 62 65  ;.          Vdbe
6460: 53 6f 72 74 65 72 49 74 65 72 20 2a 70 49 74 65  SorterIter *pIte
6470: 72 20 3d 20 26 70 53 6f 72 74 65 72 2d 3e 61 49  r = &pSorter->aI
6480: 74 65 72 5b 20 70 53 6f 72 74 65 72 2d 3e 61 54  ter[ pSorter->aT
6490: 72 65 65 5b 31 5d 20 5d 3b 0a 20 20 20 20 20 20  ree[1] ];.      
64a0: 20 20 20 20 61 73 73 65 72 74 28 20 70 49 74 65      assert( pIte
64b0: 72 2d 3e 70 46 69 6c 65 20 29 3b 0a 20 20 20 20  r->pFile );.    
64c0: 20 20 20 20 20 20 6e 54 6f 57 72 69 74 65 20 3d        nToWrite =
64d0: 20 70 49 74 65 72 2d 3e 6e 4b 65 79 20 2b 20 73   pIter->nKey + s
64e0: 71 6c 69 74 65 33 56 61 72 69 6e 74 4c 65 6e 28  qlite3VarintLen(
64f0: 70 49 74 65 72 2d 3e 6e 4b 65 79 29 3b 0a 20 20  pIter->nKey);.  
6500: 20 20 20 20 20 20 20 20 72 63 20 3d 20 73 71 6c          rc = sql
6510: 69 74 65 33 4f 73 57 72 69 74 65 28 70 54 65 6d  ite3OsWrite(pTem
6520: 70 32 2c 20 70 49 74 65 72 2d 3e 61 41 6c 6c 6f  p2, pIter->aAllo
6530: 63 2c 20 6e 54 6f 57 72 69 74 65 2c 20 69 57 72  c, nToWrite, iWr
6540: 69 74 65 32 29 3b 0a 20 20 20 20 20 20 20 20 20  ite2);.         
6550: 20 69 57 72 69 74 65 32 20 2b 3d 20 6e 54 6f 57   iWrite2 += nToW
6560: 72 69 74 65 3b 0a 20 20 20 20 20 20 20 20 20 20  rite;.          
6570: 69 66 28 20 72 63 3d 3d 53 51 4c 49 54 45 5f 4f  if( rc==SQLITE_O
6580: 4b 20 29 7b 0a 20 20 20 20 20 20 20 20 20 20 20  K ){.           
6590: 20 72 63 20 3d 20 73 71 6c 69 74 65 33 56 64 62   rc = sqlite3Vdb
65a0: 65 53 6f 72 74 65 72 4e 65 78 74 28 64 62 2c 20  eSorterNext(db, 
65b0: 70 43 73 72 2c 20 26 62 45 6f 66 29 3b 0a 20 20  pCsr, &bEof);.  
65c0: 20 20 20 20 20 20 20 20 7d 0a 20 20 20 20 20 20          }.      
65d0: 20 20 7d 0a 20 20 20 20 20 20 7d 0a 20 20 20 20    }.      }.    
65e0: 7d 0a 0a 20 20 20 20 69 66 28 20 70 53 6f 72 74  }..    if( pSort
65f0: 65 72 2d 3e 6e 50 4d 41 3c 3d 53 4f 52 54 45 52  er->nPMA<=SORTER
6600: 5f 4d 41 58 5f 4d 45 52 47 45 5f 43 4f 55 4e 54  _MAX_MERGE_COUNT
6610: 20 29 7b 0a 20 20 20 20 20 20 62 72 65 61 6b 3b   ){.      break;
6620: 0a 20 20 20 20 7d 65 6c 73 65 7b 0a 20 20 20 20  .    }else{.    
6630: 20 20 73 71 6c 69 74 65 33 5f 66 69 6c 65 20 2a    sqlite3_file *
6640: 70 54 6d 70 20 3d 20 70 53 6f 72 74 65 72 2d 3e  pTmp = pSorter->
6650: 70 54 65 6d 70 31 3b 0a 20 20 20 20 20 20 70 53  pTemp1;.      pS
6660: 6f 72 74 65 72 2d 3e 6e 50 4d 41 20 3d 20 69 4e  orter->nPMA = iN
6670: 65 77 3b 0a 20 20 20 20 20 20 70 53 6f 72 74 65  ew;.      pSorte
6680: 72 2d 3e 70 54 65 6d 70 31 20 3d 20 70 54 65 6d  r->pTemp1 = pTem
6690: 70 32 3b 0a 20 20 20 20 20 20 70 54 65 6d 70 32  p2;.      pTemp2
66a0: 20 3d 20 70 54 6d 70 3b 0a 20 20 20 20 20 20 70   = pTmp;.      p
66b0: 53 6f 72 74 65 72 2d 3e 69 57 72 69 74 65 4f 66  Sorter->iWriteOf
66c0: 66 20 3d 20 69 57 72 69 74 65 32 3b 0a 20 20 20  f = iWrite2;.   
66d0: 20 20 20 70 53 6f 72 74 65 72 2d 3e 69 52 65 61     pSorter->iRea
66e0: 64 4f 66 66 20 3d 20 30 3b 0a 20 20 20 20 20 20  dOff = 0;.      
66f0: 69 57 72 69 74 65 32 20 3d 20 30 3b 0a 20 20 20  iWrite2 = 0;.   
6700: 20 7d 0a 20 20 7d 77 68 69 6c 65 28 20 72 63 3d   }.  }while( rc=
6710: 3d 53 51 4c 49 54 45 5f 4f 4b 20 29 3b 0a 0a 20  =SQLITE_OK );.. 
6720: 20 69 66 28 20 70 54 65 6d 70 32 20 29 7b 0a 20   if( pTemp2 ){. 
6730: 20 20 20 73 71 6c 69 74 65 33 4f 73 43 6c 6f 73     sqlite3OsClos
6740: 65 46 72 65 65 28 70 54 65 6d 70 32 29 3b 0a 20  eFree(pTemp2);. 
6750: 20 7d 0a 20 20 2a 70 62 45 6f 66 20 3d 20 28 70   }.  *pbEof = (p
6760: 53 6f 72 74 65 72 2d 3e 61 49 74 65 72 5b 70 53  Sorter->aIter[pS
6770: 6f 72 74 65 72 2d 3e 61 54 72 65 65 5b 31 5d 5d  orter->aTree[1]]
6780: 2e 70 46 69 6c 65 3d 3d 30 29 3b 0a 20 20 72 65  .pFile==0);.  re
6790: 74 75 72 6e 20 72 63 3b 0a 7d 0a 0a 2f 2a 0a 2a  turn rc;.}../*.*
67a0: 2a 20 41 64 76 61 6e 63 65 20 74 6f 20 74 68 65  * Advance to the
67b0: 20 6e 65 78 74 20 65 6c 65 6d 65 6e 74 20 69 6e   next element in
67c0: 20 74 68 65 20 73 6f 72 74 65 72 2e 0a 2a 2f 0a   the sorter..*/.
67d0: 69 6e 74 20 73 71 6c 69 74 65 33 56 64 62 65 53  int sqlite3VdbeS
67e0: 6f 72 74 65 72 4e 65 78 74 28 73 71 6c 69 74 65  orterNext(sqlite
67f0: 33 20 2a 64 62 2c 20 56 64 62 65 43 75 72 73 6f  3 *db, VdbeCurso
6800: 72 20 2a 70 43 73 72 2c 20 69 6e 74 20 2a 70 62  r *pCsr, int *pb
6810: 45 6f 66 29 7b 0a 20 20 56 64 62 65 53 6f 72 74  Eof){.  VdbeSort
6820: 65 72 20 2a 70 53 6f 72 74 65 72 20 3d 20 70 43  er *pSorter = pC
6830: 73 72 2d 3e 70 53 6f 72 74 65 72 3b 0a 20 20 69  sr->pSorter;.  i
6840: 6e 74 20 72 63 3b 20 20 20 20 20 20 20 20 20 20  nt rc;          
6850: 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20 2f                 /
6860: 2a 20 52 65 74 75 72 6e 20 63 6f 64 65 20 2a 2f  * Return code */
6870: 0a 0a 20 20 69 66 28 20 70 53 6f 72 74 65 72 2d  ..  if( pSorter-
6880: 3e 61 54 72 65 65 20 29 7b 0a 20 20 20 20 69 6e  >aTree ){.    in
6890: 74 20 69 50 72 65 76 20 3d 20 70 53 6f 72 74 65  t iPrev = pSorte
68a0: 72 2d 3e 61 54 72 65 65 5b 31 5d 3b 2f 2a 20 49  r->aTree[1];/* I
68b0: 6e 64 65 78 20 6f 66 20 69 74 65 72 61 74 6f 72  ndex of iterator
68c0: 20 74 6f 20 61 64 76 61 6e 63 65 20 2a 2f 0a 20   to advance */. 
68d0: 20 20 20 69 6e 74 20 69 3b 20 20 20 20 20 20 20     int i;       
68e0: 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20                  
68f0: 20 2f 2a 20 49 6e 64 65 78 20 6f 66 20 61 54 72   /* Index of aTr
6900: 65 65 5b 5d 20 74 6f 20 72 65 63 61 6c 63 75 6c  ee[] to recalcul
6910: 61 74 65 20 2a 2f 0a 0a 20 20 20 20 72 63 20 3d  ate */..    rc =
6920: 20 76 64 62 65 53 6f 72 74 65 72 49 74 65 72 4e   vdbeSorterIterN
6930: 65 78 74 28 64 62 2c 20 26 70 53 6f 72 74 65 72  ext(db, &pSorter
6940: 2d 3e 61 49 74 65 72 5b 69 50 72 65 76 5d 29 3b  ->aIter[iPrev]);
6950: 0a 20 20 20 20 66 6f 72 28 69 3d 28 70 53 6f 72  .    for(i=(pSor
6960: 74 65 72 2d 3e 6e 54 72 65 65 2b 69 50 72 65 76  ter->nTree+iPrev
6970: 29 2f 32 3b 20 72 63 3d 3d 53 51 4c 49 54 45 5f  )/2; rc==SQLITE_
6980: 4f 4b 20 26 26 20 69 3e 30 3b 20 69 3d 69 2f 32  OK && i>0; i=i/2
6990: 29 7b 0a 20 20 20 20 20 20 72 63 20 3d 20 76 64  ){.      rc = vd
69a0: 62 65 53 6f 72 74 65 72 44 6f 43 6f 6d 70 61 72  beSorterDoCompar
69b0: 65 28 70 43 73 72 2c 20 69 29 3b 0a 20 20 20 20  e(pCsr, i);.    
69c0: 7d 0a 0a 20 20 20 20 2a 70 62 45 6f 66 20 3d 20  }..    *pbEof = 
69d0: 28 70 53 6f 72 74 65 72 2d 3e 61 49 74 65 72 5b  (pSorter->aIter[
69e0: 70 53 6f 72 74 65 72 2d 3e 61 54 72 65 65 5b 31  pSorter->aTree[1
69f0: 5d 5d 2e 70 46 69 6c 65 3d 3d 30 29 3b 0a 20 20  ]].pFile==0);.  
6a00: 7d 65 6c 73 65 7b 0a 20 20 20 20 53 6f 72 74 65  }else{.    Sorte
6a10: 72 52 65 63 6f 72 64 20 2a 70 46 72 65 65 20 3d  rRecord *pFree =
6a20: 20 70 53 6f 72 74 65 72 2d 3e 70 52 65 63 6f 72   pSorter->pRecor
6a30: 64 3b 0a 20 20 20 20 70 53 6f 72 74 65 72 2d 3e  d;.    pSorter->
6a40: 70 52 65 63 6f 72 64 20 3d 20 70 46 72 65 65 2d  pRecord = pFree-
6a50: 3e 70 4e 65 78 74 3b 0a 20 20 20 20 70 46 72 65  >pNext;.    pFre
6a60: 65 2d 3e 70 4e 65 78 74 20 3d 20 30 3b 0a 20 20  e->pNext = 0;.  
6a70: 20 20 76 64 62 65 53 6f 72 74 65 72 52 65 63 6f    vdbeSorterReco
6a80: 72 64 46 72 65 65 28 64 62 2c 20 70 46 72 65 65  rdFree(db, pFree
6a90: 29 3b 0a 20 20 20 20 2a 70 62 45 6f 66 20 3d 20  );.    *pbEof = 
6aa0: 21 70 53 6f 72 74 65 72 2d 3e 70 52 65 63 6f 72  !pSorter->pRecor
6ab0: 64 3b 0a 20 20 20 20 72 63 20 3d 20 53 51 4c 49  d;.    rc = SQLI
6ac0: 54 45 5f 4f 4b 3b 0a 20 20 7d 0a 20 20 72 65 74  TE_OK;.  }.  ret
6ad0: 75 72 6e 20 72 63 3b 0a 7d 0a 0a 2f 2a 0a 2a 2a  urn rc;.}../*.**
6ae0: 20 52 65 74 75 72 6e 20 61 20 70 6f 69 6e 74 65   Return a pointe
6af0: 72 20 74 6f 20 61 20 62 75 66 66 65 72 20 6f 77  r to a buffer ow
6b00: 6e 65 64 20 62 79 20 74 68 65 20 73 6f 72 74 65  ned by the sorte
6b10: 72 20 74 68 61 74 20 63 6f 6e 74 61 69 6e 73 20  r that contains 
6b20: 74 68 65 20 0a 2a 2a 20 63 75 72 72 65 6e 74 20  the .** current 
6b30: 6b 65 79 2e 0a 2a 2f 0a 73 74 61 74 69 63 20 76  key..*/.static v
6b40: 6f 69 64 20 2a 76 64 62 65 53 6f 72 74 65 72 52  oid *vdbeSorterR
6b50: 6f 77 6b 65 79 28 0a 20 20 56 64 62 65 53 6f 72  owkey(.  VdbeSor
6b60: 74 65 72 20 2a 70 53 6f 72 74 65 72 2c 20 20 20  ter *pSorter,   
6b70: 20 20 20 20 20 20 20 20 20 2f 2a 20 53 6f 72 74           /* Sort
6b80: 65 72 20 6f 62 6a 65 63 74 20 2a 2f 0a 20 20 69  er object */.  i
6b90: 6e 74 20 2a 70 6e 4b 65 79 20 20 20 20 20 20 20  nt *pnKey       
6ba0: 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20 2f                 /
6bb0: 2a 20 4f 55 54 3a 20 53 69 7a 65 20 6f 66 20 63  * OUT: Size of c
6bc0: 75 72 72 65 6e 74 20 6b 65 79 20 69 6e 20 62 79  urrent key in by
6bd0: 74 65 73 20 2a 2f 0a 29 7b 0a 20 20 76 6f 69 64  tes */.){.  void
6be0: 20 2a 70 4b 65 79 3b 0a 20 20 69 66 28 20 70 53   *pKey;.  if( pS
6bf0: 6f 72 74 65 72 2d 3e 61 54 72 65 65 20 29 7b 0a  orter->aTree ){.
6c00: 20 20 20 20 56 64 62 65 53 6f 72 74 65 72 49 74      VdbeSorterIt
6c10: 65 72 20 2a 70 49 74 65 72 3b 0a 20 20 20 20 70  er *pIter;.    p
6c20: 49 74 65 72 20 3d 20 26 70 53 6f 72 74 65 72 2d  Iter = &pSorter-
6c30: 3e 61 49 74 65 72 5b 20 70 53 6f 72 74 65 72 2d  >aIter[ pSorter-
6c40: 3e 61 54 72 65 65 5b 31 5d 20 5d 3b 0a 20 20 20  >aTree[1] ];.   
6c50: 20 2a 70 6e 4b 65 79 20 3d 20 70 49 74 65 72 2d   *pnKey = pIter-
6c60: 3e 6e 4b 65 79 3b 0a 20 20 20 20 70 4b 65 79 20  >nKey;.    pKey 
6c70: 3d 20 70 49 74 65 72 2d 3e 61 4b 65 79 3b 0a 20  = pIter->aKey;. 
6c80: 20 7d 65 6c 73 65 7b 0a 20 20 20 20 2a 70 6e 4b   }else{.    *pnK
6c90: 65 79 20 3d 20 70 53 6f 72 74 65 72 2d 3e 70 52  ey = pSorter->pR
6ca0: 65 63 6f 72 64 2d 3e 6e 56 61 6c 3b 0a 20 20 20  ecord->nVal;.   
6cb0: 20 70 4b 65 79 20 3d 20 70 53 6f 72 74 65 72 2d   pKey = pSorter-
6cc0: 3e 70 52 65 63 6f 72 64 2d 3e 70 56 61 6c 3b 0a  >pRecord->pVal;.
6cd0: 20 20 7d 0a 20 20 72 65 74 75 72 6e 20 70 4b 65    }.  return pKe
6ce0: 79 3b 0a 7d 0a 0a 2f 2a 0a 2a 2a 20 43 6f 70 79  y;.}../*.** Copy
6cf0: 20 74 68 65 20 63 75 72 72 65 6e 74 20 73 6f 72   the current sor
6d00: 74 65 72 20 6b 65 79 20 69 6e 74 6f 20 74 68 65  ter key into the
6d10: 20 6d 65 6d 6f 72 79 20 63 65 6c 6c 20 70 4f 75   memory cell pOu
6d20: 74 2e 0a 2a 2f 0a 69 6e 74 20 73 71 6c 69 74 65  t..*/.int sqlite
6d30: 33 56 64 62 65 53 6f 72 74 65 72 52 6f 77 6b 65  3VdbeSorterRowke
6d40: 79 28 56 64 62 65 43 75 72 73 6f 72 20 2a 70 43  y(VdbeCursor *pC
6d50: 73 72 2c 20 4d 65 6d 20 2a 70 4f 75 74 29 7b 0a  sr, Mem *pOut){.
6d60: 20 20 56 64 62 65 53 6f 72 74 65 72 20 2a 70 53    VdbeSorter *pS
6d70: 6f 72 74 65 72 20 3d 20 70 43 73 72 2d 3e 70 53  orter = pCsr->pS
6d80: 6f 72 74 65 72 3b 0a 20 20 76 6f 69 64 20 2a 70  orter;.  void *p
6d90: 4b 65 79 3b 20 69 6e 74 20 6e 4b 65 79 3b 20 20  Key; int nKey;  
6da0: 20 20 20 20 20 20 20 20 20 2f 2a 20 53 6f 72 74           /* Sort
6db0: 65 72 20 6b 65 79 20 74 6f 20 63 6f 70 79 20 69  er key to copy i
6dc0: 6e 74 6f 20 70 4f 75 74 20 2a 2f 0a 0a 20 20 70  nto pOut */..  p
6dd0: 4b 65 79 20 3d 20 76 64 62 65 53 6f 72 74 65 72  Key = vdbeSorter
6de0: 52 6f 77 6b 65 79 28 70 53 6f 72 74 65 72 2c 20  Rowkey(pSorter, 
6df0: 26 6e 4b 65 79 29 3b 0a 20 20 69 66 28 20 73 71  &nKey);.  if( sq
6e00: 6c 69 74 65 33 56 64 62 65 4d 65 6d 47 72 6f 77  lite3VdbeMemGrow
6e10: 28 70 4f 75 74 2c 20 6e 4b 65 79 2c 20 30 29 20  (pOut, nKey, 0) 
6e20: 29 7b 0a 20 20 20 20 72 65 74 75 72 6e 20 53 51  ){.    return SQ
6e30: 4c 49 54 45 5f 4e 4f 4d 45 4d 3b 0a 20 20 7d 0a  LITE_NOMEM;.  }.
6e40: 20 20 70 4f 75 74 2d 3e 6e 20 3d 20 6e 4b 65 79    pOut->n = nKey
6e50: 3b 0a 20 20 4d 65 6d 53 65 74 54 79 70 65 46 6c  ;.  MemSetTypeFl
6e60: 61 67 28 70 4f 75 74 2c 20 4d 45 4d 5f 42 6c 6f  ag(pOut, MEM_Blo
6e70: 62 29 3b 0a 20 20 6d 65 6d 63 70 79 28 70 4f 75  b);.  memcpy(pOu
6e80: 74 2d 3e 7a 2c 20 70 4b 65 79 2c 20 6e 4b 65 79  t->z, pKey, nKey
6e90: 29 3b 0a 0a 20 20 72 65 74 75 72 6e 20 53 51 4c  );..  return SQL
6ea0: 49 54 45 5f 4f 4b 3b 0a 7d 0a 0a 2f 2a 0a 2a 2a  ITE_OK;.}../*.**
6eb0: 20 43 6f 6d 70 61 72 65 20 74 68 65 20 6b 65 79   Compare the key
6ec0: 20 69 6e 20 6d 65 6d 6f 72 79 20 63 65 6c 6c 20   in memory cell 
6ed0: 70 56 61 6c 20 77 69 74 68 20 74 68 65 20 6b 65  pVal with the ke
6ee0: 79 20 74 68 61 74 20 74 68 65 20 73 6f 72 74 65  y that the sorte
6ef0: 72 20 63 75 72 73 6f 72 0a 2a 2a 20 70 61 73 73  r cursor.** pass
6f00: 65 64 20 61 73 20 74 68 65 20 66 69 72 73 74 20  ed as the first 
6f10: 61 72 67 75 6d 65 6e 74 20 63 75 72 72 65 6e 74  argument current
6f20: 6c 79 20 70 6f 69 6e 74 73 20 74 6f 2e 20 46 6f  ly points to. Fo
6f30: 72 20 74 68 65 20 70 75 72 70 6f 73 65 73 20 6f  r the purposes o
6f40: 66 0a 2a 2a 20 74 68 65 20 63 6f 6d 70 61 72 69  f.** the compari
6f50: 73 6f 6e 2c 20 69 67 6e 6f 72 65 20 74 68 65 20  son, ignore the 
6f60: 72 6f 77 69 64 20 66 69 65 6c 64 20 61 74 20 74  rowid field at t
6f70: 68 65 20 65 6e 64 20 6f 66 20 65 61 63 68 20 72  he end of each r
6f80: 65 63 6f 72 64 2e 0a 2a 2a 0a 2a 2a 20 49 66 20  ecord..**.** If 
6f90: 61 6e 20 65 72 72 6f 72 20 6f 63 63 75 72 73 2c  an error occurs,
6fa0: 20 72 65 74 75 72 6e 20 61 6e 20 53 51 4c 69 74   return an SQLit
6fb0: 65 20 65 72 72 6f 72 20 63 6f 64 65 20 28 69 2e  e error code (i.
6fc0: 65 2e 20 53 51 4c 49 54 45 5f 4e 4f 4d 45 4d 29  e. SQLITE_NOMEM)
6fd0: 2e 0a 2a 2a 20 4f 74 68 65 72 77 69 73 65 2c 20  ..** Otherwise, 
6fe0: 73 65 74 20 2a 70 52 65 73 20 74 6f 20 61 20 6e  set *pRes to a n
6ff0: 65 67 61 74 69 76 65 2c 20 7a 65 72 6f 20 6f 72  egative, zero or
7000: 20 70 6f 73 69 74 69 76 65 20 76 61 6c 75 65 20   positive value 
7010: 69 66 20 74 68 65 0a 2a 2a 20 6b 65 79 20 69 6e  if the.** key in
7020: 20 70 56 61 6c 20 69 73 20 73 6d 61 6c 6c 65 72   pVal is smaller
7030: 20 74 68 61 6e 2c 20 65 71 75 61 6c 20 74 6f 20   than, equal to 
7040: 6f 72 20 6c 61 72 67 65 72 20 74 68 61 6e 20 74  or larger than t
7050: 68 65 20 63 75 72 72 65 6e 74 20 73 6f 72 74 65  he current sorte
7060: 72 0a 2a 2a 20 6b 65 79 2e 0a 2a 2f 0a 69 6e 74  r.** key..*/.int
7070: 20 73 71 6c 69 74 65 33 56 64 62 65 53 6f 72 74   sqlite3VdbeSort
7080: 65 72 43 6f 6d 70 61 72 65 28 0a 20 20 56 64 62  erCompare(.  Vdb
7090: 65 43 75 72 73 6f 72 20 2a 70 43 73 72 2c 20 20  eCursor *pCsr,  
70a0: 20 20 20 20 20 20 20 20 20 20 20 20 20 2f 2a 20               /* 
70b0: 53 6f 72 74 65 72 20 63 75 72 73 6f 72 20 2a 2f  Sorter cursor */
70c0: 0a 20 20 4d 65 6d 20 2a 70 56 61 6c 2c 20 20 20  .  Mem *pVal,   
70d0: 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20                  
70e0: 20 20 20 2f 2a 20 56 61 6c 75 65 20 74 6f 20 63     /* Value to c
70f0: 6f 6d 70 61 72 65 20 74 6f 20 63 75 72 72 65 6e  ompare to curren
7100: 74 20 73 6f 72 74 65 72 20 6b 65 79 20 2a 2f 0a  t sorter key */.
7110: 20 20 69 6e 74 20 2a 70 52 65 73 20 20 20 20 20    int *pRes     
7120: 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20                  
7130: 20 20 2f 2a 20 4f 55 54 3a 20 52 65 73 75 6c 74    /* OUT: Result
7140: 20 6f 66 20 63 6f 6d 70 61 72 69 73 6f 6e 20 2a   of comparison *
7150: 2f 0a 29 7b 0a 20 20 56 64 62 65 53 6f 72 74 65  /.){.  VdbeSorte
7160: 72 20 2a 70 53 6f 72 74 65 72 20 3d 20 70 43 73  r *pSorter = pCs
7170: 72 2d 3e 70 53 6f 72 74 65 72 3b 0a 20 20 76 6f  r->pSorter;.  vo
7180: 69 64 20 2a 70 4b 65 79 3b 20 69 6e 74 20 6e 4b  id *pKey; int nK
7190: 65 79 3b 20 20 20 20 20 20 20 20 20 20 20 2f 2a  ey;           /*
71a0: 20 53 6f 72 74 65 72 20 6b 65 79 20 74 6f 20 63   Sorter key to c
71b0: 6f 6d 70 61 72 65 20 70 56 61 6c 20 77 69 74 68  ompare pVal with
71c0: 20 2a 2f 0a 0a 20 20 70 4b 65 79 20 3d 20 76 64   */..  pKey = vd
71d0: 62 65 53 6f 72 74 65 72 52 6f 77 6b 65 79 28 70  beSorterRowkey(p
71e0: 53 6f 72 74 65 72 2c 20 26 6e 4b 65 79 29 3b 0a  Sorter, &nKey);.
71f0: 20 20 76 64 62 65 53 6f 72 74 65 72 43 6f 6d 70    vdbeSorterComp
7200: 61 72 65 28 70 43 73 72 2c 20 31 2c 20 70 56 61  are(pCsr, 1, pVa
7210: 6c 2d 3e 7a 2c 20 70 56 61 6c 2d 3e 6e 2c 20 70  l->z, pVal->n, p
7220: 4b 65 79 2c 20 6e 4b 65 79 2c 20 70 52 65 73 29  Key, nKey, pRes)
7230: 3b 0a 20 20 72 65 74 75 72 6e 20 53 51 4c 49 54  ;.  return SQLIT
7240: 45 5f 4f 4b 3b 0a 7d 0a 0a 23 65 6e 64 69 66 20  E_OK;.}..#endif 
7250: 2f 2a 20 23 69 66 6e 64 65 66 20 53 51 4c 49 54  /* #ifndef SQLIT
7260: 45 5f 4f 4d 49 54 5f 4d 45 52 47 45 5f 53 4f 52  E_OMIT_MERGE_SOR
7270: 54 20 2a 2f 0a                                   T */.