Many hyperlinks are disabled.
Use anonymous login
to enable hyperlinks.
Overview
Comment: | Optimize queries that contain "WHERE rowid IN (x, y, z...)" by using an intkey btree to store the (x, y, z...) set instead of an index btree. (CVS 5760) |
---|---|
Downloads: | Tarball | ZIP archive |
Timelines: | family | ancestors | descendants | both | trunk |
Files: | files | file ages | folders |
SHA1: |
803a1736d56b3c07b8ad38715fe0e391 |
User & Date: | danielk1977 2008-10-02 13:50:56.000 |
Context
2008-10-02
| ||
14:33 | Fix a typo that prevents the sqlite3_sql() interface from appearing in the official documentation. (CVS 5761) (check-in: b46814b202 user: drh tags: trunk) | |
13:50 | Optimize queries that contain "WHERE rowid IN (x, y, z...)" by using an intkey btree to store the (x, y, z...) set instead of an index btree. (CVS 5760) (check-in: 803a1736d5 user: danielk1977 tags: trunk) | |
2008-10-01
| ||
13:55 | Adjust the memory usage bounds on the memsubsys1.test script so that it works on amd64. (CVS 5759) (check-in: aabde23fe1 user: drh tags: trunk) | |
Changes
Changes to src/expr.c.
︙ | ︙ | |||
8 9 10 11 12 13 14 | ** May you find forgiveness for yourself and forgive others. ** May you share freely, never taking more than you give. ** ************************************************************************* ** This file contains routines used for analyzing expressions and ** for generating VDBE code that evaluates expressions in SQLite. ** | | | 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 | ** May you find forgiveness for yourself and forgive others. ** May you share freely, never taking more than you give. ** ************************************************************************* ** This file contains routines used for analyzing expressions and ** for generating VDBE code that evaluates expressions in SQLite. ** ** $Id: expr.c,v 1.395 2008/10/02 13:50:56 danielk1977 Exp $ */ #include "sqliteInt.h" #include <ctype.h> /* ** Return the 'affinity' of the expression pExpr if any. ** |
︙ | ︙ | |||
1210 1211 1212 1213 1214 1215 1216 1217 1218 1219 | } } } } if( eType==0 ){ int rMayHaveNull = 0; if( prNotFound ){ *prNotFound = rMayHaveNull = ++pParse->nMem; } | > > > | < > > > > > > | > > > > > | 1210 1211 1212 1213 1214 1215 1216 1217 1218 1219 1220 1221 1222 1223 1224 1225 1226 1227 1228 1229 1230 1231 1232 1233 1234 1235 1236 1237 1238 1239 1240 1241 1242 1243 1244 1245 1246 1247 1248 1249 1250 1251 1252 1253 1254 1255 1256 1257 1258 1259 1260 1261 1262 | } } } } if( eType==0 ){ int rMayHaveNull = 0; eType = IN_INDEX_EPH; if( prNotFound ){ *prNotFound = rMayHaveNull = ++pParse->nMem; }else if( pX->pLeft->iColumn<0 && pX->pSelect==0 ){ eType = IN_INDEX_ROWID; } sqlite3CodeSubselect(pParse, pX, rMayHaveNull, eType==IN_INDEX_ROWID); }else{ pX->iTable = iTab; } return eType; } #endif /* ** Generate code for scalar subqueries used as an expression ** and IN operators. Examples: ** ** (SELECT a FROM b) -- subquery ** EXISTS (SELECT a FROM b) -- EXISTS subquery ** 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 describes the expression that contains the IN ** operator or subquery. ** ** 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 void sqlite3CodeSubselect( Parse *pParse, Expr *pExpr, int rMayHaveNull, int isRowid ){ int testAddr = 0; /* One-time test address */ Vdbe *v = sqlite3GetVdbe(pParse); if( v==0 ) return; /* This code must be run in its entirety every time it is encountered ** if any of the following is true: |
︙ | ︙ | |||
1263 1264 1265 1266 1267 1268 1269 1270 1271 1272 1273 1274 | } switch( pExpr->op ){ case TK_IN: { char affinity; KeyInfo keyInfo; int addr; /* Address of OP_OpenEphemeral instruction */ if( rMayHaveNull ){ sqlite3VdbeAddOp2(v, OP_Null, 0, rMayHaveNull); } | > | | > | 1276 1277 1278 1279 1280 1281 1282 1283 1284 1285 1286 1287 1288 1289 1290 1291 1292 1293 1294 1295 1296 1297 1298 1299 1300 1301 1302 1303 1304 1305 1306 1307 1308 1309 1310 1311 1312 1313 1314 1315 1316 1317 1318 1319 1320 1321 1322 1323 1324 1325 | } switch( pExpr->op ){ case TK_IN: { char affinity; KeyInfo keyInfo; int addr; /* Address of OP_OpenEphemeral instruction */ Expr *pLeft = pExpr->pLeft; if( rMayHaveNull ){ sqlite3VdbeAddOp2(v, OP_Null, 0, rMayHaveNull); } affinity = sqlite3ExprAffinity(pLeft); /* Whether this is an 'x IN(SELECT...)' or an 'x IN(<exprlist>)' ** expression it is handled the same way. A virtual 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); memset(&keyInfo, 0, sizeof(keyInfo)); keyInfo.nField = 1; if( pExpr->pSelect ){ /* 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.affinity = (int)affinity; assert( (pExpr->iTable&0x0000FFFF)==pExpr->iTable ); if( sqlite3Select(pParse, pExpr->pSelect, &dest) ){ return; } pEList = pExpr->pSelect->pEList; |
︙ | ︙ | |||
1347 1348 1349 1350 1351 1352 1353 | } /* Evaluate the expression and insert it into the temp table */ pParse->disableColCache++; r3 = sqlite3ExprCodeTarget(pParse, pE2, r1); assert( pParse->disableColCache>0 ); pParse->disableColCache--; | > > > > > > | | | > > | > | 1362 1363 1364 1365 1366 1367 1368 1369 1370 1371 1372 1373 1374 1375 1376 1377 1378 1379 1380 1381 1382 1383 1384 1385 1386 1387 1388 1389 1390 1391 1392 | } /* Evaluate the expression and insert it into the temp table */ pParse->disableColCache++; r3 = sqlite3ExprCodeTarget(pParse, pE2, r1); assert( pParse->disableColCache>0 ); pParse->disableColCache--; if( isRowid ){ sqlite3VdbeAddOp2(v, OP_Null, 0, r2); 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( !isRowid ){ sqlite3VdbeChangeP4(v, addr, (void *)&keyInfo, P4_KEYINFO); } break; } case TK_EXISTS: case TK_SELECT: { /* This has to be a scalar SELECT. Generate code to put the ** value of this select in a memory cell and record the number |
︙ | ︙ | |||
2022 2023 2024 2025 2026 2027 2028 | } #ifndef SQLITE_OMIT_SUBQUERY case TK_EXISTS: case TK_SELECT: { testcase( op==TK_EXISTS ); testcase( op==TK_SELECT ); if( pExpr->iColumn==0 ){ | | | 2046 2047 2048 2049 2050 2051 2052 2053 2054 2055 2056 2057 2058 2059 2060 | } #ifndef SQLITE_OMIT_SUBQUERY case TK_EXISTS: case TK_SELECT: { testcase( op==TK_EXISTS ); testcase( op==TK_SELECT ); if( pExpr->iColumn==0 ){ sqlite3CodeSubselect(pParse, pExpr, 0, 0); } inReg = pExpr->iColumn; break; } case TK_IN: { int rNotFound = 0; int rMayHaveNull = 0; |
︙ | ︙ | |||
2105 2106 2107 2108 2109 2110 2111 | nullRecord, P4_STATIC); j4 = sqlite3VdbeAddOp3(v, OP_Found, pExpr->iTable, 0, rMayHaveNull); sqlite3VdbeAddOp2(v, OP_Integer, 0, rNotFound); sqlite3VdbeJumpHere(v, j4); sqlite3VdbeJumpHere(v, j3); /* Copy the value of register rNotFound (which is either NULL or 0) | | | 2129 2130 2131 2132 2133 2134 2135 2136 2137 2138 2139 2140 2141 2142 2143 | nullRecord, P4_STATIC); j4 = sqlite3VdbeAddOp3(v, OP_Found, pExpr->iTable, 0, rMayHaveNull); sqlite3VdbeAddOp2(v, OP_Integer, 0, rNotFound); sqlite3VdbeJumpHere(v, j4); sqlite3VdbeJumpHere(v, j3); /* Copy the value of register rNotFound (which is either NULL or 0) ** into the target register. This will be the result of the ** expression. */ sqlite3VdbeAddOp2(v, OP_Copy, rNotFound, target); } } sqlite3VdbeJumpHere(v, j2); sqlite3VdbeJumpHere(v, j5); |
︙ | ︙ |
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.773 2008/10/02 13:50:56 danielk1977 Exp $ */ #ifndef _SQLITEINT_H_ #define _SQLITEINT_H_ /* ** Include the configuration header output by 'configure' if we're using the ** autoconf-based build |
︙ | ︙ | |||
2363 2364 2365 2366 2367 2368 2369 | void sqlite3RootPageMoved(Db*, int, int); void sqlite3Reindex(Parse*, Token*, Token*); void sqlite3AlterFunctions(sqlite3*); void sqlite3AlterRenameTable(Parse*, SrcList*, Token*); int sqlite3GetToken(const unsigned char *, int *); void sqlite3NestedParse(Parse*, const char*, ...); void sqlite3ExpirePreparedStatements(sqlite3*); | | | 2363 2364 2365 2366 2367 2368 2369 2370 2371 2372 2373 2374 2375 2376 2377 | void sqlite3RootPageMoved(Db*, int, int); void sqlite3Reindex(Parse*, Token*, Token*); void sqlite3AlterFunctions(sqlite3*); void sqlite3AlterRenameTable(Parse*, SrcList*, Token*); int sqlite3GetToken(const unsigned char *, int *); void sqlite3NestedParse(Parse*, const char*, ...); void sqlite3ExpirePreparedStatements(sqlite3*); void sqlite3CodeSubselect(Parse *, Expr *, int, int); void sqlite3SelectPrep(Parse*, Select*, NameContext*); int sqlite3ResolveExprNames(NameContext*, Expr*); void sqlite3ResolveSelectNames(Parse*, Select*, NameContext*); int sqlite3ResolveOrderGroupBy(Parse*, Select*, ExprList*, const char*); void sqlite3ColumnDefault(Vdbe *, Table *, int); void sqlite3AlterFinishAddColumn(Parse *, Token *); void sqlite3AlterBeginAddColumn(Parse *, SrcList *); |
︙ | ︙ |
Added test/in4.test.
> > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > | 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 | # 2008 September 1 # # 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. # #*********************************************************************** # # $Id: in4.test,v 1.1 2008/10/02 13:50:56 danielk1977 Exp $ set testdir [file dirname $argv0] source $testdir/tester.tcl do_test in4-1.1 { execsql { CREATE TABLE t1(a, b); CREATE INDEX i1 ON t1(a); } } {} do_test in4-1.2 { execsql { SELECT * FROM t1 WHERE a IN ('aaa', 'bbb', 'ccc'); } } {} do_test in4-1.3 { execsql { INSERT INTO t1 VALUES('aaa', 1); INSERT INTO t1 VALUES('ddd', 2); INSERT INTO t1 VALUES('ccc', 3); INSERT INTO t1 VALUES('eee', 4); SELECT b FROM t1 WHERE a IN ('aaa', 'bbb', 'ccc'); } } {1 3} do_test in4-1.4 { execsql { SELECT a FROM t1 WHERE rowid IN (1, 3); } } {aaa ccc} do_test in4-1.5 { execsql { SELECT a FROM t1 WHERE rowid IN (); } } {} do_test in4-1.6 { execsql { SELECT a FROM t1 WHERE a IN ('ddd'); } } {ddd} do_test in4-2.1 { execsql { CREATE TABLE t2(a INTEGER PRIMARY KEY, b TEXT); INSERT INTO t2 VALUES(-1, '-one'); INSERT INTO t2 VALUES(0, 'zero'); INSERT INTO t2 VALUES(1, 'one'); INSERT INTO t2 VALUES(2, 'two'); INSERT INTO t2 VALUES(3, 'three'); } } {} do_test in4-2.2 { execsql { SELECT b FROM t2 WHERE a IN (0, 2) } } {zero two} do_test in4-2.3 { execsql { SELECT b FROM t2 WHERE a IN (2, 0) } } {zero two} do_test in4-2.4 { execsql { SELECT b FROM t2 WHERE a IN (2, -1) } } {-one two} do_test in4-2.5 { execsql { SELECT b FROM t2 WHERE a IN (NULL, 3) } } {three} do_test in4-2.6 { execsql { SELECT b FROM t2 WHERE a IN (1.0, 2.1) } } {one} do_test in4-2.7 { execsql { SELECT b FROM t2 WHERE a IN ('1', '2') } } {one two} do_test in4-2.8 { execsql { SELECT b FROM t2 WHERE a IN ('', '0.0.0', '2') } } {two} finish_test |