/ Check-in [99e34bdc]
Login

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

Overview
Comment:Simplification and performance tweaks in vdbeSorterMerge().
Downloads: Tarball | ZIP archive | SQL archive
Timelines: family | ancestors | descendants | both | merge-sort
Files: files | file ages | folders
SHA1: 99e34bdce4ccca15b79159b03b96787e7a7ff85b
User & Date: drh 2011-09-03 16:42:38
Context
2011-09-03
17:07
Performance improvements to the external merge-sorter. Keep content on an in-memory linked lists rather than an ephemeral table prior to spilling to disk. Use the external merge-sorter to implement ORDER BY and GROUP BY in addition to CREATE INDEX. check-in: 4c43e8b2 user: drh tags: trunk
16:42
Simplification and performance tweaks in vdbeSorterMerge(). Closed-Leaf check-in: 99e34bdc user: drh tags: merge-sort
14:36
Reduce the number of VdbeRecordUnpack() calls made in vdbesort.c. check-in: 666c2c3c user: dan tags: merge-sort
Changes
Hide Diffs Side-by-Side Diffs Ignore Whitespace Patch

Changes to src/vdbesort.c.

   486    486     SorterRecord *p1,               /* First list to merge */
   487    487     SorterRecord *p2,               /* Second list to merge */
   488    488     SorterRecord **ppOut            /* OUT: Head of merged list */
   489    489   ){
   490    490     int rc = SQLITE_OK;
   491    491     SorterRecord *pFinal = 0;
   492    492     SorterRecord **pp = &pFinal;
   493         -  int bKey2InSpace = 0;           /* True if pCsr->aSpace contains key2 */
          493  +  void *pVal2 = p2 ? p2->pVal : 0;
   494    494   
   495         -  while( p1 || p2 ){
   496         -    if( p1==0 ){
   497         -      *pp = p2;
   498         -      p2 = 0;
   499         -    }else if( p2==0 ){
          495  +  while( p1 && p2 ){
          496  +    int res;
          497  +    rc = vdbeSorterCompare(pCsr, 0, p1->pVal, p1->nVal, pVal2, p2->nVal, &res);
          498  +    if( rc!=SQLITE_OK ){
          499  +      *pp = 0;
          500  +      vdbeSorterRecordFree(db, p1);
          501  +      vdbeSorterRecordFree(db, p2);
          502  +      vdbeSorterRecordFree(db, pFinal);
          503  +      *ppOut = 0;
          504  +      return rc;
          505  +    }
          506  +    if( res<=0 ){
   500    507         *pp = p1;
   501         -      p1 = 0;
          508  +      pp = &p1->pNext;
          509  +      p1 = p1->pNext;
          510  +      pVal2 = 0;
   502    511       }else{
   503         -      int res;
   504         -      rc = vdbeSorterCompare(pCsr, 0, 
   505         -          p1->pVal, p1->nVal, (bKey2InSpace ? 0 : p2->pVal), p2->nVal, &res
   506         -      );
   507         -      if( rc!=SQLITE_OK ){
   508         -        vdbeSorterRecordFree(db, p1);
   509         -        vdbeSorterRecordFree(db, p2);
   510         -        vdbeSorterRecordFree(db, pFinal);
   511         -        pFinal = 0;
   512         -        break;
   513         -      }
   514         -      if( res<=0 ){
   515         -        *pp = p1;
   516         -        pp = &p1->pNext;
   517         -        p1 = p1->pNext;
   518         -        bKey2InSpace = 1;
   519         -      }else{
   520         -        *pp = p2;
   521         -        pp = &p2->pNext;
   522         -        p2 = p2->pNext;
   523         -        bKey2InSpace = 0;
   524         -      }
   525         -      *pp = 0;
          512  +      *pp = p2;
          513  +       pp = &p2->pNext;
          514  +      p2 = p2->pNext;
          515  +      if( p2==0 ) break;
          516  +      pVal2 = p2->pVal;
   526    517       }
   527    518     }
          519  +  *pp = p1 ? p1 : p2;
   528    520   
   529    521     *ppOut = pFinal;
   530         -  return rc;
          522  +  return SQLITE_OK;
   531    523   }
   532    524   
   533    525   /*
   534    526   ** Sort the linked list of records headed at pCsr->pRecord. Return SQLITE_OK
   535    527   ** if successful, or an SQLite error code (i.e. SQLITE_NOMEM) if an error
   536    528   ** occurs.
   537    529   */