/ Hex Artifact Content
Login

Artifact e6d6f0c2aa003f7cbdea8c9be47a15a8e854fb97:


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 63 68 61 72 20 2a 61 53 70 61 63 65  /.  char *aSpace
1290: 3b 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20  ;               
12a0: 20 20 20 20 2f 2a 20 53 70 61 63 65 20 66 6f 72      /* Space for
12b0: 20 55 6e 70 61 63 6b 52 65 63 6f 72 64 28 29 20   UnpackRecord() 
12c0: 2a 2f 0a 20 20 69 6e 74 20 6e 53 70 61 63 65 3b  */.  int nSpace;
12d0: 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20                  
12e0: 20 20 20 20 20 2f 2a 20 53 69 7a 65 20 6f 66 20       /* Size of 
12f0: 61 53 70 61 63 65 20 69 6e 20 62 79 74 65 73 20  aSpace in bytes 
1300: 2a 2f 0a 7d 3b 0a 0a 2f 2a 0a 2a 2a 20 54 68 65  */.};../*.** The
1310: 20 66 6f 6c 6c 6f 77 69 6e 67 20 74 79 70 65 20   following type 
1320: 69 73 20 61 6e 20 69 74 65 72 61 74 6f 72 20 66  is an iterator f
1330: 6f 72 20 61 20 50 4d 41 2e 20 49 74 20 63 61 63  or a PMA. It cac
1340: 68 65 73 20 74 68 65 20 63 75 72 72 65 6e 74 20  hes the current 
1350: 6b 65 79 20 69 6e 20 0a 2a 2a 20 76 61 72 69 61  key in .** varia
1360: 62 6c 65 73 20 6e 4b 65 79 2f 61 4b 65 79 2e 20  bles nKey/aKey. 
1370: 49 66 20 74 68 65 20 69 74 65 72 61 74 6f 72 20  If the iterator 
1380: 69 73 20 61 74 20 45 4f 46 2c 20 70 46 69 6c 65  is at EOF, pFile
1390: 3d 3d 30 2e 0a 2a 2f 0a 73 74 72 75 63 74 20 56  ==0..*/.struct V
13a0: 64 62 65 53 6f 72 74 65 72 49 74 65 72 20 7b 0a  dbeSorterIter {.
13b0: 20 20 69 36 34 20 69 52 65 61 64 4f 66 66 3b 20    i64 iReadOff; 
13c0: 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20                  
13d0: 20 20 2f 2a 20 43 75 72 72 65 6e 74 20 72 65 61    /* Current rea
13e0: 64 20 6f 66 66 73 65 74 20 2a 2f 0a 20 20 69 36  d offset */.  i6
13f0: 34 20 69 45 6f 66 3b 20 20 20 20 20 20 20 20 20  4 iEof;         
1400: 20 20 20 20 20 20 20 20 20 20 20 20 20 20 2f 2a                /*
1410: 20 31 20 62 79 74 65 20 70 61 73 74 20 45 4f 46   1 byte past EOF
1420: 20 66 6f 72 20 74 68 69 73 20 69 74 65 72 61 74   for this iterat
1430: 6f 72 20 2a 2f 0a 20 20 73 71 6c 69 74 65 33 5f  or */.  sqlite3_
1440: 66 69 6c 65 20 2a 70 46 69 6c 65 3b 20 20 20 20  file *pFile;    
1450: 20 20 20 20 20 20 20 20 2f 2a 20 46 69 6c 65 20          /* File 
1460: 69 74 65 72 61 74 6f 72 20 69 73 20 72 65 61 64  iterator is read
1470: 69 6e 67 20 66 72 6f 6d 20 2a 2f 0a 20 20 69 6e  ing from */.  in
1480: 74 20 6e 41 6c 6c 6f 63 3b 20 20 20 20 20 20 20  t nAlloc;       
1490: 20 20 20 20 20 20 20 20 20 20 20 20 20 20 2f 2a                /*
14a0: 20 42 79 74 65 73 20 6f 66 20 73 70 61 63 65 20   Bytes of space 
14b0: 61 74 20 61 41 6c 6c 6f 63 20 2a 2f 0a 20 20 75  at aAlloc */.  u
14c0: 38 20 2a 61 41 6c 6c 6f 63 3b 20 20 20 20 20 20  8 *aAlloc;      
14d0: 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20 2f                 /
14e0: 2a 20 41 6c 6c 6f 63 61 74 65 64 20 73 70 61 63  * Allocated spac
14f0: 65 20 2a 2f 0a 20 20 69 6e 74 20 6e 4b 65 79 3b  e */.  int nKey;
1500: 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20                  
1510: 20 20 20 20 20 20 20 2f 2a 20 4e 75 6d 62 65 72         /* Number
1520: 20 6f 66 20 62 79 74 65 73 20 69 6e 20 6b 65 79   of bytes in key
1530: 20 2a 2f 0a 20 20 75 38 20 2a 61 4b 65 79 3b 20   */.  u8 *aKey; 
1540: 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20                  
1550: 20 20 20 20 20 20 2f 2a 20 50 6f 69 6e 74 65 72        /* Pointer
1560: 20 74 6f 20 63 75 72 72 65 6e 74 20 6b 65 79 20   to current key 
1570: 2a 2f 0a 7d 3b 0a 0a 2f 2a 0a 2a 2a 20 41 20 73  */.};../*.** A s
1580: 74 72 75 63 74 75 72 65 20 74 6f 20 73 74 6f 72  tructure to stor
1590: 65 20 61 20 73 69 6e 67 6c 65 20 72 65 63 6f 72  e a single recor
15a0: 64 2e 20 41 6c 6c 20 69 6e 2d 6d 65 6d 6f 72 79  d. All in-memory
15b0: 20 72 65 63 6f 72 64 73 20 61 72 65 20 63 6f 6e   records are con
15c0: 6e 65 63 74 65 64 0a 2a 2a 20 74 6f 67 65 74 68  nected.** togeth
15d0: 65 72 20 69 6e 74 6f 20 61 20 6c 69 6e 6b 65 64  er into a linked
15e0: 20 6c 69 73 74 20 68 65 61 64 65 64 20 61 74 20   list headed at 
15f0: 56 64 62 65 53 6f 72 74 65 72 2e 70 52 65 63 6f  VdbeSorter.pReco
1600: 72 64 20 75 73 69 6e 67 20 74 68 65 20 0a 2a 2a  rd using the .**
1610: 20 53 6f 72 74 65 72 52 65 63 6f 72 64 2e 70 4e   SorterRecord.pN
1620: 65 78 74 20 70 6f 69 6e 74 65 72 2e 0a 2a 2f 0a  ext pointer..*/.
1630: 73 74 72 75 63 74 20 53 6f 72 74 65 72 52 65 63  struct SorterRec
1640: 6f 72 64 20 7b 0a 20 20 76 6f 69 64 20 2a 70 56  ord {.  void *pV
1650: 61 6c 3b 0a 20 20 69 6e 74 20 6e 56 61 6c 3b 0a  al;.  int nVal;.
1660: 20 20 53 6f 72 74 65 72 52 65 63 6f 72 64 20 2a    SorterRecord *
1670: 70 4e 65 78 74 3b 0a 7d 3b 0a 0a 2f 2a 20 4d 69  pNext;.};../* Mi
1680: 6e 69 6d 75 6d 20 61 6c 6c 6f 77 61 62 6c 65 20  nimum allowable 
1690: 76 61 6c 75 65 20 66 6f 72 20 74 68 65 20 56 64  value for the Vd
16a0: 62 65 53 6f 72 74 65 72 2e 6e 57 6f 72 6b 69 6e  beSorter.nWorkin
16b0: 67 20 76 61 72 69 61 62 6c 65 20 2a 2f 0a 23 64  g variable */.#d
16c0: 65 66 69 6e 65 20 53 4f 52 54 45 52 5f 4d 49 4e  efine SORTER_MIN
16d0: 5f 57 4f 52 4b 49 4e 47 20 31 30 0a 0a 2f 2a 20  _WORKING 10../* 
16e0: 4d 61 78 69 6d 75 6d 20 6e 75 6d 62 65 72 20 6f  Maximum number o
16f0: 66 20 73 65 67 6d 65 6e 74 73 20 74 6f 20 6d 65  f segments to me
1700: 72 67 65 20 69 6e 20 61 20 73 69 6e 67 6c 65 20  rge in a single 
1710: 70 61 73 73 2e 20 2a 2f 0a 23 64 65 66 69 6e 65  pass. */.#define
1720: 20 53 4f 52 54 45 52 5f 4d 41 58 5f 4d 45 52 47   SORTER_MAX_MERG
1730: 45 5f 43 4f 55 4e 54 20 31 36 0a 0a 2f 2a 0a 2a  E_COUNT 16../*.*
1740: 2a 20 46 72 65 65 20 61 6c 6c 20 6d 65 6d 6f 72  * Free all memor
1750: 79 20 62 65 6c 6f 6e 67 69 6e 67 20 74 6f 20 74  y belonging to t
1760: 68 65 20 56 64 62 65 53 6f 72 74 65 72 49 74 65  he VdbeSorterIte
1770: 72 20 6f 62 6a 65 63 74 20 70 61 73 73 65 64 20  r object passed 
1780: 61 73 20 74 68 65 20 73 65 63 6f 6e 64 0a 2a 2a  as the second.**
1790: 20 61 72 67 75 6d 65 6e 74 2e 20 41 6c 6c 20 73   argument. All s
17a0: 74 72 75 63 74 75 72 65 20 66 69 65 6c 64 73 20  tructure fields 
17b0: 61 72 65 20 73 65 74 20 74 6f 20 7a 65 72 6f 20  are set to zero 
17c0: 62 65 66 6f 72 65 20 72 65 74 75 72 6e 69 6e 67  before returning
17d0: 2e 0a 2a 2f 0a 73 74 61 74 69 63 20 76 6f 69 64  ..*/.static void
17e0: 20 76 64 62 65 53 6f 72 74 65 72 49 74 65 72 5a   vdbeSorterIterZ
17f0: 65 72 6f 28 73 71 6c 69 74 65 33 20 2a 64 62 2c  ero(sqlite3 *db,
1800: 20 56 64 62 65 53 6f 72 74 65 72 49 74 65 72 20   VdbeSorterIter 
1810: 2a 70 49 74 65 72 29 7b 0a 20 20 73 71 6c 69 74  *pIter){.  sqlit
1820: 65 33 44 62 46 72 65 65 28 64 62 2c 20 70 49 74  e3DbFree(db, pIt
1830: 65 72 2d 3e 61 41 6c 6c 6f 63 29 3b 0a 20 20 6d  er->aAlloc);.  m
1840: 65 6d 73 65 74 28 70 49 74 65 72 2c 20 30 2c 20  emset(pIter, 0, 
1850: 73 69 7a 65 6f 66 28 56 64 62 65 53 6f 72 74 65  sizeof(VdbeSorte
1860: 72 49 74 65 72 29 29 3b 0a 7d 0a 0a 2f 2a 0a 2a  rIter));.}../*.*
1870: 2a 20 41 64 76 61 6e 63 65 20 69 74 65 72 61 74  * Advance iterat
1880: 6f 72 20 70 49 74 65 72 20 74 6f 20 74 68 65 20  or pIter to the 
1890: 6e 65 78 74 20 6b 65 79 20 69 6e 20 69 74 73 20  next key in its 
18a0: 50 4d 41 2e 20 52 65 74 75 72 6e 20 53 51 4c 49  PMA. Return SQLI
18b0: 54 45 5f 4f 4b 20 69 66 0a 2a 2a 20 6e 6f 20 65  TE_OK if.** no e
18c0: 72 72 6f 72 20 6f 63 63 75 72 73 2c 20 6f 72 20  rror occurs, or 
18d0: 61 6e 20 53 51 4c 69 74 65 20 65 72 72 6f 72 20  an SQLite error 
18e0: 63 6f 64 65 20 69 66 20 6f 6e 65 20 64 6f 65 73  code if one does
18f0: 2e 0a 2a 2f 0a 73 74 61 74 69 63 20 69 6e 74 20  ..*/.static int 
1900: 76 64 62 65 53 6f 72 74 65 72 49 74 65 72 4e 65  vdbeSorterIterNe
1910: 78 74 28 0a 20 20 73 71 6c 69 74 65 33 20 2a 64  xt(.  sqlite3 *d
1920: 62 2c 20 20 20 20 20 20 20 20 20 20 20 20 20 20  b,              
1930: 20 20 20 20 20 20 2f 2a 20 44 61 74 61 62 61 73        /* Databas
1940: 65 20 68 61 6e 64 6c 65 20 28 66 6f 72 20 73 71  e handle (for sq
1950: 6c 69 74 65 33 44 62 4d 61 6c 6c 6f 63 28 29 20  lite3DbMalloc() 
1960: 29 20 2a 2f 0a 20 20 56 64 62 65 53 6f 72 74 65  ) */.  VdbeSorte
1970: 72 49 74 65 72 20 2a 70 49 74 65 72 20 20 20 20  rIter *pIter    
1980: 20 20 20 20 20 20 20 2f 2a 20 49 74 65 72 61 74         /* Iterat
1990: 6f 72 20 74 6f 20 61 64 76 61 6e 63 65 20 2a 2f  or to advance */
19a0: 0a 29 7b 0a 20 20 69 6e 74 20 72 63 3b 20 20 20  .){.  int rc;   
19b0: 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20                  
19c0: 20 20 20 20 20 20 2f 2a 20 52 65 74 75 72 6e 20        /* Return 
19d0: 43 6f 64 65 20 2a 2f 0a 20 20 69 6e 74 20 6e 52  Code */.  int nR
19e0: 65 61 64 3b 20 20 20 20 20 20 20 20 20 20 20 20  ead;            
19f0: 20 20 20 20 20 20 20 20 20 20 2f 2a 20 4e 75 6d            /* Num
1a00: 62 65 72 20 6f 66 20 62 79 74 65 73 20 72 65 61  ber of bytes rea
1a10: 64 20 2a 2f 0a 20 20 69 6e 74 20 6e 52 65 63 20  d */.  int nRec 
1a20: 3d 20 30 3b 20 20 20 20 20 20 20 20 20 20 20 20  = 0;            
1a30: 20 20 20 20 20 20 20 2f 2a 20 53 69 7a 65 20 6f         /* Size o
1a40: 66 20 72 65 63 6f 72 64 20 69 6e 20 62 79 74 65  f record in byte
1a50: 73 20 2a 2f 0a 20 20 69 6e 74 20 69 4f 66 66 20  s */.  int iOff 
1a60: 3d 20 30 3b 20 20 20 20 20 20 20 20 20 20 20 20  = 0;            
1a70: 20 20 20 20 20 20 20 2f 2a 20 53 69 7a 65 20 6f         /* Size o
1a80: 66 20 73 65 72 69 61 6c 69 7a 65 64 20 73 69 7a  f serialized siz
1a90: 65 20 76 61 72 69 6e 74 20 69 6e 20 62 79 74 65  e varint in byte
1aa0: 73 20 2a 2f 0a 0a 20 20 6e 52 65 61 64 20 3d 20  s */..  nRead = 
1ab0: 70 49 74 65 72 2d 3e 69 45 6f 66 20 2d 20 70 49  pIter->iEof - pI
1ac0: 74 65 72 2d 3e 69 52 65 61 64 4f 66 66 3b 0a 20  ter->iReadOff;. 
1ad0: 20 69 66 28 20 6e 52 65 61 64 3e 35 20 29 20 6e   if( nRead>5 ) n
1ae0: 52 65 61 64 20 3d 20 35 3b 0a 20 20 69 66 28 20  Read = 5;.  if( 
1af0: 6e 52 65 61 64 3c 3d 30 20 29 7b 0a 20 20 20 20  nRead<=0 ){.    
1b00: 2f 2a 20 54 68 69 73 20 69 73 20 61 6e 20 45 4f  /* This is an EO
1b10: 46 20 63 6f 6e 64 69 74 69 6f 6e 20 2a 2f 0a 20  F condition */. 
1b20: 20 20 20 76 64 62 65 53 6f 72 74 65 72 49 74 65     vdbeSorterIte
1b30: 72 5a 65 72 6f 28 64 62 2c 20 70 49 74 65 72 29  rZero(db, pIter)
1b40: 3b 0a 20 20 20 20 72 65 74 75 72 6e 20 53 51 4c  ;.    return SQL
1b50: 49 54 45 5f 4f 4b 3b 0a 20 20 7d 0a 0a 20 20 72  ITE_OK;.  }..  r
1b60: 63 20 3d 20 73 71 6c 69 74 65 33 4f 73 52 65 61  c = sqlite3OsRea
1b70: 64 28 70 49 74 65 72 2d 3e 70 46 69 6c 65 2c 20  d(pIter->pFile, 
1b80: 70 49 74 65 72 2d 3e 61 41 6c 6c 6f 63 2c 20 6e  pIter->aAlloc, n
1b90: 52 65 61 64 2c 20 70 49 74 65 72 2d 3e 69 52 65  Read, pIter->iRe
1ba0: 61 64 4f 66 66 29 3b 0a 20 20 69 66 28 20 72 63  adOff);.  if( rc
1bb0: 3d 3d 53 51 4c 49 54 45 5f 4f 4b 20 29 7b 0a 20  ==SQLITE_OK ){. 
1bc0: 20 20 20 69 4f 66 66 20 3d 20 67 65 74 56 61 72     iOff = getVar
1bd0: 69 6e 74 33 32 28 70 49 74 65 72 2d 3e 61 41 6c  int32(pIter->aAl
1be0: 6c 6f 63 2c 20 6e 52 65 63 29 3b 0a 20 20 20 20  loc, nRec);.    
1bf0: 69 66 28 20 28 69 4f 66 66 2b 6e 52 65 63 29 3e  if( (iOff+nRec)>
1c00: 6e 52 65 61 64 20 29 7b 0a 20 20 20 20 20 20 69  nRead ){.      i
1c10: 6e 74 20 6e 52 65 61 64 32 3b 20 20 20 20 20 20  nt nRead2;      
1c20: 20 20 20 20 20 20 20 20 20 20 20 20 20 2f 2a 20               /* 
1c30: 4e 75 6d 62 65 72 20 6f 66 20 65 78 74 72 61 20  Number of extra 
1c40: 62 79 74 65 73 20 74 6f 20 72 65 61 64 20 2a 2f  bytes to read */
1c50: 0a 20 20 20 20 20 20 69 66 28 20 28 69 4f 66 66  .      if( (iOff
1c60: 2b 6e 52 65 63 29 3e 70 49 74 65 72 2d 3e 6e 41  +nRec)>pIter->nA
1c70: 6c 6c 6f 63 20 29 7b 0a 20 20 20 20 20 20 20 20  lloc ){.        
1c80: 69 6e 74 20 6e 4e 65 77 20 3d 20 70 49 74 65 72  int nNew = pIter
1c90: 2d 3e 6e 41 6c 6c 6f 63 2a 32 3b 0a 20 20 20 20  ->nAlloc*2;.    
1ca0: 20 20 20 20 77 68 69 6c 65 28 20 28 69 4f 66 66      while( (iOff
1cb0: 2b 6e 52 65 63 29 3e 6e 4e 65 77 20 29 20 6e 4e  +nRec)>nNew ) nN
1cc0: 65 77 20 3d 20 6e 4e 65 77 2a 32 3b 0a 20 20 20  ew = nNew*2;.   
1cd0: 20 20 20 20 20 70 49 74 65 72 2d 3e 61 41 6c 6c       pIter->aAll
1ce0: 6f 63 20 3d 20 73 71 6c 69 74 65 33 44 62 52 65  oc = sqlite3DbRe
1cf0: 61 6c 6c 6f 63 4f 72 46 72 65 65 28 64 62 2c 20  allocOrFree(db, 
1d00: 70 49 74 65 72 2d 3e 61 41 6c 6c 6f 63 2c 20 6e  pIter->aAlloc, n
1d10: 4e 65 77 29 3b 0a 20 20 20 20 20 20 20 20 69 66  New);.        if
1d20: 28 20 21 70 49 74 65 72 2d 3e 61 41 6c 6c 6f 63  ( !pIter->aAlloc
1d30: 20 29 20 72 65 74 75 72 6e 20 53 51 4c 49 54 45   ) return SQLITE
1d40: 5f 4e 4f 4d 45 4d 3b 0a 20 20 20 20 20 20 20 20  _NOMEM;.        
1d50: 70 49 74 65 72 2d 3e 6e 41 6c 6c 6f 63 20 3d 20  pIter->nAlloc = 
1d60: 6e 4e 65 77 3b 0a 20 20 20 20 20 20 7d 0a 20 20  nNew;.      }.  
1d70: 0a 20 20 20 20 20 20 6e 52 65 61 64 32 20 3d 20  .      nRead2 = 
1d80: 69 4f 66 66 20 2b 20 6e 52 65 63 20 2d 20 6e 52  iOff + nRec - nR
1d90: 65 61 64 3b 0a 20 20 20 20 20 20 72 63 20 3d 20  ead;.      rc = 
1da0: 73 71 6c 69 74 65 33 4f 73 52 65 61 64 28 0a 20  sqlite3OsRead(. 
1db0: 20 20 20 20 20 20 20 20 20 70 49 74 65 72 2d 3e           pIter->
1dc0: 70 46 69 6c 65 2c 20 26 70 49 74 65 72 2d 3e 61  pFile, &pIter->a
1dd0: 41 6c 6c 6f 63 5b 6e 52 65 61 64 5d 2c 20 6e 52  Alloc[nRead], nR
1de0: 65 61 64 32 2c 20 70 49 74 65 72 2d 3e 69 52 65  ead2, pIter->iRe
1df0: 61 64 4f 66 66 2b 6e 52 65 61 64 0a 20 20 20 20  adOff+nRead.    
1e00: 20 20 29 3b 0a 20 20 20 20 7d 0a 20 20 7d 0a 0a    );.    }.  }..
1e10: 20 20 61 73 73 65 72 74 28 20 72 63 21 3d 53 51    assert( rc!=SQ
1e20: 4c 49 54 45 5f 4f 4b 20 7c 7c 20 6e 52 65 63 3e  LITE_OK || nRec>
1e30: 30 20 29 3b 0a 20 20 70 49 74 65 72 2d 3e 69 52  0 );.  pIter->iR
1e40: 65 61 64 4f 66 66 20 2b 3d 20 69 4f 66 66 2b 6e  eadOff += iOff+n
1e50: 52 65 63 3b 0a 20 20 70 49 74 65 72 2d 3e 6e 4b  Rec;.  pIter->nK
1e60: 65 79 20 3d 20 6e 52 65 63 3b 0a 20 20 70 49 74  ey = nRec;.  pIt
1e70: 65 72 2d 3e 61 4b 65 79 20 3d 20 26 70 49 74 65  er->aKey = &pIte
1e80: 72 2d 3e 61 41 6c 6c 6f 63 5b 69 4f 66 66 5d 3b  r->aAlloc[iOff];
1e90: 0a 20 20 72 65 74 75 72 6e 20 72 63 3b 0a 7d 0a  .  return rc;.}.
1ea0: 0a 2f 2a 0a 2a 2a 20 57 72 69 74 65 20 61 20 73  ./*.** Write a s
1eb0: 69 6e 67 6c 65 20 76 61 72 69 6e 74 2c 20 76 61  ingle varint, va
1ec0: 6c 75 65 20 69 56 61 6c 2c 20 74 6f 20 66 69 6c  lue iVal, to fil
1ed0: 65 2d 64 65 73 63 72 69 70 74 6f 72 20 70 46 69  e-descriptor pFi
1ee0: 6c 65 2e 20 52 65 74 75 72 6e 0a 2a 2a 20 53 51  le. Return.** SQ
1ef0: 4c 49 54 45 5f 4f 4b 20 69 66 20 73 75 63 63 65  LITE_OK if succe
1f00: 73 73 66 75 6c 2c 20 6f 72 20 61 6e 20 53 51 4c  ssful, or an SQL
1f10: 69 74 65 20 65 72 72 6f 72 20 63 6f 64 65 20 69  ite error code i
1f20: 66 20 73 6f 6d 65 20 65 72 72 6f 72 20 6f 63 63  f some error occ
1f30: 75 72 73 2e 0a 2a 2a 0a 2a 2a 20 54 68 65 20 76  urs..**.** The v
1f40: 61 6c 75 65 20 6f 66 20 2a 70 69 4f 66 66 73 65  alue of *piOffse
1f50: 74 20 77 68 65 6e 20 74 68 69 73 20 66 75 6e 63  t when this func
1f60: 74 69 6f 6e 20 69 73 20 63 61 6c 6c 65 64 20 69  tion is called i
1f70: 73 20 75 73 65 64 20 61 73 20 74 68 65 20 62 79  s used as the by
1f80: 74 65 0a 2a 2a 20 6f 66 66 73 65 74 20 69 6e 20  te.** offset in 
1f90: 66 69 6c 65 20 70 46 69 6c 65 20 74 6f 20 77 72  file pFile to wr
1fa0: 69 74 65 20 74 6f 2e 20 42 65 66 6f 72 65 20 72  ite to. Before r
1fb0: 65 74 75 72 6e 69 6e 67 2c 20 2a 70 69 4f 66 66  eturning, *piOff
1fc0: 73 65 74 20 69 73 20 0a 2a 2a 20 69 6e 63 72 65  set is .** incre
1fd0: 6d 65 6e 74 65 64 20 62 79 20 74 68 65 20 6e 75  mented by the nu
1fe0: 6d 62 65 72 20 6f 66 20 62 79 74 65 73 20 77 72  mber of bytes wr
1ff0: 69 74 74 65 6e 2e 0a 2a 2f 0a 73 74 61 74 69 63  itten..*/.static
2000: 20 69 6e 74 20 76 64 62 65 53 6f 72 74 65 72 57   int vdbeSorterW
2010: 72 69 74 65 56 61 72 69 6e 74 28 0a 20 20 73 71  riteVarint(.  sq
2020: 6c 69 74 65 33 5f 66 69 6c 65 20 2a 70 46 69 6c  lite3_file *pFil
2030: 65 2c 20 20 20 20 20 20 20 20 20 20 20 20 2f 2a  e,            /*
2040: 20 46 69 6c 65 20 74 6f 20 77 72 69 74 65 20 74   File to write t
2050: 6f 20 2a 2f 0a 20 20 69 36 34 20 69 56 61 6c 2c  o */.  i64 iVal,
2060: 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20                  
2070: 20 20 20 20 20 20 20 2f 2a 20 56 61 6c 75 65 20         /* Value 
2080: 74 6f 20 77 72 69 74 65 20 61 73 20 61 20 76 61  to write as a va
2090: 72 69 6e 74 20 2a 2f 0a 20 20 69 36 34 20 2a 70  rint */.  i64 *p
20a0: 69 4f 66 66 73 65 74 20 20 20 20 20 20 20 20 20  iOffset         
20b0: 20 20 20 20 20 20 20 20 20 20 2f 2a 20 49 4e 2f            /* IN/
20c0: 4f 55 54 3a 20 57 72 69 74 65 20 6f 66 66 73 65  OUT: Write offse
20d0: 74 20 69 6e 20 66 69 6c 65 20 70 46 69 6c 65 20  t in file pFile 
20e0: 2a 2f 0a 29 7b 0a 20 20 75 38 20 61 56 61 72 69  */.){.  u8 aVari
20f0: 6e 74 5b 39 5d 3b 20 20 20 20 20 20 20 20 20 20  nt[9];          
2100: 20 20 20 20 20 20 20 20 2f 2a 20 42 75 66 66 65          /* Buffe
2110: 72 20 6c 61 72 67 65 20 65 6e 6f 75 67 68 20 66  r large enough f
2120: 6f 72 20 61 20 76 61 72 69 6e 74 20 2a 2f 0a 20  or a varint */. 
2130: 20 69 6e 74 20 6e 56 61 72 69 6e 74 3b 20 20 20   int nVarint;   
2140: 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20                  
2150: 20 2f 2a 20 4e 75 6d 62 65 72 20 6f 66 20 75 73   /* Number of us
2160: 65 64 20 62 79 74 65 73 20 69 6e 20 76 61 72 69  ed bytes in vari
2170: 6e 74 20 2a 2f 0a 20 20 69 6e 74 20 72 63 3b 20  nt */.  int rc; 
2180: 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20                  
2190: 20 20 20 20 20 20 20 20 2f 2a 20 52 65 73 75 6c          /* Resul
21a0: 74 20 6f 66 20 77 72 69 74 65 28 29 20 63 61 6c  t of write() cal
21b0: 6c 20 2a 2f 0a 0a 20 20 6e 56 61 72 69 6e 74 20  l */..  nVarint 
21c0: 3d 20 73 71 6c 69 74 65 33 50 75 74 56 61 72 69  = sqlite3PutVari
21d0: 6e 74 28 61 56 61 72 69 6e 74 2c 20 69 56 61 6c  nt(aVarint, iVal
21e0: 29 3b 0a 20 20 72 63 20 3d 20 73 71 6c 69 74 65  );.  rc = sqlite
21f0: 33 4f 73 57 72 69 74 65 28 70 46 69 6c 65 2c 20  3OsWrite(pFile, 
2200: 61 56 61 72 69 6e 74 2c 20 6e 56 61 72 69 6e 74  aVarint, nVarint
2210: 2c 20 2a 70 69 4f 66 66 73 65 74 29 3b 0a 20 20  , *piOffset);.  
2220: 2a 70 69 4f 66 66 73 65 74 20 2b 3d 20 6e 56 61  *piOffset += nVa
2230: 72 69 6e 74 3b 0a 0a 20 20 72 65 74 75 72 6e 20  rint;..  return 
2240: 72 63 3b 0a 7d 0a 0a 2f 2a 0a 2a 2a 20 52 65 61  rc;.}../*.** Rea
2250: 64 20 61 20 73 69 6e 67 6c 65 20 76 61 72 69 6e  d a single varin
2260: 74 20 66 72 6f 6d 20 66 69 6c 65 2d 64 65 73 63  t from file-desc
2270: 72 69 70 74 6f 72 20 70 46 69 6c 65 2e 20 52 65  riptor pFile. Re
2280: 74 75 72 6e 20 53 51 4c 49 54 45 5f 4f 4b 20 69  turn SQLITE_OK i
2290: 66 0a 2a 2a 20 73 75 63 63 65 73 73 66 75 6c 2c  f.** successful,
22a0: 20 6f 72 20 61 6e 20 53 51 4c 69 74 65 20 65 72   or an SQLite er
22b0: 72 6f 72 20 63 6f 64 65 20 69 66 20 73 6f 6d 65  ror code if some
22c0: 20 65 72 72 6f 72 20 6f 63 63 75 72 73 2e 0a 2a   error occurs..*
22d0: 2a 0a 2a 2a 20 54 68 65 20 76 61 6c 75 65 20 6f  *.** The value o
22e0: 66 20 2a 70 69 4f 66 66 73 65 74 20 77 68 65 6e  f *piOffset when
22f0: 20 74 68 69 73 20 66 75 6e 63 74 69 6f 6e 20 69   this function i
2300: 73 20 63 61 6c 6c 65 64 20 69 73 20 75 73 65 64  s called is used
2310: 20 61 73 20 74 68 65 0a 2a 2a 20 62 79 74 65 20   as the.** byte 
2320: 6f 66 66 73 65 74 20 69 6e 20 66 69 6c 65 20 70  offset in file p
2330: 46 69 6c 65 20 66 72 6f 6d 20 77 68 65 6e 63 65  File from whence
2340: 20 74 6f 20 72 65 61 64 20 74 68 65 20 76 61 72   to read the var
2350: 69 6e 74 2e 20 49 66 20 73 75 63 63 65 73 73 66  int. If successf
2360: 75 6c 0a 2a 2a 20 28 69 2e 65 2e 20 69 66 20 6e  ul.** (i.e. if n
2370: 6f 20 49 4f 20 65 72 72 6f 72 20 6f 63 63 75 72  o IO error occur
2380: 73 29 2c 20 74 68 65 6e 20 2a 70 69 4f 66 66 73  s), then *piOffs
2390: 65 74 20 69 73 20 73 65 74 20 74 6f 20 74 68 65  et is set to the
23a0: 20 6f 66 66 73 65 74 20 6f 66 0a 2a 2a 20 74 68   offset of.** th
23b0: 65 20 66 69 72 73 74 20 62 79 74 65 20 70 61 73  e first byte pas
23c0: 74 20 74 68 65 20 65 6e 64 20 6f 66 20 74 68 65  t the end of the
23d0: 20 76 61 72 69 6e 74 20 62 65 66 6f 72 65 20 72   varint before r
23e0: 65 74 75 72 6e 69 6e 67 2e 20 2a 70 69 56 61 6c  eturning. *piVal
23f0: 20 69 73 0a 2a 2a 20 73 65 74 20 74 6f 20 74 68   is.** set to th
2400: 65 20 69 6e 74 65 67 65 72 20 76 61 6c 75 65 20  e integer value 
2410: 72 65 61 64 2e 20 49 66 20 61 6e 20 65 72 72 6f  read. If an erro
2420: 72 20 6f 63 63 75 72 73 2c 20 74 68 65 20 66 69  r occurs, the fi
2430: 6e 61 6c 20 76 61 6c 75 65 73 20 6f 66 0a 2a 2a  nal values of.**
2440: 20 62 6f 74 68 20 2a 70 69 4f 66 66 73 65 74 20   both *piOffset 
2450: 61 6e 64 20 2a 70 69 56 61 6c 20 61 72 65 20 75  and *piVal are u
2460: 6e 64 65 66 69 6e 65 64 2e 0a 2a 2f 0a 73 74 61  ndefined..*/.sta
2470: 74 69 63 20 69 6e 74 20 76 64 62 65 53 6f 72 74  tic int vdbeSort
2480: 65 72 52 65 61 64 56 61 72 69 6e 74 28 0a 20 20  erReadVarint(.  
2490: 73 71 6c 69 74 65 33 5f 66 69 6c 65 20 2a 70 46  sqlite3_file *pF
24a0: 69 6c 65 2c 20 20 20 20 20 20 20 20 20 20 20 20  ile,            
24b0: 2f 2a 20 46 69 6c 65 20 74 6f 20 72 65 61 64 20  /* File to read 
24c0: 66 72 6f 6d 20 2a 2f 0a 20 20 69 36 34 20 69 45  from */.  i64 iE
24d0: 6f 66 2c 20 20 20 20 20 20 20 20 20 20 20 20 20  of,             
24e0: 20 20 20 20 20 20 20 20 20 20 2f 2a 20 54 6f 74            /* Tot
24f0: 61 6c 20 6e 75 6d 62 65 72 20 6f 66 20 62 79 74  al number of byt
2500: 65 73 20 69 6e 20 66 69 6c 65 20 2a 2f 0a 20 20  es in file */.  
2510: 69 36 34 20 2a 70 69 4f 66 66 73 65 74 2c 20 20  i64 *piOffset,  
2520: 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20                  
2530: 2f 2a 20 49 4e 2f 4f 55 54 3a 20 52 65 61 64 20  /* IN/OUT: Read 
2540: 6f 66 66 73 65 74 20 69 6e 20 70 46 69 6c 65 20  offset in pFile 
2550: 2a 2f 0a 20 20 69 36 34 20 2a 70 69 56 61 6c 20  */.  i64 *piVal 
2560: 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20                  
2570: 20 20 20 20 20 2f 2a 20 4f 55 54 3a 20 56 61 6c       /* OUT: Val
2580: 75 65 20 72 65 61 64 20 66 72 6f 6d 20 66 69 6c  ue read from fil
2590: 65 20 2a 2f 0a 29 7b 0a 20 20 75 38 20 61 56 61  e */.){.  u8 aVa
25a0: 72 69 6e 74 5b 39 5d 3b 20 20 20 20 20 20 20 20  rint[9];        
25b0: 20 20 20 20 20 20 20 20 20 20 2f 2a 20 42 75 66            /* Buf
25c0: 66 65 72 20 6c 61 72 67 65 20 65 6e 6f 75 67 68  fer large enough
25d0: 20 66 6f 72 20 61 20 76 61 72 69 6e 74 20 2a 2f   for a varint */
25e0: 0a 20 20 69 36 34 20 69 4f 66 66 20 3d 20 2a 70  .  i64 iOff = *p
25f0: 69 4f 66 66 73 65 74 3b 20 20 20 20 20 20 20 20  iOffset;        
2600: 20 20 20 2f 2a 20 4f 66 66 73 65 74 20 69 6e 20     /* Offset in 
2610: 66 69 6c 65 20 74 6f 20 72 65 61 64 20 66 72 6f  file to read fro
2620: 6d 20 2a 2f 0a 20 20 69 6e 74 20 6e 52 65 61 64  m */.  int nRead
2630: 20 3d 20 39 3b 20 20 20 20 20 20 20 20 20 20 20   = 9;           
2640: 20 20 20 20 20 20 20 2f 2a 20 4e 75 6d 62 65 72         /* Number
2650: 20 6f 66 20 62 79 74 65 73 20 74 6f 20 72 65 61   of bytes to rea
2660: 64 20 66 72 6f 6d 20 66 69 6c 65 20 2a 2f 0a 20  d from file */. 
2670: 20 69 6e 74 20 72 63 3b 20 20 20 20 20 20 20 20   int rc;        
2680: 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20                  
2690: 20 2f 2a 20 52 65 74 75 72 6e 20 63 6f 64 65 20   /* Return code 
26a0: 2a 2f 0a 0a 20 20 61 73 73 65 72 74 28 20 69 45  */..  assert( iE
26b0: 6f 66 3e 69 4f 66 66 20 29 3b 0a 20 20 69 66 28  of>iOff );.  if(
26c0: 20 28 69 45 6f 66 2d 69 4f 66 66 29 3c 6e 52 65   (iEof-iOff)<nRe
26d0: 61 64 20 29 7b 0a 20 20 20 20 6e 52 65 61 64 20  ad ){.    nRead 
26e0: 3d 20 69 45 6f 66 2d 69 4f 66 66 3b 0a 20 20 7d  = iEof-iOff;.  }
26f0: 0a 0a 20 20 72 63 20 3d 20 73 71 6c 69 74 65 33  ..  rc = sqlite3
2700: 4f 73 52 65 61 64 28 70 46 69 6c 65 2c 20 61 56  OsRead(pFile, aV
2710: 61 72 69 6e 74 2c 20 6e 52 65 61 64 2c 20 69 4f  arint, nRead, iO
2720: 66 66 29 3b 0a 20 20 69 66 28 20 72 63 3d 3d 53  ff);.  if( rc==S
2730: 51 4c 49 54 45 5f 4f 4b 20 29 7b 0a 20 20 20 20  QLITE_OK ){.    
2740: 2a 70 69 4f 66 66 73 65 74 20 2b 3d 20 67 65 74  *piOffset += get
2750: 56 61 72 69 6e 74 28 61 56 61 72 69 6e 74 2c 20  Varint(aVarint, 
2760: 28 75 36 34 20 2a 29 70 69 56 61 6c 29 3b 0a 20  (u64 *)piVal);. 
2770: 20 7d 0a 0a 20 20 72 65 74 75 72 6e 20 72 63 3b   }..  return rc;
2780: 0a 7d 0a 0a 2f 2a 0a 2a 2a 20 49 6e 69 74 69 61  .}../*.** Initia
2790: 6c 69 7a 65 20 69 74 65 72 61 74 6f 72 20 70 49  lize iterator pI
27a0: 74 65 72 20 74 6f 20 73 63 61 6e 20 74 68 72 6f  ter to scan thro
27b0: 75 67 68 20 74 68 65 20 50 4d 41 20 73 74 6f 72  ugh the PMA stor
27c0: 65 64 20 69 6e 20 66 69 6c 65 20 70 46 69 6c 65  ed in file pFile
27d0: 0a 2a 2a 20 73 74 61 72 74 69 6e 67 20 61 74 20  .** starting at 
27e0: 6f 66 66 73 65 74 20 69 53 74 61 72 74 20 61 6e  offset iStart an
27f0: 64 20 65 6e 64 69 6e 67 20 61 74 20 6f 66 66 73  d ending at offs
2800: 65 74 20 69 45 6f 66 2d 31 2e 20 54 68 69 73 20  et iEof-1. This 
2810: 66 75 6e 63 74 69 6f 6e 20 0a 2a 2a 20 6c 65 61  function .** lea
2820: 76 65 73 20 74 68 65 20 69 74 65 72 61 74 6f 72  ves the iterator
2830: 20 70 6f 69 6e 74 69 6e 67 20 74 6f 20 74 68 65   pointing to the
2840: 20 66 69 72 73 74 20 6b 65 79 20 69 6e 20 74 68   first key in th
2850: 65 20 50 4d 41 20 28 6f 72 20 45 4f 46 20 69 66  e PMA (or EOF if
2860: 20 74 68 65 20 0a 2a 2a 20 50 4d 41 20 69 73 20   the .** PMA is 
2870: 65 6d 70 74 79 29 2e 0a 2a 2f 0a 73 74 61 74 69  empty)..*/.stati
2880: 63 20 69 6e 74 20 76 64 62 65 53 6f 72 74 65 72  c int vdbeSorter
2890: 49 74 65 72 49 6e 69 74 28 0a 20 20 73 71 6c 69  IterInit(.  sqli
28a0: 74 65 33 20 2a 64 62 2c 20 20 20 20 20 20 20 20  te3 *db,        
28b0: 20 20 20 20 20 20 20 20 20 20 20 20 2f 2a 20 44              /* D
28c0: 61 74 61 62 61 73 65 20 68 61 6e 64 6c 65 20 2a  atabase handle *
28d0: 2f 0a 20 20 56 64 62 65 53 6f 72 74 65 72 20 2a  /.  VdbeSorter *
28e0: 70 53 6f 72 74 65 72 2c 20 20 20 20 20 20 20 20  pSorter,        
28f0: 20 20 20 20 2f 2a 20 53 6f 72 74 65 72 20 6f 62      /* Sorter ob
2900: 6a 65 63 74 20 2a 2f 0a 20 20 69 36 34 20 69 53  ject */.  i64 iS
2910: 74 61 72 74 2c 20 20 20 20 20 20 20 20 20 20 20  tart,           
2920: 20 20 20 20 20 20 20 20 20 20 2f 2a 20 53 74 61            /* Sta
2930: 72 74 20 6f 66 66 73 65 74 20 69 6e 20 70 46 69  rt offset in pFi
2940: 6c 65 20 2a 2f 0a 20 20 56 64 62 65 53 6f 72 74  le */.  VdbeSort
2950: 65 72 49 74 65 72 20 2a 70 49 74 65 72 2c 20 20  erIter *pIter,  
2960: 20 20 20 20 20 20 20 20 2f 2a 20 49 74 65 72 61          /* Itera
2970: 74 6f 72 20 74 6f 20 70 6f 70 75 6c 61 74 65 20  tor to populate 
2980: 2a 2f 0a 20 20 69 36 34 20 2a 70 6e 42 79 74 65  */.  i64 *pnByte
2990: 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20                  
29a0: 20 20 20 20 20 2f 2a 20 49 4e 2f 4f 55 54 3a 20       /* IN/OUT: 
29b0: 49 6e 63 72 65 6d 65 6e 74 20 74 68 69 73 20 76  Increment this v
29c0: 61 6c 75 65 20 62 79 20 50 4d 41 20 73 69 7a 65  alue by PMA size
29d0: 20 2a 2f 0a 29 7b 0a 20 20 69 6e 74 20 72 63 3b   */.){.  int rc;
29e0: 0a 0a 20 20 61 73 73 65 72 74 28 20 70 53 6f 72  ..  assert( pSor
29f0: 74 65 72 2d 3e 69 57 72 69 74 65 4f 66 66 3e 69  ter->iWriteOff>i
2a00: 53 74 61 72 74 20 29 3b 0a 20 20 61 73 73 65 72  Start );.  asser
2a10: 74 28 20 70 49 74 65 72 2d 3e 61 41 6c 6c 6f 63  t( pIter->aAlloc
2a20: 3d 3d 30 20 29 3b 0a 20 20 70 49 74 65 72 2d 3e  ==0 );.  pIter->
2a30: 70 46 69 6c 65 20 3d 20 70 53 6f 72 74 65 72 2d  pFile = pSorter-
2a40: 3e 70 54 65 6d 70 31 3b 0a 20 20 70 49 74 65 72  >pTemp1;.  pIter
2a50: 2d 3e 69 52 65 61 64 4f 66 66 20 3d 20 69 53 74  ->iReadOff = iSt
2a60: 61 72 74 3b 0a 20 20 70 49 74 65 72 2d 3e 6e 41  art;.  pIter->nA
2a70: 6c 6c 6f 63 20 3d 20 31 32 38 3b 0a 20 20 70 49  lloc = 128;.  pI
2a80: 74 65 72 2d 3e 61 41 6c 6c 6f 63 20 3d 20 28 75  ter->aAlloc = (u
2a90: 38 20 2a 29 73 71 6c 69 74 65 33 44 62 4d 61 6c  8 *)sqlite3DbMal
2aa0: 6c 6f 63 52 61 77 28 64 62 2c 20 70 49 74 65 72  locRaw(db, pIter
2ab0: 2d 3e 6e 41 6c 6c 6f 63 29 3b 0a 20 20 69 66 28  ->nAlloc);.  if(
2ac0: 20 21 70 49 74 65 72 2d 3e 61 41 6c 6c 6f 63 20   !pIter->aAlloc 
2ad0: 29 7b 0a 20 20 20 20 72 63 20 3d 20 53 51 4c 49  ){.    rc = SQLI
2ae0: 54 45 5f 4e 4f 4d 45 4d 3b 0a 20 20 7d 65 6c 73  TE_NOMEM;.  }els
2af0: 65 7b 0a 20 20 20 20 69 36 34 20 69 45 6f 66 20  e{.    i64 iEof 
2b00: 3d 20 70 53 6f 72 74 65 72 2d 3e 69 57 72 69 74  = pSorter->iWrit
2b10: 65 4f 66 66 3b 20 20 20 20 20 2f 2a 20 45 4f 46  eOff;     /* EOF
2b20: 20 6f 66 20 66 69 6c 65 20 70 53 6f 72 74 65 72   of file pSorter
2b30: 2d 3e 70 54 65 6d 70 31 20 2a 2f 0a 20 20 20 20  ->pTemp1 */.    
2b40: 69 36 34 20 6e 42 79 74 65 3b 20 20 20 20 20 20  i64 nByte;      
2b50: 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20                  
2b60: 20 20 20 2f 2a 20 54 6f 74 61 6c 20 73 69 7a 65     /* Total size
2b70: 20 6f 66 20 50 4d 41 20 69 6e 20 62 79 74 65 73   of PMA in bytes
2b80: 20 2a 2f 0a 20 20 20 20 72 63 20 3d 20 76 64 62   */.    rc = vdb
2b90: 65 53 6f 72 74 65 72 52 65 61 64 56 61 72 69 6e  eSorterReadVarin
2ba0: 74 28 70 53 6f 72 74 65 72 2d 3e 70 54 65 6d 70  t(pSorter->pTemp
2bb0: 31 2c 20 69 45 6f 66 2c 20 26 70 49 74 65 72 2d  1, iEof, &pIter-
2bc0: 3e 69 52 65 61 64 4f 66 66 2c 20 26 6e 42 79 74  >iReadOff, &nByt
2bd0: 65 29 3b 0a 20 20 20 20 2a 70 6e 42 79 74 65 20  e);.    *pnByte 
2be0: 2b 3d 20 6e 42 79 74 65 3b 0a 20 20 20 20 70 49  += nByte;.    pI
2bf0: 74 65 72 2d 3e 69 45 6f 66 20 3d 20 70 49 74 65  ter->iEof = pIte
2c00: 72 2d 3e 69 52 65 61 64 4f 66 66 20 2b 20 6e 42  r->iReadOff + nB
2c10: 79 74 65 3b 0a 20 20 7d 0a 20 20 69 66 28 20 72  yte;.  }.  if( r
2c20: 63 3d 3d 53 51 4c 49 54 45 5f 4f 4b 20 29 7b 0a  c==SQLITE_OK ){.
2c30: 20 20 20 20 72 63 20 3d 20 76 64 62 65 53 6f 72      rc = vdbeSor
2c40: 74 65 72 49 74 65 72 4e 65 78 74 28 64 62 2c 20  terIterNext(db, 
2c50: 70 49 74 65 72 29 3b 0a 20 20 7d 0a 20 20 72 65  pIter);.  }.  re
2c60: 74 75 72 6e 20 72 63 3b 0a 7d 0a 0a 0a 2f 2a 0a  turn rc;.}.../*.
2c70: 2a 2a 20 43 6f 6d 70 61 72 65 20 6b 65 79 31 20  ** Compare key1 
2c80: 28 62 75 66 66 65 72 20 70 4b 65 79 31 2c 20 73  (buffer pKey1, s
2c90: 69 7a 65 20 6e 4b 65 79 31 20 62 79 74 65 73 29  ize nKey1 bytes)
2ca0: 20 77 69 74 68 20 6b 65 79 32 20 28 62 75 66 66   with key2 (buff
2cb0: 65 72 20 70 4b 65 79 32 2c 20 0a 2a 2a 20 73 69  er pKey2, .** si
2cc0: 7a 65 20 6e 4b 65 79 32 20 62 79 74 65 73 29 2e  ze nKey2 bytes).
2cd0: 20 20 41 72 67 75 6d 65 6e 74 20 70 4b 65 79 49    Argument pKeyI
2ce0: 6e 66 6f 20 73 75 70 70 6c 69 65 73 20 74 68 65  nfo supplies the
2cf0: 20 63 6f 6c 6c 61 74 69 6f 6e 20 66 75 6e 63 74   collation funct
2d00: 69 6f 6e 73 0a 2a 2a 20 75 73 65 64 20 62 79 20  ions.** used by 
2d10: 74 68 65 20 63 6f 6d 70 61 72 69 73 6f 6e 2e 20  the comparison. 
2d20: 49 66 20 61 6e 20 65 72 72 6f 72 20 6f 63 63 75  If an error occu
2d30: 72 73 2c 20 72 65 74 75 72 6e 20 61 6e 20 53 51  rs, return an SQ
2d40: 4c 69 74 65 20 65 72 72 6f 72 20 63 6f 64 65 2e  Lite error code.
2d50: 0a 2a 2a 20 4f 74 68 65 72 77 69 73 65 2c 20 72  .** Otherwise, r
2d60: 65 74 75 72 6e 20 53 51 4c 49 54 45 5f 4f 4b 20  eturn SQLITE_OK 
2d70: 61 6e 64 20 73 65 74 20 2a 70 52 65 73 20 74 6f  and set *pRes to
2d80: 20 61 20 6e 65 67 61 74 69 76 65 2c 20 7a 65 72   a negative, zer
2d90: 6f 20 6f 72 20 70 6f 73 69 74 69 76 65 0a 2a 2a  o or positive.**
2da0: 20 76 61 6c 75 65 2c 20 64 65 70 65 6e 64 69 6e   value, dependin
2db0: 67 20 6f 6e 20 77 68 65 74 68 65 72 20 6b 65 79  g on whether key
2dc0: 31 20 69 73 20 73 6d 61 6c 6c 65 72 2c 20 65 71  1 is smaller, eq
2dd0: 75 61 6c 20 74 6f 20 6f 72 20 6c 61 72 67 65 72  ual to or larger
2de0: 20 74 68 61 6e 20 6b 65 79 32 2e 0a 2a 2a 0a 2a   than key2..**.*
2df0: 2a 20 49 66 20 74 68 65 20 62 4f 6d 69 74 52 6f  * If the bOmitRo
2e00: 77 69 64 20 61 72 67 75 6d 65 6e 74 20 69 73 20  wid argument is 
2e10: 6e 6f 6e 2d 7a 65 72 6f 2c 20 61 73 73 75 6d 65  non-zero, assume
2e20: 20 62 6f 74 68 20 6b 65 79 73 20 65 6e 64 20 69   both keys end i
2e30: 6e 20 61 20 72 6f 77 69 64 0a 2a 2a 20 66 69 65  n a rowid.** fie
2e40: 6c 64 2e 20 46 6f 72 20 74 68 65 20 70 75 72 70  ld. For the purp
2e50: 6f 73 65 73 20 6f 66 20 74 68 65 20 63 6f 6d 70  oses of the comp
2e60: 61 72 69 73 6f 6e 2c 20 69 67 6e 6f 72 65 20 69  arison, ignore i
2e70: 74 2e 20 41 6c 73 6f 2c 20 69 66 20 62 4f 6d 69  t. Also, if bOmi
2e80: 74 52 6f 77 69 64 0a 2a 2a 20 69 73 20 74 72 75  tRowid.** is tru
2e90: 65 20 61 6e 64 20 6b 65 79 31 20 63 6f 6e 74 61  e and key1 conta
2ea0: 69 6e 73 20 65 76 65 6e 20 61 20 73 69 6e 67 6c  ins even a singl
2eb0: 65 20 4e 55 4c 4c 20 76 61 6c 75 65 2c 20 69 74  e NULL value, it
2ec0: 20 69 73 20 63 6f 6e 73 69 64 65 72 65 64 20 74   is considered t
2ed0: 6f 0a 2a 2a 20 62 65 20 6c 65 73 73 20 74 68 61  o.** be less tha
2ee0: 6e 20 6b 65 79 32 2e 20 45 76 65 6e 20 69 66 20  n key2. Even if 
2ef0: 6b 65 79 32 20 61 6c 73 6f 20 63 6f 6e 74 61 69  key2 also contai
2f00: 6e 73 20 4e 55 4c 4c 20 76 61 6c 75 65 73 2e 0a  ns NULL values..
2f10: 2a 2a 0a 2a 2a 20 49 66 20 70 4b 65 79 32 20 69  **.** If pKey2 i
2f20: 73 20 70 61 73 73 65 64 20 61 20 4e 55 4c 4c 20  s passed a NULL 
2f30: 70 6f 69 6e 74 65 72 2c 20 74 68 65 6e 20 69 74  pointer, then it
2f40: 20 69 73 20 61 73 73 75 6d 65 64 20 74 68 61 74   is assumed that
2f50: 20 74 68 65 20 70 43 73 72 2d 3e 61 53 70 61 63   the pCsr->aSpac
2f60: 65 0a 2a 2a 20 68 61 73 20 62 65 65 6e 20 61 6c  e.** has been al
2f70: 6c 6f 63 61 74 65 64 20 61 6e 64 20 63 6f 6e 74  located and cont
2f80: 61 69 6e 73 20 61 6e 20 75 6e 70 61 63 6b 65 64  ains an unpacked
2f90: 20 72 65 63 6f 72 64 20 74 68 61 74 20 69 73 20   record that is 
2fa0: 75 73 65 64 20 61 73 20 6b 65 79 32 2e 0a 2a 2f  used as key2..*/
2fb0: 0a 73 74 61 74 69 63 20 69 6e 74 20 76 64 62 65  .static int vdbe
2fc0: 53 6f 72 74 65 72 43 6f 6d 70 61 72 65 28 0a 20  SorterCompare(. 
2fd0: 20 56 64 62 65 43 75 72 73 6f 72 20 2a 70 43 73   VdbeCursor *pCs
2fe0: 72 2c 20 20 20 20 20 20 20 20 20 20 20 20 20 20  r,              
2ff0: 20 2f 2a 20 43 75 72 73 6f 72 20 6f 62 6a 65 63   /* Cursor objec
3000: 74 20 28 66 6f 72 20 70 4b 65 79 49 6e 66 6f 29  t (for pKeyInfo)
3010: 20 2a 2f 0a 20 20 69 6e 74 20 62 4f 6d 69 74 52   */.  int bOmitR
3020: 6f 77 69 64 2c 20 20 20 20 20 20 20 20 20 20 20  owid,           
3030: 20 20 20 20 20 20 2f 2a 20 49 67 6e 6f 72 65 20        /* Ignore 
3040: 72 6f 77 69 64 20 66 69 65 6c 64 20 61 74 20 65  rowid field at e
3050: 6e 64 20 6f 66 20 6b 65 79 73 20 2a 2f 0a 20 20  nd of keys */.  
3060: 76 6f 69 64 20 2a 70 4b 65 79 31 2c 20 69 6e 74  void *pKey1, int
3070: 20 6e 4b 65 79 31 2c 20 20 20 20 20 20 20 20 20   nKey1,         
3080: 2f 2a 20 4c 65 66 74 20 73 69 64 65 20 6f 66 20  /* Left side of 
3090: 63 6f 6d 70 61 72 69 73 6f 6e 20 2a 2f 0a 20 20  comparison */.  
30a0: 76 6f 69 64 20 2a 70 4b 65 79 32 2c 20 69 6e 74  void *pKey2, int
30b0: 20 6e 4b 65 79 32 2c 20 20 20 20 20 20 20 20 20   nKey2,         
30c0: 2f 2a 20 52 69 67 68 74 20 73 69 64 65 20 6f 66  /* Right side of
30d0: 20 63 6f 6d 70 61 72 69 73 6f 6e 20 2a 2f 0a 20   comparison */. 
30e0: 20 69 6e 74 20 2a 70 52 65 73 20 20 20 20 20 20   int *pRes      
30f0: 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20                  
3100: 20 2f 2a 20 4f 55 54 3a 20 52 65 73 75 6c 74 20   /* OUT: Result 
3110: 6f 66 20 63 6f 6d 70 61 72 69 73 6f 6e 20 2a 2f  of comparison */
3120: 0a 29 7b 0a 20 20 4b 65 79 49 6e 66 6f 20 2a 70  .){.  KeyInfo *p
3130: 4b 65 79 49 6e 66 6f 20 3d 20 70 43 73 72 2d 3e  KeyInfo = pCsr->
3140: 70 4b 65 79 49 6e 66 6f 3b 0a 20 20 56 64 62 65  pKeyInfo;.  Vdbe
3150: 53 6f 72 74 65 72 20 2a 70 53 6f 72 74 65 72 20  Sorter *pSorter 
3160: 3d 20 70 43 73 72 2d 3e 70 53 6f 72 74 65 72 3b  = pCsr->pSorter;
3170: 0a 20 20 63 68 61 72 20 2a 61 53 70 61 63 65 20  .  char *aSpace 
3180: 3d 20 70 53 6f 72 74 65 72 2d 3e 61 53 70 61 63  = pSorter->aSpac
3190: 65 3b 0a 20 20 69 6e 74 20 6e 53 70 61 63 65 20  e;.  int nSpace 
31a0: 3d 20 70 53 6f 72 74 65 72 2d 3e 6e 53 70 61 63  = pSorter->nSpac
31b0: 65 3b 0a 20 20 55 6e 70 61 63 6b 65 64 52 65 63  e;.  UnpackedRec
31c0: 6f 72 64 20 2a 72 32 3b 0a 20 20 69 6e 74 20 69  ord *r2;.  int i
31d0: 3b 0a 0a 20 20 69 66 28 20 61 53 70 61 63 65 3d  ;..  if( aSpace=
31e0: 3d 30 20 29 7b 0a 20 20 20 20 6e 53 70 61 63 65  =0 ){.    nSpace
31f0: 20 3d 20 52 4f 55 4e 44 38 28 73 69 7a 65 6f 66   = ROUND8(sizeof
3200: 28 55 6e 70 61 63 6b 65 64 52 65 63 6f 72 64 29  (UnpackedRecord)
3210: 29 2b 28 70 4b 65 79 49 6e 66 6f 2d 3e 6e 46 69  )+(pKeyInfo->nFi
3220: 65 6c 64 2b 31 29 2a 73 69 7a 65 6f 66 28 4d 65  eld+1)*sizeof(Me
3230: 6d 29 3b 0a 20 20 20 20 61 53 70 61 63 65 20 3d  m);.    aSpace =
3240: 20 28 63 68 61 72 20 2a 29 73 71 6c 69 74 65 33   (char *)sqlite3
3250: 4d 61 6c 6c 6f 63 28 6e 53 70 61 63 65 29 3b 0a  Malloc(nSpace);.
3260: 20 20 20 20 69 66 28 20 61 53 70 61 63 65 3d 3d      if( aSpace==
3270: 30 20 29 20 72 65 74 75 72 6e 20 53 51 4c 49 54  0 ) return SQLIT
3280: 45 5f 4e 4f 4d 45 4d 3b 0a 20 20 20 20 70 53 6f  E_NOMEM;.    pSo
3290: 72 74 65 72 2d 3e 61 53 70 61 63 65 20 3d 20 61  rter->aSpace = a
32a0: 53 70 61 63 65 3b 0a 20 20 20 20 70 53 6f 72 74  Space;.    pSort
32b0: 65 72 2d 3e 6e 53 70 61 63 65 20 3d 20 6e 53 70  er->nSpace = nSp
32c0: 61 63 65 3b 0a 20 20 7d 0a 0a 20 20 69 66 28 20  ace;.  }..  if( 
32d0: 70 4b 65 79 32 20 29 7b 0a 20 20 20 20 2f 2a 20  pKey2 ){.    /* 
32e0: 54 68 69 73 20 63 61 6c 6c 20 63 61 6e 6e 6f 74  This call cannot
32f0: 20 66 61 69 6c 2e 20 41 73 20 74 68 65 20 6d 65   fail. As the me
3300: 6d 6f 72 79 20 69 73 20 61 6c 72 65 61 64 79 20  mory is already 
3310: 61 6c 6c 6f 63 61 74 65 64 2e 20 2a 2f 0a 20 20  allocated. */.  
3320: 20 20 72 32 20 3d 20 73 71 6c 69 74 65 33 56 64    r2 = sqlite3Vd
3330: 62 65 52 65 63 6f 72 64 55 6e 70 61 63 6b 28 70  beRecordUnpack(p
3340: 4b 65 79 49 6e 66 6f 2c 20 6e 4b 65 79 32 2c 20  KeyInfo, nKey2, 
3350: 70 4b 65 79 32 2c 20 61 53 70 61 63 65 2c 20 6e  pKey2, aSpace, n
3360: 53 70 61 63 65 29 3b 0a 20 20 20 20 61 73 73 65  Space);.    asse
3370: 72 74 28 20 72 32 20 26 26 20 28 72 32 2d 3e 66  rt( r2 && (r2->f
3380: 6c 61 67 73 20 26 20 55 4e 50 41 43 4b 45 44 5f  lags & UNPACKED_
3390: 4e 45 45 44 5f 46 52 45 45 29 3d 3d 30 20 29 3b  NEED_FREE)==0 );
33a0: 0a 20 20 20 20 61 73 73 65 72 74 28 20 72 32 3d  .    assert( r2=
33b0: 3d 61 53 70 61 63 65 20 29 3b 0a 20 20 7d 65 6c  =aSpace );.  }el
33c0: 73 65 7b 0a 20 20 20 20 72 32 20 3d 20 28 55 6e  se{.    r2 = (Un
33d0: 70 61 63 6b 65 64 52 65 63 6f 72 64 20 2a 29 61  packedRecord *)a
33e0: 53 70 61 63 65 3b 0a 20 20 20 20 61 73 73 65 72  Space;.    asser
33f0: 74 28 20 21 62 4f 6d 69 74 52 6f 77 69 64 20 29  t( !bOmitRowid )
3400: 3b 0a 20 20 7d 0a 0a 20 20 69 66 28 20 62 4f 6d  ;.  }..  if( bOm
3410: 69 74 52 6f 77 69 64 20 29 7b 0a 20 20 20 20 66  itRowid ){.    f
3420: 6f 72 28 69 3d 30 3b 20 69 3c 72 32 2d 3e 6e 46  or(i=0; i<r2->nF
3430: 69 65 6c 64 2d 31 3b 20 69 2b 2b 29 7b 0a 20 20  ield-1; i++){.  
3440: 20 20 20 20 69 66 28 20 72 32 2d 3e 61 4d 65 6d      if( r2->aMem
3450: 5b 69 5d 2e 66 6c 61 67 73 20 26 20 4d 45 4d 5f  [i].flags & MEM_
3460: 4e 75 6c 6c 20 29 7b 0a 20 20 20 20 20 20 20 20  Null ){.        
3470: 2a 70 52 65 73 20 3d 20 2d 31 3b 0a 20 20 20 20  *pRes = -1;.    
3480: 20 20 20 20 72 65 74 75 72 6e 20 53 51 4c 49 54      return SQLIT
3490: 45 5f 4f 4b 3b 0a 20 20 20 20 20 20 7d 0a 20 20  E_OK;.      }.  
34a0: 20 20 7d 0a 20 20 20 20 72 32 2d 3e 66 6c 61 67    }.    r2->flag
34b0: 73 20 7c 3d 20 55 4e 50 41 43 4b 45 44 5f 50 52  s |= UNPACKED_PR
34c0: 45 46 49 58 5f 4d 41 54 43 48 3b 0a 20 20 20 20  EFIX_MATCH;.    
34d0: 72 32 2d 3e 6e 46 69 65 6c 64 2d 2d 3b 0a 20 20  r2->nField--;.  
34e0: 20 20 61 73 73 65 72 74 28 20 72 32 2d 3e 6e 46    assert( r2->nF
34f0: 69 65 6c 64 3e 30 20 29 3b 0a 20 20 7d 0a 0a 20  ield>0 );.  }.. 
3500: 20 2a 70 52 65 73 20 3d 20 73 71 6c 69 74 65 33   *pRes = sqlite3
3510: 56 64 62 65 52 65 63 6f 72 64 43 6f 6d 70 61 72  VdbeRecordCompar
3520: 65 28 6e 4b 65 79 31 2c 20 70 4b 65 79 31 2c 20  e(nKey1, pKey1, 
3530: 72 32 29 3b 0a 20 20 72 65 74 75 72 6e 20 53 51  r2);.  return SQ
3540: 4c 49 54 45 5f 4f 4b 3b 0a 7d 0a 0a 2f 2a 0a 2a  LITE_OK;.}../*.*
3550: 2a 20 54 68 69 73 20 66 75 6e 63 74 69 6f 6e 20  * This function 
3560: 69 73 20 63 61 6c 6c 65 64 20 74 6f 20 63 6f 6d  is called to com
3570: 70 61 72 65 20 74 77 6f 20 69 74 65 72 61 74 6f  pare two iterato
3580: 72 20 6b 65 79 73 20 77 68 65 6e 20 6d 65 72 67  r keys when merg
3590: 69 6e 67 20 0a 2a 2a 20 6d 75 6c 74 69 70 6c 65  ing .** multiple
35a0: 20 62 2d 74 72 65 65 20 73 65 67 6d 65 6e 74 73   b-tree segments
35b0: 2e 20 50 61 72 61 6d 65 74 65 72 20 69 4f 75 74  . Parameter iOut
35c0: 20 69 73 20 74 68 65 20 69 6e 64 65 78 20 6f 66   is the index of
35d0: 20 74 68 65 20 61 54 72 65 65 5b 5d 20 0a 2a 2a   the aTree[] .**
35e0: 20 76 61 6c 75 65 20 74 6f 20 72 65 63 61 6c 63   value to recalc
35f0: 75 6c 61 74 65 2e 0a 2a 2f 0a 73 74 61 74 69 63  ulate..*/.static
3600: 20 69 6e 74 20 76 64 62 65 53 6f 72 74 65 72 44   int vdbeSorterD
3610: 6f 43 6f 6d 70 61 72 65 28 56 64 62 65 43 75 72  oCompare(VdbeCur
3620: 73 6f 72 20 2a 70 43 73 72 2c 20 69 6e 74 20 69  sor *pCsr, int i
3630: 4f 75 74 29 7b 0a 20 20 56 64 62 65 53 6f 72 74  Out){.  VdbeSort
3640: 65 72 20 2a 70 53 6f 72 74 65 72 20 3d 20 70 43  er *pSorter = pC
3650: 73 72 2d 3e 70 53 6f 72 74 65 72 3b 0a 20 20 69  sr->pSorter;.  i
3660: 6e 74 20 69 31 3b 0a 20 20 69 6e 74 20 69 32 3b  nt i1;.  int i2;
3670: 0a 20 20 69 6e 74 20 69 52 65 73 3b 0a 20 20 56  .  int iRes;.  V
3680: 64 62 65 53 6f 72 74 65 72 49 74 65 72 20 2a 70  dbeSorterIter *p
3690: 31 3b 0a 20 20 56 64 62 65 53 6f 72 74 65 72 49  1;.  VdbeSorterI
36a0: 74 65 72 20 2a 70 32 3b 0a 0a 20 20 61 73 73 65  ter *p2;..  asse
36b0: 72 74 28 20 69 4f 75 74 3c 70 53 6f 72 74 65 72  rt( iOut<pSorter
36c0: 2d 3e 6e 54 72 65 65 20 26 26 20 69 4f 75 74 3e  ->nTree && iOut>
36d0: 30 20 29 3b 0a 0a 20 20 69 66 28 20 69 4f 75 74  0 );..  if( iOut
36e0: 3e 3d 28 70 53 6f 72 74 65 72 2d 3e 6e 54 72 65  >=(pSorter->nTre
36f0: 65 2f 32 29 20 29 7b 0a 20 20 20 20 69 31 20 3d  e/2) ){.    i1 =
3700: 20 28 69 4f 75 74 20 2d 20 70 53 6f 72 74 65 72   (iOut - pSorter
3710: 2d 3e 6e 54 72 65 65 2f 32 29 20 2a 20 32 3b 0a  ->nTree/2) * 2;.
3720: 20 20 20 20 69 32 20 3d 20 69 31 20 2b 20 31 3b      i2 = i1 + 1;
3730: 0a 20 20 7d 65 6c 73 65 7b 0a 20 20 20 20 69 31  .  }else{.    i1
3740: 20 3d 20 70 53 6f 72 74 65 72 2d 3e 61 54 72 65   = pSorter->aTre
3750: 65 5b 69 4f 75 74 2a 32 5d 3b 0a 20 20 20 20 69  e[iOut*2];.    i
3760: 32 20 3d 20 70 53 6f 72 74 65 72 2d 3e 61 54 72  2 = pSorter->aTr
3770: 65 65 5b 69 4f 75 74 2a 32 2b 31 5d 3b 0a 20 20  ee[iOut*2+1];.  
3780: 7d 0a 0a 20 20 70 31 20 3d 20 26 70 53 6f 72 74  }..  p1 = &pSort
3790: 65 72 2d 3e 61 49 74 65 72 5b 69 31 5d 3b 0a 20  er->aIter[i1];. 
37a0: 20 70 32 20 3d 20 26 70 53 6f 72 74 65 72 2d 3e   p2 = &pSorter->
37b0: 61 49 74 65 72 5b 69 32 5d 3b 0a 0a 20 20 69 66  aIter[i2];..  if
37c0: 28 20 70 31 2d 3e 70 46 69 6c 65 3d 3d 30 20 29  ( p1->pFile==0 )
37d0: 7b 0a 20 20 20 20 69 52 65 73 20 3d 20 69 32 3b  {.    iRes = i2;
37e0: 0a 20 20 7d 65 6c 73 65 20 69 66 28 20 70 32 2d  .  }else if( p2-
37f0: 3e 70 46 69 6c 65 3d 3d 30 20 29 7b 0a 20 20 20  >pFile==0 ){.   
3800: 20 69 52 65 73 20 3d 20 69 31 3b 0a 20 20 7d 65   iRes = i1;.  }e
3810: 6c 73 65 7b 0a 20 20 20 20 69 6e 74 20 72 65 73  lse{.    int res
3820: 3b 0a 20 20 20 20 69 6e 74 20 72 63 20 3d 20 76  ;.    int rc = v
3830: 64 62 65 53 6f 72 74 65 72 43 6f 6d 70 61 72 65  dbeSorterCompare
3840: 28 0a 20 20 20 20 20 20 20 20 70 43 73 72 2c 20  (.        pCsr, 
3850: 30 2c 20 70 31 2d 3e 61 4b 65 79 2c 20 70 31 2d  0, p1->aKey, p1-
3860: 3e 6e 4b 65 79 2c 20 70 32 2d 3e 61 4b 65 79 2c  >nKey, p2->aKey,
3870: 20 70 32 2d 3e 6e 4b 65 79 2c 20 26 72 65 73 0a   p2->nKey, &res.
3880: 20 20 20 20 29 3b 0a 20 20 20 20 69 66 28 20 72      );.    if( r
3890: 63 21 3d 53 51 4c 49 54 45 5f 4f 4b 20 29 20 72  c!=SQLITE_OK ) r
38a0: 65 74 75 72 6e 20 72 63 3b 0a 20 20 20 20 69 66  eturn rc;.    if
38b0: 28 20 72 65 73 3c 3d 30 20 29 7b 0a 20 20 20 20  ( res<=0 ){.    
38c0: 20 20 69 52 65 73 20 3d 20 69 31 3b 0a 20 20 20    iRes = i1;.   
38d0: 20 7d 65 6c 73 65 7b 0a 20 20 20 20 20 20 69 52   }else{.      iR
38e0: 65 73 20 3d 20 69 32 3b 0a 20 20 20 20 7d 0a 20  es = i2;.    }. 
38f0: 20 7d 0a 0a 20 20 70 53 6f 72 74 65 72 2d 3e 61   }..  pSorter->a
3900: 54 72 65 65 5b 69 4f 75 74 5d 20 3d 20 69 52 65  Tree[iOut] = iRe
3910: 73 3b 0a 20 20 72 65 74 75 72 6e 20 53 51 4c 49  s;.  return SQLI
3920: 54 45 5f 4f 4b 3b 0a 7d 0a 0a 2f 2a 0a 2a 2a 20  TE_OK;.}../*.** 
3930: 49 6e 69 74 69 61 6c 69 7a 65 20 74 68 65 20 74  Initialize the t
3940: 65 6d 70 6f 72 61 72 79 20 69 6e 64 65 78 20 63  emporary index c
3950: 75 72 73 6f 72 20 6a 75 73 74 20 6f 70 65 6e 65  ursor just opene
3960: 64 20 61 73 20 61 20 73 6f 72 74 65 72 20 63 75  d as a sorter cu
3970: 72 73 6f 72 2e 0a 2a 2f 0a 69 6e 74 20 73 71 6c  rsor..*/.int sql
3980: 69 74 65 33 56 64 62 65 53 6f 72 74 65 72 49 6e  ite3VdbeSorterIn
3990: 69 74 28 73 71 6c 69 74 65 33 20 2a 64 62 2c 20  it(sqlite3 *db, 
39a0: 56 64 62 65 43 75 72 73 6f 72 20 2a 70 43 73 72  VdbeCursor *pCsr
39b0: 29 7b 0a 20 20 69 6e 74 20 70 67 73 7a 3b 20 20  ){.  int pgsz;  
39c0: 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20                  
39d0: 20 20 20 20 20 2f 2a 20 50 61 67 65 20 73 69 7a       /* Page siz
39e0: 65 20 6f 66 20 6d 61 69 6e 20 64 61 74 61 62 61  e of main databa
39f0: 73 65 20 2a 2f 0a 20 20 69 6e 74 20 6d 78 43 61  se */.  int mxCa
3a00: 63 68 65 3b 20 20 20 20 20 20 20 20 20 20 20 20  che;            
3a10: 20 20 20 20 20 20 20 20 2f 2a 20 43 61 63 68 65          /* Cache
3a20: 20 73 69 7a 65 20 2a 2f 0a 20 20 56 64 62 65 53   size */.  VdbeS
3a30: 6f 72 74 65 72 20 2a 70 53 6f 72 74 65 72 3b 20  orter *pSorter; 
3a40: 20 20 20 20 20 20 20 20 20 20 20 2f 2a 20 54 68             /* Th
3a50: 65 20 6e 65 77 20 73 6f 72 74 65 72 20 2a 2f 0a  e new sorter */.
3a60: 0a 20 20 61 73 73 65 72 74 28 20 70 43 73 72 2d  .  assert( pCsr-
3a70: 3e 70 4b 65 79 49 6e 66 6f 20 26 26 20 70 43 73  >pKeyInfo && pCs
3a80: 72 2d 3e 70 42 74 3d 3d 30 20 29 3b 0a 20 20 70  r->pBt==0 );.  p
3a90: 43 73 72 2d 3e 70 53 6f 72 74 65 72 20 3d 20 70  Csr->pSorter = p
3aa0: 53 6f 72 74 65 72 20 3d 20 73 71 6c 69 74 65 33  Sorter = sqlite3
3ab0: 44 62 4d 61 6c 6c 6f 63 5a 65 72 6f 28 64 62 2c  DbMallocZero(db,
3ac0: 20 73 69 7a 65 6f 66 28 56 64 62 65 53 6f 72 74   sizeof(VdbeSort
3ad0: 65 72 29 29 3b 0a 20 20 69 66 28 20 70 53 6f 72  er));.  if( pSor
3ae0: 74 65 72 3d 3d 30 20 29 7b 0a 20 20 20 20 72 65  ter==0 ){.    re
3af0: 74 75 72 6e 20 53 51 4c 49 54 45 5f 4e 4f 4d 45  turn SQLITE_NOME
3b00: 4d 3b 0a 20 20 7d 0a 0a 20 20 69 66 28 20 21 73  M;.  }..  if( !s
3b10: 71 6c 69 74 65 33 54 65 6d 70 49 6e 4d 65 6d 6f  qlite3TempInMemo
3b20: 72 79 28 64 62 29 20 29 7b 0a 20 20 20 20 70 67  ry(db) ){.    pg
3b30: 73 7a 20 3d 20 73 71 6c 69 74 65 33 42 74 72 65  sz = sqlite3Btre
3b40: 65 47 65 74 50 61 67 65 53 69 7a 65 28 64 62 2d  eGetPageSize(db-
3b50: 3e 61 44 62 5b 30 5d 2e 70 42 74 29 3b 0a 20 20  >aDb[0].pBt);.  
3b60: 20 20 70 53 6f 72 74 65 72 2d 3e 6d 6e 50 6d 61    pSorter->mnPma
3b70: 53 69 7a 65 20 3d 20 53 4f 52 54 45 52 5f 4d 49  Size = SORTER_MI
3b80: 4e 5f 57 4f 52 4b 49 4e 47 20 2a 20 70 67 73 7a  N_WORKING * pgsz
3b90: 3b 0a 20 20 20 20 6d 78 43 61 63 68 65 20 3d 20  ;.    mxCache = 
3ba0: 64 62 2d 3e 61 44 62 5b 30 5d 2e 70 53 63 68 65  db->aDb[0].pSche
3bb0: 6d 61 2d 3e 63 61 63 68 65 5f 73 69 7a 65 3b 0a  ma->cache_size;.
3bc0: 20 20 20 20 69 66 28 20 6d 78 43 61 63 68 65 3c      if( mxCache<
3bd0: 53 4f 52 54 45 52 5f 4d 49 4e 5f 57 4f 52 4b 49  SORTER_MIN_WORKI
3be0: 4e 47 20 29 20 6d 78 43 61 63 68 65 20 3d 20 53  NG ) mxCache = S
3bf0: 4f 52 54 45 52 5f 4d 49 4e 5f 57 4f 52 4b 49 4e  ORTER_MIN_WORKIN
3c00: 47 3b 0a 20 20 20 20 70 53 6f 72 74 65 72 2d 3e  G;.    pSorter->
3c10: 6d 78 50 6d 61 53 69 7a 65 20 3d 20 6d 78 43 61  mxPmaSize = mxCa
3c20: 63 68 65 20 2a 20 70 67 73 7a 3b 0a 20 20 7d 0a  che * pgsz;.  }.
3c30: 0a 20 20 72 65 74 75 72 6e 20 53 51 4c 49 54 45  .  return SQLITE
3c40: 5f 4f 4b 3b 0a 7d 0a 0a 2f 2a 0a 2a 2a 20 46 72  _OK;.}../*.** Fr
3c50: 65 65 20 74 68 65 20 6c 69 73 74 20 6f 66 20 73  ee the list of s
3c60: 6f 72 74 65 64 20 72 65 63 6f 72 64 73 20 73 74  orted records st
3c70: 61 72 74 69 6e 67 20 61 74 20 70 52 65 63 6f 72  arting at pRecor
3c80: 64 2e 0a 2a 2f 0a 73 74 61 74 69 63 20 76 6f 69  d..*/.static voi
3c90: 64 20 76 64 62 65 53 6f 72 74 65 72 52 65 63 6f  d vdbeSorterReco
3ca0: 72 64 46 72 65 65 28 73 71 6c 69 74 65 33 20 2a  rdFree(sqlite3 *
3cb0: 64 62 2c 20 53 6f 72 74 65 72 52 65 63 6f 72 64  db, SorterRecord
3cc0: 20 2a 70 52 65 63 6f 72 64 29 7b 0a 20 20 53 6f   *pRecord){.  So
3cd0: 72 74 65 72 52 65 63 6f 72 64 20 2a 70 3b 0a 20  rterRecord *p;. 
3ce0: 20 53 6f 72 74 65 72 52 65 63 6f 72 64 20 2a 70   SorterRecord *p
3cf0: 4e 65 78 74 3b 0a 20 20 66 6f 72 28 70 3d 70 52  Next;.  for(p=pR
3d00: 65 63 6f 72 64 3b 20 70 3b 20 70 3d 70 4e 65 78  ecord; p; p=pNex
3d10: 74 29 7b 0a 20 20 20 20 70 4e 65 78 74 20 3d 20  t){.    pNext = 
3d20: 70 2d 3e 70 4e 65 78 74 3b 0a 20 20 20 20 73 71  p->pNext;.    sq
3d30: 6c 69 74 65 33 44 62 46 72 65 65 28 64 62 2c 20  lite3DbFree(db, 
3d40: 70 29 3b 0a 20 20 7d 0a 7d 0a 0a 2f 2a 0a 2a 2a  p);.  }.}../*.**
3d50: 20 46 72 65 65 20 61 6e 79 20 63 75 72 73 6f 72   Free any cursor
3d60: 20 63 6f 6d 70 6f 6e 65 6e 74 73 20 61 6c 6c 6f   components allo
3d70: 63 61 74 65 64 20 62 79 20 73 71 6c 69 74 65 33  cated by sqlite3
3d80: 56 64 62 65 53 6f 72 74 65 72 58 58 58 20 72 6f  VdbeSorterXXX ro
3d90: 75 74 69 6e 65 73 2e 0a 2a 2f 0a 76 6f 69 64 20  utines..*/.void 
3da0: 73 71 6c 69 74 65 33 56 64 62 65 53 6f 72 74 65  sqlite3VdbeSorte
3db0: 72 43 6c 6f 73 65 28 73 71 6c 69 74 65 33 20 2a  rClose(sqlite3 *
3dc0: 64 62 2c 20 56 64 62 65 43 75 72 73 6f 72 20 2a  db, VdbeCursor *
3dd0: 70 43 73 72 29 7b 0a 20 20 56 64 62 65 53 6f 72  pCsr){.  VdbeSor
3de0: 74 65 72 20 2a 70 53 6f 72 74 65 72 20 3d 20 70  ter *pSorter = p
3df0: 43 73 72 2d 3e 70 53 6f 72 74 65 72 3b 0a 20 20  Csr->pSorter;.  
3e00: 69 66 28 20 70 53 6f 72 74 65 72 20 29 7b 0a 20  if( pSorter ){. 
3e10: 20 20 20 69 66 28 20 70 53 6f 72 74 65 72 2d 3e     if( pSorter->
3e20: 61 49 74 65 72 20 29 7b 0a 20 20 20 20 20 20 69  aIter ){.      i
3e30: 6e 74 20 69 3b 0a 20 20 20 20 20 20 66 6f 72 28  nt i;.      for(
3e40: 69 3d 30 3b 20 69 3c 70 53 6f 72 74 65 72 2d 3e  i=0; i<pSorter->
3e50: 6e 54 72 65 65 3b 20 69 2b 2b 29 7b 0a 20 20 20  nTree; i++){.   
3e60: 20 20 20 20 20 76 64 62 65 53 6f 72 74 65 72 49       vdbeSorterI
3e70: 74 65 72 5a 65 72 6f 28 64 62 2c 20 26 70 53 6f  terZero(db, &pSo
3e80: 72 74 65 72 2d 3e 61 49 74 65 72 5b 69 5d 29 3b  rter->aIter[i]);
3e90: 0a 20 20 20 20 20 20 7d 0a 20 20 20 20 20 20 73  .      }.      s
3ea0: 71 6c 69 74 65 33 44 62 46 72 65 65 28 64 62 2c  qlite3DbFree(db,
3eb0: 20 70 53 6f 72 74 65 72 2d 3e 61 49 74 65 72 29   pSorter->aIter)
3ec0: 3b 0a 20 20 20 20 7d 0a 20 20 20 20 69 66 28 20  ;.    }.    if( 
3ed0: 70 53 6f 72 74 65 72 2d 3e 70 54 65 6d 70 31 20  pSorter->pTemp1 
3ee0: 29 7b 0a 20 20 20 20 20 20 73 71 6c 69 74 65 33  ){.      sqlite3
3ef0: 4f 73 43 6c 6f 73 65 46 72 65 65 28 70 53 6f 72  OsCloseFree(pSor
3f00: 74 65 72 2d 3e 70 54 65 6d 70 31 29 3b 0a 20 20  ter->pTemp1);.  
3f10: 20 20 7d 0a 20 20 20 20 76 64 62 65 53 6f 72 74    }.    vdbeSort
3f20: 65 72 52 65 63 6f 72 64 46 72 65 65 28 64 62 2c  erRecordFree(db,
3f30: 20 70 53 6f 72 74 65 72 2d 3e 70 52 65 63 6f 72   pSorter->pRecor
3f40: 64 29 3b 0a 20 20 20 20 73 71 6c 69 74 65 33 5f  d);.    sqlite3_
3f50: 66 72 65 65 28 70 53 6f 72 74 65 72 2d 3e 61 53  free(pSorter->aS
3f60: 70 61 63 65 29 3b 0a 20 20 20 20 73 71 6c 69 74  pace);.    sqlit
3f70: 65 33 44 62 46 72 65 65 28 64 62 2c 20 70 53 6f  e3DbFree(db, pSo
3f80: 72 74 65 72 29 3b 0a 20 20 20 20 70 43 73 72 2d  rter);.    pCsr-
3f90: 3e 70 53 6f 72 74 65 72 20 3d 20 30 3b 0a 20 20  >pSorter = 0;.  
3fa0: 7d 0a 7d 0a 0a 2f 2a 0a 2a 2a 20 41 6c 6c 6f 63  }.}../*.** Alloc
3fb0: 61 74 65 20 73 70 61 63 65 20 66 6f 72 20 61 20  ate space for a 
3fc0: 66 69 6c 65 2d 68 61 6e 64 6c 65 20 61 6e 64 20  file-handle and 
3fd0: 6f 70 65 6e 20 61 20 74 65 6d 70 6f 72 61 72 79  open a temporary
3fe0: 20 66 69 6c 65 2e 20 49 66 20 73 75 63 63 65 73   file. If succes
3ff0: 73 66 75 6c 2c 0a 2a 2a 20 73 65 74 20 2a 70 70  sful,.** set *pp
4000: 46 69 6c 65 20 74 6f 20 70 6f 69 6e 74 20 74 6f  File to point to
4010: 20 74 68 65 20 6d 61 6c 6c 6f 63 27 64 20 66 69   the malloc'd fi
4020: 6c 65 2d 68 61 6e 64 6c 65 20 61 6e 64 20 72 65  le-handle and re
4030: 74 75 72 6e 20 53 51 4c 49 54 45 5f 4f 4b 2e 0a  turn SQLITE_OK..
4040: 2a 2a 20 4f 74 68 65 72 77 69 73 65 2c 20 73 65  ** Otherwise, se
4050: 74 20 2a 70 70 46 69 6c 65 20 74 6f 20 30 20 61  t *ppFile to 0 a
4060: 6e 64 20 72 65 74 75 72 6e 20 61 6e 20 53 51 4c  nd return an SQL
4070: 69 74 65 20 65 72 72 6f 72 20 63 6f 64 65 2e 0a  ite error code..
4080: 2a 2f 0a 73 74 61 74 69 63 20 69 6e 74 20 76 64  */.static int vd
4090: 62 65 53 6f 72 74 65 72 4f 70 65 6e 54 65 6d 70  beSorterOpenTemp
40a0: 46 69 6c 65 28 73 71 6c 69 74 65 33 20 2a 64 62  File(sqlite3 *db
40b0: 2c 20 73 71 6c 69 74 65 33 5f 66 69 6c 65 20 2a  , sqlite3_file *
40c0: 2a 70 70 46 69 6c 65 29 7b 0a 20 20 69 6e 74 20  *ppFile){.  int 
40d0: 64 75 6d 6d 79 3b 0a 20 20 72 65 74 75 72 6e 20  dummy;.  return 
40e0: 73 71 6c 69 74 65 33 4f 73 4f 70 65 6e 4d 61 6c  sqlite3OsOpenMal
40f0: 6c 6f 63 28 64 62 2d 3e 70 56 66 73 2c 20 30 2c  loc(db->pVfs, 0,
4100: 20 70 70 46 69 6c 65 2c 0a 20 20 20 20 20 20 53   ppFile,.      S
4110: 51 4c 49 54 45 5f 4f 50 45 4e 5f 54 45 4d 50 5f  QLITE_OPEN_TEMP_
4120: 4a 4f 55 52 4e 41 4c 20 7c 0a 20 20 20 20 20 20  JOURNAL |.      
4130: 53 51 4c 49 54 45 5f 4f 50 45 4e 5f 52 45 41 44  SQLITE_OPEN_READ
4140: 57 52 49 54 45 20 20 20 20 7c 20 53 51 4c 49 54  WRITE    | SQLIT
4150: 45 5f 4f 50 45 4e 5f 43 52 45 41 54 45 20 7c 0a  E_OPEN_CREATE |.
4160: 20 20 20 20 20 20 53 51 4c 49 54 45 5f 4f 50 45        SQLITE_OPE
4170: 4e 5f 45 58 43 4c 55 53 49 56 45 20 20 20 20 7c  N_EXCLUSIVE    |
4180: 20 53 51 4c 49 54 45 5f 4f 50 45 4e 5f 44 45 4c   SQLITE_OPEN_DEL
4190: 45 54 45 4f 4e 43 4c 4f 53 45 2c 20 26 64 75 6d  ETEONCLOSE, &dum
41a0: 6d 79 0a 20 20 29 3b 0a 7d 0a 0a 2f 2a 0a 2a 2a  my.  );.}../*.**
41b0: 20 41 74 74 65 6d 70 20 74 6f 20 6d 65 72 67 65   Attemp to merge
41c0: 20 74 68 65 20 74 77 6f 20 73 6f 72 74 65 64 20   the two sorted 
41d0: 6c 69 73 74 73 20 70 31 20 61 6e 64 20 70 32 20  lists p1 and p2 
41e0: 69 6e 74 6f 20 61 20 73 69 6e 67 6c 65 20 6c 69  into a single li
41f0: 73 74 2e 20 49 66 20 6e 6f 0a 2a 2a 20 65 72 72  st. If no.** err
4200: 6f 72 20 6f 63 63 75 72 73 20 73 65 74 20 2a 70  or occurs set *p
4210: 70 4f 75 74 20 74 6f 20 74 68 65 20 68 65 61 64  pOut to the head
4220: 20 6f 66 20 74 68 65 20 6e 65 77 20 6c 69 73 74   of the new list
4230: 20 61 6e 64 20 72 65 74 75 72 6e 20 53 51 4c 49   and return SQLI
4240: 54 45 5f 4f 4b 2e 0a 2a 2f 0a 73 74 61 74 69 63  TE_OK..*/.static
4250: 20 69 6e 74 20 76 64 62 65 53 6f 72 74 65 72 4d   int vdbeSorterM
4260: 65 72 67 65 28 0a 20 20 73 71 6c 69 74 65 33 20  erge(.  sqlite3 
4270: 2a 64 62 2c 20 20 20 20 20 20 20 20 20 20 20 20  *db,            
4280: 20 20 20 20 20 20 20 20 2f 2a 20 44 61 74 61 62          /* Datab
4290: 61 73 65 20 68 61 6e 64 6c 65 20 2a 2f 0a 20 20  ase handle */.  
42a0: 56 64 62 65 43 75 72 73 6f 72 20 2a 70 43 73 72  VdbeCursor *pCsr
42b0: 2c 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20  ,               
42c0: 2f 2a 20 46 6f 72 20 70 4b 65 79 49 6e 66 6f 20  /* For pKeyInfo 
42d0: 2a 2f 0a 20 20 53 6f 72 74 65 72 52 65 63 6f 72  */.  SorterRecor
42e0: 64 20 2a 70 31 2c 20 20 20 20 20 20 20 20 20 20  d *p1,          
42f0: 20 20 20 20 20 2f 2a 20 46 69 72 73 74 20 6c 69       /* First li
4300: 73 74 20 74 6f 20 6d 65 72 67 65 20 2a 2f 0a 20  st to merge */. 
4310: 20 53 6f 72 74 65 72 52 65 63 6f 72 64 20 2a 70   SorterRecord *p
4320: 32 2c 20 20 20 20 20 20 20 20 20 20 20 20 20 20  2,              
4330: 20 2f 2a 20 53 65 63 6f 6e 64 20 6c 69 73 74 20   /* Second list 
4340: 74 6f 20 6d 65 72 67 65 20 2a 2f 0a 20 20 53 6f  to merge */.  So
4350: 72 74 65 72 52 65 63 6f 72 64 20 2a 2a 70 70 4f  rterRecord **ppO
4360: 75 74 20 20 20 20 20 20 20 20 20 20 20 20 2f 2a  ut            /*
4370: 20 4f 55 54 3a 20 48 65 61 64 20 6f 66 20 6d 65   OUT: Head of me
4380: 72 67 65 64 20 6c 69 73 74 20 2a 2f 0a 29 7b 0a  rged list */.){.
4390: 20 20 69 6e 74 20 72 63 20 3d 20 53 51 4c 49 54    int rc = SQLIT
43a0: 45 5f 4f 4b 3b 0a 20 20 53 6f 72 74 65 72 52 65  E_OK;.  SorterRe
43b0: 63 6f 72 64 20 2a 70 46 69 6e 61 6c 20 3d 20 30  cord *pFinal = 0
43c0: 3b 0a 20 20 53 6f 72 74 65 72 52 65 63 6f 72 64  ;.  SorterRecord
43d0: 20 2a 2a 70 70 20 3d 20 26 70 46 69 6e 61 6c 3b   **pp = &pFinal;
43e0: 0a 20 20 76 6f 69 64 20 2a 70 56 61 6c 32 20 3d  .  void *pVal2 =
43f0: 20 70 32 20 3f 20 70 32 2d 3e 70 56 61 6c 20 3a   p2 ? p2->pVal :
4400: 20 30 3b 0a 0a 20 20 77 68 69 6c 65 28 20 70 31   0;..  while( p1
4410: 20 26 26 20 70 32 20 29 7b 0a 20 20 20 20 69 6e   && p2 ){.    in
4420: 74 20 72 65 73 3b 0a 20 20 20 20 72 63 20 3d 20  t res;.    rc = 
4430: 76 64 62 65 53 6f 72 74 65 72 43 6f 6d 70 61 72  vdbeSorterCompar
4440: 65 28 70 43 73 72 2c 20 30 2c 20 70 31 2d 3e 70  e(pCsr, 0, p1->p
4450: 56 61 6c 2c 20 70 31 2d 3e 6e 56 61 6c 2c 20 70  Val, p1->nVal, p
4460: 56 61 6c 32 2c 20 70 32 2d 3e 6e 56 61 6c 2c 20  Val2, p2->nVal, 
4470: 26 72 65 73 29 3b 0a 20 20 20 20 69 66 28 20 72  &res);.    if( r
4480: 63 21 3d 53 51 4c 49 54 45 5f 4f 4b 20 29 7b 0a  c!=SQLITE_OK ){.
4490: 20 20 20 20 20 20 2a 70 70 20 3d 20 30 3b 0a 20        *pp = 0;. 
44a0: 20 20 20 20 20 76 64 62 65 53 6f 72 74 65 72 52       vdbeSorterR
44b0: 65 63 6f 72 64 46 72 65 65 28 64 62 2c 20 70 31  ecordFree(db, p1
44c0: 29 3b 0a 20 20 20 20 20 20 76 64 62 65 53 6f 72  );.      vdbeSor
44d0: 74 65 72 52 65 63 6f 72 64 46 72 65 65 28 64 62  terRecordFree(db
44e0: 2c 20 70 32 29 3b 0a 20 20 20 20 20 20 76 64 62  , p2);.      vdb
44f0: 65 53 6f 72 74 65 72 52 65 63 6f 72 64 46 72 65  eSorterRecordFre
4500: 65 28 64 62 2c 20 70 46 69 6e 61 6c 29 3b 0a 20  e(db, pFinal);. 
4510: 20 20 20 20 20 2a 70 70 4f 75 74 20 3d 20 30 3b       *ppOut = 0;
4520: 0a 20 20 20 20 20 20 72 65 74 75 72 6e 20 72 63  .      return rc
4530: 3b 0a 20 20 20 20 7d 0a 20 20 20 20 69 66 28 20  ;.    }.    if( 
4540: 72 65 73 3c 3d 30 20 29 7b 0a 20 20 20 20 20 20  res<=0 ){.      
4550: 2a 70 70 20 3d 20 70 31 3b 0a 20 20 20 20 20 20  *pp = p1;.      
4560: 70 70 20 3d 20 26 70 31 2d 3e 70 4e 65 78 74 3b  pp = &p1->pNext;
4570: 0a 20 20 20 20 20 20 70 31 20 3d 20 70 31 2d 3e  .      p1 = p1->
4580: 70 4e 65 78 74 3b 0a 20 20 20 20 20 20 70 56 61  pNext;.      pVa
4590: 6c 32 20 3d 20 30 3b 0a 20 20 20 20 7d 65 6c 73  l2 = 0;.    }els
45a0: 65 7b 0a 20 20 20 20 20 20 2a 70 70 20 3d 20 70  e{.      *pp = p
45b0: 32 3b 0a 20 20 20 20 20 20 20 70 70 20 3d 20 26  2;.       pp = &
45c0: 70 32 2d 3e 70 4e 65 78 74 3b 0a 20 20 20 20 20  p2->pNext;.     
45d0: 20 70 32 20 3d 20 70 32 2d 3e 70 4e 65 78 74 3b   p2 = p2->pNext;
45e0: 0a 20 20 20 20 20 20 69 66 28 20 70 32 3d 3d 30  .      if( p2==0
45f0: 20 29 20 62 72 65 61 6b 3b 0a 20 20 20 20 20 20   ) break;.      
4600: 70 56 61 6c 32 20 3d 20 70 32 2d 3e 70 56 61 6c  pVal2 = p2->pVal
4610: 3b 0a 20 20 20 20 7d 0a 20 20 7d 0a 20 20 2a 70  ;.    }.  }.  *p
4620: 70 20 3d 20 70 31 20 3f 20 70 31 20 3a 20 70 32  p = p1 ? p1 : p2
4630: 3b 0a 0a 20 20 2a 70 70 4f 75 74 20 3d 20 70 46  ;..  *ppOut = pF
4640: 69 6e 61 6c 3b 0a 20 20 72 65 74 75 72 6e 20 53  inal;.  return S
4650: 51 4c 49 54 45 5f 4f 4b 3b 0a 7d 0a 0a 2f 2a 0a  QLITE_OK;.}../*.
4660: 2a 2a 20 53 6f 72 74 20 74 68 65 20 6c 69 6e 6b  ** Sort the link
4670: 65 64 20 6c 69 73 74 20 6f 66 20 72 65 63 6f 72  ed list of recor
4680: 64 73 20 68 65 61 64 65 64 20 61 74 20 70 43 73  ds headed at pCs
4690: 72 2d 3e 70 52 65 63 6f 72 64 2e 20 52 65 74 75  r->pRecord. Retu
46a0: 72 6e 20 53 51 4c 49 54 45 5f 4f 4b 0a 2a 2a 20  rn SQLITE_OK.** 
46b0: 69 66 20 73 75 63 63 65 73 73 66 75 6c 2c 20 6f  if successful, o
46c0: 72 20 61 6e 20 53 51 4c 69 74 65 20 65 72 72 6f  r an SQLite erro
46d0: 72 20 63 6f 64 65 20 28 69 2e 65 2e 20 53 51 4c  r code (i.e. SQL
46e0: 49 54 45 5f 4e 4f 4d 45 4d 29 20 69 66 20 61 6e  ITE_NOMEM) if an
46f0: 20 65 72 72 6f 72 0a 2a 2a 20 6f 63 63 75 72 73   error.** occurs
4700: 2e 0a 2a 2f 0a 73 74 61 74 69 63 20 69 6e 74 20  ..*/.static int 
4710: 76 64 62 65 53 6f 72 74 65 72 53 6f 72 74 28 73  vdbeSorterSort(s
4720: 71 6c 69 74 65 33 20 2a 64 62 2c 20 56 64 62 65  qlite3 *db, Vdbe
4730: 43 75 72 73 6f 72 20 2a 70 43 73 72 29 7b 0a 20  Cursor *pCsr){. 
4740: 20 69 6e 74 20 72 63 20 3d 20 53 51 4c 49 54 45   int rc = SQLITE
4750: 5f 4f 4b 3b 0a 20 20 69 6e 74 20 69 3b 0a 20 20  _OK;.  int i;.  
4760: 53 6f 72 74 65 72 52 65 63 6f 72 64 20 2a 2a 61  SorterRecord **a
4770: 53 6c 6f 74 3b 0a 20 20 53 6f 72 74 65 72 52 65  Slot;.  SorterRe
4780: 63 6f 72 64 20 2a 70 3b 0a 20 20 56 64 62 65 53  cord *p;.  VdbeS
4790: 6f 72 74 65 72 20 2a 70 53 6f 72 74 65 72 20 3d  orter *pSorter =
47a0: 20 70 43 73 72 2d 3e 70 53 6f 72 74 65 72 3b 0a   pCsr->pSorter;.
47b0: 0a 20 20 61 53 6c 6f 74 20 3d 20 28 53 6f 72 74  .  aSlot = (Sort
47c0: 65 72 52 65 63 6f 72 64 20 2a 2a 29 73 71 6c 69  erRecord **)sqli
47d0: 74 65 33 4d 61 6c 6c 6f 63 5a 65 72 6f 28 36 34  te3MallocZero(64
47e0: 20 2a 20 73 69 7a 65 6f 66 28 53 6f 72 74 65 72   * sizeof(Sorter
47f0: 52 65 63 6f 72 64 20 2a 29 29 3b 0a 20 20 69 66  Record *));.  if
4800: 28 20 21 61 53 6c 6f 74 20 29 7b 0a 20 20 20 20  ( !aSlot ){.    
4810: 72 65 74 75 72 6e 20 53 51 4c 49 54 45 5f 4e 4f  return SQLITE_NO
4820: 4d 45 4d 3b 0a 20 20 7d 0a 0a 20 20 70 20 3d 20  MEM;.  }..  p = 
4830: 70 53 6f 72 74 65 72 2d 3e 70 52 65 63 6f 72 64  pSorter->pRecord
4840: 3b 0a 20 20 77 68 69 6c 65 28 20 70 20 29 7b 0a  ;.  while( p ){.
4850: 20 20 20 20 53 6f 72 74 65 72 52 65 63 6f 72 64      SorterRecord
4860: 20 2a 70 4e 65 78 74 20 3d 20 70 2d 3e 70 4e 65   *pNext = p->pNe
4870: 78 74 3b 0a 20 20 20 20 70 2d 3e 70 4e 65 78 74  xt;.    p->pNext
4880: 20 3d 20 30 3b 0a 20 20 20 20 66 6f 72 28 69 3d   = 0;.    for(i=
4890: 30 3b 20 72 63 3d 3d 53 51 4c 49 54 45 5f 4f 4b  0; rc==SQLITE_OK
48a0: 20 26 26 20 61 53 6c 6f 74 5b 69 5d 3b 20 69 2b   && aSlot[i]; i+
48b0: 2b 29 7b 0a 20 20 20 20 20 20 72 63 20 3d 20 76  +){.      rc = v
48c0: 64 62 65 53 6f 72 74 65 72 4d 65 72 67 65 28 64  dbeSorterMerge(d
48d0: 62 2c 20 70 43 73 72 2c 20 70 2c 20 61 53 6c 6f  b, pCsr, p, aSlo
48e0: 74 5b 69 5d 2c 20 26 70 29 3b 0a 20 20 20 20 20  t[i], &p);.     
48f0: 20 61 53 6c 6f 74 5b 69 5d 20 3d 20 30 3b 0a 20   aSlot[i] = 0;. 
4900: 20 20 20 7d 0a 20 20 20 20 69 66 28 20 72 63 21     }.    if( rc!
4910: 3d 53 51 4c 49 54 45 5f 4f 4b 20 29 7b 0a 20 20  =SQLITE_OK ){.  
4920: 20 20 20 20 76 64 62 65 53 6f 72 74 65 72 52 65      vdbeSorterRe
4930: 63 6f 72 64 46 72 65 65 28 64 62 2c 20 70 4e 65  cordFree(db, pNe
4940: 78 74 29 3b 0a 20 20 20 20 20 20 62 72 65 61 6b  xt);.      break
4950: 3b 0a 20 20 20 20 7d 0a 20 20 20 20 61 53 6c 6f  ;.    }.    aSlo
4960: 74 5b 69 5d 20 3d 20 70 3b 0a 20 20 20 20 70 20  t[i] = p;.    p 
4970: 3d 20 70 4e 65 78 74 3b 0a 20 20 7d 0a 0a 20 20  = pNext;.  }..  
4980: 70 20 3d 20 30 3b 0a 20 20 66 6f 72 28 69 3d 30  p = 0;.  for(i=0
4990: 3b 20 69 3c 36 34 3b 20 69 2b 2b 29 7b 0a 20 20  ; i<64; i++){.  
49a0: 20 20 69 66 28 20 72 63 3d 3d 53 51 4c 49 54 45    if( rc==SQLITE
49b0: 5f 4f 4b 20 29 7b 0a 20 20 20 20 20 20 72 63 20  _OK ){.      rc 
49c0: 3d 20 76 64 62 65 53 6f 72 74 65 72 4d 65 72 67  = vdbeSorterMerg
49d0: 65 28 64 62 2c 20 70 43 73 72 2c 20 70 2c 20 61  e(db, pCsr, p, a
49e0: 53 6c 6f 74 5b 69 5d 2c 20 26 70 29 3b 0a 20 20  Slot[i], &p);.  
49f0: 20 20 7d 65 6c 73 65 7b 0a 20 20 20 20 20 20 76    }else{.      v
4a00: 64 62 65 53 6f 72 74 65 72 52 65 63 6f 72 64 46  dbeSorterRecordF
4a10: 72 65 65 28 64 62 2c 20 61 53 6c 6f 74 5b 69 5d  ree(db, aSlot[i]
4a20: 29 3b 0a 20 20 20 20 7d 0a 20 20 7d 0a 20 20 70  );.    }.  }.  p
4a30: 53 6f 72 74 65 72 2d 3e 70 52 65 63 6f 72 64 20  Sorter->pRecord 
4a40: 3d 20 70 3b 0a 0a 20 20 73 71 6c 69 74 65 33 5f  = p;..  sqlite3_
4a50: 66 72 65 65 28 61 53 6c 6f 74 29 3b 0a 20 20 72  free(aSlot);.  r
4a60: 65 74 75 72 6e 20 72 63 3b 0a 7d 0a 0a 0a 2f 2a  eturn rc;.}.../*
4a70: 0a 2a 2a 20 57 72 69 74 65 20 74 68 65 20 63 75  .** Write the cu
4a80: 72 72 65 6e 74 20 63 6f 6e 74 65 6e 74 73 20 6f  rrent contents o
4a90: 66 20 74 68 65 20 69 6e 2d 6d 65 6d 6f 72 79 20  f the in-memory 
4aa0: 6c 69 6e 6b 65 64 2d 6c 69 73 74 20 74 6f 20 61  linked-list to a
4ab0: 20 50 4d 41 2e 20 52 65 74 75 72 6e 0a 2a 2a 20   PMA. Return.** 
4ac0: 53 51 4c 49 54 45 5f 4f 4b 20 69 66 20 73 75 63  SQLITE_OK if suc
4ad0: 63 65 73 73 66 75 6c 2c 20 6f 72 20 61 6e 20 53  cessful, or an S
4ae0: 51 4c 69 74 65 20 65 72 72 6f 72 20 63 6f 64 65  QLite error code
4af0: 20 6f 74 68 65 72 77 69 73 65 2e 0a 2a 2a 0a 2a   otherwise..**.*
4b00: 2a 20 54 68 65 20 66 6f 72 6d 61 74 20 6f 66 20  * The format of 
4b10: 61 20 50 4d 41 20 69 73 3a 0a 2a 2a 0a 2a 2a 20  a PMA is:.**.** 
4b20: 20 20 20 20 2a 20 41 20 76 61 72 69 6e 74 2e 20      * A varint. 
4b30: 54 68 69 73 20 76 61 72 69 6e 74 20 63 6f 6e 74  This varint cont
4b40: 61 69 6e 73 20 74 68 65 20 74 6f 74 61 6c 20 6e  ains the total n
4b50: 75 6d 62 65 72 20 6f 66 20 62 79 74 65 73 20 6f  umber of bytes o
4b60: 66 20 63 6f 6e 74 65 6e 74 0a 2a 2a 20 20 20 20  f content.**    
4b70: 20 20 20 69 6e 20 74 68 65 20 50 4d 41 20 28 6e     in the PMA (n
4b80: 6f 74 20 69 6e 63 6c 75 64 69 6e 67 20 74 68 65  ot including the
4b90: 20 76 61 72 69 6e 74 20 69 74 73 65 6c 66 29 2e   varint itself).
4ba0: 0a 2a 2a 0a 2a 2a 20 20 20 20 20 2a 20 4f 6e 65  .**.**     * One
4bb0: 20 6f 72 20 6d 6f 72 65 20 72 65 63 6f 72 64 73   or more records
4bc0: 20 70 61 63 6b 65 64 20 65 6e 64 2d 74 6f 2d 65   packed end-to-e
4bd0: 6e 64 20 69 6e 20 6f 72 64 65 72 20 6f 66 20 61  nd in order of a
4be0: 73 63 65 6e 64 69 6e 67 20 6b 65 79 73 2e 20 0a  scending keys. .
4bf0: 2a 2a 20 20 20 20 20 20 20 45 61 63 68 20 72 65  **       Each re
4c00: 63 6f 72 64 20 63 6f 6e 73 69 73 74 73 20 6f 66  cord consists of
4c10: 20 61 20 76 61 72 69 6e 74 20 66 6f 6c 6c 6f 77   a varint follow
4c20: 65 64 20 62 79 20 61 20 62 6c 6f 62 20 6f 66 20  ed by a blob of 
4c30: 64 61 74 61 20 28 74 68 65 20 0a 2a 2a 20 20 20  data (the .**   
4c40: 20 20 20 20 6b 65 79 29 2e 20 54 68 65 20 76 61      key). The va
4c50: 72 69 6e 74 20 69 73 20 74 68 65 20 6e 75 6d 62  rint is the numb
4c60: 65 72 20 6f 66 20 62 79 74 65 73 20 69 6e 20 74  er of bytes in t
4c70: 68 65 20 62 6c 6f 62 20 6f 66 20 64 61 74 61 2e  he blob of data.
4c80: 0a 2a 2f 0a 73 74 61 74 69 63 20 69 6e 74 20 76  .*/.static int v
4c90: 64 62 65 53 6f 72 74 65 72 4c 69 73 74 54 6f 50  dbeSorterListToP
4ca0: 4d 41 28 73 71 6c 69 74 65 33 20 2a 64 62 2c 20  MA(sqlite3 *db, 
4cb0: 56 64 62 65 43 75 72 73 6f 72 20 2a 70 43 73 72  VdbeCursor *pCsr
4cc0: 29 7b 0a 20 20 69 6e 74 20 72 63 20 3d 20 53 51  ){.  int rc = SQ
4cd0: 4c 49 54 45 5f 4f 4b 3b 20 20 20 20 20 20 20 20  LITE_OK;        
4ce0: 20 20 20 20 20 2f 2a 20 52 65 74 75 72 6e 20 63       /* Return c
4cf0: 6f 64 65 20 2a 2f 0a 20 20 56 64 62 65 53 6f 72  ode */.  VdbeSor
4d00: 74 65 72 20 2a 70 53 6f 72 74 65 72 20 3d 20 70  ter *pSorter = p
4d10: 43 73 72 2d 3e 70 53 6f 72 74 65 72 3b 0a 0a 20  Csr->pSorter;.. 
4d20: 20 69 66 28 20 70 53 6f 72 74 65 72 2d 3e 6e 49   if( pSorter->nI
4d30: 6e 4d 65 6d 6f 72 79 3d 3d 30 20 29 7b 0a 20 20  nMemory==0 ){.  
4d40: 20 20 61 73 73 65 72 74 28 20 70 53 6f 72 74 65    assert( pSorte
4d50: 72 2d 3e 70 52 65 63 6f 72 64 3d 3d 30 20 29 3b  r->pRecord==0 );
4d60: 0a 20 20 20 20 72 65 74 75 72 6e 20 72 63 3b 0a  .    return rc;.
4d70: 20 20 7d 0a 0a 20 20 72 63 20 3d 20 76 64 62 65    }..  rc = vdbe
4d80: 53 6f 72 74 65 72 53 6f 72 74 28 64 62 2c 20 70  SorterSort(db, p
4d90: 43 73 72 29 3b 0a 0a 20 20 2f 2a 20 49 66 20 74  Csr);..  /* If t
4da0: 68 65 20 66 69 72 73 74 20 74 65 6d 70 6f 72 61  he first tempora
4db0: 72 79 20 50 4d 41 20 66 69 6c 65 20 68 61 73 20  ry PMA file has 
4dc0: 6e 6f 74 20 62 65 65 6e 20 6f 70 65 6e 65 64 2c  not been opened,
4dd0: 20 6f 70 65 6e 20 69 74 20 6e 6f 77 2e 20 2a 2f   open it now. */
4de0: 0a 20 20 69 66 28 20 72 63 3d 3d 53 51 4c 49 54  .  if( rc==SQLIT
4df0: 45 5f 4f 4b 20 26 26 20 70 53 6f 72 74 65 72 2d  E_OK && pSorter-
4e00: 3e 70 54 65 6d 70 31 3d 3d 30 20 29 7b 0a 20 20  >pTemp1==0 ){.  
4e10: 20 20 72 63 20 3d 20 76 64 62 65 53 6f 72 74 65    rc = vdbeSorte
4e20: 72 4f 70 65 6e 54 65 6d 70 46 69 6c 65 28 64 62  rOpenTempFile(db
4e30: 2c 20 26 70 53 6f 72 74 65 72 2d 3e 70 54 65 6d  , &pSorter->pTem
4e40: 70 31 29 3b 0a 20 20 20 20 61 73 73 65 72 74 28  p1);.    assert(
4e50: 20 72 63 21 3d 53 51 4c 49 54 45 5f 4f 4b 20 7c   rc!=SQLITE_OK |
4e60: 7c 20 70 53 6f 72 74 65 72 2d 3e 70 54 65 6d 70  | pSorter->pTemp
4e70: 31 20 29 3b 0a 20 20 20 20 61 73 73 65 72 74 28  1 );.    assert(
4e80: 20 70 53 6f 72 74 65 72 2d 3e 69 57 72 69 74 65   pSorter->iWrite
4e90: 4f 66 66 3d 3d 30 20 29 3b 0a 20 20 20 20 61 73  Off==0 );.    as
4ea0: 73 65 72 74 28 20 70 53 6f 72 74 65 72 2d 3e 6e  sert( pSorter->n
4eb0: 50 4d 41 3d 3d 30 20 29 3b 0a 20 20 7d 0a 0a 20  PMA==0 );.  }.. 
4ec0: 20 69 66 28 20 72 63 3d 3d 53 51 4c 49 54 45 5f   if( rc==SQLITE_
4ed0: 4f 4b 20 29 7b 0a 20 20 20 20 69 36 34 20 69 4f  OK ){.    i64 iO
4ee0: 66 66 20 3d 20 70 53 6f 72 74 65 72 2d 3e 69 57  ff = pSorter->iW
4ef0: 72 69 74 65 4f 66 66 3b 0a 20 20 20 20 53 6f 72  riteOff;.    Sor
4f00: 74 65 72 52 65 63 6f 72 64 20 2a 70 3b 0a 20 20  terRecord *p;.  
4f10: 20 20 53 6f 72 74 65 72 52 65 63 6f 72 64 20 2a    SorterRecord *
4f20: 70 4e 65 78 74 20 3d 20 30 3b 0a 0a 20 20 20 20  pNext = 0;..    
4f30: 70 53 6f 72 74 65 72 2d 3e 6e 50 4d 41 2b 2b 3b  pSorter->nPMA++;
4f40: 0a 20 20 20 20 72 63 20 3d 20 76 64 62 65 53 6f  .    rc = vdbeSo
4f50: 72 74 65 72 57 72 69 74 65 56 61 72 69 6e 74 28  rterWriteVarint(
4f60: 70 53 6f 72 74 65 72 2d 3e 70 54 65 6d 70 31 2c  pSorter->pTemp1,
4f70: 20 70 53 6f 72 74 65 72 2d 3e 6e 49 6e 4d 65 6d   pSorter->nInMem
4f80: 6f 72 79 2c 20 26 69 4f 66 66 29 3b 0a 20 20 20  ory, &iOff);.   
4f90: 20 66 6f 72 28 70 3d 70 53 6f 72 74 65 72 2d 3e   for(p=pSorter->
4fa0: 70 52 65 63 6f 72 64 3b 20 72 63 3d 3d 53 51 4c  pRecord; rc==SQL
4fb0: 49 54 45 5f 4f 4b 20 26 26 20 70 3b 20 70 3d 70  ITE_OK && p; p=p
4fc0: 4e 65 78 74 29 7b 0a 20 20 20 20 20 20 70 4e 65  Next){.      pNe
4fd0: 78 74 20 3d 20 70 2d 3e 70 4e 65 78 74 3b 0a 20  xt = p->pNext;. 
4fe0: 20 20 20 20 20 72 63 20 3d 20 76 64 62 65 53 6f       rc = vdbeSo
4ff0: 72 74 65 72 57 72 69 74 65 56 61 72 69 6e 74 28  rterWriteVarint(
5000: 70 53 6f 72 74 65 72 2d 3e 70 54 65 6d 70 31 2c  pSorter->pTemp1,
5010: 20 70 2d 3e 6e 56 61 6c 2c 20 26 69 4f 66 66 29   p->nVal, &iOff)
5020: 3b 0a 0a 20 20 20 20 20 20 69 66 28 20 72 63 3d  ;..      if( rc=
5030: 3d 53 51 4c 49 54 45 5f 4f 4b 20 29 7b 0a 20 20  =SQLITE_OK ){.  
5040: 20 20 20 20 20 20 72 63 20 3d 20 73 71 6c 69 74        rc = sqlit
5050: 65 33 4f 73 57 72 69 74 65 28 70 53 6f 72 74 65  e3OsWrite(pSorte
5060: 72 2d 3e 70 54 65 6d 70 31 2c 20 70 2d 3e 70 56  r->pTemp1, p->pV
5070: 61 6c 2c 20 70 2d 3e 6e 56 61 6c 2c 20 69 4f 66  al, p->nVal, iOf
5080: 66 29 3b 0a 20 20 20 20 20 20 20 20 69 4f 66 66  f);.        iOff
5090: 20 2b 3d 20 70 2d 3e 6e 56 61 6c 3b 0a 20 20 20   += p->nVal;.   
50a0: 20 20 20 7d 0a 0a 20 20 20 20 20 20 73 71 6c 69     }..      sqli
50b0: 74 65 33 44 62 46 72 65 65 28 64 62 2c 20 70 29  te3DbFree(db, p)
50c0: 3b 0a 20 20 20 20 7d 0a 0a 20 20 20 20 2f 2a 20  ;.    }..    /* 
50d0: 54 68 69 73 20 61 73 73 65 72 74 20 76 65 72 69  This assert veri
50e0: 66 69 65 73 20 74 68 61 74 20 75 6e 6c 65 73 73  fies that unless
50f0: 20 61 6e 20 65 72 72 6f 72 20 68 61 73 20 6f 63   an error has oc
5100: 63 75 72 72 65 64 2c 20 74 68 65 20 73 69 7a 65  curred, the size
5110: 20 6f 66 20 0a 20 20 20 20 2a 2a 20 74 68 65 20   of .    ** the 
5120: 50 4d 41 20 6f 6e 20 64 69 73 6b 20 69 73 20 74  PMA on disk is t
5130: 68 65 20 73 61 6d 65 20 61 73 20 74 68 65 20 65  he same as the e
5140: 78 70 65 63 74 65 64 20 73 69 7a 65 20 73 74 6f  xpected size sto
5150: 72 65 64 20 69 6e 0a 20 20 20 20 2a 2a 20 70 53  red in.    ** pS
5160: 6f 72 74 65 72 2d 3e 6e 49 6e 4d 65 6d 6f 72 79  orter->nInMemory
5170: 2e 20 2a 2f 20 0a 20 20 20 20 61 73 73 65 72 74  . */ .    assert
5180: 28 20 72 63 21 3d 53 51 4c 49 54 45 5f 4f 4b 20  ( rc!=SQLITE_OK 
5190: 7c 7c 20 70 53 6f 72 74 65 72 2d 3e 6e 49 6e 4d  || pSorter->nInM
51a0: 65 6d 6f 72 79 3d 3d 28 0a 20 20 20 20 20 20 20  emory==(.       
51b0: 20 20 20 69 4f 66 66 2d 70 53 6f 72 74 65 72 2d     iOff-pSorter-
51c0: 3e 69 57 72 69 74 65 4f 66 66 2d 73 71 6c 69 74  >iWriteOff-sqlit
51d0: 65 33 56 61 72 69 6e 74 4c 65 6e 28 70 53 6f 72  e3VarintLen(pSor
51e0: 74 65 72 2d 3e 6e 49 6e 4d 65 6d 6f 72 79 29 0a  ter->nInMemory).
51f0: 20 20 20 20 29 29 3b 0a 0a 20 20 20 20 70 53 6f      ));..    pSo
5200: 72 74 65 72 2d 3e 69 57 72 69 74 65 4f 66 66 20  rter->iWriteOff 
5210: 3d 20 69 4f 66 66 3b 0a 20 20 20 20 70 53 6f 72  = iOff;.    pSor
5220: 74 65 72 2d 3e 70 52 65 63 6f 72 64 20 3d 20 70  ter->pRecord = p
5230: 3b 0a 20 20 7d 0a 0a 20 20 72 65 74 75 72 6e 20  ;.  }..  return 
5240: 72 63 3b 0a 7d 0a 0a 2f 2a 0a 2a 2a 20 41 64 64  rc;.}../*.** Add
5250: 20 61 20 72 65 63 6f 72 64 20 74 6f 20 74 68 65   a record to the
5260: 20 73 6f 72 74 65 72 2e 0a 2a 2f 0a 69 6e 74 20   sorter..*/.int 
5270: 73 71 6c 69 74 65 33 56 64 62 65 53 6f 72 74 65  sqlite3VdbeSorte
5280: 72 57 72 69 74 65 28 0a 20 20 73 71 6c 69 74 65  rWrite(.  sqlite
5290: 33 20 2a 64 62 2c 20 20 20 20 20 20 20 20 20 20  3 *db,          
52a0: 20 20 20 20 20 20 20 20 20 20 2f 2a 20 44 61 74            /* Dat
52b0: 61 62 61 73 65 20 68 61 6e 64 6c 65 20 2a 2f 0a  abase handle */.
52c0: 20 20 56 64 62 65 43 75 72 73 6f 72 20 2a 70 43    VdbeCursor *pC
52d0: 73 72 2c 20 20 20 20 20 20 20 20 20 20 20 20 20  sr,             
52e0: 20 20 2f 2a 20 53 6f 72 74 65 72 20 63 75 72 73    /* Sorter curs
52f0: 6f 72 20 2a 2f 0a 20 20 4d 65 6d 20 2a 70 56 61  or */.  Mem *pVa
5300: 6c 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20  l               
5310: 20 20 20 20 20 20 20 20 2f 2a 20 4d 65 6d 6f 72          /* Memor
5320: 79 20 63 65 6c 6c 20 63 6f 6e 74 61 69 6e 69 6e  y cell containin
5330: 67 20 72 65 63 6f 72 64 20 2a 2f 0a 29 7b 0a 20  g record */.){. 
5340: 20 56 64 62 65 53 6f 72 74 65 72 20 2a 70 53 6f   VdbeSorter *pSo
5350: 72 74 65 72 20 3d 20 70 43 73 72 2d 3e 70 53 6f  rter = pCsr->pSo
5360: 72 74 65 72 3b 0a 20 20 69 6e 74 20 72 63 20 3d  rter;.  int rc =
5370: 20 53 51 4c 49 54 45 5f 4f 4b 3b 20 20 20 20 20   SQLITE_OK;     
5380: 20 20 20 20 20 20 20 20 2f 2a 20 52 65 74 75 72          /* Retur
5390: 6e 20 43 6f 64 65 20 2a 2f 0a 20 20 53 6f 72 74  n Code */.  Sort
53a0: 65 72 52 65 63 6f 72 64 20 2a 70 4e 65 77 3b 20  erRecord *pNew; 
53b0: 20 20 20 20 20 20 20 20 20 20 20 20 2f 2a 20 4e              /* N
53c0: 65 77 20 6c 69 73 74 20 65 6c 65 6d 65 6e 74 20  ew list element 
53d0: 2a 2f 0a 0a 20 20 61 73 73 65 72 74 28 20 70 53  */..  assert( pS
53e0: 6f 72 74 65 72 20 29 3b 0a 20 20 70 53 6f 72 74  orter );.  pSort
53f0: 65 72 2d 3e 6e 49 6e 4d 65 6d 6f 72 79 20 2b 3d  er->nInMemory +=
5400: 20 73 71 6c 69 74 65 33 56 61 72 69 6e 74 4c 65   sqlite3VarintLe
5410: 6e 28 70 56 61 6c 2d 3e 6e 29 20 2b 20 70 56 61  n(pVal->n) + pVa
5420: 6c 2d 3e 6e 3b 0a 0a 20 20 70 4e 65 77 20 3d 20  l->n;..  pNew = 
5430: 28 53 6f 72 74 65 72 52 65 63 6f 72 64 20 2a 29  (SorterRecord *)
5440: 73 71 6c 69 74 65 33 44 62 4d 61 6c 6c 6f 63 52  sqlite3DbMallocR
5450: 61 77 28 64 62 2c 20 70 56 61 6c 2d 3e 6e 20 2b  aw(db, pVal->n +
5460: 20 73 69 7a 65 6f 66 28 53 6f 72 74 65 72 52 65   sizeof(SorterRe
5470: 63 6f 72 64 29 29 3b 0a 20 20 69 66 28 20 70 4e  cord));.  if( pN
5480: 65 77 3d 3d 30 20 29 7b 0a 20 20 20 20 72 63 20  ew==0 ){.    rc 
5490: 3d 20 53 51 4c 49 54 45 5f 4e 4f 4d 45 4d 3b 0a  = SQLITE_NOMEM;.
54a0: 20 20 7d 65 6c 73 65 7b 0a 20 20 20 20 70 4e 65    }else{.    pNe
54b0: 77 2d 3e 70 56 61 6c 20 3d 20 28 76 6f 69 64 20  w->pVal = (void 
54c0: 2a 29 26 70 4e 65 77 5b 31 5d 3b 0a 20 20 20 20  *)&pNew[1];.    
54d0: 6d 65 6d 63 70 79 28 70 4e 65 77 2d 3e 70 56 61  memcpy(pNew->pVa
54e0: 6c 2c 20 70 56 61 6c 2d 3e 7a 2c 20 70 56 61 6c  l, pVal->z, pVal
54f0: 2d 3e 6e 29 3b 0a 20 20 20 20 70 4e 65 77 2d 3e  ->n);.    pNew->
5500: 6e 56 61 6c 20 3d 20 70 56 61 6c 2d 3e 6e 3b 0a  nVal = pVal->n;.
5510: 20 20 20 20 70 4e 65 77 2d 3e 70 4e 65 78 74 20      pNew->pNext 
5520: 3d 20 70 53 6f 72 74 65 72 2d 3e 70 52 65 63 6f  = pSorter->pReco
5530: 72 64 3b 0a 20 20 20 20 70 53 6f 72 74 65 72 2d  rd;.    pSorter-
5540: 3e 70 52 65 63 6f 72 64 20 3d 20 70 4e 65 77 3b  >pRecord = pNew;
5550: 0a 20 20 7d 0a 0a 20 20 2f 2a 20 53 65 65 20 69  .  }..  /* See i
5560: 66 20 74 68 65 20 63 6f 6e 74 65 6e 74 73 20 6f  f the contents o
5570: 66 20 74 68 65 20 73 6f 72 74 65 72 20 73 68 6f  f the sorter sho
5580: 75 6c 64 20 6e 6f 77 20 62 65 20 77 72 69 74 74  uld now be writt
5590: 65 6e 20 6f 75 74 2e 20 54 68 65 79 0a 20 20 2a  en out. They.  *
55a0: 2a 20 61 72 65 20 77 72 69 74 74 65 6e 20 6f 75  * are written ou
55b0: 74 20 77 68 65 6e 20 65 69 74 68 65 72 20 6f 66  t when either of
55c0: 20 74 68 65 20 66 6f 6c 6c 6f 77 69 6e 67 20 61   the following a
55d0: 72 65 20 74 72 75 65 3a 0a 20 20 2a 2a 0a 20 20  re true:.  **.  
55e0: 2a 2a 20 20 20 2a 20 54 68 65 20 74 6f 74 61 6c  **   * The total
55f0: 20 6d 65 6d 6f 72 79 20 61 6c 6c 6f 63 61 74 65   memory allocate
5600: 64 20 66 6f 72 20 74 68 65 20 69 6e 2d 6d 65 6d  d for the in-mem
5610: 6f 72 79 20 6c 69 73 74 20 69 73 20 67 72 65 61  ory list is grea
5620: 74 65 72 20 0a 20 20 2a 2a 20 20 20 20 20 74 68  ter .  **     th
5630: 61 6e 20 28 70 61 67 65 2d 73 69 7a 65 20 2a 20  an (page-size * 
5640: 63 61 63 68 65 2d 73 69 7a 65 29 2c 20 6f 72 0a  cache-size), or.
5650: 20 20 2a 2a 0a 20 20 2a 2a 20 20 20 2a 20 54 68    **.  **   * Th
5660: 65 20 74 6f 74 61 6c 20 6d 65 6d 6f 72 79 20 61  e total memory a
5670: 6c 6c 6f 63 61 74 65 64 20 66 6f 72 20 74 68 65  llocated for the
5680: 20 69 6e 2d 6d 65 6d 6f 72 79 20 6c 69 73 74 20   in-memory list 
5690: 69 73 20 67 72 65 61 74 65 72 20 0a 20 20 2a 2a  is greater .  **
56a0: 20 20 20 20 20 74 68 61 6e 20 28 70 61 67 65 2d       than (page-
56b0: 73 69 7a 65 20 2a 20 31 30 29 20 61 6e 64 20 73  size * 10) and s
56c0: 71 6c 69 74 65 33 48 65 61 70 4e 65 61 72 6c 79  qlite3HeapNearly
56d0: 46 75 6c 6c 28 29 20 72 65 74 75 72 6e 73 20 74  Full() returns t
56e0: 72 75 65 2e 0a 20 20 2a 2f 0a 20 20 69 66 28 20  rue..  */.  if( 
56f0: 72 63 3d 3d 53 51 4c 49 54 45 5f 4f 4b 20 26 26  rc==SQLITE_OK &&
5700: 20 70 53 6f 72 74 65 72 2d 3e 6d 78 50 6d 61 53   pSorter->mxPmaS
5710: 69 7a 65 3e 30 20 26 26 20 28 0a 20 20 20 20 20  ize>0 && (.     
5720: 20 20 20 28 70 53 6f 72 74 65 72 2d 3e 6e 49 6e     (pSorter->nIn
5730: 4d 65 6d 6f 72 79 3e 70 53 6f 72 74 65 72 2d 3e  Memory>pSorter->
5740: 6d 78 50 6d 61 53 69 7a 65 29 0a 20 20 20 20 20  mxPmaSize).     
5750: 7c 7c 20 28 70 53 6f 72 74 65 72 2d 3e 6e 49 6e  || (pSorter->nIn
5760: 4d 65 6d 6f 72 79 3e 70 53 6f 72 74 65 72 2d 3e  Memory>pSorter->
5770: 6d 6e 50 6d 61 53 69 7a 65 20 26 26 20 73 71 6c  mnPmaSize && sql
5780: 69 74 65 33 48 65 61 70 4e 65 61 72 6c 79 46 75  ite3HeapNearlyFu
5790: 6c 6c 28 29 29 0a 20 20 29 29 7b 0a 20 20 20 20  ll()).  )){.    
57a0: 72 63 20 3d 20 76 64 62 65 53 6f 72 74 65 72 4c  rc = vdbeSorterL
57b0: 69 73 74 54 6f 50 4d 41 28 64 62 2c 20 70 43 73  istToPMA(db, pCs
57c0: 72 29 3b 0a 20 20 20 20 70 53 6f 72 74 65 72 2d  r);.    pSorter-
57d0: 3e 6e 49 6e 4d 65 6d 6f 72 79 20 3d 20 30 3b 0a  >nInMemory = 0;.
57e0: 20 20 7d 0a 0a 20 20 72 65 74 75 72 6e 20 72 63    }..  return rc
57f0: 3b 0a 7d 0a 0a 2f 2a 0a 2a 2a 20 48 65 6c 70 65  ;.}../*.** Helpe
5800: 72 20 66 75 6e 63 74 69 6f 6e 20 66 6f 72 20 73  r function for s
5810: 71 6c 69 74 65 33 56 64 62 65 53 6f 72 74 65 72  qlite3VdbeSorter
5820: 52 65 77 69 6e 64 28 29 2e 20 0a 2a 2f 0a 73 74  Rewind(). .*/.st
5830: 61 74 69 63 20 69 6e 74 20 76 64 62 65 53 6f 72  atic int vdbeSor
5840: 74 65 72 49 6e 69 74 4d 65 72 67 65 28 0a 20 20  terInitMerge(.  
5850: 73 71 6c 69 74 65 33 20 2a 64 62 2c 20 20 20 20  sqlite3 *db,    
5860: 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20                  
5870: 2f 2a 20 44 61 74 61 62 61 73 65 20 68 61 6e 64  /* Database hand
5880: 6c 65 20 2a 2f 0a 20 20 56 64 62 65 43 75 72 73  le */.  VdbeCurs
5890: 6f 72 20 2a 70 43 73 72 2c 20 20 20 20 20 20 20  or *pCsr,       
58a0: 20 20 20 20 20 20 20 20 2f 2a 20 43 75 72 73 6f          /* Curso
58b0: 72 20 68 61 6e 64 6c 65 20 66 6f 72 20 74 68 69  r handle for thi
58c0: 73 20 73 6f 72 74 65 72 20 2a 2f 0a 20 20 69 36  s sorter */.  i6
58d0: 34 20 2a 70 6e 42 79 74 65 20 20 20 20 20 20 20  4 *pnByte       
58e0: 20 20 20 20 20 20 20 20 20 20 20 20 20 20 2f 2a                /*
58f0: 20 53 75 6d 20 6f 66 20 62 79 74 65 73 20 69 6e   Sum of bytes in
5900: 20 61 6c 6c 20 6f 70 65 6e 65 64 20 50 4d 41 73   all opened PMAs
5910: 20 2a 2f 0a 29 7b 0a 20 20 56 64 62 65 53 6f 72   */.){.  VdbeSor
5920: 74 65 72 20 2a 70 53 6f 72 74 65 72 20 3d 20 70  ter *pSorter = p
5930: 43 73 72 2d 3e 70 53 6f 72 74 65 72 3b 0a 20 20  Csr->pSorter;.  
5940: 69 6e 74 20 72 63 20 3d 20 53 51 4c 49 54 45 5f  int rc = SQLITE_
5950: 4f 4b 3b 20 20 20 20 20 20 20 20 20 20 20 20 20  OK;             
5960: 2f 2a 20 52 65 74 75 72 6e 20 63 6f 64 65 20 2a  /* Return code *
5970: 2f 0a 20 20 69 6e 74 20 69 3b 20 20 20 20 20 20  /.  int i;      
5980: 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20                  
5990: 20 20 20 20 2f 2a 20 55 73 65 64 20 74 6f 20 69      /* Used to i
59a0: 74 65 72 61 74 6f 72 20 74 68 72 6f 75 67 68 20  terator through 
59b0: 61 49 74 65 72 5b 5d 20 2a 2f 0a 20 20 69 36 34  aIter[] */.  i64
59c0: 20 6e 42 79 74 65 20 3d 20 30 3b 20 20 20 20 20   nByte = 0;     
59d0: 20 20 20 20 20 20 20 20 20 20 20 20 20 2f 2a 20               /* 
59e0: 54 6f 74 61 6c 20 62 79 74 65 73 20 69 6e 20 61  Total bytes in a
59f0: 6c 6c 20 6f 70 65 6e 65 64 20 50 4d 41 73 20 2a  ll opened PMAs *
5a00: 2f 0a 0a 20 20 2f 2a 20 49 6e 69 74 69 61 6c 69  /..  /* Initiali
5a10: 7a 65 20 74 68 65 20 69 74 65 72 61 74 6f 72 73  ze the iterators
5a20: 2e 20 2a 2f 0a 20 20 66 6f 72 28 69 3d 30 3b 20  . */.  for(i=0; 
5a30: 69 3c 53 4f 52 54 45 52 5f 4d 41 58 5f 4d 45 52  i<SORTER_MAX_MER
5a40: 47 45 5f 43 4f 55 4e 54 3b 20 69 2b 2b 29 7b 0a  GE_COUNT; i++){.
5a50: 20 20 20 20 56 64 62 65 53 6f 72 74 65 72 49 74      VdbeSorterIt
5a60: 65 72 20 2a 70 49 74 65 72 20 3d 20 26 70 53 6f  er *pIter = &pSo
5a70: 72 74 65 72 2d 3e 61 49 74 65 72 5b 69 5d 3b 0a  rter->aIter[i];.
5a80: 20 20 20 20 72 63 20 3d 20 76 64 62 65 53 6f 72      rc = vdbeSor
5a90: 74 65 72 49 74 65 72 49 6e 69 74 28 64 62 2c 20  terIterInit(db, 
5aa0: 70 53 6f 72 74 65 72 2c 20 70 53 6f 72 74 65 72  pSorter, pSorter
5ab0: 2d 3e 69 52 65 61 64 4f 66 66 2c 20 70 49 74 65  ->iReadOff, pIte
5ac0: 72 2c 20 26 6e 42 79 74 65 29 3b 0a 20 20 20 20  r, &nByte);.    
5ad0: 70 53 6f 72 74 65 72 2d 3e 69 52 65 61 64 4f 66  pSorter->iReadOf
5ae0: 66 20 3d 20 70 49 74 65 72 2d 3e 69 45 6f 66 3b  f = pIter->iEof;
5af0: 0a 20 20 20 20 61 73 73 65 72 74 28 20 72 63 21  .    assert( rc!
5b00: 3d 53 51 4c 49 54 45 5f 4f 4b 20 7c 7c 20 70 53  =SQLITE_OK || pS
5b10: 6f 72 74 65 72 2d 3e 69 52 65 61 64 4f 66 66 3c  orter->iReadOff<
5b20: 3d 70 53 6f 72 74 65 72 2d 3e 69 57 72 69 74 65  =pSorter->iWrite
5b30: 4f 66 66 20 29 3b 0a 20 20 20 20 69 66 28 20 72  Off );.    if( r
5b40: 63 21 3d 53 51 4c 49 54 45 5f 4f 4b 20 7c 7c 20  c!=SQLITE_OK || 
5b50: 70 53 6f 72 74 65 72 2d 3e 69 52 65 61 64 4f 66  pSorter->iReadOf
5b60: 66 3e 3d 70 53 6f 72 74 65 72 2d 3e 69 57 72 69  f>=pSorter->iWri
5b70: 74 65 4f 66 66 20 29 20 62 72 65 61 6b 3b 0a 20  teOff ) break;. 
5b80: 20 7d 0a 0a 20 20 2f 2a 20 49 6e 69 74 69 61 6c   }..  /* Initial
5b90: 69 7a 65 20 74 68 65 20 61 54 72 65 65 5b 5d 20  ize the aTree[] 
5ba0: 61 72 72 61 79 2e 20 2a 2f 0a 20 20 66 6f 72 28  array. */.  for(
5bb0: 69 3d 70 53 6f 72 74 65 72 2d 3e 6e 54 72 65 65  i=pSorter->nTree
5bc0: 2d 31 3b 20 72 63 3d 3d 53 51 4c 49 54 45 5f 4f  -1; rc==SQLITE_O
5bd0: 4b 20 26 26 20 69 3e 30 3b 20 69 2d 2d 29 7b 0a  K && i>0; i--){.
5be0: 20 20 20 20 72 63 20 3d 20 76 64 62 65 53 6f 72      rc = vdbeSor
5bf0: 74 65 72 44 6f 43 6f 6d 70 61 72 65 28 70 43 73  terDoCompare(pCs
5c00: 72 2c 20 69 29 3b 0a 20 20 7d 0a 0a 20 20 2a 70  r, i);.  }..  *p
5c10: 6e 42 79 74 65 20 3d 20 6e 42 79 74 65 3b 0a 20  nByte = nByte;. 
5c20: 20 72 65 74 75 72 6e 20 72 63 3b 0a 7d 0a 0a 2f   return rc;.}../
5c30: 2a 0a 2a 2a 20 4f 6e 63 65 20 74 68 65 20 73 6f  *.** Once the so
5c40: 72 74 65 72 20 68 61 73 20 62 65 65 6e 20 70 6f  rter has been po
5c50: 70 75 6c 61 74 65 64 2c 20 74 68 69 73 20 66 75  pulated, this fu
5c60: 6e 63 74 69 6f 6e 20 69 73 20 63 61 6c 6c 65 64  nction is called
5c70: 20 74 6f 20 70 72 65 70 61 72 65 0a 2a 2a 20 66   to prepare.** f
5c80: 6f 72 20 69 74 65 72 61 74 69 6e 67 20 74 68 72  or iterating thr
5c90: 6f 75 67 68 20 69 74 73 20 63 6f 6e 74 65 6e 74  ough its content
5ca0: 73 20 69 6e 20 73 6f 72 74 65 64 20 6f 72 64 65  s in sorted orde
5cb0: 72 2e 0a 2a 2f 0a 69 6e 74 20 73 71 6c 69 74 65  r..*/.int sqlite
5cc0: 33 56 64 62 65 53 6f 72 74 65 72 52 65 77 69 6e  3VdbeSorterRewin
5cd0: 64 28 73 71 6c 69 74 65 33 20 2a 64 62 2c 20 56  d(sqlite3 *db, V
5ce0: 64 62 65 43 75 72 73 6f 72 20 2a 70 43 73 72 2c  dbeCursor *pCsr,
5cf0: 20 69 6e 74 20 2a 70 62 45 6f 66 29 7b 0a 20 20   int *pbEof){.  
5d00: 56 64 62 65 53 6f 72 74 65 72 20 2a 70 53 6f 72  VdbeSorter *pSor
5d10: 74 65 72 20 3d 20 70 43 73 72 2d 3e 70 53 6f 72  ter = pCsr->pSor
5d20: 74 65 72 3b 0a 20 20 69 6e 74 20 72 63 3b 20 20  ter;.  int rc;  
5d30: 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20                  
5d40: 20 20 20 20 20 20 20 2f 2a 20 52 65 74 75 72 6e         /* Return
5d50: 20 63 6f 64 65 20 2a 2f 0a 20 20 73 71 6c 69 74   code */.  sqlit
5d60: 65 33 5f 66 69 6c 65 20 2a 70 54 65 6d 70 32 20  e3_file *pTemp2 
5d70: 3d 20 30 3b 20 20 20 20 20 20 20 2f 2a 20 53 65  = 0;       /* Se
5d80: 63 6f 6e 64 20 74 65 6d 70 20 66 69 6c 65 20 74  cond temp file t
5d90: 6f 20 75 73 65 20 2a 2f 0a 20 20 69 36 34 20 69  o use */.  i64 i
5da0: 57 72 69 74 65 32 20 3d 20 30 3b 20 20 20 20 20  Write2 = 0;     
5db0: 20 20 20 20 20 20 20 20 20 20 20 2f 2a 20 57 72             /* Wr
5dc0: 69 74 65 20 6f 66 66 73 65 74 20 66 6f 72 20 70  ite offset for p
5dd0: 54 65 6d 70 32 20 2a 2f 0a 20 20 69 6e 74 20 6e  Temp2 */.  int n
5de0: 49 74 65 72 3b 20 20 20 20 20 20 20 20 20 20 20  Iter;           
5df0: 20 20 20 20 20 20 20 20 20 20 20 2f 2a 20 4e 75             /* Nu
5e00: 6d 62 65 72 20 6f 66 20 69 74 65 72 61 74 6f 72  mber of iterator
5e10: 73 20 75 73 65 64 20 2a 2f 0a 20 20 69 6e 74 20  s used */.  int 
5e20: 6e 42 79 74 65 3b 20 20 20 20 20 20 20 20 20 20  nByte;          
5e30: 20 20 20 20 20 20 20 20 20 20 20 20 2f 2a 20 42              /* B
5e40: 79 74 65 73 20 6f 66 20 73 70 61 63 65 20 72 65  ytes of space re
5e50: 71 75 69 72 65 64 20 66 6f 72 20 61 49 74 65 72  quired for aIter
5e60: 2f 61 54 72 65 65 20 2a 2f 0a 20 20 69 6e 74 20  /aTree */.  int 
5e70: 4e 20 3d 20 32 3b 20 20 20 20 20 20 20 20 20 20  N = 2;          
5e80: 20 20 20 20 20 20 20 20 20 20 20 20 2f 2a 20 50              /* P
5e90: 6f 77 65 72 20 6f 66 20 32 20 3e 3d 20 6e 49 74  ower of 2 >= nIt
5ea0: 65 72 20 2a 2f 0a 0a 20 20 61 73 73 65 72 74 28  er */..  assert(
5eb0: 20 70 53 6f 72 74 65 72 20 29 3b 0a 0a 20 20 2f   pSorter );..  /
5ec0: 2a 20 49 66 20 6e 6f 20 64 61 74 61 20 68 61 73  * If no data has
5ed0: 20 62 65 65 6e 20 77 72 69 74 74 65 6e 20 74 6f   been written to
5ee0: 20 64 69 73 6b 2c 20 74 68 65 6e 20 64 6f 20 6e   disk, then do n
5ef0: 6f 74 20 64 6f 20 73 6f 20 6e 6f 77 2e 20 49 6e  ot do so now. In
5f00: 73 74 65 61 64 2c 0a 20 20 2a 2a 20 73 6f 72 74  stead,.  ** sort
5f10: 20 74 68 65 20 56 64 62 65 53 6f 72 74 65 72 2e   the VdbeSorter.
5f20: 70 52 65 63 6f 72 64 20 6c 69 73 74 2e 20 54 68  pRecord list. Th
5f30: 65 20 76 64 62 65 20 6c 61 79 65 72 20 77 69 6c  e vdbe layer wil
5f40: 6c 20 72 65 61 64 20 64 61 74 61 20 64 69 72 65  l read data dire
5f50: 63 74 6c 79 0a 20 20 2a 2a 20 66 72 6f 6d 20 74  ctly.  ** from t
5f60: 68 65 20 69 6e 2d 6d 65 6d 6f 72 79 20 6c 69 73  he in-memory lis
5f70: 74 2e 20 20 2a 2f 0a 20 20 69 66 28 20 70 53 6f  t.  */.  if( pSo
5f80: 72 74 65 72 2d 3e 6e 50 4d 41 3d 3d 30 20 29 7b  rter->nPMA==0 ){
5f90: 0a 20 20 20 20 2a 70 62 45 6f 66 20 3d 20 21 70  .    *pbEof = !p
5fa0: 53 6f 72 74 65 72 2d 3e 70 52 65 63 6f 72 64 3b  Sorter->pRecord;
5fb0: 0a 20 20 20 20 61 73 73 65 72 74 28 20 70 53 6f  .    assert( pSo
5fc0: 72 74 65 72 2d 3e 61 54 72 65 65 3d 3d 30 20 29  rter->aTree==0 )
5fd0: 3b 0a 20 20 20 20 72 65 74 75 72 6e 20 76 64 62  ;.    return vdb
5fe0: 65 53 6f 72 74 65 72 53 6f 72 74 28 64 62 2c 20  eSorterSort(db, 
5ff0: 70 43 73 72 29 3b 0a 20 20 7d 0a 0a 20 20 2f 2a  pCsr);.  }..  /*
6000: 20 57 72 69 74 65 20 74 68 65 20 63 75 72 72 65   Write the curre
6010: 6e 74 20 62 2d 74 72 65 65 20 74 6f 20 61 20 50  nt b-tree to a P
6020: 4d 41 2e 20 43 6c 6f 73 65 20 74 68 65 20 62 2d  MA. Close the b-
6030: 74 72 65 65 20 63 75 72 73 6f 72 2e 20 2a 2f 0a  tree cursor. */.
6040: 20 20 72 63 20 3d 20 76 64 62 65 53 6f 72 74 65    rc = vdbeSorte
6050: 72 4c 69 73 74 54 6f 50 4d 41 28 64 62 2c 20 70  rListToPMA(db, p
6060: 43 73 72 29 3b 0a 20 20 69 66 28 20 72 63 21 3d  Csr);.  if( rc!=
6070: 53 51 4c 49 54 45 5f 4f 4b 20 29 20 72 65 74 75  SQLITE_OK ) retu
6080: 72 6e 20 72 63 3b 0a 0a 20 20 2f 2a 20 41 6c 6c  rn rc;..  /* All
6090: 6f 63 61 74 65 20 73 70 61 63 65 20 66 6f 72 20  ocate space for 
60a0: 61 49 74 65 72 5b 5d 20 61 6e 64 20 61 54 72 65  aIter[] and aTre
60b0: 65 5b 5d 2e 20 2a 2f 0a 20 20 6e 49 74 65 72 20  e[]. */.  nIter 
60c0: 3d 20 70 53 6f 72 74 65 72 2d 3e 6e 50 4d 41 3b  = pSorter->nPMA;
60d0: 0a 20 20 69 66 28 20 6e 49 74 65 72 3e 53 4f 52  .  if( nIter>SOR
60e0: 54 45 52 5f 4d 41 58 5f 4d 45 52 47 45 5f 43 4f  TER_MAX_MERGE_CO
60f0: 55 4e 54 20 29 20 6e 49 74 65 72 20 3d 20 53 4f  UNT ) nIter = SO
6100: 52 54 45 52 5f 4d 41 58 5f 4d 45 52 47 45 5f 43  RTER_MAX_MERGE_C
6110: 4f 55 4e 54 3b 0a 20 20 61 73 73 65 72 74 28 20  OUNT;.  assert( 
6120: 6e 49 74 65 72 3e 30 20 29 3b 0a 20 20 77 68 69  nIter>0 );.  whi
6130: 6c 65 28 20 4e 3c 6e 49 74 65 72 20 29 20 4e 20  le( N<nIter ) N 
6140: 2b 3d 20 4e 3b 0a 20 20 6e 42 79 74 65 20 3d 20  += N;.  nByte = 
6150: 4e 20 2a 20 28 73 69 7a 65 6f 66 28 69 6e 74 29  N * (sizeof(int)
6160: 20 2b 20 73 69 7a 65 6f 66 28 56 64 62 65 53 6f   + sizeof(VdbeSo
6170: 72 74 65 72 49 74 65 72 29 29 3b 0a 20 20 70 53  rterIter));.  pS
6180: 6f 72 74 65 72 2d 3e 61 49 74 65 72 20 3d 20 28  orter->aIter = (
6190: 56 64 62 65 53 6f 72 74 65 72 49 74 65 72 20 2a  VdbeSorterIter *
61a0: 29 73 71 6c 69 74 65 33 44 62 4d 61 6c 6c 6f 63  )sqlite3DbMalloc
61b0: 5a 65 72 6f 28 64 62 2c 20 6e 42 79 74 65 29 3b  Zero(db, nByte);
61c0: 0a 20 20 69 66 28 20 21 70 53 6f 72 74 65 72 2d  .  if( !pSorter-
61d0: 3e 61 49 74 65 72 20 29 20 72 65 74 75 72 6e 20  >aIter ) return 
61e0: 53 51 4c 49 54 45 5f 4e 4f 4d 45 4d 3b 0a 20 20  SQLITE_NOMEM;.  
61f0: 70 53 6f 72 74 65 72 2d 3e 61 54 72 65 65 20 3d  pSorter->aTree =
6200: 20 28 69 6e 74 20 2a 29 26 70 53 6f 72 74 65 72   (int *)&pSorter
6210: 2d 3e 61 49 74 65 72 5b 4e 5d 3b 0a 20 20 70 53  ->aIter[N];.  pS
6220: 6f 72 74 65 72 2d 3e 6e 54 72 65 65 20 3d 20 4e  orter->nTree = N
6230: 3b 0a 0a 20 20 64 6f 20 7b 0a 20 20 20 20 69 6e  ;..  do {.    in
6240: 74 20 69 4e 65 77 3b 20 20 20 20 20 20 20 20 20  t iNew;         
6250: 20 20 20 20 20 20 20 20 20 20 20 20 2f 2a 20 49              /* I
6260: 6e 64 65 78 20 6f 66 20 6e 65 77 2c 20 6d 65 72  ndex of new, mer
6270: 67 65 64 2c 20 50 4d 41 20 2a 2f 0a 0a 20 20 20  ged, PMA */..   
6280: 20 66 6f 72 28 69 4e 65 77 3d 30 3b 20 0a 20 20   for(iNew=0; .  
6290: 20 20 20 20 20 20 72 63 3d 3d 53 51 4c 49 54 45        rc==SQLITE
62a0: 5f 4f 4b 20 26 26 20 69 4e 65 77 2a 53 4f 52 54  _OK && iNew*SORT
62b0: 45 52 5f 4d 41 58 5f 4d 45 52 47 45 5f 43 4f 55  ER_MAX_MERGE_COU
62c0: 4e 54 3c 70 53 6f 72 74 65 72 2d 3e 6e 50 4d 41  NT<pSorter->nPMA
62d0: 3b 20 0a 20 20 20 20 20 20 20 20 69 4e 65 77 2b  ; .        iNew+
62e0: 2b 0a 20 20 20 20 29 7b 0a 20 20 20 20 20 20 69  +.    ){.      i
62f0: 36 34 20 6e 57 72 69 74 65 3b 20 20 20 20 20 20  64 nWrite;      
6300: 20 20 20 20 20 20 20 20 20 20 20 2f 2a 20 4e 75             /* Nu
6310: 6d 62 65 72 20 6f 66 20 62 79 74 65 73 20 69 6e  mber of bytes in
6320: 20 6e 65 77 20 50 4d 41 20 2a 2f 0a 0a 20 20 20   new PMA */..   
6330: 20 20 20 2f 2a 20 49 66 20 74 68 65 72 65 20 61     /* If there a
6340: 72 65 20 53 4f 52 54 45 52 5f 4d 41 58 5f 4d 45  re SORTER_MAX_ME
6350: 52 47 45 5f 43 4f 55 4e 54 20 6f 72 20 6c 65 73  RGE_COUNT or les
6360: 73 20 50 4d 41 73 20 69 6e 20 66 69 6c 65 20 70  s PMAs in file p
6370: 54 65 6d 70 31 2c 0a 20 20 20 20 20 20 2a 2a 20  Temp1,.      ** 
6380: 69 6e 69 74 69 61 6c 69 7a 65 20 61 6e 20 69 74  initialize an it
6390: 65 72 61 74 6f 72 20 66 6f 72 20 65 61 63 68 20  erator for each 
63a0: 6f 66 20 74 68 65 6d 20 61 6e 64 20 62 72 65 61  of them and brea
63b0: 6b 20 6f 75 74 20 6f 66 20 74 68 65 20 6c 6f 6f  k out of the loo
63c0: 70 2e 0a 20 20 20 20 20 20 2a 2a 20 54 68 65 73  p..      ** Thes
63d0: 65 20 69 74 65 72 61 74 6f 72 73 20 77 69 6c 6c  e iterators will
63e0: 20 62 65 20 69 6e 63 72 65 6d 65 6e 74 61 6c 6c   be incrementall
63f0: 79 20 6d 65 72 67 65 64 20 61 73 20 74 68 65 20  y merged as the 
6400: 56 44 42 45 20 6c 61 79 65 72 20 63 61 6c 6c 73  VDBE layer calls
6410: 0a 20 20 20 20 20 20 2a 2a 20 73 71 6c 69 74 65  .      ** sqlite
6420: 33 56 64 62 65 53 6f 72 74 65 72 4e 65 78 74 28  3VdbeSorterNext(
6430: 29 2e 0a 20 20 20 20 20 20 2a 2a 0a 20 20 20 20  )..      **.    
6440: 20 20 2a 2a 20 4f 74 68 65 72 77 69 73 65 2c 20    ** Otherwise, 
6450: 69 66 20 70 54 65 6d 70 31 20 63 6f 6e 74 61 69  if pTemp1 contai
6460: 6e 73 20 6d 6f 72 65 20 74 68 61 6e 20 53 4f 52  ns more than SOR
6470: 54 45 52 5f 4d 41 58 5f 4d 45 52 47 45 5f 43 4f  TER_MAX_MERGE_CO
6480: 55 4e 54 20 50 4d 41 73 2c 0a 20 20 20 20 20 20  UNT PMAs,.      
6490: 2a 2a 20 69 6e 69 74 69 61 6c 69 7a 65 20 69 6e  ** initialize in
64a0: 74 65 72 61 74 6f 72 73 20 66 6f 72 20 53 4f 52  terators for SOR
64b0: 54 45 52 5f 4d 41 58 5f 4d 45 52 47 45 5f 43 4f  TER_MAX_MERGE_CO
64c0: 55 4e 54 20 6f 66 20 74 68 65 6d 2e 20 54 68 65  UNT of them. The
64d0: 73 65 20 50 4d 41 73 0a 20 20 20 20 20 20 2a 2a  se PMAs.      **
64e0: 20 61 72 65 20 6d 65 72 67 65 64 20 69 6e 74 6f   are merged into
64f0: 20 61 20 73 69 6e 67 6c 65 20 50 4d 41 20 74 68   a single PMA th
6500: 61 74 20 69 73 20 77 72 69 74 74 65 6e 20 74 6f  at is written to
6510: 20 66 69 6c 65 20 70 54 65 6d 70 32 2e 0a 20 20   file pTemp2..  
6520: 20 20 20 20 2a 2f 0a 20 20 20 20 20 20 72 63 20      */.      rc 
6530: 3d 20 76 64 62 65 53 6f 72 74 65 72 49 6e 69 74  = vdbeSorterInit
6540: 4d 65 72 67 65 28 64 62 2c 20 70 43 73 72 2c 20  Merge(db, pCsr, 
6550: 26 6e 57 72 69 74 65 29 3b 0a 20 20 20 20 20 20  &nWrite);.      
6560: 61 73 73 65 72 74 28 20 72 63 21 3d 53 51 4c 49  assert( rc!=SQLI
6570: 54 45 5f 4f 4b 20 7c 7c 20 70 53 6f 72 74 65 72  TE_OK || pSorter
6580: 2d 3e 61 49 74 65 72 5b 20 70 53 6f 72 74 65 72  ->aIter[ pSorter
6590: 2d 3e 61 54 72 65 65 5b 31 5d 20 5d 2e 70 46 69  ->aTree[1] ].pFi
65a0: 6c 65 20 29 3b 0a 20 20 20 20 20 20 69 66 28 20  le );.      if( 
65b0: 72 63 21 3d 53 51 4c 49 54 45 5f 4f 4b 20 7c 7c  rc!=SQLITE_OK ||
65c0: 20 70 53 6f 72 74 65 72 2d 3e 6e 50 4d 41 3c 3d   pSorter->nPMA<=
65d0: 53 4f 52 54 45 52 5f 4d 41 58 5f 4d 45 52 47 45  SORTER_MAX_MERGE
65e0: 5f 43 4f 55 4e 54 20 29 7b 0a 20 20 20 20 20 20  _COUNT ){.      
65f0: 20 20 62 72 65 61 6b 3b 0a 20 20 20 20 20 20 7d    break;.      }
6600: 0a 0a 20 20 20 20 20 20 2f 2a 20 4f 70 65 6e 20  ..      /* Open 
6610: 74 68 65 20 73 65 63 6f 6e 64 20 74 65 6d 70 20  the second temp 
6620: 66 69 6c 65 2c 20 69 66 20 69 74 20 69 73 20 6e  file, if it is n
6630: 6f 74 20 61 6c 72 65 61 64 79 20 6f 70 65 6e 2e  ot already open.
6640: 20 2a 2f 0a 20 20 20 20 20 20 69 66 28 20 70 54   */.      if( pT
6650: 65 6d 70 32 3d 3d 30 20 29 7b 0a 20 20 20 20 20  emp2==0 ){.     
6660: 20 20 20 61 73 73 65 72 74 28 20 69 57 72 69 74     assert( iWrit
6670: 65 32 3d 3d 30 20 29 3b 0a 20 20 20 20 20 20 20  e2==0 );.       
6680: 20 72 63 20 3d 20 76 64 62 65 53 6f 72 74 65 72   rc = vdbeSorter
6690: 4f 70 65 6e 54 65 6d 70 46 69 6c 65 28 64 62 2c  OpenTempFile(db,
66a0: 20 26 70 54 65 6d 70 32 29 3b 0a 20 20 20 20 20   &pTemp2);.     
66b0: 20 7d 0a 0a 20 20 20 20 20 20 69 66 28 20 72 63   }..      if( rc
66c0: 3d 3d 53 51 4c 49 54 45 5f 4f 4b 20 29 7b 0a 20  ==SQLITE_OK ){. 
66d0: 20 20 20 20 20 20 20 72 63 20 3d 20 76 64 62 65         rc = vdbe
66e0: 53 6f 72 74 65 72 57 72 69 74 65 56 61 72 69 6e  SorterWriteVarin
66f0: 74 28 70 54 65 6d 70 32 2c 20 6e 57 72 69 74 65  t(pTemp2, nWrite
6700: 2c 20 26 69 57 72 69 74 65 32 29 3b 0a 20 20 20  , &iWrite2);.   
6710: 20 20 20 7d 0a 0a 20 20 20 20 20 20 69 66 28 20     }..      if( 
6720: 72 63 3d 3d 53 51 4c 49 54 45 5f 4f 4b 20 29 7b  rc==SQLITE_OK ){
6730: 0a 20 20 20 20 20 20 20 20 69 6e 74 20 62 45 6f  .        int bEo
6740: 66 20 3d 20 30 3b 0a 20 20 20 20 20 20 20 20 77  f = 0;.        w
6750: 68 69 6c 65 28 20 72 63 3d 3d 53 51 4c 49 54 45  hile( rc==SQLITE
6760: 5f 4f 4b 20 26 26 20 62 45 6f 66 3d 3d 30 20 29  _OK && bEof==0 )
6770: 7b 0a 20 20 20 20 20 20 20 20 20 20 69 6e 74 20  {.          int 
6780: 6e 54 6f 57 72 69 74 65 3b 0a 20 20 20 20 20 20  nToWrite;.      
6790: 20 20 20 20 56 64 62 65 53 6f 72 74 65 72 49 74      VdbeSorterIt
67a0: 65 72 20 2a 70 49 74 65 72 20 3d 20 26 70 53 6f  er *pIter = &pSo
67b0: 72 74 65 72 2d 3e 61 49 74 65 72 5b 20 70 53 6f  rter->aIter[ pSo
67c0: 72 74 65 72 2d 3e 61 54 72 65 65 5b 31 5d 20 5d  rter->aTree[1] ]
67d0: 3b 0a 20 20 20 20 20 20 20 20 20 20 61 73 73 65  ;.          asse
67e0: 72 74 28 20 70 49 74 65 72 2d 3e 70 46 69 6c 65  rt( pIter->pFile
67f0: 20 29 3b 0a 20 20 20 20 20 20 20 20 20 20 6e 54   );.          nT
6800: 6f 57 72 69 74 65 20 3d 20 70 49 74 65 72 2d 3e  oWrite = pIter->
6810: 6e 4b 65 79 20 2b 20 73 71 6c 69 74 65 33 56 61  nKey + sqlite3Va
6820: 72 69 6e 74 4c 65 6e 28 70 49 74 65 72 2d 3e 6e  rintLen(pIter->n
6830: 4b 65 79 29 3b 0a 20 20 20 20 20 20 20 20 20 20  Key);.          
6840: 72 63 20 3d 20 73 71 6c 69 74 65 33 4f 73 57 72  rc = sqlite3OsWr
6850: 69 74 65 28 70 54 65 6d 70 32 2c 20 70 49 74 65  ite(pTemp2, pIte
6860: 72 2d 3e 61 41 6c 6c 6f 63 2c 20 6e 54 6f 57 72  r->aAlloc, nToWr
6870: 69 74 65 2c 20 69 57 72 69 74 65 32 29 3b 0a 20  ite, iWrite2);. 
6880: 20 20 20 20 20 20 20 20 20 69 57 72 69 74 65 32           iWrite2
6890: 20 2b 3d 20 6e 54 6f 57 72 69 74 65 3b 0a 20 20   += nToWrite;.  
68a0: 20 20 20 20 20 20 20 20 69 66 28 20 72 63 3d 3d          if( rc==
68b0: 53 51 4c 49 54 45 5f 4f 4b 20 29 7b 0a 20 20 20  SQLITE_OK ){.   
68c0: 20 20 20 20 20 20 20 20 20 72 63 20 3d 20 73 71           rc = sq
68d0: 6c 69 74 65 33 56 64 62 65 53 6f 72 74 65 72 4e  lite3VdbeSorterN
68e0: 65 78 74 28 64 62 2c 20 70 43 73 72 2c 20 26 62  ext(db, pCsr, &b
68f0: 45 6f 66 29 3b 0a 20 20 20 20 20 20 20 20 20 20  Eof);.          
6900: 7d 0a 20 20 20 20 20 20 20 20 7d 0a 20 20 20 20  }.        }.    
6910: 20 20 7d 0a 20 20 20 20 7d 0a 0a 20 20 20 20 69    }.    }..    i
6920: 66 28 20 70 53 6f 72 74 65 72 2d 3e 6e 50 4d 41  f( pSorter->nPMA
6930: 3c 3d 53 4f 52 54 45 52 5f 4d 41 58 5f 4d 45 52  <=SORTER_MAX_MER
6940: 47 45 5f 43 4f 55 4e 54 20 29 7b 0a 20 20 20 20  GE_COUNT ){.    
6950: 20 20 62 72 65 61 6b 3b 0a 20 20 20 20 7d 65 6c    break;.    }el
6960: 73 65 7b 0a 20 20 20 20 20 20 73 71 6c 69 74 65  se{.      sqlite
6970: 33 5f 66 69 6c 65 20 2a 70 54 6d 70 20 3d 20 70  3_file *pTmp = p
6980: 53 6f 72 74 65 72 2d 3e 70 54 65 6d 70 31 3b 0a  Sorter->pTemp1;.
6990: 20 20 20 20 20 20 70 53 6f 72 74 65 72 2d 3e 6e        pSorter->n
69a0: 50 4d 41 20 3d 20 69 4e 65 77 3b 0a 20 20 20 20  PMA = iNew;.    
69b0: 20 20 70 53 6f 72 74 65 72 2d 3e 70 54 65 6d 70    pSorter->pTemp
69c0: 31 20 3d 20 70 54 65 6d 70 32 3b 0a 20 20 20 20  1 = pTemp2;.    
69d0: 20 20 70 54 65 6d 70 32 20 3d 20 70 54 6d 70 3b    pTemp2 = pTmp;
69e0: 0a 20 20 20 20 20 20 70 53 6f 72 74 65 72 2d 3e  .      pSorter->
69f0: 69 57 72 69 74 65 4f 66 66 20 3d 20 69 57 72 69  iWriteOff = iWri
6a00: 74 65 32 3b 0a 20 20 20 20 20 20 70 53 6f 72 74  te2;.      pSort
6a10: 65 72 2d 3e 69 52 65 61 64 4f 66 66 20 3d 20 30  er->iReadOff = 0
6a20: 3b 0a 20 20 20 20 20 20 69 57 72 69 74 65 32 20  ;.      iWrite2 
6a30: 3d 20 30 3b 0a 20 20 20 20 7d 0a 20 20 7d 77 68  = 0;.    }.  }wh
6a40: 69 6c 65 28 20 72 63 3d 3d 53 51 4c 49 54 45 5f  ile( rc==SQLITE_
6a50: 4f 4b 20 29 3b 0a 0a 20 20 69 66 28 20 70 54 65  OK );..  if( pTe
6a60: 6d 70 32 20 29 7b 0a 20 20 20 20 73 71 6c 69 74  mp2 ){.    sqlit
6a70: 65 33 4f 73 43 6c 6f 73 65 46 72 65 65 28 70 54  e3OsCloseFree(pT
6a80: 65 6d 70 32 29 3b 0a 20 20 7d 0a 20 20 2a 70 62  emp2);.  }.  *pb
6a90: 45 6f 66 20 3d 20 28 70 53 6f 72 74 65 72 2d 3e  Eof = (pSorter->
6aa0: 61 49 74 65 72 5b 70 53 6f 72 74 65 72 2d 3e 61  aIter[pSorter->a
6ab0: 54 72 65 65 5b 31 5d 5d 2e 70 46 69 6c 65 3d 3d  Tree[1]].pFile==
6ac0: 30 29 3b 0a 20 20 72 65 74 75 72 6e 20 72 63 3b  0);.  return rc;
6ad0: 0a 7d 0a 0a 2f 2a 0a 2a 2a 20 41 64 76 61 6e 63  .}../*.** Advanc
6ae0: 65 20 74 6f 20 74 68 65 20 6e 65 78 74 20 65 6c  e to the next el
6af0: 65 6d 65 6e 74 20 69 6e 20 74 68 65 20 73 6f 72  ement in the sor
6b00: 74 65 72 2e 0a 2a 2f 0a 69 6e 74 20 73 71 6c 69  ter..*/.int sqli
6b10: 74 65 33 56 64 62 65 53 6f 72 74 65 72 4e 65 78  te3VdbeSorterNex
6b20: 74 28 73 71 6c 69 74 65 33 20 2a 64 62 2c 20 56  t(sqlite3 *db, V
6b30: 64 62 65 43 75 72 73 6f 72 20 2a 70 43 73 72 2c  dbeCursor *pCsr,
6b40: 20 69 6e 74 20 2a 70 62 45 6f 66 29 7b 0a 20 20   int *pbEof){.  
6b50: 56 64 62 65 53 6f 72 74 65 72 20 2a 70 53 6f 72  VdbeSorter *pSor
6b60: 74 65 72 20 3d 20 70 43 73 72 2d 3e 70 53 6f 72  ter = pCsr->pSor
6b70: 74 65 72 3b 0a 20 20 69 6e 74 20 72 63 3b 20 20  ter;.  int rc;  
6b80: 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20                  
6b90: 20 20 20 20 20 20 20 2f 2a 20 52 65 74 75 72 6e         /* Return
6ba0: 20 63 6f 64 65 20 2a 2f 0a 0a 20 20 69 66 28 20   code */..  if( 
6bb0: 70 53 6f 72 74 65 72 2d 3e 61 54 72 65 65 20 29  pSorter->aTree )
6bc0: 7b 0a 20 20 20 20 69 6e 74 20 69 50 72 65 76 20  {.    int iPrev 
6bd0: 3d 20 70 53 6f 72 74 65 72 2d 3e 61 54 72 65 65  = pSorter->aTree
6be0: 5b 31 5d 3b 2f 2a 20 49 6e 64 65 78 20 6f 66 20  [1];/* Index of 
6bf0: 69 74 65 72 61 74 6f 72 20 74 6f 20 61 64 76 61  iterator to adva
6c00: 6e 63 65 20 2a 2f 0a 20 20 20 20 69 6e 74 20 69  nce */.    int i
6c10: 3b 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20  ;               
6c20: 20 20 20 20 20 20 20 20 20 2f 2a 20 49 6e 64 65           /* Inde
6c30: 78 20 6f 66 20 61 54 72 65 65 5b 5d 20 74 6f 20  x of aTree[] to 
6c40: 72 65 63 61 6c 63 75 6c 61 74 65 20 2a 2f 0a 0a  recalculate */..
6c50: 20 20 20 20 72 63 20 3d 20 76 64 62 65 53 6f 72      rc = vdbeSor
6c60: 74 65 72 49 74 65 72 4e 65 78 74 28 64 62 2c 20  terIterNext(db, 
6c70: 26 70 53 6f 72 74 65 72 2d 3e 61 49 74 65 72 5b  &pSorter->aIter[
6c80: 69 50 72 65 76 5d 29 3b 0a 20 20 20 20 66 6f 72  iPrev]);.    for
6c90: 28 69 3d 28 70 53 6f 72 74 65 72 2d 3e 6e 54 72  (i=(pSorter->nTr
6ca0: 65 65 2b 69 50 72 65 76 29 2f 32 3b 20 72 63 3d  ee+iPrev)/2; rc=
6cb0: 3d 53 51 4c 49 54 45 5f 4f 4b 20 26 26 20 69 3e  =SQLITE_OK && i>
6cc0: 30 3b 20 69 3d 69 2f 32 29 7b 0a 20 20 20 20 20  0; i=i/2){.     
6cd0: 20 72 63 20 3d 20 76 64 62 65 53 6f 72 74 65 72   rc = vdbeSorter
6ce0: 44 6f 43 6f 6d 70 61 72 65 28 70 43 73 72 2c 20  DoCompare(pCsr, 
6cf0: 69 29 3b 0a 20 20 20 20 7d 0a 0a 20 20 20 20 2a  i);.    }..    *
6d00: 70 62 45 6f 66 20 3d 20 28 70 53 6f 72 74 65 72  pbEof = (pSorter
6d10: 2d 3e 61 49 74 65 72 5b 70 53 6f 72 74 65 72 2d  ->aIter[pSorter-
6d20: 3e 61 54 72 65 65 5b 31 5d 5d 2e 70 46 69 6c 65  >aTree[1]].pFile
6d30: 3d 3d 30 29 3b 0a 20 20 7d 65 6c 73 65 7b 0a 20  ==0);.  }else{. 
6d40: 20 20 20 53 6f 72 74 65 72 52 65 63 6f 72 64 20     SorterRecord 
6d50: 2a 70 46 72 65 65 20 3d 20 70 53 6f 72 74 65 72  *pFree = pSorter
6d60: 2d 3e 70 52 65 63 6f 72 64 3b 0a 20 20 20 20 70  ->pRecord;.    p
6d70: 53 6f 72 74 65 72 2d 3e 70 52 65 63 6f 72 64 20  Sorter->pRecord 
6d80: 3d 20 70 46 72 65 65 2d 3e 70 4e 65 78 74 3b 0a  = pFree->pNext;.
6d90: 20 20 20 20 70 46 72 65 65 2d 3e 70 4e 65 78 74      pFree->pNext
6da0: 20 3d 20 30 3b 0a 20 20 20 20 76 64 62 65 53 6f   = 0;.    vdbeSo
6db0: 72 74 65 72 52 65 63 6f 72 64 46 72 65 65 28 64  rterRecordFree(d
6dc0: 62 2c 20 70 46 72 65 65 29 3b 0a 20 20 20 20 2a  b, pFree);.    *
6dd0: 70 62 45 6f 66 20 3d 20 21 70 53 6f 72 74 65 72  pbEof = !pSorter
6de0: 2d 3e 70 52 65 63 6f 72 64 3b 0a 20 20 20 20 72  ->pRecord;.    r
6df0: 63 20 3d 20 53 51 4c 49 54 45 5f 4f 4b 3b 0a 20  c = SQLITE_OK;. 
6e00: 20 7d 0a 20 20 72 65 74 75 72 6e 20 72 63 3b 0a   }.  return rc;.
6e10: 7d 0a 0a 2f 2a 0a 2a 2a 20 52 65 74 75 72 6e 20  }../*.** Return 
6e20: 61 20 70 6f 69 6e 74 65 72 20 74 6f 20 61 20 62  a pointer to a b
6e30: 75 66 66 65 72 20 6f 77 6e 65 64 20 62 79 20 74  uffer owned by t
6e40: 68 65 20 73 6f 72 74 65 72 20 74 68 61 74 20 63  he sorter that c
6e50: 6f 6e 74 61 69 6e 73 20 74 68 65 20 0a 2a 2a 20  ontains the .** 
6e60: 63 75 72 72 65 6e 74 20 6b 65 79 2e 0a 2a 2f 0a  current key..*/.
6e70: 73 74 61 74 69 63 20 76 6f 69 64 20 2a 76 64 62  static void *vdb
6e80: 65 53 6f 72 74 65 72 52 6f 77 6b 65 79 28 0a 20  eSorterRowkey(. 
6e90: 20 56 64 62 65 53 6f 72 74 65 72 20 2a 70 53 6f   VdbeSorter *pSo
6ea0: 72 74 65 72 2c 20 20 20 20 20 20 20 20 20 20 20  rter,           
6eb0: 20 2f 2a 20 53 6f 72 74 65 72 20 6f 62 6a 65 63   /* Sorter objec
6ec0: 74 20 2a 2f 0a 20 20 69 6e 74 20 2a 70 6e 4b 65  t */.  int *pnKe
6ed0: 79 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20  y               
6ee0: 20 20 20 20 20 20 20 2f 2a 20 4f 55 54 3a 20 53         /* OUT: S
6ef0: 69 7a 65 20 6f 66 20 63 75 72 72 65 6e 74 20 6b  ize of current k
6f00: 65 79 20 69 6e 20 62 79 74 65 73 20 2a 2f 0a 29  ey in bytes */.)
6f10: 7b 0a 20 20 76 6f 69 64 20 2a 70 4b 65 79 3b 0a  {.  void *pKey;.
6f20: 20 20 69 66 28 20 70 53 6f 72 74 65 72 2d 3e 61    if( pSorter->a
6f30: 54 72 65 65 20 29 7b 0a 20 20 20 20 56 64 62 65  Tree ){.    Vdbe
6f40: 53 6f 72 74 65 72 49 74 65 72 20 2a 70 49 74 65  SorterIter *pIte
6f50: 72 3b 0a 20 20 20 20 70 49 74 65 72 20 3d 20 26  r;.    pIter = &
6f60: 70 53 6f 72 74 65 72 2d 3e 61 49 74 65 72 5b 20  pSorter->aIter[ 
6f70: 70 53 6f 72 74 65 72 2d 3e 61 54 72 65 65 5b 31  pSorter->aTree[1
6f80: 5d 20 5d 3b 0a 20 20 20 20 2a 70 6e 4b 65 79 20  ] ];.    *pnKey 
6f90: 3d 20 70 49 74 65 72 2d 3e 6e 4b 65 79 3b 0a 20  = pIter->nKey;. 
6fa0: 20 20 20 70 4b 65 79 20 3d 20 70 49 74 65 72 2d     pKey = pIter-
6fb0: 3e 61 4b 65 79 3b 0a 20 20 7d 65 6c 73 65 7b 0a  >aKey;.  }else{.
6fc0: 20 20 20 20 2a 70 6e 4b 65 79 20 3d 20 70 53 6f      *pnKey = pSo
6fd0: 72 74 65 72 2d 3e 70 52 65 63 6f 72 64 2d 3e 6e  rter->pRecord->n
6fe0: 56 61 6c 3b 0a 20 20 20 20 70 4b 65 79 20 3d 20  Val;.    pKey = 
6ff0: 70 53 6f 72 74 65 72 2d 3e 70 52 65 63 6f 72 64  pSorter->pRecord
7000: 2d 3e 70 56 61 6c 3b 0a 20 20 7d 0a 20 20 72 65  ->pVal;.  }.  re
7010: 74 75 72 6e 20 70 4b 65 79 3b 0a 7d 0a 0a 2f 2a  turn pKey;.}../*
7020: 0a 2a 2a 20 43 6f 70 79 20 74 68 65 20 63 75 72  .** Copy the cur
7030: 72 65 6e 74 20 73 6f 72 74 65 72 20 6b 65 79 20  rent sorter key 
7040: 69 6e 74 6f 20 74 68 65 20 6d 65 6d 6f 72 79 20  into the memory 
7050: 63 65 6c 6c 20 70 4f 75 74 2e 0a 2a 2f 0a 69 6e  cell pOut..*/.in
7060: 74 20 73 71 6c 69 74 65 33 56 64 62 65 53 6f 72  t sqlite3VdbeSor
7070: 74 65 72 52 6f 77 6b 65 79 28 56 64 62 65 43 75  terRowkey(VdbeCu
7080: 72 73 6f 72 20 2a 70 43 73 72 2c 20 4d 65 6d 20  rsor *pCsr, Mem 
7090: 2a 70 4f 75 74 29 7b 0a 20 20 56 64 62 65 53 6f  *pOut){.  VdbeSo
70a0: 72 74 65 72 20 2a 70 53 6f 72 74 65 72 20 3d 20  rter *pSorter = 
70b0: 70 43 73 72 2d 3e 70 53 6f 72 74 65 72 3b 0a 20  pCsr->pSorter;. 
70c0: 20 76 6f 69 64 20 2a 70 4b 65 79 3b 20 69 6e 74   void *pKey; int
70d0: 20 6e 4b 65 79 3b 20 20 20 20 20 20 20 20 20 20   nKey;          
70e0: 20 2f 2a 20 53 6f 72 74 65 72 20 6b 65 79 20 74   /* Sorter key t
70f0: 6f 20 63 6f 70 79 20 69 6e 74 6f 20 70 4f 75 74  o copy into pOut
7100: 20 2a 2f 0a 0a 20 20 70 4b 65 79 20 3d 20 76 64   */..  pKey = vd
7110: 62 65 53 6f 72 74 65 72 52 6f 77 6b 65 79 28 70  beSorterRowkey(p
7120: 53 6f 72 74 65 72 2c 20 26 6e 4b 65 79 29 3b 0a  Sorter, &nKey);.
7130: 20 20 69 66 28 20 73 71 6c 69 74 65 33 56 64 62    if( sqlite3Vdb
7140: 65 4d 65 6d 47 72 6f 77 28 70 4f 75 74 2c 20 6e  eMemGrow(pOut, n
7150: 4b 65 79 2c 20 30 29 20 29 7b 0a 20 20 20 20 72  Key, 0) ){.    r
7160: 65 74 75 72 6e 20 53 51 4c 49 54 45 5f 4e 4f 4d  eturn SQLITE_NOM
7170: 45 4d 3b 0a 20 20 7d 0a 20 20 70 4f 75 74 2d 3e  EM;.  }.  pOut->
7180: 6e 20 3d 20 6e 4b 65 79 3b 0a 20 20 4d 65 6d 53  n = nKey;.  MemS
7190: 65 74 54 79 70 65 46 6c 61 67 28 70 4f 75 74 2c  etTypeFlag(pOut,
71a0: 20 4d 45 4d 5f 42 6c 6f 62 29 3b 0a 20 20 6d 65   MEM_Blob);.  me
71b0: 6d 63 70 79 28 70 4f 75 74 2d 3e 7a 2c 20 70 4b  mcpy(pOut->z, pK
71c0: 65 79 2c 20 6e 4b 65 79 29 3b 0a 0a 20 20 72 65  ey, nKey);..  re
71d0: 74 75 72 6e 20 53 51 4c 49 54 45 5f 4f 4b 3b 0a  turn SQLITE_OK;.
71e0: 7d 0a 0a 2f 2a 0a 2a 2a 20 43 6f 6d 70 61 72 65  }../*.** Compare
71f0: 20 74 68 65 20 6b 65 79 20 69 6e 20 6d 65 6d 6f   the key in memo
7200: 72 79 20 63 65 6c 6c 20 70 56 61 6c 20 77 69 74  ry cell pVal wit
7210: 68 20 74 68 65 20 6b 65 79 20 74 68 61 74 20 74  h the key that t
7220: 68 65 20 73 6f 72 74 65 72 20 63 75 72 73 6f 72  he sorter cursor
7230: 0a 2a 2a 20 70 61 73 73 65 64 20 61 73 20 74 68  .** passed as th
7240: 65 20 66 69 72 73 74 20 61 72 67 75 6d 65 6e 74  e first argument
7250: 20 63 75 72 72 65 6e 74 6c 79 20 70 6f 69 6e 74   currently point
7260: 73 20 74 6f 2e 20 46 6f 72 20 74 68 65 20 70 75  s to. For the pu
7270: 72 70 6f 73 65 73 20 6f 66 0a 2a 2a 20 74 68 65  rposes of.** the
7280: 20 63 6f 6d 70 61 72 69 73 6f 6e 2c 20 69 67 6e   comparison, ign
7290: 6f 72 65 20 74 68 65 20 72 6f 77 69 64 20 66 69  ore the rowid fi
72a0: 65 6c 64 20 61 74 20 74 68 65 20 65 6e 64 20 6f  eld at the end o
72b0: 66 20 65 61 63 68 20 72 65 63 6f 72 64 2e 0a 2a  f each record..*
72c0: 2a 0a 2a 2a 20 49 66 20 61 6e 20 65 72 72 6f 72  *.** If an error
72d0: 20 6f 63 63 75 72 73 2c 20 72 65 74 75 72 6e 20   occurs, return 
72e0: 61 6e 20 53 51 4c 69 74 65 20 65 72 72 6f 72 20  an SQLite error 
72f0: 63 6f 64 65 20 28 69 2e 65 2e 20 53 51 4c 49 54  code (i.e. SQLIT
7300: 45 5f 4e 4f 4d 45 4d 29 2e 0a 2a 2a 20 4f 74 68  E_NOMEM)..** Oth
7310: 65 72 77 69 73 65 2c 20 73 65 74 20 2a 70 52 65  erwise, set *pRe
7320: 73 20 74 6f 20 61 20 6e 65 67 61 74 69 76 65 2c  s to a negative,
7330: 20 7a 65 72 6f 20 6f 72 20 70 6f 73 69 74 69 76   zero or positiv
7340: 65 20 76 61 6c 75 65 20 69 66 20 74 68 65 0a 2a  e value if the.*
7350: 2a 20 6b 65 79 20 69 6e 20 70 56 61 6c 20 69 73  * key in pVal is
7360: 20 73 6d 61 6c 6c 65 72 20 74 68 61 6e 2c 20 65   smaller than, e
7370: 71 75 61 6c 20 74 6f 20 6f 72 20 6c 61 72 67 65  qual to or large
7380: 72 20 74 68 61 6e 20 74 68 65 20 63 75 72 72 65  r than the curre
7390: 6e 74 20 73 6f 72 74 65 72 0a 2a 2a 20 6b 65 79  nt sorter.** key
73a0: 2e 0a 2a 2f 0a 69 6e 74 20 73 71 6c 69 74 65 33  ..*/.int sqlite3
73b0: 56 64 62 65 53 6f 72 74 65 72 43 6f 6d 70 61 72  VdbeSorterCompar
73c0: 65 28 0a 20 20 56 64 62 65 43 75 72 73 6f 72 20  e(.  VdbeCursor 
73d0: 2a 70 43 73 72 2c 20 20 20 20 20 20 20 20 20 20  *pCsr,          
73e0: 20 20 20 20 20 2f 2a 20 53 6f 72 74 65 72 20 63       /* Sorter c
73f0: 75 72 73 6f 72 20 2a 2f 0a 20 20 4d 65 6d 20 2a  ursor */.  Mem *
7400: 70 56 61 6c 2c 20 20 20 20 20 20 20 20 20 20 20  pVal,           
7410: 20 20 20 20 20 20 20 20 20 20 20 2f 2a 20 56 61             /* Va
7420: 6c 75 65 20 74 6f 20 63 6f 6d 70 61 72 65 20 74  lue to compare t
7430: 6f 20 63 75 72 72 65 6e 74 20 73 6f 72 74 65 72  o current sorter
7440: 20 6b 65 79 20 2a 2f 0a 20 20 69 6e 74 20 2a 70   key */.  int *p
7450: 52 65 73 20 20 20 20 20 20 20 20 20 20 20 20 20  Res             
7460: 20 20 20 20 20 20 20 20 20 20 2f 2a 20 4f 55 54            /* OUT
7470: 3a 20 52 65 73 75 6c 74 20 6f 66 20 63 6f 6d 70  : Result of comp
7480: 61 72 69 73 6f 6e 20 2a 2f 0a 29 7b 0a 20 20 69  arison */.){.  i
7490: 6e 74 20 72 63 3b 0a 20 20 56 64 62 65 53 6f 72  nt rc;.  VdbeSor
74a0: 74 65 72 20 2a 70 53 6f 72 74 65 72 20 3d 20 70  ter *pSorter = p
74b0: 43 73 72 2d 3e 70 53 6f 72 74 65 72 3b 0a 20 20  Csr->pSorter;.  
74c0: 76 6f 69 64 20 2a 70 4b 65 79 3b 20 69 6e 74 20  void *pKey; int 
74d0: 6e 4b 65 79 3b 20 20 20 20 20 20 20 20 20 20 20  nKey;           
74e0: 2f 2a 20 53 6f 72 74 65 72 20 6b 65 79 20 74 6f  /* Sorter key to
74f0: 20 63 6f 6d 70 61 72 65 20 70 56 61 6c 20 77 69   compare pVal wi
7500: 74 68 20 2a 2f 0a 0a 20 20 70 4b 65 79 20 3d 20  th */..  pKey = 
7510: 76 64 62 65 53 6f 72 74 65 72 52 6f 77 6b 65 79  vdbeSorterRowkey
7520: 28 70 53 6f 72 74 65 72 2c 20 26 6e 4b 65 79 29  (pSorter, &nKey)
7530: 3b 0a 20 20 72 63 20 3d 20 76 64 62 65 53 6f 72  ;.  rc = vdbeSor
7540: 74 65 72 43 6f 6d 70 61 72 65 28 70 43 73 72 2c  terCompare(pCsr,
7550: 20 31 2c 20 70 56 61 6c 2d 3e 7a 2c 20 70 56 61   1, pVal->z, pVa
7560: 6c 2d 3e 6e 2c 20 70 4b 65 79 2c 20 6e 4b 65 79  l->n, pKey, nKey
7570: 2c 20 70 52 65 73 29 3b 0a 20 20 61 73 73 65 72  , pRes);.  asser
7580: 74 28 20 72 63 21 3d 53 51 4c 49 54 45 5f 4f 4b  t( rc!=SQLITE_OK
7590: 20 7c 7c 20 70 56 61 6c 2d 3e 64 62 2d 3e 6d 61   || pVal->db->ma
75a0: 6c 6c 6f 63 46 61 69 6c 65 64 20 7c 7c 20 28 2a  llocFailed || (*
75b0: 70 52 65 73 29 3c 3d 30 20 29 3b 0a 20 20 72 65  pRes)<=0 );.  re
75c0: 74 75 72 6e 20 72 63 3b 0a 7d 0a 0a 23 65 6e 64  turn rc;.}..#end
75d0: 69 66 20 2f 2a 20 23 69 66 6e 64 65 66 20 53 51  if /* #ifndef SQ
75e0: 4c 49 54 45 5f 4f 4d 49 54 5f 4d 45 52 47 45 5f  LITE_OMIT_MERGE_
75f0: 53 4f 52 54 20 2a 2f 0a                          SORT */.