/ Check-in [065b0c98]
Login

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

Overview
Comment:Reduce the number of malloc() calls made when creating an index on more than 2 columns.
Downloads: Tarball | ZIP archive | SQL archive
Timelines: family | ancestors | descendants | both | merge-sort
Files: files | file ages | folders
SHA1:065b0c9858da0ebb41722f3c56bdaf62f28b2f2c
User & Date: dan 2011-09-02 15:41:33
Context
2011-09-02
18:03
Combine two malloc calls in vdbesort.c. check-in: cf48ad83 user: dan tags: merge-sort
15:41
Reduce the number of malloc() calls made when creating an index on more than 2 columns. check-in: 065b0c98 user: dan tags: merge-sort
11:45
If all data being sorted fits in memory, avoid writing any data out to temporary files in vdbesort.c. check-in: 71075673 user: dan tags: merge-sort
Changes
Hide Diffs Unified Diffs Ignore Whitespace Patch

Changes to src/vdbesort.c.

100
101
102
103
104
105
106


107
108
109
110
111
112
113
...
299
300
301
302
303
304
305
306
307
308
309
310
311
312



313
314
315
316


317








318
319
320
321
322
323
324
...
325
326
327
328
329
330
331
332
333
334
335
336
337
338
339
...
362
363
364
365
366
367
368
369
370
371
372
373
374
375
376
...
425
426
427
428
429
430
431

432
433
434
435
436
437
438
...
450
451
452
453
454
455
456
457
458
459
460
461
462
463
464
...
469
470
471
472
473
474
475
476
477
478
479
480
481
482
483
...
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
538
539
540
541
542
543
544
545
546
547
548
549
550
551
552
553
554
555
556
557
558
559
560
...
909
910
911
912
913
914
915
916
917
918
919
920
921
  i64 iWriteOff;                  /* Current write offset within file pTemp1 */
  i64 iReadOff;                   /* Current read offset within file pTemp1 */
  sqlite3_file *pTemp1;           /* PMA file 1 */
  int nPMA;                       /* Number of PMAs stored in pTemp1 */
  SorterRecord *pRecord;          /* Head of in-memory record list */
  int nLimit1;                    /* Minimum PMA size, in bytes */
  int nLimit2;                    /* Maximum PMA size, in bytes */


};

/*
** The following type is an iterator for a PMA. It caches the current key in 
** variables nKey/aKey. If the iterator is at EOF, pFile==0.
*/
struct VdbeSorterIter {
................................................................................
**
** 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(
  KeyInfo *pKeyInfo,              /* Collation functions to use in comparison */
  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 */
){
  char aSpace[150];



  UnpackedRecord *r2;
  int i;

  r2 = sqlite3VdbeRecordUnpack(pKeyInfo, nKey2, pKey2, aSpace, sizeof(aSpace));


  if( r2==0 ) return SQLITE_NOMEM;








  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.
................................................................................
  if( p1->pFile==0 ){
    iRes = i2;
  }else if( p2->pFile==0 ){
    iRes = i1;
  }else{
    int res;
    int rc = vdbeSorterCompare(
        pCsr->pKeyInfo, 0, p1->aKey, p1->nKey, p2->aKey, p2->nKey, &res
    );
    if( rc!=SQLITE_OK ) return rc;
    if( res<=0 ){
      iRes = i1;
    }else{
      iRes = i2;
    }
................................................................................
      }
      sqlite3DbFree(db, pSorter->aIter);
    }
    if( pSorter->pTemp1 ){
      sqlite3OsCloseFree(pSorter->pTemp1);
    }
    vdbeSorterRecordFree(db, pSorter->pRecord);

    sqlite3DbFree(db, pSorter);
    pCsr->pSorter = 0;
  }
}

