Many hyperlinks are disabled.
Use anonymous login
to enable hyperlinks.
Overview
Comment: | Separate out the code generators for the RHS of an IN operator and for SELECT/EXISTS expressions. |
---|---|
Downloads: | Tarball | ZIP archive |
Timelines: | family | ancestors | descendants | both | subquery-codegen-refactor |
Files: | files | file ages | folders |
SHA1: |
61c34ba71b733b81312078d90c1e21a8 |
User & Date: | drh 2014-02-05 19:10:06.824 |
Context
2014-02-06
| ||
03:31 | Use OpenHash instead of OpenEphemeral for the RHS of IN operators if the result is not needed for sorting. (check-in: 715fac7749 user: drh tags: subquery-codegen-refactor) | |
2014-02-05
| ||
19:10 | Separate out the code generators for the RHS of an IN operator and for SELECT/EXISTS expressions. (check-in: 61c34ba71b user: drh tags: subquery-codegen-refactor) | |
18:15 | Use a new opcode, OP_OpenHash, to indicate that ephemeral tables can be unordered, rather than using the BTREE_UNORDERED bit in the P5 field. (check-in: 2997e18157 user: drh tags: subquery-codegen-refactor) | |
Changes
Changes to src/expr.c.
︙ | ︙ | |||
1486 1487 1488 1489 1490 1491 1492 1493 1494 1495 1496 1497 1498 1499 | ** address of the new instruction. */ int sqlite3CodeOnce(Parse *pParse){ Vdbe *v = sqlite3GetVdbe(pParse); /* Virtual machine being coded */ return sqlite3VdbeAddOp1(v, OP_Once, pParse->nOnce++); } /* ** This function is used by the implementation of the IN (...) operator. ** The pX parameter is the expression on the RHS of the IN operator, which ** might be either a list of expressions or a subquery. ** ** The job of this routine is to find or create a b-tree object that can ** be used either to test for membership in the RHS set or to iterate through | > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > | 1486 1487 1488 1489 1490 1491 1492 1493 1494 1495 1496 1497 1498 1499 1500 1501 1502 1503 1504 1505 1506 1507 1508 1509 1510 1511 1512 1513 1514 1515 1516 1517 1518 1519 1520 1521 1522 1523 1524 1525 1526 1527 1528 1529 1530 1531 1532 1533 1534 1535 1536 1537 1538 1539 1540 1541 1542 1543 1544 1545 1546 1547 1548 1549 1550 1551 1552 1553 1554 1555 1556 1557 1558 1559 1560 1561 1562 1563 1564 1565 1566 1567 1568 1569 1570 1571 1572 1573 1574 1575 1576 1577 1578 1579 1580 1581 1582 1583 1584 1585 1586 1587 1588 1589 1590 1591 1592 1593 1594 1595 1596 1597 1598 1599 1600 1601 1602 1603 1604 1605 1606 1607 1608 1609 1610 1611 1612 1613 1614 1615 1616 1617 1618 1619 1620 1621 1622 1623 1624 1625 1626 1627 1628 1629 1630 1631 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 | ** address of the new instruction. */ int sqlite3CodeOnce(Parse *pParse){ Vdbe *v = sqlite3GetVdbe(pParse); /* Virtual machine being coded */ return sqlite3VdbeAddOp1(v, OP_Once, pParse->nOnce++); } /* ** Generate code that constructs a transient table for the RHS of an IN ** operator: ** ** x IN (4,5,11) -- IN operator with list on right-hand side ** x IN (SELECT a FROM b) -- IN operator with subquery on the right ** ** The pExpr parameter is the IN expression. ** ** If parameter isRowid is non-zero, then expression pExpr is guaranteed ** to be of the form "<rowid> IN (?, ?, ?)", where <rowid> is a reference ** to some integer key column of a table B-Tree. In this case, use an ** intkey B-Tree to store the set of IN(...) values instead of the usual ** (slower) variable length keys B-Tree. */ #ifndef SQLITE_OMIT_SUBQUERY static void sqlite3CreateInOperatorRhsTable( Parse *pParse, /* Parsing context */ Expr *pExpr, /* The IN, SELECT, or EXISTS operator */ int isRowid /* If true, LHS of IN operator is a rowid */ ){ int testAddr = -1; /* One-time test address */ Vdbe *v = sqlite3GetVdbe(pParse); /* prepared stmt under construction */ char affinity; /* Affinity of the LHS of the IN */ int addr; /* Address of OP_Open.. instruction */ Expr *pLeft = pExpr->pLeft; /* the LHS of the IN operator */ KeyInfo *pKeyInfo = 0; /* Key information */ assert( v!=0 ); assert( pExpr->op==TK_IN ); sqlite3ExprCachePush(pParse); /* This code must be run in its entirety every time it is encountered ** if any of the following is true: ** ** * The right-hand side is a correlated subquery ** * We are inside a trigger ** ** If all of the above are false, then we can run this code just once ** save the results, and reuse the same result on subsequent invocations. */ if( !ExprHasProperty(pExpr, EP_VarSelect) ){ testAddr = sqlite3CodeOnce(pParse); } #ifndef SQLITE_OMIT_EXPLAIN if( pParse->explain==2 ){ char *zMsg = sqlite3MPrintf( pParse->db, "EXECUTE %sLIST SUBQUERY %d", testAddr>=0?"":"CORRELATED ", pParse->iNextSelectId ); sqlite3VdbeAddOp4(v, OP_Explain, pParse->iSelectId, 0, 0, zMsg, P4_DYNAMIC); } #endif affinity = sqlite3ExprAffinity(pLeft); /* Whether this is an 'x IN(SELECT...)' or an 'x IN(<exprlist>)' ** expression it is handled the same way. An ephemeral table is ** filled with single-field index keys representing the results ** from the SELECT or the <exprlist>. ** ** If the 'x' expression is a column value, or the SELECT... ** statement returns a column value, then the affinity of that ** column is used to build the index keys. If both 'x' and the ** SELECT... statement are columns, then numeric affinity is used ** if either column has NUMERIC or INTEGER affinity. If neither ** 'x' nor the SELECT... statement are columns, then numeric affinity ** is used. */ pExpr->iTable = pParse->nTab++; addr = sqlite3VdbeAddOp2(v, OP_OpenEphemeral, pExpr->iTable, !isRowid); pKeyInfo = isRowid ? 0 : sqlite3KeyInfoAlloc(pParse->db, 1, 1); if( ExprHasProperty(pExpr, EP_xIsSelect) ){ /* Case 1: expr IN (SELECT ...) ** ** Generate code to write the results of the select into the temporary ** table allocated and opened above. */ SelectDest dest; ExprList *pEList; assert( !isRowid ); sqlite3SelectDestInit(&dest, SRT_Set, pExpr->iTable); dest.affSdst = (u8)affinity; assert( (pExpr->iTable&0x0000FFFF)==pExpr->iTable ); pExpr->x.pSelect->iLimit = 0; testcase( pKeyInfo==0 ); /* Caused by OOM in sqlite3KeyInfoAlloc() */ if( sqlite3Select(pParse, pExpr->x.pSelect, &dest) ){ sqlite3KeyInfoUnref(pKeyInfo); return; } pEList = pExpr->x.pSelect->pEList; assert( pKeyInfo!=0 ); /* OOM will cause exit after sqlite3Select() */ assert( pEList!=0 ); assert( pEList->nExpr>0 ); assert( sqlite3KeyInfoIsWriteable(pKeyInfo) ); pKeyInfo->aColl[0] = sqlite3BinaryCompareCollSeq(pParse, pExpr->pLeft, pEList->a[0].pExpr); }else if( ALWAYS(pExpr->x.pList!=0) ){ /* Case 2: expr IN (exprlist) ** ** For each expression, build an index key from the evaluation and ** store it in the temporary table. If <expr> is a column, then use ** that columns affinity when building index keys. If <expr> is not ** a column, use numeric affinity. */ int i; ExprList *pList = pExpr->x.pList; struct ExprList_item *pItem; int r1, r2, r3; if( !affinity ){ affinity = SQLITE_AFF_NONE; } if( pKeyInfo ){ assert( sqlite3KeyInfoIsWriteable(pKeyInfo) ); pKeyInfo->aColl[0] = sqlite3ExprCollSeq(pParse, pExpr->pLeft); } /* Loop through each expression in <exprlist>. */ r1 = sqlite3GetTempReg(pParse); r2 = sqlite3GetTempReg(pParse); sqlite3VdbeAddOp2(v, OP_Null, 0, r2); for(i=pList->nExpr, pItem=pList->a; i>0; i--, pItem++){ Expr *pE2 = pItem->pExpr; int iValToIns; /* If the expression is not constant then we will need to ** disable the test that was generated above that makes sure ** this code only executes once. Because for a non-constant ** expression we need to rerun this code each time. */ if( testAddr>=0 && !sqlite3ExprIsConstant(pE2) ){ sqlite3VdbeChangeToNoop(v, testAddr); testAddr = -1; } /* Evaluate the expression and insert it into the temp table */ if( isRowid && sqlite3ExprIsInteger(pE2, &iValToIns) ){ sqlite3VdbeAddOp3(v, OP_InsertInt, pExpr->iTable, r2, iValToIns); }else{ r3 = sqlite3ExprCodeTarget(pParse, pE2, r1); if( isRowid ){ sqlite3VdbeAddOp2(v, OP_MustBeInt, r3, sqlite3VdbeCurrentAddr(v)+2); sqlite3VdbeAddOp3(v, OP_Insert, pExpr->iTable, r2, r3); }else{ sqlite3VdbeAddOp4(v, OP_MakeRecord, r3, 1, r2, &affinity, 1); sqlite3ExprCacheAffinityChange(pParse, r3, 1); sqlite3VdbeAddOp2(v, OP_IdxInsert, pExpr->iTable, r2); } } } sqlite3ReleaseTempReg(pParse, r1); sqlite3ReleaseTempReg(pParse, r2); } if( pKeyInfo ){ sqlite3VdbeChangeP4(v, addr, (void *)pKeyInfo, P4_KEYINFO); } if( testAddr>=0 ){ sqlite3VdbeJumpHere(v, testAddr); } sqlite3ExprCachePop(pParse, 1); } #endif /* SQLITE_OMIT_SUBQUERY */ /* ** This function is used by the implementation of the IN (...) operator. ** The pX parameter is the expression on the RHS of the IN operator, which ** might be either a list of expressions or a subquery. ** ** The job of this routine is to find or create a b-tree object that can ** be used either to test for membership in the RHS set or to iterate through |
︙ | ︙ | |||
1558 1559 1560 1561 1562 1563 1564 1565 1566 1567 1568 1569 1570 1571 1572 | int sqlite3FindInIndex(Parse *pParse, Expr *pX, int *prNotFound){ Select *p; /* SELECT to the right of IN operator */ int eType = 0; /* Type of RHS table. IN_INDEX_* */ int iTab = pParse->nTab++; /* Cursor of the RHS table */ int mustBeUnique = (prNotFound==0); /* True if RHS must be unique */ Vdbe *v = sqlite3GetVdbe(pParse); /* Virtual machine being coded */ assert( pX->op==TK_IN ); /* Check to see if an existing table or index can be used to ** satisfy the query. This is preferable to generating a new ** ephemeral table. */ p = (ExprHasProperty(pX, EP_xIsSelect) ? pX->x.pSelect : 0); if( ALWAYS(pParse->nErr==0) && isCandidateForInOpt(p) ){ | > | | | | | < < < < < < < | < < | 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 | int sqlite3FindInIndex(Parse *pParse, Expr *pX, int *prNotFound){ Select *p; /* SELECT to the right of IN operator */ int eType = 0; /* Type of RHS table. IN_INDEX_* */ int iTab = pParse->nTab++; /* Cursor of the RHS table */ int mustBeUnique = (prNotFound==0); /* True if RHS must be unique */ Vdbe *v = sqlite3GetVdbe(pParse); /* Virtual machine being coded */ assert( v!=0 ); assert( pX->op==TK_IN ); /* Check to see if an existing table or index can be used to ** satisfy the query. This is preferable to generating a new ** ephemeral table. */ p = (ExprHasProperty(pX, EP_xIsSelect) ? pX->x.pSelect : 0); if( ALWAYS(pParse->nErr==0) && isCandidateForInOpt(p) ){ sqlite3 *db = pParse->db; /* Database connection */ Table *pTab; /* Table <table>. */ Expr *pExpr; /* Expression <column> */ i16 iCol; /* Index of column <column> */ i16 iDb; /* Database idx for pTab */ assert( p ); /* Because of isCandidateForInOpt(p) */ assert( p->pEList!=0 ); /* Because of isCandidateForInOpt(p) */ assert( p->pEList->a[0].pExpr!=0 ); /* Because of isCandidateForInOpt(p) */ assert( p->pSrc!=0 ); /* Because of isCandidateForInOpt(p) */ pTab = p->pSrc->a[0].pTab; pExpr = p->pEList->a[0].pExpr; iCol = (i16)pExpr->iColumn; /* Code an OP_VerifyCookie and OP_TableLock for <table>. */ iDb = sqlite3SchemaToIndex(db, pTab->pSchema); sqlite3CodeVerifySchema(pParse, iDb); sqlite3TableLock(pParse, iDb, pTab->tnum, 0, pTab->zName); if( iCol<0 ){ int iAddr = sqlite3CodeOnce(pParse); sqlite3OpenTable(pParse, iTab, iDb, pTab, OP_OpenRead); eType = IN_INDEX_ROWID; sqlite3VdbeJumpHere(v, iAddr); }else{ Index *pIdx; /* Iterator variable */ /* The collation sequence used by the comparison. If an index is to ** be used in place of a temp-table, it must be ordered according ** to this collation sequence. */ |
︙ | ︙ | |||
1652 1653 1654 1655 1656 1657 1658 | }else{ testcase( pParse->nQueryLoop>0 ); pParse->nQueryLoop = 0; if( pX->pLeft->iColumn<0 && !ExprHasProperty(pX, EP_xIsSelect) ){ eType = IN_INDEX_ROWID; } } | | | < < < | < < < < < < < < < < < < < < < < < < < | < | | < < > > > > > > > | < | | < < < < < < < < < < < < < < < < < < < < < < < < < < < < < < < < < < < < < < < < < < < < < < < < < < < < < < < < < < < < < < < < < < < < < < < < < < < < < < < < < < < < < < < < < < < < < < < < < < < < < < < < < < < < < < < < < < < < < < < < < < < < < < < < < < < < < < < < < | | | | | | | | | | | | | | | | | | | | < < < | 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 1843 1844 1845 1846 1847 1848 1849 1850 1851 1852 1853 1854 1855 1856 1857 1858 1859 1860 1861 1862 1863 1864 1865 1866 1867 1868 1869 1870 1871 1872 1873 1874 1875 1876 1877 1878 1879 1880 1881 1882 1883 1884 1885 1886 1887 1888 1889 1890 1891 1892 1893 1894 1895 1896 1897 1898 1899 1900 1901 1902 1903 1904 1905 1906 | }else{ testcase( pParse->nQueryLoop>0 ); pParse->nQueryLoop = 0; if( pX->pLeft->iColumn<0 && !ExprHasProperty(pX, EP_xIsSelect) ){ eType = IN_INDEX_ROWID; } } sqlite3CreateInOperatorRhsTable(pParse, pX, eType==IN_INDEX_ROWID); pParse->nQueryLoop = savedNQueryLoop; }else{ pX->iTable = iTab; } return eType; } #endif /* ** Generate code for scalar subqueries used as a subquery expression: ** ** (SELECT a FROM b) -- subquery ** EXISTS (SELECT a FROM b) -- EXISTS subquery ** ** The pExpr parameter describes the expression that contains the subquery. ** ** Return the register that holds the result. */ #ifndef SQLITE_OMIT_SUBQUERY static int sqlite3CodeScalarSubquery( Parse *pParse, /* Parsing context */ Expr *pExpr /* The SELECT or EXISTS operator */ ){ int testAddr = -1; /* One-time test address */ int rReg = 0; /* Register storing resulting */ Vdbe *v = sqlite3GetVdbe(pParse); Select *pSel; /* SELECT statement to encode */ SelectDest dest; /* How to deal with SELECt result */ if( NEVER(v==0) ) return 0; testcase( pExpr->op==TK_EXISTS ); testcase( pExpr->op==TK_SELECT ); assert( pExpr->op==TK_EXISTS || pExpr->op==TK_SELECT ); assert( ExprHasProperty(pExpr, EP_xIsSelect) ); sqlite3ExprCachePush(pParse); /* This code must be run in its entirety every time it is encountered ** if any of the following is true: ** ** * pExpr is a correlated subquery ** * We are inside a trigger ** ** If all of the above are false, then we can run this code just once ** save the results, and reuse the same result on subsequent invocations. */ if( !ExprHasProperty(pExpr, EP_VarSelect) ){ testAddr = sqlite3CodeOnce(pParse); } #ifndef SQLITE_OMIT_EXPLAIN if( pParse->explain==2 ){ char *zMsg = sqlite3MPrintf( pParse->db, "EXECUTE %sSCALAR SUBQUERY %d", testAddr>=0?"":"CORRELATED ", pParse->iNextSelectId ); sqlite3VdbeAddOp4(v, OP_Explain, pParse->iSelectId, 0, 0, zMsg, P4_DYNAMIC); } #endif pSel = pExpr->x.pSelect; sqlite3SelectDestInit(&dest, 0, ++pParse->nMem); if( pExpr->op==TK_SELECT ){ dest.eDest = SRT_Mem; sqlite3VdbeAddOp2(v, OP_Null, 0, dest.iSDParm); VdbeComment((v, "Init subquery result")); }else{ dest.eDest = SRT_Exists; sqlite3VdbeAddOp2(v, OP_Integer, 0, dest.iSDParm); VdbeComment((v, "Init EXISTS result")); } sqlite3ExprDelete(pParse->db, pSel->pLimit); pSel->pLimit = sqlite3PExpr(pParse, TK_INTEGER, 0, 0, &sqlite3IntTokens[1]); pSel->iLimit = 0; if( sqlite3Select(pParse, pSel, &dest) ){ return 0; } rReg = dest.iSDParm; ExprSetVVAProperty(pExpr, EP_NoReduce); if( testAddr>=0 ){ sqlite3VdbeJumpHere(v, testAddr); } sqlite3ExprCachePop(pParse, 1); return rReg; |
︙ | ︙ | |||
2809 2810 2811 2812 2813 2814 2815 | break; } #ifndef SQLITE_OMIT_SUBQUERY case TK_EXISTS: case TK_SELECT: { testcase( op==TK_EXISTS ); testcase( op==TK_SELECT ); | | | 2811 2812 2813 2814 2815 2816 2817 2818 2819 2820 2821 2822 2823 2824 2825 | break; } #ifndef SQLITE_OMIT_SUBQUERY case TK_EXISTS: case TK_SELECT: { testcase( op==TK_EXISTS ); testcase( op==TK_SELECT ); inReg = sqlite3CodeScalarSubquery(pParse, pExpr); break; } case TK_IN: { int destIfFalse = sqlite3VdbeMakeLabel(v); int destIfNull = sqlite3VdbeMakeLabel(v); sqlite3VdbeAddOp2(v, OP_Null, 0, target); sqlite3ExprCodeIN(pParse, pExpr, destIfFalse, destIfNull); |
︙ | ︙ |
Changes to src/sqliteInt.h.
︙ | ︙ | |||
3279 3280 3281 3282 3283 3284 3285 | void sqlite3RootPageMoved(sqlite3*, int, int, int); void sqlite3Reindex(Parse*, Token*, Token*); void sqlite3AlterFunctions(void); void sqlite3AlterRenameTable(Parse*, SrcList*, Token*); int sqlite3GetToken(const unsigned char *, int *); void sqlite3NestedParse(Parse*, const char*, ...); void sqlite3ExpirePreparedStatements(sqlite3*); | < | 3279 3280 3281 3282 3283 3284 3285 3286 3287 3288 3289 3290 3291 3292 | void sqlite3RootPageMoved(sqlite3*, int, int, int); void sqlite3Reindex(Parse*, Token*, Token*); void sqlite3AlterFunctions(void); void sqlite3AlterRenameTable(Parse*, SrcList*, Token*); int sqlite3GetToken(const unsigned char *, int *); void sqlite3NestedParse(Parse*, const char*, ...); void sqlite3ExpirePreparedStatements(sqlite3*); void sqlite3SelectPrep(Parse*, Select*, NameContext*); int sqlite3MatchSpanName(const char*, const char*, const char*, const char*); int sqlite3ResolveExprNames(NameContext*, Expr*); void sqlite3ResolveSelectNames(Parse*, Select*, NameContext*); void sqlite3ResolveSelfReference(Parse*,Table*,int,Expr*,ExprList*); int sqlite3ResolveOrderGroupBy(Parse*, Select*, ExprList*, const char*); void sqlite3ColumnDefault(Vdbe *, Table *, int, int); |
︙ | ︙ |