/ Check-in [666c2c3c]
Login
SQLite training in Houston TX on 2019-11-05 (details)
Part of the 2019 Tcl Conference

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

Overview
Comment:Reduce the number of VdbeRecordUnpack() calls made in vdbesort.c.
Downloads: Tarball | ZIP archive | SQL archive
Timelines: family | ancestors | descendants | both | merge-sort
Files: files | file ages | folders
SHA1: 666c2c3cff51dac2ba5689b75705d99c3705673b
User & Date: dan 2011-09-03 14:36:13
Context
2011-09-03
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
00:17
The build works again with -DSQLITE_OMIT_MERGE_SORT. The merge-sorter now avoids spilling to disk (letting the in-memory linked list grow without bound) if PRAGMA temp_store=3. check-in: 68e26c44 user: drh tags: merge-sort
Changes
Hide Diffs Unified Diffs Ignore Whitespace Patch

Changes to src/vdbesort.c.

299
300
301
302
303
304
305



306
307
308
309
310
311
312
...
322
323
324
325
326
327
328

329
330
331





332
333
334
335
336
337
338
339
340
341
342
343
344
345
346
347
348
349
350
351
352
353
354
...
479
480
481
482
483
484
485

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
** Otherwise, return SQLITE_OK and set *pRes to a negative, zero or positive
** value, depending on whether key1 is smaller, equal to or larger than key2.
**
** If the bOmitRowid argument is non-zero, assume both keys end in a rowid
** field. For the purposes of the comparison, ignore it. Also, if bOmitRowid
** is true and key1 contains even a single NULL value, it is considered to
** be less than key2. Even if key2 also contains NULL values.



*/
static int vdbeSorterCompare(
  VdbeCursor *pCsr,               /* Cursor object (for pKeyInfo) */
  int bOmitRowid,                 /* Ignore rowid field at end of keys */
  void *pKey1, int nKey1,         /* Left side of comparison */
  void *pKey2, int nKey2,         /* Right side of comparison */
  int *pRes                       /* OUT: Result of comparison */
................................................................................
    nSpace = ROUND8(sizeof(UnpackedRecord))+(pKeyInfo->nField+1)*sizeof(Mem);
    aSpace = (char *)sqlite3Malloc(nSpace);
    if( aSpace==0 ) return SQLITE_NOMEM;
    pSorter->aSpace = aSpace;
    pSorter->nSpace = nSpace;
  }


  /* This call cannot fail. As the memory is already allocated. */
  r2 = sqlite3VdbeRecordUnpack(pKeyInfo, nKey2, pKey2, aSpace, nSpace);
  assert( r2 && (r2->flags & UNPACKED_NEED_FREE)==0 );






  if( bOmitRowid ){
    for(i=0; i<r2->nField-1; i++){
      if( r2->aMem[i].flags & MEM_Null ){
        *pRes = -1;
        sqlite3VdbeDeleteUnpackedRecord(r2);
        return SQLITE_OK;
      }
    }
    r2->flags |= UNPACKED_PREFIX_MATCH;
    r2->nField--;
    assert( r2->nField>0 );
  }

  *pRes = sqlite3VdbeRecordCompare(nKey1, pKey1, r2);
  /* sqlite3VdbeDeleteUnpackedRecord(r2); */
  return SQLITE_OK;
}

/*
** This function is called to compare two iterator keys when merging 
** multiple b-tree segments. Parameter iOut is the index of the aTree[] 
** value to recalculate.
................................................................................
  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;


  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, 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;

      }else{
        *pp = p2;
        pp = &p2->pNext;
        p2 = p2->pNext;

      }
      *pp = 0;
    }
  }

  *ppOut = pFinal;
  return rc;







>
>
>







 







>
|
|
|
>
>
>
>
>





<









<







 







>










|
|












>




>







299
300
301
302
303
304
305
306
307
308
309
310
311
312
313
314
315
...
325
326
327
328
329
330
331
332
333
334
335
336
337
338
339
340
341
342
343
344
345

346
347
348
349
350
351
352
353
354

355
356
357
358
359
360
361
...
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
** Otherwise, return SQLITE_OK and set *pRes to a negative, zero or positive
** value, depending on whether key1 is smaller, equal to or larger than key2.
**
** If the bOmitRowid argument is non-zero, assume both keys end in a rowid
** field. For the purposes of the comparison, ignore it. Also, if bOmitRowid
** is true and key1 contains even a single NULL value, it is considered to
** be less than key2. Even if key2 also contains NULL values.
**
** If pKey2 is passed a NULL pointer, then it is assumed that the pCsr->aSpace
** has been allocated and contains an unpacked record that is used as key2.
*/
static int vdbeSorterCompare(
  VdbeCursor *pCsr,               /* Cursor object (for pKeyInfo) */
  int bOmitRowid,                 /* Ignore rowid field at end of keys */
  void *pKey1, int nKey1,         /* Left side of comparison */
  void *pKey2, int nKey2,         /* Right side of comparison */
  int *pRes                       /* OUT: Result of comparison */
................................................................................
    nSpace = ROUND8(sizeof(UnpackedRecord))+(pKeyInfo->nField+1)*sizeof(Mem);
    aSpace = (char *)sqlite3Malloc(nSpace);
    if( aSpace==0 ) return SQLITE_NOMEM;
    pSorter->aSpace = aSpace;
    pSorter->nSpace = nSpace;
  }

  if( pKey2 ){
    /* This call cannot fail. As the memory is already allocated. */
    r2 = sqlite3VdbeRecordUnpack(pKeyInfo, nKey2, pKey2, aSpace, nSpace);
    assert( r2 && (r2->flags & UNPACKED_NEED_FREE)==0 );
    assert( r2==aSpace );
  }else{
    r2 = (UnpackedRecord *)aSpace;
    assert( !bOmitRowid );
  }

  if( bOmitRowid ){
    for(i=0; i<r2->nField-1; i++){
      if( r2->aMem[i].flags & MEM_Null ){
        *pRes = -1;

        return SQLITE_OK;
      }
    }
    r2->flags |= UNPACKED_PREFIX_MATCH;
    r2->nField--;
    assert( r2->nField>0 );
  }

  *pRes = sqlite3VdbeRecordCompare(nKey1, pKey1, r2);

  return SQLITE_OK;
}

/*
** This function is called to compare two iterator keys when merging 
** multiple b-tree segments. Parameter iOut is the index of the aTree[] 
** value to recalculate.
................................................................................
  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;