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
Side-by-Side 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

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;
  int bKey2InSpace = 0;           /* True if pCsr->aSpace contains key2 */
  void *pVal2 = p2 ? p2->pVal : 0;

  while( p1 || p2 ){
  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, 
    int res;
    rc = vdbeSorterCompare(pCsr, 0, p1->pVal, p1->nVal, pVal2, p2->nVal, &res);
          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;
    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;
        bKey2InSpace = 0;
      }
      *pp = 0;
      if( p2==0 ) break;
      pVal2 = p2->pVal;
    }
  }
  *pp = p1 ? p1 : p2;

  *ppOut = pFinal;
  return rc;
  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.
*/
︙