/ Check-in [81987c8c]
Login

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

Overview
Comment:Instead of allocating a single large buffer at the beginning of each sort operation, start with a small buffer and extend it using realloc() as required.
Downloads: Tarball | ZIP archive | SQL archive
Timelines: family | ancestors | descendants | both | orderby-planning
Files: files | file ages | folders
SHA1: 81987c8ceb64f051528a6ca42673821d9ab7c0ff
User & Date: dan 2014-03-27 19:25:02
Context
2014-03-28
18:35
Merge the latest changes from trunk. check-in: 3047a25f user: drh tags: orderby-planning
2014-03-27
19:25
Instead of allocating a single large buffer at the beginning of each sort operation, start with a small buffer and extend it using realloc() as required. check-in: 81987c8c user: dan tags: orderby-planning
17:23
Use xFetch() to access temporary files in vdbesort.c. Use a single large allocation instead of many small allocations when accumulating records in vdbesort.c. This is an interim commit - it allocates a buffer the size of the page-cache every time data is sorted. check-in: f4ac1bf2 user: dan tags: orderby-planning
Changes
Hide Diffs Side-by-Side Diffs Ignore Whitespace Patch

Changes to src/vdbesort.c.

   103    103     VdbeSorterIter *aIter;          /* Array of iterators to merge */
   104    104     int *aTree;                     /* Current state of incremental merge */
   105    105     sqlite3_file *pTemp1;           /* PMA file 1 */
   106    106     SorterRecord *pRecord;          /* Head of in-memory record list */
   107    107     UnpackedRecord *pUnpacked;      /* Used to unpack keys */
   108    108     u8* aMemory;                    /* Block to allocate records from */
   109    109     int iMemory;                    /* Offset of free space in aMemory */
          110  +  int nMemory;                    /* Current size of allocation at aMemory */
   110    111   };
   111    112   
   112    113   /*
   113    114   ** The following type is an iterator for a PMA. It caches the current key in 
   114    115   ** variables nKey/aKey. If the iterator is at EOF, pFile==0.
   115    116   */
   116    117   struct VdbeSorterIter {
................................................................................
   140    141     int iBufEnd;                    /* Last byte of buffer to write */
   141    142     i64 iWriteOff;                  /* Offset of start of buffer in file */
   142    143     sqlite3_file *pFile;            /* File to write to */
   143    144   };
   144    145   
   145    146   /*
   146    147   ** A structure to store a single record. All in-memory records are connected
   147         -** together into a linked list headed at VdbeSorter.pRecord using the 
   148         -** SorterRecord.pNext pointer.
          148  +** together into a linked list headed at VdbeSorter.pRecord.
          149  +**
          150  +** How the linked list is connected depends on how memory is being managed
          151  +** by this module. If using a separate allocation for each in-memory record
          152  +** (VdbeSorter.aMemory==0), then the list is always connected using the 
          153  +** SorterRecord.u.pNext pointers.
          154  +**
          155  +** Or, if using the single large allocation method (VdbeSorter.aMemory!=0),
          156  +** then while records are being accumulated the list is linked using the
          157  +** SorterRecord.u.iNext offset. This is because the aMemory[] array may
          158  +** be sqlite3Realloc()ed while records are being accumulated. Once the VM
          159  +** has finished passing records to the sorter, or when the in-memory buffer
          160  +** is full, the list is sorted. As part of the sorting process, it is
          161  +** converted to use the SorterRecord.u.pNext pointers. See function
          162  +** vdbeSorterSort() for details.
   149    163   */
   150    164   struct SorterRecord {
   151         -  void *pVal;
   152    165     int nVal;
   153         -  SorterRecord *pNext;
          166  +  union {
          167  +    SorterRecord *pNext;          /* Pointer to next record in list */
          168  +    int iNext;                    /* Offset within aMemory of next record */
          169  +  } u;
   154    170   };
          171  +
          172  +/* Return a pointer to the buffer containing the record data for SorterRecord
          173  +** object p. Should be used as if:
          174  +**
          175  +**   void *SRVAL(SorterRecord *p) { return (void*)&p[1]; }
          176  +*/
          177  +#define SRVAL(p) ((void*)((SorterRecord*)(p) + 1))
   155    178   
   156    179   /* Minimum allowable value for the VdbeSorter.nWorking variable */
   157    180   #define SORTER_MIN_WORKING 10
   158    181   
   159    182   /* Maximum number of segments to merge in a single pass. */
   160    183   #define SORTER_MAX_MERGE_COUNT 16
   161    184   
