Many hyperlinks are disabled.
Use anonymous login
to enable hyperlinks.
Overview
Comment: | Begin adding code to support multiple IN constraints on the same index. (CVS 2557) |
---|---|
Downloads: | Tarball | ZIP archive |
Timelines: | family | ancestors | descendants | both | trunk |
Files: | files | file ages | folders |
SHA1: |
103f8ccb9013689a480766ebffbf570d |
User & Date: | drh 2005-07-22 00:31:40.000 |
Context
2005-07-22
| ||
22:53 | Correct the documentation to show that sqlite3_column_text() returns a NULL pointer (not an empty string) when the column value is NULL. The same goes for sqlite3_column_blob(). Ticket #1334. (CVS 2558) (check-in: fd1e013a14 user: drh tags: trunk) | |
00:31 | Begin adding code to support multiple IN constraints on the same index. (CVS 2557) (check-in: 103f8ccb90 user: drh tags: trunk) | |
2005-07-21
| ||
18:23 | Split the OP_Integer opcode into OP_Integer and OP_Int64. This allows comments to be added to OP_Integer. Cleanup in the optimizer. Allow terms of the FROM clause to be reordered automatically. (CVS 2556) (check-in: e2f822ac82 user: drh 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.397 2005/07/22 00:31:40 drh Exp $ */ #ifndef _SQLITEINT_H_ #define _SQLITEINT_H_ /* ** These #defines should enable >2GB file support on Posix if the ** underlying operating system supports it. If the OS lacks |
︙ | ︙ | |||
956 957 958 959 960 961 962 | Index *pIdx; /* Index used. NULL if no index */ int iTabCur; /* The VDBE cursor used to access the table */ int iIdxCur; /* The VDBE cursor used to acesss pIdx */ int brk; /* Jump here to break out of the loop */ int cont; /* Jump here to continue with the next loop cycle */ int top; /* First instruction of interior of the loop */ int op, p1, p2; /* Opcode used to terminate the loop */ | > | | 956 957 958 959 960 961 962 963 964 965 966 967 968 969 970 971 | Index *pIdx; /* Index used. NULL if no index */ int iTabCur; /* The VDBE cursor used to access the table */ int iIdxCur; /* The VDBE cursor used to acesss pIdx */ int brk; /* Jump here to break out of the loop */ int cont; /* Jump here to continue with the next loop cycle */ int top; /* First instruction of interior of the loop */ int op, p1, p2; /* Opcode used to terminate the loop */ int nIn; /* Number of IN operators constraining this loop */ int *aInLoop; /* Loop terminators for IN operators */ }; /* ** The WHERE clause processing routine has two halves. The ** first part does the start of the WHERE loop and the second ** half does the tail of the WHERE loop. An instance of ** this structure is returned by the first half and passed |
︙ | ︙ |
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.151 2005/07/22 00:31:40 drh Exp $ */ #include "sqliteInt.h" /* ** The number of bits in a Bitmask. "BMS" means "BitMask Size". */ #define BMS (sizeof(Bitmask)*8) |
︙ | ︙ | |||
92 93 94 95 96 97 98 99 100 101 102 103 104 105 | struct WhereClause { Parse *pParse; /* The parser context */ int nTerm; /* Number of terms */ int nSlot; /* Number of entries in a[] */ WhereTerm *a; /* Pointer to an array of terms */ WhereTerm aStatic[10]; /* Initial static space for the terms */ }; /* ** An instance of the following structure keeps track of a mapping ** between VDBE cursor numbers and bits of the bitmasks in WhereTerm. ** ** The VDBE cursor numbers are small integers contained in ** SrcList_item.iCursor and Expr.iTable fields. For any given WHERE | > > > > > > > > > > > > > > > > > > > > > > > > > > > > > | 92 93 94 95 96 97 98 99 100 101 102 103 104 105 106 107 108 109 110 111 112 113 114 115 116 117 118 119 120 121 122 123 124 125 126 127 128 129 130 131 132 133 134 | struct WhereClause { Parse *pParse; /* The parser context */ int nTerm; /* Number of terms */ int nSlot; /* Number of entries in a[] */ WhereTerm *a; /* Pointer to an array of terms */ WhereTerm aStatic[10]; /* Initial static space for the terms */ }; /* ** When WhereTerms are used to select elements from an index, we ** call those terms "constraints". For example, consider the following ** SQL: ** ** CREATE TABLE t1(a INTEGER PRIMARY KEY, b, c, d); ** CREATE INDEX t1i1 ON t1(b,c); ** ** SELECT * FROM t1 WHERE d=5 AND b=7 AND c>11; ** ** In the SELECT statement, the "b=7" and "c>11" terms are constraints ** because they can be used to choose rows out of the t1i1 index. But ** the "d=5" term is not a constraint because it is not indexed. ** ** When generating code to access an index, we have to keep track of ** all of the constraints associated with that index. This is done ** using an array of instanaces of the following structure. There is ** one instance of this structure for each constraint on the index. ** ** Actually, we allocate the array of this structure based on the total ** number of terms in the entire WHERE clause (because the number of ** constraints can never be more than that) and reuse it when coding ** each index. */ typedef struct WhereConstraint WhereConstraint; struct WhereConstraint { int iMem; /* Mem cell used to hold <expr> part of constraint */ }; /* ** An instance of the following structure keeps track of a mapping ** between VDBE cursor numbers and bits of the bitmasks in WhereTerm. ** ** The VDBE cursor numbers are small integers contained in ** SrcList_item.iCursor and Expr.iTable fields. For any given WHERE |
︙ | ︙ | |||
238 239 240 241 242 243 244 | ** array will never overflow. */ static void createMask(ExprMaskSet *pMaskSet, int iCursor){ assert( pMaskSet->n < ARRAYSIZE(pMaskSet->ix) ); pMaskSet->ix[pMaskSet->n++] = iCursor; } | < < < < < | 267 268 269 270 271 272 273 274 275 276 277 278 279 280 | ** array will never overflow. */ static void createMask(ExprMaskSet *pMaskSet, int iCursor){ assert( pMaskSet->n < ARRAYSIZE(pMaskSet->ix) ); pMaskSet->ix[pMaskSet->n++] = iCursor; } /* ** This routine walks (recursively) an expression tree and generates ** a bitmask indicating which tables are used in that expression ** tree. ** ** In order for this routine to work, the calling function must have ** previously invoked sqlite3ExprResolveNames() on the expression. See |
︙ | ︙ | |||
572 573 574 575 576 577 578 | } return 0; } /* ** Value for flags returned by bestIndex() */ | | | | | | | | | | | > > | 596 597 598 599 600 601 602 603 604 605 606 607 608 609 610 611 612 613 614 615 616 617 618 619 620 621 | } return 0; } /* ** Value for flags returned by bestIndex() */ #define WHERE_ROWID_EQ 0x0001 /* rowid=EXPR or rowid IN (...) */ #define WHERE_ROWID_RANGE 0x0002 /* rowid<EXPR and/or rowid>EXPR */ #define WHERE_COLUMN_EQ 0x0004 /* x=EXPR or x IN (...) */ #define WHERE_COLUMN_RANGE 0x0008 /* x<EXPR and/or x>EXPR */ #define WHERE_SCAN 0x0010 /* Do a full table scan */ #define WHERE_REVERSE 0x0020 /* Scan in reverse order */ #define WHERE_ORDERBY 0x0040 /* Output will appear in correct order */ #define WHERE_IDX_ONLY 0x0080 /* Use index only - omit table */ #define WHERE_TOP_LIMIT 0x0100 /* x<EXPR or x<=EXPR constraint */ #define WHERE_BTM_LIMIT 0x0200 /* x>EXPR or x>=EXPR constraint */ #define WHERE_USES_IN 0x0400 /* True if the IN operator is used */ #define WHERE_UNIQUE 0x0800 /* True if fully specifies a unique idx */ /* ** Find the best index for accessing a particular table. Return the index, ** flags that describe how the index should be used, and the "score" for ** this index. */ static double bestIndex( |
︙ | ︙ | |||
615 616 617 618 619 620 621 | if( pTerm ){ *ppIndex = 0; if( pTerm->operator & WO_EQ ){ *pFlags = WHERE_ROWID_EQ; if( pOrderBy ) *pFlags |= WHERE_ORDERBY; return 1.0e10; }else{ | | | 641 642 643 644 645 646 647 648 649 650 651 652 653 654 655 | if( pTerm ){ *ppIndex = 0; if( pTerm->operator & WO_EQ ){ *pFlags = WHERE_ROWID_EQ; if( pOrderBy ) *pFlags |= WHERE_ORDERBY; return 1.0e10; }else{ *pFlags = WHERE_ROWID_EQ | WHERE_USES_IN; return 1.0e9; } } /* Check for constraints on a range of rowids */ pTerm = findTerm(pWC, iCur, -1, notReady, WO_LT|WO_LE|WO_GT|WO_GE, 0); |
︙ | ︙ | |||
671 672 673 674 675 676 677 | } } nEq = i + usesIN; score = i*100.0 + usesIN*50.0; /* The optimization type is RANGE if there are no == or IN constraints */ | | > > > > > > > > > > | 697 698 699 700 701 702 703 704 705 706 707 708 709 710 711 712 713 714 715 716 717 718 719 720 721 722 723 724 725 | } } nEq = i + usesIN; score = i*100.0 + usesIN*50.0; /* The optimization type is RANGE if there are no == or IN constraints */ if( usesIN ){ flags = WHERE_COLUMN_EQ | WHERE_USES_IN; }else if( nEq ){ flags = WHERE_COLUMN_EQ; }else{ flags = WHERE_COLUMN_RANGE; } /* Check for a uniquely specified row */ #if 0 if( nEq==pProbe->nColumn && pProbe->isUnique ){ flags |= WHERE_UNIQUE; } #endif /* Look for range constraints */ if( !usesIN && nEq<pProbe->nColumn ){ int j = pProbe->aiColumn[nEq]; pTerm = findTerm(pWC, iCur, j, notReady, WO_LT|WO_LE|WO_GT|WO_GE, pProbe); if( pTerm ){ |
︙ | ︙ | |||
815 816 817 818 819 820 821 | /* ** Generate code for an equality term of the WHERE clause. An equality ** term can be either X=expr or X IN (...). pTerm is the X. */ static void codeEqualityTerm( Parse *pParse, /* The parsing context */ | | > | > > > > | | > > | 851 852 853 854 855 856 857 858 859 860 861 862 863 864 865 866 867 868 869 870 871 872 873 874 875 876 877 878 879 880 881 882 883 884 885 886 887 888 889 890 891 | /* ** Generate code for an equality term of the WHERE clause. An equality ** term can be either X=expr or X IN (...). pTerm is the X. */ static void codeEqualityTerm( Parse *pParse, /* The parsing context */ WhereTerm *pTerm, /* The term of the WHERE clause to be coded */ int brk, /* Jump here to abandon the loop */ WhereLevel *pLevel /* When level of the FROM clause we are working on */ ){ Expr *pX = pTerm->pExpr; if( pX->op!=TK_IN ){ assert( pX->op==TK_EQ ); sqlite3ExprCode(pParse, pX->pRight); #ifndef SQLITE_OMIT_SUBQUERY }else{ int iTab; int *aIn; Vdbe *v = pParse->pVdbe; sqlite3CodeSubselect(pParse, pX); iTab = pX->iTable; sqlite3VdbeAddOp(v, OP_Rewind, iTab, brk); VdbeComment((v, "# %.*s", pX->span.n, pX->span.z)); pLevel->nIn++; pLevel->aInLoop = aIn = sqliteRealloc(pLevel->aInLoop, sizeof(pLevel->aInLoop[0])*3*pLevel->nIn); if( aIn ){ aIn += pLevel->nIn*3 - 3; aIn[0] = OP_Next; aIn[1] = iTab; aIn[2] = sqlite3VdbeAddOp(v, OP_Column, iTab, 0); } #endif } disableTerm(pLevel, pTerm); } #ifdef SQLITE_TEST /* |
︙ | ︙ | |||
957 958 959 960 961 962 963 964 965 966 967 968 969 970 | Bitmask notReady; /* Cursors that are not yet positioned */ WhereTerm *pTerm; /* A single term in the WHERE clause */ ExprMaskSet maskSet; /* The expression mask set */ WhereClause wc; /* The WHERE clause is divided into these terms */ struct SrcList_item *pTabItem; /* A single entry from pTabList */ WhereLevel *pLevel; /* A single level in the pWInfo list */ int iFrom; /* First unused FROM clause element */ /* The number of tables in the FROM clause is limited by the number of ** bits in a Bitmask */ if( pTabList->nSrc>BMS ){ sqlite3ErrorMsg(pParse, "at most %d tables in a join", BMS); return 0; | > | 1000 1001 1002 1003 1004 1005 1006 1007 1008 1009 1010 1011 1012 1013 1014 | Bitmask notReady; /* Cursors that are not yet positioned */ WhereTerm *pTerm; /* A single term in the WHERE clause */ ExprMaskSet maskSet; /* The expression mask set */ WhereClause wc; /* The WHERE clause is divided into these terms */ struct SrcList_item *pTabItem; /* A single entry from pTabList */ WhereLevel *pLevel; /* A single level in the pWInfo list */ int iFrom; /* First unused FROM clause element */ WhereConstraint *aConstraint; /* Information on constraints */ /* The number of tables in the FROM clause is limited by the number of ** bits in a Bitmask */ if( pTabList->nSrc>BMS ){ sqlite3ErrorMsg(pParse, "at most %d tables in a join", BMS); return 0; |
︙ | ︙ | |||
978 979 980 981 982 983 984 | whereSplit(&wc, pWhere); /* Allocate and initialize the WhereInfo structure that will become the ** return value. */ pWInfo = sqliteMalloc( sizeof(WhereInfo) + pTabList->nSrc*sizeof(WhereLevel)); if( sqlite3_malloc_failed ){ | < | < | 1022 1023 1024 1025 1026 1027 1028 1029 1030 1031 1032 1033 1034 1035 1036 | whereSplit(&wc, pWhere); /* Allocate and initialize the WhereInfo structure that will become the ** return value. */ pWInfo = sqliteMalloc( sizeof(WhereInfo) + pTabList->nSrc*sizeof(WhereLevel)); if( sqlite3_malloc_failed ){ goto whereBeginNoMem; } pWInfo->pParse = pParse; pWInfo->pTabList = pTabList; pWInfo->iBreak = sqlite3VdbeMakeLabel(v); /* Special case: a WHERE clause that is constant. Evaluate the ** expression and either jump over all of the code or fall thru. |
︙ | ︙ | |||
1004 1005 1006 1007 1008 1009 1010 1011 1012 1013 1014 1015 1016 1017 | ** and work forward so that they added virtual terms are never processed. */ for(i=0; i<pTabList->nSrc; i++){ createMask(&maskSet, pTabList->a[i].iCursor); } for(i=wc.nTerm-1; i>=0; i--){ exprAnalyze(pTabList, &maskSet, &wc.a[i]); } /* Chose the best index to use for each table in the FROM clause. ** ** This loop fills in the pWInfo->a[].pIdx and pWInfo->a[].flags fields ** with information ** Reorder tables if necessary in order to choose a good ordering. | > > > > | 1046 1047 1048 1049 1050 1051 1052 1053 1054 1055 1056 1057 1058 1059 1060 1061 1062 1063 | ** and work forward so that they added virtual terms are never processed. */ for(i=0; i<pTabList->nSrc; i++){ createMask(&maskSet, pTabList->a[i].iCursor); } for(i=wc.nTerm-1; i>=0; i--){ exprAnalyze(pTabList, &maskSet, &wc.a[i]); } aConstraint = sqliteMalloc( wc.nTerm*sizeof(aConstraint[0]) ); if( aConstraint==0 && wc.nTerm>0 ){ goto whereBeginNoMem; } /* Chose the best index to use for each table in the FROM clause. ** ** This loop fills in the pWInfo->a[].pIdx and pWInfo->a[].flags fields ** with information ** Reorder tables if necessary in order to choose a good ordering. |
︙ | ︙ | |||
1053 1054 1055 1056 1057 1058 1059 1060 1061 1062 1063 1064 1065 1066 | } } if( bestFlags & WHERE_ORDERBY ){ *ppOrderBy = 0; } pLevel->flags = bestFlags; pLevel->pIdx = pBest; if( pBest ){ pLevel->iIdxCur = pParse->nTab++; }else{ pLevel->iIdxCur = -1; } notReady &= ~getMask(&maskSet, pTabList->a[bestJ].iCursor); pLevel->iFrom = bestJ; | > > | 1099 1100 1101 1102 1103 1104 1105 1106 1107 1108 1109 1110 1111 1112 1113 1114 | } } if( bestFlags & WHERE_ORDERBY ){ *ppOrderBy = 0; } pLevel->flags = bestFlags; pLevel->pIdx = pBest; pLevel->aInLoop = 0; pLevel->nIn = 0; if( pBest ){ pLevel->iIdxCur = pParse->nTab++; }else{ pLevel->iIdxCur = -1; } notReady &= ~getMask(&maskSet, pTabList->a[bestJ].iCursor); pLevel->iFrom = bestJ; |
︙ | ︙ | |||
1109 1110 1111 1112 1113 1114 1115 | int omitTable; /* True if we use the index only */ int bRev; /* True if we need to scan in reverse order */ pTabItem = &pTabList->a[pLevel->iFrom]; iCur = pTabItem->iCursor; pIdx = pLevel->pIdx; iIdxCur = pLevel->iIdxCur; | < | 1157 1158 1159 1160 1161 1162 1163 1164 1165 1166 1167 1168 1169 1170 | int omitTable; /* True if we use the index only */ int bRev; /* True if we need to scan in reverse order */ pTabItem = &pTabList->a[pLevel->iFrom]; iCur = pTabItem->iCursor; pIdx = pLevel->pIdx; iIdxCur = pLevel->iIdxCur; bRev = (pLevel->flags & WHERE_REVERSE)!=0; omitTable = (pLevel->flags & WHERE_IDX_ONLY)!=0; /* Create labels for the "break" and "continue" instructions ** for the current loop. Jump to brk to break out of a loop. ** Jump to cont to go immediately to the next iteration of the ** loop. |
︙ | ︙ | |||
1507 1508 1509 1510 1511 1512 1513 | nQPlan = 0; #endif /* SQLITE_TEST // Testing and debugging use only */ /* Record the continuation address in the WhereInfo structure. Then ** clean up and return. */ pWInfo->iContinue = cont; | > > > | > > > | | 1554 1555 1556 1557 1558 1559 1560 1561 1562 1563 1564 1565 1566 1567 1568 1569 1570 1571 1572 1573 1574 1575 1576 | nQPlan = 0; #endif /* SQLITE_TEST // Testing and debugging use only */ /* Record the continuation address in the WhereInfo structure. Then ** clean up and return. */ pWInfo->iContinue = cont; whereClauseClear(&wc); sqliteFree(aConstraint); return pWInfo; /* Jump here if malloc fails */ whereBeginNoMem: whereClauseClear(&wc); sqliteFree(pWInfo); return 0; } /* ** Generate the end of the WHERE loop. See comments on ** sqlite3WhereBegin() for additional information. */ void sqlite3WhereEnd(WhereInfo *pWInfo){ |
︙ | ︙ | |||
1531 1532 1533 1534 1535 1536 1537 | for(i=pTabList->nSrc-1; i>=0; i--){ pLevel = &pWInfo->a[i]; sqlite3VdbeResolveLabel(v, pLevel->cont); if( pLevel->op!=OP_Noop ){ sqlite3VdbeAddOp(v, pLevel->op, pLevel->p1, pLevel->p2); } sqlite3VdbeResolveLabel(v, pLevel->brk); | | > > > | > > | 1584 1585 1586 1587 1588 1589 1590 1591 1592 1593 1594 1595 1596 1597 1598 1599 1600 1601 1602 1603 1604 | for(i=pTabList->nSrc-1; i>=0; i--){ pLevel = &pWInfo->a[i]; sqlite3VdbeResolveLabel(v, pLevel->cont); if( pLevel->op!=OP_Noop ){ sqlite3VdbeAddOp(v, pLevel->op, pLevel->p1, pLevel->p2); } sqlite3VdbeResolveLabel(v, pLevel->brk); if( pLevel->nIn ){ int *a; int j; for(j=pLevel->nIn, a=&pLevel->aInLoop[j*3-3]; j>0; j--, a-=3){ sqlite3VdbeAddOp(v, a[0], a[1], a[2]); } sqliteFree(pLevel->aInLoop); } if( pLevel->iLeftJoin ){ int addr; addr = sqlite3VdbeAddOp(v, OP_MemLoad, pLevel->iLeftJoin, 0); sqlite3VdbeAddOp(v, OP_NotNull, 1, addr+4 + (pLevel->iIdxCur>=0)); sqlite3VdbeAddOp(v, OP_NullRow, pTabList->a[i].iCursor, 0); if( pLevel->iIdxCur>=0 ){ |
︙ | ︙ |