SQLite

Check-in [69026ec7dc]
Login

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

Overview
Comment:Rework the way trees of MergeEngine objects are built in vdbesort.c to make it easier to follow. Fix memory leaks that could follow an OOM or IO error. Add various comments to explain functions in vdbesort.c.
Downloads: Tarball | ZIP archive
Timelines: family | ancestors | descendants | both | threads
Files: files | file ages | folders
SHA1: 69026ec7dc3bd3e33bbe17c221a53cf1dd0f8945
User & Date: dan 2014-04-16 16:43:05.014
Context
2014-04-16
17:41
Change the name of vdbeIncrInit2 to vdbePmaReaderIncrInit. Add a header comment to the same function. (check-in: 6622d87675 user: dan tags: threads)
16:43
Rework the way trees of MergeEngine objects are built in vdbesort.c to make it easier to follow. Fix memory leaks that could follow an OOM or IO error. Add various comments to explain functions in vdbesort.c. (check-in: 69026ec7dc user: dan tags: threads)
2014-04-15
20:52
Fix some problems to do with OOM conditions in vdbesort.c. Some problems remain. (check-in: 2f94f9ce9b user: dan tags: threads)
Changes
Unified Diff Ignore Whitespace Patch
Changes to src/vdbesort.c.
1748
1749
1750
1751
1752
1753
1754



1755


1756



1757
1758
1759
1760
1761
1762
1763



1764
1765
1766
1767
1768
1769
1770
1771
1772
1773
1774
1775
1776
1777
1778
1779
1780
1781
1782
1783

















1784
1785
1786
1787
1788
1789
1790

1791
1792
1793
1794
1795
1796
1797
  }

  return rc;
}

/*
** Allocate and return a new IncrMerger object to read data from pMerger.



*/


static IncrMerger *vdbeIncrNew(SortSubtask *pTask, MergeEngine *pMerger){



  IncrMerger *pIncr = sqlite3_malloc(sizeof(IncrMerger));
  if( pIncr ){
    memset(pIncr, 0, sizeof(IncrMerger));
    pIncr->pMerger = pMerger;
    pIncr->pTask = pTask;
    pIncr->mxSz = MAX(pTask->pSorter->mxKeysize+9,pTask->pSorter->mxPmaSize/2);
    pTask->file2.iEof += pIncr->mxSz;



  }
  return pIncr;
}

/*
** Set the "use-threads" flag on object pIncr.
*/
static void vdbeIncrSetThreads(IncrMerger *pIncr, int bUseThread){
  if( bUseThread ){
    pIncr->bUseThread = 1;
    pIncr->pTask->file2.iEof -= pIncr->mxSz;
  }
}

#define INCRINIT2_NORMAL 0
#define INCRINIT2_TASK   1
#define INCRINIT2_ROOT   2

static int vdbeIncrInit2(PmaReader *pIter, int eMode);


















static int vdbeIncrInitMerger(
  SortSubtask *pTask, 
  MergeEngine *pMerger, 
  int eMode
){
  int i;
  int rc = SQLITE_OK;


  for(i=0; rc==SQLITE_OK && i<pMerger->nTree; i++){
    if( eMode==INCRINIT2_ROOT ){
      rc = vdbePmaReaderNext(&pMerger->aIter[i]);
    }else{
      rc = vdbeIncrInit2(&pMerger->aIter[i], INCRINIT2_NORMAL);
    }







>
>
>

>
>
|
>
>
>
|






>
>
>

|















<


>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>



|

<
|
>







1748
1749
1750
1751
1752
1753
1754
1755
1756
1757
1758
1759
1760
1761
1762
1763
1764
1765
1766
1767
1768
1769
1770
1771
1772
1773
1774
1775
1776
1777
1778
1779
1780
1781
1782
1783
1784
1785
1786
1787
1788
1789
1790
1791

1792
1793
1794
1795
1796
1797
1798
1799
1800
1801
1802
1803
1804
1805
1806
1807
1808
1809
1810
1811
1812
1813
1814
1815

1816
1817
1818
1819
1820
1821
1822
1823
1824
  }

  return rc;
}

