Many hyperlinks are disabled.
Use anonymous login
to enable hyperlinks.
Changes In Branch sorter-opt Excluding Merge-Ins
This is equivalent to a diff from 46e00162 to dd62d2de
2016-11-11
| ||
19:08 | Avoid storing redundant fields in sorter records when the sort-key and data have fields in common. (check-in: b835cf3e user: drh tags: trunk) | |
19:01 | Enhance the OP_IdxInsert opcode so that it can used unpacked key values if they are available. Update the code generator to take advantage of this new capability. The speedtest1.c test is about 2.6% faster as a result. Later: This also introduced bug [30027b613b]. Bummer. (check-in: 925840cf user: drh tags: trunk) | |
18:45 | Merge trunk with this branch. (Closed-Leaf check-in: dd62d2de user: dan tags: sorter-opt) | |
18:08 | Reenable the SQLITE_EXPR_REF optimization for "SELECT DISTINCT ... ORDER BY" queries. (check-in: 6e2e9d38 user: dan tags: sorter-opt) | |
17:52 | Merge enhancements and bug-fixes from trunk. (check-in: 5515b827 user: drh tags: unpacked-IdxInsert) | |
17:08 | Fix a problem with switching from wal to rollback mode when SQLITE_DBCONFIG_NO_CKPT_ON_CLOSE is configured. (check-in: 46e00162 user: dan tags: trunk) | |
16:33 | Add the test/ossfuzz.c interface adaptor for OSS-FUZZ. Make previsions for testing the adaptor using fuzzcheck.c. (check-in: 119d6ef8 user: drh tags: trunk) | |
Changes to src/expr.c.
4082 4082 assert( pList!=0 ); 4083 4083 assert( target>0 ); 4084 4084 assert( pParse->pVdbe!=0 ); /* Never gets this far otherwise */ 4085 4085 n = pList->nExpr; 4086 4086 if( !ConstFactorOk(pParse) ) flags &= ~SQLITE_ECEL_FACTOR; 4087 4087 for(pItem=pList->a, i=0; i<n; i++, pItem++){ 4088 4088 Expr *pExpr = pItem->pExpr; 4089 - if( (flags & SQLITE_ECEL_REF)!=0 && (j = pList->a[i].u.x.iOrderByCol)>0 ){ 4090 - sqlite3VdbeAddOp2(v, copyOp, j+srcReg-1, target+i); 4089 + if( (flags & SQLITE_ECEL_REF)!=0 && (j = pItem->u.x.iOrderByCol)>0 ){ 4090 + if( flags & SQLITE_ECEL_OMITREF ){ 4091 + i--; 4092 + n--; 4093 + }else{ 4094 + sqlite3VdbeAddOp2(v, copyOp, j+srcReg-1, target+i); 4095 + } 4091 4096 }else if( (flags & SQLITE_ECEL_FACTOR)!=0 && sqlite3ExprIsConstant(pExpr) ){ 4092 4097 sqlite3ExprCodeAtInit(pParse, pExpr, target+i, 0); 4093 4098 }else{ 4094 4099 int inReg = sqlite3ExprCodeTarget(pParse, pExpr, target+i); 4095 4100 if( inReg!=target+i ){ 4096 4101 VdbeOp *pOp; 4097 4102 if( copyOp==OP_Copy
Changes to src/select.c.
517 517 int regBase; /* Regs for sorter record */ 518 518 int regRecord = ++pParse->nMem; /* Assembled sorter record */ 519 519 int nOBSat = pSort->nOBSat; /* ORDER BY terms to skip */ 520 520 int op; /* Opcode to add sorter record to sorter */ 521 521 int iLimit; /* LIMIT counter */ 522 522 523 523 assert( bSeq==0 || bSeq==1 ); 524 - assert( nData==1 || regData==regOrigData ); 524 + assert( nData==1 || regData==regOrigData || regOrigData==0 ); 525 525 if( nPrefixReg ){ 526 526 assert( nPrefixReg==nExpr+bSeq ); 527 527 regBase = regData - nExpr - bSeq; 528 528 }else{ 529 529 regBase = pParse->nMem + 1; 530 530 pParse->nMem += nBase; 531 531 } 532 532 assert( pSelect->iOffset==0 || pSelect->iLimit!=0 ); 533 533 iLimit = pSelect->iOffset ? pSelect->iOffset+1 : pSelect->iLimit; 534 534 pSort->labelDone = sqlite3VdbeMakeLabel(v); 535 535 sqlite3ExprCodeExprList(pParse, pSort->pOrderBy, regBase, regOrigData, 536 - SQLITE_ECEL_DUP|SQLITE_ECEL_REF); 536 + SQLITE_ECEL_DUP | (regOrigData? SQLITE_ECEL_REF : 0)); 537 537 if( bSeq ){ 538 538 sqlite3VdbeAddOp2(v, OP_Sequence, pSort->iECursor, regBase+nExpr); 539 539 } 540 - if( nPrefixReg==0 ){ 540 + if( nPrefixReg==0 && nData>0 ){ 541 541 sqlite3ExprCodeMove(pParse, regData, regBase+nExpr+bSeq, nData); 542 542 } 543 543 sqlite3VdbeAddOp3(v, OP_MakeRecord, regBase+nOBSat, nBase-nOBSat, regRecord); 544 544 if( nOBSat>0 ){ 545 545 int regPrevKey; /* The first nOBSat columns of the previous row */ 546 546 int addrFirst; /* Address of the OP_IfNot opcode */ 547 547 int addrJmp; /* Address of the OP_Jump opcode */ ................................................................................ 662 662 /* 663 663 ** This routine generates the code for the inside of the inner loop 664 664 ** of a SELECT. 665 665 ** 666 666 ** If srcTab is negative, then the pEList expressions 667 667 ** are evaluated in order to get the data for this row. If srcTab is 668 668 ** zero or more, then data is pulled from srcTab and pEList is used only 669 -** to get number columns and the datatype for each column. 669 +** to get the number of columns and the collation sequence for each column. 670 670 */ 671 671 static void selectInnerLoop( 672 672 Parse *pParse, /* The parser context */ 673 673 Select *p, /* The complete select statement being coded */ 674 674 ExprList *pEList, /* List of values being extracted */ 675 675 int srcTab, /* Pull data from this table */ 676 676 SortCtx *pSort, /* If not NULL, info on how to process ORDER BY */ ................................................................................ 677 677 DistinctCtx *pDistinct, /* If not NULL, info on how to process DISTINCT */ 678 678 SelectDest *pDest, /* How to dispose of the results */ 679 679 int iContinue, /* Jump here to continue with next row */ 680 680 int iBreak /* Jump here to break out of the inner loop */ 681 681 ){ 682 682 Vdbe *v = pParse->pVdbe; 683 683 int i; 684 - int hasDistinct; /* True if the DISTINCT keyword is present */ 685 - int regResult; /* Start of memory holding result set */ 684 + int hasDistinct; /* True if the DISTINCT keyword is present */ 686 685 int eDest = pDest->eDest; /* How to dispose of results */ 687 686 int iParm = pDest->iSDParm; /* First argument to disposal method */ 688 687 int nResultCol; /* Number of result columns */ 689 688 int nPrefixReg = 0; /* Number of extra registers before regResult */ 690 689 690 + /* Usually, regResult is the first cell in an array of memory cells 691 + ** containing the current result row. In this case regOrig is set to the 692 + ** same value. However, if the results are being sent to the sorter, the 693 + ** values for any expressions that are also part of the sort-key are omitted 694 + ** from this array. In this case regOrig is set to zero. */ 695 + int regResult; /* Start of memory holding current results */ 696 + int regOrig; /* Start of memory holding full result (or 0) */ 697 + 691 698 assert( v ); 692 699 assert( pEList!=0 ); 693 700 hasDistinct = pDistinct ? pDistinct->eTnctType : WHERE_DISTINCT_NOOP; 694 701 if( pSort && pSort->pOrderBy==0 ) pSort = 0; 695 702 if( pSort==0 && !hasDistinct ){ 696 703 assert( iContinue!=0 ); 697 704 codeOffset(v, p->iOffset, iContinue); ................................................................................ 714 721 ** on the right-hand side of an INSERT contains more result columns than 715 722 ** there are columns in the table on the left. The error will be caught 716 723 ** and reported later. But we need to make sure enough memory is allocated 717 724 ** to avoid other spurious errors in the meantime. */ 718 725 pParse->nMem += nResultCol; 719 726 } 720 727 pDest->nSdst = nResultCol; 721 - regResult = pDest->iSdst; 728 + regOrig = regResult = pDest->iSdst; 722 729 if( srcTab>=0 ){ 723 730 for(i=0; i<nResultCol; i++){ 724 731 sqlite3VdbeAddOp3(v, OP_Column, srcTab, i, regResult+i); 725 732 VdbeComment((v, "%s", pEList->a[i].zName)); 726 733 } 727 734 }else if( eDest!=SRT_Exists ){ 728 735 /* If the destination is an EXISTS(...) expression, the actual ................................................................................ 730 737 */ 731 738 u8 ecelFlags; 732 739 if( eDest==SRT_Mem || eDest==SRT_Output || eDest==SRT_Coroutine ){ 733 740 ecelFlags = SQLITE_ECEL_DUP; 734 741 }else{ 735 742 ecelFlags = 0; 736 743 } 737 - sqlite3ExprCodeExprList(pParse, pEList, regResult, 0, ecelFlags); 744 + assert( eDest!=SRT_Table || pSort==0 ); 745 + if( pSort && hasDistinct==0 && eDest!=SRT_EphemTab ){ 746 + /* For each expression in pEList that is a copy of an expression in 747 + ** the ORDER BY clause (pSort->pOrderBy), set the associated 748 + ** iOrderByCol value to one more than the index of the ORDER BY 749 + ** expression within the sort-key that pushOntoSorter() will generate. 750 + ** This allows the pEList field to be omitted from the sorted record, 751 + ** saving space and CPU cycles. */ 752 + ecelFlags |= (SQLITE_ECEL_OMITREF|SQLITE_ECEL_REF); 753 + for(i=pSort->nOBSat; i<pSort->pOrderBy->nExpr; i++){ 754 + int j; 755 + if( (j = pSort->pOrderBy->a[i].u.x.iOrderByCol)>0 ){ 756 + pEList->a[j-1].u.x.iOrderByCol = i+1-pSort->nOBSat; 757 + } 758 + } 759 + regOrig = 0; 760 + assert( eDest==SRT_Set || eDest==SRT_Mem 761 + || eDest==SRT_Coroutine || eDest==SRT_Output ); 762 + } 763 + nResultCol = sqlite3ExprCodeExprList(pParse,pEList,regResult,0,ecelFlags); 738 764 } 739 765 740 766 /* If the DISTINCT keyword was present on the SELECT statement 741 767 ** and this row has been seen before, then do not make this row 742 768 ** part of the result. 743 769 */ 744 770 if( hasDistinct ){ ................................................................................ 870 896 case SRT_Set: { 871 897 if( pSort ){ 872 898 /* At first glance you would think we could optimize out the 873 899 ** ORDER BY in this case since the order of entries in the set 874 900 ** does not matter. But there might be a LIMIT clause, in which 875 901 ** case the order does matter */ 876 902 pushOntoSorter( 877 - pParse, pSort, p, regResult, regResult, nResultCol, nPrefixReg); 903 + pParse, pSort, p, regResult, regOrig, nResultCol, nPrefixReg); 878 904 }else{ 879 905 int r1 = sqlite3GetTempReg(pParse); 880 906 assert( sqlite3Strlen30(pDest->zAffSdst)==nResultCol ); 881 907 sqlite3VdbeAddOp4(v, OP_MakeRecord, regResult, nResultCol, 882 908 r1, pDest->zAffSdst, nResultCol); 883 909 sqlite3ExprCacheAffinityChange(pParse, regResult, nResultCol); 884 910 sqlite3VdbeAddOp2(v, OP_IdxInsert, iParm, r1); ................................................................................ 896 922 } 897 923 898 924 /* If this is a scalar select that is part of an expression, then 899 925 ** store the results in the appropriate memory cell or array of 900 926 ** memory cells and break out of the scan loop. 901 927 */ 902 928 case SRT_Mem: { 903 - assert( nResultCol==pDest->nSdst ); 904 929 if( pSort ){ 930 + assert( nResultCol<=pDest->nSdst ); 905 931 pushOntoSorter( 906 - pParse, pSort, p, regResult, regResult, nResultCol, nPrefixReg); 932 + pParse, pSort, p, regResult, regOrig, nResultCol, nPrefixReg); 907 933 }else{ 934 + assert( nResultCol==pDest->nSdst ); 908 935 assert( regResult==iParm ); 909 936 /* The LIMIT clause will jump out of the loop for us */ 910 937 } 911 938 break; 912 939 } 913 940 #endif /* #ifndef SQLITE_OMIT_SUBQUERY */ 914 941 915 942 case SRT_Coroutine: /* Send data to a co-routine */ 916 943 case SRT_Output: { /* Return the results */ 917 944 testcase( eDest==SRT_Coroutine ); 918 945 testcase( eDest==SRT_Output ); 919 946 if( pSort ){ 920 - pushOntoSorter(pParse, pSort, p, regResult, regResult, nResultCol, 947 + pushOntoSorter(pParse, pSort, p, regResult, regOrig, nResultCol, 921 948 nPrefixReg); 922 949 }else if( eDest==SRT_Coroutine ){ 923 950 sqlite3VdbeAddOp1(v, OP_Yield, pDest->iSDParm); 924 951 }else{ 925 952 sqlite3VdbeAddOp2(v, OP_ResultRow, regResult, nResultCol); 926 953 sqlite3ExprCacheAffinityChange(pParse, regResult, nResultCol); 927 954 } ................................................................................ 1198 1225 int addrOnce = 0; 1199 1226 int iTab; 1200 1227 ExprList *pOrderBy = pSort->pOrderBy; 1201 1228 int eDest = pDest->eDest; 1202 1229 int iParm = pDest->iSDParm; 1203 1230 int regRow; 1204 1231 int regRowid; 1232 + int iCol; 1205 1233 int nKey; 1206 1234 int iSortTab; /* Sorter cursor to read from */ 1207 1235 int nSortData; /* Trailing values to read from sorter */ 1208 1236 int i; 1209 1237 int bSeq; /* True if sorter record includes seq. no. */ 1210 -#ifdef SQLITE_ENABLE_EXPLAIN_COMMENTS 1211 1238 struct ExprList_item *aOutEx = p->pEList->a; 1212 -#endif 1213 1239 1214 1240 assert( addrBreak<0 ); 1215 1241 if( pSort->labelBkOut ){ 1216 1242 sqlite3VdbeAddOp2(v, OP_Gosub, pSort->regReturn, pSort->labelBkOut); 1217 1243 sqlite3VdbeGoto(v, addrBreak); 1218 1244 sqlite3VdbeResolveLabel(v, pSort->labelBkOut); 1219 1245 } ................................................................................ 1243 1269 bSeq = 0; 1244 1270 }else{ 1245 1271 addr = 1 + sqlite3VdbeAddOp2(v, OP_Sort, iTab, addrBreak); VdbeCoverage(v); 1246 1272 codeOffset(v, p->iOffset, addrContinue); 1247 1273 iSortTab = iTab; 1248 1274 bSeq = 1; 1249 1275 } 1250 - for(i=0; i<nSortData; i++){ 1251 - sqlite3VdbeAddOp3(v, OP_Column, iSortTab, nKey+bSeq+i, regRow+i); 1276 + for(i=0, iCol=nKey+bSeq; i<nSortData; i++){ 1277 + int iRead; 1278 + if( aOutEx[i].u.x.iOrderByCol ){ 1279 + iRead = aOutEx[i].u.x.iOrderByCol-1; 1280 + }else{ 1281 + iRead = iCol++; 1282 + } 1283 + sqlite3VdbeAddOp3(v, OP_Column, iSortTab, iRead, regRow+i); 1252 1284 VdbeComment((v, "%s", aOutEx[i].zName ? aOutEx[i].zName : aOutEx[i].zSpan)); 1253 1285 } 1254 1286 switch( eDest ){ 1255 1287 case SRT_EphemTab: { 1256 1288 sqlite3VdbeAddOp2(v, OP_NewRowid, iParm, regRowid); 1257 1289 sqlite3VdbeAddOp3(v, OP_Insert, iParm, regRow, regRowid); 1258 1290 sqlite3VdbeChangeP5(v, OPFLAG_APPEND);
Changes to src/sqliteInt.h.
3702 3702 int sqlite3ExprCodeTemp(Parse*, Expr*, int*); 3703 3703 int sqlite3ExprCodeTarget(Parse*, Expr*, int); 3704 3704 void sqlite3ExprCodeAndCache(Parse*, Expr*, int); 3705 3705 int sqlite3ExprCodeExprList(Parse*, ExprList*, int, int, u8); 3706 3706 #define SQLITE_ECEL_DUP 0x01 /* Deep, not shallow copies */ 3707 3707 #define SQLITE_ECEL_FACTOR 0x02 /* Factor out constant terms */ 3708 3708 #define SQLITE_ECEL_REF 0x04 /* Use ExprList.u.x.iOrderByCol */ 3709 +#define SQLITE_ECEL_OMITREF 0x08 /* Omit if ExprList.u.x.iOrderByCol */ 3709 3710 void sqlite3ExprIfTrue(Parse*, Expr*, int, int); 3710 3711 void sqlite3ExprIfFalse(Parse*, Expr*, int, int); 3711 3712 void sqlite3ExprIfFalseDup(Parse*, Expr*, int, int); 3712 3713 Table *sqlite3FindTable(sqlite3*,const char*, const char*); 3713 3714 #define LOCATE_VIEW 0x01 3714 3715 #define LOCATE_NOERR 0x02 3715 3716 Table *sqlite3LocateTable(Parse*,u32 flags,const char*, const char*);