Many hyperlinks are disabled.
Use anonymous login
to enable hyperlinks.
Overview
Comment: | Progress toward getting automatic indices to work. Still failing in corner cases. |
---|---|
Downloads: | Tarball | ZIP archive |
Timelines: | family | ancestors | descendants | both | experimental |
Files: | files | file ages | folders |
SHA1: |
ac6d0fba78eb9dcd69372e128d4a039a |
User & Date: | drh 2010-04-06 18:28:21.000 |
Context
2010-04-06
| ||
18:51 | Runs quicktest without hitting an assert now. Some tests get unexpected results still and there is a memory leak. (check-in: a8224448cc user: drh tags: experimental) | |
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) | |
Changes
Changes to src/where.c.
︙ | ︙ | |||
1653 1654 1655 1656 1657 1658 1659 1660 1661 1662 1663 1664 1665 1666 | 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. */ | > | 1653 1654 1655 1656 1657 1658 1659 1660 1661 1662 1663 1664 1665 1666 1667 | 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[] */ Table *pTable; /* Table tht might be indexed */ 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. */ |
︙ | ︙ | |||
1674 1675 1676 1677 1678 1679 1680 1681 1682 1683 1684 1685 1686 1687 1688 1689 1690 1691 1692 | 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; | > > > | 1675 1676 1677 1678 1679 1680 1681 1682 1683 1684 1685 1686 1687 1688 1689 1690 1691 1692 1693 1694 1695 1696 | 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 */ pTable = pSrc->pTab; 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 && sqlite3IndexAffinityOk(pTerm->pExpr, pTable->aCol[pTerm->u.leftColumn].affinity) ){ 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; |
︙ | ︙ | |||
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 | 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; | > > > > > > | > > > > > | < > | 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 1799 | 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 */ CollSeq *pColl; /* Collating sequence to on a column */ /* 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; pTable = pSrc->pTab; 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 && sqlite3IndexAffinityOk(pTerm->pExpr, pTable->aCol[pTerm->u.leftColumn].affinity) ){ nColumn++; } } assert( nColumn>0 ); pLevel->plan.nEq = nColumn; pLevel->plan.wsFlags = WHERE_COLUMN_EQ | WO_EQ; /* 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; n = 0; for(pTerm=pWC->a; pTerm<pWCEnd; pTerm++){ if( pTerm->leftCursor==pSrc->iCursor && (pTerm->prereqRight & notReady)==0 && (pTerm->eOperator & WO_EQ)!=0 && sqlite3IndexAffinityOk(pTerm->pExpr, pTable->aCol[pTerm->u.leftColumn].affinity) ){ int iCol = pTerm->u.leftColumn; Expr *pX; pIdx->aiColumn[n] = iCol; pX = pTerm->pExpr; pColl = sqlite3BinaryCompareCollSeq(pParse, pX->pLeft, pX->pRight); pIdx->azColl[n] = pColl->zName; 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); VdbeComment((v, "auto-idx for %s", pTable->zName)); /* 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); |
︙ | ︙ | |||
4056 4057 4058 4059 4060 4061 4062 4063 | zMsg = sqlite3MAppendf(db, zMsg, "%s ORDER BY", zMsg); } sqlite3VdbeAddOp4(v, OP_Explain, i, pLevel->iFrom, 0, zMsg, P4_DYNAMIC); } #endif /* SQLITE_OMIT_EXPLAIN */ pTabItem = &pTabList->a[pLevel->iFrom]; pTab = pTabItem->pTab; iDb = sqlite3SchemaToIndex(db, pTab->pSchema); | > | > > > > > | 4071 4072 4073 4074 4075 4076 4077 4078 4079 4080 4081 4082 4083 4084 4085 4086 4087 4088 4089 4090 4091 4092 | zMsg = sqlite3MAppendf(db, zMsg, "%s ORDER BY", zMsg); } sqlite3VdbeAddOp4(v, OP_Explain, i, pLevel->iFrom, 0, zMsg, P4_DYNAMIC); } #endif /* SQLITE_OMIT_EXPLAIN */ pTabItem = &pTabList->a[pLevel->iFrom]; pTab = pTabItem->pTab; pLevel->iTabCur = pTabItem->iCursor; iDb = sqlite3SchemaToIndex(db, pTab->pSchema); if( (pTab->tabFlags & TF_Ephemeral)!=0 || pTab->pSelect ){ if( pLevel->plan.wsFlags & WHERE_TEMP_INDEX ){ constructTransientIndex(pParse, pWC, pTabItem, notReady, pLevel); } continue; } #ifndef SQLITE_OMIT_VIRTUALTABLE if( (pLevel->plan.wsFlags & WHERE_VIRTUALTABLE)!=0 ){ const char *pVTab = (const char *)sqlite3GetVTable(db, pTab); int iCur = pTabItem->iCursor; sqlite3VdbeAddOp4(v, OP_VOpen, iCur, 0, 0, pVTab, P4_VTAB); }else #endif |
︙ | ︙ | |||
4080 4081 4082 4083 4084 4085 4086 | sqlite3VdbeChangeP4(v, sqlite3VdbeCurrentAddr(v)-1, SQLITE_INT_TO_PTR(n), P4_INT32); assert( n<=pTab->nCol ); } }else{ sqlite3TableLock(pParse, iDb, pTab->tnum, 0, pTab->zName); } | < | 4101 4102 4103 4104 4105 4106 4107 4108 4109 4110 4111 4112 4113 4114 | sqlite3VdbeChangeP4(v, sqlite3VdbeCurrentAddr(v)-1, SQLITE_INT_TO_PTR(n), P4_INT32); assert( n<=pTab->nCol ); } }else{ sqlite3TableLock(pParse, iDb, pTab->tnum, 0, pTab->zName); } 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 ); |
︙ | ︙ |