/*
** Allocate and return a new IncrMerger object to read data from pMerger.
**
** If an OOM condition is encountered, return NULL. In this case free the
** pMerger argument before returning.
*/
static int vdbeIncrNew(
  SortSubtask *pTask, 
  MergeEngine *pMerger,
  IncrMerger **ppOut
){
  int rc = SQLITE_OK;
  IncrMerger *pIncr = *ppOut = (IncrMerger*)sqlite3_malloc(sizeof(IncrMerger));
  if( pIncr ){
    memset(pIncr, 0, sizeof(IncrMerger));
    pIncr->pMerger = pMerger;
    pIncr->pTask = pTask;
    pIncr->mxSz = MAX(pTask->pSorter->mxKeysize+9,pTask->pSorter->mxPmaSize/2);
    pTask->file2.iEof += pIncr->mxSz;
  }else{
    vdbeMergeEngineFree(pMerger);
    rc = SQLITE_NOMEM;
  }
  return rc;
}

/*
** Set the "use-threads" flag on object pIncr.
*/
static void vdbeIncrSetThreads(IncrMerger *pIncr, int bUseThread){
  if( bUseThread ){
    pIncr->bUseThread = 1;
    pIncr->pTask->file2.iEof -= pIncr->mxSz;
  }
}

#define INCRINIT2_NORMAL 0
#define INCRINIT2_TASK   1
#define INCRINIT2_ROOT   2

static int vdbeIncrInit2(PmaReader *pIter, int eMode);

/*
** Initialize the merger argument passed as the second argument. Once this
** function returns, the first key of merged data may be read from the merger
** object in the usual fashion.
**
** If argument eMode is INCRINIT2_ROOT, then it is assumed that any IncrMerge
** objects attached to the PmaReader objects that the merger reads from have
** already been populated, but that they have not yet populated aFile[0] and
** set the PmaReader objects up to read from it. In this case all that is
** required is to call vdbePmaReaderNext() on each iterator to point it at
** its first key.
**
** Otherwise, if eMode is any value other than INCRINIT2_ROOT, then use 
** vdbeIncrInit2() to initialize each PmaReader that feeds data to pMerger.
**
** SQLITE_OK is returned if successful, or an SQLite error code otherwise.
*/
static int vdbeIncrInitMerger(
  SortSubtask *pTask, 
  MergeEngine *pMerger, 
  int eMode                       /* One of the INCRINIT2_XXX constants */
){

  int rc = SQLITE_OK;             /* Return code */
  int i;                          /* For iterating through PmaReader objects */

  for(i=0; rc==SQLITE_OK && i<pMerger->nTree; i++){
    if( eMode==INCRINIT2_ROOT ){
      rc = vdbePmaReaderNext(&pMerger->aIter[i]);
    }else{
      rc = vdbeIncrInit2(&pMerger->aIter[i], INCRINIT2_NORMAL);
    }
1847
1848
1849
1850
1851
1852
1853



1854
1855
1856
1857
1858
1859
1860








1861
1862
1863
1864
1865
1866
1867
      rc = vdbePmaReaderNext(pIter);
    }
  }
  return rc;
}

#if SQLITE_MAX_WORKER_THREADS>0



static void *vdbeIncrInit2Thread(void *pCtx){
  PmaReader *pReader = (PmaReader*)pCtx;
  void *pRet = SQLITE_INT_TO_PTR( vdbeIncrInit2(pReader, INCRINIT2_TASK) );
  pReader->pIncr->pTask->bDone = 1;
  return pRet;
}









static int vdbeIncrBgInit2(PmaReader *pIter){
  void *pCtx = (void*)pIter;
  return vdbeSorterCreateThread(pIter->pIncr->pTask, vdbeIncrInit2Thread, pCtx);
}
#endif

