Many hyperlinks are disabled.
Use anonymous login
to enable hyperlinks.
Changes In Branch skip-scan Excluding Merge-Ins
This is equivalent to a diff from e7d34ec6 to f668616a
2013-11-13
| ||
20:46 | Merge the skip-scan enhancement into trunk. (check-in: b0bb975c user: drh tags: trunk) | |
19:01 | Import the "PRAGMA vdbe_eqp" enhancement and the enhanced EXPLAIN formatting the shell from trunk. Fix a bug in skip-scan and add a test case to prevent a regression. (Closed-Leaf check-in: f668616a user: drh tags: skip-scan) | |
18:35 | In the shell tool, if an "EXPLAIN" command is executed in ".explain on" mode, attempt to automatically indent the bodies of loops in the output VDBE program. (check-in: e7d34ec6 user: dan tags: trunk) | |
17:58 | Add the "PRAGMA vdbe_eqp" command, only available with SQLITE_DEBUG. Simplify some of the other debugging logic. (check-in: 8ce33f4c user: drh tags: trunk) | |
17:24 | Add VDBE comments to the beginning and end of skip-scan loops. (check-in: 0c85d93b user: drh tags: skip-scan) | |
Changes to src/analyze.c.
︙ | |||
1424 1425 1426 1427 1428 1429 1430 | 1424 1425 1426 1427 1428 1429 1430 1431 1432 1433 1434 1435 1436 1437 1438 1439 1440 1441 1442 1443 | - - + + + + - + | if( argv==0 || argv[0]==0 || argv[2]==0 ){ return 0; } pTable = sqlite3FindTable(pInfo->db, argv[0], pInfo->zDatabase); if( pTable==0 ){ return 0; } |
︙ |
Changes to src/shell.c.
︙ | |||
1169 1170 1171 1172 1173 1174 1175 | 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 | - - - + + + + - + | ** ** The indenting rules are: ** ** * For each "Next", "Prev", "VNext" or "VPrev" instruction, indent ** all opcodes that occur between the p2 jump destination and the opcode ** itself by 2 spaces. ** |
︙ |
Changes to src/where.c.
︙ | |||
2418 2419 2420 2421 2422 2423 2424 | 2418 2419 2420 2421 2422 2423 2424 2425 2426 2427 2428 2429 2430 2431 2432 2433 2434 2435 2436 2437 2438 2439 2440 2441 2442 2443 2444 2445 2446 2447 2448 2449 2450 2451 2452 2453 2454 2455 | - + + + + + + - - - + + + + | } disableTerm(pLevel, pTerm); return iReg; } /* ** Generate code that will evaluate all == and IN constraints for an |
︙ | |||
2462 2463 2464 2465 2466 2467 2468 | 2468 2469 2470 2471 2472 2473 2474 2475 2476 2477 2478 2479 2480 2481 2482 2483 2484 2485 2486 2487 2488 2489 2490 2491 2492 2493 2494 2495 2496 2497 2498 2499 2500 2501 2502 2503 2504 2505 2506 2507 2508 2509 2510 2511 2512 2513 2514 2515 2516 2517 2518 2519 2520 2521 2522 2523 2524 2525 2526 2527 2528 2529 2530 2531 2532 2533 2534 | - + + + + + + + + + + + + + + + + + + - + - + | static int codeAllEqualityTerms( Parse *pParse, /* Parsing context */ WhereLevel *pLevel, /* Which nested loop of the FROM we are coding */ int bRev, /* Reverse the order of IN operators */ int nExtraReg, /* Number of extra registers to allocate */ char **pzAff /* OUT: Set to point to affinity string */ ){ |
︙ | |||
2571 2572 2573 2574 2575 2576 2577 | 2594 2595 2596 2597 2598 2599 2600 2601 2602 2603 2604 2605 2606 2607 2608 2609 2610 2611 2612 2613 2614 2615 2616 2617 2618 2619 2620 2621 2622 2623 2624 2625 2626 2627 2628 2629 2630 | - + + + - + + + + + + + | ** ** The returned pointer points to memory obtained from sqlite3DbMalloc(). ** It is the responsibility of the caller to free the buffer when it is ** no longer required. */ static char *explainIndexRange(sqlite3 *db, WhereLoop *pLoop, Table *pTab){ Index *pIndex = pLoop->u.btree.pIndex; |
︙ | |||
2951 2952 2953 2954 2955 2956 2957 | 2982 2983 2984 2985 2986 2987 2988 2989 2990 2991 2992 2993 2994 2995 2996 2997 2998 2999 3000 3001 3002 3003 3004 3005 3006 3007 3008 3009 3010 3011 3012 3013 3014 3015 3016 3017 3018 3019 3020 3021 3022 3023 3024 3025 3026 3027 3028 3029 3030 | - - + + + + - + - | OP_SeekLe /* 7: (start_constraints && startEq && bRev) */ }; static const u8 aEndOp[] = { OP_Noop, /* 0: (!end_constraints) */ OP_IdxGE, /* 1: (end_constraints && !bRev) */ OP_IdxLT /* 2: (end_constraints && bRev) */ }; |
︙ | |||
3535 3536 3537 3538 3539 3540 3541 3542 3543 3544 3545 3546 3547 3548 | 3567 3568 3569 3570 3571 3572 3573 3574 3575 3576 3577 3578 3579 3580 3581 | + | */ if( p->nLTerm && (sqlite3WhereTrace & 0x100)!=0 ){ /* WHERETRACE 0x100 */ int i; Vdbe *v = pWInfo->pParse->pVdbe; sqlite3ExplainBegin(v); for(i=0; i<p->nLTerm; i++){ WhereTerm *pTerm = p->aLTerm[i]; if( pTerm==0 ) continue; sqlite3ExplainPrintf(v, " (%d) #%-2d ", i+1, (int)(pTerm-pWC->a)); sqlite3ExplainPush(v); whereExplainTerm(v, pTerm); sqlite3ExplainPop(v); sqlite3ExplainNL(v); } sqlite3ExplainFinish(v); |
︙ | |||
3818 3819 3820 3821 3822 3823 3824 3825 3826 3827 3828 3829 3830 3831 | 3851 3852 3853 3854 3855 3856 3857 3858 3859 3860 3861 3862 3863 3864 3865 | + | } for(i=pWC->nTerm, pTerm=pWC->a; i>0; i--, pTerm++){ if( (pTerm->wtFlags & TERM_VIRTUAL)!=0 ) break; if( (pTerm->prereqAll & pLoop->maskSelf)==0 ) continue; if( (pTerm->prereqAll & notAllowed)!=0 ) continue; for(j=pLoop->nLTerm-1; j>=0; j--){ pX = pLoop->aLTerm[j]; if( pX==0 ) continue; if( pX==pTerm ) break; if( pX->iParent>=0 && (&pWC->a[pX->iParent])==pTerm ) break; } if( j<0 ) pLoop->nOut += pTerm->truthProb; } } |
︙ | |||
3847 3848 3849 3850 3851 3852 3853 | 3881 3882 3883 3884 3885 3886 3887 3888 3889 3890 3891 3892 3893 3894 3895 3896 | - + + | sqlite3 *db = pParse->db; /* Database connection malloc context */ WhereLoop *pNew; /* Template WhereLoop under construction */ WhereTerm *pTerm; /* A WhereTerm under consideration */ int opMask; /* Valid operators for constraints */ WhereScan scan; /* Iterator for WHERE terms */ Bitmask saved_prereq; /* Original value of pNew->prereq */ u16 saved_nLTerm; /* Original value of pNew->nLTerm */ |
︙ | |||
3882 3883 3884 3885 3886 3887 3888 3889 3890 3891 3892 3893 3894 3895 3896 3897 3898 3899 3900 3901 | 3917 3918 3919 3920 3921 3922 3923 3924 3925 3926 3927 3928 3929 3930 3931 3932 3933 3934 3935 3936 3937 3938 3939 3940 3941 3942 3943 3944 3945 3946 3947 3948 3949 3950 | + + + + + + + + + + + + + + | }else{ iCol = -1; nRowEst = 0; } pTerm = whereScanInit(&scan, pBuilder->pWC, pSrc->iCursor, iCol, opMask, pProbe); saved_nEq = pNew->u.btree.nEq; saved_nSkip = pNew->u.btree.nSkip; saved_nLTerm = pNew->nLTerm; saved_wsFlags = pNew->wsFlags; saved_prereq = pNew->prereq; saved_nOut = pNew->nOut; pNew->rSetup = 0; rLogSize = estLog(sqlite3LogEst(pProbe->aiRowEst[0])); if( pTerm==0 && saved_nEq==saved_nSkip && saved_nEq+1<pProbe->nKeyCol && pProbe->aiRowEst[saved_nEq+1]>50 ){ LogEst nIter; pNew->u.btree.nEq++; pNew->u.btree.nSkip++; pNew->aLTerm[pNew->nLTerm++] = 0; pNew->wsFlags |= WHERE_SKIPSCAN; nIter = sqlite3LogEst(pProbe->aiRowEst[0]/pProbe->aiRowEst[saved_nEq+1]); whereLoopAddBtreeIndex(pBuilder, pSrc, pProbe, nIter); } for(; rc==SQLITE_OK && pTerm!=0; pTerm = whereScanNext(&scan)){ int nIn = 0; #ifdef SQLITE_ENABLE_STAT3_OR_STAT4 int nRecValid = pBuilder->nRecValid; #endif if( (pTerm->eOperator==WO_ISNULL || (pTerm->wtFlags&TERM_VNULL)!=0) && (iCol<0 || pSrc->pTab->aCol[iCol].notNull) |
︙ | |||
3923 3924 3925 3926 3927 3928 3929 | 3972 3973 3974 3975 3976 3977 3978 3979 3980 3981 3982 3983 3984 3985 3986 3987 3988 3989 | + - - + + + | /* "x IN (value, value, ...)" */ nIn = sqlite3LogEst(pExpr->x.pList->nExpr); } pNew->rRun += nIn; pNew->u.btree.nEq++; pNew->nOut = nRowEst + nInMul + nIn; }else if( pTerm->eOperator & (WO_EQ) ){ assert( |
︙ | |||
4005 4006 4007 4008 4009 4010 4011 4012 4013 4014 4015 4016 4017 4018 | 4056 4057 4058 4059 4060 4061 4062 4063 4064 4065 4066 4067 4068 4069 4070 | + | pNew->nOut = saved_nOut; #ifdef SQLITE_ENABLE_STAT3_OR_STAT4 pBuilder->nRecValid = nRecValid; #endif } pNew->prereq = saved_prereq; pNew->u.btree.nEq = saved_nEq; pNew->u.btree.nSkip = saved_nSkip; pNew->wsFlags = saved_wsFlags; pNew->nOut = saved_nOut; pNew->nLTerm = saved_nLTerm; return rc; } /* |
︙ | |||
4151 4152 4153 4154 4155 4156 4157 4158 4159 4160 4161 4162 4163 4164 | 4203 4204 4205 4206 4207 4208 4209 4210 4211 4212 4213 4214 4215 4216 4217 | + | /* Generate auto-index WhereLoops */ WhereTerm *pTerm; WhereTerm *pWCEnd = pWC->a + pWC->nTerm; for(pTerm=pWC->a; rc==SQLITE_OK && pTerm<pWCEnd; pTerm++){ if( pTerm->prereqRight & pNew->maskSelf ) continue; if( termCanDriveIndex(pTerm, pSrc, 0) ){ pNew->u.btree.nEq = 1; pNew->u.btree.nSkip = 0; pNew->u.btree.pIndex = 0; pNew->nLTerm = 1; pNew->aLTerm[0] = pTerm; /* TUNING: One-time cost for computing the automatic index is ** approximately 7*N*log2(N) where N is the number of rows in ** the table being indexed. */ pNew->rSetup = rLogSize + rSize + 28; assert( 28==sqlite3LogEst(7) ); |
︙ | |||
4180 4181 4182 4183 4184 4185 4186 4187 4188 4189 4190 4191 4192 4193 | 4233 4234 4235 4236 4237 4238 4239 4240 4241 4242 4243 4244 4245 4246 4247 | + | */ for(; rc==SQLITE_OK && pProbe; pProbe=pProbe->pNext, iSortIdx++){ if( pProbe->pPartIdxWhere!=0 && !whereUsablePartialIndex(pNew->iTab, pWC, pProbe->pPartIdxWhere) ){ continue; /* Partial index inappropriate for this query */ } pNew->u.btree.nEq = 0; pNew->u.btree.nSkip = 0; pNew->nLTerm = 0; pNew->iSortIdx = 0; pNew->rSetup = 0; pNew->prereq = mExtra; pNew->nOut = rSize; pNew->u.btree.pIndex = pProbe; b = indexMightHelpWithOrderBy(pBuilder, pProbe, pSrc->iCursor); |
︙ | |||
4714 4715 4716 4717 4718 4719 4720 4721 4722 4723 4724 4725 4726 4727 | 4768 4769 4770 4771 4772 4773 4774 4775 4776 4777 4778 4779 4780 4781 4782 | + | rev = revSet = 0; distinctColumns = 0; for(j=0; j<nColumn; j++){ u8 bOnce; /* True to run the ORDER BY search loop */ /* Skip over == and IS NULL terms */ if( j<pLoop->u.btree.nEq && pLoop->u.btree.nSkip==0 && ((i = pLoop->aLTerm[j]->eOperator) & (WO_EQ|WO_ISNULL))!=0 ){ if( i & WO_ISNULL ){ testcase( isOrderDistinct ); isOrderDistinct = 0; } continue; |
︙ | |||
5139 5140 5141 5142 5143 5144 5145 5146 5147 5148 5149 5150 5151 5152 | 5194 5195 5196 5197 5198 5199 5200 5201 5202 5203 5204 5205 5206 5207 5208 | + | pTab = pItem->pTab; if( IsVirtual(pTab) ) return 0; if( pItem->zIndex ) return 0; iCur = pItem->iCursor; pWC = &pWInfo->sWC; pLoop = pBuilder->pNew; pLoop->wsFlags = 0; pLoop->u.btree.nSkip = 0; pTerm = findTerm(pWC, iCur, -1, 0, WO_EQ, 0); if( pTerm ){ pLoop->wsFlags = WHERE_COLUMN_EQ|WHERE_IPK|WHERE_ONEROW; pLoop->aLTerm[0] = pTerm; pLoop->nLTerm = 1; pLoop->u.btree.nEq = 1; /* TUNING: Cost of a rowid lookup is 10 */ |
︙ | |||
5712 5713 5714 5715 5716 5717 5718 5719 5720 5721 5722 5723 5724 5725 5726 5727 5728 5729 5730 5731 5732 5733 5734 5735 5736 5737 5738 | 5768 5769 5770 5771 5772 5773 5774 5775 5776 5777 5778 5779 5780 5781 5782 5783 5784 5785 5786 5787 5788 5789 5790 5791 5792 5793 5794 5795 5796 5797 5798 5799 5800 5801 5802 5803 5804 5805 5806 5807 5808 | + + + + + + + - | sqlite3 *db = pParse->db; /* Generate loop termination code. */ VdbeNoopComment((v, "End WHERE-core")); sqlite3ExprCacheClear(pParse); for(i=pWInfo->nLevel-1; i>=0; i--){ int addr; pLevel = &pWInfo->a[i]; pLoop = pLevel->pWLoop; sqlite3VdbeResolveLabel(v, pLevel->addrCont); if( pLevel->op!=OP_Noop ){ sqlite3VdbeAddOp2(v, pLevel->op, pLevel->p1, pLevel->p2); sqlite3VdbeChangeP5(v, pLevel->p5); } if( pLoop->wsFlags & WHERE_IN_ABLE && pLevel->u.in.nIn>0 ){ struct InLoop *pIn; int j; sqlite3VdbeResolveLabel(v, pLevel->addrNxt); for(j=pLevel->u.in.nIn, pIn=&pLevel->u.in.aInLoop[j-1]; j>0; j--, pIn--){ sqlite3VdbeJumpHere(v, pIn->addrInTop+1); sqlite3VdbeAddOp2(v, pIn->eEndLoopOp, pIn->iCur, pIn->addrInTop); sqlite3VdbeJumpHere(v, pIn->addrInTop-1); } sqlite3DbFree(db, pLevel->u.in.aInLoop); } sqlite3VdbeResolveLabel(v, pLevel->addrBrk); if( pLevel->addrSkip ){ sqlite3VdbeAddOp2(v, OP_Goto, 0, pLevel->addrSkip); VdbeComment((v, "next skip-scan on %s", pLoop->u.btree.pIndex->zName)); sqlite3VdbeJumpHere(v, pLevel->addrSkip); sqlite3VdbeJumpHere(v, pLevel->addrSkip-2); } if( pLevel->iLeftJoin ){ |
︙ |
Changes to src/whereInt.h.
︙ | |||
61 62 63 64 65 66 67 68 69 70 71 72 73 74 | 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 | + | */ struct WhereLevel { int iLeftJoin; /* Memory cell used to implement LEFT OUTER JOIN */ int iTabCur; /* The VDBE cursor used to access the table */ int iIdxCur; /* The VDBE cursor used to access pIdx */ int addrBrk; /* Jump here to break out of the loop */ int addrNxt; /* Jump here to start the next IN combination */ int addrSkip; /* Jump here for next iteration of skip-scan */ int addrCont; /* Jump here to continue with the next loop cycle */ int addrFirst; /* First instruction of interior of the loop */ int addrBody; /* Beginning of the body of this loop */ u8 iFrom; /* Which entry in the FROM clause */ u8 op, p5; /* Opcode and P5 of the opcode that ends the loop */ int p1, p2; /* Operands of the opcode used to ends the loop */ union { /* Information that depends on pWLoop->wsFlags */ |
︙ | |||
451 452 453 454 455 456 457 | 452 453 454 455 456 457 458 459 | + | #define WHERE_IPK 0x00000100 /* x is the INTEGER PRIMARY KEY */ #define WHERE_INDEXED 0x00000200 /* WhereLoop.u.btree.pIndex is valid */ #define WHERE_VIRTUALTABLE 0x00000400 /* WhereLoop.u.vtab is valid */ #define WHERE_IN_ABLE 0x00000800 /* Able to support an IN operator */ #define WHERE_ONEROW 0x00001000 /* Selects no more than one row */ #define WHERE_MULTI_OR 0x00002000 /* OR using multiple indices */ #define WHERE_AUTO_INDEX 0x00004000 /* Uses an ephemeral index */ #define WHERE_SKIPSCAN 0x00008000 /* Uses the skip-scan algorithm */ |
Added test/skipscan1.test.