Many hyperlinks are disabled.
Use anonymous login
to enable hyperlinks.
Overview
Comment: | Merge latest changes from orderby-planning branch. |
---|---|
Downloads: | Tarball | ZIP archive |
Timelines: | family | ancestors | descendants | both | threads |
Files: | files | file ages | folders |
SHA1: |
4c7fb5423430f3b936befaa7c309f8e1 |
User & Date: | dan 2014-03-28 19:18:16.969 |
Context
2014-03-29
| ||
06:27 | Add the optimization to avoid some unnecessary calls to sqlite3VdbeRecordUnpack() added to the trunk by [707ea170b3]. (check-in: fc4d04e6b0 user: dan tags: threads) | |
2014-03-28
| ||
19:18 | Merge latest changes from orderby-planning branch. (check-in: 4c7fb54234 user: dan tags: threads) | |
18:35 | Merge the latest changes from trunk. (check-in: 3047a25f1c user: drh tags: orderby-planning) | |
2014-03-26
| ||
19:45 | Merge from trunk the fix for the crash on a corrupt database. (check-in: 8cb2b02baa user: drh tags: threads) | |
Changes
Changes to src/btree.c.
︙ | ︙ | |||
4584 4585 4586 4587 4588 4589 4590 4591 4592 4593 4594 4595 4596 4597 | *pRes = -1; return SQLITE_OK; } } if( pIdxKey ){ xRecordCompare = sqlite3VdbeFindCompare(pIdxKey); assert( pIdxKey->default_rc==1 || pIdxKey->default_rc==0 || pIdxKey->default_rc==-1 ); }else{ xRecordCompare = 0; /* All keys are integers */ } | > | 4584 4585 4586 4587 4588 4589 4590 4591 4592 4593 4594 4595 4596 4597 4598 | *pRes = -1; return SQLITE_OK; } } if( pIdxKey ){ xRecordCompare = sqlite3VdbeFindCompare(pIdxKey); pIdxKey->isCorrupt = 0; assert( pIdxKey->default_rc==1 || pIdxKey->default_rc==0 || pIdxKey->default_rc==-1 ); }else{ xRecordCompare = 0; /* All keys are integers */ } |
︙ | ︙ | |||
4707 4708 4709 4710 4711 4712 4713 4714 4715 4716 4717 4718 4719 4720 4721 4722 4723 4724 4725 4726 4727 4728 4729 | if( rc ){ sqlite3_free(pCellKey); goto moveto_finish; } c = xRecordCompare(nCell, pCellKey, pIdxKey, 0); sqlite3_free(pCellKey); } if( c<0 ){ lwr = idx+1; }else if( c>0 ){ upr = idx-1; }else{ assert( c==0 ); *pRes = 0; rc = SQLITE_OK; pCur->aiIdx[pCur->iPage] = (u16)idx; goto moveto_finish; } if( lwr>upr ) break; assert( lwr+upr>=0 ); idx = (lwr+upr)>>1; /* idx = (lwr+upr)/2 */ } } | > > | 4708 4709 4710 4711 4712 4713 4714 4715 4716 4717 4718 4719 4720 4721 4722 4723 4724 4725 4726 4727 4728 4729 4730 4731 4732 | if( rc ){ sqlite3_free(pCellKey); goto moveto_finish; } c = xRecordCompare(nCell, pCellKey, pIdxKey, 0); sqlite3_free(pCellKey); } assert( pIdxKey->isCorrupt==0 || c==0 ); if( c<0 ){ lwr = idx+1; }else if( c>0 ){ upr = idx-1; }else{ assert( c==0 ); *pRes = 0; rc = SQLITE_OK; pCur->aiIdx[pCur->iPage] = (u16)idx; if( pIdxKey->isCorrupt ) rc = SQLITE_CORRUPT; goto moveto_finish; } if( lwr>upr ) break; assert( lwr+upr>=0 ); idx = (lwr+upr)>>1; /* idx = (lwr+upr)/2 */ } } |
︙ | ︙ |
Changes to src/select.c.
︙ | ︙ | |||
451 452 453 454 455 456 457 | Parse *pParse, /* Parsing context */ ExprList *pList, /* Form the KeyInfo object from this ExprList */ int iStart, /* Begin with this column of pList */ int nExtra /* Add this many extra columns to the end */ ); /* | | | | > > | > | > | | | | | > > > > > > > | > | > > | > > | | > | > > > > | 451 452 453 454 455 456 457 458 459 460 461 462 463 464 465 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 500 501 502 503 504 505 506 507 508 509 510 511 512 513 514 515 516 517 | Parse *pParse, /* Parsing context */ ExprList *pList, /* Form the KeyInfo object from this ExprList */ int iStart, /* Begin with this column of pList */ int nExtra /* Add this many extra columns to the end */ ); /* ** Generate code that will push the record in registers regData ** through regData+nData-1 onto the sorter. */ static void pushOntoSorter( Parse *pParse, /* Parser context */ SortCtx *pSort, /* Information about the ORDER BY clause */ Select *pSelect, /* The whole SELECT statement */ int regData, /* First register holding data to be sorted */ int nData, /* Number of elements in the data array */ int nPrefixReg /* No. of reg prior to regData available for use */ ){ Vdbe *v = pParse->pVdbe; /* Stmt under construction */ int bSeq = ((pSort->sortFlags & SORTFLAG_UseSorter)==0); int nExpr = pSort->pOrderBy->nExpr; /* No. of ORDER BY terms */ int nBase = nExpr + bSeq + nData; /* Fields in sorter record */ int regBase; /* Regs for sorter record */ int regRecord = sqlite3GetTempReg(pParse); /* Assembled sorter record */ int nOBSat = pSort->nOBSat; /* ORDER BY terms to skip */ int op; /* Opcode to add sorter record to sorter */ assert( bSeq==0 || bSeq==1 ); if( nPrefixReg ){ assert( nPrefixReg==nExpr+bSeq ); regBase = regData - nExpr - bSeq; }else{ regBase = sqlite3GetTempRange(pParse, nBase); } sqlite3ExprCodeExprList(pParse, pSort->pOrderBy, regBase, SQLITE_ECEL_DUP); if( bSeq ){ sqlite3VdbeAddOp2(v, OP_Sequence, pSort->iECursor, regBase+nExpr); } if( nPrefixReg==0 ){ sqlite3VdbeAddOp3(v, OP_Move, regData, regBase+nExpr+bSeq, nData); } sqlite3VdbeAddOp3(v, OP_MakeRecord, regBase+nOBSat, nBase-nOBSat, regRecord); if( nOBSat>0 ){ int regPrevKey; /* The first nOBSat columns of the previous row */ int addrFirst; /* Address of the OP_IfNot opcode */ int addrJmp; /* Address of the OP_Jump opcode */ VdbeOp *pOp; /* Opcode that opens the sorter */ int nKey; /* Number of sorting key columns, including OP_Sequence */ KeyInfo *pKI; /* Original KeyInfo on the sorter table */ regPrevKey = pParse->nMem+1; pParse->nMem += pSort->nOBSat; nKey = nExpr - pSort->nOBSat + bSeq; if( bSeq ){ addrFirst = sqlite3VdbeAddOp1(v, OP_IfNot, regBase+nExpr); }else{ addrFirst = sqlite3VdbeAddOp1(v, OP_SequenceTest, pSort->iECursor); } VdbeCoverage(v); sqlite3VdbeAddOp3(v, OP_Compare, regPrevKey, regBase, pSort->nOBSat); pOp = sqlite3VdbeGetOp(v, pSort->addrSortIndex); if( pParse->db->mallocFailed ) return; pOp->p2 = nKey + 1; pKI = pOp->p4.pKeyInfo; memset(pKI->aSortOrder, 0, pKI->nField); /* Makes OP_Jump below testable */ sqlite3VdbeChangeP4(v, -1, (char*)pKI, P4_KEYINFO); |
︙ | ︙ | |||
509 510 511 512 513 514 515 | op = OP_SorterInsert; }else{ op = OP_IdxInsert; } sqlite3VdbeAddOp2(v, op, pSort->iECursor, regRecord); if( nOBSat==0 ){ sqlite3ReleaseTempReg(pParse, regRecord); | > | > | 530 531 532 533 534 535 536 537 538 539 540 541 542 543 544 545 546 | op = OP_SorterInsert; }else{ op = OP_IdxInsert; } sqlite3VdbeAddOp2(v, op, pSort->iECursor, regRecord); if( nOBSat==0 ){ sqlite3ReleaseTempReg(pParse, regRecord); if( nPrefixReg==0 ){ sqlite3ReleaseTempRange(pParse, regBase, nBase); } } if( pSelect->iLimit ){ int addr1, addr2; int iLimit; if( pSelect->iOffset ){ iLimit = pSelect->iOffset+1; }else{ |
︙ | ︙ | |||
625 626 627 628 629 630 631 632 633 634 635 636 637 638 639 640 641 642 643 644 645 646 647 648 649 650 651 652 653 | Vdbe *v = pParse->pVdbe; int i; int hasDistinct; /* True if the DISTINCT keyword is present */ int regResult; /* Start of memory holding result set */ int eDest = pDest->eDest; /* How to dispose of results */ int iParm = pDest->iSDParm; /* First argument to disposal method */ int nResultCol; /* Number of result columns */ assert( v ); assert( pEList!=0 ); hasDistinct = pDistinct ? pDistinct->eTnctType : WHERE_DISTINCT_NOOP; if( pSort && pSort->pOrderBy==0 ) pSort = 0; if( pSort==0 && !hasDistinct ){ assert( iContinue!=0 ); codeOffset(v, p->iOffset, iContinue); } /* Pull the requested columns. */ nResultCol = pEList->nExpr; if( pDest->iSdst==0 ){ pDest->iSdst = pParse->nMem+1; pParse->nMem += nResultCol; }else if( pDest->iSdst+nResultCol > pParse->nMem ){ /* This is an error condition that can result, for example, when a SELECT ** on the right-hand side of an INSERT contains more result columns than ** there are columns in the table on the left. The error will be caught ** and reported later. But we need to make sure enough memory is allocated | > > > > > > | 648 649 650 651 652 653 654 655 656 657 658 659 660 661 662 663 664 665 666 667 668 669 670 671 672 673 674 675 676 677 678 679 680 681 682 | Vdbe *v = pParse->pVdbe; int i; int hasDistinct; /* True if the DISTINCT keyword is present */ int regResult; /* Start of memory holding result set */ int eDest = pDest->eDest; /* How to dispose of results */ int iParm = pDest->iSDParm; /* First argument to disposal method */ int nResultCol; /* Number of result columns */ int nPrefixReg = 0; /* Number of extra registers before regResult */ assert( v ); assert( pEList!=0 ); hasDistinct = pDistinct ? pDistinct->eTnctType : WHERE_DISTINCT_NOOP; if( pSort && pSort->pOrderBy==0 ) pSort = 0; if( pSort==0 && !hasDistinct ){ assert( iContinue!=0 ); codeOffset(v, p->iOffset, iContinue); } /* Pull the requested columns. */ nResultCol = pEList->nExpr; if( pDest->iSdst==0 ){ if( pSort ){ nPrefixReg = pSort->pOrderBy->nExpr; if( !(pSort->sortFlags & SORTFLAG_UseSorter) ) nPrefixReg++; pParse->nMem += nPrefixReg; } pDest->iSdst = pParse->nMem+1; pParse->nMem += nResultCol; }else if( pDest->iSdst+nResultCol > pParse->nMem ){ /* This is an error condition that can result, for example, when a SELECT ** on the right-hand side of an INSERT contains more result columns than ** there are columns in the table on the left. The error will be caught ** and reported later. But we need to make sure enough memory is allocated |
︙ | ︙ | |||
756 757 758 759 760 761 762 | /* Store the result as data using a unique key. */ case SRT_Fifo: case SRT_DistFifo: case SRT_Table: case SRT_EphemTab: { | | | | | | | 785 786 787 788 789 790 791 792 793 794 795 796 797 798 799 800 801 802 803 804 805 806 807 808 809 810 811 812 813 814 815 816 817 818 819 820 821 822 823 824 825 826 827 828 829 830 831 832 833 834 835 836 837 838 839 840 841 842 843 | /* Store the result as data using a unique key. */ case SRT_Fifo: case SRT_DistFifo: case SRT_Table: case SRT_EphemTab: { int r1 = sqlite3GetTempRange(pParse, nPrefixReg+1); testcase( eDest==SRT_Table ); testcase( eDest==SRT_EphemTab ); sqlite3VdbeAddOp3(v, OP_MakeRecord, regResult, nResultCol, r1+nPrefixReg); #ifndef SQLITE_OMIT_CTE if( eDest==SRT_DistFifo ){ /* If the destination is DistFifo, then cursor (iParm+1) is open ** on an ephemeral index. If the current row is already present ** in the index, do not write it to the output. If not, add the ** current row to the index and proceed with writing it to the ** output table as well. */ int addr = sqlite3VdbeCurrentAddr(v) + 4; sqlite3VdbeAddOp4Int(v, OP_Found, iParm+1, addr, r1, 0); VdbeCoverage(v); sqlite3VdbeAddOp2(v, OP_IdxInsert, iParm+1, r1); assert( pSort==0 ); } #endif if( pSort ){ pushOntoSorter(pParse, pSort, p, r1+nPrefixReg, 1, nPrefixReg); }else{ int r2 = sqlite3GetTempReg(pParse); sqlite3VdbeAddOp2(v, OP_NewRowid, iParm, r2); sqlite3VdbeAddOp3(v, OP_Insert, iParm, r1, r2); sqlite3VdbeChangeP5(v, OPFLAG_APPEND); sqlite3ReleaseTempReg(pParse, r2); } sqlite3ReleaseTempRange(pParse, r1, nPrefixReg+1); break; } #ifndef SQLITE_OMIT_SUBQUERY /* If we are creating a set for an "expr IN (SELECT ...)" construct, ** then there should be a single item on the stack. Write this ** item into the set table with bogus data. */ case SRT_Set: { assert( nResultCol==1 ); pDest->affSdst = sqlite3CompareAffinity(pEList->a[0].pExpr, pDest->affSdst); if( pSort ){ /* At first glance you would think we could optimize out the ** ORDER BY in this case since the order of entries in the set ** does not matter. But there might be a LIMIT clause, in which ** case the order does matter */ pushOntoSorter(pParse, pSort, p, regResult, 1, nPrefixReg); }else{ int r1 = sqlite3GetTempReg(pParse); sqlite3VdbeAddOp4(v, OP_MakeRecord, regResult,1,r1, &pDest->affSdst, 1); sqlite3ExprCacheAffinityChange(pParse, regResult, 1); sqlite3VdbeAddOp2(v, OP_IdxInsert, iParm, r1); sqlite3ReleaseTempReg(pParse, r1); } |
︙ | ︙ | |||
826 827 828 829 830 831 832 | /* If this is a scalar select that is part of an expression, then ** store the results in the appropriate memory cell and break out ** of the scan loop. */ case SRT_Mem: { assert( nResultCol==1 ); if( pSort ){ | | < < | < | 855 856 857 858 859 860 861 862 863 864 865 866 867 868 869 870 871 872 873 874 875 876 877 878 879 880 881 882 883 | /* If this is a scalar select that is part of an expression, then ** store the results in the appropriate memory cell and break out ** of the scan loop. */ case SRT_Mem: { assert( nResultCol==1 ); if( pSort ){ pushOntoSorter(pParse, pSort, p, regResult, 1, nPrefixReg); }else{ sqlite3ExprCodeMove(pParse, regResult, iParm, 1); /* The LIMIT clause will jump out of the loop for us */ } break; } #endif /* #ifndef SQLITE_OMIT_SUBQUERY */ case SRT_Coroutine: /* Send data to a co-routine */ case SRT_Output: { /* Return the results */ testcase( eDest==SRT_Coroutine ); testcase( eDest==SRT_Output ); if( pSort ){ pushOntoSorter(pParse, pSort, p, regResult, nResultCol, nPrefixReg); }else if( eDest==SRT_Coroutine ){ sqlite3VdbeAddOp1(v, OP_Yield, pDest->iSDParm); }else{ sqlite3VdbeAddOp2(v, OP_ResultRow, regResult, nResultCol); sqlite3ExprCacheAffinityChange(pParse, regResult, nResultCol); } break; |
︙ | ︙ | |||
1123 1124 1125 1126 1127 1128 1129 | ){ Vdbe *v = pParse->pVdbe; /* The prepared statement */ int addrBreak = sqlite3VdbeMakeLabel(v); /* Jump here to exit loop */ int addrContinue = sqlite3VdbeMakeLabel(v); /* Jump here for next cycle */ int addr; int addrOnce = 0; int iTab; | < > > > > > > > > < < < < > > > > | > > > | < | > < > > > > > | > > | 1149 1150 1151 1152 1153 1154 1155 1156 1157 1158 1159 1160 1161 1162 1163 1164 1165 1166 1167 1168 1169 1170 1171 1172 1173 1174 1175 1176 1177 1178 1179 1180 1181 1182 1183 1184 1185 1186 1187 1188 1189 1190 1191 1192 1193 1194 1195 1196 1197 1198 1199 1200 1201 1202 1203 1204 1205 1206 1207 1208 1209 1210 1211 1212 1213 1214 1215 1216 1217 1218 | ){ Vdbe *v = pParse->pVdbe; /* The prepared statement */ int addrBreak = sqlite3VdbeMakeLabel(v); /* Jump here to exit loop */ int addrContinue = sqlite3VdbeMakeLabel(v); /* Jump here for next cycle */ int addr; int addrOnce = 0; int iTab; ExprList *pOrderBy = pSort->pOrderBy; int eDest = pDest->eDest; int iParm = pDest->iSDParm; int regRow; int regRowid; int nKey; int iSortTab; /* Sorter cursor to read from */ int nSortData; /* Trailing values to read from sorter */ u8 p5; /* p5 parameter for 1st OP_Column */ int i; int bSeq; /* True if sorter record includes seq. no. */ #ifdef SQLITE_ENABLE_EXPLAIN_COMMENTS struct ExprList_item *aOutEx = p->pEList->a; #endif if( pSort->labelBkOut ){ sqlite3VdbeAddOp2(v, OP_Gosub, pSort->regReturn, pSort->labelBkOut); sqlite3VdbeAddOp2(v, OP_Goto, 0, addrBreak); sqlite3VdbeResolveLabel(v, pSort->labelBkOut); } iTab = pSort->iECursor; if( eDest==SRT_Output || eDest==SRT_Coroutine ){ regRowid = 0; regRow = pDest->iSdst; nSortData = nColumn; }else{ regRowid = sqlite3GetTempReg(pParse); regRow = sqlite3GetTempReg(pParse); nSortData = 1; } nKey = pOrderBy->nExpr - pSort->nOBSat; if( pSort->sortFlags & SORTFLAG_UseSorter ){ int regSortOut = ++pParse->nMem; iSortTab = pParse->nTab++; if( pSort->labelBkOut ){ addrOnce = sqlite3CodeOnce(pParse); VdbeCoverage(v); } sqlite3VdbeAddOp3(v, OP_OpenPseudo, iSortTab, regSortOut, nKey+1+nSortData); if( addrOnce ) sqlite3VdbeJumpHere(v, addrOnce); addr = 1 + sqlite3VdbeAddOp2(v, OP_SorterSort, iTab, addrBreak); VdbeCoverage(v); codeOffset(v, p->iOffset, addrContinue); sqlite3VdbeAddOp2(v, OP_SorterData, iTab, regSortOut); p5 = OPFLAG_CLEARCACHE; bSeq = 0; }else{ addr = 1 + sqlite3VdbeAddOp2(v, OP_Sort, iTab, addrBreak); VdbeCoverage(v); codeOffset(v, p->iOffset, addrContinue); iSortTab = iTab; p5 = 0; bSeq = 1; } for(i=0; i<nSortData; i++){ sqlite3VdbeAddOp3(v, OP_Column, iSortTab, nKey+bSeq+i, regRow+i); if( i==0 ) sqlite3VdbeChangeP5(v, p5); VdbeComment((v, "%s", aOutEx[i].zName ? aOutEx[i].zName : aOutEx[i].zSpan)); } switch( eDest ){ case SRT_Table: case SRT_EphemTab: { testcase( eDest==SRT_Table ); testcase( eDest==SRT_EphemTab ); sqlite3VdbeAddOp2(v, OP_NewRowid, iParm, regRowid); |
︙ | ︙ | |||
1191 1192 1193 1194 1195 1196 1197 | assert( nColumn==1 ); sqlite3ExprCodeMove(pParse, regRow, iParm, 1); /* The LIMIT clause will terminate the loop for us */ break; } #endif default: { | < < < < < < < < > | | | < < < | 1233 1234 1235 1236 1237 1238 1239 1240 1241 1242 1243 1244 1245 1246 1247 1248 1249 1250 1251 1252 1253 1254 1255 1256 1257 1258 1259 1260 1261 1262 1263 1264 1265 1266 1267 1268 1269 1270 1271 1272 | assert( nColumn==1 ); sqlite3ExprCodeMove(pParse, regRow, iParm, 1); /* The LIMIT clause will terminate the loop for us */ break; } #endif default: { assert( eDest==SRT_Output || eDest==SRT_Coroutine ); testcase( eDest==SRT_Output ); testcase( eDest==SRT_Coroutine ); if( eDest==SRT_Output ){ sqlite3VdbeAddOp2(v, OP_ResultRow, pDest->iSdst, nColumn); sqlite3ExprCacheAffinityChange(pParse, pDest->iSdst, nColumn); }else{ sqlite3VdbeAddOp1(v, OP_Yield, pDest->iSDParm); } break; } } if( regRowid ){ sqlite3ReleaseTempReg(pParse, regRow); sqlite3ReleaseTempReg(pParse, regRowid); } /* The bottom of the loop */ sqlite3VdbeResolveLabel(v, addrContinue); if( pSort->sortFlags & SORTFLAG_UseSorter ){ sqlite3VdbeAddOp2(v, OP_SorterNext, iTab, addr); VdbeCoverage(v); }else{ sqlite3VdbeAddOp2(v, OP_Next, iTab, addr); VdbeCoverage(v); } if( pSort->regReturn ) sqlite3VdbeAddOp1(v, OP_Return, pSort->regReturn); sqlite3VdbeResolveLabel(v, addrBreak); } /* ** Return a pointer to a string containing the 'declaration type' of the ** expression pExpr. The string may be treated as static by the caller. ** ** Also try to estimate the size of the returned value and return that |
︙ | ︙ | |||
4768 4769 4770 4771 4772 4773 4774 | */ if( sSort.pOrderBy ){ KeyInfo *pKeyInfo; pKeyInfo = keyInfoFromExprList(pParse, sSort.pOrderBy, 0, 0); sSort.iECursor = pParse->nTab++; sSort.addrSortIndex = sqlite3VdbeAddOp4(v, OP_OpenEphemeral, | | | > | 4800 4801 4802 4803 4804 4805 4806 4807 4808 4809 4810 4811 4812 4813 4814 4815 4816 | */ if( sSort.pOrderBy ){ KeyInfo *pKeyInfo; pKeyInfo = keyInfoFromExprList(pParse, sSort.pOrderBy, 0, 0); sSort.iECursor = pParse->nTab++; sSort.addrSortIndex = sqlite3VdbeAddOp4(v, OP_OpenEphemeral, sSort.iECursor, sSort.pOrderBy->nExpr+1+pEList->nExpr, 0, (char*)pKeyInfo, P4_KEYINFO ); }else{ sSort.addrSortIndex = -1; } /* If the output is destined for a temporary table, open that table. */ if( pDest->eDest==SRT_EphemTab ){ |
︙ | ︙ | |||
4887 4888 4889 4890 4891 4892 4893 | ** SELECT statement. */ memset(&sNC, 0, sizeof(sNC)); sNC.pParse = pParse; sNC.pSrcList = pTabList; sNC.pAggInfo = &sAggInfo; sAggInfo.mnReg = pParse->nMem+1; | | | 4920 4921 4922 4923 4924 4925 4926 4927 4928 4929 4930 4931 4932 4933 4934 | ** SELECT statement. */ memset(&sNC, 0, sizeof(sNC)); sNC.pParse = pParse; sNC.pSrcList = pTabList; sNC.pAggInfo = &sAggInfo; sAggInfo.mnReg = pParse->nMem+1; sAggInfo.nSortingColumn = pGroupBy ? pGroupBy->nExpr : 0; sAggInfo.pGroupBy = pGroupBy; sqlite3ExprAnalyzeAggList(&sNC, pEList); sqlite3ExprAnalyzeAggList(&sNC, sSort.pOrderBy); if( pHaving ){ sqlite3ExprAnalyzeAggregates(&sNC, pHaving); } sAggInfo.nAccumulator = sAggInfo.nColumn; |
︙ | ︙ | |||
4979 4980 4981 4982 4983 4984 4985 | explainTempTable(pParse, (sDistinct.isTnct && (p->selFlags&SF_Distinct)==0) ? "DISTINCT" : "GROUP BY"); groupBySort = 1; nGroupBy = pGroupBy->nExpr; | | | < | | 5012 5013 5014 5015 5016 5017 5018 5019 5020 5021 5022 5023 5024 5025 5026 5027 5028 5029 5030 5031 5032 5033 5034 5035 5036 5037 | explainTempTable(pParse, (sDistinct.isTnct && (p->selFlags&SF_Distinct)==0) ? "DISTINCT" : "GROUP BY"); groupBySort = 1; nGroupBy = pGroupBy->nExpr; nCol = nGroupBy; j = nGroupBy; for(i=0; i<sAggInfo.nColumn; i++){ if( sAggInfo.aCol[i].iSorterColumn>=j ){ nCol++; j++; } } regBase = sqlite3GetTempRange(pParse, nCol); sqlite3ExprCacheClear(pParse); sqlite3ExprCodeExprList(pParse, pGroupBy, regBase, 0); j = nGroupBy; for(i=0; i<sAggInfo.nColumn; i++){ struct AggInfo_col *pCol = &sAggInfo.aCol[i]; if( pCol->iSorterColumn>=j ){ int r1 = j + regBase; int r2; r2 = sqlite3ExprCodeGetColumn(pParse, |
︙ | ︙ |
Changes to src/sqliteInt.h.
︙ | ︙ | |||
1624 1625 1626 1627 1628 1629 1630 1631 1632 1633 1634 1635 1636 1637 | ** The r1 and r2 member variables are only used by the optimized comparison ** functions vdbeRecordCompareInt() and vdbeRecordCompareString(). */ struct UnpackedRecord { KeyInfo *pKeyInfo; /* Collation and sort-order information */ u16 nField; /* Number of entries in apMem[] */ i8 default_rc; /* Comparison result if keys are equal */ Mem *aMem; /* Values */ int r1; /* Value to return if (lhs > rhs) */ int r2; /* Value to return if (rhs < lhs) */ }; /* | > | 1624 1625 1626 1627 1628 1629 1630 1631 1632 1633 1634 1635 1636 1637 1638 | ** The r1 and r2 member variables are only used by the optimized comparison ** functions vdbeRecordCompareInt() and vdbeRecordCompareString(). */ struct UnpackedRecord { KeyInfo *pKeyInfo; /* Collation and sort-order information */ u16 nField; /* Number of entries in apMem[] */ i8 default_rc; /* Comparison result if keys are equal */ u8 isCorrupt; /* Corruption detected by xRecordCompare() */ Mem *aMem; /* Values */ int r1; /* Value to return if (lhs > rhs) */ int r2; /* Value to return if (rhs < lhs) */ }; /* |
︙ | ︙ |
Changes to src/vdbe.c.
︙ | ︙ | |||
3405 3406 3407 3408 3409 3410 3411 3412 3413 3414 3415 3416 3417 3418 | if( pCx==0 ) goto no_mem; pCx->pKeyInfo = pOp->p4.pKeyInfo; assert( pCx->pKeyInfo->db==db ); assert( pCx->pKeyInfo->enc==ENC(db) ); rc = sqlite3VdbeSorterInit(db, pCx); break; } /* Opcode: OpenPseudo P1 P2 P3 * * ** Synopsis: P3 columns in r[P2] ** ** Open a new cursor that points to a fake table that contains a single ** row of data. The content of that one row is the content of memory ** register P2. In other words, cursor P1 becomes an alias for the | > > > > > > > > > > > > > > > > > > | 3405 3406 3407 3408 3409 3410 3411 3412 3413 3414 3415 3416 3417 3418 3419 3420 3421 3422 3423 3424 3425 3426 3427 3428 3429 3430 3431 3432 3433 3434 3435 3436 | if( pCx==0 ) goto no_mem; pCx->pKeyInfo = pOp->p4.pKeyInfo; assert( pCx->pKeyInfo->db==db ); assert( pCx->pKeyInfo->enc==ENC(db) ); rc = sqlite3VdbeSorterInit(db, pCx); break; } /* Opcode: SequenceTest P1 P2 * * * ** Synopsis: if( cursor[P1].ctr++ ) pc = P2 ** ** P1 is a sorter cursor. If the sequence counter is currently zero, jump ** to P2. Regardless of whether or not the jump is taken, increment the ** the sequence value. */ case OP_SequenceTest: { VdbeCursor *pC; assert( pOp->p1>=0 && pOp->p1<p->nCursor ); pC = p->apCsr[pOp->p1]; assert( pC->pSorter ); if( (pC->seqCount++)==0 ){ pc = pOp->p2 - 1; } break; } /* Opcode: OpenPseudo P1 P2 P3 * * ** Synopsis: P3 columns in r[P2] ** ** Open a new cursor that points to a fake table that contains a single ** row of data. The content of that one row is the content of memory ** register P2. In other words, cursor P1 becomes an alias for the |
︙ | ︙ |
Changes to src/vdbe.h.
︙ | ︙ | |||
207 208 209 210 211 212 213 | sqlite3_value *sqlite3VdbeGetBoundValue(Vdbe*, int, u8); void sqlite3VdbeSetVarmask(Vdbe*, int); #ifndef SQLITE_OMIT_TRACE char *sqlite3VdbeExpandSql(Vdbe*, const char*); #endif void sqlite3VdbeRecordUnpack(KeyInfo*,int,const void*,UnpackedRecord*); | | | | 207 208 209 210 211 212 213 214 215 216 217 218 219 220 221 222 223 224 | sqlite3_value *sqlite3VdbeGetBoundValue(Vdbe*, int, u8); void sqlite3VdbeSetVarmask(Vdbe*, int); #ifndef SQLITE_OMIT_TRACE char *sqlite3VdbeExpandSql(Vdbe*, const char*); #endif void sqlite3VdbeRecordUnpack(KeyInfo*,int,const void*,UnpackedRecord*); int sqlite3VdbeRecordCompare(int,const void*,UnpackedRecord*,int); UnpackedRecord *sqlite3VdbeAllocUnpackedRecord(KeyInfo *, char *, int, char **); typedef int (*RecordCompare)(int,const void*,UnpackedRecord*,int); RecordCompare sqlite3VdbeFindCompare(UnpackedRecord*); #ifndef SQLITE_OMIT_TRIGGER void sqlite3VdbeLinkSubProgram(Vdbe *, SubProgram *); #endif /* Use SQLITE_ENABLE_COMMENTS to enable generation of extra comments on |
︙ | ︙ |
Changes to src/vdbeInt.h.
︙ | ︙ | |||
388 389 390 391 392 393 394 | u32 sqlite3VdbeSerialTypeLen(u32); u32 sqlite3VdbeSerialType(Mem*, int); u32 sqlite3VdbeSerialPut(unsigned char*, Mem*, u32); u32 sqlite3VdbeSerialGet(const unsigned char*, u32, Mem*); void sqlite3VdbeDeleteAuxData(Vdbe*, int, int); int sqlite2BtreeKeyCompare(BtCursor *, const void *, int, int, int *); | | | 388 389 390 391 392 393 394 395 396 397 398 399 400 401 402 | u32 sqlite3VdbeSerialTypeLen(u32); u32 sqlite3VdbeSerialType(Mem*, int); u32 sqlite3VdbeSerialPut(unsigned char*, Mem*, u32); u32 sqlite3VdbeSerialGet(const unsigned char*, u32, Mem*); void sqlite3VdbeDeleteAuxData(Vdbe*, int, int); int sqlite2BtreeKeyCompare(BtCursor *, const void *, int, int, int *); int sqlite3VdbeIdxKeyCompare(VdbeCursor*,UnpackedRecord*,int*); int sqlite3VdbeIdxRowid(sqlite3*, BtCursor *, i64 *); int sqlite3MemCompare(const Mem*, const Mem*, const CollSeq*); int sqlite3VdbeExec(Vdbe*); int sqlite3VdbeList(Vdbe*); int sqlite3VdbeHalt(Vdbe*); int sqlite3VdbeChangeEncoding(Mem *, int); int sqlite3VdbeMemTooBig(Mem*); |
︙ | ︙ |
Changes to src/vdbeaux.c.
︙ | ︙ | |||
3401 3402 3403 3404 3405 3406 3407 3408 3409 3410 | ** ** If argument bSkip is non-zero, it is assumed that the caller has already ** determined that the first fields of the keys are equal. ** ** Key1 and Key2 do not have to contain the same number of fields. If all ** fields that appear in both keys are equal, then pPKey2->default_rc is ** returned. */ int sqlite3VdbeRecordCompare( int nKey1, const void *pKey1, /* Left key */ | > > > | | 3401 3402 3403 3404 3405 3406 3407 3408 3409 3410 3411 3412 3413 3414 3415 3416 3417 3418 3419 3420 3421 | ** ** If argument bSkip is non-zero, it is assumed that the caller has already ** determined that the first fields of the keys are equal. ** ** Key1 and Key2 do not have to contain the same number of fields. If all ** fields that appear in both keys are equal, then pPKey2->default_rc is ** returned. ** ** If database corruption is discovered, set pPKey2->isCorrupt to non-zero ** and return 0. */ int sqlite3VdbeRecordCompare( int nKey1, const void *pKey1, /* Left key */ UnpackedRecord *pPKey2, /* Right key */ int bSkip /* If true, skip the first field */ ){ u32 d1; /* Offset into aKey[] of next data element */ int i; /* Index of next field to compare */ u32 szHdr1; /* Size of record header in bytes */ u32 idx1; /* Offset of first type in header */ int rc = 0; /* Return value */ |
︙ | ︙ | |||
3430 3431 3432 3433 3434 3435 3436 | szHdr1 = aKey1[0]; d1 = szHdr1 + sqlite3VdbeSerialTypeLen(s1); i = 1; pRhs++; }else{ idx1 = getVarint32(aKey1, szHdr1); d1 = szHdr1; | | > > > | 3433 3434 3435 3436 3437 3438 3439 3440 3441 3442 3443 3444 3445 3446 3447 3448 3449 3450 | szHdr1 = aKey1[0]; d1 = szHdr1 + sqlite3VdbeSerialTypeLen(s1); i = 1; pRhs++; }else{ idx1 = getVarint32(aKey1, szHdr1); d1 = szHdr1; if( d1>(unsigned)nKey1 ){ pPKey2->isCorrupt = (u8)SQLITE_CORRUPT_BKPT; return 0; /* Corruption */ } i = 0; } VVA_ONLY( mem1.zMalloc = 0; ) /* Only needed by assert() statements */ assert( pPKey2->pKeyInfo->nField+pPKey2->pKeyInfo->nXField>=pPKey2->nField || CORRUPT_DB ); assert( pPKey2->pKeyInfo->aSortOrder!=0 ); |
︙ | ︙ | |||
3507 3508 3509 3510 3511 3512 3513 | }else if( !(serial_type & 0x01) ){ rc = +1; }else{ mem1.n = (serial_type - 12) / 2; testcase( (d1+mem1.n)==(unsigned)nKey1 ); testcase( (d1+mem1.n+1)==(unsigned)nKey1 ); if( (d1+mem1.n) > (unsigned)nKey1 ){ | > | | 3513 3514 3515 3516 3517 3518 3519 3520 3521 3522 3523 3524 3525 3526 3527 3528 | }else if( !(serial_type & 0x01) ){ rc = +1; }else{ mem1.n = (serial_type - 12) / 2; testcase( (d1+mem1.n)==(unsigned)nKey1 ); testcase( (d1+mem1.n+1)==(unsigned)nKey1 ); if( (d1+mem1.n) > (unsigned)nKey1 ){ pPKey2->isCorrupt = (u8)SQLITE_CORRUPT_BKPT; return 0; /* Corruption */ }else if( pKeyInfo->aColl[i] ){ mem1.enc = pKeyInfo->enc; mem1.db = pKeyInfo->db; mem1.flags = MEM_Str; mem1.z = (char*)&aKey1[d1]; rc = vdbeCompareMemString(&mem1, pRhs, pKeyInfo->aColl[i]); }else{ |
︙ | ︙ | |||
3533 3534 3535 3536 3537 3538 3539 | if( serial_type<12 || (serial_type & 0x01) ){ rc = -1; }else{ int nStr = (serial_type - 12) / 2; testcase( (d1+nStr)==(unsigned)nKey1 ); testcase( (d1+nStr+1)==(unsigned)nKey1 ); if( (d1+nStr) > (unsigned)nKey1 ){ | > | | 3540 3541 3542 3543 3544 3545 3546 3547 3548 3549 3550 3551 3552 3553 3554 3555 | if( serial_type<12 || (serial_type & 0x01) ){ rc = -1; }else{ int nStr = (serial_type - 12) / 2; testcase( (d1+nStr)==(unsigned)nKey1 ); testcase( (d1+nStr+1)==(unsigned)nKey1 ); if( (d1+nStr) > (unsigned)nKey1 ){ pPKey2->isCorrupt = (u8)SQLITE_CORRUPT_BKPT; return 0; /* Corruption */ }else{ int nCmp = MIN(nStr, pRhs->n); rc = memcmp(&aKey1[d1], pRhs->z, nCmp); if( rc==0 ) rc = nStr - pRhs->n; } } } |
︙ | ︙ | |||
3592 3593 3594 3595 3596 3597 3598 | ** byte (i.e. is less than 128). ** ** To avoid concerns about buffer overreads, this routine is only used ** on schemas where the maximum valid header size is 63 bytes or less. */ static int vdbeRecordCompareInt( int nKey1, const void *pKey1, /* Left key */ | | | 3600 3601 3602 3603 3604 3605 3606 3607 3608 3609 3610 3611 3612 3613 3614 | ** byte (i.e. is less than 128). ** ** To avoid concerns about buffer overreads, this routine is only used ** on schemas where the maximum valid header size is 63 bytes or less. */ static int vdbeRecordCompareInt( int nKey1, const void *pKey1, /* Left key */ UnpackedRecord *pPKey2, /* Right key */ int bSkip /* Ignored */ ){ const u8 *aKey = &((const u8*)pKey1)[*(const u8*)pKey1 & 0x3F]; int serial_type = ((const u8*)pKey1)[1]; int res; u32 y; u64 x; |
︙ | ︙ | |||
3690 3691 3692 3693 3694 3695 3696 | ** This function is an optimized version of sqlite3VdbeRecordCompare() ** that (a) the first field of pPKey2 is a string, that (b) the first field ** uses the collation sequence BINARY and (c) that the size-of-header varint ** at the start of (pKey1/nKey1) fits in a single byte. */ static int vdbeRecordCompareString( int nKey1, const void *pKey1, /* Left key */ | | | > > > | 3698 3699 3700 3701 3702 3703 3704 3705 3706 3707 3708 3709 3710 3711 3712 3713 3714 3715 3716 3717 3718 3719 3720 3721 3722 3723 3724 3725 3726 3727 3728 3729 3730 3731 3732 3733 3734 3735 3736 | ** This function is an optimized version of sqlite3VdbeRecordCompare() ** that (a) the first field of pPKey2 is a string, that (b) the first field ** uses the collation sequence BINARY and (c) that the size-of-header varint ** at the start of (pKey1/nKey1) fits in a single byte. */ static int vdbeRecordCompareString( int nKey1, const void *pKey1, /* Left key */ UnpackedRecord *pPKey2, /* Right key */ int bSkip ){ const u8 *aKey1 = (const u8*)pKey1; int serial_type; int res; UNUSED_PARAMETER(bSkip); assert( bSkip==0 ); getVarint32(&aKey1[1], serial_type); if( serial_type<12 ){ res = pPKey2->r1; /* (pKey1/nKey1) is a number or a null */ }else if( !(serial_type & 0x01) ){ res = pPKey2->r2; /* (pKey1/nKey1) is a blob */ }else{ int nCmp; int nStr; int szHdr = aKey1[0]; nStr = (serial_type-12) / 2; if( (szHdr + nStr) > nKey1 ){ pPKey2->isCorrupt = (u8)SQLITE_CORRUPT_BKPT; return 0; /* Corruption */ } nCmp = MIN( pPKey2->aMem[0].n, nStr ); res = memcmp(&aKey1[szHdr], pPKey2->aMem[0].z, nCmp); if( res==0 ){ res = nStr - pPKey2->aMem[0].n; if( res==0 ){ if( pPKey2->nField>1 ){ |
︙ | ︙ | |||
3876 3877 3878 3879 3880 3881 3882 | ** pUnpacked is either created without a rowid or is truncated so that it ** omits the rowid at the end. The rowid at the end of the index entry ** is ignored as well. Hence, this routine only compares the prefixes ** of the keys prior to the final rowid, not the entire key. */ int sqlite3VdbeIdxKeyCompare( VdbeCursor *pC, /* The cursor to compare against */ | | | 3887 3888 3889 3890 3891 3892 3893 3894 3895 3896 3897 3898 3899 3900 3901 | ** pUnpacked is either created without a rowid or is truncated so that it ** omits the rowid at the end. The rowid at the end of the index entry ** is ignored as well. Hence, this routine only compares the prefixes ** of the keys prior to the final rowid, not the entire key. */ int sqlite3VdbeIdxKeyCompare( VdbeCursor *pC, /* The cursor to compare against */ UnpackedRecord *pUnpacked, /* Unpacked version of key */ int *res /* Write the comparison result here */ ){ i64 nCellKey = 0; int rc; BtCursor *pCur = pC->pCursor; Mem m; |
︙ | ︙ |
Changes to src/vdbesort.c.
︙ | ︙ | |||
86 87 88 89 90 91 92 93 94 95 96 97 98 99 | UnpackedRecord *pUnpacked; /* Space to unpack a record */ int pgsz; /* Main database page size */ u8 eWork; /* One of the SORTER_THREAD_* constants */ int nConsolidate; /* For THREAD_CONS, max final PMAs */ SorterRecord *pList; /* List of records for pThread to sort */ int nInMemory; /* Expected size of PMA based on pList */ int nPMA; /* Number of PMAs currently in pTemp1 */ i64 iTemp1Off; /* Offset to write to in pTemp1 */ sqlite3_file *pTemp1; /* File to write PMAs to, or NULL */ }; | > | 86 87 88 89 90 91 92 93 94 95 96 97 98 99 100 | UnpackedRecord *pUnpacked; /* Space to unpack a record */ int pgsz; /* Main database page size */ u8 eWork; /* One of the SORTER_THREAD_* constants */ int nConsolidate; /* For THREAD_CONS, max final PMAs */ SorterRecord *pList; /* List of records for pThread to sort */ int nInMemory; /* Expected size of PMA based on pList */ u8 *aListMemory; /* Records memory (or NULL) */ int nPMA; /* Number of PMAs currently in pTemp1 */ i64 iTemp1Off; /* Offset to write to in pTemp1 */ sqlite3_file *pTemp1; /* File to write PMAs to, or NULL */ }; |
︙ | ︙ | |||
179 180 181 182 183 184 185 186 187 188 189 190 191 192 193 194 195 196 197 198 199 200 201 202 203 204 205 206 207 208 209 210 211 212 213 214 215 216 217 218 219 220 221 222 | struct VdbeSorter { int nInMemory; /* Current size of pRecord list as PMA */ int mnPmaSize; /* Minimum PMA size, in bytes */ int mxPmaSize; /* Maximum PMA size, in bytes. 0==no limit */ int bUsePMA; /* True if one or more PMAs created */ SorterRecord *pRecord; /* Head of in-memory record list */ SorterMerger *pMerger; /* For final merge of PMAs (by caller) */ SorterThread aThread[SQLITE_MAX_SORTER_THREAD]; }; /* ** 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 { i64 iReadOff; /* Current read offset */ i64 iEof; /* 1 byte past EOF for this iterator */ int nAlloc; /* Bytes of space at aAlloc */ int nKey; /* Number of bytes in key */ sqlite3_file *pFile; /* File iterator is reading from */ u8 *aAlloc; /* Allocated space */ u8 *aKey; /* Pointer to current key */ u8 *aBuffer; /* Current read buffer */ int nBuffer; /* Size of read buffer in bytes */ }; /* ** An instance of this structure is used to organize the stream of records ** being written to files by the merge-sort code into aligned, page-sized ** blocks. Doing all I/O in aligned page-sized blocks helps I/O to go ** faster on many operating systems. */ struct FileWriter { int eFWErr; /* Non-zero if in an error state */ u8 *aBuffer; /* Pointer to write buffer */ int nBuffer; /* Size of write buffer in bytes */ int iBufStart; /* First byte of buffer to write */ int iBufEnd; /* Last byte of buffer to write */ i64 iWriteOff; /* Offset of start of buffer in file */ sqlite3_file *pFile; /* File to write to */ }; /* ** A structure to store a single record. All in-memory records are connected | > > > > | > > > > | > > > > > > > > > < > | > > > > > > > > > > > > > > > > > | 180 181 182 183 184 185 186 187 188 189 190 191 192 193 194 195 196 197 198 199 200 201 202 203 204 205 206 207 208 209 210 211 212 213 214 215 216 217 218 219 220 221 222 223 224 225 226 227 228 229 230 231 232 233 234 235 236 237 238 239 240 241 242 243 244 245 246 247 248 249 250 251 252 253 254 255 256 257 258 259 260 261 262 263 264 265 266 267 268 269 270 271 272 273 274 275 276 277 278 279 280 281 282 283 284 285 286 287 288 289 290 291 292 293 294 295 296 297 298 299 300 301 302 303 304 305 306 | struct VdbeSorter { int nInMemory; /* Current size of pRecord list as PMA */ int mnPmaSize; /* Minimum PMA size, in bytes */ int mxPmaSize; /* Maximum PMA size, in bytes. 0==no limit */ int bUsePMA; /* True if one or more PMAs created */ SorterRecord *pRecord; /* Head of in-memory record list */ SorterMerger *pMerger; /* For final merge of PMAs (by caller) */ u8 *aMemory; /* Block of memory to alloc records from */ int iMemory; /* Offset of first free byte in aMemory */ int nMemory; /* Size of aMemory allocation in bytes */ SorterThread aThread[SQLITE_MAX_SORTER_THREAD]; }; /* ** 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 { i64 iReadOff; /* Current read offset */ i64 iEof; /* 1 byte past EOF for this iterator */ int nAlloc; /* Bytes of space at aAlloc */ int nKey; /* Number of bytes in key */ sqlite3_file *pFile; /* File iterator is reading from */ u8 *aAlloc; /* Allocated space */ u8 *aKey; /* Pointer to current key */ u8 *aBuffer; /* Current read buffer */ int nBuffer; /* Size of read buffer in bytes */ u8 *aMap; /* Pointer to mapping of entire file */ }; /* ** An instance of this structure is used to organize the stream of records ** being written to files by the merge-sort code into aligned, page-sized ** blocks. Doing all I/O in aligned page-sized blocks helps I/O to go ** faster on many operating systems. */ struct FileWriter { int eFWErr; /* Non-zero if in an error state */ u8 *aBuffer; /* Pointer to write buffer */ int nBuffer; /* Size of write buffer in bytes */ int iBufStart; /* First byte of buffer to write */ int iBufEnd; /* Last byte of buffer to write */ i64 iWriteOff; /* Offset of start of buffer in file */ sqlite3_file *pFile; /* File to write to */ }; /* ** A structure to store a single record. All in-memory records are connected ** together into a linked list headed at VdbeSorter.pRecord. ** ** How the linked list is connected depends on how memory is being managed ** by this module. If using a separate allocation for each in-memory record ** (VdbeSorter.aMemory==0), then the list is always connected using the ** SorterRecord.u.pNext pointers. ** ** Or, if using the single large allocation method (VdbeSorter.aMemory!=0), ** then while records are being accumulated the list is linked using the ** SorterRecord.u.iNext offset. This is because the aMemory[] array may ** be sqlite3Realloc()ed while records are being accumulated. Once the VM ** has finished passing records to the sorter, or when the in-memory buffer ** is full, the list is sorted. As part of the sorting process, it is ** converted to use the SorterRecord.u.pNext pointers. See function ** vdbeSorterSort() for details. */ struct SorterRecord { int nVal; union { SorterRecord *pNext; /* Pointer to next record in list */ int iNext; /* Offset within aMemory of next record */ } u; }; /* Return a pointer to the buffer containing the record data for SorterRecord ** object p. Should be used as if: ** ** void *SRVAL(SorterRecord *p) { return (void*)&p[1]; } */ #define SRVAL(p) ((void*)((SorterRecord*)(p) + 1)) /* The minimum PMA size is set to this value multiplied by the database ** page size in bytes. */ #define SORTER_MIN_WORKING 10 /* Maximum number of segments to merge in a single pass. */ #define SORTER_MAX_MERGE_COUNT 16 /* ** Free all memory belonging to the VdbeSorterIter object passed as the second ** argument. All structure fields are set to zero before returning. */ static void vdbeSorterIterZero(VdbeSorterIter *pIter){ sqlite3_free(pIter->aAlloc); sqlite3_free(pIter->aBuffer); if( pIter->aMap ) sqlite3OsUnfetch(pIter->pFile, 0, pIter->aMap); memset(pIter, 0, sizeof(VdbeSorterIter)); } /* ** Read nByte bytes of data from the stream of data iterated by object p. ** If successful, set *ppOut to point to a buffer containing the data ** and return SQLITE_OK. Otherwise, if an error occurs, return an SQLite ** error code. ** ** The buffer indicated by *ppOut may only be considered valid until the ** next call to this function. */ static int vdbeSorterIterRead( VdbeSorterIter *p, /* Iterator */ int nByte, /* Bytes of data to read */ u8 **ppOut /* OUT: Pointer to buffer containing data */ ){ int iBuf; /* Offset within buffer to read from */ int nAvail; /* Bytes of data available in buffer */ if( p->aMap ){ *ppOut = &p->aMap[p->iReadOff]; p->iReadOff += nByte; return SQLITE_OK; } assert( p->aBuffer ); /* If there is no more data to be read from the buffer, read the next ** p->nBuffer bytes of data from the file into it. Or, if there are less ** than p->nBuffer bytes remaining in the PMA, read all remaining data. */ iBuf = p->iReadOff % p->nBuffer; if( iBuf==0 ){ |
︙ | ︙ | |||
341 342 343 344 345 346 347 | /* ** Read a varint from the stream of data accessed by p. Set *pnOut to ** the value read. */ static int vdbeSorterIterVarint(VdbeSorterIter *p, u64 *pnOut){ int iBuf; | > > > | | | | | | | | | | | | > | 376 377 378 379 380 381 382 383 384 385 386 387 388 389 390 391 392 393 394 395 396 397 398 399 400 401 402 403 404 405 | /* ** Read a varint from the stream of data accessed by p. Set *pnOut to ** the value read. */ static int vdbeSorterIterVarint(VdbeSorterIter *p, u64 *pnOut){ int iBuf; if( p->aMap ){ p->iReadOff += sqlite3GetVarint(&p->aMap[p->iReadOff], pnOut); }else{ iBuf = p->iReadOff % p->nBuffer; if( iBuf && (p->nBuffer-iBuf)>=9 ){ p->iReadOff += sqlite3GetVarint(&p->aBuffer[iBuf], pnOut); }else{ u8 aVarint[16], *a; int i = 0, rc; do{ rc = vdbeSorterIterRead(p, 1, &a); if( rc ) return rc; aVarint[(i++)&0xf] = a[0]; }while( (a[0]&0x80)!=0 ); sqlite3GetVarint(aVarint, pnOut); } } return SQLITE_OK; } /* |
︙ | ︙ | |||
396 397 398 399 400 401 402 403 404 405 406 407 408 409 410 | SorterThread *pThread, /* Thread context */ i64 iStart, /* Start offset in pThread->pTemp1 */ VdbeSorterIter *pIter, /* Iterator to populate */ i64 *pnByte /* IN/OUT: Increment this value by PMA size */ ){ int rc = SQLITE_OK; int nBuf = pThread->pgsz; assert( pThread->iTemp1Off>iStart ); assert( pIter->aAlloc==0 ); assert( pIter->aBuffer==0 ); pIter->pFile = pThread->pTemp1; pIter->iReadOff = iStart; pIter->nAlloc = 128; pIter->aAlloc = (u8*)sqlite3Malloc(pIter->nAlloc); | > > > > > > > > > > | | < | | | < < | | | | | | | | | | | | > > > | | | | | | < | 435 436 437 438 439 440 441 442 443 444 445 446 447 448 449 450 451 452 453 454 455 456 457 458 459 460 461 462 463 464 465 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 | SorterThread *pThread, /* Thread context */ i64 iStart, /* Start offset in pThread->pTemp1 */ VdbeSorterIter *pIter, /* Iterator to populate */ i64 *pnByte /* IN/OUT: Increment this value by PMA size */ ){ int rc = SQLITE_OK; int nBuf = pThread->pgsz; void *pMap = 0; /* Mapping of temp file */ assert( pThread->iTemp1Off>iStart ); assert( pIter->aAlloc==0 ); assert( pIter->aBuffer==0 ); pIter->pFile = pThread->pTemp1; pIter->iReadOff = iStart; pIter->nAlloc = 128; pIter->aAlloc = (u8*)sqlite3Malloc(pIter->nAlloc); /* Try to xFetch() a mapping of the entire temp file. If this is possible, ** the PMA will be read via the mapping. Otherwise, use xRead(). */ rc = sqlite3OsFetch(pIter->pFile, 0, pThread->iTemp1Off, &pMap); if( rc==SQLITE_OK ){ if( pMap ){ pIter->aMap = (u8*)pMap; }else{ pIter->nBuffer = nBuf; pIter->aBuffer = (u8*)sqlite3Malloc(nBuf); if( !pIter->aBuffer ){ rc = SQLITE_NOMEM; }else{ int iBuf = iStart % nBuf; if( iBuf ){ int nRead = nBuf - iBuf; if( (iStart + nRead) > pThread->iTemp1Off ){ nRead = (int)(pThread->iTemp1Off - iStart); } rc = sqlite3OsRead( pThread->pTemp1, &pIter->aBuffer[iBuf], nRead, iStart ); assert( rc!=SQLITE_IOERR_SHORT_READ ); } } } } if( rc==SQLITE_OK ){ u64 nByte; /* Size of PMA in bytes */ pIter->iEof = pThread->iTemp1Off; rc = vdbeSorterIterVarint(pIter, &nByte); pIter->iEof = pIter->iReadOff + nByte; *pnByte += nByte; } if( rc==SQLITE_OK ){ rc = vdbeSorterIterNext(pIter); } return rc; } |
︙ | ︙ | |||
545 546 547 548 549 550 551 552 553 554 555 556 557 | int sqlite3VdbeSorterInit(sqlite3 *db, VdbeCursor *pCsr){ int pgsz; /* Page size of main database */ int i; /* Used to iterate through aThread[] */ int mxCache; /* Cache size */ VdbeSorter *pSorter; /* The new sorter */ KeyInfo *pKeyInfo; /* Copy of pCsr->pKeyInfo with db==0 */ int szKeyInfo; /* Size of pCsr->pKeyInfo in bytes */ assert( pCsr->pKeyInfo && pCsr->pBt==0 ); szKeyInfo = sizeof(KeyInfo) + (pCsr->pKeyInfo->nField-1)*sizeof(CollSeq*); pSorter = (VdbeSorter*)sqlite3DbMallocZero(db, sizeof(VdbeSorter)+szKeyInfo); pCsr->pSorter = pSorter; if( pSorter==0 ){ | > | | | | | | | | | | | | | | | | | | > > > > > > > > | > > > | | > | > > > > | 593 594 595 596 597 598 599 600 601 602 603 604 605 606 607 608 609 610 611 612 613 614 615 616 617 618 619 620 621 622 623 624 625 626 627 628 629 630 631 632 633 634 635 636 637 638 639 640 641 642 643 644 645 646 647 648 649 650 651 652 653 654 655 656 657 658 659 660 661 662 663 664 665 666 667 668 669 670 671 672 673 | int sqlite3VdbeSorterInit(sqlite3 *db, VdbeCursor *pCsr){ int pgsz; /* Page size of main database */ int i; /* Used to iterate through aThread[] */ int mxCache; /* Cache size */ VdbeSorter *pSorter; /* The new sorter */ KeyInfo *pKeyInfo; /* Copy of pCsr->pKeyInfo with db==0 */ int szKeyInfo; /* Size of pCsr->pKeyInfo in bytes */ int rc = SQLITE_OK; assert( pCsr->pKeyInfo && pCsr->pBt==0 ); szKeyInfo = sizeof(KeyInfo) + (pCsr->pKeyInfo->nField-1)*sizeof(CollSeq*); pSorter = (VdbeSorter*)sqlite3DbMallocZero(db, sizeof(VdbeSorter)+szKeyInfo); pCsr->pSorter = pSorter; if( pSorter==0 ){ rc = SQLITE_NOMEM; }else{ pKeyInfo = (KeyInfo*)&pSorter[1]; memcpy(pKeyInfo, pCsr->pKeyInfo, szKeyInfo); pKeyInfo->db = 0; pgsz = sqlite3BtreeGetPageSize(db->aDb[0].pBt); for(i=0; i<SQLITE_MAX_SORTER_THREAD; i++){ SorterThread *pThread = &pSorter->aThread[i]; pThread->pKeyInfo = pKeyInfo; pThread->pVfs = db->pVfs; pThread->pgsz = pgsz; } if( !sqlite3TempInMemory(db) ){ pSorter->mnPmaSize = SORTER_MIN_WORKING * pgsz; mxCache = db->aDb[0].pSchema->cache_size; if( mxCache<SORTER_MIN_WORKING ) mxCache = SORTER_MIN_WORKING; pSorter->mxPmaSize = mxCache * pgsz; /* If the application is using memsys3 or memsys5, use a separate ** allocation for each sort-key in memory. Otherwise, use a single big ** allocation at pSorter->aMemory for all sort-keys. */ if( sqlite3GlobalConfig.pHeap==0 ){ assert( pSorter->iMemory==0 ); pSorter->nMemory = pgsz; pSorter->aMemory = (u8*)sqlite3Malloc(pgsz); if( !pSorter->aMemory ) rc = SQLITE_NOMEM; } } } return rc; } /* ** Free the list of sorted records starting at pRecord. */ static void vdbeSorterRecordFree(sqlite3 *db, SorterRecord *pRecord){ SorterRecord *p; SorterRecord *pNext; for(p=pRecord; p; p=pNext){ pNext = p->u.pNext; sqlite3DbFree(db, p); } } /* ** Free all resources owned by the object indicated by argument pThread. All ** fields of *pThread are zeroed before returning. */ static void vdbeSorterThreadCleanup(sqlite3 *db, SorterThread *pThread){ sqlite3DbFree(db, pThread->pUnpacked); pThread->pUnpacked = 0; if( pThread->aListMemory==0 ){ vdbeSorterRecordFree(0, pThread->pList); }else{ sqlite3_free(pThread->aListMemory); pThread->aListMemory = 0; } pThread->pList = 0; if( pThread->pTemp1 ){ sqlite3OsCloseFree(pThread->pTemp1); pThread->pTemp1 = 0; } } |
︙ | ︙ | |||
674 675 676 677 678 679 680 | void sqlite3VdbeSorterReset(sqlite3 *db, VdbeSorter *pSorter){ int i; vdbeSorterJoinAll(pSorter, SQLITE_OK); for(i=0; i<SQLITE_MAX_SORTER_THREAD; i++){ SorterThread *pThread = &pSorter->aThread[i]; vdbeSorterThreadCleanup(db, pThread); } | > | > > > | | | > > > > > | | | | | | | | 739 740 741 742 743 744 745 746 747 748 749 750 751 752 753 754 755 756 757 758 759 760 761 762 763 764 765 766 767 768 769 770 771 772 773 774 775 776 777 778 779 780 781 782 783 784 785 786 787 788 789 790 791 792 793 794 795 796 797 798 799 800 801 802 803 804 805 806 807 808 809 810 811 812 813 814 815 816 817 818 819 820 821 822 823 | void sqlite3VdbeSorterReset(sqlite3 *db, VdbeSorter *pSorter){ int i; vdbeSorterJoinAll(pSorter, SQLITE_OK); for(i=0; i<SQLITE_MAX_SORTER_THREAD; i++){ SorterThread *pThread = &pSorter->aThread[i]; vdbeSorterThreadCleanup(db, pThread); } if( pSorter->aMemory==0 ){ vdbeSorterRecordFree(0, pSorter->pRecord); } vdbeSorterMergerReset(pSorter->pMerger); pSorter->pRecord = 0; pSorter->nInMemory = 0; pSorter->bUsePMA = 0; pSorter->iMemory = 0; } /* ** Free any cursor components allocated by sqlite3VdbeSorterXXX routines. */ void sqlite3VdbeSorterClose(sqlite3 *db, VdbeCursor *pCsr){ VdbeSorter *pSorter = pCsr->pSorter; if( pSorter ){ sqlite3VdbeSorterReset(db, pSorter); vdbeSorterMergerFree(pSorter->pMerger); sqlite3_free(pSorter->aMemory); sqlite3DbFree(db, pSorter); pCsr->pSorter = 0; } } /* ** Allocate space for a file-handle and open a temporary file. If successful, ** set *ppFile to point to the malloc'd file-handle and return SQLITE_OK. ** Otherwise, set *ppFile to 0 and return an SQLite error code. */ static int vdbeSorterOpenTempFile(sqlite3_vfs *pVfs, sqlite3_file **ppFile){ int rc; rc = sqlite3OsOpenMalloc(pVfs, 0, ppFile, SQLITE_OPEN_TEMP_JOURNAL | SQLITE_OPEN_READWRITE | SQLITE_OPEN_CREATE | SQLITE_OPEN_EXCLUSIVE | SQLITE_OPEN_DELETEONCLOSE, &rc ); if( rc==SQLITE_OK ){ i64 max = SQLITE_MAX_MMAP_SIZE; sqlite3OsFileControlHint( *ppFile, SQLITE_FCNTL_MMAP_SIZE, (void*)&max); } return rc; } /* ** Merge the two sorted lists p1 and p2 into a single list. ** Set *ppOut to the head of the new list. */ static void vdbeSorterMerge( SorterThread *pThread, /* Calling thread context */ SorterRecord *p1, /* First list to merge */ SorterRecord *p2, /* Second list to merge */ SorterRecord **ppOut /* OUT: Head of merged list */ ){ SorterRecord *pFinal = 0; SorterRecord **pp = &pFinal; void *pVal2 = p2 ? SRVAL(p2) : 0; while( p1 && p2 ){ int res; vdbeSorterCompare(pThread, 0, SRVAL(p1), p1->nVal, pVal2, p2->nVal, &res); if( res<=0 ){ *pp = p1; pp = &p1->u.pNext; p1 = p1->u.pNext; pVal2 = 0; }else{ *pp = p2; pp = &p2->u.pNext; p2 = p2->u.pNext; if( p2==0 ) break; pVal2 = SRVAL(p2); } } *pp = p1 ? p1 : p2; *ppOut = pFinal; } /* |
︙ | ︙ | |||
759 760 761 762 763 764 765 | aSlot = (SorterRecord **)sqlite3MallocZero(64 * sizeof(SorterRecord *)); if( !aSlot ){ return SQLITE_NOMEM; } p = pThread->pList; while( p ){ | | > > | > > > > > > > > > | 833 834 835 836 837 838 839 840 841 842 843 844 845 846 847 848 849 850 851 852 853 854 855 856 857 858 859 | aSlot = (SorterRecord **)sqlite3MallocZero(64 * sizeof(SorterRecord *)); if( !aSlot ){ return SQLITE_NOMEM; } p = pThread->pList; while( p ){ SorterRecord *pNext; if( pThread->aListMemory ){ if( (u8*)p==pThread->aListMemory ){ pNext = 0; }else{ assert( p->u.iNext<sqlite3MallocSize(pThread->aListMemory) ); pNext = (SorterRecord*)&pThread->aListMemory[p->u.iNext]; } }else{ pNext = p->u.pNext; } p->u.pNext = 0; for(i=0; aSlot[i]; i++){ vdbeSorterMerge(pThread, p, aSlot[i], &p); aSlot[i] = 0; } aSlot[i] = p; p = pNext; } |
︙ | ︙ | |||
862 863 864 865 866 867 868 869 870 871 872 873 874 875 | */ static void fileWriterWriteVarint(FileWriter *p, u64 iVal){ int nByte; u8 aByte[10]; nByte = sqlite3PutVarint(aByte, iVal); fileWriterWrite(p, aByte, nByte); } /* ** Write the current contents of the in-memory linked-list to a PMA. Return ** SQLITE_OK if successful, or an SQLite error code otherwise. ** ** The format of a PMA is: ** | > > > > > > > > > > > > > > > > > > > > > > > > | 947 948 949 950 951 952 953 954 955 956 957 958 959 960 961 962 963 964 965 966 967 968 969 970 971 972 973 974 975 976 977 978 979 980 981 982 983 984 | */ static void fileWriterWriteVarint(FileWriter *p, u64 iVal){ int nByte; u8 aByte[10]; nByte = sqlite3PutVarint(aByte, iVal); fileWriterWrite(p, aByte, nByte); } #if SQLITE_MAX_MMAP_SIZE>0 /* ** The first argument is a file-handle open on a temporary file. The file ** is guaranteed to be nByte bytes or smaller in size. This function ** attempts to extend the file to nByte bytes in size and to ensure that ** the VFS has memory mapped it. ** ** Whether or not the file does end up memory mapped of course depends on ** the specific VFS implementation. */ static int vdbeSorterExtendFile(sqlite3_file *pFile, i64 nByte){ int rc = sqlite3OsTruncate(pFile, nByte); if( rc==SQLITE_OK ){ void *p = 0; sqlite3OsFetch(pFile, 0, nByte, &p); sqlite3OsUnfetch(pFile, 0, p); } return rc; } #else # define vdbeSorterExtendFile(x,y) SQLITE_OK #endif /* ** Write the current contents of the in-memory linked-list to a PMA. Return ** SQLITE_OK if successful, or an SQLite error code otherwise. ** ** The format of a PMA is: ** |
︙ | ︙ | |||
890 891 892 893 894 895 896 897 898 899 900 901 902 903 904 905 | /* If the first temporary PMA file has not been opened, open it now. */ if( pThread->pTemp1==0 ){ rc = vdbeSorterOpenTempFile(pThread->pVfs, &pThread->pTemp1); assert( rc!=SQLITE_OK || pThread->pTemp1 ); assert( pThread->iTemp1Off==0 ); assert( pThread->nPMA==0 ); } if( rc==SQLITE_OK ){ SorterRecord *p; SorterRecord *pNext = 0; fileWriterInit(pThread->pTemp1, &writer, pThread->pgsz, pThread->iTemp1Off); pThread->nPMA++; fileWriterWriteVarint(&writer, pThread->nInMemory); for(p=pThread->pList; p; p=pNext){ | > > > > > > > | | | > | 999 1000 1001 1002 1003 1004 1005 1006 1007 1008 1009 1010 1011 1012 1013 1014 1015 1016 1017 1018 1019 1020 1021 1022 1023 1024 1025 1026 1027 1028 1029 1030 1031 1032 1033 1034 1035 1036 1037 1038 | /* If the first temporary PMA file has not been opened, open it now. */ if( pThread->pTemp1==0 ){ rc = vdbeSorterOpenTempFile(pThread->pVfs, &pThread->pTemp1); assert( rc!=SQLITE_OK || pThread->pTemp1 ); assert( pThread->iTemp1Off==0 ); assert( pThread->nPMA==0 ); } /* Try to get the file to memory map */ if( rc==SQLITE_OK ){ rc = vdbeSorterExtendFile( pThread->pTemp1, pThread->iTemp1Off + pThread->nInMemory + 9 ); } if( rc==SQLITE_OK ){ SorterRecord *p; SorterRecord *pNext = 0; fileWriterInit(pThread->pTemp1, &writer, pThread->pgsz, pThread->iTemp1Off); pThread->nPMA++; fileWriterWriteVarint(&writer, pThread->nInMemory); for(p=pThread->pList; p; p=pNext){ pNext = p->u.pNext; fileWriterWriteVarint(&writer, p->nVal); fileWriterWrite(&writer, SRVAL(p), p->nVal); if( pThread->aListMemory==0 ) sqlite3_free(p); } pThread->pList = p; rc = fileWriterFinish(&writer, &pThread->iTemp1Off); } assert( pThread->pList==0 || rc!=SQLITE_OK ); return rc; } /* ** Advance the SorterMerger iterator passed as the second argument to ** the next entry. Set *pbEof to true if this means the iterator has ** reached EOF. |
︙ | ︙ | |||
962 963 964 965 966 967 968 969 970 971 972 973 974 975 | pThread->pKeyInfo, 0, 0, &pFree ); assert( pThread->pUnpacked==(UnpackedRecord*)pFree ); if( pFree==0 ){ rc = SQLITE_NOMEM; goto thread_out; } } if( pThread->eWork==SORTER_THREAD_CONS ){ assert( pThread->pList==0 ); while( pThread->nPMA>pThread->nConsolidate && rc==SQLITE_OK ){ int nIter = MIN(pThread->nPMA, SORTER_MAX_MERGE_COUNT); sqlite3_file *pTemp2 = 0; /* Second temp file to use */ | > | 1079 1080 1081 1082 1083 1084 1085 1086 1087 1088 1089 1090 1091 1092 1093 | pThread->pKeyInfo, 0, 0, &pFree ); assert( pThread->pUnpacked==(UnpackedRecord*)pFree ); if( pFree==0 ){ rc = SQLITE_NOMEM; goto thread_out; } pThread->pUnpacked->nField = pThread->pKeyInfo->nField; } if( pThread->eWork==SORTER_THREAD_CONS ){ assert( pThread->pList==0 ); while( pThread->nPMA>pThread->nConsolidate && rc==SQLITE_OK ){ int nIter = MIN(pThread->nPMA, SORTER_MAX_MERGE_COUNT); sqlite3_file *pTemp2 = 0; /* Second temp file to use */ |
︙ | ︙ | |||
983 984 985 986 987 988 989 990 991 992 993 994 995 996 | if( pMerger==0 ){ rc = SQLITE_NOMEM; break; } /* Open a second temp file to write merged data to */ rc = vdbeSorterOpenTempFile(pThread->pVfs, &pTemp2); if( rc!=SQLITE_OK ){ vdbeSorterMergerFree(pMerger); break; } /* This loop runs once for each output PMA. Each output PMA is made ** of data merged from up to SORTER_MAX_MERGE_COUNT input PMAs. */ | > > > | 1101 1102 1103 1104 1105 1106 1107 1108 1109 1110 1111 1112 1113 1114 1115 1116 1117 | if( pMerger==0 ){ rc = SQLITE_NOMEM; break; } /* Open a second temp file to write merged data to */ rc = vdbeSorterOpenTempFile(pThread->pVfs, &pTemp2); if( rc==SQLITE_OK ){ rc = vdbeSorterExtendFile(pTemp2, pThread->iTemp1Off); } if( rc!=SQLITE_OK ){ vdbeSorterMergerFree(pMerger); break; } /* This loop runs once for each output PMA. Each output PMA is made ** of data merged from up to SORTER_MAX_MERGE_COUNT input PMAs. */ |
︙ | ︙ | |||
1090 1091 1092 1093 1094 1095 1096 1097 1098 1099 1100 1101 1102 1103 | rc = SQLITE_PTR_TO_INT(pRet); } } if( pThread->pThread==0 ) break; } if( rc==SQLITE_OK ){ assert( pThread->pThread==0 && pThread->bDone==0 ); pThread->eWork = SORTER_THREAD_TO_PMA; pThread->pList = pSorter->pRecord; pThread->nInMemory = pSorter->nInMemory; pSorter->nInMemory = 0; pSorter->pRecord = 0; | > > > > > > > | > > > > > > > > > > > > | | > < < < < < < < | < | | > > > | > > > | > > > | > > | | | > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > | 1211 1212 1213 1214 1215 1216 1217 1218 1219 1220 1221 1222 1223 1224 1225 1226 1227 1228 1229 1230 1231 1232 1233 1234 1235 1236 1237 1238 1239 1240 1241 1242 1243 1244 1245 1246 1247 1248 1249 1250 1251 1252 1253 1254 1255 1256 1257 1258 1259 1260 1261 1262 1263 1264 1265 1266 1267 1268 1269 1270 1271 1272 1273 1274 1275 1276 1277 1278 1279 1280 1281 1282 1283 1284 1285 1286 1287 1288 1289 1290 1291 1292 1293 1294 1295 1296 1297 1298 1299 1300 1301 1302 1303 1304 1305 1306 1307 1308 1309 1310 1311 1312 1313 1314 1315 1316 1317 1318 1319 1320 1321 1322 1323 1324 1325 1326 1327 1328 1329 1330 1331 1332 1333 1334 1335 1336 1337 1338 1339 1340 1341 1342 1343 1344 1345 1346 | rc = SQLITE_PTR_TO_INT(pRet); } } if( pThread->pThread==0 ) break; } if( rc==SQLITE_OK ){ int bUseFg = (bFg || i==(SQLITE_MAX_SORTER_THREAD-1)); assert( pThread->pThread==0 && pThread->bDone==0 ); pThread->eWork = SORTER_THREAD_TO_PMA; pThread->pList = pSorter->pRecord; pThread->nInMemory = pSorter->nInMemory; pSorter->nInMemory = 0; pSorter->pRecord = 0; if( pSorter->aMemory ){ u8 *aMem = pThread->aListMemory; pThread->aListMemory = pSorter->aMemory; pSorter->aMemory = aMem; } if( bUseFg==0 ){ /* Launch a background thread for this operation */ void *pCtx = (void*)pThread; if( pSorter->aMemory==0 ){ pSorter->aMemory = sqlite3Malloc(pSorter->nMemory); if( pSorter->aMemory==0 ) return SQLITE_NOMEM; }else{ pSorter->nMemory = sqlite3MallocSize(pSorter->aMemory); } rc = sqlite3ThreadCreate(&pThread->pThread, vdbeSorterThreadMain, pCtx); }else{ /* Use the foreground thread for this operation */ u8 *aMem; rc = vdbeSorterRunThread(pThread); aMem = pThread->aListMemory; pThread->aListMemory = pSorter->aMemory; pSorter->aMemory = aMem; } } return rc; } /* ** Add a record to the sorter. */ int sqlite3VdbeSorterWrite( sqlite3 *db, /* Database handle */ const VdbeCursor *pCsr, /* Sorter cursor */ Mem *pVal /* Memory cell containing record */ ){ VdbeSorter *pSorter = pCsr->pSorter; int rc = SQLITE_OK; /* Return Code */ SorterRecord *pNew; /* New list element */ int bFlush; /* True to flush contents of memory to PMA */ int nReq; /* Bytes of memory required */ int nPMA; /* Bytes of PMA space required */ assert( pSorter ); /* Figure out whether or not the current contents of memory should be ** flushed to a PMA before continuing. If so, do so. ** ** If using the single large allocation mode (pSorter->aMemory!=0), then ** flush the contents of memory to a new PMA if (a) at least one value is ** already in memory and (b) the new value will not fit in memory. ** ** Or, if using separate allocations for each record, flush the contents ** of memory to a PMA if either of the following are true: ** ** * The total memory allocated for the in-memory list is greater ** than (page-size * cache-size), or ** ** * The total memory allocated for the in-memory list is greater ** than (page-size * 10) and sqlite3HeapNearlyFull() returns true. */ nReq = pVal->n + sizeof(SorterRecord); nPMA = pVal->n + sqlite3VarintLen(pVal->n); if( pSorter->aMemory ){ bFlush = pSorter->iMemory && (pSorter->iMemory+nReq) > pSorter->mxPmaSize; }else{ bFlush = ( (pSorter->nInMemory > pSorter->mxPmaSize) || (pSorter->nInMemory > pSorter->mnPmaSize && sqlite3HeapNearlyFull()) ); } if( bFlush ){ rc = vdbeSorterFlushPMA(db, pCsr, 0); pSorter->nInMemory = 0; pSorter->iMemory = 0; assert( rc!=SQLITE_OK || pSorter->pRecord==0 ); } pSorter->nInMemory += nPMA; if( pSorter->aMemory ){ int nMin = pSorter->iMemory + nReq; if( nMin>pSorter->nMemory ){ u8 *aNew; int nNew = pSorter->nMemory * 2; while( nNew < nMin ) nNew = nNew*2; if( nNew > pSorter->mxPmaSize ) nNew = pSorter->mxPmaSize; if( nNew < nMin ) nNew = nMin; aNew = sqlite3Realloc(pSorter->aMemory, nNew); if( !aNew ) return SQLITE_NOMEM; pSorter->pRecord = aNew + ((u8*)pSorter->pRecord - pSorter->aMemory); pSorter->aMemory = aNew; pSorter->nMemory = nNew; } pNew = (SorterRecord*)&pSorter->aMemory[pSorter->iMemory]; pSorter->iMemory += ROUND8(nReq); pNew->u.iNext = (u8*)(pSorter->pRecord) - pSorter->aMemory; }else{ pNew = (SorterRecord *)sqlite3Malloc(pVal->n+sizeof(SorterRecord)); if( pNew==0 ){ return SQLITE_NOMEM; } pNew->u.pNext = pSorter->pRecord; } memcpy(SRVAL(pNew), pVal->z, pVal->n); pNew->nVal = pVal->n; pSorter->pRecord = pNew; return rc; } /* ** Return the total number of PMAs in all temporary files. */ |
︙ | ︙ | |||
1185 1186 1187 1188 1189 1190 1191 1192 1193 1194 1195 1196 1197 1198 1199 | ** from the in-memory list. */ if( pSorter->bUsePMA==0 ){ if( pSorter->pRecord ){ SorterThread *pThread = &pSorter->aThread[0]; *pbEof = 0; pThread->pList = pSorter->pRecord; pThread->eWork = SORTER_THREAD_SORT; rc = vdbeSorterRunThread(pThread); pSorter->pRecord = pThread->pList; pThread->pList = 0; }else{ *pbEof = 1; } return rc; } | > > > | 1368 1369 1370 1371 1372 1373 1374 1375 1376 1377 1378 1379 1380 1381 1382 1383 1384 1385 | ** from the in-memory list. */ if( pSorter->bUsePMA==0 ){ if( pSorter->pRecord ){ SorterThread *pThread = &pSorter->aThread[0]; *pbEof = 0; pThread->pList = pSorter->pRecord; pThread->eWork = SORTER_THREAD_SORT; assert( pThread->aListMemory==0 ); pThread->aListMemory = pSorter->aMemory; rc = vdbeSorterRunThread(pThread); pThread->aListMemory = 0; pSorter->pRecord = pThread->pList; pThread->pList = 0; }else{ *pbEof = 1; } return rc; } |
︙ | ︙ | |||
1278 1279 1280 1281 1282 1283 1284 | VdbeSorter *pSorter = pCsr->pSorter; int rc; /* Return code */ if( pSorter->pMerger ){ rc = vdbeSorterNext(&pSorter->aThread[0], pSorter->pMerger, pbEof); }else{ SorterRecord *pFree = pSorter->pRecord; | | | | | 1464 1465 1466 1467 1468 1469 1470 1471 1472 1473 1474 1475 1476 1477 1478 1479 1480 | VdbeSorter *pSorter = pCsr->pSorter; int rc; /* Return code */ if( pSorter->pMerger ){ rc = vdbeSorterNext(&pSorter->aThread[0], pSorter->pMerger, pbEof); }else{ SorterRecord *pFree = pSorter->pRecord; pSorter->pRecord = pFree->u.pNext; pFree->u.pNext = 0; if( pSorter->aMemory==0 ) vdbeSorterRecordFree(db, pFree); *pbEof = !pSorter->pRecord; rc = SQLITE_OK; } return rc; } /* |
︙ | ︙ | |||
1303 1304 1305 1306 1307 1308 1309 | if( pSorter->pMerger ){ VdbeSorterIter *pIter; pIter = &pSorter->pMerger->aIter[ pSorter->pMerger->aTree[1] ]; *pnKey = pIter->nKey; pKey = pIter->aKey; }else{ *pnKey = pSorter->pRecord->nVal; | | | 1489 1490 1491 1492 1493 1494 1495 1496 1497 1498 1499 1500 1501 1502 1503 | if( pSorter->pMerger ){ VdbeSorterIter *pIter; pIter = &pSorter->pMerger->aIter[ pSorter->pMerger->aTree[1] ]; *pnKey = pIter->nKey; pKey = pIter->aKey; }else{ *pnKey = pSorter->pRecord->nVal; pKey = SRVAL(pSorter->pRecord); } return pKey; } /* ** Copy the current sorter key into the memory cell pOut. */ |
︙ | ︙ |
Changes to src/where.c.
︙ | ︙ | |||
4324 4325 4326 4327 4328 4329 4330 4331 4332 4333 4334 4335 4336 | && (pProbe->szIdxRow<pTab->szTabRow) && (pWInfo->wctrlFlags & WHERE_ONEPASS_DESIRED)==0 && sqlite3GlobalConfig.bUseCis && OptimizationEnabled(pWInfo->pParse->db, SQLITE_CoverIdxScan) ) ){ pNew->iSortIdx = b ? iSortIdx : 0; if( m==0 ){ /* TUNING: Cost of a covering index scan is K*(N + log2(N)). ** + The extra factor K of between 1.1 and 3.0 that depends ** on the relative sizes of the table and the index. K ** is smaller for smaller indices, thus favoring them. */ | > > > > > > > < | | | > > > > > > > > > > | | 4324 4325 4326 4327 4328 4329 4330 4331 4332 4333 4334 4335 4336 4337 4338 4339 4340 4341 4342 4343 4344 4345 4346 4347 4348 4349 4350 4351 4352 4353 4354 4355 4356 4357 4358 4359 4360 4361 4362 4363 4364 4365 | && (pProbe->szIdxRow<pTab->szTabRow) && (pWInfo->wctrlFlags & WHERE_ONEPASS_DESIRED)==0 && sqlite3GlobalConfig.bUseCis && OptimizationEnabled(pWInfo->pParse->db, SQLITE_CoverIdxScan) ) ){ pNew->iSortIdx = b ? iSortIdx : 0; /* TUNING: The base cost of an index scan is N + log2(N). ** The log2(N) is for the initial seek to the beginning and the N ** is for the scan itself. */ pNew->rRun = sqlite3LogEstAdd(rSize, rLogSize); if( m==0 ){ /* TUNING: Cost of a covering index scan is K*(N + log2(N)). ** + The extra factor K of between 1.1 and 3.0 that depends ** on the relative sizes of the table and the index. K ** is smaller for smaller indices, thus favoring them. ** The upper bound on K (3.0) matches the penalty factor ** on a full table scan that tries to encourage the use of ** indexed lookups over full scans. */ pNew->rRun += 1 + (15*pProbe->szIdxRow)/pTab->szTabRow; }else{ /* TUNING: The cost of scanning a non-covering index is multiplied ** by log2(N) to account for the binary search of the main table ** that must happen for each row of the index. ** TODO: Should there be a multiplier here, analogous to the 3x ** multiplier for a fulltable scan or covering index scan, to ** further discourage the use of an index scan? Or is the log2(N) ** term sufficient discouragement? ** TODO: What if some or all of the WHERE clause terms can be ** computed without reference to the original table. Then the ** penality should reduce to logK where K is the number of output ** rows. */ pNew->rRun += rLogSize; } whereLoopOutputAdjust(pWC, pNew); rc = whereLoopInsert(pBuilder, pNew); pNew->nOut = rSize; if( rc ) break; } } |
︙ | ︙ | |||
4916 4917 4918 4919 4920 4921 4922 | if( mTerm==0 && !sqlite3ExprIsConstant(p) ) continue; if( (mTerm&~orderDistinctMask)==0 ){ obSat |= MASKBIT(i); } } } } /* End the loop over all WhereLoops from outer-most down to inner-most */ | | | 4932 4933 4934 4935 4936 4937 4938 4939 4940 4941 4942 4943 4944 4945 4946 | if( mTerm==0 && !sqlite3ExprIsConstant(p) ) continue; if( (mTerm&~orderDistinctMask)==0 ){ obSat |= MASKBIT(i); } } } } /* End the loop over all WhereLoops from outer-most down to inner-most */ if( obSat==obDone ) return (i8)nOrderBy; if( !isOrderDistinct ){ for(i=nOrderBy-1; i>0; i--){ Bitmask m = MASKBIT(i) - 1; if( (obSat&m)==m ) return i; } return 0; } |
︙ | ︙ | |||
5037 5038 5039 5040 5041 5042 5043 | nOut = pFrom->nRow + pWLoop->nOut; maskNew = pFrom->maskLoop | pWLoop->maskSelf; if( isOrdered<0 ){ isOrdered = wherePathSatisfiesOrderBy(pWInfo, pWInfo->pOrderBy, pFrom, pWInfo->wctrlFlags, iLoop, pWLoop, &revMask); if( isOrdered>=0 && isOrdered<nOrderBy ){ | | > | > > > > | > > > | | | 5053 5054 5055 5056 5057 5058 5059 5060 5061 5062 5063 5064 5065 5066 5067 5068 5069 5070 5071 5072 5073 5074 5075 5076 5077 5078 5079 | nOut = pFrom->nRow + pWLoop->nOut; maskNew = pFrom->maskLoop | pWLoop->maskSelf; if( isOrdered<0 ){ isOrdered = wherePathSatisfiesOrderBy(pWInfo, pWInfo->pOrderBy, pFrom, pWInfo->wctrlFlags, iLoop, pWLoop, &revMask); if( isOrdered>=0 && isOrdered<nOrderBy ){ /* TUNING: Estimated cost of sorting is N*log(N). ** If the order-by clause has X terms but only the last Y terms ** are out of order, then block-sorting will reduce the sorting ** cost to N*log(N)*log(Y/X). The log(Y/X) term is computed ** by rScale. ** TODO: Should the sorting cost get a small multiplier to help ** discourage the use of sorting and encourage the use of index ** scans instead? */ LogEst rScale, rSortCost; assert( nOrderBy>0 ); rScale = sqlite3LogEst((nOrderBy-isOrdered)*100/nOrderBy) - 66; rSortCost = nRowEst + estLog(nRowEst) + rScale; /* TUNING: The cost of implementing DISTINCT using a B-TREE is ** also N*log(N) but it has a larger constant of proportionality. ** Multiply by 3.0. */ if( pWInfo->wctrlFlags & WHERE_WANT_DISTINCT ){ rSortCost += 16; } WHERETRACE(0x002, |
︙ | ︙ |
Changes to test/corruptG.test.
︙ | ︙ | |||
43 44 45 46 47 48 49 | sqlite3 db test.db # Try to use the file. do_test 1.2 { catchsql { SELECT c FROM t1 WHERE a>'abc'; } | | | < | < < < < | 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 | sqlite3 db test.db # Try to use the file. do_test 1.2 { catchsql { SELECT c FROM t1 WHERE a>'abc'; } } {1 {database disk image is malformed}} do_test 1.3 { catchsql { PRAGMA integrity_check } } {1 {database disk image is malformed}} do_test 1.4 { catchsql { SELECT c FROM t1 ORDER BY a; } } {1 {database disk image is malformed}} # Corrupt the same file in a slightly different way. Make the record header # sane, but corrupt one of the serial_type value to indicate a huge payload # such that the payload begins in allocated space but overflows the buffer. # db close hexio_write test.db [expr {$idxroot*512-15}] 0513ff7f01 sqlite3 db test.db do_test 2.1 { catchsql { SELECT rowid FROM t1 WHERE a='abc' and b='xyz123456789XYZ'; } } {1 {database disk image is malformed}} finish_test |
Changes to test/corruptI.test.
︙ | ︙ | |||
47 48 49 50 51 52 53 | do_test 1.3 { db close set offset [hexio_get_int [hexio_read test.db [expr 2*1024 + 8] 2]] set off [expr 2*1024 + $offset + 1] hexio_write test.db $off FFFF7f02 sqlite3 db test.db catchsql { SELECT * FROM t1 WHERE a = 10 } | | | 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 | do_test 1.3 { db close set offset [hexio_get_int [hexio_read test.db [expr 2*1024 + 8] 2]] set off [expr 2*1024 + $offset + 1] hexio_write test.db $off FFFF7f02 sqlite3 db test.db catchsql { SELECT * FROM t1 WHERE a = 10 } } {1 {database disk image is malformed}} do_test 2.0 { execsql { CREATE TABLE r(x); INSERT INTO r VALUES('ABCDEFGHIJK'); CREATE INDEX r1 ON r(x); } |
︙ | ︙ |
Changes to test/sort.test.
︙ | ︙ | |||
459 460 461 462 463 464 465 466 467 | insert into b values (2, 1, 'xxx'); insert into b values (1, 1, 'zzz'); insert into b values (3, 1, 'yyy'); select a.id, b.id, b.text from a join b on (a.id = b.aId) order by a.id, b.text; } } {1 2 xxx 1 3 yyy 1 1 zzz} finish_test | > > > > > > > > > > > > > > > > > > > > > > | 459 460 461 462 463 464 465 466 467 468 469 470 471 472 473 474 475 476 477 478 479 480 481 482 483 484 485 486 487 488 489 | insert into b values (2, 1, 'xxx'); insert into b values (1, 1, 'zzz'); insert into b values (3, 1, 'yyy'); select a.id, b.id, b.text from a join b on (a.id = b.aId) order by a.id, b.text; } } {1 2 xxx 1 3 yyy 1 1 zzz} #------------------------------------------------------------------------- # Check that the sorter in vdbesort.c sorts in a stable fashion. # do_execsql_test sort-13.0 { CREATE TABLE t10(a, b); } do_test sort-13.1 { db transaction { for {set i 0} {$i < 100000} {incr i} { execsql { INSERT INTO t10 VALUES( $i/10, $i%10 ) } } } } {} do_execsql_test sort-13.2 { SELECT a, b FROM t10 ORDER BY a; } [db eval {SELECT a, b FROM t10 ORDER BY a, b}] do_execsql_test sort-13.3 { PRAGMA cache_size = 5; SELECT a, b FROM t10 ORDER BY a; } [db eval {SELECT a, b FROM t10 ORDER BY a, b}] finish_test |
Changes to test/tester.tcl.
︙ | ︙ | |||
1072 1073 1074 1075 1076 1077 1078 1079 1080 1081 1082 1083 1084 1085 | set G "" set B "" set D "" } foreach opcode { Seek SeekGe SeekGt SeekLe SeekLt NotFound Last Rewind NoConflict Next Prev VNext VPrev VFilter } { set color($opcode) $B } foreach opcode {ResultRow} { set color($opcode) $G } foreach opcode {IdxInsert Insert Delete IdxDelete} { | > | 1072 1073 1074 1075 1076 1077 1078 1079 1080 1081 1082 1083 1084 1085 1086 | set G "" set B "" set D "" } foreach opcode { Seek SeekGe SeekGt SeekLe SeekLt NotFound Last Rewind NoConflict Next Prev VNext VPrev VFilter SorterSort SorterNext } { set color($opcode) $B } foreach opcode {ResultRow} { set color($opcode) $G } foreach opcode {IdxInsert Insert Delete IdxDelete} { |
︙ | ︙ | |||
1094 1095 1096 1097 1098 1099 1100 1101 1102 1103 1104 1105 1106 1107 | if {$opcode == "Goto" && ($bSeenGoto==0 || ($p2 > $addr+10))} { set linebreak($p2) 1 set bSeenGoto 1 } if {$opcode=="Next" || $opcode=="Prev" || $opcode=="VNext" || $opcode=="VPrev" } { for {set i $p2} {$i<$addr} {incr i} { incr x($i) 2 } } if {$opcode == "Goto" && $p2<$addr && $op($p2)=="Yield"} { | > | 1095 1096 1097 1098 1099 1100 1101 1102 1103 1104 1105 1106 1107 1108 1109 | if {$opcode == "Goto" && ($bSeenGoto==0 || ($p2 > $addr+10))} { set linebreak($p2) 1 set bSeenGoto 1 } if {$opcode=="Next" || $opcode=="Prev" || $opcode=="VNext" || $opcode=="VPrev" || $opcode=="SorterNext" } { for {set i $p2} {$i<$addr} {incr i} { incr x($i) 2 } } if {$opcode == "Goto" && $p2<$addr && $op($p2)=="Yield"} { |
︙ | ︙ |
Changes to test/wal64k.test.
︙ | ︙ | |||
14 15 16 17 18 19 20 21 22 23 24 25 26 27 | # set testdir [file dirname $argv0] source $testdir/tester.tcl set testprefix wal64k ifcapable !wal {finish_test ; return } db close test_syscall pagesize 65536 sqlite3 db test.db do_execsql_test 1.0 { PRAGMA journal_mode = WAL; | > > > > > | 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 | # set testdir [file dirname $argv0] source $testdir/tester.tcl set testprefix wal64k ifcapable !wal {finish_test ; return } if {$tcl_platform(platform) != "unix"} { finish_test return } db close test_syscall pagesize 65536 sqlite3 db test.db do_execsql_test 1.0 { PRAGMA journal_mode = WAL; |
︙ | ︙ | |||
40 41 42 43 44 45 46 | } {131072} integrity_check 1.3 db close test_syscall pagesize -1 finish_test | < | 45 46 47 48 49 50 51 | } {131072} integrity_check 1.3 db close test_syscall pagesize -1 finish_test |
Changes to tool/logest.c.
︙ | ︙ | |||
13 14 15 16 17 18 19 | ** integers and LogEst values and back again and for doing simple ** arithmetic operations (multiple and add) on LogEst values. ** ** Usage: ** ** ./LogEst ARGS ** | | < < < < < < | 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 | ** integers and LogEst values and back again and for doing simple ** arithmetic operations (multiple and add) on LogEst values. ** ** Usage: ** ** ./LogEst ARGS ** ** See the showHelp() routine for a description of valid arguments. ** Examples: ** ** To convert 123 from LogEst to integer: ** ** ./LogEst ^123 ** ** To convert 123456 from integer to LogEst: |
︙ | ︙ | |||
92 93 94 95 96 97 98 99 | if( x<1.0 ) return -logEstFromDouble(1/x); if( x<1024.0 ) return logEstFromInteger((sqlite3_uint64)(1024.0*x)) - 100; if( x<=2000000000.0 ) return logEstFromInteger((sqlite3_uint64)x); memcpy(&a, &x, 8); e = (a>>52) - 1022; return e*10; } | | | | < | > > > > > | > > > > > > > > > > > > > > > | | > > > > > > > > > > > > > | < > | | | 86 87 88 89 90 91 92 93 94 95 96 97 98 99 100 101 102 103 104 105 106 107 108 109 110 111 112 113 114 115 116 117 118 119 120 121 122 123 124 125 126 127 128 129 130 131 132 133 134 135 136 137 138 139 140 141 142 143 144 145 146 147 148 149 150 151 152 153 154 155 156 157 158 159 160 161 162 163 164 165 166 167 | if( x<1.0 ) return -logEstFromDouble(1/x); if( x<1024.0 ) return logEstFromInteger((sqlite3_uint64)(1024.0*x)) - 100; if( x<=2000000000.0 ) return logEstFromInteger((sqlite3_uint64)x); memcpy(&a, &x, 8); e = (a>>52) - 1022; return e*10; } int isInteger(const char *z){ while( z[0]>='0' && z[0]<='9' ) z++; return z[0]==0; } int isFloat(const char *z){ char c; while( ((c=z[0])>='0' && c<='9') || c=='.' || c=='E' || c=='e' || c=='+' || c=='-' ) z++; return z[0]==0; } static void showHelp(const char *zArgv0){ printf("Usage: %s ARGS...\n", zArgv0); printf("Arguments:\n" " NUM Convert NUM from integer to LogEst and push onto the stack\n" " ^NUM Interpret NUM as a LogEst and push onto stack\n" " x Multiple the top two elements of the stack\n" " + Add the top two elements of the stack\n" " dup Dupliate the top element on the stack\n" " inv Take the reciprocal of the top of stack. N = 1/N.\n" " log Find the LogEst of the number on top of stack\n" " nlogn Compute NlogN where N is the top of stack\n" ); exit(1); } int main(int argc, char **argv){ int i; int n = 0; LogEst a[100]; for(i=1; i<argc; i++){ const char *z = argv[i]; if( strcmp(z,"+")==0 ){ if( n>=2 ){ a[n-2] = logEstAdd(a[n-2],a[n-1]); n--; } }else if( strcmp(z,"x")==0 ){ if( n>=2 ){ a[n-2] = logEstMultiply(a[n-2],a[n-1]); n--; } }else if( strcmp(z,"dup")==0 ){ if( n>0 ){ a[n] = a[n-1]; n++; } }else if( strcmp(z,"log")==0 ){ if( n>0 ) a[n-1] = logEstFromInteger(a[n-1]) - 33; }else if( strcmp(z,"nlogn")==0 ){ if( n>0 ) a[n-1] += logEstFromInteger(a[n-1]) - 33; }else if( strcmp(z,"inv")==0 ){ if( n>0 ) a[n-1] = -a[n-1]; }else if( z[0]=='^' ){ a[n++] = atoi(z+1); }else if( isInteger(z) ){ a[n++] = logEstFromInteger(atoi(z)); }else if( isFloat(z) && z[0]!='-' ){ a[n++] = logEstFromDouble(atof(z)); }else{ showHelp(argv[0]); } } for(i=n-1; i>=0; i--){ if( a[i]<0 ){ printf("%5d (%f)\n", a[i], 1.0/(double)logEstToInt(-a[i])); }else{ sqlite3_uint64 x = logEstToInt(a[i]+100)*100/1024; printf("%5d (%lld.%02lld)\n", a[i], x/100, x%100); } } return 0; } |