/*







>
>
>







>
>
>
>
>
>
>
>







1874
1875
1876
1877
1878
1879
1880
1881
1882
1883
1884
1885
1886
1887
1888
1889
1890
1891
1892
1893
1894
1895
1896
1897
1898
1899
1900
1901
1902
1903
1904
1905
      rc = vdbePmaReaderNext(pIter);
    }
  }
  return rc;
}

#if SQLITE_MAX_WORKER_THREADS>0
/*
** The main routine for vdbeIncrInit2() operations run in background threads.
*/
static void *vdbeIncrInit2Thread(void *pCtx){
  PmaReader *pReader = (PmaReader*)pCtx;
  void *pRet = SQLITE_INT_TO_PTR( vdbeIncrInit2(pReader, INCRINIT2_TASK) );
  pReader->pIncr->pTask->bDone = 1;
  return pRet;
}

/*
** Use a background thread to invoke vdbeIncrInit2(INCRINIT2_TASK) on the
** the PmaReader object passed as the first argument.
**
** This call will initialize the various fields of the pIter->pIncr 
** structure and, if it is a multi-threaded IncrMerger, launch a 
** background thread to populate aFile[1].
*/
static int vdbeIncrBgInit2(PmaReader *pIter){
  void *pCtx = (void*)pIter;
  return vdbeSorterCreateThread(pIter->pIncr->pTask, vdbeIncrInit2Thread, pCtx);
}
#endif

/*
1901
1902
1903
1904
1905
1906
1907
1908

1909








1910
1911
1912





1913











1914
1915
1916


1917

1918
1919



1920
1921

1922

1923
1924
1925
1926
1927
1928
1929




1930

1931


1932
1933





1934






1935






















1936

1937






1938










1939




















1940
1941

1942
1943
1944
1945
1946
1947
1948
1949
1950
1951

1952
1953
1954
1955
1956
1957
1958
1959
1960
1961
1962
1963
1964
1965
1966
1967
1968
1969
1970
1971
1972
1973
1974
1975
1976
1977
1978
1979
1980
1981
1982
1983
1984
1985
1986
1987
1988
1989
1990
1991
1992
1993
1994
1995
1996
1997
1998
1999
2000
2001
2002
2003
2004
2005
2006
2007
2008
2009
2010
2011
2012
2013
2014
2015
2016
2017
2018
2019
2020
2021
2022
2023
2024
2025
2026
2027
2028
2029
2030
2031
2032
2033
2034
2035
2036
2037
2038
2039
2040
2041
2042
2043
2044
2045
2046
2047
2048
2049
2050
2051
2052
2053
2054
2055
2056
2057
2058
2059

2060
2061
2062
2063
2064
2065
2066
2067
2068
2069

2070
2071
2072
2073
2074
2075
2076
2077
2078
2079
2080
2081
2082
2083
2084
2085
2086
2087
2088
    vdbeMergeEngineFree(pNew);
    *ppOut = 0;
  }
  *piOffset = iOff;
  return rc;
}

typedef struct IncrBuilder IncrBuilder;

struct IncrBuilder {








  int nPMA;                     /* Number of iterators used so far */
  MergeEngine *pMerger;         /* Merge engine to populate. */
};

















static int vdbeAddToBuilder(
  SortSubtask *pTask,
  IncrBuilder *pBuilder, 


  MergeEngine *pMerger

){
  int rc = SQLITE_OK;



  IncrMerger *pIncr;


  assert( pMerger );

  if( pBuilder->nPMA==SORTER_MAX_MERGE_COUNT ){
    rc = vdbeAddToBuilder(pTask, &pBuilder[1], pBuilder->pMerger);
    pBuilder->pMerger = 0;
    pBuilder->nPMA = 0;
  }

  if( rc==SQLITE_OK && pBuilder->pMerger==0 ){




    pBuilder->pMerger = vdbeMergeEngineNew(SORTER_MAX_MERGE_COUNT);

    if( pBuilder->pMerger==0 ) rc = SQLITE_NOMEM;


  }






  if( rc==SQLITE_OK ){






    pIncr = vdbeIncrNew(pTask, pMerger);






















    if( pIncr==0 ) rc = SQLITE_NOMEM;

    pBuilder->pMerger->aIter[pBuilder->nPMA++].pIncr = pIncr;






  }































  if( rc!=SQLITE_OK ){
    vdbeMergeEngineFree(pMerger);

  }

  return rc;
}