................................................................................
   509    532     if( !sqlite3TempInMemory(db) ){
   510    533       pgsz = sqlite3BtreeGetPageSize(db->aDb[0].pBt);
   511    534       pSorter->mnPmaSize = SORTER_MIN_WORKING * pgsz;
   512    535       mxCache = db->aDb[0].pSchema->cache_size;
   513    536       if( mxCache<SORTER_MIN_WORKING ) mxCache = SORTER_MIN_WORKING;
   514    537       pSorter->mxPmaSize = mxCache * pgsz;
   515    538   
   516         -    pSorter->aMemory = (u8*)sqlite3DbMallocRaw(db, pSorter->mxPmaSize);
   517         -    assert( pSorter->iMemory==0 );
   518         -    if( !pSorter->aMemory ) return SQLITE_NOMEM;
          539  +    /* If the application is using memsys3 or memsys5, use a separate 
          540  +    ** allocation for each sort-key in memory. Otherwise, use a single big
          541  +    ** allocation at pSorter->aMemory for all sort-keys.  */
          542  +    if( sqlite3GlobalConfig.pHeap==0 ){
          543  +      assert( pSorter->iMemory==0 );
          544  +      pSorter->nMemory = pgsz;
          545  +      pSorter->aMemory = (u8*)sqlite3Malloc(pSorter->nMemory);
          546  +      if( !pSorter->aMemory ) return SQLITE_NOMEM;
          547  +    }
   519    548     }
   520    549   
   521    550     return SQLITE_OK;
   522    551   }
   523    552   
   524    553   /*
   525    554   ** Free the list of sorted records starting at pRecord.
   526    555   */
   527    556   static void vdbeSorterRecordFree(sqlite3 *db, SorterRecord *pRecord){
   528    557     SorterRecord *p;
   529    558     SorterRecord *pNext;
   530    559     for(p=pRecord; p; p=pNext){
   531         -    pNext = p->pNext;
          560  +    pNext = p->u.pNext;
   532    561       sqlite3DbFree(db, p);
   533    562     }
   534    563   }
   535    564   
   536    565   /*
   537    566   ** Reset a sorting cursor back to its original empty state.
   538    567   */
