Many hyperlinks are disabled.
Use anonymous login to enable hyperlinks.

Changes to src/vdbesort.c.

    87     87   */
    88     88   #include "sqliteInt.h"
    89     89   #include "vdbeInt.h"
    90     90   
    91     91   /*
    92     92   ** Private objects used by the sorter
    93     93   */
    94         -typedef struct VdbeSorterIter VdbeSorterIter;
    95         -typedef struct SortSubtask SortSubtask;
    96         -typedef struct SorterRecord SorterRecord;
    97         -typedef struct SorterMerger SorterMerger;
    98         -typedef struct FileWriter FileWriter;
           94  +typedef struct MergeEngine MergeEngine;     /* Merge PMAs together */
           95  +typedef struct PmaReader PmaReader;         /* Incrementally read one PMA */
           96  +typedef struct PmaWriter PmaWriter;         /* Incrementally write on PMA */
           97  +typedef struct SorterRecord SorterRecord;   /* A record being sorted */
           98  +typedef struct SortSubtask SortSubtask;     /* A sub-task in the sort process */
    99     99   
   100    100   
   101    101   /*
   102    102   ** Candidate values for SortSubtask.eWork
   103    103   */
   104    104   #define SORT_SUBTASK_SORT   1     /* Sort records on pList */
   105    105   #define SORT_SUBTASK_TO_PMA 2     /* Xfer pList to Packed-Memory-Array pTemp1 */
   106    106   #define SORT_SUBTASK_CONS   3     /* Consolidate multiple PMAs */
   107    107   
   108    108   /*
   109    109   ** Sorting is divided up into smaller subtasks.  Each subtask is controlled
   110         -** by an instance of this object.  Subtask might run in either the main thread
          110  +** by an instance of this object. A Subtask might run in either the main thread
   111    111   ** or in a background thread.
   112    112   **
   113         -** Exactly VdbeSorter.nThread instances of this object are allocated
          113  +** Exactly VdbeSorter.nTask instances of this object are allocated
   114    114   ** as part of each VdbeSorter object. Instances are never allocated any other
   115         -** way. VdbeSorter.nThread is set to the number of worker threads allowed
          115  +** way. VdbeSorter.nTask is set to the number of worker threads allowed
   116    116   ** (see SQLITE_CONFIG_WORKER_THREADS) plus one (the main thread).
   117    117   **
   118    118   ** When a background thread is launched to perform work, SortSubtask.bDone
   119         -** is set to 0 and the SortSubtask.pThread variable set to point to the
          119  +** is set to 0 and the SortSubtask.pTask variable set to point to the
   120    120   ** thread handle. SortSubtask.bDone is set to 1 (to indicate to the main
   121         -** thread that joining SortSubtask.pThread will not block) before the thread
   122         -** exits. SortSubtask.pThread and bDone are always cleared after the 
          121  +** thread that joining SortSubtask.pTask will not block) before the thread
          122  +** exits. SortSubtask.pTask and bDone are always cleared after the 
   123    123   ** background thread has been joined.
   124    124   **
   125         -** One object (specifically, VdbeSorter.aThread[VdbeSorter.nThread-1])
          125  +** One object (specifically, VdbeSorter.aTask[VdbeSorter.nTask-1])
   126    126   ** is reserved for the foreground thread.
   127    127   **
   128    128   ** The nature of the work performed is determined by SortSubtask.eWork,
   129    129   ** as follows:
   130    130   **
   131    131   **   SORT_SUBTASK_SORT:
   132    132   **     Sort the linked list of records at SortSubtask.pList.
................................................................................
   138    138   **
   139    139   **   SORT_SUBTASK_CONS:
   140    140   **     Merge existing PMAs until SortSubtask.nConsolidate or fewer
   141    141   **     remain in temp file SortSubtask.pTemp1.
   142    142   */
   143    143   struct SortSubtask {
   144    144     SQLiteThread *pThread;          /* Thread handle, or NULL */
   145         -  int bDone;                      /* Set to true by pThread when finished */
          145  +  int bDone;                      /* Set to true by pTask when finished */
   146    146   
   147    147     sqlite3_vfs *pVfs;              /* VFS used to open temporary files */
   148    148     KeyInfo *pKeyInfo;              /* How to compare records */
   149    149     UnpackedRecord *pUnpacked;      /* Space to unpack a record */
   150    150     int pgsz;                       /* Main database page size */
   151    151   
   152    152     u8 eWork;                       /* One of the SORT_SUBTASK_* constants */
   153    153     int nConsolidate;               /* For SORT_SUBTASK_CONS, max final PMAs */
   154         -  SorterRecord *pList;            /* List of records for pThread to sort */
          154  +  SorterRecord *pList;            /* List of records for pTask to sort */
   155    155     int nInMemory;                  /* Expected size of PMA based on pList */
   156    156     u8 *aListMemory;                /* Records memory (or NULL) */
   157    157   
   158    158     int nPMA;                       /* Number of PMAs currently in pTemp1 */
   159    159     i64 iTemp1Off;                  /* Offset to write to in pTemp1 */
   160    160     sqlite3_file *pTemp1;           /* File to write PMAs to, or NULL */
   161    161   };
   162    162   
   163    163   
   164    164   /*
   165         -** NOTES ON DATA STRUCTURE USED FOR N-WAY MERGES:
          165  +** The MergeEngine object is used to combine two or more smaller PMAs into
          166  +** one big PMA using a merge operation.  Separate PMAs all need to be
          167  +** combined into one big PMA in order to be able to step through the sorted
          168  +** records in order.
   166    169   **
   167         -** As keys are added to the sorter, they are written to disk in a series
   168         -** of sorted packed-memory-arrays (PMAs). The size of each PMA is roughly
   169         -** the same as the cache-size allowed for temporary databases. In order
   170         -** to allow the caller to extract keys from the sorter in sorted order,
   171         -** all PMAs currently stored on disk must be merged together. This comment
   172         -** describes the data structure used to do so. The structure supports 
   173         -** merging any number of arrays in a single pass with no redundant comparison 
   174         -** operations.
   175         -**
   176         -** The aIter[] array contains an iterator for each of the PMAs being merged.
   177         -** An aIter[] iterator either points to a valid key or else is at EOF. For 
   178         -** the purposes of the paragraphs below, we assume that the array is actually 
   179         -** N elements in size, where N is the smallest power of 2 greater to or equal 
   180         -** to the number of iterators being merged. The extra aIter[] elements are 
   181         -** treated as if they are empty (always at EOF).
          170  +** The aIter[] array contains a PmaReader object for each of the PMAs being
          171  +** merged.  An aIter[] object either points to a valid key or else is at EOF.
          172  +** For the purposes of the paragraphs below, we assume that the array is
          173  +** actually N elements in size, where N is the smallest power of 2 greater
          174  +** to or equal to the number of PMAs being merged. The extra aIter[] elements
          175  +** are treated as if they are empty (always at EOF).
   182    176   **
   183    177   ** The aTree[] array is also N elements in size. The value of N is stored in
   184         -** the VdbeSorter.nTree variable.
          178  +** the MergeEngine.nTree variable.
   185    179   **
   186    180   ** The final (N/2) elements of aTree[] contain the results of comparing
   187         -** pairs of iterator keys together. Element i contains the result of 
          181  +** pairs of PMA keys together. Element i contains the result of 
   188    182   ** comparing aIter[2*i-N] and aIter[2*i-N+1]. Whichever key is smaller, the
   189    183   ** aTree element is set to the index of it. 
   190    184   **
   191    185   ** For the purposes of this comparison, EOF is considered greater than any
   192    186   ** other key value. If the keys are equal (only possible with two EOF
   193    187   ** values), it doesn't matter which index is stored.
   194    188   **
................................................................................
   226    220   **
   227    221   **     aTree[] = { X, 0   0, 6    0, 3, 5, 6 }
   228    222   **
   229    223   ** In other words, each time we advance to the next sorter element, log2(N)
   230    224   ** key comparison operations are required, where N is the number of segments
   231    225   ** being merged (rounded up to the next power of 2).
   232    226   */
   233         -struct SorterMerger {
   234         -  int nTree;                      /* Used size of aTree/aIter (power of 2) */
   235         -  int *aTree;                     /* Current state of incremental merge */
   236         -  VdbeSorterIter *aIter;          /* Array of iterators to merge data from */
          227  +struct MergeEngine {
          228  +  int nTree;                 /* Used size of aTree/aIter (power of 2) */
          229  +  int *aTree;                /* Current state of incremental merge */
          230  +  PmaReader *aIter;          /* Array of iterators to merge data from */
   237    231   };
   238    232   
   239    233   /*
   240    234   ** Main sorter structure. A single instance of this is allocated for each 
   241    235   ** sorter cursor created by the VDBE.
   242    236   */
   243    237   struct VdbeSorter {
   244    238     int nInMemory;                  /* Current size of pRecord list as PMA */
   245    239     int mnPmaSize;                  /* Minimum PMA size, in bytes */
   246    240     int mxPmaSize;                  /* Maximum PMA size, in bytes.  0==no limit */
   247    241     int bUsePMA;                    /* True if one or more PMAs created */
   248    242     SorterRecord *pRecord;          /* Head of in-memory record list */
   249         -  SorterMerger *pMerger;          /* For final merge of PMAs (by caller) */ 
          243  +  MergeEngine *pMerger;           /* For final merge of PMAs (by caller) */ 
   250    244     u8 *aMemory;                    /* Block of memory to alloc records from */
   251    245     int iMemory;                    /* Offset of first free byte in aMemory */
   252    246     int nMemory;                    /* Size of aMemory allocation in bytes */
   253    247     int iPrev;                      /* Previous thread used to flush PMA */
   254         -  int nThread;                    /* Size of aThread[] array */
   255         -  SortSubtask aThread[1];
          248  +  int nTask;                      /* Size of aTask[] array */
          249  +  SortSubtask aTask[1];           /* One or more subtasks */
   256    250   };
   257    251   
   258    252   /*
   259         -** The following type is an iterator for a PMA. It caches the current key in 
   260         -** variables nKey/aKey. If the iterator is at EOF, pFile==0.
          253  +** An instance of the following object is used to read records out of a
          254  +** PMA, in sorted order.  The next key to be read is cached in nKey/aKey.
          255  +** pFile==0 at EOF.
   261    256   */
   262         -struct VdbeSorterIter {
          257  +struct PmaReader {
   263    258     i64 iReadOff;                   /* Current read offset */
   264    259     i64 iEof;                       /* 1 byte past EOF for this iterator */
   265    260     int nAlloc;                     /* Bytes of space at aAlloc */
   266    261     int nKey;                       /* Number of bytes in key */
   267    262     sqlite3_file *pFile;            /* File iterator is reading from */
   268    263     u8 *aAlloc;                     /* Allocated space */
   269    264     u8 *aKey;                       /* Pointer to current key */
   270    265     u8 *aBuffer;                    /* Current read buffer */
   271    266     int nBuffer;                    /* Size of read buffer in bytes */
   272    267     u8 *aMap;                       /* Pointer to mapping of entire file */
   273    268   };
   274    269   
   275    270   /*
   276         -** An instance of this structure is used to organize the stream of records
   277         -** being written to files by the merge-sort code into aligned, page-sized
   278         -** blocks.  Doing all I/O in aligned page-sized blocks helps I/O to go
   279         -** faster on many operating systems.
          271  +** An instance of this object is used for writing a PMA.
          272  +**
          273  +** The PMA is written one record at a time.  Each record is of an arbitrary
          274  +** size.  But I/O is more efficient if it occurs in page-sized blocks where
          275  +** each block is aligned on a page boundary.  This object caches writes to
          276  +** the PMA so that aligned, page-size blocks are written.
   280    277   */
   281         -struct FileWriter {
          278  +struct PmaWriter {
   282    279     int eFWErr;                     /* Non-zero if in an error state */
   283    280     u8 *aBuffer;                    /* Pointer to write buffer */
   284    281     int nBuffer;                    /* Size of write buffer in bytes */
   285    282     int iBufStart;                  /* First byte of buffer to write */
   286    283     int iBufEnd;                    /* Last byte of buffer to write */
   287    284     i64 iWriteOff;                  /* Offset of start of buffer in file */
   288    285     sqlite3_file *pFile;            /* File to write to */
   289    286   };
   290    287   
   291    288   /*
   292         -** A structure to store a single record. All in-memory records are connected
   293         -** together into a linked list headed at VdbeSorter.pRecord.
          289  +** This object is the header on a single record while that record is being
          290  +** held in memory and prior to being written out as part of a PMA.
   294    291   **
   295    292   ** How the linked list is connected depends on how memory is being managed
   296    293   ** by this module. If using a separate allocation for each in-memory record
   297    294   ** (VdbeSorter.aMemory==0), then the list is always connected using the
   298    295   ** SorterRecord.u.pNext pointers.
   299    296   **
   300    297   ** Or, if using the single large allocation method (VdbeSorter.aMemory!=0),
................................................................................
   303    300   ** be sqlite3Realloc()ed while records are being accumulated. Once the VM
   304    301   ** has finished passing records to the sorter, or when the in-memory buffer
   305    302   ** is full, the list is sorted. As part of the sorting process, it is
   306    303   ** converted to use the SorterRecord.u.pNext pointers. See function
   307    304   ** vdbeSorterSort() for details.
   308    305   */
   309    306   struct SorterRecord {
   310         -  int nVal;
          307  +  int nVal;                       /* Size of the record in bytes */
   311    308     union {
   312    309       SorterRecord *pNext;          /* Pointer to next record in list */
   313    310       int iNext;                    /* Offset within aMemory of next record */
   314    311     } u;
          312  +  /* The data for the record immediately follows this header */
   315    313   };
   316    314   
   317    315   /* Return a pointer to the buffer containing the record data for SorterRecord
   318    316   ** object p. Should be used as if:
   319    317   **
   320    318   **   void *SRVAL(SorterRecord *p) { return (void*)&p[1]; }
   321    319   */
   322    320   #define SRVAL(p) ((void*)((SorterRecord*)(p) + 1))
   323    321   
   324    322   /* The minimum PMA size is set to this value multiplied by the database
   325    323   ** page size in bytes.  */
   326    324   #define SORTER_MIN_WORKING 10
   327    325   
   328         -/* Maximum number of segments to merge in a single pass. */
          326  +/* Maximum number of PMAs that a single MergeEngine can merge */
   329    327   #define SORTER_MAX_MERGE_COUNT 16
   330    328   
   331    329   /*
   332         -** Free all memory belonging to the VdbeSorterIter object passed as the second
          330  +** Free all memory belonging to the PmaReader object passed as the second
   333    331   ** argument. All structure fields are set to zero before returning.
   334    332   */
   335         -static void vdbeSorterIterZero(VdbeSorterIter *pIter){
          333  +static void vdbePmaReaderClear(PmaReader *pIter){
   336    334     sqlite3_free(pIter->aAlloc);
   337    335     sqlite3_free(pIter->aBuffer);
   338    336     if( pIter->aMap ) sqlite3OsUnfetch(pIter->pFile, 0, pIter->aMap);
   339         -  memset(pIter, 0, sizeof(VdbeSorterIter));
          337  +  memset(pIter, 0, sizeof(PmaReader));
   340    338   }
   341    339   
   342    340   /*
   343    341   ** Read nByte bytes of data from the stream of data iterated by object p.
   344    342   ** If successful, set *ppOut to point to a buffer containing the data
   345    343   ** and return SQLITE_OK. Otherwise, if an error occurs, return an SQLite
   346    344   ** error code.
   347    345   **
   348    346   ** The buffer indicated by *ppOut may only be considered valid until the
   349    347   ** next call to this function.
   350    348   */
   351         -static int vdbeSorterIterRead(
   352         -  VdbeSorterIter *p,              /* Iterator */
          349  +static int vdbePmaReadBlob(
          350  +  PmaReader *p,                   /* Iterator */
   353    351     int nByte,                      /* Bytes of data to read */
   354    352     u8 **ppOut                      /* OUT: Pointer to buffer containing data */
   355    353   ){
   356    354     int iBuf;                       /* Offset within buffer to read from */
   357    355     int nAvail;                     /* Bytes of data available in buffer */
   358    356   
   359    357     if( p->aMap ){
................................................................................
   415    413       memcpy(p->aAlloc, &p->aBuffer[iBuf], nAvail);
   416    414       p->iReadOff += nAvail;
   417    415       nRem = nByte - nAvail;
   418    416   
   419    417       /* The following loop copies up to p->nBuffer bytes per iteration into
   420    418       ** the p->aAlloc[] buffer.  */
   421    419       while( nRem>0 ){
   422         -      int rc;                     /* vdbeSorterIterRead() return code */
          420  +      int rc;                     /* vdbePmaReadBlob() return code */
   423    421         int nCopy;                  /* Number of bytes to copy */
   424    422         u8 *aNext;                  /* Pointer to buffer to copy data from */
   425    423   
   426    424         nCopy = nRem;
   427    425         if( nRem>p->nBuffer ) nCopy = p->nBuffer;
   428         -      rc = vdbeSorterIterRead(p, nCopy, &aNext);
          426  +      rc = vdbePmaReadBlob(p, nCopy, &aNext);
   429    427         if( rc!=SQLITE_OK ) return rc;
   430    428         assert( aNext!=p->aAlloc );
   431    429         memcpy(&p->aAlloc[nByte - nRem], aNext, nCopy);
   432    430         nRem -= nCopy;
   433    431       }
   434    432   
   435    433       *ppOut = p->aAlloc;
................................................................................
   438    436     return SQLITE_OK;
   439    437   }
   440    438   
   441    439   /*
   442    440   ** Read a varint from the stream of data accessed by p. Set *pnOut to
   443    441   ** the value read.
   444    442   */
   445         -static int vdbeSorterIterVarint(VdbeSorterIter *p, u64 *pnOut){
          443  +static int vdbePmaReadVarint(PmaReader *p, u64 *pnOut){
   446    444     int iBuf;
   447    445   
   448    446     if( p->aMap ){
   449    447       p->iReadOff += sqlite3GetVarint(&p->aMap[p->iReadOff], pnOut);
   450    448     }else{
   451    449       iBuf = p->iReadOff % p->nBuffer;
   452    450       if( iBuf && (p->nBuffer-iBuf)>=9 ){
   453    451         p->iReadOff += sqlite3GetVarint(&p->aBuffer[iBuf], pnOut);
   454    452       }else{
   455    453         u8 aVarint[16], *a;
   456    454         int i = 0, rc;
   457    455         do{
   458         -        rc = vdbeSorterIterRead(p, 1, &a);
          456  +        rc = vdbePmaReadBlob(p, 1, &a);
   459    457           if( rc ) return rc;
   460    458           aVarint[(i++)&0xf] = a[0];
   461    459         }while( (a[0]&0x80)!=0 );
   462    460         sqlite3GetVarint(aVarint, pnOut);
   463    461       }
   464    462     }
   465    463   
................................................................................
   467    465   }
   468    466   
   469    467   
   470    468   /*
   471    469   ** Advance iterator pIter to the next key in its PMA. Return SQLITE_OK if
   472    470   ** no error occurs, or an SQLite error code if one does.
   473    471   */
   474         -static int vdbeSorterIterNext(VdbeSorterIter *pIter){
          472  +static int vdbePmaReaderNext(PmaReader *pIter){
   475    473     int rc;                         /* Return Code */
   476    474     u64 nRec = 0;                   /* Size of record in bytes */
   477    475   
   478    476     if( pIter->iReadOff>=pIter->iEof ){
   479    477       /* This is an EOF condition */
   480         -    vdbeSorterIterZero(pIter);
          478  +    vdbePmaReaderClear(pIter);
   481    479       return SQLITE_OK;
   482    480     }
   483    481   
   484         -  rc = vdbeSorterIterVarint(pIter, &nRec);
          482  +  rc = vdbePmaReadVarint(pIter, &nRec);
   485    483     if( rc==SQLITE_OK ){
   486    484       pIter->nKey = (int)nRec;
   487         -    rc = vdbeSorterIterRead(pIter, (int)nRec, &pIter->aKey);
          485  +    rc = vdbePmaReadBlob(pIter, (int)nRec, &pIter->aKey);
   488    486     }
   489    487   
   490    488     return rc;
   491    489   }
   492    490   
   493    491   /*
   494    492   ** Initialize iterator pIter to scan through the PMA stored in file pFile
   495    493   ** starting at offset iStart and ending at offset iEof-1. This function 
   496    494   ** leaves the iterator pointing to the first key in the PMA (or EOF if the 
   497    495   ** PMA is empty).
   498    496   */
   499         -static int vdbeSorterIterInit(
   500         -  SortSubtask *pThread,           /* Thread context */
   501         -  i64 iStart,                     /* Start offset in pThread->pTemp1 */
   502         -  VdbeSorterIter *pIter,          /* Iterator to populate */
          497  +static int vdbePmaReaderInit(
          498  +  SortSubtask *pTask,             /* Thread context */
          499  +  i64 iStart,                     /* Start offset in pTask->pTemp1 */
          500  +  PmaReader *pIter,               /* Iterator to populate */
   503    501     i64 *pnByte                     /* IN/OUT: Increment this value by PMA size */
   504    502   ){
   505    503     int rc = SQLITE_OK;
   506         -  int nBuf = pThread->pgsz;
          504  +  int nBuf = pTask->pgsz;
   507    505     void *pMap = 0;                 /* Mapping of temp file */
   508    506   
   509         -  assert( pThread->iTemp1Off>iStart );
          507  +  assert( pTask->iTemp1Off>iStart );
   510    508     assert( pIter->aAlloc==0 );
   511    509     assert( pIter->aBuffer==0 );
   512         -  pIter->pFile = pThread->pTemp1;
          510  +  pIter->pFile = pTask->pTemp1;
   513    511     pIter->iReadOff = iStart;
   514    512     pIter->nAlloc = 128;
   515    513     pIter->aAlloc = (u8*)sqlite3Malloc(pIter->nAlloc);
   516    514     if( pIter->aAlloc ){
   517    515       /* Try to xFetch() a mapping of the entire temp file. If this is possible,
   518    516       ** the PMA will be read via the mapping. Otherwise, use xRead().  */
   519         -    rc = sqlite3OsFetch(pIter->pFile, 0, pThread->iTemp1Off, &pMap);
          517  +    rc = sqlite3OsFetch(pIter->pFile, 0, pTask->iTemp1Off, &pMap);
   520    518     }else{
   521    519       rc = SQLITE_NOMEM;
   522    520     }
   523    521   
   524    522     if( rc==SQLITE_OK ){
   525    523       if( pMap ){
   526    524         pIter->aMap = (u8*)pMap;
................................................................................
   529    527         pIter->aBuffer = (u8*)sqlite3Malloc(nBuf);
   530    528         if( !pIter->aBuffer ){
   531    529           rc = SQLITE_NOMEM;
   532    530         }else{
   533    531           int iBuf = iStart % nBuf;
   534    532           if( iBuf ){
   535    533             int nRead = nBuf - iBuf;
   536         -          if( (iStart + nRead) > pThread->iTemp1Off ){
   537         -            nRead = (int)(pThread->iTemp1Off - iStart);
          534  +          if( (iStart + nRead) > pTask->iTemp1Off ){
          535  +            nRead = (int)(pTask->iTemp1Off - iStart);
   538    536             }
   539    537             rc = sqlite3OsRead(
   540         -              pThread->pTemp1, &pIter->aBuffer[iBuf], nRead, iStart
          538  +              pTask->pTemp1, &pIter->aBuffer[iBuf], nRead, iStart
   541    539                 );
   542    540             assert( rc!=SQLITE_IOERR_SHORT_READ );
   543    541           }
   544    542         }
   545    543       }
   546    544     }
   547    545   
   548    546     if( rc==SQLITE_OK ){
   549    547       u64 nByte;                    /* Size of PMA in bytes */
   550         -    pIter->iEof = pThread->iTemp1Off;
   551         -    rc = vdbeSorterIterVarint(pIter, &nByte);
          548  +    pIter->iEof = pTask->iTemp1Off;
          549  +    rc = vdbePmaReadVarint(pIter, &nByte);
   552    550       pIter->iEof = pIter->iReadOff + nByte;
   553    551       *pnByte += nByte;
   554    552     }
   555    553   
   556    554     if( rc==SQLITE_OK ){
   557         -    rc = vdbeSorterIterNext(pIter);
          555  +    rc = vdbePmaReaderNext(pIter);
   558    556     }
   559    557     return rc;
   560    558   }
   561    559   
   562    560   
   563    561   /*
   564    562   ** Compare key1 (buffer pKey1, size nKey1 bytes) with key2 (buffer pKey2, 
   565         -** size nKey2 bytes). Use (pThread->pKeyInfo) for the collation sequences
          563  +** size nKey2 bytes). Use (pTask->pKeyInfo) for the collation sequences
   566    564   ** used by the comparison. Return the result of the comparison.
   567    565   **
   568         -** Before returning, object (pThread->pUnpacked) is populated with the
          566  +** Before returning, object (pTask->pUnpacked) is populated with the
   569    567   ** unpacked version of key2. Or, if pKey2 is passed a NULL pointer, then it 
   570         -** is assumed that the (pThread->pUnpacked) structure already contains the 
          568  +** is assumed that the (pTask->pUnpacked) structure already contains the 
   571    569   ** unpacked key to use as key2.
   572    570   **
   573         -** If an OOM error is encountered, (pThread->pUnpacked->error_rc) is set
          571  +** If an OOM error is encountered, (pTask->pUnpacked->error_rc) is set
   574    572   ** to SQLITE_NOMEM.
   575    573   */
   576    574   static int vdbeSorterCompare(
   577         -  SortSubtask *pThread,           /* Thread context (for pKeyInfo) */
          575  +  SortSubtask *pTask,             /* Subtask context (for pKeyInfo) */
   578    576     const void *pKey1, int nKey1,   /* Left side of comparison */
   579    577     const void *pKey2, int nKey2    /* Right side of comparison */
   580    578   ){
   581         -  UnpackedRecord *r2 = pThread->pUnpacked;
          579  +  UnpackedRecord *r2 = pTask->pUnpacked;
   582    580     if( pKey2 ){
   583         -    sqlite3VdbeRecordUnpack(pThread->pKeyInfo, nKey2, pKey2, r2);
          581  +    sqlite3VdbeRecordUnpack(pTask->pKeyInfo, nKey2, pKey2, r2);
   584    582     }
   585    583     return sqlite3VdbeRecordCompare(nKey1, pKey1, r2, 0);
   586    584   }
   587    585   
   588    586   /*
   589    587   ** This function is called to compare two iterator keys when merging 
   590    588   ** multiple b-tree segments. Parameter iOut is the index of the aTree[] 
   591    589   ** value to recalculate.
   592    590   */
   593    591   static int vdbeSorterDoCompare(
   594         -  SortSubtask *pThread, 
   595         -  SorterMerger *pMerger, 
          592  +  SortSubtask *pTask, 
          593  +  MergeEngine *pMerger, 
   596    594     int iOut
   597    595   ){
   598    596     int i1;
   599    597     int i2;
   600    598     int iRes;
   601         -  VdbeSorterIter *p1;
   602         -  VdbeSorterIter *p2;
          599  +  PmaReader *p1;
          600  +  PmaReader *p2;
   603    601   
   604    602     assert( iOut<pMerger->nTree && iOut>0 );
   605    603   
   606    604     if( iOut>=(pMerger->nTree/2) ){
   607    605       i1 = (iOut - pMerger->nTree/2) * 2;
   608    606       i2 = i1 + 1;
   609    607     }else{
................................................................................
   616    614   
   617    615     if( p1->pFile==0 ){
   618    616       iRes = i2;
   619    617     }else if( p2->pFile==0 ){
   620    618       iRes = i1;
   621    619     }else{
   622    620       int res;
   623         -    assert( pThread->pUnpacked!=0 );  /* allocated in vdbeSortSubtaskMain() */
          621  +    assert( pTask->pUnpacked!=0 );  /* allocated in vdbeSortSubtaskMain() */
   624    622       res = vdbeSorterCompare(
   625         -        pThread, p1->aKey, p1->nKey, p2->aKey, p2->nKey
          623  +        pTask, p1->aKey, p1->nKey, p2->aKey, p2->nKey
   626    624       );
   627    625       if( res<=0 ){
   628    626         iRes = i1;
   629    627       }else{
   630    628         iRes = i2;
   631    629       }
   632    630     }
................................................................................
   634    632     pMerger->aTree[iOut] = iRes;
   635    633     return SQLITE_OK;
   636    634   }
   637    635   
   638    636   /*
   639    637   ** Initialize the temporary index cursor just opened as a sorter cursor.
   640    638   */
   641         -int sqlite3VdbeSorterInit(sqlite3 *db, int nField, VdbeCursor *pCsr){
          639  +int sqlite3VdbeSorterInit(
          640  +  sqlite3 *db,                    /* Database connection (for malloc()) */
          641  +  int nField,                     /* Number of key fields in each record */
          642  +  VdbeCursor *pCsr                /* Cursor that holds the new sorter */
          643  +){
   642    644     int pgsz;                       /* Page size of main database */
   643         -  int i;                          /* Used to iterate through aThread[] */
          645  +  int i;                          /* Used to iterate through aTask[] */
   644    646     int mxCache;                    /* Cache size */
   645    647     VdbeSorter *pSorter;            /* The new sorter */
   646    648     KeyInfo *pKeyInfo;              /* Copy of pCsr->pKeyInfo with db==0 */
   647    649     int szKeyInfo;                  /* Size of pCsr->pKeyInfo in bytes */
   648    650     int sz;                         /* Size of pSorter in bytes */
   649    651     int rc = SQLITE_OK;
   650    652     int nWorker = (sqlite3GlobalConfig.bCoreMutex?sqlite3GlobalConfig.nWorker:0);
................................................................................
   660    662     }else{
   661    663       pKeyInfo = (KeyInfo*)((u8*)pSorter + sz);
   662    664       memcpy(pKeyInfo, pCsr->pKeyInfo, szKeyInfo);
   663    665       pKeyInfo->db = 0;
   664    666       if( nField && nWorker==0 ) pKeyInfo->nField = nField;
   665    667       pgsz = sqlite3BtreeGetPageSize(db->aDb[0].pBt);
   666    668   
   667         -    pSorter->nThread = nWorker + 1;
   668         -    for(i=0; i<pSorter->nThread; i++){
   669         -      SortSubtask *pThread = &pSorter->aThread[i];
   670         -      pThread->pKeyInfo = pKeyInfo;
   671         -      pThread->pVfs = db->pVfs;
   672         -      pThread->pgsz = pgsz;
          669  +    pSorter->nTask = nWorker + 1;
          670  +    for(i=0; i<pSorter->nTask; i++){
          671  +      SortSubtask *pTask = &pSorter->aTask[i];
          672  +      pTask->pKeyInfo = pKeyInfo;
          673  +      pTask->pVfs = db->pVfs;
          674  +      pTask->pgsz = pgsz;
   673    675       }
   674    676   
   675    677       if( !sqlite3TempInMemory(db) ){
   676    678         pSorter->mnPmaSize = SORTER_MIN_WORKING * pgsz;
   677    679         mxCache = db->aDb[0].pSchema->cache_size;
   678    680         if( mxCache<SORTER_MIN_WORKING ) mxCache = SORTER_MIN_WORKING;
   679    681         pSorter->mxPmaSize = mxCache * pgsz;
................................................................................
   702    704     for(p=pRecord; p; p=pNext){
   703    705       pNext = p->u.pNext;
   704    706       sqlite3DbFree(db, p);
   705    707     }
   706    708   }
   707    709   
   708    710   /*
   709         -** Free all resources owned by the object indicated by argument pThread. All 
   710         -** fields of *pThread are zeroed before returning.
          711  +** Free all resources owned by the object indicated by argument pTask. All 
          712  +** fields of *pTask are zeroed before returning.
   711    713   */
   712         -static void vdbeSortSubtaskCleanup(sqlite3 *db, SortSubtask *pThread){
   713         -  sqlite3DbFree(db, pThread->pUnpacked);
   714         -  pThread->pUnpacked = 0;
   715         -  if( pThread->aListMemory==0 ){
   716         -    vdbeSorterRecordFree(0, pThread->pList);
          714  +static void vdbeSortSubtaskCleanup(sqlite3 *db, SortSubtask *pTask){
          715  +  sqlite3DbFree(db, pTask->pUnpacked);
          716  +  pTask->pUnpacked = 0;
          717  +  if( pTask->aListMemory==0 ){
          718  +    vdbeSorterRecordFree(0, pTask->pList);
   717    719     }else{
   718         -    sqlite3_free(pThread->aListMemory);
   719         -    pThread->aListMemory = 0;
          720  +    sqlite3_free(pTask->aListMemory);
          721  +    pTask->aListMemory = 0;
   720    722     }
   721         -  pThread->pList = 0;
   722         -  if( pThread->pTemp1 ){
   723         -    sqlite3OsCloseFree(pThread->pTemp1);
   724         -    pThread->pTemp1 = 0;
          723  +  pTask->pList = 0;
          724  +  if( pTask->pTemp1 ){
          725  +    sqlite3OsCloseFree(pTask->pTemp1);
          726  +    pTask->pTemp1 = 0;
   725    727     }
   726    728   }
   727    729   
   728    730   /*
   729    731   ** Join all threads.  
   730    732   */
   731    733   #if SQLITE_MAX_WORKER_THREADS>0
   732    734   static int vdbeSorterJoinAll(VdbeSorter *pSorter, int rcin){
   733    735     int rc = rcin;
   734    736     int i;
   735         -  for(i=0; i<pSorter->nThread; i++){
   736         -    SortSubtask *pThread = &pSorter->aThread[i];
   737         -    if( pThread->pThread ){
          737  +  for(i=0; i<pSorter->nTask; i++){
          738  +    SortSubtask *pTask = &pSorter->aTask[i];
          739  +    if( pTask->pTask ){
   738    740         void *pRet;
   739         -      int rc2 = sqlite3ThreadJoin(pThread->pThread, &pRet);
   740         -      pThread->pThread = 0;
   741         -      pThread->bDone = 0;
          741  +      int rc2 = sqlite3ThreadJoin(pTask->pTask, &pRet);
          742  +      pTask->pTask = 0;
          743  +      pTask->bDone = 0;
   742    744         if( rc==SQLITE_OK ) rc = rc2;
   743    745         if( rc==SQLITE_OK ) rc = SQLITE_PTR_TO_INT(pRet);
   744    746       }
   745    747     }
   746    748     return rc;
   747    749   }
   748    750   #else
   749    751   # define vdbeSorterJoinAll(x,rcin) (rcin)
   750    752   #endif
   751    753   
   752    754   /*
   753         -** Allocate a new SorterMerger object with space for nIter iterators.
          755  +** Allocate a new MergeEngine object with space for nIter iterators.
   754    756   */
   755         -static SorterMerger *vdbeSorterMergerNew(int nIter){
          757  +static MergeEngine *vdbeMergeEngineNew(int nIter){
   756    758     int N = 2;                      /* Smallest power of two >= nIter */
   757    759     int nByte;                      /* Total bytes of space to allocate */
   758         -  SorterMerger *pNew;             /* Pointer to allocated object to return */
          760  +  MergeEngine *pNew;              /* Pointer to allocated object to return */
   759    761   
   760    762     assert( nIter<=SORTER_MAX_MERGE_COUNT );
   761    763     while( N<nIter ) N += N;
   762         -  nByte = sizeof(SorterMerger) + N * (sizeof(int) + sizeof(VdbeSorterIter));
          764  +  nByte = sizeof(MergeEngine) + N * (sizeof(int) + sizeof(PmaReader));
   763    765   
   764         -  pNew = (SorterMerger*)sqlite3MallocZero(nByte);
          766  +  pNew = (MergeEngine*)sqlite3MallocZero(nByte);
   765    767     if( pNew ){
   766    768       pNew->nTree = N;
   767         -    pNew->aIter = (VdbeSorterIter*)&pNew[1];
          769  +    pNew->aIter = (PmaReader*)&pNew[1];
   768    770       pNew->aTree = (int*)&pNew->aIter[N];
   769    771     }
   770    772     return pNew;
   771    773   }
   772    774   
   773    775   /*
   774         -** Free the SorterMerger object passed as the only argument.
          776  +** Free the MergeEngine object passed as the only argument.
   775    777   */
   776         -static void vdbeSorterMergerFree(SorterMerger *pMerger){
          778  +static void vdbeMergeEngineFree(MergeEngine *pMerger){
   777    779     int i;
   778    780     if( pMerger ){
   779    781       for(i=0; i<pMerger->nTree; i++){
   780         -      vdbeSorterIterZero(&pMerger->aIter[i]);
          782  +      vdbePmaReaderClear(&pMerger->aIter[i]);
   781    783       }
   782    784     }
   783    785     sqlite3_free(pMerger);
   784    786   }
   785    787   
   786    788   /*
   787    789   ** Reset a sorting cursor back to its original empty state.
   788    790   */
   789    791   void sqlite3VdbeSorterReset(sqlite3 *db, VdbeSorter *pSorter){
   790    792     int i;
   791         -  vdbeSorterJoinAll(pSorter, SQLITE_OK);
   792         -  vdbeSorterMergerFree(pSorter->pMerger);
          793  +  (void)vdbeSorterJoinAll(pSorter, SQLITE_OK);
          794  +  vdbeMergeEngineFree(pSorter->pMerger);
   793    795     pSorter->pMerger = 0;
   794         -  for(i=0; i<pSorter->nThread; i++){
   795         -    SortSubtask *pThread = &pSorter->aThread[i];
   796         -    vdbeSortSubtaskCleanup(db, pThread);
          796  +  for(i=0; i<pSorter->nTask; i++){
          797  +    SortSubtask *pTask = &pSorter->aTask[i];
          798  +    vdbeSortSubtaskCleanup(db, pTask);
   797    799     }
   798    800     if( pSorter->aMemory==0 ){
   799    801       vdbeSorterRecordFree(0, pSorter->pRecord);
   800    802     }
   801    803     pSorter->pRecord = 0;
   802    804     pSorter->nInMemory = 0;
   803    805     pSorter->bUsePMA = 0;
................................................................................
   807    809   /*
   808    810   ** Free any cursor components allocated by sqlite3VdbeSorterXXX routines.
   809    811   */
   810    812   void sqlite3VdbeSorterClose(sqlite3 *db, VdbeCursor *pCsr){
   811    813     VdbeSorter *pSorter = pCsr->pSorter;
   812    814     if( pSorter ){
   813    815       sqlite3VdbeSorterReset(db, pSorter);
   814         -    vdbeSorterMergerFree(pSorter->pMerger);
          816  +    vdbeMergeEngineFree(pSorter->pMerger);
   815    817       sqlite3_free(pSorter->aMemory);
   816    818       sqlite3DbFree(db, pSorter);
   817    819       pCsr->pSorter = 0;
   818    820     }
   819    821   }
   820    822   
   821    823   /*
................................................................................
   838    840   }
   839    841   
   840    842   /*
   841    843   ** Merge the two sorted lists p1 and p2 into a single list.
   842    844   ** Set *ppOut to the head of the new list.
   843    845   */
   844    846   static void vdbeSorterMerge(
   845         -  SortSubtask *pThread,          /* Calling thread context */
          847  +  SortSubtask *pTask,             /* Calling thread context */
   846    848     SorterRecord *p1,               /* First list to merge */
   847    849     SorterRecord *p2,               /* Second list to merge */
   848    850     SorterRecord **ppOut            /* OUT: Head of merged list */
   849    851   ){
   850    852     SorterRecord *pFinal = 0;
   851    853     SorterRecord **pp = &pFinal;
   852    854     void *pVal2 = p2 ? SRVAL(p2) : 0;
   853    855   
   854    856     while( p1 && p2 ){
   855    857       int res;
   856         -    res = vdbeSorterCompare(pThread, SRVAL(p1), p1->nVal, pVal2, p2->nVal);
          858  +    res = vdbeSorterCompare(pTask, SRVAL(p1), p1->nVal, pVal2, p2->nVal);
   857    859       if( res<=0 ){
   858    860         *pp = p1;
   859    861         pp = &p1->u.pNext;
   860    862         p1 = p1->u.pNext;
   861    863         pVal2 = 0;
   862    864       }else{
   863    865         *pp = p2;
................................................................................
   868    870       }
   869    871     }
   870    872     *pp = p1 ? p1 : p2;
   871    873     *ppOut = pFinal;
   872    874   }
   873    875   
   874    876   /*
   875         -** Sort the linked list of records headed at pThread->pList. Return 
          877  +** Sort the linked list of records headed at pTask->pList. Return 
   876    878   ** SQLITE_OK if successful, or an SQLite error code (i.e. SQLITE_NOMEM) if 
   877    879   ** an error occurs.
   878    880   */
   879         -static int vdbeSorterSort(SortSubtask *pThread){
          881  +static int vdbeSorterSort(SortSubtask *pTask){
   880    882     int i;
   881    883     SorterRecord **aSlot;
   882    884     SorterRecord *p;
   883    885   
   884    886     aSlot = (SorterRecord **)sqlite3MallocZero(64 * sizeof(SorterRecord *));
   885    887     if( !aSlot ){
   886    888       return SQLITE_NOMEM;
   887    889     }
   888    890   
   889         -  p = pThread->pList;
          891  +  p = pTask->pList;
   890    892     while( p ){
   891    893       SorterRecord *pNext;
   892         -    if( pThread->aListMemory ){
   893         -      if( (u8*)p==pThread->aListMemory ){
          894  +    if( pTask->aListMemory ){
          895  +      if( (u8*)p==pTask->aListMemory ){
   894    896           pNext = 0;
   895    897         }else{
   896         -        assert( p->u.iNext<sqlite3MallocSize(pThread->aListMemory) );
   897         -        pNext = (SorterRecord*)&pThread->aListMemory[p->u.iNext];
          898  +        assert( p->u.iNext<sqlite3MallocSize(pTask->aListMemory) );
          899  +        pNext = (SorterRecord*)&pTask->aListMemory[p->u.iNext];
   898    900         }
   899    901       }else{
   900    902         pNext = p->u.pNext;
   901    903       }
   902    904   
   903    905       p->u.pNext = 0;
   904    906       for(i=0; aSlot[i]; i++){
   905         -      vdbeSorterMerge(pThread, p, aSlot[i], &p);
          907  +      vdbeSorterMerge(pTask, p, aSlot[i], &p);
   906    908         aSlot[i] = 0;
   907    909       }
   908    910       aSlot[i] = p;
   909    911       p = pNext;
   910    912     }
   911    913   
   912    914     p = 0;
   913    915     for(i=0; i<64; i++){
   914         -    vdbeSorterMerge(pThread, p, aSlot[i], &p);
          916  +    vdbeSorterMerge(pTask, p, aSlot[i], &p);
   915    917     }
   916         -  pThread->pList = p;
          918  +  pTask->pList = p;
   917    919   
   918    920     sqlite3_free(aSlot);
   919    921     return SQLITE_OK;
   920    922   }
   921    923   
   922    924   /*
   923         -** Initialize a file-writer object.
          925  +** Initialize a PMA-writer object.
   924    926   */
   925         -static void fileWriterInit(
          927  +static void vdbePmaWriterInit(
   926    928     sqlite3_file *pFile,            /* File to write to */
   927         -  FileWriter *p,                  /* Object to populate */
          929  +  PmaWriter *p,                   /* Object to populate */
   928    930     int nBuf,                       /* Buffer size */
   929    931     i64 iStart                      /* Offset of pFile to begin writing at */
   930    932   ){
   931         -  memset(p, 0, sizeof(FileWriter));
          933  +  memset(p, 0, sizeof(PmaWriter));
   932    934     p->aBuffer = (u8*)sqlite3Malloc(nBuf);
   933    935     if( !p->aBuffer ){
   934    936       p->eFWErr = SQLITE_NOMEM;
   935    937     }else{
   936    938       p->iBufEnd = p->iBufStart = (iStart % nBuf);
   937    939       p->iWriteOff = iStart - p->iBufStart;
   938    940       p->nBuffer = nBuf;
   939    941       p->pFile = pFile;
   940    942     }
   941    943   }
   942    944   
   943    945   /*
   944         -** Write nData bytes of data to the file-write object. Return SQLITE_OK
          946  +** Write nData bytes of data to the PMA. Return SQLITE_OK
   945    947   ** if successful, or an SQLite error code if an error occurs.
   946    948   */
   947         -static void fileWriterWrite(FileWriter *p, u8 *pData, int nData){
          949  +static void vdbePmaWriteBlob(PmaWriter *p, u8 *pData, int nData){
   948    950     int nRem = nData;
   949    951     while( nRem>0 && p->eFWErr==0 ){
   950    952       int nCopy = nRem;
   951    953       if( nCopy>(p->nBuffer - p->iBufEnd) ){
   952    954         nCopy = p->nBuffer - p->iBufEnd;
   953    955       }
   954    956   
................................................................................
   965    967       assert( p->iBufEnd<p->nBuffer );
   966    968   
   967    969       nRem -= nCopy;
   968    970     }
   969    971   }
   970    972   
   971    973   /*
   972         -** Flush any buffered data to disk and clean up the file-writer object.
   973         -** The results of using the file-writer after this call are undefined.
          974  +** Flush any buffered data to disk and clean up the PMA-writer object.
          975  +** The results of using the PMA-writer after this call are undefined.
   974    976   ** Return SQLITE_OK if flushing the buffered data succeeds or is not 
   975    977   ** required. Otherwise, return an SQLite error code.
   976    978   **
   977    979   ** Before returning, set *piEof to the offset immediately following the
   978    980   ** last byte written to the file.
   979    981   */
   980         -static int fileWriterFinish(FileWriter *p, i64 *piEof){
          982  +static int vdbePmaWriterFinish(PmaWriter *p, i64 *piEof){
   981    983     int rc;
   982    984     if( p->eFWErr==0 && ALWAYS(p->aBuffer) && p->iBufEnd>p->iBufStart ){
   983    985       p->eFWErr = sqlite3OsWrite(p->pFile, 
   984    986           &p->aBuffer[p->iBufStart], p->iBufEnd - p->iBufStart, 
   985    987           p->iWriteOff + p->iBufStart
   986    988       );
   987    989     }
   988    990     *piEof = (p->iWriteOff + p->iBufEnd);
   989    991     sqlite3_free(p->aBuffer);
   990    992     rc = p->eFWErr;
   991         -  memset(p, 0, sizeof(FileWriter));
          993  +  memset(p, 0, sizeof(PmaWriter));
   992    994     return rc;
   993    995   }
   994    996   
   995    997   /*
   996         -** Write value iVal encoded as a varint to the file-write object. Return 
          998  +** Write value iVal encoded as a varint to the PMA. Return 
   997    999   ** SQLITE_OK if successful, or an SQLite error code if an error occurs.
   998   1000   */
   999         -static void fileWriterWriteVarint(FileWriter *p, u64 iVal){
         1001  +static void vdbePmaWriteVarint(PmaWriter *p, u64 iVal){
  1000   1002     int nByte; 
  1001   1003     u8 aByte[10];
  1002   1004     nByte = sqlite3PutVarint(aByte, iVal);
  1003         -  fileWriterWrite(p, aByte, nByte);
         1005  +  vdbePmaWriteBlob(p, aByte, nByte);
  1004   1006   }
  1005   1007   
  1006   1008   #if SQLITE_MAX_MMAP_SIZE>0
  1007   1009   /*
  1008   1010   ** The first argument is a file-handle open on a temporary file. The file
  1009   1011   ** is guaranteed to be nByte bytes or smaller in size. This function
  1010   1012   ** attempts to extend the file to nByte bytes in size and to ensure that
................................................................................
  1036   1038   **     * A varint. This varint contains the total number of bytes of content
  1037   1039   **       in the PMA (not including the varint itself).
  1038   1040   **
  1039   1041   **     * One or more records packed end-to-end in order of ascending keys. 
  1040   1042   **       Each record consists of a varint followed by a blob of data (the 
  1041   1043   **       key). The varint is the number of bytes in the blob of data.
  1042   1044   */
  1043         -static int vdbeSorterListToPMA(SortSubtask *pThread){
         1045  +static int vdbeSorterListToPMA(SortSubtask *pTask){
  1044   1046     int rc = SQLITE_OK;             /* Return code */
  1045         -  FileWriter writer;              /* Object used to write to the file */
         1047  +  PmaWriter writer;               /* Object used to write to the file */
  1046   1048   
  1047         -  memset(&writer, 0, sizeof(FileWriter));
  1048         -  assert( pThread->nInMemory>0 );
         1049  +  memset(&writer, 0, sizeof(PmaWriter));
         1050  +  assert( pTask->nInMemory>0 );
  1049   1051   
  1050   1052     /* If the first temporary PMA file has not been opened, open it now. */
  1051         -  if( pThread->pTemp1==0 ){
  1052         -    rc = vdbeSorterOpenTempFile(pThread->pVfs, &pThread->pTemp1);
  1053         -    assert( rc!=SQLITE_OK || pThread->pTemp1 );
  1054         -    assert( pThread->iTemp1Off==0 );
  1055         -    assert( pThread->nPMA==0 );
         1053  +  if( pTask->pTemp1==0 ){
         1054  +    rc = vdbeSorterOpenTempFile(pTask->pVfs, &pTask->pTemp1);
         1055  +    assert( rc!=SQLITE_OK || pTask->pTemp1 );
         1056  +    assert( pTask->iTemp1Off==0 );
         1057  +    assert( pTask->nPMA==0 );
  1056   1058     }
  1057   1059   
  1058   1060     /* Try to get the file to memory map */
  1059   1061     if( rc==SQLITE_OK ){
  1060   1062       rc = vdbeSorterExtendFile(
  1061         -        pThread->pTemp1, pThread->iTemp1Off + pThread->nInMemory + 9
         1063  +        pTask->pTemp1, pTask->iTemp1Off + pTask->nInMemory + 9
  1062   1064       );
  1063   1065     }
  1064   1066   
  1065   1067     if( rc==SQLITE_OK ){
  1066   1068       SorterRecord *p;
  1067   1069       SorterRecord *pNext = 0;
  1068   1070   
  1069         -    fileWriterInit(pThread->pTemp1, &writer, pThread->pgsz, pThread->iTemp1Off);
  1070         -    pThread->nPMA++;
  1071         -    fileWriterWriteVarint(&writer, pThread->nInMemory);
  1072         -    for(p=pThread->pList; p; p=pNext){
         1071  +    vdbePmaWriterInit(pTask->pTemp1, &writer, pTask->pgsz,
         1072  +                      pTask->iTemp1Off);
         1073  +    pTask->nPMA++;
         1074  +    vdbePmaWriteVarint(&writer, pTask->nInMemory);
         1075  +    for(p=pTask->pList; p; p=pNext){
  1073   1076         pNext = p->u.pNext;
  1074         -      fileWriterWriteVarint(&writer, p->nVal);
  1075         -      fileWriterWrite(&writer, SRVAL(p), p->nVal);
  1076         -      if( pThread->aListMemory==0 ) sqlite3_free(p);
         1077  +      vdbePmaWriteVarint(&writer, p->nVal);
         1078  +      vdbePmaWriteBlob(&writer, SRVAL(p), p->nVal);
         1079  +      if( pTask->aListMemory==0 ) sqlite3_free(p);
  1077   1080       }
  1078         -    pThread->pList = p;
  1079         -    rc = fileWriterFinish(&writer, &pThread->iTemp1Off);
         1081  +    pTask->pList = p;
         1082  +    rc = vdbePmaWriterFinish(&writer, &pTask->iTemp1Off);
  1080   1083     }
  1081   1084   
  1082         -  assert( pThread->pList==0 || rc!=SQLITE_OK );
         1085  +  assert( pTask->pList==0 || rc!=SQLITE_OK );
  1083   1086     return rc;
  1084   1087   }
  1085   1088   
  1086   1089   /*
  1087         -** Advance the SorterMerger iterator passed as the second argument to
         1090  +** Advance the MergeEngine iterator passed as the second argument to
  1088   1091   ** the next entry. Set *pbEof to true if this means the iterator has 
  1089   1092   ** reached EOF.
  1090   1093   **
  1091   1094   ** Return SQLITE_OK if successful or an error code if an error occurs.
  1092   1095   */
  1093   1096   static int vdbeSorterNext(
  1094         -  SortSubtask *pThread, 
  1095         -  SorterMerger *pMerger, 
         1097  +  SortSubtask *pTask, 
         1098  +  MergeEngine *pMerger, 
  1096   1099     int *pbEof
  1097   1100   ){
  1098   1101     int rc;
  1099   1102     int iPrev = pMerger->aTree[1];/* Index of iterator to advance */
  1100   1103   
  1101   1104     /* Advance the current iterator */
  1102         -  rc = vdbeSorterIterNext(&pMerger->aIter[iPrev]);
         1105  +  rc = vdbePmaReaderNext(&pMerger->aIter[iPrev]);
  1103   1106   
  1104   1107     /* Update contents of aTree[] */
  1105   1108     if( rc==SQLITE_OK ){
  1106   1109       int i;                      /* Index of aTree[] to recalculate */
  1107         -    VdbeSorterIter *pIter1;     /* First iterator to compare */
  1108         -    VdbeSorterIter *pIter2;     /* Second iterator to compare */
         1110  +    PmaReader *pIter1;     /* First iterator to compare */
         1111  +    PmaReader *pIter2;     /* Second iterator to compare */
  1109   1112       u8 *pKey2;                  /* To pIter2->aKey, or 0 if record cached */
  1110   1113   
  1111   1114       /* Find the first two iterators to compare. The one that was just
  1112   1115       ** advanced (iPrev) and the one next to it in the array.  */
  1113   1116       pIter1 = &pMerger->aIter[(iPrev & 0xFFFE)];
  1114   1117       pIter2 = &pMerger->aIter[(iPrev | 0x0001)];
  1115   1118       pKey2 = pIter2->aKey;
................................................................................
  1118   1121         /* Compare pIter1 and pIter2. Store the result in variable iRes. */
  1119   1122         int iRes;
  1120   1123         if( pIter1->pFile==0 ){
  1121   1124           iRes = +1;
  1122   1125         }else if( pIter2->pFile==0 ){
  1123   1126           iRes = -1;
  1124   1127         }else{
  1125         -        iRes = vdbeSorterCompare(pThread, 
         1128  +        iRes = vdbeSorterCompare(pTask, 
  1126   1129               pIter1->aKey, pIter1->nKey, pKey2, pIter2->nKey
  1127   1130           );
  1128   1131         }
  1129   1132   
  1130   1133         /* If pIter1 contained the smaller value, set aTree[i] to its index.
  1131   1134         ** Then set pIter2 to the next iterator to compare to pIter1. In this
  1132         -      ** case there is no cache of pIter2 in pThread->pUnpacked, so set
         1135  +      ** case there is no cache of pIter2 in pTask->pUnpacked, so set
  1133   1136         ** pKey2 to point to the record belonging to pIter2.
  1134   1137         **
  1135   1138         ** Alternatively, if pIter2 contains the smaller of the two values,
  1136   1139         ** set aTree[i] to its index and update pIter1. If vdbeSorterCompare()
  1137         -      ** was actually called above, then pThread->pUnpacked now contains
         1140  +      ** was actually called above, then pTask->pUnpacked now contains
  1138   1141         ** a value equivalent to pIter2. So set pKey2 to NULL to prevent
  1139   1142         ** vdbeSorterCompare() from decoding pIter2 again.
  1140   1143         **
  1141   1144         ** If the two values were equal, then the value from the oldest
  1142   1145         ** PMA should be considered smaller. The VdbeSorter.aIter[] array
  1143   1146         ** is sorted from oldest to newest, so pIter1 contains older values
  1144   1147         ** than pIter2 iff (pIter1<pIter2).  */
................................................................................
  1159   1162   }
  1160   1163   
  1161   1164   /*
  1162   1165   ** The main routine for sorter-thread operations.
  1163   1166   */
  1164   1167   static void *vdbeSortSubtaskMain(void *pCtx){
  1165   1168     int rc = SQLITE_OK;
  1166         -  SortSubtask *pThread = (SortSubtask*)pCtx;
         1169  +  SortSubtask *pTask = (SortSubtask*)pCtx;
  1167   1170   
  1168         -  assert( pThread->eWork==SORT_SUBTASK_SORT
  1169         -       || pThread->eWork==SORT_SUBTASK_TO_PMA
  1170         -       || pThread->eWork==SORT_SUBTASK_CONS
         1171  +  assert( pTask->eWork==SORT_SUBTASK_SORT
         1172  +       || pTask->eWork==SORT_SUBTASK_TO_PMA
         1173  +       || pTask->eWork==SORT_SUBTASK_CONS
  1171   1174     );
  1172         -  assert( pThread->bDone==0 );
         1175  +  assert( pTask->bDone==0 );
  1173   1176   
  1174         -  if( pThread->pUnpacked==0 ){
         1177  +  if( pTask->pUnpacked==0 ){
  1175   1178       char *pFree;
  1176         -    pThread->pUnpacked = sqlite3VdbeAllocUnpackedRecord(
  1177         -        pThread->pKeyInfo, 0, 0, &pFree
         1179  +    pTask->pUnpacked = sqlite3VdbeAllocUnpackedRecord(
         1180  +        pTask->pKeyInfo, 0, 0, &pFree
  1178   1181       );
  1179         -    assert( pThread->pUnpacked==(UnpackedRecord*)pFree );
         1182  +    assert( pTask->pUnpacked==(UnpackedRecord*)pFree );
  1180   1183       if( pFree==0 ){
  1181   1184         rc = SQLITE_NOMEM;
  1182   1185         goto thread_out;
  1183   1186       }
  1184         -    pThread->pUnpacked->nField = pThread->pKeyInfo->nField;
  1185         -    pThread->pUnpacked->errCode = 0;
         1187  +    pTask->pUnpacked->nField = pTask->pKeyInfo->nField;
         1188  +    pTask->pUnpacked->errCode = 0;
  1186   1189     }
  1187   1190   
  1188         -  if( pThread->eWork==SORT_SUBTASK_CONS ){
  1189         -    assert( pThread->pList==0 );
  1190         -    while( pThread->nPMA>pThread->nConsolidate && rc==SQLITE_OK ){
  1191         -      int nIter = MIN(pThread->nPMA, SORTER_MAX_MERGE_COUNT);
         1191  +  if( pTask->eWork==SORT_SUBTASK_CONS ){
         1192  +    assert( pTask->pList==0 );
         1193  +    while( pTask->nPMA>pTask->nConsolidate && rc==SQLITE_OK ){
         1194  +      int nIter = MIN(pTask->nPMA, SORTER_MAX_MERGE_COUNT);
  1192   1195         sqlite3_file *pTemp2 = 0;     /* Second temp file to use */
  1193         -      SorterMerger *pMerger;        /* Object for reading/merging PMA data */
         1196  +      MergeEngine *pMerger;         /* Object for reading/merging PMA data */
  1194   1197         i64 iReadOff = 0;             /* Offset in pTemp1 to read from */
  1195   1198         i64 iWriteOff = 0;            /* Offset in pTemp2 to write to */
  1196   1199         int i;
  1197   1200         
  1198   1201         /* Allocate a merger object to merge PMAs together. */
  1199         -      pMerger = vdbeSorterMergerNew(nIter);
         1202  +      pMerger = vdbeMergeEngineNew(nIter);
  1200   1203         if( pMerger==0 ){
  1201   1204           rc = SQLITE_NOMEM;
  1202   1205           break;
  1203   1206         }
  1204   1207   
  1205   1208         /* Open a second temp file to write merged data to */
  1206         -      rc = vdbeSorterOpenTempFile(pThread->pVfs, &pTemp2);
         1209  +      rc = vdbeSorterOpenTempFile(pTask->pVfs, &pTemp2);
  1207   1210         if( rc==SQLITE_OK ){
  1208         -        rc = vdbeSorterExtendFile(pTemp2, pThread->iTemp1Off);
         1211  +        rc = vdbeSorterExtendFile(pTemp2, pTask->iTemp1Off);
  1209   1212         }
  1210   1213         if( rc!=SQLITE_OK ){
  1211         -        vdbeSorterMergerFree(pMerger);
         1214  +        vdbeMergeEngineFree(pMerger);
  1212   1215           break;
  1213   1216         }
  1214   1217   
  1215   1218         /* This loop runs once for each output PMA. Each output PMA is made
  1216   1219         ** of data merged from up to SORTER_MAX_MERGE_COUNT input PMAs. */
  1217         -      for(i=0; i<pThread->nPMA; i+=SORTER_MAX_MERGE_COUNT){
  1218         -        FileWriter writer;        /* Object for writing data to pTemp2 */
         1220  +      for(i=0; i<pTask->nPMA; i+=SORTER_MAX_MERGE_COUNT){
         1221  +        PmaWriter writer;         /* Object for writing data to pTemp2 */
  1219   1222           i64 nOut = 0;             /* Bytes of data in output PMA */
  1220   1223           int bEof = 0;
  1221   1224           int rc2;
  1222   1225   
  1223   1226           /* Configure the merger object to read and merge data from the next 
  1224   1227           ** SORTER_MAX_MERGE_COUNT PMAs in pTemp1 (or from all remaining PMAs,
  1225   1228           ** if that is fewer). */
  1226   1229           int iIter;
  1227   1230           for(iIter=0; iIter<SORTER_MAX_MERGE_COUNT; iIter++){
  1228         -          VdbeSorterIter *pIter = &pMerger->aIter[iIter];
  1229         -          rc = vdbeSorterIterInit(pThread, iReadOff, pIter, &nOut);
         1231  +          PmaReader *pIter = &pMerger->aIter[iIter];
         1232  +          rc = vdbePmaReaderInit(pTask, iReadOff, pIter, &nOut);
  1230   1233             iReadOff = pIter->iEof;
  1231         -          if( iReadOff>=pThread->iTemp1Off || rc!=SQLITE_OK ) break;
         1234  +          if( iReadOff>=pTask->iTemp1Off || rc!=SQLITE_OK ) break;
  1232   1235           }
  1233   1236           for(iIter=pMerger->nTree-1; rc==SQLITE_OK && iIter>0; iIter--){
  1234         -          rc = vdbeSorterDoCompare(pThread, pMerger, iIter);
         1237  +          rc = vdbeSorterDoCompare(pTask, pMerger, iIter);
  1235   1238           }
  1236   1239   
  1237         -        fileWriterInit(pTemp2, &writer, pThread->pgsz, iWriteOff);
  1238         -        fileWriterWriteVarint(&writer, nOut);
         1240  +        vdbePmaWriterInit(pTemp2, &writer, pTask->pgsz, iWriteOff);
         1241  +        vdbePmaWriteVarint(&writer, nOut);
  1239   1242           while( rc==SQLITE_OK && bEof==0 ){
  1240         -          VdbeSorterIter *pIter = &pMerger->aIter[ pMerger->aTree[1] ];
         1243  +          PmaReader *pIter = &pMerger->aIter[ pMerger->aTree[1] ];
  1241   1244             assert( pIter->pFile!=0 );        /* pIter is not at EOF */
  1242         -          fileWriterWriteVarint(&writer, pIter->nKey);
  1243         -          fileWriterWrite(&writer, pIter->aKey, pIter->nKey);
  1244         -          rc = vdbeSorterNext(pThread, pMerger, &bEof);
         1245  +          vdbePmaWriteVarint(&writer, pIter->nKey);
         1246  +          vdbePmaWriteBlob(&writer, pIter->aKey, pIter->nKey);
         1247  +          rc = vdbeSorterNext(pTask, pMerger, &bEof);
  1245   1248           }
  1246         -        rc2 = fileWriterFinish(&writer, &iWriteOff);
         1249  +        rc2 = vdbePmaWriterFinish(&writer, &iWriteOff);
  1247   1250           if( rc==SQLITE_OK ) rc = rc2;
  1248   1251         }
  1249   1252   
  1250         -      vdbeSorterMergerFree(pMerger);
  1251         -      sqlite3OsCloseFree(pThread->pTemp1);
  1252         -      pThread->pTemp1 = pTemp2;
  1253         -      pThread->nPMA = (i / SORTER_MAX_MERGE_COUNT);
  1254         -      pThread->iTemp1Off = iWriteOff;
         1253  +      vdbeMergeEngineFree(pMerger);
         1254  +      sqlite3OsCloseFree(pTask->pTemp1);
         1255  +      pTask->pTemp1 = pTemp2;
         1256  +      pTask->nPMA = (i / SORTER_MAX_MERGE_COUNT);
         1257  +      pTask->iTemp1Off = iWriteOff;
  1255   1258       }
  1256   1259     }else{
  1257         -    /* Sort the pThread->pList list */
  1258         -    rc = vdbeSorterSort(pThread);
         1260  +    /* Sort the pTask->pList list */
         1261  +    rc = vdbeSorterSort(pTask);
  1259   1262   
  1260   1263       /* If required, write the list out to a PMA. */
  1261         -    if( rc==SQLITE_OK && pThread->eWork==SORT_SUBTASK_TO_PMA ){
         1264  +    if( rc==SQLITE_OK && pTask->eWork==SORT_SUBTASK_TO_PMA ){
  1262   1265   #ifdef SQLITE_DEBUG
  1263         -      i64 nExpect = pThread->nInMemory
  1264         -        + sqlite3VarintLen(pThread->nInMemory)
  1265         -        + pThread->iTemp1Off;
         1266  +      i64 nExpect = pTask->nInMemory
         1267  +        + sqlite3VarintLen(pTask->nInMemory)
         1268  +        + pTask->iTemp1Off;
  1266   1269   #endif
  1267         -      rc = vdbeSorterListToPMA(pThread);
  1268         -      assert( rc!=SQLITE_OK || (nExpect==pThread->iTemp1Off) );
         1270  +      rc = vdbeSorterListToPMA(pTask);
         1271  +      assert( rc!=SQLITE_OK || (nExpect==pTask->iTemp1Off) );
  1269   1272       }
  1270   1273     }
  1271   1274   
  1272   1275    thread_out:
  1273         -  pThread->bDone = 1;
  1274         -  if( rc==SQLITE_OK && pThread->pUnpacked->errCode ){
  1275         -    assert( pThread->pUnpacked->errCode==SQLITE_NOMEM );
         1276  +  pTask->bDone = 1;
         1277  +  if( rc==SQLITE_OK && pTask->pUnpacked->errCode ){
         1278  +    assert( pTask->pUnpacked->errCode==SQLITE_NOMEM );
  1276   1279       rc = SQLITE_NOMEM;
  1277   1280     }
  1278   1281     return SQLITE_INT_TO_PTR(rc);
  1279   1282   }
  1280   1283   
  1281   1284   /*
  1282   1285   ** Run the activity scheduled by the object passed as the only argument
  1283   1286   ** in the current thread.
  1284   1287   */
  1285         -static int vdbeSorterRunThread(SortSubtask *pThread){
  1286         -  int rc = SQLITE_PTR_TO_INT( vdbeSortSubtaskMain((void*)pThread) );
  1287         -  assert( pThread->bDone );
  1288         -  pThread->bDone = 0;
         1288  +static int vdbeSorterRunTask(SortSubtask *pTask){
         1289  +  int rc = SQLITE_PTR_TO_INT( vdbeSortSubtaskMain((void*)pTask) );
         1290  +  assert( pTask->bDone );
         1291  +  pTask->bDone = 0;
  1289   1292     return rc;
  1290   1293   }
  1291   1294   
  1292   1295   /*
  1293   1296   ** Flush the current contents of VdbeSorter.pRecord to a new PMA, possibly
  1294   1297   ** using a background thread.
  1295   1298   **
  1296   1299   ** If argument bFg is non-zero, the operation always uses the calling thread.
  1297   1300   */
  1298   1301   static int vdbeSorterFlushPMA(sqlite3 *db, const VdbeCursor *pCsr, int bFg){
  1299   1302     VdbeSorter *pSorter = pCsr->pSorter;
  1300   1303     int rc = SQLITE_OK;
  1301   1304     int i;
  1302         -  SortSubtask *pThread = 0;    /* Thread context used to create new PMA */
  1303         -  int nWorker = (pSorter->nThread-1);
         1305  +  SortSubtask *pTask = 0;    /* Thread context used to create new PMA */
         1306  +  int nWorker = (pSorter->nTask-1);
  1304   1307   
  1305   1308     pSorter->bUsePMA = 1;
  1306   1309     for(i=0; i<nWorker; i++){
  1307   1310       int iTest = (pSorter->iPrev + i + 1) % nWorker;
  1308         -    pThread = &pSorter->aThread[iTest];
         1311  +    pTask = &pSorter->aTask[iTest];
  1309   1312   #if SQLITE_MAX_WORKER_THREADS>0
  1310         -    if( pThread->bDone ){
         1313  +    if( pTask->bDone ){
  1311   1314         void *pRet;
  1312         -      assert( pThread->pThread );
  1313         -      rc = sqlite3ThreadJoin(pThread->pThread, &pRet);
  1314         -      pThread->pThread = 0;
  1315         -      pThread->bDone = 0;
         1315  +      assert( pTask->pTask );
         1316  +      rc = sqlite3ThreadJoin(pTask->pTask, &pRet);
         1317  +      pTask->pTask = 0;
         1318  +      pTask->bDone = 0;
  1316   1319         if( rc==SQLITE_OK ){
  1317   1320           rc = SQLITE_PTR_TO_INT(pRet);
  1318   1321         }
  1319   1322       }
  1320   1323   #endif
  1321         -    if( pThread->pThread==0 ) break;
  1322         -    pThread = 0;
         1324  +    if( pTask->pThread==0 ) break;
         1325  +    pTask = 0;
  1323   1326     }
  1324         -  if( pThread==0 ){
  1325         -    pThread = &pSorter->aThread[nWorker];
         1327  +  if( pTask==0 ){
         1328  +    pTask = &pSorter->aTask[nWorker];
  1326   1329     }
  1327         -  pSorter->iPrev = (pThread - pSorter->aThread);
         1330  +  pSorter->iPrev = (pTask - pSorter->aTask);
  1328   1331   
  1329   1332     if( rc==SQLITE_OK ){
  1330         -    assert( pThread->pThread==0 && pThread->bDone==0 );
  1331         -    pThread->eWork = SORT_SUBTASK_TO_PMA;
  1332         -    pThread->pList = pSorter->pRecord;
  1333         -    pThread->nInMemory = pSorter->nInMemory;
         1333  +    assert( pTask->pThread==0 && pTask->bDone==0 );
         1334  +    pTask->eWork = SORT_SUBTASK_TO_PMA;
         1335  +    pTask->pList = pSorter->pRecord;
         1336  +    pTask->nInMemory = pSorter->nInMemory;
  1334   1337       pSorter->nInMemory = 0;
  1335   1338       pSorter->pRecord = 0;
  1336   1339   
  1337   1340       if( pSorter->aMemory ){
  1338         -      u8 *aMem = pThread->aListMemory;
  1339         -      pThread->aListMemory = pSorter->aMemory;
         1341  +      u8 *aMem = pTask->aListMemory;
         1342  +      pTask->aListMemory = pSorter->aMemory;
  1340   1343         pSorter->aMemory = aMem;
  1341   1344       }
  1342   1345   
  1343   1346   #if SQLITE_MAX_WORKER_THREADS>0
  1344         -    if( !bFg && pThread!=&pSorter->aThread[nWorker] ){
         1347  +    if( !bFg && pTask!=&pSorter->aTask[nWorker] ){
  1345   1348         /* Launch a background thread for this operation */
  1346         -      void *pCtx = (void*)pThread;
  1347         -      assert( pSorter->aMemory==0 || pThread->aListMemory!=0 );
  1348         -      if( pThread->aListMemory ){
         1349  +      void *pCtx = (void*)pTask;
         1350  +      assert( pSorter->aMemory==0 || pTask->aListMemory!=0 );
         1351  +      if( pTask->aListMemory ){
  1349   1352           if( pSorter->aMemory==0 ){
  1350   1353             pSorter->aMemory = sqlite3Malloc(pSorter->nMemory);
  1351   1354             if( pSorter->aMemory==0 ) return SQLITE_NOMEM;
  1352   1355           }else{
  1353   1356             pSorter->nMemory = sqlite3MallocSize(pSorter->aMemory);
  1354   1357           }
  1355   1358         }
  1356         -      rc = sqlite3ThreadCreate(&pThread->pThread, vdbeSortSubtaskMain, pCtx);
         1359  +      rc = sqlite3ThreadCreate(&pTask->pTask, vdbeSortSubtaskMain, pCtx);
  1357   1360       }else
  1358   1361   #endif
  1359   1362       {
  1360   1363         /* Use the foreground thread for this operation */
  1361         -      rc = vdbeSorterRunThread(pThread);
         1364  +      rc = vdbeSorterRunTask(pTask);
  1362   1365         if( rc==SQLITE_OK ){
  1363         -        u8 *aMem = pThread->aListMemory;
  1364         -        pThread->aListMemory = pSorter->aMemory;
         1366  +        u8 *aMem = pTask->aListMemory;
         1367  +        pTask->aListMemory = pSorter->aMemory;
  1365   1368           pSorter->aMemory = aMem;
  1366         -        assert( pThread->pList==0 );
         1369  +        assert( pTask->pList==0 );
  1367   1370         }
  1368   1371       }
  1369   1372     }
  1370   1373   
  1371   1374     return rc;
  1372   1375   }
  1373   1376   
................................................................................
  1465   1468   
  1466   1469   /*
  1467   1470   ** Return the total number of PMAs in all temporary files.
  1468   1471   */
  1469   1472   static int vdbeSorterCountPMA(VdbeSorter *pSorter){
  1470   1473     int nPMA = 0;
  1471   1474     int i;
  1472         -  for(i=0; i<pSorter->nThread; i++){
  1473         -    nPMA += pSorter->aThread[i].nPMA;
         1475  +  for(i=0; i<pSorter->nTask; i++){
         1476  +    nPMA += pSorter->aTask[i].nPMA;
  1474   1477     }
  1475   1478     return nPMA;
  1476   1479   }
  1477   1480   
  1478   1481   /*
  1479         -** Once the sorter has been populated, this function is called to prepare
  1480         -** for iterating through its contents in sorted order.
         1482  +** Once the sorter has been populated by calls to sqlite3VdbeSorterWrite,
         1483  +** this function is called to prepare for iterating through the records
         1484  +** in sorted order.
  1481   1485   */
  1482   1486   int sqlite3VdbeSorterRewind(sqlite3 *db, const VdbeCursor *pCsr, int *pbEof){
  1483   1487     VdbeSorter *pSorter = pCsr->pSorter;
  1484   1488     int rc = SQLITE_OK;             /* Return code */
  1485   1489   
  1486   1490     assert( pSorter );
  1487   1491   
  1488   1492     /* If no data has been written to disk, then do not do so now. Instead,
  1489   1493     ** sort the VdbeSorter.pRecord list. The vdbe layer will read data directly
  1490   1494     ** from the in-memory list.  */
  1491   1495     if( pSorter->bUsePMA==0 ){
  1492   1496       if( pSorter->pRecord ){
  1493         -      SortSubtask *pThread = &pSorter->aThread[0];
         1497  +      SortSubtask *pTask = &pSorter->aTask[0];
  1494   1498         *pbEof = 0;
  1495         -      pThread->pList = pSorter->pRecord;
  1496         -      pThread->eWork = SORT_SUBTASK_SORT;
  1497         -      assert( pThread->aListMemory==0 );
  1498         -      pThread->aListMemory = pSorter->aMemory;
  1499         -      rc = vdbeSorterRunThread(pThread);
  1500         -      pThread->aListMemory = 0;
  1501         -      pSorter->pRecord = pThread->pList;
  1502         -      pThread->pList = 0;
         1499  +      pTask->pList = pSorter->pRecord;
         1500  +      pTask->eWork = SORT_SUBTASK_SORT;
         1501  +      assert( pTask->aListMemory==0 );
         1502  +      pTask->aListMemory = pSorter->aMemory;
         1503  +      rc = vdbeSorterRunTask(pTask);
         1504  +      pTask->aListMemory = 0;
         1505  +      pSorter->pRecord = pTask->pList;
         1506  +      pTask->pList = 0;
  1503   1507       }else{
  1504   1508         *pbEof = 1;
  1505   1509       }
  1506   1510       return rc;
  1507   1511     }
  1508   1512   
  1509   1513     /* Write the current in-memory list to a PMA. */
................................................................................
  1514   1518     /* Join all threads */
  1515   1519     rc = vdbeSorterJoinAll(pSorter, rc);
  1516   1520   
  1517   1521     /* If there are more than SORTER_MAX_MERGE_COUNT PMAs on disk, merge
  1518   1522     ** some of them together so that this is no longer the case. */
  1519   1523     if( vdbeSorterCountPMA(pSorter)>SORTER_MAX_MERGE_COUNT ){
  1520   1524       int i;
  1521         -    for(i=0; rc==SQLITE_OK && i<pSorter->nThread; i++){
  1522         -      SortSubtask *pThread = &pSorter->aThread[i];
  1523         -      if( pThread->pTemp1 ){
  1524         -        pThread->nConsolidate = SORTER_MAX_MERGE_COUNT / pSorter->nThread;
  1525         -        pThread->eWork = SORT_SUBTASK_CONS;
         1525  +    for(i=0; rc==SQLITE_OK && i<pSorter->nTask; i++){
         1526  +      SortSubtask *pTask = &pSorter->aTask[i];
         1527  +      if( pTask->pTemp1 ){
         1528  +        pTask->nConsolidate = SORTER_MAX_MERGE_COUNT / pSorter->nTask;
         1529  +        pTask->eWork = SORT_SUBTASK_CONS;
  1526   1530   
  1527   1531   #if SQLITE_MAX_WORKER_THREADS>0
  1528         -        if( i<(pSorter->nThread-1) ){
  1529         -          void *pCtx = (void*)pThread;
  1530         -          rc = sqlite3ThreadCreate(&pThread->pThread,vdbeSortSubtaskMain,pCtx);
         1532  +        if( i<(pSorter->nTask-1) ){
         1533  +          void *pCtx = (void*)pTask;
         1534  +          rc = sqlite3ThreadCreate(&pTask->pTask,vdbeSortSubtaskMain,pCtx);
  1531   1535           }else
  1532   1536   #endif
  1533   1537           {
  1534         -          rc = vdbeSorterRunThread(pThread);
         1538  +          rc = vdbeSorterRunTask(pTask);
  1535   1539           }
  1536   1540         }
  1537   1541       }
  1538   1542     }
  1539   1543   
  1540   1544     /* Join all threads */
  1541   1545     rc = vdbeSorterJoinAll(pSorter, rc);
................................................................................
  1542   1546   
  1543   1547     /* Assuming no errors have occurred, set up a merger structure to read
  1544   1548     ** and merge all remaining PMAs.  */
  1545   1549     assert( pSorter->pMerger==0 );
  1546   1550     if( rc==SQLITE_OK ){
  1547   1551       int nIter = 0;                /* Number of iterators used */
  1548   1552       int i;
  1549         -    SorterMerger *pMerger;
  1550         -    for(i=0; i<pSorter->nThread; i++){
  1551         -      nIter += pSorter->aThread[i].nPMA;
         1553  +    MergeEngine *pMerger;
         1554  +    for(i=0; i<pSorter->nTask; i++){
         1555  +      nIter += pSorter->aTask[i].nPMA;
  1552   1556       }
  1553   1557   
  1554         -    pSorter->pMerger = pMerger = vdbeSorterMergerNew(nIter);
         1558  +    pSorter->pMerger = pMerger = vdbeMergeEngineNew(nIter);
  1555   1559       if( pMerger==0 ){
  1556   1560         rc = SQLITE_NOMEM;
  1557   1561       }else{
  1558   1562         int iIter = 0;
  1559   1563         int iThread = 0;
  1560         -      for(iThread=0; iThread<pSorter->nThread; iThread++){
         1564  +      for(iThread=0; iThread<pSorter->nTask; iThread++){
  1561   1565           int iPMA;
  1562   1566           i64 iReadOff = 0;
  1563         -        SortSubtask *pThread = &pSorter->aThread[iThread];
  1564         -        for(iPMA=0; iPMA<pThread->nPMA && rc==SQLITE_OK; iPMA++){
         1567  +        SortSubtask *pTask = &pSorter->aTask[iThread];
         1568  +        for(iPMA=0; iPMA<pTask->nPMA && rc==SQLITE_OK; iPMA++){
  1565   1569             i64 nDummy = 0;
  1566         -          VdbeSorterIter *pIter = &pMerger->aIter[iIter++];
  1567         -          rc = vdbeSorterIterInit(pThread, iReadOff, pIter, &nDummy);
         1570  +          PmaReader *pIter = &pMerger->aIter[iIter++];
         1571  +          rc = vdbePmaReaderInit(pTask, iReadOff, pIter, &nDummy);
  1568   1572             iReadOff = pIter->iEof;
  1569   1573           }
  1570   1574         }
  1571   1575   
  1572   1576         for(i=pMerger->nTree-1; rc==SQLITE_OK && i>0; i--){
  1573         -        rc = vdbeSorterDoCompare(&pSorter->aThread[0], pMerger, i);
         1577  +        rc = vdbeSorterDoCompare(&pSorter->aTask[0], pMerger, i);
  1574   1578         }
  1575   1579       }
  1576   1580     }
  1577   1581   
  1578   1582     if( rc==SQLITE_OK ){
  1579   1583       *pbEof = (pSorter->pMerger->aIter[pSorter->pMerger->aTree[1]].pFile==0);
  1580   1584     }
................................................................................
  1585   1589   ** Advance to the next element in the sorter.
  1586   1590   */
  1587   1591   int sqlite3VdbeSorterNext(sqlite3 *db, const VdbeCursor *pCsr, int *pbEof){
  1588   1592     VdbeSorter *pSorter = pCsr->pSorter;
  1589   1593     int rc;                         /* Return code */
  1590   1594   
  1591   1595     if( pSorter->pMerger ){
  1592         -    rc = vdbeSorterNext(&pSorter->aThread[0], pSorter->pMerger, pbEof);
         1596  +    rc = vdbeSorterNext(&pSorter->aTask[0], pSorter->pMerger, pbEof);
  1593   1597     }else{
  1594   1598       SorterRecord *pFree = pSorter->pRecord;
  1595   1599       pSorter->pRecord = pFree->u.pNext;
  1596   1600       pFree->u.pNext = 0;
  1597   1601       if( pSorter->aMemory==0 ) vdbeSorterRecordFree(db, pFree);
  1598   1602       *pbEof = !pSorter->pRecord;
  1599   1603       rc = SQLITE_OK;
................................................................................
  1607   1611   */
  1608   1612   static void *vdbeSorterRowkey(
  1609   1613     const VdbeSorter *pSorter,      /* Sorter object */
  1610   1614     int *pnKey                      /* OUT: Size of current key in bytes */
  1611   1615   ){
  1612   1616     void *pKey;
  1613   1617     if( pSorter->pMerger ){
  1614         -    VdbeSorterIter *pIter;
         1618  +    PmaReader *pIter;
  1615   1619       pIter = &pSorter->pMerger->aIter[ pSorter->pMerger->aTree[1] ];
  1616   1620       *pnKey = pIter->nKey;
  1617   1621       pKey = pIter->aKey;
  1618   1622     }else{
  1619   1623       *pnKey = pSorter->pRecord->nVal;
  1620   1624       pKey = SRVAL(pSorter->pRecord);
  1621   1625     }
................................................................................
  1659   1663   int sqlite3VdbeSorterCompare(
  1660   1664     const VdbeCursor *pCsr,         /* Sorter cursor */
  1661   1665     Mem *pVal,                      /* Value to compare to current sorter key */
  1662   1666     int nIgnore,                    /* Ignore this many fields at the end */
  1663   1667     int *pRes                       /* OUT: Result of comparison */
  1664   1668   ){
  1665   1669     VdbeSorter *pSorter = pCsr->pSorter;
  1666         -  UnpackedRecord *r2 = pSorter->aThread[0].pUnpacked;
         1670  +  UnpackedRecord *r2 = pSorter->aTask[0].pUnpacked;
  1667   1671     KeyInfo *pKeyInfo = pCsr->pKeyInfo;
  1668   1672     int i;
  1669   1673     void *pKey; int nKey;           /* Sorter key to compare pVal with */
  1670   1674   
  1671   1675     assert( r2->nField>=pKeyInfo->nField-nIgnore );
  1672   1676     r2->nField = pKeyInfo->nField-nIgnore;
  1673   1677