/*
** Populate iterator *pIter so that it may be used to iterate through all 
** keys stored in all PMAs created by this sorter.
*/
static int vdbePmaReaderIncrInit(VdbeSorter *pSorter){

  SortSubtask *pTask0 = &pSorter->aTask[0];
  MergeEngine *pMain = 0;
  sqlite3 *db = pTask0->pSorter->db;
  int rc = SQLITE_OK;
  int iTask;

  IncrBuilder *aMerge;
  const int nMerge = 32;
  aMerge = sqlite3DbMallocZero(db, sizeof(aMerge[0])*nMerge);
  if( aMerge==0 ) return SQLITE_NOMEM;

  if( pSorter->nTask>1 ){
    pMain = vdbeMergeEngineNew(pSorter->nTask);
    if( pMain==0 ) rc = SQLITE_NOMEM;
  }

  for(iTask=0; iTask<pSorter->nTask && rc==SQLITE_OK; iTask++){
    MergeEngine *pRoot = 0;
    int iPMA;
    i64 iReadOff = 0;
    SortSubtask *pTask = &pSorter->aTask[iTask];
    if( pTask->nPMA==0 ) continue;
    for(iPMA=0; iPMA<pTask->nPMA; iPMA += SORTER_MAX_MERGE_COUNT){
      MergeEngine *pMerger = 0;
      int nReader = MIN(pTask->nPMA - iPMA, SORTER_MAX_MERGE_COUNT);

      rc = vdbeMergeEngineLevel0(pTask, nReader, &iReadOff, &pMerger);
      if( rc!=SQLITE_OK ) break;

      if( iPMA==0 ){
        pRoot = pMerger;
      }else{
        if( pRoot ){
          rc = vdbeAddToBuilder(pTask, &aMerge[0], pRoot);
          pRoot = 0;
          if( rc!=SQLITE_OK ){
            vdbeMergeEngineFree(pMerger);
            break;
          }
        }
        rc = vdbeAddToBuilder(pTask, &aMerge[0], pMerger);
        if( rc!=SQLITE_OK ) break;
      }
    }

    if( pRoot==0 ){
      int i;
      for(i=0; rc==SQLITE_OK && i<nMerge; i++){
        if( aMerge[i].pMerger ){
          if( pRoot ){
            rc = vdbeAddToBuilder(pTask, &aMerge[i], pRoot);
            if( rc!=SQLITE_OK ) break;
          }
          pRoot = aMerge[i].pMerger;
          aMerge[i].pMerger = 0;
        }
      }
    }

    if( rc==SQLITE_OK ){
      if( pMain==0 ){
        pMain = pRoot;
      }else{
        IncrMerger *pNew = vdbeIncrNew(pTask, pRoot);
        pMain->aIter[iTask].pIncr = pNew;
        if( pNew==0 ) rc = SQLITE_NOMEM;
      }
      memset(aMerge, 0, nMerge*sizeof(aMerge[0]));
    }

    if( rc!=SQLITE_OK ){
      vdbeMergeEngineFree(pRoot);
    }
  }

  if( rc==SQLITE_OK ){
#if SQLITE_MAX_WORKER_THREADS
    if( pSorter->bUseThreads ){
      PmaReader *pIter;
      SortSubtask *pLast = &pSorter->aTask[pSorter->nTask-1];
      rc = vdbeSortAllocUnpacked(pLast);
      if( rc==SQLITE_OK ){
        pIter = (PmaReader*)sqlite3DbMallocZero(db, sizeof(PmaReader));
        pSorter->pReader = pIter;
      }
      if( rc==SQLITE_OK ){
        pIter->pIncr = vdbeIncrNew(pLast, pMain);
        if( pIter->pIncr==0 ){
          rc = SQLITE_NOMEM;
        }
        else{
          vdbeIncrSetThreads(pIter->pIncr, pSorter->bUseThreads);
          for(iTask=0; iTask<(pSorter->nTask-1); iTask++){
            IncrMerger *pIncr;
            if( (pIncr = pMain->aIter[iTask].pIncr) ){
              vdbeIncrSetThreads(pIncr, pSorter->bUseThreads);
              assert( pIncr->pTask!=pLast );
            }
          }
          if( pSorter->nTask>1 ){
            for(iTask=0; rc==SQLITE_OK && iTask<pSorter->nTask; iTask++){
              PmaReader *p = &pMain->aIter[iTask];
              assert( p->pIncr==0 || p->pIncr->pTask==&pSorter->aTask[iTask] );
              if( p->pIncr ){ rc = vdbeIncrBgInit2(p); }
            }
          }
          pMain = 0;
        }

      }
      if( rc==SQLITE_OK ){
        int eMode = (pSorter->nTask>1 ? INCRINIT2_ROOT : INCRINIT2_NORMAL);
        rc = vdbeIncrInit2(pIter, eMode);
      }
    }else
#endif
    {
      pSorter->pMerger = pMain;
      rc = vdbeIncrInitMerger(pTask0, pMain, INCRINIT2_NORMAL);

      pMain = 0;
    }
  }

  if( rc!=SQLITE_OK ){
    int i;
    for(i=0; rc==SQLITE_OK && i<nMerge; i++){
      vdbeMergeEngineFree(aMerge[i].pMerger);
    }
    vdbeMergeEngineFree(pMain);
  }
  sqlite3_free(aMerge);
  return rc;
}


