Many hyperlinks are disabled.
Use anonymous login
to enable hyperlinks.
Overview
| Comment: | The idea of coding IN operator with a short list on the RHS as an OR expression turns out to be helpful. If the list is of length 1 or 2, the OR expression is very slightly faster, but the ephemeral table approach is clearly better for all list lengths greater than 2. Better to keep the code simple. |
|---|---|
| Downloads: | Tarball | ZIP archive | SQL archive |
| Timelines: | family | ancestors | descendants | both | IN-operator-improvements |
| Files: | files | file ages | folders |
| SHA1: |
e13175d3579e1045165bab091b3b2895 |
| User & Date: | drh 2014-08-01 15:34:36 |
Context
|
2014-08-01
| ||
| 15:51 | Clean up the IN operator code generation logic to make it easier to reason about. In the process, improve code generation to omit some unused OP_Null operations. check-in: 7c6fbcfe user: drh tags: trunk | |
| 15:34 | The idea of coding IN operator with a short list on the RHS as an OR expression turns out to be helpful. If the list is of length 1 or 2, the OR expression is very slightly faster, but the ephemeral table approach is clearly better for all list lengths greater than 2. Better to keep the code simple. Closed-Leaf check-in: e13175d3 user: drh tags: IN-operator-improvements | |
| 14:46 | Begin making changes to the IN operator in an attempt to make it run faster and to make the code easier to understand. check-in: ee0fd6aa user: drh tags: IN-operator-improvements | |
Changes
Changes to src/expr.c.
1490 1491 1492 1493 1494 1495 1496 1497 1498 1499 1500 1501 1502 1503 1504 1505 .... 1521 1522 1523 1524 1525 1526 1527 1528 1529 1530 1531 1532 1533 1534 1535 1536 1537 1538 1539 1540 1541 .... 1935 1936 1937 1938 1939 1940 1941 1942 1943 1944 1945 1946 1947 1948 1949 .... 1982 1983 1984 1985 1986 1987 1988 1989 1990 1991 1992 1993 1994 1995 1996 |
** The returned value of this function indicates the b-tree type, as follows: ** ** IN_INDEX_ROWID - The cursor was opened on a database table. ** IN_INDEX_INDEX_ASC - The cursor was opened on an ascending index. ** IN_INDEX_INDEX_DESC - The cursor was opened on a descending index. ** IN_INDEX_EPH - The cursor was opened on a specially created and ** populated epheremal table. ** IN_INDEX_NOOP - No cursor was allocated. The in operator must be ** implemented as a sequence of comparisons. ** ** An existing b-tree might be used if the RHS expression pX is a simple ** subquery such as: ** ** SELECT <column> FROM <table> ** ** If the RHS of the IN operator is a list or a more complex subquery, then ................................................................................ ** has a UNIQUE constraint or UNIQUE index. ** ** When IN_INDEX_MEMBERSHIP is used (and the b-tree will be used ** for fast set membership tests) then an epheremal table must ** be used unless <column> is an INTEGER PRIMARY KEY or an index can ** be found with <column> as its left-most column. ** ** If the IN_INDEX_NOOP_OK and IN_INDEX_MEMBERSHIP are both set and ** if the RHS of the IN operator is a list (not a subquery) then this ** routine might decide that creating an ephemeral b-tree for membership ** testing is too expensive and return IN_INDEX_NOOP. IN that case, the ** calling routine should implement the IN operator using a sequence ** of Eq or Ne comparison operations. ** ** When the b-tree is being used for membership tests, the calling function ** might need to know whether or not the RHS side of the IN operator ** contains a NULL. If prNotFound is not NULL and ** if there is any chance that the (...) might contain a NULL value at ** runtime, then a register is allocated and the register number written ** to *prNotFound. If there is no chance that the (...) contains a ** NULL value, then *prNotFound is left unchanged. ................................................................................ /* Compute the RHS. After this step, the table with cursor ** pExpr->iTable will contains the values that make up the RHS. */ v = pParse->pVdbe; assert( v!=0 ); /* OOM detected prior to this routine */ VdbeNoopComment((v, "begin IN expr")); eType = sqlite3FindInIndex(pParse, pExpr, 0, destIfFalse==destIfNull ? 0 : &rRhsHasNull); /* Figure out the affinity to use to create a key from the results ** of the expression. affinityStr stores a static string suitable for ** P4 of OP_MakeRecord. */ affinity = comparisonAffinity(pExpr); ................................................................................ /* If the set membership test fails, then the result of the ** "x IN (...)" expression must be either 0 or NULL. If the set ** contains no NULL values, then the result is 0. If the set ** contains one or more NULL values, then the result of the ** expression is also NULL. */ if( rRhsHasNull==0 || destIfFalse==destIfNull ){ /* This branch runs if it is known at compile time that the RHS ** cannot contain NULL values. This happens as the result ** of a "NOT NULL" constraint in the database schema. ** ** Also run this branch if NULL is equivalent to FALSE ** for this particular IN operator. */ |
< < < < < < < < < | > | |
1490 1491 1492 1493 1494 1495 1496 1497 1498 1499 1500 1501 1502 1503 .... 1519 1520 1521 1522 1523 1524 1525 1526 1527 1528 1529 1530 1531 1532 .... 1926 1927 1928 1929 1930 1931 1932 1933 1934 1935 1936 1937 1938 1939 1940 .... 1973 1974 1975 1976 1977 1978 1979 1980 1981 1982 1983 1984 1985 1986 1987 1988 |
** The returned value of this function indicates the b-tree type, as follows: ** ** IN_INDEX_ROWID - The cursor was opened on a database table. ** IN_INDEX_INDEX_ASC - The cursor was opened on an ascending index. ** IN_INDEX_INDEX_DESC - The cursor was opened on a descending index. ** IN_INDEX_EPH - The cursor was opened on a specially created and ** populated epheremal table. ** ** An existing b-tree might be used if the RHS expression pX is a simple ** subquery such as: ** ** SELECT <column> FROM <table> ** ** If the RHS of the IN operator is a list or a more complex subquery, then ................................................................................ ** has a UNIQUE constraint or UNIQUE index. ** ** When IN_INDEX_MEMBERSHIP is used (and the b-tree will be used ** for fast set membership tests) then an epheremal table must ** be used unless <column> is an INTEGER PRIMARY KEY or an index can ** be found with <column> as its left-most column. ** ** When the b-tree is being used for membership tests, the calling function ** might need to know whether or not the RHS side of the IN operator ** contains a NULL. If prNotFound is not NULL and ** if there is any chance that the (...) might contain a NULL value at ** runtime, then a register is allocated and the register number written ** to *prNotFound. If there is no chance that the (...) contains a ** NULL value, then *prNotFound is left unchanged. ................................................................................ /* Compute the RHS. After this step, the table with cursor ** pExpr->iTable will contains the values that make up the RHS. */ v = pParse->pVdbe; assert( v!=0 ); /* OOM detected prior to this routine */ VdbeNoopComment((v, "begin IN expr")); eType = sqlite3FindInIndex(pParse, pExpr, IN_INDEX_MEMBERSHIP, destIfFalse==destIfNull ? 0 : &rRhsHasNull); /* Figure out the affinity to use to create a key from the results ** of the expression. affinityStr stores a static string suitable for ** P4 of OP_MakeRecord. */ affinity = comparisonAffinity(pExpr); ................................................................................ /* If the set membership test fails, then the result of the ** "x IN (...)" expression must be either 0 or NULL. If the set ** contains no NULL values, then the result is 0. If the set ** contains one or more NULL values, then the result of the ** expression is also NULL. */ assert( destIfFalse!=destIfNull || rRhsHasNull==0 ); if( rRhsHasNull==0 ){ /* This branch runs if it is known at compile time that the RHS ** cannot contain NULL values. This happens as the result ** of a "NOT NULL" constraint in the database schema. ** ** Also run this branch if NULL is equivalent to FALSE ** for this particular IN operator. */ |
Changes to src/sqliteInt.h.
3594 3595 3596 3597 3598 3599 3600 3601 3602 3603 3604 3605 3606 3607 3608 3609 3610 3611 3612 3613 3614 |
/* ** Allowed return values from sqlite3FindInIndex() */ #define IN_INDEX_ROWID 1 /* Search the rowid of the table */ #define IN_INDEX_EPH 2 /* Search an ephemeral b-tree */ #define IN_INDEX_INDEX_ASC 3 /* Existing index ASCENDING */ #define IN_INDEX_INDEX_DESC 4 /* Existing index DESCENDING */ #define IN_INDEX_NOOP 5 /* No table available. Use comparisons */ /* ** Allowed flags for the 3rd parameter to sqlite3FindInIndex(). */ #define IN_INDEX_NOOP_OK 0x0001 /* OK to return IN_INDEX_NOOP */ #define IN_INDEX_MEMBERSHIP 0x0002 /* IN operator used for membership test */ #define IN_INDEX_LOOP 0x0004 /* IN operator used as a loop */ int sqlite3FindInIndex(Parse *, Expr *, u32, int*); #ifdef SQLITE_ENABLE_ATOMIC_WRITE int sqlite3JournalOpen(sqlite3_vfs *, const char *, sqlite3_file *, int, int); int sqlite3JournalSize(sqlite3_vfs *); int sqlite3JournalCreate(sqlite3_file *); int sqlite3JournalExists(sqlite3_file *p); |
< < | | |
3594 3595 3596 3597 3598 3599 3600 3601 3602 3603 3604 3605 3606 3607 3608 3609 3610 3611 3612 |
/* ** Allowed return values from sqlite3FindInIndex() */ #define IN_INDEX_ROWID 1 /* Search the rowid of the table */ #define IN_INDEX_EPH 2 /* Search an ephemeral b-tree */ #define IN_INDEX_INDEX_ASC 3 /* Existing index ASCENDING */ #define IN_INDEX_INDEX_DESC 4 /* Existing index DESCENDING */ /* ** Allowed flags for the 3rd parameter to sqlite3FindInIndex(). */ #define IN_INDEX_MEMBERSHIP 0x0001 /* IN operator used for membership test */ #define IN_INDEX_LOOP 0x0002 /* IN operator used as a loop */ int sqlite3FindInIndex(Parse *, Expr *, u32, int*); #ifdef SQLITE_ENABLE_ATOMIC_WRITE int sqlite3JournalOpen(sqlite3_vfs *, const char *, sqlite3_file *, int, int); int sqlite3JournalSize(sqlite3_vfs *); int sqlite3JournalCreate(sqlite3_file *); int sqlite3JournalExists(sqlite3_file *p); |