Many hyperlinks are disabled.
Use anonymous login
to enable hyperlinks.
Overview
Comment: | Progress toward decending indices. (CVS 2839) |
---|---|
Downloads: | Tarball | ZIP archive |
Timelines: | family | ancestors | descendants | both | trunk |
Files: | files | file ages | folders |
SHA1: |
112a34b8dcceb39540cb0cd629e264a8 |
User & Date: | drh 2005-12-21 03:16:43.000 |
Context
2005-12-21
| ||
14:43 | Basic functionality for descending indices is in place. Lots more testing needed. (CVS 2840) (check-in: 7064433e5b user: drh tags: trunk) | |
03:16 | Progress toward decending indices. (CVS 2839) (check-in: 112a34b8dc user: drh tags: trunk) | |
2005-12-20
| ||
14:38 | Include sqlite3_release_memory() code when SQLITE_MEMDEBUG is not defined. (CVS 2838) (check-in: 77a37ceca7 user: danielk1977 tags: trunk) | |
Changes
Changes to src/build.c.
︙ | ︙ | |||
18 19 20 21 22 23 24 | ** CREATE INDEX ** DROP INDEX ** creating ID lists ** BEGIN TRANSACTION ** COMMIT ** ROLLBACK ** | | | 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 | ** CREATE INDEX ** DROP INDEX ** creating ID lists ** BEGIN TRANSACTION ** COMMIT ** ROLLBACK ** ** $Id: build.c,v 1.359 2005/12/21 03:16:43 drh Exp $ */ #include "sqliteInt.h" #include <ctype.h> /* ** This routine is called when a new SQL statement is beginning to ** be parsed. Initialize the pParse structure as needed. |
︙ | ︙ | |||
2109 2110 2111 2112 2113 2114 2115 | int sortOrderMask; /* 1 to honor DESC in index. 0 to ignore. */ int descSeen = 0; /* Changes to true if a DESC is seen */ sqlite3 *db = pParse->db; Db *pDb; /* The specific table containing the indexed database */ int iDb; /* Index of the database that is being written */ Token *pName = 0; /* Unqualified name of the index to create */ struct ExprList_item *pListItem; /* For looping over pList */ | < | 2109 2110 2111 2112 2113 2114 2115 2116 2117 2118 2119 2120 2121 2122 | int sortOrderMask; /* 1 to honor DESC in index. 0 to ignore. */ int descSeen = 0; /* Changes to true if a DESC is seen */ sqlite3 *db = pParse->db; Db *pDb; /* The specific table containing the indexed database */ int iDb; /* Index of the database that is being written */ Token *pName = 0; /* Unqualified name of the index to create */ struct ExprList_item *pListItem; /* For looping over pList */ if( pParse->nErr || sqlite3Tsd()->mallocFailed ) goto exit_create_index; /* ** Find the table that is to be indexed. Return early if not found. */ if( pTblName!=0 ){ |
︙ | ︙ | |||
2273 2274 2275 2276 2277 2278 2279 | /* Scan the names of the columns of the table to be indexed and ** load the column indices into the Index structure. Report an error ** if any column is not found. */ for(i=0, pListItem=pList->a; i<pList->nExpr; i++, pListItem++){ const char *zColName = pListItem->zName; Column *pTabCol; | | | 2272 2273 2274 2275 2276 2277 2278 2279 2280 2281 2282 2283 2284 2285 2286 | /* Scan the names of the columns of the table to be indexed and ** load the column indices into the Index structure. Report an error ** if any column is not found. */ for(i=0, pListItem=pList->a; i<pList->nExpr; i++, pListItem++){ const char *zColName = pListItem->zName; Column *pTabCol; int requestedSortOrder; for(j=0, pTabCol=pTab->aCol; j<pTab->nCol; j++, pTabCol++){ if( sqlite3StrICmp(zColName, pTabCol->zName)==0 ) break; } if( j>=pTab->nCol ){ sqlite3ErrorMsg(pParse, "table %s has no column named %s", pTab->zName, zColName); goto exit_create_index; |
︙ | ︙ | |||
2295 2296 2297 2298 2299 2300 2301 | } assert( pIndex->keyInfo.aColl[i] ); if( !db->init.busy && sqlite3CheckCollSeq(pParse, pIndex->keyInfo.aColl[i]) ){ goto exit_create_index; } | | | | | | | 2294 2295 2296 2297 2298 2299 2300 2301 2302 2303 2304 2305 2306 2307 2308 2309 2310 2311 2312 | } assert( pIndex->keyInfo.aColl[i] ); if( !db->init.busy && sqlite3CheckCollSeq(pParse, pIndex->keyInfo.aColl[i]) ){ goto exit_create_index; } requestedSortOrder = pListItem->sortOrder; pDb->descIndex |= requestedSortOrder; requestedSortOrder &= sortOrderMask; pIndex->keyInfo.aSortOrder[i] = requestedSortOrder; descSeen |= requestedSortOrder; } pIndex->keyInfo.nField = pList->nExpr; sqlite3DefaultRowEst(pIndex); if( pTab==pParse->pNewTable ){ /* This routine has been called to create an automatic index as a ** result of a PRIMARY KEY or UNIQUE clause on a column definition, or |
︙ | ︙ |
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 reponsible 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 reponsible 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.188 2005/12/21 03:16:43 drh Exp $ */ #include "sqliteInt.h" /* ** The number of bits in a Bitmask. "BMS" means "BitMask Size". */ #define BMS (sizeof(Bitmask)*8) |
︙ | ︙ | |||
781 782 783 784 785 786 787 | Table *pTab, /* The table to be sorted */ int base, /* Cursor number for pTab */ ExprList *pOrderBy, /* The ORDER BY clause */ int nEqCol, /* Number of index columns with == constraints */ int *pbRev /* Set to 1 if ORDER BY is DESC */ ){ int i, j; /* Loop counters */ | | > | 781 782 783 784 785 786 787 788 789 790 791 792 793 794 795 796 797 798 799 800 801 802 803 804 805 806 807 808 809 810 | Table *pTab, /* The table to be sorted */ int base, /* Cursor number for pTab */ ExprList *pOrderBy, /* The ORDER BY clause */ int nEqCol, /* Number of index columns with == constraints */ int *pbRev /* Set to 1 if ORDER BY is DESC */ ){ int i, j; /* Loop counters */ int sortOrder = 0; /* XOR of index and ORDER BY sort direction */ int nTerm; /* Number of ORDER BY terms */ struct ExprList_item *pTerm; /* A term of the ORDER BY clause */ sqlite3 *db = pParse->db; assert( pOrderBy!=0 ); nTerm = pOrderBy->nExpr; assert( nTerm>0 ); /* Match terms of the ORDER BY clause against columns of ** the index. */ for(i=j=0, pTerm=pOrderBy->a; j<nTerm && i<pIdx->nColumn; i++){ Expr *pExpr; /* The expression of the ORDER BY pTerm */ CollSeq *pColl; /* The collating sequence of pExpr */ int termSortOrder; /* Sort order for this term */ pExpr = pTerm->pExpr; if( pExpr->op!=TK_COLUMN || pExpr->iTable!=base ){ /* Can not use an index sort on anything that is not a column in the ** left-most table of the FROM clause */ return 0; } |
︙ | ︙ | |||
819 820 821 822 823 824 825 826 | }else{ /* If an index column fails to match and is not constrained by == ** then the index cannot satisfy the ORDER BY constraint. */ return 0; } } if( i>nEqCol ){ | > > > > | | | | 820 821 822 823 824 825 826 827 828 829 830 831 832 833 834 835 836 837 838 839 840 841 842 843 844 845 846 847 848 849 850 851 852 853 854 855 | }else{ /* If an index column fails to match and is not constrained by == ** then the index cannot satisfy the ORDER BY constraint. */ return 0; } } assert( pIdx->keyInfo.aSortOrder!=0 ); assert( pTerm->sortOrder==0 || pTerm->sortOrder==1 ); assert( pIdx->keyInfo.aSortOrder[i]==0 || pIdx->keyInfo.aSortOrder[i]==1 ); termSortOrder = pIdx->keyInfo.aSortOrder[i] ^ pTerm->sortOrder; if( i>nEqCol ){ if( termSortOrder!=sortOrder ){ /* Indices can only be used if all ORDER BY terms past the ** equality constraints are all either DESC or ASC. */ return 0; } }else{ sortOrder = termSortOrder; } j++; pTerm++; } /* The index can be used for sorting if all terms of the ORDER BY clause ** are covered. */ if( j>=nTerm ){ *pbRev = sortOrder!=0; return 1; } return 0; } /* ** Check table to see if the ORDER BY clause in pOrderBy can be satisfied |
︙ | ︙ | |||
1706 1707 1708 1709 1710 1711 1712 | ** ** This case is also used when there are no WHERE clause ** constraints but an index is selected anyway, in order ** to force the output order to conform to an ORDER BY. */ int start; int nEq = pLevel->nEq; | | > > > > > > > > > > > > > > > > | | | | | | | | | | 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 1799 1800 1801 1802 1803 1804 1805 1806 1807 1808 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 | ** ** This case is also used when there are no WHERE clause ** constraints but an index is selected anyway, in order ** to force the output order to conform to an ORDER BY. */ int start; int nEq = pLevel->nEq; int topEq=0; /* True if top limit uses ==. False is strictly < */ int btmEq=0; /* True if btm limit uses ==. False if strictly > */ int topOp, btmOp; /* Operators for the top and bottom search bounds */ int testOp; int topLimit = (pLevel->flags & WHERE_TOP_LIMIT)!=0; int btmLimit = (pLevel->flags & WHERE_BTM_LIMIT)!=0; /* Generate code to evaluate all constraint terms using == or IN ** and level the values of those terms on the stack. */ codeAllEqualityTerms(pParse, pLevel, &wc, notReady, brk); /* Duplicate the equality term values because they will all be ** used twice: once to make the termination key and once to make the ** start key. */ for(j=0; j<nEq; j++){ sqlite3VdbeAddOp(v, OP_Dup, nEq-1, 0); } /* Figure out what comparison operators to use for top and bottom ** search bounds. For an ascending index, the bottom bound is a > or >= ** operator and the top bound is a < or <= operator. For a descending ** index the operators are reversed. */ if( pIdx->keyInfo.aSortOrder[nEq]==SQLITE_SO_ASC ){ topOp = WO_LT|WO_LE; btmOp = WO_GT|WO_GE; }else{ topOp = WO_GT|WO_GE; btmOp = WO_LT|WO_LE; SWAP(int, topLimit, btmLimit); } /* Generate the termination key. This is the key value that ** will end the search. There is no termination key if there ** are no equality terms and no "X<..." term. ** ** 2002-Dec-04: On a reverse-order scan, the so-called "termination" ** key computed here really ends up being the start key. */ if( topLimit ){ Expr *pX; int k = pIdx->aiColumn[j]; pTerm = findTerm(&wc, iCur, k, notReady, topOp, pIdx); assert( pTerm!=0 ); pX = pTerm->pExpr; assert( (pTerm->flags & TERM_CODED)==0 ); sqlite3ExprCode(pParse, pX->pRight); topEq = pTerm->operator & (WO_LE|WO_GE); disableTerm(pLevel, pTerm); testOp = OP_IdxGE; }else{ testOp = nEq>0 ? OP_IdxGE : OP_Noop; topEq = 1; } if( testOp!=OP_Noop ){ int nCol = nEq + topLimit; pLevel->iMem = pParse->nMem++; buildIndexProbe(v, nCol, brk, pIdx); if( bRev ){ int op = topEq ? OP_MoveLe : OP_MoveLt; sqlite3VdbeAddOp(v, op, iIdxCur, brk); }else{ sqlite3VdbeAddOp(v, OP_MemStore, pLevel->iMem, 1); } }else if( bRev ){ sqlite3VdbeAddOp(v, OP_Last, iIdxCur, brk); } /* Generate the start key. This is the key that defines the lower ** bound on the search. There is no start key if there are no ** equality terms and if there is no "X>..." term. In ** that case, generate a "Rewind" instruction in place of the ** start key search. ** ** 2002-Dec-04: In the case of a reverse-order search, the so-called ** "start" key really ends up being used as the termination key. */ if( btmLimit ){ Expr *pX; int k = pIdx->aiColumn[j]; pTerm = findTerm(&wc, iCur, k, notReady, btmOp, pIdx); assert( pTerm!=0 ); pX = pTerm->pExpr; assert( (pTerm->flags & TERM_CODED)==0 ); sqlite3ExprCode(pParse, pX->pRight); btmEq = pTerm->operator & (WO_LE|WO_GE); disableTerm(pLevel, pTerm); }else{ btmEq = 1; } if( nEq>0 || btmLimit ){ int nCol = nEq + btmLimit; buildIndexProbe(v, nCol, brk, pIdx); if( bRev ){ pLevel->iMem = pParse->nMem++; sqlite3VdbeAddOp(v, OP_MemStore, pLevel->iMem, 1); testOp = OP_IdxLT; }else{ int op = btmEq ? OP_MoveGe : OP_MoveGt; sqlite3VdbeAddOp(v, op, iIdxCur, brk); } }else if( bRev ){ testOp = OP_Noop; }else{ sqlite3VdbeAddOp(v, OP_Rewind, iIdxCur, brk); } /* Generate the the top of the loop. If there is a termination ** key we have to test for that key and abort at the top of the ** loop. */ start = sqlite3VdbeCurrentAddr(v); if( testOp!=OP_Noop ){ sqlite3VdbeAddOp(v, OP_MemLoad, pLevel->iMem, 0); sqlite3VdbeAddOp(v, testOp, iIdxCur, brk); if( (topEq && !bRev) || (!btmEq && bRev) ){ sqlite3VdbeChangeP3(v, -1, "+", P3_STATIC); } } sqlite3VdbeAddOp(v, OP_RowKey, iIdxCur, 0); sqlite3VdbeAddOp(v, OP_IdxIsNull, nEq + topLimit, cont); if( !omitTable ){ sqlite3VdbeAddOp(v, OP_IdxRowid, iIdxCur, 0); |
︙ | ︙ |