/*
** Once the sorter has been populated by calls to sqlite3VdbeSorterWrite,
** this function is called to prepare for iterating through the records







<
>
|
>
>
>
>
>
>
>
>
|
<
<
>
>
>
>
>
|
>
>
>
>
>
>
>
>
>
>
>
|
|
<
>
>
|
>


>
>
>


>
|
>
|
<
<
<


|
>
>
>
>
|
>
|
>
>
|
|
>
>
>
>
>

>
>
>
>
>
>
|
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
|
>
|
>
>
>
>
>
>
|
>
>
>
>
>
>
>
>
>
>

>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>

|
>

|








>



<


<
<
<
<
|
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<











|
<
|
<
<















<

>








<

>





<
<
<
<


<







1939
1940
1941
1942
1943
1944
1945

1946
1947
1948
1949
1950
1951
1952
1953
1954
1955
1956


1957
1958
1959
1960
1961
1962
1963
1964
1965
1966
1967
1968
1969
1970
1971
1972
1973
1974
1975

1976
1977
1978
1979
1980
1981
1982
1983
1984
1985
1986
1987
1988
1989
1990



1991
1992
1993
1994
1995
1996
1997
1998
1999
2000
2001
2002
2003
2004
2005
2006
2007
2008
2009
2010
2011
2012
2013
2014
2015
2016
2017
2018
2019
2020
2021
2022
2023
2024
2025
2026
2027
2028
2029
2030
2031
2032
2033
2034
2035
2036
2037
2038
2039
2040
2041
2042
2043
2044
2045
2046
2047
2048
2049
2050
2051
2052
2053
2054
2055
2056
2057
2058
2059
2060
2061
2062
2063
2064
2065
2066
2067
2068
2069
2070
2071
2072
2073
2074
2075
2076
2077
2078
2079
2080
2081
2082
2083
2084
2085
2086
2087
2088
2089
2090
2091
2092
2093
2094
2095
2096
2097

2098
2099




2100
































































2101
2102
2103
2104
2105
2106
2107
2108
2109
2110
2111
2112

2113


2114
2115
2116
2117
2118
2119
2120
2121
2122
2123
2124
2125
2126
2127
2128

2129
2130
2131
2132
2133
2134
2135
2136
2137
2138

2139
2140
2141
2142
2143
2144
2145




2146
2147

2148
2149
2150
2151
2152
2153
2154
    vdbeMergeEngineFree(pNew);
    *ppOut = 0;
  }
  *piOffset = iOff;
  return rc;
}


/*
** Return the depth of a tree comprising nPMA PMAs, assuming a fanout of
** SORTER_MAX_MERGE_COUNT. The returned value does not include leaf nodes.
**
** i.e.
**
**   nPMA<=16    -> TreeDepth() == 0
**   nPMA<=256   -> TreeDepth() == 1
**   nPMA<=65536 -> TreeDepth() == 2
*/
static int vdbeSorterTreeDepth(int nPMA){


  int nDepth = 0;
  i64 nDiv = SORTER_MAX_MERGE_COUNT;
  while( nDiv < (i64)nPMA ){
    nDiv = nDiv * SORTER_MAX_MERGE_COUNT;
    nDepth++;
  }
  return nDepth;
}

