Many hyperlinks are disabled.
Use anonymous login
to enable hyperlinks.
Overview
Comment: | When possible, use the multi-column samples in sqlite_stat4 to estimate the number of index rows scanned by a query plan. |
---|---|
Downloads: | Tarball | ZIP archive |
Timelines: | family | ancestors | descendants | both | sqlite_stat4 |
Files: | files | file ages | folders |
SHA1: |
2973f5ca736c4a6f13c653d54b6a29d7 |
User & Date: | dan 2013-08-06 20:01:43.152 |
Context
2013-08-06
| ||
20:15 | Fixes for builds without SQLITE_ENABLE_STAT4. (check-in: 84999e27cc user: dan tags: sqlite_stat4) | |
20:01 | When possible, use the multi-column samples in sqlite_stat4 to estimate the number of index rows scanned by a query plan. (check-in: 2973f5ca73 user: dan tags: sqlite_stat4) | |
2013-08-05
| ||
19:04 | Modify the vdbe code generated by ANALYZE to use fewer memory cells and cursor slots. (check-in: 4a51cf289f user: dan tags: sqlite_stat4) | |
Changes
Changes to src/alter.c.
︙ | ︙ | |||
683 684 685 686 687 688 689 | return; } /* Ensure the default expression is something that sqlite3ValueFromExpr() ** can handle (i.e. not CURRENT_TIME etc.) */ if( pDflt ){ | | | 683 684 685 686 687 688 689 690 691 692 693 694 695 696 697 | return; } /* Ensure the default expression is something that sqlite3ValueFromExpr() ** can handle (i.e. not CURRENT_TIME etc.) */ if( pDflt ){ sqlite3_value *pVal = 0; if( sqlite3ValueFromExpr(db, pDflt, SQLITE_UTF8, SQLITE_AFF_NONE, &pVal) ){ db->mallocFailed = 1; return; } if( !pVal ){ sqlite3ErrorMsg(pParse, "Cannot add a column with non-constant default"); return; |
︙ | ︙ |
Changes to src/sqliteInt.h.
︙ | ︙ | |||
3096 3097 3098 3099 3100 3101 3102 3103 3104 3105 3106 3107 3108 3109 | char *sqlite3StrAccumFinish(StrAccum*); void sqlite3StrAccumReset(StrAccum*); void sqlite3SelectDestInit(SelectDest*,int,int); Expr *sqlite3CreateColumnExpr(sqlite3 *, SrcList *, int, int); void sqlite3BackupRestart(sqlite3_backup *); void sqlite3BackupUpdate(sqlite3_backup *, Pgno, const u8 *); /* ** The interface to the LEMON-generated parser */ void *sqlite3ParserAlloc(void*(*)(size_t)); void sqlite3ParserFree(void*, void(*)(void*)); void sqlite3Parser(void*, int, Token, Parse*); | > > > > | 3096 3097 3098 3099 3100 3101 3102 3103 3104 3105 3106 3107 3108 3109 3110 3111 3112 3113 | char *sqlite3StrAccumFinish(StrAccum*); void sqlite3StrAccumReset(StrAccum*); void sqlite3SelectDestInit(SelectDest*,int,int); Expr *sqlite3CreateColumnExpr(sqlite3 *, SrcList *, int, int); void sqlite3BackupRestart(sqlite3_backup *); void sqlite3BackupUpdate(sqlite3_backup *, Pgno, const u8 *); int sqlite3Stat4ProbeSetValue(Parse*, UnpackedRecord*, Expr*, u8, int, int*); void sqlite3Stat4ProbeFree(UnpackedRecord*); int sqlite3Stat4ProbeNew(Parse*, Index*, UnpackedRecord**); /* ** The interface to the LEMON-generated parser */ void *sqlite3ParserAlloc(void*(*)(size_t)); void sqlite3ParserFree(void*, void(*)(void*)); void sqlite3Parser(void*, int, Token, Parse*); |
︙ | ︙ |
Changes to src/update.c.
︙ | ︙ | |||
57 58 59 60 61 62 63 | ** on register iReg. This is used when an equivalent integer value is ** stored in place of an 8-byte floating point value in order to save ** space. */ void sqlite3ColumnDefault(Vdbe *v, Table *pTab, int i, int iReg){ assert( pTab!=0 ); if( !pTab->pSelect ){ | | | 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 | ** on register iReg. This is used when an equivalent integer value is ** stored in place of an 8-byte floating point value in order to save ** space. */ void sqlite3ColumnDefault(Vdbe *v, Table *pTab, int i, int iReg){ assert( pTab!=0 ); if( !pTab->pSelect ){ sqlite3_value *pValue = 0; u8 enc = ENC(sqlite3VdbeDb(v)); Column *pCol = &pTab->aCol[i]; VdbeComment((v, "%s.%s", pTab->zName, pCol->zName)); assert( i<pTab->nCol ); sqlite3ValueFromExpr(sqlite3VdbeDb(v), pCol->pDflt, enc, pCol->affinity, &pValue); if( pValue ){ |
︙ | ︙ |
Changes to src/vdbemem.c.
︙ | ︙ | |||
1000 1001 1002 1003 1004 1005 1006 1007 1008 1009 1010 1011 1012 1013 | if( p ){ p->flags = MEM_Null; p->type = SQLITE_NULL; p->db = db; } return p; } /* ** Create a new sqlite3_value object, containing the value of pExpr. ** ** This only works for very simple expressions that consist of one constant ** token (i.e. "5", "5.1", "'a string'"). If the expression can ** be converted directly into a value, then the value is allocated and | > > > > > | 1000 1001 1002 1003 1004 1005 1006 1007 1008 1009 1010 1011 1012 1013 1014 1015 1016 1017 1018 | if( p ){ p->flags = MEM_Null; p->type = SQLITE_NULL; p->db = db; } return p; } static sqlite3_value *valueNew(sqlite3 *db, sqlite3_value *pOld){ if( pOld ) return pOld; return sqlite3ValueNew(db); } /* ** Create a new sqlite3_value object, containing the value of pExpr. ** ** This only works for very simple expressions that consist of one constant ** token (i.e. "5", "5.1", "'a string'"). If the expression can ** be converted directly into a value, then the value is allocated and |
︙ | ︙ | |||
1052 1053 1054 1055 1056 1057 1058 | pExpr = pExpr->pLeft; op = pExpr->op; negInt = -1; zNeg = "-"; } if( op==TK_STRING || op==TK_FLOAT || op==TK_INTEGER ){ | | | 1057 1058 1059 1060 1061 1062 1063 1064 1065 1066 1067 1068 1069 1070 1071 | pExpr = pExpr->pLeft; op = pExpr->op; negInt = -1; zNeg = "-"; } if( op==TK_STRING || op==TK_FLOAT || op==TK_INTEGER ){ pVal = valueNew(db, *ppVal); if( pVal==0 ) goto no_mem; if( ExprHasProperty(pExpr, EP_IntValue) ){ sqlite3VdbeMemSetInt64(pVal, (i64)pExpr->u.iValue*negInt); }else{ zVal = sqlite3MPrintf(db, "%s%s", zNeg, pExpr->u.zToken); if( zVal==0 ) goto no_mem; sqlite3ValueSetStr(pVal, -1, zVal, SQLITE_UTF8, SQLITE_DYNAMIC); |
︙ | ︙ | |||
1086 1087 1088 1089 1090 1091 1092 | }else{ pVal->u.i = -pVal->u.i; } pVal->r = -pVal->r; sqlite3ValueApplyAffinity(pVal, affinity, enc); } }else if( op==TK_NULL ){ | | | | > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > | 1091 1092 1093 1094 1095 1096 1097 1098 1099 1100 1101 1102 1103 1104 1105 1106 1107 1108 1109 1110 1111 1112 1113 1114 1115 1116 1117 1118 1119 1120 1121 1122 1123 1124 1125 1126 1127 1128 1129 1130 1131 1132 1133 1134 1135 1136 1137 1138 1139 1140 1141 1142 1143 1144 1145 1146 1147 1148 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 1219 1220 1221 1222 1223 1224 1225 1226 1227 1228 1229 | }else{ pVal->u.i = -pVal->u.i; } pVal->r = -pVal->r; sqlite3ValueApplyAffinity(pVal, affinity, enc); } }else if( op==TK_NULL ){ pVal = valueNew(db, *ppVal); if( pVal==0 ) goto no_mem; } #ifndef SQLITE_OMIT_BLOB_LITERAL else if( op==TK_BLOB ){ int nVal; assert( pExpr->u.zToken[0]=='x' || pExpr->u.zToken[0]=='X' ); assert( pExpr->u.zToken[1]=='\'' ); pVal = valueNew(db, *ppVal); if( !pVal ) goto no_mem; zVal = &pExpr->u.zToken[2]; nVal = sqlite3Strlen30(zVal)-1; assert( zVal[nVal]=='\'' ); sqlite3VdbeMemSetStr(pVal, sqlite3HexToBlob(db, zVal, nVal), nVal/2, 0, SQLITE_DYNAMIC); } #endif if( pVal ){ sqlite3VdbeMemStoreType(pVal); } *ppVal = pVal; return SQLITE_OK; no_mem: db->mallocFailed = 1; sqlite3DbFree(db, zVal); if( *ppVal==0 ) sqlite3ValueFree(pVal); *ppVal = 0; return SQLITE_NOMEM; } #ifdef SQLITE_ENABLE_STAT4 int sqlite3Stat4ProbeSetValue( Parse *pParse, /* Parse context */ UnpackedRecord *pRec, /* Set field in this probe */ Expr *pExpr, /* The expression to extract a value from */ u8 affinity, /* Affinity to use */ int iVal, /* Array element to populate */ int *pbOk /* OUT: True if value was extracted */ ){ int rc = SQLITE_OK; sqlite3_value *pVal = &pRec->aMem[iVal]; #if 0 if( iVal>0 ){ *pbOk = 0; return SQLITE_OK; } #endif if( !pExpr ){ sqlite3VdbeMemSetNull((Mem*)pVal); *pbOk = 1; }else if( pExpr->op==TK_VARIABLE || (pExpr->op==TK_REGISTER && pExpr->op2==TK_VARIABLE) ){ Vdbe *v; int iVar = pExpr->iColumn; sqlite3VdbeSetVarmask(pParse->pVdbe, iVar); if( v = pParse->pReprepare ){ rc = sqlite3VdbeMemCopy((Mem*)pVal, &v->aVar[iVal-1]); if( rc==SQLITE_OK ){ sqlite3ValueApplyAffinity(pVal, affinity, SQLITE_UTF8); } pVal->db = pParse->db; *pbOk = 1; sqlite3VdbeMemStoreType((Mem*)pVal); }else{ *pbOk = 0; } }else{ sqlite3 *db = pRec->aMem[0].db; rc = sqlite3ValueFromExpr(db, pExpr, ENC(db), affinity, &pVal); *pbOk = (pVal!=0); } assert( pVal==0 || pVal->db==pParse->db ); return rc; } void sqlite3Stat4ProbeFree(UnpackedRecord *pRec){ if( pRec ){ int i; Mem *aMem = pRec->aMem; sqlite3 *db = aMem[0].db; for(i=0; i<pRec->pKeyInfo->nField; i++){ sqlite3DbFree(db, aMem[i].zMalloc); } sqlite3DbFree(db, pRec->pKeyInfo); sqlite3DbFree(db, pRec); } } int sqlite3Stat4ProbeNew( Parse *pParse, /* Parse context */ Index *pIdx, /* Allocate record for this index */ UnpackedRecord **ppRec /* OUT: Allocated record */ ){ sqlite3 *db = pParse->db; /* Database handle */ UnpackedRecord *pRec; /* Return value */ int nByte; /* Bytes of space to allocate */ int i; /* Counter variable */ assert( *ppRec==0 ); if( pIdx->nSample==0 ) return SQLITE_OK; nByte = sizeof(Mem) * pIdx->nColumn + sizeof(UnpackedRecord); *ppRec = pRec = (UnpackedRecord*)sqlite3DbMallocZero(db, nByte); if( !pRec ) return SQLITE_NOMEM; pRec->pKeyInfo = sqlite3IndexKeyinfo(pParse, pIdx); if( !pRec->pKeyInfo ){ sqlite3DbFree(db, pRec); *ppRec = 0; return SQLITE_NOMEM; } pRec->pKeyInfo->enc = ENC(pParse->db); pRec->flags = UNPACKED_PREFIX_MATCH; pRec->aMem = (Mem *)&pRec[1]; for(i=0; i<pIdx->nColumn; i++){ pRec->aMem[i].flags = MEM_Null; pRec->aMem[i].type = SQLITE_NULL; pRec->aMem[i].db = db; } return SQLITE_OK; } #endif /* ifdef SQLITE_ENABLE_STAT4 */ /* ** Change the string value of an sqlite3_value object */ void sqlite3ValueSetStr( sqlite3_value *v, /* Value to be set */ int n, /* Length of string z */ const void *z, /* Text of the new string */ |
︙ | ︙ |
Changes to src/where.c.
︙ | ︙ | |||
386 387 388 389 390 391 392 393 394 395 396 397 398 399 | */ struct WhereLoopBuilder { WhereInfo *pWInfo; /* Information about this WHERE */ WhereClause *pWC; /* WHERE clause terms */ ExprList *pOrderBy; /* ORDER BY clause */ WhereLoop *pNew; /* Template WhereLoop */ WhereOrSet *pOrSet; /* Record best loops here, if not NULL */ }; /* ** The WHERE clause processing routine has two halves. The ** first part does the start of the WHERE loop and the second ** half does the tail of the WHERE loop. An instance of ** this structure is returned by the first half and passed | > > > > > | 386 387 388 389 390 391 392 393 394 395 396 397 398 399 400 401 402 403 404 | */ struct WhereLoopBuilder { WhereInfo *pWInfo; /* Information about this WHERE */ WhereClause *pWC; /* WHERE clause terms */ ExprList *pOrderBy; /* ORDER BY clause */ WhereLoop *pNew; /* Template WhereLoop */ WhereOrSet *pOrSet; /* Record best loops here, if not NULL */ #ifdef SQLITE_ENABLE_STAT4 UnpackedRecord *pRec; /* Probe for stat4 (if required) */ int nRecValid; /* Number of valid fields currently in pRec */ tRowcnt nMaxRowcnt; /* If !=0, the maximum estimated row count */ #endif }; /* ** The WHERE clause processing routine has two halves. The ** first part does the start of the WHERE loop and the second ** half does the tail of the WHERE loop. An instance of ** this structure is returned by the first half and passed |
︙ | ︙ | |||
2401 2402 2403 2404 2405 2406 2407 | ** aStat[1] Est. number of rows equal to pVal ** ** Return SQLITE_OK on success. */ static int whereKeyStats( Parse *pParse, /* Database connection */ Index *pIdx, /* Index to consider domain of */ | | < < < < < < < < < < < | < | 2406 2407 2408 2409 2410 2411 2412 2413 2414 2415 2416 2417 2418 2419 2420 2421 2422 2423 2424 2425 2426 2427 2428 2429 2430 2431 2432 2433 2434 | ** aStat[1] Est. number of rows equal to pVal ** ** Return SQLITE_OK on success. */ static int whereKeyStats( Parse *pParse, /* Database connection */ Index *pIdx, /* Index to consider domain of */ UnpackedRecord *pRec, /* Vector of values to consider */ int roundUp, /* Round up if true. Round down if false */ tRowcnt *aStat /* OUT: stats written here */ ){ IndexSample *aSample = pIdx->aSample; int i; int isEq = 0; for(i=0; i<pIdx->nSample; i++){ int res = sqlite3VdbeRecordCompare(aSample[i].n, aSample[i].p, pRec); if( res>=0 ){ isEq = (res==0); break; } } /* At this point, aSample[i] is the first sample that is greater than ** or equal to pVal. Or if i==pIdx->nSample, then all samples are less ** than pVal. If aSample[i]==pVal, then isEq==1. */ if( isEq ){ assert( i<pIdx->nSample ); |
︙ | ︙ | |||
2463 2464 2465 2466 2467 2468 2469 | } aStat[0] = iLower + iGap; } return SQLITE_OK; } #endif /* SQLITE_ENABLE_STAT4 */ | < < < < < < < < < < < < < < < < < < < < < < < < < < < < < < < < < < < | 2456 2457 2458 2459 2460 2461 2462 2463 2464 2465 2466 2467 2468 2469 | } aStat[0] = iLower + iGap; } return SQLITE_OK; } #endif /* SQLITE_ENABLE_STAT4 */ /* ** This function is used to estimate the number of rows that will be visited ** by scanning an index for a range of values. The range may have an upper ** bound, a lower bound, or both. The WHERE clause terms that set the upper ** and lower bounds are represented by pLower and pUpper respectively. For ** example, assuming that index p is on t1(a): ** |
︙ | ︙ | |||
2539 2540 2541 2542 2543 2544 2545 | ** In the absence of sqlite_stat3 ANALYZE data, each range inequality ** reduces the search space by a factor of 4. Hence a single constraint (x>?) ** results in a return of 4 and a range constraint (x>? AND x<?) results ** in a return of 16. */ static int whereRangeScanEst( Parse *pParse, /* Parsing & code generating context */ | | < > > > > | > | < > < > > | | < > < > > | | < > > > | > | | 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 2535 2536 2537 2538 2539 2540 2541 2542 2543 2544 2545 2546 2547 2548 2549 2550 2551 2552 2553 2554 2555 2556 2557 2558 2559 2560 2561 2562 2563 2564 2565 2566 2567 2568 2569 2570 2571 2572 2573 2574 | ** In the absence of sqlite_stat3 ANALYZE data, each range inequality ** reduces the search space by a factor of 4. Hence a single constraint (x>?) ** results in a return of 4 and a range constraint (x>? AND x<?) results ** in a return of 16. */ static int whereRangeScanEst( Parse *pParse, /* Parsing & code generating context */ WhereLoopBuilder *pBuilder, WhereTerm *pLower, /* Lower bound on the range. ex: "x>123" Might be NULL */ WhereTerm *pUpper, /* Upper bound on the range. ex: "x<455" Might be NULL */ WhereCost *pRangeDiv /* OUT: Reduce search space by this divisor */ ){ int rc = SQLITE_OK; #ifdef SQLITE_ENABLE_STAT4 Index *p = pBuilder->pNew->u.btree.pIndex; int nEq = pBuilder->pNew->u.btree.nEq; if( nEq==pBuilder->nRecValid && p->nSample && OptimizationEnabled(pParse->db, SQLITE_Stat3) ){ UnpackedRecord *pRec = pBuilder->pRec; tRowcnt iLower = 0; tRowcnt iUpper = p->aiRowEst[0]; tRowcnt a[2]; u8 aff = p->pTable->aCol[p->aiColumn[0]].affinity; if( pLower ){ int bOk; /* True if value is extracted from pExpr */ Expr *pExpr = pLower->pExpr->pRight; assert( (pLower->eOperator & (WO_GT|WO_GE))!=0 ); rc = sqlite3Stat4ProbeSetValue(pParse, pRec, pExpr, aff, nEq, &bOk); pRec->nField = nEq+1; if( rc==SQLITE_OK && bOk && whereKeyStats(pParse, p, pRec, 0, a)==SQLITE_OK ){ iLower = a[0]; if( (pLower->eOperator & WO_GT)!=0 ) iLower += a[1]; } } if( rc==SQLITE_OK && pUpper ){ int bOk; /* True if value is extracted from pExpr */ Expr *pExpr = pUpper->pExpr->pRight; assert( (pUpper->eOperator & (WO_LT|WO_LE))!=0 ); rc = sqlite3Stat4ProbeSetValue(pParse, pRec, pExpr, aff, nEq, &bOk); pRec->nField = nEq+1; if( rc==SQLITE_OK && bOk && whereKeyStats(pParse, p, pRec, 1, a)==SQLITE_OK ){ iUpper = a[0]; if( (pUpper->eOperator & WO_LE)!=0 ) iUpper += a[1]; } } if( rc==SQLITE_OK ){ WhereCost iBase = whereCost(p->aiRowEst[0]); if( iUpper>iLower ){ iBase -= whereCost(iUpper - iLower); } if( pBuilder->nMaxRowcnt && iBase<pBuilder->nMaxRowcnt ){ *pRangeDiv = pBuilder->nMaxRowcnt; }else{ *pRangeDiv = iBase; } WHERETRACE(0x100, ("range scan regions: %u..%u div=%d\n", (u32)iLower, (u32)iUpper, *pRangeDiv)); return SQLITE_OK; } } #else UNUSED_PARAMETER(pParse); UNUSED_PARAMETER(pBuilder); UNUSED_PARAMETER(nEq); #endif assert( pLower || pUpper ); *pRangeDiv = 0; /* TUNING: Each inequality constraint reduces the search space 4-fold. ** A BETWEEN operator, therefore, reduces the search space 16-fold */ if( pLower && (pLower->wtFlags & TERM_VNULL)==0 ){ |
︙ | ︙ | |||
2629 2630 2631 2632 2633 2634 2635 | ** This routine can fail if it is unable to load a collating sequence ** required for string comparison, or if unable to allocate memory ** for a UTF conversion required for comparison. The error is stored ** in the pParse structure. */ static int whereEqualScanEst( Parse *pParse, /* Parsing & code generating context */ | | | > > > > > > | > > | > > | | < | > > > > > | > > > > | > > | > | < | 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 2631 2632 2633 2634 2635 2636 2637 2638 2639 2640 2641 2642 2643 2644 2645 2646 2647 2648 2649 2650 2651 2652 2653 2654 2655 | ** This routine can fail if it is unable to load a collating sequence ** required for string comparison, or if unable to allocate memory ** for a UTF conversion required for comparison. The error is stored ** in the pParse structure. */ static int whereEqualScanEst( Parse *pParse, /* Parsing & code generating context */ WhereLoopBuilder *pBuilder, Expr *pExpr, /* Expression for VALUE in the x=VALUE constraint */ tRowcnt *pnRow /* Write the revised row estimate here */ ){ Index *p = pBuilder->pNew->u.btree.pIndex; int nEq = pBuilder->pNew->u.btree.nEq; UnpackedRecord *pRec = pBuilder->pRec; u8 aff; /* Column affinity */ int rc; /* Subfunction return code */ tRowcnt a[2]; /* Statistics */ int bOk; assert( nEq>=1 ); assert( nEq<=(p->nColumn+1) ); assert( p->aSample!=0 ); assert( p->nSample>0 ); assert( pBuilder->nRecValid<nEq ); /* If values are not available for all fields of the index to the left ** of this one, no estimate can be made. Return SQLITE_NOTFOUND. */ if( pBuilder->nRecValid<(nEq-1) ){ return SQLITE_NOTFOUND; } if( nEq>p->nColumn ){ *pnRow = 1; return SQLITE_OK; } aff = p->pTable->aCol[p->aiColumn[0]].affinity; rc = sqlite3Stat4ProbeSetValue(pParse, pRec, pExpr, aff, nEq-1, &bOk); if( rc!=SQLITE_OK ) return rc; if( bOk==0 ) return SQLITE_NOTFOUND; pBuilder->nRecValid = nEq; pRec->nField = nEq; rc = whereKeyStats(pParse, p, pRec, 0, a); if( rc==SQLITE_OK ){ WHERETRACE(0x100,("equality scan regions: %d\n", (int)a[1])); *pnRow = a[1]; if( pBuilder->nMaxRowcnt && *pnRow>pBuilder->nMaxRowcnt ){ *pnRow = pBuilder->nMaxRowcnt; } } return rc; } #endif /* defined(SQLITE_ENABLE_STAT4) */ #ifdef SQLITE_ENABLE_STAT4 /* ** Estimate the number of rows that will be returned based on |
︙ | ︙ | |||
2678 2679 2680 2681 2682 2683 2684 | ** This routine can fail if it is unable to load a collating sequence ** required for string comparison, or if unable to allocate memory ** for a UTF conversion required for comparison. The error is stored ** in the pParse structure. */ static int whereInScanEst( Parse *pParse, /* Parsing & code generating context */ | | > > | > > > > > | > > | 2665 2666 2667 2668 2669 2670 2671 2672 2673 2674 2675 2676 2677 2678 2679 2680 2681 2682 2683 2684 2685 2686 2687 2688 2689 2690 2691 2692 2693 2694 2695 2696 2697 2698 2699 2700 2701 2702 2703 2704 2705 2706 2707 | ** This routine can fail if it is unable to load a collating sequence ** required for string comparison, or if unable to allocate memory ** for a UTF conversion required for comparison. The error is stored ** in the pParse structure. */ static int whereInScanEst( Parse *pParse, /* Parsing & code generating context */ WhereLoopBuilder *pBuilder, ExprList *pList, /* The value list on the RHS of "x IN (v1,v2,v3,...)" */ tRowcnt *pnRow /* Write the revised row estimate here */ ){ Index *p = pBuilder->pNew->u.btree.pIndex; int nRecValid = pBuilder->nRecValid; int rc = SQLITE_OK; /* Subfunction return code */ tRowcnt nEst; /* Number of rows for a single term */ tRowcnt nRowEst = 0; /* New estimate of the number of rows */ int i; /* Loop counter */ assert( p->aSample!=0 ); for(i=0; rc==SQLITE_OK && i<pList->nExpr; i++){ nEst = p->aiRowEst[0]; rc = whereEqualScanEst(pParse, pBuilder, pList->a[i].pExpr, &nEst); nRowEst += nEst; pBuilder->nRecValid = nRecValid; } if( rc==SQLITE_OK ){ if( nRowEst > p->aiRowEst[0] ) nRowEst = p->aiRowEst[0]; if( pBuilder->nMaxRowcnt && nRowEst>pBuilder->nMaxRowcnt ){ *pnRow = pBuilder->nMaxRowcnt; }else{ *pnRow = nRowEst; } WHERETRACE(0x100,("IN row estimate: est=%g\n", nRowEst)); } assert( pBuilder->nRecValid==nRecValid ); return rc; } #endif /* defined(SQLITE_ENABLE_STAT4) */ /* ** Disable a term in the WHERE clause. Except, do not disable the term ** if it controls a LEFT OUTER JOIN and it did not originate in the ON |
︙ | ︙ | |||
4244 4245 4246 4247 4248 4249 4250 | saved_wsFlags = pNew->wsFlags; saved_prereq = pNew->prereq; saved_nOut = pNew->nOut; pNew->rSetup = 0; rLogSize = estLog(whereCost(pProbe->aiRowEst[0])); for(; rc==SQLITE_OK && pTerm!=0; pTerm = whereScanNext(&scan)){ int nIn = 0; | < > > > > | 4240 4241 4242 4243 4244 4245 4246 4247 4248 4249 4250 4251 4252 4253 4254 4255 4256 4257 4258 4259 4260 4261 4262 | saved_wsFlags = pNew->wsFlags; saved_prereq = pNew->prereq; saved_nOut = pNew->nOut; pNew->rSetup = 0; rLogSize = estLog(whereCost(pProbe->aiRowEst[0])); for(; rc==SQLITE_OK && pTerm!=0; pTerm = whereScanNext(&scan)){ int nIn = 0; #ifdef SQLITE_ENABLE_STAT4 int nRecValid = pBuilder->nRecValid; int nMaxRowcnt = pBuilder->nMaxRowcnt; if( (pTerm->wtFlags & TERM_VNULL)!=0 && pSrc->pTab->aCol[iCol].notNull ){ continue; /* skip IS NOT NULL constraints on a NOT NULL column */ } #endif if( pTerm->prereqRight & pNew->maskSelf ) continue; pNew->wsFlags = saved_wsFlags; pNew->u.btree.nEq = saved_nEq; pNew->nLTerm = saved_nLTerm; if( whereLoopResize(db, pNew, pNew->nLTerm+1) ) break; /* OOM */ pNew->aLTerm[pNew->nLTerm++] = pTerm; pNew->prereq = (saved_prereq | pTerm->prereqRight) & ~pNew->maskSelf; pNew->rRun = rLogSize; /* Baseline cost is log2(N). Adjustments below */ |
︙ | ︙ | |||
4307 4308 4309 4310 4311 4312 4313 | pTop = pTerm; pBtm = (pNew->wsFlags & WHERE_BTM_LIMIT)!=0 ? pNew->aLTerm[pNew->nLTerm-2] : 0; } if( pNew->wsFlags & WHERE_COLUMN_RANGE ){ /* Adjust nOut and rRun for STAT3 range values */ WhereCost rDiv; | | < < | > | > > | | > > > > | 4306 4307 4308 4309 4310 4311 4312 4313 4314 4315 4316 4317 4318 4319 4320 4321 4322 4323 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 | pTop = pTerm; pBtm = (pNew->wsFlags & WHERE_BTM_LIMIT)!=0 ? pNew->aLTerm[pNew->nLTerm-2] : 0; } if( pNew->wsFlags & WHERE_COLUMN_RANGE ){ /* Adjust nOut and rRun for STAT3 range values */ WhereCost rDiv; whereRangeScanEst(pParse, pBuilder, pBtm, pTop, &rDiv); pNew->nOut = saved_nOut>rDiv+10 ? saved_nOut - rDiv : 10; } #ifdef SQLITE_ENABLE_STAT4 if( nInMul==0 && pProbe->nSample && OptimizationEnabled(db, SQLITE_Stat3) ){ Expr *pExpr = pTerm->pExpr; tRowcnt nOut = 0; if( (pTerm->eOperator & (WO_EQ|WO_ISNULL))!=0 ){ testcase( pTerm->eOperator & WO_EQ ); testcase( pTerm->eOperator & WO_ISNULL ); rc = whereEqualScanEst(pParse, pBuilder, pExpr->pRight, &nOut); assert( nOut==0||pBuilder->nMaxRowcnt==0||nOut<=pBuilder->nMaxRowcnt); if( nOut ) pBuilder->nMaxRowcnt = nOut; }else if( (pTerm->eOperator & WO_IN) && !ExprHasProperty(pExpr, EP_xIsSelect) ){ rc = whereInScanEst(pParse, pBuilder, pExpr->x.pList, &nOut); } assert( nOut==0 || rc==SQLITE_OK ); if( nOut ) pNew->nOut = whereCost(nOut); } #endif if( (pNew->wsFlags & (WHERE_IDX_ONLY|WHERE_IPK))==0 ){ /* Each row involves a step of the index, then a binary search of ** the main table */ pNew->rRun = whereCostAdd(pNew->rRun, rLogSize>27 ? rLogSize-17 : 10); } /* Step cost for each output row */ pNew->rRun = whereCostAdd(pNew->rRun, pNew->nOut); /* TBD: Adjust nOut for additional constraints */ rc = whereLoopInsert(pBuilder, pNew); if( (pNew->wsFlags & WHERE_TOP_LIMIT)==0 && pNew->u.btree.nEq<(pProbe->nColumn + (pProbe->zName!=0)) ){ whereLoopAddBtreeIndex(pBuilder, pSrc, pProbe, nInMul+nIn); } #ifdef SQLITE_ENABLE_STAT4 pBuilder->nRecValid = nRecValid; pBuilder->nMaxRowcnt = nMaxRowcnt; #endif } pNew->prereq = saved_prereq; pNew->u.btree.nEq = saved_nEq; pNew->wsFlags = saved_wsFlags; pNew->nOut = saved_nOut; pNew->nLTerm = saved_nLTerm; return rc; |
︙ | ︙ | |||
4567 4568 4569 4570 4571 4572 4573 | ** which we will simplify to just N*log2(N) */ pNew->rRun = rSize + rLogSize; } rc = whereLoopInsert(pBuilder, pNew); if( rc ) break; } } | > > > > | > > > > > | 4571 4572 4573 4574 4575 4576 4577 4578 4579 4580 4581 4582 4583 4584 4585 4586 4587 4588 4589 4590 4591 4592 4593 4594 | ** which we will simplify to just N*log2(N) */ pNew->rRun = rSize + rLogSize; } rc = whereLoopInsert(pBuilder, pNew); if( rc ) break; } } assert( pBuilder->pRec==0 ); rc = sqlite3Stat4ProbeNew(pWInfo->pParse, pProbe, &pBuilder->pRec); if( rc==SQLITE_OK ){ rc = whereLoopAddBtreeIndex(pBuilder, pSrc, pProbe, 0); sqlite3Stat4ProbeFree(pBuilder->pRec); pBuilder->nRecValid = 0; pBuilder->pRec = 0; } assert( pBuilder->pRec==0 ); /* If there was an INDEXED BY clause, then only that one index is ** considered. */ if( pSrc->pIndex ) break; } return rc; } |
︙ | ︙ |