Many hyperlinks are disabled.
Use anonymous login
to enable hyperlinks.
Overview
Comment: | Fix problems in estimating the number of rows visited by a range query using sqlite_stat4 data when the column subject to the range query is not the leftmost of the index. |
---|---|
Downloads: | Tarball | ZIP archive |
Timelines: | family | ancestors | descendants | both | sqlite_stat4 |
Files: | files | file ages | folders |
SHA1: |
9228aaf54dd2700c4f460f94f9c23094 |
User & Date: | dan 2013-08-08 19:38:40.828 |
Context
2013-08-09
| ||
14:07 | Update the header comment on analyze.c to describe the sqlite_stat4 table format. (check-in: 4d97809d6b user: drh tags: sqlite_stat4) | |
2013-08-08
| ||
19:38 | Fix problems in estimating the number of rows visited by a range query using sqlite_stat4 data when the column subject to the range query is not the leftmost of the index. (check-in: 9228aaf54d user: dan tags: sqlite_stat4) | |
16:17 | Use a binary search instead of a linear scan when comparing a sample key against data from the sqlite_stat4 table. (check-in: e50dc30523 user: dan tags: sqlite_stat4) | |
Changes
Changes to src/where.c.
︙ | ︙ | |||
2403 2404 2405 2406 2407 2408 2409 | ** index. Store the results in aStat as follows: ** ** aStat[0] Est. number of rows less than pVal ** aStat[1] Est. number of rows equal to pVal ** ** Return SQLITE_OK on success. */ | | | 2403 2404 2405 2406 2407 2408 2409 2410 2411 2412 2413 2414 2415 2416 2417 | ** index. Store the results in aStat as follows: ** ** aStat[0] Est. number of rows less than pVal ** aStat[1] Est. number of rows equal to pVal ** ** Return SQLITE_OK on success. */ static void 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; |
︙ | ︙ | |||
2476 2477 2478 2479 2480 2481 2482 | if( roundUp ){ iGap = (iGap*2)/3; }else{ iGap = iGap/3; } aStat[0] = iLower + iGap; } | < | 2476 2477 2478 2479 2480 2481 2482 2483 2484 2485 2486 2487 2488 2489 | if( roundUp ){ iGap = (iGap*2)/3; }else{ iGap = iGap/3; } aStat[0] = iLower + iGap; } } #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 |
︙ | ︙ | |||
2539 2540 2541 2542 2543 2544 2545 | int nEq = pBuilder->pNew->u.btree.nEq; if( nEq==pBuilder->nRecValid && p->nSample && OptimizationEnabled(pParse->db, SQLITE_Stat3) ){ UnpackedRecord *pRec = pBuilder->pRec; | | > > > > > > > > > > > > > > > > > > > | | | > > > > > > > > > > > > > | > | < < | > > > | | > | < < | > > | | 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 2575 2576 2577 2578 2579 2580 2581 2582 2583 2584 2585 2586 2587 2588 2589 2590 2591 2592 2593 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 | int nEq = pBuilder->pNew->u.btree.nEq; if( nEq==pBuilder->nRecValid && p->nSample && OptimizationEnabled(pParse->db, SQLITE_Stat3) ){ UnpackedRecord *pRec = pBuilder->pRec; tRowcnt a[2]; u8 aff = p->pTable->aCol[p->aiColumn[0]].affinity; /* Variable iLower will be set to the estimate of the number of rows in ** the index that are less than the lower bound of the range query. The ** lower bound being the concatenation of $P and $L, where $P is the ** key-prefix formed by the nEq values matched against the nEq left-most ** columns of the index, and $L is the value in pLower. ** ** Or, if pLower is NULL or $L cannot be extracted from it (because it ** is not a simple variable or literal value), the lower bound of the ** range is $P. Due to a quirk in the way whereKeyStats() works, even ** if $L is available, whereKeyStats() is called for both ($P) and ** ($P:$L) and the larger of the two returned values used. ** ** Similarly, iUpper is to be set to the estimate of the number of rows ** less than the upper bound of the range query. Where the upper bound ** is either ($P) or ($P:$U). Again, even if $U is available, both values ** of iUpper are requested of whereKeyStats() and the smaller used. */ tRowcnt iLower; tRowcnt iUpper; /* Determine iLower and iUpper using ($P) only. */ if( nEq==0 ){ iLower = 0; iUpper = p->aiRowEst[0]; }else{ /* Note: this call could be optimized away - since the same values must ** have been requested when testing key $P in whereEqualScanEst(). */ whereKeyStats(pParse, p, pRec, 0, a); iLower = a[0]; iUpper = a[0] + a[1]; } /* If possible, improve on the iLower estimate using ($P:$L). */ 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, p, &pRec, pExpr, aff, nEq, &bOk); if( rc==SQLITE_OK && bOk ){ tRowcnt iNew; whereKeyStats(pParse, p, pRec, 0, a); iNew = a[0] + ((pLower->eOperator & WO_GT) ? a[1] : 0); if( iNew>iLower ) iLower = iNew; } } /* If possible, improve on the iUpper estimate using ($P:$U). */ if( 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, p, &pRec, pExpr, aff, nEq, &bOk); if( rc==SQLITE_OK && bOk ){ tRowcnt iNew; whereKeyStats(pParse, p, pRec, 1, a); iNew = a[0] + ((pUpper->eOperator & WO_LE) ? a[1] : 0); if( iNew<iUpper ) iUpper = iNew; } } pBuilder->pRec = pRec; if( rc==SQLITE_OK ){ WhereCost nNew; if( iUpper>iLower ){ nNew = whereCost(iUpper - iLower); }else{ nNew = 10; assert( 10==whereCost(2) ); } if( nNew<nOut ){ nOut = nNew; } *pnOut = (WhereCost)nOut; WHERETRACE(0x100, ("range scan regions: %u..%u est=%d\n", (u32)iLower, (u32)iUpper, nOut)); |
︙ | ︙ | |||
2658 2659 2660 2661 2662 2663 2664 | aff = p->pTable->aCol[p->aiColumn[nEq-1]].affinity; rc = sqlite3Stat4ProbeSetValue(pParse, p, &pRec, pExpr, aff, nEq-1, &bOk); pBuilder->pRec = pRec; if( rc!=SQLITE_OK ) return rc; if( bOk==0 ) return SQLITE_NOTFOUND; pBuilder->nRecValid = nEq; | | < | | < | 2692 2693 2694 2695 2696 2697 2698 2699 2700 2701 2702 2703 2704 2705 2706 2707 2708 | aff = p->pTable->aCol[p->aiColumn[nEq-1]].affinity; rc = sqlite3Stat4ProbeSetValue(pParse, p, &pRec, pExpr, aff, nEq-1, &bOk); pBuilder->pRec = pRec; if( rc!=SQLITE_OK ) return rc; if( bOk==0 ) return SQLITE_NOTFOUND; pBuilder->nRecValid = nEq; whereKeyStats(pParse, p, pRec, 0, a); WHERETRACE(0x100,("equality scan regions: %d\n", (int)a[1])); *pnRow = a[1]; return rc; } #endif /* defined(SQLITE_ENABLE_STAT4) */ #ifdef SQLITE_ENABLE_STAT4 /* |
︙ | ︙ |