/*
** pRoot is the root of an incremental merge-tree with depth nDepth (according
** to vdbeSorterTreeDepth()). pLeaf is the iSeq'th leaf to be added to the
** tree, counting from zero. This function adds pLeaf to the tree.
**
** If successful, SQLITE_OK is returned. If an error occurs, an SQLite error
** code is returned and pLeaf is freed.
*/
static int vdbeSorterAddToTree(
  SortSubtask *pTask,             /* Task context */

  int nDepth,                     /* Depth of tree according to TreeDepth() */
  int iSeq,                       /* Sequence number of leaf within tree */
  MergeEngine *pRoot,             /* Root of tree */
  MergeEngine *pLeaf              /* Leaf to add to tree */
){
  int rc = SQLITE_OK;
  int nDiv = 1;
  int i;
  MergeEngine *p = pRoot;
  IncrMerger *pIncr;

  rc = vdbeIncrNew(pTask, pLeaf, &pIncr);

  for(i=1; i<nDepth; i++){
    nDiv = nDiv * SORTER_MAX_MERGE_COUNT;



  }

  for(i=1; i<nDepth && rc==SQLITE_OK; i++){
    int iIter = (iSeq / nDiv) % SORTER_MAX_MERGE_COUNT;
    PmaReader *pIter = &p->aIter[iIter];

    if( pIter->pIncr==0 ){
      MergeEngine *pNew = vdbeMergeEngineNew(SORTER_MAX_MERGE_COUNT);
      if( pNew==0 ){
        rc = SQLITE_NOMEM;
      }else{
        rc = vdbeIncrNew(pTask, pNew, &pIter->pIncr);
      }
    }

    p = pIter->pIncr->pMerger;
    nDiv = nDiv / SORTER_MAX_MERGE_COUNT;
  }

  if( rc==SQLITE_OK ){
    p->aIter[iSeq % SORTER_MAX_MERGE_COUNT].pIncr = pIncr;
  }else{
    vdbeIncrFree(pIncr);
  }
  return rc;
}

/*
** This function is called as part of a SorterRewind() operation on a sorter
** that has already written two or more level-0 PMAs to one or more temp
** files. It builds a tree of MergeEngine/IncrMerger/PmaReader objects that 
** can be used to incrementally merge all PMAs on disk.
**
** If successful, SQLITE_OK is returned and *ppOut set to point to the
** MergeEngine object at the root of the tree before returning. Or, if an
** error occurs, an SQLite error code is returned and the final value 
** of *ppOut is undefined.
*/
static int vdbeSorterMergeTreeBuild(VdbeSorter *pSorter, MergeEngine **ppOut){
  MergeEngine *pMain = 0;
  int rc = SQLITE_OK;
  int iTask;

  /* If the sorter uses more than one task, then create the top-level 
  ** MergeEngine here. This MergeEngine will read data from exactly 
  ** one PmaReader per sub-task.  */
  assert( pSorter->bUseThreads || pSorter->nTask==1 );
  if( pSorter->nTask>1 ){
    pMain = vdbeMergeEngineNew(pSorter->nTask);
    if( pMain==0 ) rc = SQLITE_NOMEM;
  }

  for(iTask=0; iTask<pSorter->nTask && rc==SQLITE_OK; iTask++){
    SortSubtask *pTask = &pSorter->aTask[iTask];
    if( pTask->nPMA ){
      MergeEngine *pRoot = 0;     /* Root node of tree for this task */
      int nDepth = vdbeSorterTreeDepth(pTask->nPMA);
      i64 iReadOff = 0;

      if( pTask->nPMA<=SORTER_MAX_MERGE_COUNT ){
        rc = vdbeMergeEngineLevel0(pTask, pTask->nPMA, &iReadOff, &pRoot);
      }else{
        int i;
        int iSeq = 0;
        pRoot = vdbeMergeEngineNew(SORTER_MAX_MERGE_COUNT);
        if( pRoot==0 ) rc = SQLITE_NOMEM;
        for(i=0; i<pTask->nPMA && rc==SQLITE_OK; i += SORTER_MAX_MERGE_COUNT){
          MergeEngine *pMerger = 0; /* New level-0 PMA merger */
          int nReader;              /* Number of level-0 PMAs to merge */

          nReader = MIN(pTask->nPMA - i, SORTER_MAX_MERGE_COUNT);
          rc = vdbeMergeEngineLevel0(pTask, nReader, &iReadOff, &pMerger);
          if( rc==SQLITE_OK ){
            rc = vdbeSorterAddToTree(pTask, nDepth, iSeq++, pRoot, pMerger);
          }
        }
      }

      if( rc==SQLITE_OK ){
        if( pMain==0 ){
          pMain = pRoot;
        }else{
          rc = vdbeIncrNew(pTask, pRoot, &pMain->aIter[iTask].pIncr);
        }
      }else{
        vdbeMergeEngineFree(pRoot);
      }
    }
  }

  if( rc!=SQLITE_OK ){
    vdbeMergeEngineFree(pMain);
    pMain = 0;
  }
  *ppOut = pMain;
  return rc;
}