/*
** Allocate space for a file-handle and open a temporary file. If successful,
................................................................................

/*
** Attemp to merge the two sorted lists p1 and p2 into a single list. If no
** error occurs set *ppOut to the head of the new list and return SQLITE_OK.
*/
static int vdbeSorterMerge(
  sqlite3 *db,                    /* Database handle */
  KeyInfo *pKeyInfo,              /* Collation functions to use in comparison */
  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;
................................................................................
      p2 = 0;
    }else if( p2==0 ){
      *pp = p1;
      p1 = 0;
    }else{
      int res;
      rc = vdbeSorterCompare(
          pKeyInfo, 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;
................................................................................
*/
static int vdbeSorterSort(sqlite3 *db, VdbeCursor *pCsr){
  int rc = SQLITE_OK;
  int i;
  SorterRecord **aSlot;
  SorterRecord *p;
  VdbeSorter *pSorter = pCsr->pSorter;
  KeyInfo *pKeyInfo = pCsr->pKeyInfo;

  aSlot = (SorterRecord **)sqlite3MallocZero(64 * sizeof(SorterRecord *));
  if( !aSlot ){
    return SQLITE_NOMEM;
  }

  p = pSorter->pRecord;
  while( p ){
    SorterRecord *pNext = p->pNext;
    p->pNext = 0;
    for(i=0; rc==SQLITE_OK && aSlot[i]; i++){
      rc = vdbeSorterMerge(db, pKeyInfo, p, aSlot[i], &p);
      aSlot[i] = 0;
    }
    if( rc!=SQLITE_OK ){
      vdbeSorterRecordFree(db, pNext);
      break;
    }
    aSlot[i] = p;
    p = pNext;
  }

  p = 0;
  for(i=0; i<64; i++){
    if( rc==SQLITE_OK ){
      rc = vdbeSorterMerge(db, pKeyInfo, p, aSlot[i], &p);
    }else{
      vdbeSorterRecordFree(db, aSlot[i]);
    }
  }
  pSorter->pRecord = p;

#if 0
  {
    SorterRecord *pTmp1 = 0;
    SorterRecord *pTmp2;
    for(pTmp2=pSorter->pRecord; pTmp2 && rc==SQLITE_OK; pTmp2=pTmp2->pNext){
      if( pTmp1 ){
        int res;
        rc = vdbeSorterCompare(pKeyInfo, 
            0, pTmp1->pVal, pTmp1->nVal, pTmp2->pVal, pTmp2->nVal, &res
        );
        assert( rc!=SQLITE_OK || res<0 );
      }
      pTmp1 = pTmp2;
    }
  }
................................................................................
  int *pRes                       /* OUT: Result of comparison */
){
  int rc;
  VdbeSorter *pSorter = pCsr->pSorter;
  void *pKey; int nKey;           /* Sorter key to compare pVal with */

  pKey = vdbeSorterRowkey(pSorter, &nKey);
  rc = vdbeSorterCompare(pCsr->pKeyInfo, 1, pVal->z, pVal->n, pKey, nKey, pRes);
  assert( rc!=SQLITE_OK || *pRes<=0 );
  return rc;
}

#endif /* #ifndef SQLITE_OMIT_MERGE_SORT */







>
>







 







|





|
>
>
>



|
>
>
|
>
>
>
>
>
>
>
>







 







|







 







|







 







>







 







|







 







|







 







<











|













|













|







 







|





100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
...
301
302
303
304
305
306
307
308
309
310
311
312
313
314
315
316
317
318
319
320
321
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
...
377
378
379
380
381
382
383
384
385
386
387
388
389
390
391
...
440
441
442
443
444
445
446
447
448
449
450
451
452
453
454
...
466
467
468
469
470
471
472
473
474
475
476
477
478
479
480
...
485
486
487
488
489
490
491
492
493
494
495
496
497
498
499
...
522
523
524
525
526
527
528

529
530
531
532
533
534
535
536
537
538
539
540
541
542
543
544
545
546
547
548
549
550
551
552
553
554
555
556
557
558
559
560
561
562
563
564
565
566
567
568
569
570
571
572
573
574
575
...
924
925
926
927
928
929
930
931
932
933
934
935
936
  i64 iWriteOff;                  /* Current write offset within file pTemp1 */
  i64 iReadOff;                   /* Current read offset within file pTemp1 */
  sqlite3_file *pTemp1;           /* PMA file 1 */
  int nPMA;                       /* Number of PMAs stored in pTemp1 */
  SorterRecord *pRecord;          /* Head of in-memory record list */
  int nLimit1;                    /* Minimum PMA size, in bytes */
  int nLimit2;                    /* Maximum PMA size, in bytes */
  char *aSpace;                   /* Space for UnpackRecord() */
  int nSpace;                     /* Size of aSpace in bytes */
};

/*
** The following type is an iterator for a PMA. It caches the current key in 
** variables nKey/aKey. If the iterator is at EOF, pFile==0.
*/
struct VdbeSorterIter {
................................................................................
**
** 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 */
){
  KeyInfo *pKeyInfo = pCsr->pKeyInfo;
  VdbeSorter *pSorter = pCsr->pSorter;
  char *aSpace = pSorter->aSpace;
  int nSpace = pSorter->nSpace;
  UnpackedRecord *r2;
  int i;

  if( aSpace==0 ){
    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.
................................................................................
  if( p1->pFile==0 ){
    iRes = i2;
  }else if( p2->pFile==0 ){
    iRes = i1;
  }else{
    int res;
    int rc = vdbeSorterCompare(
        pCsr, 0, p1->aKey, p1->nKey, p2->aKey, p2->nKey, &res
    );
    if( rc!=SQLITE_OK ) return rc;
    if( res<=0 ){
      iRes = i1;
    }else{
      iRes = i2;
    }
................................................................................
      }
      sqlite3DbFree(db, pSorter->aIter);
    }
    if( pSorter->pTemp1 ){
      sqlite3OsCloseFree(pSorter->pTemp1);
    }
    vdbeSorterRecordFree(db, pSorter->pRecord);
    sqlite3_free(pSorter->aSpace);
    sqlite3DbFree(db, pSorter);
    pCsr->pSorter = 0;
  }
}