................................................................................
   607    636     const VdbeCursor *pCsr,         /* For pKeyInfo */
   608    637     SorterRecord *p1,               /* First list to merge */
   609    638     SorterRecord *p2,               /* Second list to merge */
   610    639     SorterRecord **ppOut            /* OUT: Head of merged list */
   611    640   ){
   612    641     SorterRecord *pFinal = 0;
   613    642     SorterRecord **pp = &pFinal;
   614         -  void *pVal2 = p2 ? p2->pVal : 0;
          643  +  void *pVal2 = p2 ? SRVAL(p2) : 0;
   615    644   
   616    645     while( p1 && p2 ){
   617    646       int res;
   618         -    vdbeSorterCompare(pCsr, 0, p1->pVal, p1->nVal, pVal2, p2->nVal, &res);
          647  +    vdbeSorterCompare(pCsr, 0, SRVAL(p1), p1->nVal, pVal2, p2->nVal, &res);
   619    648       if( res<=0 ){
   620    649         *pp = p1;
   621         -      pp = &p1->pNext;
   622         -      p1 = p1->pNext;
          650  +      pp = &p1->u.pNext;
          651  +      p1 = p1->u.pNext;
   623    652         pVal2 = 0;
   624    653       }else{
   625    654         *pp = p2;
   626         -       pp = &p2->pNext;
   627         -      p2 = p2->pNext;
          655  +       pp = &p2->u.pNext;
          656  +      p2 = p2->u.pNext;
   628    657         if( p2==0 ) break;
   629         -      pVal2 = p2->pVal;
          658  +      pVal2 = SRVAL(p2);
   630    659       }
   631    660     }
   632    661     *pp = p1 ? p1 : p2;
   633    662     *ppOut = pFinal;
   634    663   }
   635    664   
   636    665   /*
................................................................................
   652    681     aSlot = (SorterRecord **)sqlite3MallocZero(64 * sizeof(SorterRecord *));
   653    682     if( !aSlot ){
   654    683       return SQLITE_NOMEM;
   655    684     }
   656    685   
   657    686     p = pSorter->pRecord;
   658    687     while( p ){
   659         -    SorterRecord *pNext = p->pNext;
   660         -    p->pNext = 0;
          688  +    SorterRecord *pNext;
          689  +    if( pSorter->aMemory ){
          690  +      assert( p->u.iNext<pSorter->nMemory );
          691  +      if( (u8*)p==pSorter->aMemory ){
          692  +        pNext = 0;
          693  +      }else{
          694  +        pNext = (SorterRecord*)&pSorter->aMemory[p->u.iNext];
          695  +      }
          696  +    }else{
          697  +      pNext = p->u.pNext;
          698  +    }
          699  +    p->u.pNext = 0;
   661    700       for(i=0; aSlot[i]; i++){
   662    701         vdbeSorterMerge(pCsr, p, aSlot[i], &p);
   663    702         aSlot[i] = 0;
   664    703       }
   665    704       aSlot[i] = p;
   666    705       p = pNext;
   667    706     }
................................................................................
   831    870       SorterRecord *p;
   832    871       SorterRecord *pNext = 0;
   833    872   
   834    873       fileWriterInit(db, pSorter->pTemp1, &writer, pSorter->iWriteOff);
   835    874       pSorter->nPMA++;
   836    875       fileWriterWriteVarint(&writer, pSorter->nInMemory);
   837    876       for(p=pSorter->pRecord; p; p=pNext){
   838         -      pNext = p->pNext;
          877  +      pNext = p->u.pNext;
   839    878         fileWriterWriteVarint(&writer, p->nVal);
   840         -      fileWriterWrite(&writer, p->pVal, p->nVal);
          879  +      fileWriterWrite(&writer, SRVAL(p), p->nVal);
   841    880         if( pSorter->aMemory==0 ) sqlite3DbFree(db, p);
   842    881       }
   843    882       pSorter->pRecord = p;
   844    883       rc = fileWriterFinish(db, &writer, &pSorter->iWriteOff);
   845    884     }
   846    885   
   847    886     if( pSorter->aMemory ) pSorter->pRecord = 0;
................................................................................
   854    893   */
   855    894   int sqlite3VdbeSorterWrite(
   856    895     sqlite3 *db,                    /* Database handle */
   857    896     const VdbeCursor *pCsr,               /* Sorter cursor */
   858    897     Mem *pVal                       /* Memory cell containing record */
   859    898   ){
   860    899     VdbeSorter *pSorter = pCsr->pSorter;
   861         -  SorterRecord sRecord;           /* Used for aMemory overflow record */
   862    900     int rc = SQLITE_OK;             /* Return Code */
   863    901     SorterRecord *pNew;             /* New list element */
   864    902   
          903  +  int bFlush;                     /* True to flush contents of memory to PMA */
          904  +  int nReq;                       /* Bytes of memory required */
          905  +  int nPMA;                       /* Bytes of PMA space required */
          906  +
   865    907     assert( pSorter );
   866         -  pSorter->nInMemory += sqlite3VarintLen(pVal->n) + pVal->n;
   867    908   
   868         -  if( pSorter->aMemory ){
   869         -    int nReq = sizeof(SorterRecord) + pVal->n;
   870         -    if( (pSorter->iMemory+nReq) > pSorter->mxPmaSize ){
   871         -      pNew = &sRecord;
   872         -      pNew->pVal = pVal->z;
   873         -    }else{
   874         -      pNew = &pSorter->aMemory[pSorter->iMemory];
   875         -      pSorter->iMemory += ROUND8(nReq);
   876         -    }
   877         -  }else{
   878         -    pNew = (SorterRecord *)sqlite3DbMallocRaw(db, pVal->n+sizeof(SorterRecord));
   879         -    if( pNew==0 ){
   880         -      return SQLITE_NOMEM;
   881         -    }
   882         -  }
   883         -
   884         -  if( pNew!=&sRecord ){
   885         -    pNew->pVal = (void*)&pNew[1];
   886         -    memcpy(pNew->pVal, pVal->z, pVal->n);
   887         -  }
   888         -  pNew->nVal = pVal->n;
   889         -  pNew->pNext = pSorter->pRecord;
   890         -  pSorter->pRecord = pNew;
   891         -
   892         -  /* See if the contents of the sorter should now be written out. They
   893         -  ** are written out when either of the following are true:
          909  +  /* Figure out whether or not the current contents of memory should be
          910  +  ** flushed to a PMA before continuing. If so, do so.
          911  +  **
          912  +  ** If using the single large allocation mode (pSorter->aMemory!=0), then
          913  +  ** flush the contents of memory to a new PMA if (a) at least one value is
          914  +  ** already in memory and (b) the new value will not fit in memory.
          915  +  ** 
          916  +  ** Or, if using separate allocations for each record, flush the contents
          917  +  ** of memory to a PMA if either of the following are true:
   894    918     **
   895    919     **   * The total memory allocated for the in-memory list is greater 
   896    920     **     than (page-size * cache-size), or
   897    921     **
   898    922     **   * The total memory allocated for the in-memory list is greater 
   899    923     **     than (page-size * 10) and sqlite3HeapNearlyFull() returns true.
   900    924     */
   901         -  if( pSorter->mxPmaSize>0 ){
   902         -    if( (pNew==&sRecord) || (pSorter->aMemory==0 && (
          925  +  nReq = pVal->n + sizeof(SorterRecord);
          926  +  nPMA = pVal->n + sqlite3VarintLen(pVal->n);
          927  +  if( pSorter->aMemory ){
          928  +    bFlush = pSorter->iMemory && (pSorter->iMemory+nReq) > pSorter->mxPmaSize;
          929  +  }else{
          930  +    bFlush = (
   903    931           (pSorter->nInMemory > pSorter->mxPmaSize)
   904    932        || (pSorter->nInMemory > pSorter->mnPmaSize && sqlite3HeapNearlyFull())
   905         -    ))){
          933  +    );
          934  +  }
          935  +  if( bFlush ){
   906    936   #ifdef SQLITE_DEBUG
   907         -      i64 nExpect = pSorter->iWriteOff
   908         -        + sqlite3VarintLen(pSorter->nInMemory)
   909         -        + pSorter->nInMemory;
          937  +    i64 nExpect = pSorter->iWriteOff
          938  +      + sqlite3VarintLen(pSorter->nInMemory)
          939  +      + pSorter->nInMemory;
   910    940   #endif
   911         -      rc = vdbeSorterListToPMA(db, pCsr);
   912         -      pSorter->nInMemory = 0;
   913         -      pSorter->iMemory = 0;
   914         -      assert( rc!=SQLITE_OK || (nExpect==pSorter->iWriteOff) );
   915         -      assert( rc!=SQLITE_OK || pSorter->pRecord==0 );
          941  +    rc = vdbeSorterListToPMA(db, pCsr);
          942  +    pSorter->nInMemory = 0;
          943  +    pSorter->iMemory = 0;
          944  +    assert( rc!=SQLITE_OK || (nExpect==pSorter->iWriteOff) );
          945  +    assert( rc!=SQLITE_OK || pSorter->pRecord==0 );
          946  +  }
          947  +
          948  +  pSorter->nInMemory += nPMA;
          949  +
          950  +  if( pSorter->aMemory ){
          951  +    int nMin = pSorter->iMemory + nReq;
          952  +
          953  +    if( nMin>pSorter->nMemory ){
          954  +      u8 *aNew;
          955  +      int nNew = pSorter->nMemory * 2;
          956  +      while( nNew < nMin ) nNew = nNew*2;
          957  +      if( nNew > pSorter->mxPmaSize ) nNew = pSorter->mxPmaSize;
          958  +      if( nNew < nMin ) nNew = nMin;
          959  +
          960  +      aNew = sqlite3Realloc(pSorter->aMemory, nNew);
          961  +      if( !aNew ) return SQLITE_NOMEM;
          962  +      pSorter->pRecord = aNew + ((u8*)pSorter->pRecord - pSorter->aMemory);
          963  +      pSorter->aMemory = aNew;
          964  +      pSorter->nMemory = nNew;
          965  +    }
          966  +
          967  +    pNew = (SorterRecord*)&pSorter->aMemory[pSorter->iMemory];
          968  +    pSorter->iMemory += ROUND8(nReq);
          969  +    pNew->u.iNext = (u8*)(pSorter->pRecord) - pSorter->aMemory;
          970  +  }else{
          971  +    pNew = (SorterRecord *)sqlite3DbMallocRaw(db, pVal->n+sizeof(SorterRecord));
          972  +    if( pNew==0 ){
          973  +      return SQLITE_NOMEM;
   916    974       }
          975  +    pNew->u.pNext = pSorter->pRecord;
   917    976     }
          977  +
          978  +  memcpy(SRVAL(pNew), pVal->z, pVal->n);
          979  +  pNew->nVal = pVal->n;
          980  +  pSorter->pRecord = pNew;
   918    981   
   919    982     return rc;
   920    983   }
   921    984   
   922    985   /*
   923    986   ** Helper function for sqlite3VdbeSorterRewind(). 
   924    987   */
................................................................................
  1123   1186             pIter1 = &pSorter->aIter[ pSorter->aTree[i ^ 0x0001] ];
  1124   1187           }
  1125   1188         }
  1126   1189         *pbEof = (pSorter->aIter[pSorter->aTree[1]].pFile==0);
  1127   1190       }
  1128   1191     }else{
  1129   1192       SorterRecord *pFree = pSorter->pRecord;
  1130         -    pSorter->pRecord = pFree->pNext;
  1131         -    pFree->pNext = 0;
         1193  +    pSorter->pRecord = pFree->u.pNext;
         1194  +    pFree->u.pNext = 0;
  1132   1195       if( pSorter->aMemory==0 ){
  1133   1196         vdbeSorterRecordFree(db, pFree);
  1134   1197       }
  1135   1198       *pbEof = !pSorter->pRecord;
  1136   1199       rc = SQLITE_OK;
  1137   1200     }
  1138   1201     return rc;
................................................................................
  1150   1213     if( pSorter->aTree ){
  1151   1214       VdbeSorterIter *pIter;
  1152   1215       pIter = &pSorter->aIter[ pSorter->aTree[1] ];
  1153   1216       *pnKey = pIter->nKey;
  1154   1217       pKey = pIter->aKey;
  1155   1218     }else{
  1156   1219       *pnKey = pSorter->pRecord->nVal;
  1157         -    pKey = pSorter->pRecord->pVal;
         1220  +    pKey = SRVAL(pSorter->pRecord);
  1158   1221     }
  1159   1222     return pKey;
  1160   1223   }
  1161   1224   
  1162   1225   /*
  1163   1226   ** Copy the current sorter key into the memory cell pOut.
  1164   1227   */