Many hyperlinks are disabled.
Use anonymous login
to enable hyperlinks.
Overview
Comment: | Multi-index OR-clause optimization now works for simple tests. There are no test scripts for it yet, though. And it is disabled by default, pending further testing and optimization. We need a lot of both. (CVS 6058) |
---|---|
Downloads: | Tarball | ZIP archive |
Timelines: | family | ancestors | descendants | both | trunk |
Files: | files | file ages | folders |
SHA1: |
d77a702358deddfa9987147999d06a23 |
User & Date: | drh 2008-12-23 13:35:23.000 |
Context
2008-12-23
| ||
15:58 | Make sure nOverflow is always cleared when a page is released. (CVS 6059) (check-in: 8d0f724477 user: drh tags: trunk) | |
13:35 | Multi-index OR-clause optimization now works for simple tests. There are no test scripts for it yet, though. And it is disabled by default, pending further testing and optimization. We need a lot of both. (CVS 6058) (check-in: d77a702358 user: drh tags: trunk) | |
11:46 | Add a test to savepoint.test that tests that nothing goes wrong if an incremental vacuum occurs inside a savepoint. (CVS 6057) (check-in: fc4f062153 user: danielk1977 tags: trunk) | |
Changes
Changes to src/sqliteInt.h.
1 2 3 4 5 6 7 8 9 10 11 12 13 | /* ** 2001 September 15 ** ** The author disclaims copyright to this source code. In place of ** a legal notice, here is a blessing: ** ** May you do good and not evil. ** May you find forgiveness for yourself and forgive others. ** May you share freely, never taking more than you give. ** ************************************************************************* ** Internal interface definitions for SQLite. ** | | | 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 | /* ** 2001 September 15 ** ** The author disclaims copyright to this source code. In place of ** a legal notice, here is a blessing: ** ** May you do good and not evil. ** May you find forgiveness for yourself and forgive others. ** May you share freely, never taking more than you give. ** ************************************************************************* ** Internal interface definitions for SQLite. ** ** @(#) $Id: sqliteInt.h,v 1.814 2008/12/23 13:35:23 drh Exp $ */ #ifndef _SQLITEINT_H_ #define _SQLITEINT_H_ /* ** Include the configuration header output by 'configure' if we're using the ** autoconf-based build |
︙ | ︙ | |||
1495 1496 1497 1498 1499 1500 1501 1502 1503 1504 1505 | char *zDatabase; /* Name of database holding this table */ char *zName; /* Name of the table */ char *zAlias; /* The "B" part of a "A AS B" phrase. zName is the "A" */ Table *pTab; /* An SQL table corresponding to zName */ Select *pSelect; /* A SELECT statement used in place of a table name */ u8 isPopulated; /* Temporary table associated with SELECT is populated */ u8 jointype; /* Type of join between this able and the previous */ int iCursor; /* The VDBE cursor number used to access this table */ Expr *pOn; /* The ON clause of a join */ IdList *pUsing; /* The USING clause of a join */ Bitmask colUsed; /* Bit N (1<<N) set if column N or pTab is used */ | > < | 1495 1496 1497 1498 1499 1500 1501 1502 1503 1504 1505 1506 1507 1508 1509 1510 1511 1512 1513 | char *zDatabase; /* Name of database holding this table */ char *zName; /* Name of the table */ char *zAlias; /* The "B" part of a "A AS B" phrase. zName is the "A" */ Table *pTab; /* An SQL table corresponding to zName */ Select *pSelect; /* A SELECT statement used in place of a table name */ u8 isPopulated; /* Temporary table associated with SELECT is populated */ u8 jointype; /* Type of join between this able and the previous */ u8 notIndexed; /* True if there is a NOT INDEXED clause */ int iCursor; /* The VDBE cursor number used to access this table */ Expr *pOn; /* The ON clause of a join */ IdList *pUsing; /* The USING clause of a join */ Bitmask colUsed; /* Bit N (1<<N) set if column N or pTab is used */ char *zIndex; /* Identifier from "INDEXED BY <zIndex>" clause */ Index *pIndex; /* Index structure corresponding to zIndex, if any */ } a[1]; /* One entry for each identifier on the list */ }; /* ** Permitted values of the SrcList.a.jointype field |
︙ | ︙ |
Changes to src/vdbe.c.
︙ | ︙ | |||
39 40 41 42 43 44 45 | ** ** Various scripts scan this source file in order to generate HTML ** documentation, headers files, or other derived files. The formatting ** of the code in this file is, therefore, important. See other comments ** in this file for details. If in doubt, do not deviate from existing ** commenting and indentation practices when changing or adding code. ** | | | 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 | ** ** Various scripts scan this source file in order to generate HTML ** documentation, headers files, or other derived files. The formatting ** of the code in this file is, therefore, important. See other comments ** in this file for details. If in doubt, do not deviate from existing ** commenting and indentation practices when changing or adding code. ** ** $Id: vdbe.c,v 1.806 2008/12/23 13:35:23 drh Exp $ */ #include "sqliteInt.h" #include <ctype.h> #include "vdbeInt.h" /* ** The following global variable is incremented every time a cursor |
︙ | ︙ | |||
4504 4505 4506 4507 4508 4509 4510 4511 4512 4513 4514 4515 4516 4517 4518 4519 | */ case OP_RowSetRead: { /* jump, out3 */ Mem *pIdx; i64 val; assert( pOp->p1>0 && pOp->p1<=p->nMem ); CHECK_FOR_INTERRUPT; pIdx = &p->aMem[pOp->p1]; if( (pIdx->flags & MEM_RowSet)==0 || sqlite3RowSetNext(pIdx->u.pRowSet, &val)==0 ){ /* The boolean index is empty */ sqlite3VdbeMemSetNull(pIdx); pc = pOp->p2 - 1; }else{ /* A value was pulled from the index */ assert( pOp->p3>0 && pOp->p3<=p->nMem ); | > < | 4504 4505 4506 4507 4508 4509 4510 4511 4512 4513 4514 4515 4516 4517 4518 4519 4520 4521 4522 4523 4524 4525 4526 4527 | */ case OP_RowSetRead: { /* jump, out3 */ Mem *pIdx; i64 val; assert( pOp->p1>0 && pOp->p1<=p->nMem ); CHECK_FOR_INTERRUPT; pIdx = &p->aMem[pOp->p1]; pOut = &p->aMem[pOp->p3]; if( (pIdx->flags & MEM_RowSet)==0 || sqlite3RowSetNext(pIdx->u.pRowSet, &val)==0 ){ /* The boolean index is empty */ sqlite3VdbeMemSetNull(pIdx); pc = pOp->p2 - 1; }else{ /* A value was pulled from the index */ assert( pOp->p3>0 && pOp->p3<=p->nMem ); sqlite3VdbeMemSetInt64(pOut, val); } break; } #ifndef SQLITE_OMIT_TRIGGER |
︙ | ︙ |
Changes to src/where.c.
︙ | ︙ | |||
12 13 14 15 16 17 18 | ** This module contains C code that generates VDBE code used to process ** the WHERE clause of SQL statements. This module is responsible for ** generating the code that loops through a table looking for applicable ** rows. Indices are selected and used to speed the search when doing ** so is applicable. Because this module is responsible for selecting ** indices, you might also think of this module as the "query optimizer". ** | | | 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 | ** This module contains C code that generates VDBE code used to process ** the WHERE clause of SQL statements. This module is responsible for ** generating the code that loops through a table looking for applicable ** rows. Indices are selected and used to speed the search when doing ** so is applicable. Because this module is responsible for selecting ** indices, you might also think of this module as the "query optimizer". ** ** $Id: where.c,v 1.341 2008/12/23 13:35:23 drh Exp $ */ #include "sqliteInt.h" /* ** Trace output macros */ #if defined(SQLITE_TEST) || defined(SQLITE_DEBUG) |
︙ | ︙ | |||
138 139 140 141 142 143 144 | /* ** A WhereTerm with eOperator==WO_OR has its u.pOrInfo pointer set to ** a dynamically allocated instance of the following structure. */ struct WhereOrInfo { WhereClause wc; /* Decomposition into subterms */ Bitmask indexable; /* Bitmask of all indexable tables in the clause */ | < | 138 139 140 141 142 143 144 145 146 147 148 149 150 151 | /* ** A WhereTerm with eOperator==WO_OR has its u.pOrInfo pointer set to ** a dynamically allocated instance of the following structure. */ struct WhereOrInfo { WhereClause wc; /* Decomposition into subterms */ Bitmask indexable; /* Bitmask of all indexable tables in the clause */ }; /* ** A WhereTerm with eOperator==WO_AND has its u.pAndInfo pointer set to ** a dynamically allocated instance of the following structure. */ struct WhereAndInfo { |
︙ | ︙ | |||
264 265 266 267 268 269 270 | /* ** Deallocate all memory associated with a WhereOrInfo object. */ static void whereOrInfoDelete(sqlite3 *db, WhereOrInfo *p){ if( p ){ whereClauseClear(&p->wc); | < | 263 264 265 266 267 268 269 270 271 272 273 274 275 276 | /* ** Deallocate all memory associated with a WhereOrInfo object. */ static void whereOrInfoDelete(sqlite3 *db, WhereOrInfo *p){ if( p ){ whereClauseClear(&p->wc); sqlite3DbFree(db, p); } } /* ** Deallocate all memory associated with a WhereAndInfo object. */ |
︙ | ︙ | |||
822 823 824 825 826 827 828 | assert( (pTerm->wtFlags & (TERM_DYNAMIC|TERM_ORINFO|TERM_ANDINFO))==0 ); assert( pExpr->op==TK_OR ); pTerm->u.pOrInfo = pOrInfo = sqlite3DbMallocRaw(db, sizeof(*pOrInfo)); if( pOrInfo==0 ) return; pTerm->wtFlags |= TERM_ORINFO; pOrWc = &pOrInfo->wc; whereClauseInit(pOrWc, pWC->pParse, pMaskSet); | < | 820 821 822 823 824 825 826 827 828 829 830 831 832 833 | assert( (pTerm->wtFlags & (TERM_DYNAMIC|TERM_ORINFO|TERM_ANDINFO))==0 ); assert( pExpr->op==TK_OR ); pTerm->u.pOrInfo = pOrInfo = sqlite3DbMallocRaw(db, sizeof(*pOrInfo)); if( pOrInfo==0 ) return; pTerm->wtFlags |= TERM_ORINFO; pOrWc = &pOrInfo->wc; whereClauseInit(pOrWc, pWC->pParse, pMaskSet); whereSplit(pOrWc, pExpr, TK_OR); exprAnalyzeAll(pSrc, pOrWc); if( db->mallocFailed ) return; assert( pOrWc->nTerm>=2 ); /* ** Compute the set of tables that might satisfy cases 1 or 2. |
︙ | ︙ | |||
958 959 960 961 962 963 964 | pTerm->nChild = 1; }else{ sqlite3ExprListDelete(db, pList); } pTerm->eOperator = 0; /* case 1 trumps case 2 */ } } | < < < < < < | 955 956 957 958 959 960 961 962 963 964 965 966 967 968 | pTerm->nChild = 1; }else{ sqlite3ExprListDelete(db, pList); } pTerm->eOperator = 0; /* case 1 trumps case 2 */ } } } #endif /* !SQLITE_OMIT_OR_OPTIMIZATION && !SQLITE_OMIT_SUBQUERY */ /* ** The input to this routine is an WhereTerm structure with only the ** "pExpr" field filled in. The job of this routine is to analyze the |
︙ | ︙ | |||
1719 1720 1721 1722 1723 1724 1725 1726 1727 1728 1729 1730 1731 1732 | Index *pProbe; /* An index we are evaluating */ int rev; /* True to scan in reverse order */ int wsFlags; /* Flags associated with pProbe */ int nEq; /* Number of == or IN constraints */ int eqTermMask; /* Mask of valid equality operators */ double cost; /* Cost of using pProbe */ double nRow; /* Estimated number of rows in result set */ WHERETRACE(("bestIndex: tbl=%s notReady=%llx\n", pSrc->pTab->zName,notReady)); pProbe = pSrc->pTab->pIndex; if( pSrc->notIndexed ){ pProbe = 0; } | > > | 1710 1711 1712 1713 1714 1715 1716 1717 1718 1719 1720 1721 1722 1723 1724 1725 | Index *pProbe; /* An index we are evaluating */ int rev; /* True to scan in reverse order */ int wsFlags; /* Flags associated with pProbe */ int nEq; /* Number of == or IN constraints */ int eqTermMask; /* Mask of valid equality operators */ double cost; /* Cost of using pProbe */ double nRow; /* Estimated number of rows in result set */ int i; /* Loop counter */ Bitmask maskSrc; /* Bitmask for the pSrc table */ WHERETRACE(("bestIndex: tbl=%s notReady=%llx\n", pSrc->pTab->zName,notReady)); pProbe = pSrc->pTab->pIndex; if( pSrc->notIndexed ){ pProbe = 0; } |
︙ | ︙ | |||
1816 1817 1818 1819 1820 1821 1822 1823 1824 1825 1826 1827 1828 1829 | } if( cost<pCost->rCost ){ pCost->rCost = cost; pCost->nRow = nRow; pCost->plan.wsFlags = wsFlags; } } /* If the pSrc table is the right table of a LEFT JOIN then we may not ** use an index to satisfy IS NULL constraints on that table. This is ** because columns might end up being NULL if the table does not match - ** a circumstance which the index cannot help us discover. Ticket #2177. */ if( (pSrc->jointype & JT_LEFT)!=0 ){ | > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > | 1809 1810 1811 1812 1813 1814 1815 1816 1817 1818 1819 1820 1821 1822 1823 1824 1825 1826 1827 1828 1829 1830 1831 1832 1833 1834 1835 1836 1837 1838 1839 1840 1841 1842 1843 1844 1845 1846 1847 1848 1849 1850 1851 1852 1853 1854 1855 1856 1857 1858 1859 1860 | } if( cost<pCost->rCost ){ pCost->rCost = cost; pCost->nRow = nRow; pCost->plan.wsFlags = wsFlags; } } #if SQLITE_ENABLE_MULTI_OR /* Search for an OR-clause that can be used to look up the table. */ maskSrc = getMask(pWC->pMaskSet, iCur); for(i=0, pTerm=pWC->a; i<pWC->nTerm; i++, pTerm++){ WhereClause tempWC; tempWC = *pWC; tempWC.nSlot = 1; if( pTerm->eOperator==WO_OR && ((pTerm->prereqAll & ~maskSrc) & notReady)==0 && (pTerm->u.pOrInfo->indexable & maskSrc)!=0 ){ WhereClause *pOrWC = &pTerm->u.pOrInfo->wc; WhereTerm *pOrTerm; int j; double rTotal = 0; double nRow = 0; for(j=0, pOrTerm=pOrWC->a; j<pOrWC->nTerm; j++, pOrTerm++){ WhereCost sTermCost; if( pOrTerm->leftCursor!=iCur ) continue; tempWC.a = pOrTerm; bestIndex(pParse, &tempWC, pSrc, notReady, 0, &sTermCost); if( sTermCost.plan.wsFlags==0 ){ rTotal = pCost->rCost; break; } rTotal += sTermCost.rCost; nRow += sTermCost.nRow; } if( rTotal<pCost->rCost ){ pCost->rCost = rTotal; pCost->nRow = nRow; pCost->plan.wsFlags = WHERE_MULTI_OR; pCost->plan.u.pTerm = pTerm; } } } #endif /* If the pSrc table is the right table of a LEFT JOIN then we may not ** use an index to satisfy IS NULL constraints on that table. This is ** because columns might end up being NULL if the table does not match - ** a circumstance which the index cannot help us discover. Ticket #2177. */ if( (pSrc->jointype & JT_LEFT)!=0 ){ |
︙ | ︙ | |||
2525 2526 2527 2528 2529 2530 2531 | /* Record the instruction used to terminate the loop. Disable ** WHERE clause terms made redundant by the index range scan. */ pLevel->op = bRev ? OP_Prev : OP_Next; pLevel->p1 = iIdxCur; disableTerm(pLevel, pRangeStart); disableTerm(pLevel, pRangeEnd); | > > > | | 2556 2557 2558 2559 2560 2561 2562 2563 2564 2565 2566 2567 2568 2569 2570 2571 2572 2573 | /* Record the instruction used to terminate the loop. Disable ** WHERE clause terms made redundant by the index range scan. */ pLevel->op = bRev ? OP_Prev : OP_Next; pLevel->p1 = iIdxCur; disableTerm(pLevel, pRangeStart); disableTerm(pLevel, pRangeEnd); }else #if SQLITE_ENABLE_MULTI_OR if( pLevel->plan.wsFlags & WHERE_MULTI_OR ){ /* Case 4: Two or more separately indexed terms connected by OR ** ** Example: ** ** CREATE TABLE t1(a,b,c,d); ** CREATE INDEX i1 ON t1(a); ** CREATE INDEX i2 ON t1(b); |
︙ | ︙ | |||
2558 2559 2560 2561 2562 2563 2564 2565 2566 2567 2568 2569 2570 2571 2572 | ** B: */ int regRowset; /* Register holding the RowSet object */ int regNextRowid; /* Register holding next rowid */ WhereTerm *pTerm; /* The complete OR-clause */ WhereClause *pOrWc; /* The OR-clause broken out into subterms */ WhereTerm *pOrTerm; /* A single subterm within the OR-clause */ pTerm = pLevel->plan.u.pTerm; assert( pTerm!=0 ); assert( pTerm->eOperator==WO_OR ); assert( (pTerm->wtFlags & TERM_ORINFO)!=0 ); pOrWc = &pTerm->u.pOrInfo->wc; regRowset = sqlite3GetTempReg(pParse); | > > | > > > > > > > | > > | < > | > > > | 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 2622 2623 2624 2625 2626 2627 2628 2629 2630 2631 2632 2633 2634 2635 2636 2637 2638 2639 2640 2641 | ** B: */ int regRowset; /* Register holding the RowSet object */ int regNextRowid; /* Register holding next rowid */ WhereTerm *pTerm; /* The complete OR-clause */ WhereClause *pOrWc; /* The OR-clause broken out into subterms */ WhereTerm *pOrTerm; /* A single subterm within the OR-clause */ SrcList oneTab; /* Shortened table list */ pTerm = pLevel->plan.u.pTerm; assert( pTerm!=0 ); assert( pTerm->eOperator==WO_OR ); assert( (pTerm->wtFlags & TERM_ORINFO)!=0 ); pOrWc = &pTerm->u.pOrInfo->wc; regRowset = sqlite3GetTempReg(pParse); regNextRowid = sqlite3GetTempReg(pParse); sqlite3VdbeAddOp2(v, OP_Null, 0, regRowset); oneTab.nSrc = 1; oneTab.nAlloc = 1; oneTab.a[0] = *pTabItem; for(j=0, pOrTerm=pOrWc->a; j<pOrWc->nTerm; j++, pOrTerm++){ WhereInfo *pSubWInfo; if( pOrTerm->leftCursor!=iCur ) continue; pSubWInfo = sqlite3WhereBegin(pParse, &oneTab, pOrTerm->pExpr, 0, 0); if( pSubWInfo ){ sqlite3VdbeAddOp2(v, OP_Rowid, oneTab.a[0].iCursor, regNextRowid); sqlite3VdbeAddOp2(v, OP_RowSetAdd, regRowset, regNextRowid); pSubWInfo->a[0].plan.wsFlags |= WHERE_IDX_ONLY; sqlite3WhereEnd(pSubWInfo); } } sqlite3VdbeResolveLabel(v, addrCont); addrCont = sqlite3VdbeAddOp3(v, OP_RowSetRead, regRowset, addrBrk, regNextRowid); sqlite3VdbeAddOp2(v, OP_Seek, iCur, regNextRowid); sqlite3ReleaseTempReg(pParse, regNextRowid); pLevel->op = OP_Goto; pLevel->p2 = addrCont; }else #endif /* SQLITE_ENABLE_MULTI_OR */ { /* Case 5: There is no usable index. We must do a complete ** scan of the entire table. */ assert( omitTable==0 ); assert( bRev==0 ); pLevel->op = OP_Next; pLevel->p1 = iCur; |
︙ | ︙ |