/ 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 Unified Diffs Show Whitespace Changes 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.
*/