SQLite

Check-in [99e34bdce4]
Login

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

Overview
Comment:Simplification and performance tweaks in vdbeSorterMerge().
Downloads: Tarball | ZIP archive
Timelines: family | ancestors | descendants | both | merge-sort
Files: files | file ages | folders
SHA1: 99e34bdce4ccca15b79159b03b96787e7a7ff85b
User & Date: drh 2011-09-03 16:42:38.728
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: 4c43e8b2d2 user: drh tags: trunk)
16:42
Simplification and performance tweaks in vdbeSorterMerge(). (Closed-Leaf check-in: 99e34bdce4 user: drh tags: merge-sort)
14:36
Reduce the number of VdbeRecordUnpack() calls made in vdbesort.c. (check-in: 666c2c3cff user: dan tags: merge-sort)
Changes
Unified Diff Ignore Whitespace Patch
Changes to src/vdbesort.c.
︙︙
486
487
488
489
490
491
492
493
494
495
496
497
498
499
500
501
502
503
504
505
506
507

508
509
510
511
512
513
514
515
516
517
518
519
520
521
522
523
524

525
526
527

528
529
530
531
532
533
534
535
536
537

  SorterRecord *p1,               /* First list to merge */
  SorterRecord *p2,               /* Second list to merge */
  SorterRecord **ppOut            /* OUT: Head of merged list */
){
  int rc = SQLITE_OK;
  SorterRecord *pFinal = 0;
  SorterRecord **pp = &pFinal;
  int bKey2InSpace = 0;           /* True if pCsr->aSpace contains key2 */

  while( p1 || p2 ){
    if( p1==0 ){
      *pp = p2;
      p2 = 0;
    }else if( p2==0 ){
      *pp = p1;
      p1 = 0;
    }else{
      int res;
      rc = vdbeSorterCompare(pCsr, 0, 
          p1->pVal, p1->nVal, (bKey2InSpace ? 0 : p2->pVal), p2->nVal, &res
      );
      if( rc!=SQLITE_OK ){

        vdbeSorterRecordFree(db, p1);
        vdbeSorterRecordFree(db, p2);
        vdbeSorterRecordFree(db, pFinal);
        pFinal = 0;
        break;
      }
      if( res<=0 ){
        *pp = p1;
        pp = &p1->pNext;
        p1 = p1->pNext;
        bKey2InSpace = 1;
      }else{
        *pp = p2;
        pp = &p2->pNext;
        p2 = p2->pNext;
        bKey2InSpace = 0;
      }

      *pp = 0;
    }
  }


  *ppOut = pFinal;
  return rc;
}

/*
** Sort the linked list of records headed at pCsr->pRecord. Return SQLITE_OK
** if successful, or an SQLite error code (i.e. SQLITE_NOMEM) if an error
** occurs.
*/








|

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


>


|








486
487
488
489
490
491
492
493
494
495







496
497


498
499
500
501
502
503
504
505
506
507
508
509
510
511
512
513
514


515
516
517
518
519
520
521
522
523
524
525
526
527
528
529

  SorterRecord *p1,               /* First list to merge */
  SorterRecord *p2,               /* Second list to merge */
  SorterRecord **ppOut            /* OUT: Head of merged list */
){
  int rc = SQLITE_OK;
  SorterRecord *pFinal = 0;
  SorterRecord **pp = &pFinal;
  void *pVal2 = p2 ? p2->pVal : 0;

  while( p1 && p2 ){







    int res;
    rc = vdbeSorterCompare(pCsr, 0, p1->pVal, p1->nVal, pVal2, p2->nVal, &res);


    if( rc!=SQLITE_OK ){
      *pp = 0;
      vdbeSorterRecordFree(db, p1);
      vdbeSorterRecordFree(db, p2);
      vdbeSorterRecordFree(db, pFinal);
      *ppOut = 0;
      return rc;
    }
    if( res<=0 ){
      *pp = p1;
      pp = &p1->pNext;
      p1 = p1->pNext;
      pVal2 = 0;
    }else{
      *pp = p2;
       pp = &p2->pNext;
      p2 = p2->pNext;


      if( p2==0 ) break;
      pVal2 = p2->pVal;
    }
  }
  *pp = p1 ? p1 : p2;

  *ppOut = pFinal;
  return SQLITE_OK;
}

/*
** Sort the linked list of records headed at pCsr->pRecord. Return SQLITE_OK
** if successful, or an SQLite error code (i.e. SQLITE_NOMEM) if an error
** occurs.
*/
︙︙