/*
** Populate iterator *pIter so that it may be used to iterate through all 
** keys stored in all PMAs created by this sorter.
*/
static int vdbePmaReaderIncrInit(VdbeSorter *pSorter){
  int rc;                         /* Return code */
  SortSubtask *pTask0 = &pSorter->aTask[0];
  MergeEngine *pMain = 0;
  sqlite3 *db = pTask0->pSorter->db;

  int iTask;





  rc = vdbeSorterMergeTreeBuild(pSorter, &pMain);
































































  if( rc==SQLITE_OK ){
#if SQLITE_MAX_WORKER_THREADS
    if( pSorter->bUseThreads ){
      PmaReader *pIter;
      SortSubtask *pLast = &pSorter->aTask[pSorter->nTask-1];
      rc = vdbeSortAllocUnpacked(pLast);
      if( rc==SQLITE_OK ){
        pIter = (PmaReader*)sqlite3DbMallocZero(db, sizeof(PmaReader));
        pSorter->pReader = pIter;
      }
      if( rc==SQLITE_OK ){
        rc = vdbeIncrNew(pLast, pMain, &pIter->pIncr);

        if( rc==SQLITE_OK ){


          vdbeIncrSetThreads(pIter->pIncr, pSorter->bUseThreads);
          for(iTask=0; iTask<(pSorter->nTask-1); iTask++){
            IncrMerger *pIncr;
            if( (pIncr = pMain->aIter[iTask].pIncr) ){
              vdbeIncrSetThreads(pIncr, pSorter->bUseThreads);
              assert( pIncr->pTask!=pLast );
            }
          }
          if( pSorter->nTask>1 ){
            for(iTask=0; rc==SQLITE_OK && iTask<pSorter->nTask; iTask++){
              PmaReader *p = &pMain->aIter[iTask];
              assert( p->pIncr==0 || p->pIncr->pTask==&pSorter->aTask[iTask] );
              if( p->pIncr ){ rc = vdbeIncrBgInit2(p); }
            }
          }

        }
        pMain = 0;
      }
      if( rc==SQLITE_OK ){
        int eMode = (pSorter->nTask>1 ? INCRINIT2_ROOT : INCRINIT2_NORMAL);
        rc = vdbeIncrInit2(pIter, eMode);
      }
    }else
#endif
    {

      rc = vdbeIncrInitMerger(pTask0, pMain, INCRINIT2_NORMAL);
      pSorter->pMerger = pMain;
      pMain = 0;
    }
  }

  if( rc!=SQLITE_OK ){




    vdbeMergeEngineFree(pMain);
  }

  return rc;
}


/*
** Once the sorter has been populated by calls to sqlite3VdbeSorterWrite,
** this function is called to prepare for iterating through the records