Many hyperlinks are disabled.
Use anonymous login
to enable hyperlinks.
Overview
Comment: | Automatically generate transient indices for tables in joins that would otherwise have to use a full table scan. |
---|---|
Downloads: | Tarball | ZIP archive |
Timelines: | family | ancestors | descendants | both | experimental |
Files: | files | file ages | folders |
SHA1: |
1b2a04125f964e14f3fb90171c5ab86a |
User & Date: | drh 2010-04-06 15:57:05.000 |
Context
2010-04-06
| ||
18:28 | Progress toward getting automatic indices to work. Still failing in corner cases. (check-in: ac6d0fba78 user: drh tags: experimental) | |
15:57 | Automatically generate transient indices for tables in joins that would otherwise have to use a full table scan. (check-in: 1b2a04125f user: drh tags: experimental) | |
2010-04-05
| ||
15:11 | Minor comment changes to the OP_OpenEphemeral header. No changes to code. (check-in: 8e1d7ef47f user: drh tags: trunk) | |
Changes
Changes to src/prepare.c.
︙ | ︙ | |||
575 576 577 578 579 580 581 582 583 584 585 586 587 588 | } } } sqlite3VtabUnlockList(db); pParse->db = db; if( nBytes>=0 && (nBytes==0 || zSql[nBytes-1]!=0) ){ char *zSqlCopy; int mxLen = db->aLimit[SQLITE_LIMIT_SQL_LENGTH]; testcase( nBytes==mxLen ); testcase( nBytes==mxLen+1 ); if( nBytes>mxLen ){ sqlite3Error(db, SQLITE_TOOBIG, "statement too long"); | > | 575 576 577 578 579 580 581 582 583 584 585 586 587 588 589 | } } } sqlite3VtabUnlockList(db); pParse->db = db; pParse->nQueryLoop = (double)1; if( nBytes>=0 && (nBytes==0 || zSql[nBytes-1]!=0) ){ char *zSqlCopy; int mxLen = db->aLimit[SQLITE_LIMIT_SQL_LENGTH]; testcase( nBytes==mxLen ); testcase( nBytes==mxLen+1 ); if( nBytes>mxLen ){ sqlite3Error(db, SQLITE_TOOBIG, "statement too long"); |
︙ | ︙ | |||
596 597 598 599 600 601 602 603 604 605 606 607 608 609 | pParse->zTail = &zSql[pParse->zTail-zSqlCopy]; }else{ pParse->zTail = &zSql[nBytes]; } }else{ sqlite3RunParser(pParse, zSql, &zErrMsg); } if( db->mallocFailed ){ pParse->rc = SQLITE_NOMEM; } if( pParse->rc==SQLITE_DONE ) pParse->rc = SQLITE_OK; if( pParse->checkSchema ){ schemaIsValid(pParse); | > | 597 598 599 600 601 602 603 604 605 606 607 608 609 610 611 | pParse->zTail = &zSql[pParse->zTail-zSqlCopy]; }else{ pParse->zTail = &zSql[nBytes]; } }else{ sqlite3RunParser(pParse, zSql, &zErrMsg); } assert( 1==(int)pParse->nQueryLoop ); if( db->mallocFailed ){ pParse->rc = SQLITE_NOMEM; } if( pParse->rc==SQLITE_DONE ) pParse->rc = SQLITE_OK; if( pParse->checkSchema ){ schemaIsValid(pParse); |
︙ | ︙ |
Changes to src/sqliteInt.h.
︙ | ︙ | |||
297 298 299 300 301 302 303 304 305 306 307 308 309 310 | /* ** If compiling for a processor that lacks floating point support, ** substitute integer for floating-point */ #ifdef SQLITE_OMIT_FLOATING_POINT # define double sqlite_int64 # define LONGDOUBLE_TYPE sqlite_int64 # ifndef SQLITE_BIG_DBL # define SQLITE_BIG_DBL (((sqlite3_int64)1)<<50) # endif # define SQLITE_OMIT_DATETIME_FUNCS 1 # define SQLITE_OMIT_TRACE 1 # undef SQLITE_MIXED_ENDIAN_64BIT_FLOAT | > | 297 298 299 300 301 302 303 304 305 306 307 308 309 310 311 | /* ** If compiling for a processor that lacks floating point support, ** substitute integer for floating-point */ #ifdef SQLITE_OMIT_FLOATING_POINT # define double sqlite_int64 # define float sqlite_int64 # define LONGDOUBLE_TYPE sqlite_int64 # ifndef SQLITE_BIG_DBL # define SQLITE_BIG_DBL (((sqlite3_int64)1)<<50) # endif # define SQLITE_OMIT_DATETIME_FUNCS 1 # define SQLITE_OMIT_TRACE 1 # undef SQLITE_MIXED_ENDIAN_64BIT_FLOAT |
︙ | ︙ | |||
1880 1881 1882 1883 1884 1885 1886 | ** and the WhereInfo.wctrlFlags member. */ #define WHERE_ORDERBY_NORMAL 0x0000 /* No-op */ #define WHERE_ORDERBY_MIN 0x0001 /* ORDER BY processing for min() func */ #define WHERE_ORDERBY_MAX 0x0002 /* ORDER BY processing for max() func */ #define WHERE_ONEPASS_DESIRED 0x0004 /* Want to do one-pass UPDATE/DELETE */ #define WHERE_DUPLICATES_OK 0x0008 /* Ok to return a row more than once */ | | | 1881 1882 1883 1884 1885 1886 1887 1888 1889 1890 1891 1892 1893 1894 1895 | ** and the WhereInfo.wctrlFlags member. */ #define WHERE_ORDERBY_NORMAL 0x0000 /* No-op */ #define WHERE_ORDERBY_MIN 0x0001 /* ORDER BY processing for min() func */ #define WHERE_ORDERBY_MAX 0x0002 /* ORDER BY processing for max() func */ #define WHERE_ONEPASS_DESIRED 0x0004 /* Want to do one-pass UPDATE/DELETE */ #define WHERE_DUPLICATES_OK 0x0008 /* Ok to return a row more than once */ #define WHERE_OMIT_OPEN 0x0010 /* Table cursors are already open */ #define WHERE_OMIT_CLOSE 0x0020 /* Omit close of table & index cursors */ #define WHERE_FORCE_TABLE 0x0040 /* Do not use an index-only search */ #define WHERE_ONETABLE_ONLY 0x0080 /* Only code the 1st table in pTabList */ /* ** The WHERE clause processing routine has two halves. The ** first part does the start of the WHERE loop and the second |
︙ | ︙ | |||
1903 1904 1905 1906 1907 1908 1909 1910 1911 1912 1913 1914 1915 1916 | u8 untestedTerms; /* Not all WHERE terms resolved by outer loop */ SrcList *pTabList; /* List of tables in the join */ int iTop; /* The very beginning of the WHERE loop */ int iContinue; /* Jump here to continue with next record */ int iBreak; /* Jump here to break out of the loop */ int nLevel; /* Number of nested loop */ struct WhereClause *pWC; /* Decomposition of the WHERE clause */ WhereLevel a[1]; /* Information about each nest loop in WHERE */ }; /* ** A NameContext defines a context in which to resolve table and column ** names. The context consists of a list of tables (the pSrcList) field and ** a list of named expression (pEList). The named expression list may | > | 1904 1905 1906 1907 1908 1909 1910 1911 1912 1913 1914 1915 1916 1917 1918 | u8 untestedTerms; /* Not all WHERE terms resolved by outer loop */ SrcList *pTabList; /* List of tables in the join */ int iTop; /* The very beginning of the WHERE loop */ int iContinue; /* Jump here to continue with next record */ int iBreak; /* Jump here to break out of the loop */ int nLevel; /* Number of nested loop */ struct WhereClause *pWC; /* Decomposition of the WHERE clause */ double savedNQueryLoop; /* pParse->nQueryLoop outside the WHERE loop */ WhereLevel a[1]; /* Information about each nest loop in WHERE */ }; /* ** A NameContext defines a context in which to resolve table and column ** names. The context consists of a list of tables (the pSrcList) field and ** a list of named expression (pEList). The named expression list may |
︙ | ︙ | |||
2144 2145 2146 2147 2148 2149 2150 2151 2152 2153 2154 2155 2156 2157 | Parse *pToplevel; /* Parse structure for main program (or NULL) */ Table *pTriggerTab; /* Table triggers are being coded for */ u32 oldmask; /* Mask of old.* columns referenced */ u32 newmask; /* Mask of new.* columns referenced */ u8 eTriggerOp; /* TK_UPDATE, TK_INSERT or TK_DELETE */ u8 eOrconf; /* Default ON CONFLICT policy for trigger steps */ u8 disableTriggers; /* True to disable triggers */ /* Above is constant between recursions. Below is reset before and after ** each recursion */ int nVar; /* Number of '?' variables seen in the SQL so far */ int nVarExpr; /* Number of used slots in apVarExpr[] */ int nVarExprAlloc; /* Number of allocated slots in apVarExpr[] */ | > | 2146 2147 2148 2149 2150 2151 2152 2153 2154 2155 2156 2157 2158 2159 2160 | Parse *pToplevel; /* Parse structure for main program (or NULL) */ Table *pTriggerTab; /* Table triggers are being coded for */ u32 oldmask; /* Mask of old.* columns referenced */ u32 newmask; /* Mask of new.* columns referenced */ u8 eTriggerOp; /* TK_UPDATE, TK_INSERT or TK_DELETE */ u8 eOrconf; /* Default ON CONFLICT policy for trigger steps */ u8 disableTriggers; /* True to disable triggers */ double nQueryLoop; /* Estimated number of iterations of a query */ /* Above is constant between recursions. Below is reset before and after ** each recursion */ int nVar; /* Number of '?' variables seen in the SQL so far */ int nVarExpr; /* Number of used slots in apVarExpr[] */ int nVarExprAlloc; /* Number of allocated slots in apVarExpr[] */ |
︙ | ︙ |
Changes to src/trigger.c.
︙ | ︙ | |||
822 823 824 825 826 827 828 829 830 831 832 833 834 835 | memset(&sNC, 0, sizeof(sNC)); sNC.pParse = pSubParse; pSubParse->db = db; pSubParse->pTriggerTab = pTab; pSubParse->pToplevel = pTop; pSubParse->zAuthContext = pTrigger->zName; pSubParse->eTriggerOp = pTrigger->op; v = sqlite3GetVdbe(pSubParse); if( v ){ VdbeComment((v, "Start: %s.%s (%s %s%s%s ON %s)", pTrigger->zName, onErrorText(orconf), (pTrigger->tr_tm==TRIGGER_BEFORE ? "BEFORE" : "AFTER"), (pTrigger->op==TK_UPDATE ? "UPDATE" : ""), | > | 822 823 824 825 826 827 828 829 830 831 832 833 834 835 836 | memset(&sNC, 0, sizeof(sNC)); sNC.pParse = pSubParse; pSubParse->db = db; pSubParse->pTriggerTab = pTab; pSubParse->pToplevel = pTop; pSubParse->zAuthContext = pTrigger->zName; pSubParse->eTriggerOp = pTrigger->op; pSubParse->nQueryLoop = pParse->nQueryLoop; v = sqlite3GetVdbe(pSubParse); if( v ){ VdbeComment((v, "Start: %s.%s (%s %s%s%s ON %s)", pTrigger->zName, onErrorText(orconf), (pTrigger->tr_tm==TRIGGER_BEFORE ? "BEFORE" : "AFTER"), (pTrigger->op==TK_UPDATE ? "UPDATE" : ""), |
︙ | ︙ |
Changes to src/vtab.c.
︙ | ︙ | |||
653 654 655 656 657 658 659 660 661 662 663 664 665 666 | pParse = sqlite3StackAllocZero(db, sizeof(*pParse)); if( pParse==0 ){ rc = SQLITE_NOMEM; }else{ pParse->declareVtab = 1; pParse->db = db; if( SQLITE_OK==sqlite3RunParser(pParse, zCreateTable, &zErr) && pParse->pNewTable && !db->mallocFailed && !pParse->pNewTable->pSelect && (pParse->pNewTable->tabFlags & TF_Virtual)==0 ){ | > | 653 654 655 656 657 658 659 660 661 662 663 664 665 666 667 | pParse = sqlite3StackAllocZero(db, sizeof(*pParse)); if( pParse==0 ){ rc = SQLITE_NOMEM; }else{ pParse->declareVtab = 1; pParse->db = db; pParse->nQueryLoop = 1; if( SQLITE_OK==sqlite3RunParser(pParse, zCreateTable, &zErr) && pParse->pNewTable && !db->mallocFailed && !pParse->pNewTable->pSelect && (pParse->pNewTable->tabFlags & TF_Virtual)==0 ){ |
︙ | ︙ |
Changes to src/where.c.
︙ | ︙ | |||
231 232 233 234 235 236 237 238 239 240 241 242 243 244 245 246 247 248 249 250 251 252 253 | #define WHERE_ROWID_EQ 0x00001000 /* rowid=EXPR or rowid IN (...) */ #define WHERE_ROWID_RANGE 0x00002000 /* rowid<EXPR and/or rowid>EXPR */ #define WHERE_COLUMN_EQ 0x00010000 /* x=EXPR or x IN (...) or x IS NULL */ #define WHERE_COLUMN_RANGE 0x00020000 /* x<EXPR and/or x>EXPR */ #define WHERE_COLUMN_IN 0x00040000 /* x IN (...) */ #define WHERE_COLUMN_NULL 0x00080000 /* x IS NULL */ #define WHERE_INDEXED 0x000f0000 /* Anything that uses an index */ #define WHERE_IN_ABLE 0x000f1000 /* Able to support an IN operator */ #define WHERE_TOP_LIMIT 0x00100000 /* x<EXPR or x<=EXPR constraint */ #define WHERE_BTM_LIMIT 0x00200000 /* x>EXPR or x>=EXPR constraint */ #define WHERE_IDX_ONLY 0x00800000 /* Use index only - omit table */ #define WHERE_ORDERBY 0x01000000 /* Output will appear in correct order */ #define WHERE_REVERSE 0x02000000 /* Scan in reverse order */ #define WHERE_UNIQUE 0x04000000 /* Selects no more than one row */ #define WHERE_VIRTUALTABLE 0x08000000 /* Use virtual-table processing */ #define WHERE_MULTI_OR 0x10000000 /* OR using multiple indices */ /* ** Initialize a preallocated WhereClause structure. */ static void whereClauseInit( WhereClause *pWC, /* The WhereClause to be initialized */ Parse *pParse, /* The parsing context */ | > > | 231 232 233 234 235 236 237 238 239 240 241 242 243 244 245 246 247 248 249 250 251 252 253 254 255 | #define WHERE_ROWID_EQ 0x00001000 /* rowid=EXPR or rowid IN (...) */ #define WHERE_ROWID_RANGE 0x00002000 /* rowid<EXPR and/or rowid>EXPR */ #define WHERE_COLUMN_EQ 0x00010000 /* x=EXPR or x IN (...) or x IS NULL */ #define WHERE_COLUMN_RANGE 0x00020000 /* x<EXPR and/or x>EXPR */ #define WHERE_COLUMN_IN 0x00040000 /* x IN (...) */ #define WHERE_COLUMN_NULL 0x00080000 /* x IS NULL */ #define WHERE_INDEXED 0x000f0000 /* Anything that uses an index */ #define WHERE_NOT_FULLSCAN 0x000f3000 /* Does not do a full table scan */ #define WHERE_IN_ABLE 0x000f1000 /* Able to support an IN operator */ #define WHERE_TOP_LIMIT 0x00100000 /* x<EXPR or x<=EXPR constraint */ #define WHERE_BTM_LIMIT 0x00200000 /* x>EXPR or x>=EXPR constraint */ #define WHERE_IDX_ONLY 0x00800000 /* Use index only - omit table */ #define WHERE_ORDERBY 0x01000000 /* Output will appear in correct order */ #define WHERE_REVERSE 0x02000000 /* Scan in reverse order */ #define WHERE_UNIQUE 0x04000000 /* Selects no more than one row */ #define WHERE_VIRTUALTABLE 0x08000000 /* Use virtual-table processing */ #define WHERE_MULTI_OR 0x10000000 /* OR using multiple indices */ #define WHERE_TEMP_INDEX 0x20000000 /* Uses an ephemeral index */ /* ** Initialize a preallocated WhereClause structure. */ static void whereClauseInit( WhereClause *pWC, /* The WhereClause to be initialized */ Parse *pParse, /* The parsing context */ |
︙ | ︙ | |||
1630 1631 1632 1633 1634 1635 1636 1637 1638 1639 1640 1641 1642 1643 | pCost->plan.wsFlags = flags; pCost->plan.u.pTerm = pTerm; } } } #endif /* SQLITE_OMIT_OR_OPTIMIZATION */ } #ifndef SQLITE_OMIT_VIRTUALTABLE /* ** Allocate and populate an sqlite3_index_info structure. It is the ** responsibility of the caller to eventually release the structure ** by passing the pointer returned by this function to sqlite3_free(). */ | > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > | 1632 1633 1634 1635 1636 1637 1638 1639 1640 1641 1642 1643 1644 1645 1646 1647 1648 1649 1650 1651 1652 1653 1654 1655 1656 1657 1658 1659 1660 1661 1662 1663 1664 1665 1666 1667 1668 1669 1670 1671 1672 1673 1674 1675 1676 1677 1678 1679 1680 1681 1682 1683 1684 1685 1686 1687 1688 1689 1690 1691 1692 1693 1694 1695 1696 1697 1698 1699 1700 1701 1702 1703 1704 1705 1706 1707 1708 1709 1710 1711 1712 1713 1714 1715 1716 1717 1718 1719 1720 1721 1722 1723 1724 1725 1726 1727 1728 1729 1730 1731 1732 1733 1734 1735 1736 1737 1738 1739 1740 1741 1742 1743 1744 1745 1746 1747 1748 1749 1750 1751 1752 1753 1754 1755 1756 1757 1758 1759 1760 1761 1762 1763 1764 1765 1766 1767 1768 1769 1770 1771 1772 1773 1774 1775 1776 1777 1778 1779 1780 1781 1782 1783 1784 1785 1786 1787 1788 1789 1790 1791 1792 1793 1794 1795 1796 1797 1798 | pCost->plan.wsFlags = flags; pCost->plan.u.pTerm = pTerm; } } } #endif /* SQLITE_OMIT_OR_OPTIMIZATION */ } /* ** If the query plan for pSrc specified in pCost is a full table scan ** an indexing is allows (if there is no NOT INDEXED clause) and it ** possible to construct a transient index that would perform better ** than a full table scan even when the cost of constructing the index ** is taken into account, then alter the query plan to use the ** transient index. */ static void bestTransientIndex( Parse *pParse, /* The parsing context */ WhereClause *pWC, /* The WHERE clause */ struct SrcList_item *pSrc, /* The FROM clause term to search */ Bitmask notReady, /* Mask of cursors that are not available */ WhereCost *pCost /* Lowest cost query plan */ ){ double nTableRow; /* Rows in the input table */ double logN; /* log(nTableRow) */ double costTempIdx; /* per-query cost of the transient index */ WhereTerm *pTerm; /* A single term of the WHERE clause */ WhereTerm *pWCEnd; /* End of pWC->a[] */ if( (pCost->plan.wsFlags & WHERE_NOT_FULLSCAN)!=0 ){ /* We already have some kind of index in use for this query. */ return; } if( pSrc->notIndexed ){ /* The NOT INDEXED clause appears in the SQL. */ return; } assert( pParse->nQueryLoop >= (double)1 ); nTableRow = pSrc->pIndex ? pSrc->pIndex->aiRowEst[0] : 1000000; logN = estLog(nTableRow); costTempIdx = 2*logN*(nTableRow/pParse->nQueryLoop + 1); if( costTempIdx>=pCost->rCost ){ /* The cost of creating the transient table would be greater than ** doing the full table scan */ return; } /* Search for any equality comparison term */ pWCEnd = &pWC->a[pWC->nTerm]; for(pTerm=pWC->a; pTerm<pWCEnd; pTerm++){ if( pTerm->leftCursor==pSrc->iCursor && (pTerm->prereqRight & notReady)==0 && (pTerm->eOperator & WO_EQ)!=0 ){ WHERETRACE(("auto-index reduces cost from %.2f to %.2f\n", pCost->rCost, costTempIdx)); pCost->rCost = costTempIdx; pCost->nRow = logN + 1; pCost->plan.wsFlags = WHERE_TEMP_INDEX; pCost->used = pTerm->prereqRight; break; } } } /* ** Generate code to construct a transient index. Also create the ** corresponding Index structure and put it in pLevel->plan.u.pIdx. */ static void constructTransientIndex( Parse *pParse, /* The parsing context */ WhereClause *pWC, /* The WHERE clause */ struct SrcList_item *pSrc, /* The FROM clause term to get the next index */ Bitmask notReady, /* Mask of cursors that are not available */ WhereLevel *pLevel /* Write new index here */ ){ int nColumn; /* Number of columns in the constructed index */ WhereTerm *pTerm; /* A single term of the WHERE clause */ WhereTerm *pWCEnd; /* End of pWC->a[] */ int nByte; /* Byte of memory needed for pIdx */ Index *pIdx; /* Object describing the transient index */ Vdbe *v; /* Prepared statement under construction */ int regIsInit; /* Register set by initialization */ int addrInit; /* Address of the initialization bypass jump */ Table *pTable; /* The table being indexed */ KeyInfo *pKeyinfo; /* Key information for the index */ int addrTop; /* Top of the index fill loop */ int regRecord; /* Register holding an index record */ int n; /* Column counter */ /* Generate code to skip over the creation and initialization of the ** transient index on 2nd and subsequent iterations of the loop. */ v = pParse->pVdbe; assert( v!=0 ); regIsInit = ++pParse->nMem; addrInit = sqlite3VdbeAddOp1(v, OP_If, regIsInit); sqlite3VdbeAddOp2(v, OP_Integer, 1, regIsInit); /* Count the number of columns that will be added to the index */ nColumn = 0; pWCEnd = &pWC->a[pWC->nTerm]; for(pTerm=pWC->a; pTerm<pWCEnd; pTerm++){ if( pTerm->leftCursor==pSrc->iCursor && (pTerm->prereqRight & notReady)==0 && (pTerm->eOperator & WO_EQ)!=0 ){ nColumn++; } } assert( nColumn>0 ); /* Construct the Index object to describe this index */ nByte = sizeof(Index); nByte += nColumn*sizeof(int); /* Index.aiColumn */ nByte += nColumn*sizeof(char*); /* Index.azColl */ nByte += nColumn; /* Index.aSortOrder */ pIdx = sqlite3DbMallocZero(pParse->db, nByte); if( pIdx==0 ) return; pLevel->plan.u.pIdx = pIdx; pIdx->azColl = (char**)&pIdx[1]; pIdx->aiColumn = (int*)&pIdx->azColl[nColumn]; pIdx->aSortOrder = (u8*)&pIdx->aiColumn[nColumn]; pIdx->zName = "auto-index"; pIdx->nColumn = nColumn; pIdx->pTable = pTable = pSrc->pTab; n = 0; for(pTerm=pWC->a; pTerm<pWCEnd; pTerm++){ if( pTerm->leftCursor==pSrc->iCursor && (pTerm->prereqRight & notReady)==0 && (pTerm->eOperator & WO_EQ)!=0 ){ int iCol = pTerm->u.leftColumn; pIdx->aiColumn[n] = iCol; pIdx->azColl[n] = pTable->aCol[iCol].zColl; if( pIdx->azColl[n]==0 ) pIdx->azColl[n] = "BINARY"; n++; } } assert( n==pIdx->nColumn ); /* Create the transient index */ pKeyinfo = sqlite3IndexKeyinfo(pParse, pIdx); assert( pLevel->iIdxCur>=0 ); sqlite3VdbeAddOp4(v, OP_OpenEphemeral, pLevel->iIdxCur, nColumn+1, 0, (char*)pKeyinfo, P4_KEYINFO_HANDOFF); /* Fill the transient index with content */ addrTop = sqlite3VdbeAddOp1(v, OP_Rewind, pLevel->iTabCur); regRecord = sqlite3GetTempReg(pParse); sqlite3GenerateIndexKey(pParse, pIdx, pLevel->iTabCur, regRecord, 1); sqlite3VdbeAddOp2(v, OP_IdxInsert, pLevel->iIdxCur, regRecord); sqlite3VdbeChangeP5(v, OPFLAG_USESEEKRESULT); sqlite3VdbeAddOp2(v, OP_Next, pLevel->iTabCur, addrTop+1); sqlite3VdbeJumpHere(v, addrTop); sqlite3ReleaseTempReg(pParse, regRecord); /* Jump here when skipping the initialization */ sqlite3VdbeJumpHere(v, addrInit); } #ifndef SQLITE_OMIT_VIRTUALTABLE /* ** Allocate and populate an sqlite3_index_info structure. It is the ** responsibility of the caller to eventually release the structure ** by passing the pointer returned by this function to sqlite3_free(). */ |
︙ | ︙ | |||
2477 2478 2479 2480 2481 2482 2483 | */ if( pIdx && bLookup==0 ){ cost /= (double)2; } /**** Cost of using this index has now been computed ****/ WHERETRACE(( | | | | | 2632 2633 2634 2635 2636 2637 2638 2639 2640 2641 2642 2643 2644 2645 2646 2647 2648 2649 | */ if( pIdx && bLookup==0 ){ cost /= (double)2; } /**** Cost of using this index has now been computed ****/ WHERETRACE(( "%s(%s): nEq=%d nInMul=%d nBound=%d bSort=%d bLookup=%d wsFlags=0x%x\n" " notReady=0x%llx nRow=%.2f cost=%.2f used=0x%llx\n", pSrc->pTab->zName, (pIdx ? pIdx->zName : "ipk"), nEq, nInMul, nBound, bSort, bLookup, wsFlags, notReady, nRow, cost, used )); /* If this index is the best we have seen so far, then record this ** index and its cost in the pCost structure. */ if( (!pIdx || wsFlags) && cost<pCost->rCost ){ pCost->rCost = cost; |
︙ | ︙ | |||
2525 2526 2527 2528 2529 2530 2531 2532 2533 2534 2535 2536 2537 2538 | ); WHERETRACE(("best index is: %s\n", (pCost->plan.u.pIdx ? pCost->plan.u.pIdx->zName : "ipk") )); bestOrClauseIndex(pParse, pWC, pSrc, notReady, pOrderBy, pCost); pCost->plan.wsFlags |= eqTermMask; } /* ** Find the query plan for accessing table pSrc->pTab. Write the ** best query plan and its cost into the WhereCost object supplied ** as the last parameter. This function may calculate the cost of | > | 2680 2681 2682 2683 2684 2685 2686 2687 2688 2689 2690 2691 2692 2693 2694 | ); WHERETRACE(("best index is: %s\n", (pCost->plan.u.pIdx ? pCost->plan.u.pIdx->zName : "ipk") )); bestOrClauseIndex(pParse, pWC, pSrc, notReady, pOrderBy, pCost); bestTransientIndex(pParse, pWC, pSrc, notReady, pCost); pCost->plan.wsFlags |= eqTermMask; } /* ** Find the query plan for accessing table pSrc->pTab. Write the ** best query plan and its cost into the WhereCost object supplied ** as the last parameter. This function may calculate the cost of |
︙ | ︙ | |||
3467 3468 3469 3470 3471 3472 3473 3474 3475 3476 3477 3478 3479 3480 | if( pInfo ){ /* assert( pInfo->needToFreeIdxStr==0 || db->mallocFailed ); */ if( pInfo->needToFreeIdxStr ){ sqlite3_free(pInfo->idxStr); } sqlite3DbFree(db, pInfo); } } whereClauseClear(pWInfo->pWC); sqlite3DbFree(db, pWInfo); } } | > > > | 3623 3624 3625 3626 3627 3628 3629 3630 3631 3632 3633 3634 3635 3636 3637 3638 3639 | if( pInfo ){ /* assert( pInfo->needToFreeIdxStr==0 || db->mallocFailed ); */ if( pInfo->needToFreeIdxStr ){ sqlite3_free(pInfo->idxStr); } sqlite3DbFree(db, pInfo); } if( pWInfo->a[i].plan.wsFlags & WHERE_TEMP_INDEX ){ sqlite3DbFree(db, pWInfo->a[i].plan.u.pIdx); } } whereClauseClear(pWInfo->pWC); sqlite3DbFree(db, pWInfo); } } |
︙ | ︙ | |||
3613 3614 3615 3616 3617 3618 3619 3620 3621 3622 3623 3624 3625 3626 3627 3628 3629 3630 3631 3632 3633 3634 | nByteWInfo = ROUND8(sizeof(WhereInfo)+(nTabList-1)*sizeof(WhereLevel)); pWInfo = sqlite3DbMallocZero(db, nByteWInfo + sizeof(WhereClause) + sizeof(WhereMaskSet) ); if( db->mallocFailed ){ goto whereBeginError; } pWInfo->nLevel = nTabList; pWInfo->pParse = pParse; pWInfo->pTabList = pTabList; pWInfo->iBreak = sqlite3VdbeMakeLabel(v); pWInfo->pWC = pWC = (WhereClause *)&((u8 *)pWInfo)[nByteWInfo]; pWInfo->wctrlFlags = wctrlFlags; pMaskSet = (WhereMaskSet*)&pWC[1]; /* Split the WHERE clause into separate subexpressions where each ** subexpression is separated by an AND operator. */ initMaskSet(pMaskSet); whereClauseInit(pWC, pParse, pMaskSet); | > > > | 3772 3773 3774 3775 3776 3777 3778 3779 3780 3781 3782 3783 3784 3785 3786 3787 3788 3789 3790 3791 3792 3793 3794 3795 3796 | nByteWInfo = ROUND8(sizeof(WhereInfo)+(nTabList-1)*sizeof(WhereLevel)); pWInfo = sqlite3DbMallocZero(db, nByteWInfo + sizeof(WhereClause) + sizeof(WhereMaskSet) ); if( db->mallocFailed ){ sqlite3DbFree(db, pWInfo); pWInfo = 0; goto whereBeginError; } pWInfo->nLevel = nTabList; pWInfo->pParse = pParse; pWInfo->pTabList = pTabList; pWInfo->iBreak = sqlite3VdbeMakeLabel(v); pWInfo->pWC = pWC = (WhereClause *)&((u8 *)pWInfo)[nByteWInfo]; pWInfo->wctrlFlags = wctrlFlags; pWInfo->savedNQueryLoop = pParse->nQueryLoop; pMaskSet = (WhereMaskSet*)&pWC[1]; /* Split the WHERE clause into separate subexpressions where each ** subexpression is separated by an AND operator. */ initMaskSet(pMaskSet); whereClauseInit(pWC, pParse, pMaskSet); |
︙ | ︙ | |||
3800 3801 3802 3803 3804 3805 3806 | WHERETRACE(("*** Optimizer selects table %d for loop %d\n", bestJ, pLevel-pWInfo->a)); if( (bestPlan.plan.wsFlags & WHERE_ORDERBY)!=0 ){ *ppOrderBy = 0; } andFlags &= bestPlan.plan.wsFlags; pLevel->plan = bestPlan.plan; | | > > > | 3962 3963 3964 3965 3966 3967 3968 3969 3970 3971 3972 3973 3974 3975 3976 3977 3978 3979 3980 3981 3982 3983 3984 3985 | WHERETRACE(("*** Optimizer selects table %d for loop %d\n", bestJ, pLevel-pWInfo->a)); if( (bestPlan.plan.wsFlags & WHERE_ORDERBY)!=0 ){ *ppOrderBy = 0; } andFlags &= bestPlan.plan.wsFlags; pLevel->plan = bestPlan.plan; testcase( bestPlan.plan.wsFlags & WHERE_INDEXED ); testcase( bestPlan.plan.wsFlags & WHERE_TEMP_INDEX ); if( bestPlan.plan.wsFlags & (WHERE_INDEXED|WHERE_TEMP_INDEX) ){ pLevel->iIdxCur = pParse->nTab++; }else{ pLevel->iIdxCur = -1; } notReady &= ~getMask(pMaskSet, pTabList->a[bestJ].iCursor); pLevel->iFrom = (u8)bestJ; if( bestPlan.nRow>=(double)1 ) pParse->nQueryLoop *= bestPlan.nRow; /* Check that if the table scanned by this loop iteration had an ** INDEXED BY clause attached to it, that the named index is being ** used for the scan. If not, then query compilation has failed. ** Return an error. */ pIdx = pTabList->a[bestJ].pIndex; |
︙ | ︙ | |||
3853 3854 3855 3856 3857 3858 3859 3860 3861 3862 3863 3864 3865 3866 3867 3868 3869 3870 3871 | pWInfo->a[0].plan.wsFlags &= ~WHERE_IDX_ONLY; } /* Open all tables in the pTabList and any indices selected for ** searching those tables. */ sqlite3CodeVerifySchema(pParse, -1); /* Insert the cookie verifier Goto */ for(i=0, pLevel=pWInfo->a; i<nTabList; i++, pLevel++){ Table *pTab; /* Table to open */ int iDb; /* Index of database containing table/index */ #ifndef SQLITE_OMIT_EXPLAIN if( pParse->explain==2 ){ char *zMsg; struct SrcList_item *pItem = &pTabList->a[pLevel->iFrom]; zMsg = sqlite3MPrintf(db, "TABLE %s", pItem->zName); if( pItem->zAlias ){ zMsg = sqlite3MAppendf(db, zMsg, "%s AS %s", zMsg, pItem->zAlias); } | > | > > | 4018 4019 4020 4021 4022 4023 4024 4025 4026 4027 4028 4029 4030 4031 4032 4033 4034 4035 4036 4037 4038 4039 4040 4041 4042 4043 4044 4045 4046 4047 | pWInfo->a[0].plan.wsFlags &= ~WHERE_IDX_ONLY; } /* Open all tables in the pTabList and any indices selected for ** searching those tables. */ sqlite3CodeVerifySchema(pParse, -1); /* Insert the cookie verifier Goto */ notReady = ~(Bitmask)0; for(i=0, pLevel=pWInfo->a; i<nTabList; i++, pLevel++){ Table *pTab; /* Table to open */ int iDb; /* Index of database containing table/index */ #ifndef SQLITE_OMIT_EXPLAIN if( pParse->explain==2 ){ char *zMsg; struct SrcList_item *pItem = &pTabList->a[pLevel->iFrom]; zMsg = sqlite3MPrintf(db, "TABLE %s", pItem->zName); if( pItem->zAlias ){ zMsg = sqlite3MAppendf(db, zMsg, "%s AS %s", zMsg, pItem->zAlias); } if( (pLevel->plan.wsFlags & WHERE_TEMP_INDEX)!=0 ){ zMsg = sqlite3MAppendf(db, zMsg, "%s WITH AUTOMATIC INDEX", zMsg); }else if( (pLevel->plan.wsFlags & WHERE_INDEXED)!=0 ){ zMsg = sqlite3MAppendf(db, zMsg, "%s WITH INDEX %s", zMsg, pLevel->plan.u.pIdx->zName); }else if( pLevel->plan.wsFlags & WHERE_MULTI_OR ){ zMsg = sqlite3MAppendf(db, zMsg, "%s VIA MULTI-INDEX UNION", zMsg); }else if( pLevel->plan.wsFlags & (WHERE_ROWID_EQ|WHERE_ROWID_RANGE) ){ zMsg = sqlite3MAppendf(db, zMsg, "%s USING PRIMARY KEY", zMsg); } |
︙ | ︙ | |||
3913 3914 3915 3916 3917 3918 3919 | SQLITE_INT_TO_PTR(n), P4_INT32); assert( n<=pTab->nCol ); } }else{ sqlite3TableLock(pParse, iDb, pTab->tnum, 0, pTab->zName); } pLevel->iTabCur = pTabItem->iCursor; | | > > > | 4081 4082 4083 4084 4085 4086 4087 4088 4089 4090 4091 4092 4093 4094 4095 4096 4097 4098 4099 4100 4101 4102 4103 4104 4105 4106 4107 4108 | SQLITE_INT_TO_PTR(n), P4_INT32); assert( n<=pTab->nCol ); } }else{ sqlite3TableLock(pParse, iDb, pTab->tnum, 0, pTab->zName); } pLevel->iTabCur = pTabItem->iCursor; if( (pLevel->plan.wsFlags & WHERE_TEMP_INDEX)!=0 ){ constructTransientIndex(pParse, pWC, pTabItem, notReady, pLevel); }else if( (pLevel->plan.wsFlags & WHERE_INDEXED)!=0 ){ Index *pIx = pLevel->plan.u.pIdx; KeyInfo *pKey = sqlite3IndexKeyinfo(pParse, pIx); int iIdxCur = pLevel->iIdxCur; assert( pIx->pSchema==pTab->pSchema ); assert( iIdxCur>=0 ); sqlite3VdbeAddOp4(v, OP_OpenRead, iIdxCur, pIx->tnum, iDb, (char*)pKey, P4_KEYINFO_HANDOFF); VdbeComment((v, "%s", pIx->zName)); } sqlite3CodeVerifySchema(pParse, iDb); notReady &= ~getMask(pWC->pMaskSet, pTabItem->iCursor); } pWInfo->iTop = sqlite3VdbeCurrentAddr(v); /* Generate the code to do the search. Each iteration of the for ** loop below generates code for a single nested loop of the VM ** program. */ |
︙ | ︙ | |||
3993 3994 3995 3996 3997 3998 3999 | /* Record the continuation address in the WhereInfo structure. Then ** clean up and return. */ return pWInfo; /* Jump here if malloc fails */ whereBeginError: | > > | > | 4164 4165 4166 4167 4168 4169 4170 4171 4172 4173 4174 4175 4176 4177 4178 4179 4180 4181 | /* Record the continuation address in the WhereInfo structure. Then ** clean up and return. */ return pWInfo; /* Jump here if malloc fails */ whereBeginError: if( pWInfo ){ pParse->nQueryLoop = pWInfo->savedNQueryLoop; whereInfoFree(db, pWInfo); } return 0; } /* ** Generate the end of the WHERE loop. See comments on ** sqlite3WhereBegin() for additional information. */ |
︙ | ︙ | |||
4065 4066 4067 4068 4069 4070 4071 | assert( pWInfo->nLevel==1 || pWInfo->nLevel==pTabList->nSrc ); for(i=0, pLevel=pWInfo->a; i<pWInfo->nLevel; i++, pLevel++){ struct SrcList_item *pTabItem = &pTabList->a[pLevel->iFrom]; Table *pTab = pTabItem->pTab; assert( pTab!=0 ); if( (pTab->tabFlags & TF_Ephemeral)!=0 || pTab->pSelect ) continue; if( (pWInfo->wctrlFlags & WHERE_OMIT_CLOSE)==0 ){ | > | | | 4239 4240 4241 4242 4243 4244 4245 4246 4247 4248 4249 4250 4251 4252 4253 4254 4255 4256 4257 | assert( pWInfo->nLevel==1 || pWInfo->nLevel==pTabList->nSrc ); for(i=0, pLevel=pWInfo->a; i<pWInfo->nLevel; i++, pLevel++){ struct SrcList_item *pTabItem = &pTabList->a[pLevel->iFrom]; Table *pTab = pTabItem->pTab; assert( pTab!=0 ); if( (pTab->tabFlags & TF_Ephemeral)!=0 || pTab->pSelect ) continue; if( (pWInfo->wctrlFlags & WHERE_OMIT_CLOSE)==0 ){ int ws = pLevel->plan.wsFlags; if( !pWInfo->okOnePass && (ws & WHERE_IDX_ONLY)==0 ){ sqlite3VdbeAddOp1(v, OP_Close, pTabItem->iCursor); } if( (ws & (WHERE_INDEXED|WHERE_TEMP_INDEX)) == WHERE_INDEXED ){ sqlite3VdbeAddOp1(v, OP_Close, pLevel->iIdxCur); } } /* If this scan uses an index, make code substitutions to read data ** from the index in preference to the table. Sometimes, this means ** the table need never be read from. This is a performance boost, |
︙ | ︙ | |||
4116 4117 4118 4119 4120 4121 4122 | } } } } /* Final cleanup */ | > > | > | 4291 4292 4293 4294 4295 4296 4297 4298 4299 4300 4301 4302 4303 | } } } } /* Final cleanup */ if( pWInfo ){ pParse->nQueryLoop = pWInfo->savedNQueryLoop; whereInfoFree(db, pWInfo); } return; } |