/*
** Allocate space for a file-handle and open a temporary file. If successful,
................................................................................

/*
** Attemp to merge the two sorted lists p1 and p2 into a single list. If no
** error occurs set *ppOut to the head of the new list and return SQLITE_OK.
*/
static int vdbeSorterMerge(
  sqlite3 *db,                    /* Database handle */
  VdbeCursor *pCsr,               /* For pKeyInfo */
  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;
................................................................................
      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;
................................................................................
*/
static int vdbeSorterSort(sqlite3 *db, VdbeCursor *pCsr){
  int rc = SQLITE_OK;
  int i;
  SorterRecord **aSlot;
  SorterRecord *p;
  VdbeSorter *pSorter = pCsr->pSorter;


  aSlot = (SorterRecord **)sqlite3MallocZero(64 * sizeof(SorterRecord *));
  if( !aSlot ){
    return SQLITE_NOMEM;
  }

  p = pSorter->pRecord;
  while( p ){
    SorterRecord *pNext = p->pNext;
    p->pNext = 0;
    for(i=0; rc==SQLITE_OK && aSlot[i]; i++){
      rc = vdbeSorterMerge(db, pCsr, p, aSlot[i], &p);
      aSlot[i] = 0;
    }
    if( rc!=SQLITE_OK ){
      vdbeSorterRecordFree(db, pNext);
      break;
    }
    aSlot[i] = p;
    p = pNext;
  }

  p = 0;
  for(i=0; i<64; i++){
    if( rc==SQLITE_OK ){
      rc = vdbeSorterMerge(db, pCsr, p, aSlot[i], &p);
    }else{
      vdbeSorterRecordFree(db, aSlot[i]);
    }
  }
  pSorter->pRecord = p;

#if 0
  {
    SorterRecord *pTmp1 = 0;
    SorterRecord *pTmp2;
    for(pTmp2=pSorter->pRecord; pTmp2 && rc==SQLITE_OK; pTmp2=pTmp2->pNext){
      if( pTmp1 ){
        int res;
        rc = vdbeSorterCompare(pCsr, 
            0, pTmp1->pVal, pTmp1->nVal, pTmp2->pVal, pTmp2->nVal, &res
        );
        assert( rc!=SQLITE_OK || res<0 );
      }
      pTmp1 = pTmp2;
    }
  }
................................................................................
  int *pRes                       /* OUT: Result of comparison */
){
  int rc;
  VdbeSorter *pSorter = pCsr->pSorter;
  void *pKey; int nKey;           /* Sorter key to compare pVal with */

  pKey = vdbeSorterRowkey(pSorter, &nKey);
  rc = vdbeSorterCompare(pCsr, 1, pVal->z, pVal->n, pKey, nKey, pRes);
  assert( rc!=SQLITE_OK || *pRes<=0 );
  return rc;
}

#endif /* #ifndef SQLITE_OMIT_MERGE_SORT */