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 |
Timelines: | family | ancestors | descendants | both | merge-sort |
Files: | files | file ages | folders |
SHA1: |
065b0c9858da0ebb41722f3c56bdaf62 |
User & Date: | dan 2011-09-02 15:41:33.781 |
Context
2011-09-02
| ||
18:03 | Combine two malloc calls in vdbesort.c. (check-in: cf48ad8353 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: 065b0c9858 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: 71075673c6 user: dan tags: merge-sort) | |
Changes
Changes to src/vdbesort.c.
︙ | ︙ | |||
100 101 102 103 104 105 106 107 108 109 110 111 112 113 | 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 { | > > | 100 101 102 103 104 105 106 107 108 109 110 111 112 113 114 115 | 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 { |
︙ | ︙ | |||
299 300 301 302 303 304 305 | ** ** 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( | | > > > | > > > > > > > > > | > | | | 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 | ** ** 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. |
︙ | ︙ | |||
362 363 364 365 366 367 368 | if( p1->pFile==0 ){ iRes = i2; }else if( p2->pFile==0 ){ iRes = i1; }else{ int res; int rc = vdbeSorterCompare( | | | 377 378 379 380 381 382 383 384 385 386 387 388 389 390 391 | 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; } |
︙ | ︙ | |||
425 426 427 428 429 430 431 432 433 434 435 436 437 438 | } 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, | > | 440 441 442 443 444 445 446 447 448 449 450 451 452 453 454 | } 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, |
︙ | ︙ | |||
450 451 452 453 454 455 456 | /* ** 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 */ | | | | 466 467 468 469 470 471 472 473 474 475 476 477 478 479 480 481 482 483 484 485 486 487 488 489 490 491 492 493 494 495 496 497 498 499 | /* ** 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; 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; |
︙ | ︙ | |||
506 507 508 509 510 511 512 | */ static int vdbeSorterSort(sqlite3 *db, VdbeCursor *pCsr){ int rc = SQLITE_OK; int i; SorterRecord **aSlot; SorterRecord *p; VdbeSorter *pSorter = pCsr->pSorter; | < | | | | 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 | */ 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; } } |
︙ | ︙ | |||
909 910 911 912 913 914 915 | 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); | | | 924 925 926 927 928 929 930 931 932 933 934 935 936 | 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 */ |