Many hyperlinks are disabled.
Use anonymous login
to enable hyperlinks.
Changes In Branch without-rowid-or-opt Excluding Merge-Ins
This is equivalent to a diff from 856d44a2 to cbec30d0
2014-05-26
| ||
22:05 | Add the OR-optimization to WITHOUT ROWID tables. (check-in: 06a23b8b user: drh tags: trunk) | |
22:01 | Minor enhancements to comments and clarification of the code. (Closed-Leaf check-in: cbec30d0 user: drh tags: without-rowid-or-opt) | |
20:25 | Add a missing VdbeCoverage() macro on an OP_Found opcode added in the previous check-in. (check-in: b4980a07 user: drh tags: without-rowid-or-opt) | |
20:15 | Merge recent trunk changes into the threads branch. (check-in: 82152027 user: drh tags: threads) | |
20:08 | Merge recent trunk changes into the apple-osx branch. (check-in: 54b5fa77 user: drh tags: apple-osx) | |
20:06 | Enable the OR optimization for WITHOUT ROWID tables. Use a temp table instead of the RowSet object to track the rows that have already been included in the result set. (check-in: 2c7e277b user: dan tags: without-rowid-or-opt) | |
20:00 | Merge recent trunk changes into the sessions branch. (check-in: a769c7e0 user: drh tags: sessions) | |
18:27 | Fix a problem in the shell when importing CSV files. If the leftmost field of the first row in the CSV file was both zero bytes in size and unquoted, no data was imported. (check-in: 856d44a2 user: dan tags: trunk) | |
16:40 | Fix a problem in FTS4 where columns with names that are prefixes of any notindexed column were also being (incorrectly) marked as not indexed. For example in "CREATE ... t1(abc, bc, abcd, notindexed=abcd)", both abc and abcd were being treated as notindexed. (check-in: d90c4964 user: dan tags: trunk) | |
Changes to src/where.c.
︙ | ︙ | |||
3289 3290 3291 3292 3293 3294 3295 3296 3297 3298 3299 3300 3301 3302 3303 3304 3305 3306 3307 3308 3309 3310 3311 3312 3313 3314 3315 3316 | ** ** A: <loop body> # Return data, whatever. ** ** Return 2 # Jump back to the Gosub ** ** B: <after the loop> ** */ WhereClause *pOrWc; /* The OR-clause broken out into subterms */ SrcList *pOrTab; /* Shortened table list or OR-clause generation */ Index *pCov = 0; /* Potential covering index (or NULL) */ int iCovCur = pParse->nTab++; /* Cursor used for index scans (if any) */ int regReturn = ++pParse->nMem; /* Register used with OP_Gosub */ int regRowset = 0; /* Register for RowSet object */ int regRowid = 0; /* Register holding rowid */ int iLoopBody = sqlite3VdbeMakeLabel(v); /* Start of loop body */ int iRetInit; /* Address of regReturn init */ int untestedTerms = 0; /* Some terms not completely tested */ int ii; /* Loop counter */ Expr *pAndExpr = 0; /* An ".. AND (...)" expression */ pTerm = pLoop->aLTerm[0]; assert( pTerm!=0 ); assert( pTerm->eOperator & WO_OR ); assert( (pTerm->wtFlags & TERM_ORINFO)!=0 ); pOrWc = &pTerm->u.pOrInfo->wc; pLevel->op = OP_Return; | > > > > > | 3289 3290 3291 3292 3293 3294 3295 3296 3297 3298 3299 3300 3301 3302 3303 3304 3305 3306 3307 3308 3309 3310 3311 3312 3313 3314 3315 3316 3317 3318 3319 3320 3321 | ** ** A: <loop body> # Return data, whatever. ** ** Return 2 # Jump back to the Gosub ** ** B: <after the loop> ** ** Added 2014-05-26: If the table is a WITHOUT ROWID table, then ** use an ephermeral index instead of a RowSet to record the primary ** keys of the rows we have already seen. ** */ WhereClause *pOrWc; /* The OR-clause broken out into subterms */ SrcList *pOrTab; /* Shortened table list or OR-clause generation */ Index *pCov = 0; /* Potential covering index (or NULL) */ int iCovCur = pParse->nTab++; /* Cursor used for index scans (if any) */ int regReturn = ++pParse->nMem; /* Register used with OP_Gosub */ int regRowset = 0; /* Register for RowSet object */ int regRowid = 0; /* Register holding rowid */ int iLoopBody = sqlite3VdbeMakeLabel(v); /* Start of loop body */ int iRetInit; /* Address of regReturn init */ int untestedTerms = 0; /* Some terms not completely tested */ int ii; /* Loop counter */ Expr *pAndExpr = 0; /* An ".. AND (...)" expression */ Table *pTab = pTabItem->pTab; pTerm = pLoop->aLTerm[0]; assert( pTerm!=0 ); assert( pTerm->eOperator & WO_OR ); assert( (pTerm->wtFlags & TERM_ORINFO)!=0 ); pOrWc = &pTerm->u.pOrInfo->wc; pLevel->op = OP_Return; |
︙ | ︙ | |||
3335 3336 3337 3338 3339 3340 3341 | memcpy(&pOrTab->a[k], &origSrc[pLevel[k].iFrom], sizeof(pOrTab->a[k])); } }else{ pOrTab = pWInfo->pTabList; } /* Initialize the rowset register to contain NULL. An SQL NULL is | | > > | < | > > > > > > > | 3340 3341 3342 3343 3344 3345 3346 3347 3348 3349 3350 3351 3352 3353 3354 3355 3356 3357 3358 3359 3360 3361 3362 3363 3364 3365 3366 3367 3368 3369 3370 3371 3372 3373 3374 3375 | memcpy(&pOrTab->a[k], &origSrc[pLevel[k].iFrom], sizeof(pOrTab->a[k])); } }else{ pOrTab = pWInfo->pTabList; } /* Initialize the rowset register to contain NULL. An SQL NULL is ** equivalent to an empty rowset. Or, create an ephermeral index ** capable of holding primary keys in the case of a WITHOUT ROWID. ** ** Also initialize regReturn to contain the address of the instruction ** immediately following the OP_Return at the bottom of the loop. This ** is required in a few obscure LEFT JOIN cases where control jumps ** over the top of the loop into the body of it. In this case the ** correct response for the end-of-loop code (the OP_Return) is to ** fall through to the next instruction, just as an OP_Next does if ** called on an uninitialized cursor. */ if( (pWInfo->wctrlFlags & WHERE_DUPLICATES_OK)==0 ){ if( HasRowid(pTab) ){ regRowset = ++pParse->nMem; sqlite3VdbeAddOp2(v, OP_Null, 0, regRowset); }else{ Index *pPk = sqlite3PrimaryKeyIndex(pTab); regRowset = pParse->nTab++; sqlite3VdbeAddOp2(v, OP_OpenEphemeral, regRowset, pPk->nKeyCol); sqlite3VdbeSetP4KeyInfo(pParse, pPk); } regRowid = ++pParse->nMem; } iRetInit = sqlite3VdbeAddOp2(v, OP_Integer, 0, regReturn); /* If the original WHERE clause is z of the form: (x1 OR x2 OR ...) AND y ** Then for every term xN, evaluate as the subexpression: xN AND z ** That way, terms in y that are factored into the disjunction will ** be picked up by the recursive calls to sqlite3WhereBegin() below. |
︙ | ︙ | |||
3389 3390 3391 3392 3393 3394 3395 3396 3397 3398 3399 3400 3401 3402 3403 3404 3405 3406 3407 3408 3409 3410 | } for(ii=0; ii<pOrWc->nTerm; ii++){ WhereTerm *pOrTerm = &pOrWc->a[ii]; if( pOrTerm->leftCursor==iCur || (pOrTerm->eOperator & WO_AND)!=0 ){ WhereInfo *pSubWInfo; /* Info for single OR-term scan */ Expr *pOrExpr = pOrTerm->pExpr; if( pAndExpr && !ExprHasProperty(pOrExpr, EP_FromJoin) ){ pAndExpr->pLeft = pOrExpr; pOrExpr = pAndExpr; } /* Loop through table entries that match term pOrTerm. */ pSubWInfo = sqlite3WhereBegin(pParse, pOrTab, pOrExpr, 0, 0, WHERE_OMIT_OPEN_CLOSE | WHERE_AND_ONLY | WHERE_FORCE_TABLE | WHERE_ONETABLE_ONLY, iCovCur); assert( pSubWInfo || pParse->nErr || db->mallocFailed ); if( pSubWInfo ){ WhereLoop *pSubLoop; explainOneScan( pParse, pOrTab, &pSubWInfo->a[0], iLevel, pLevel->iFrom, 0 ); if( (pWInfo->wctrlFlags & WHERE_DUPLICATES_OK)==0 ){ | > < > > | < | > > > > > | > > > > > > > > > > > > > > > > > > > > | | > > > > > > > > > > > | 3402 3403 3404 3405 3406 3407 3408 3409 3410 3411 3412 3413 3414 3415 3416 3417 3418 3419 3420 3421 3422 3423 3424 3425 3426 3427 3428 3429 3430 3431 3432 3433 3434 3435 3436 3437 3438 3439 3440 3441 3442 3443 3444 3445 3446 3447 3448 3449 3450 3451 3452 3453 3454 3455 3456 3457 3458 3459 3460 3461 3462 3463 3464 3465 3466 3467 3468 3469 3470 3471 3472 3473 3474 3475 3476 | } for(ii=0; ii<pOrWc->nTerm; ii++){ WhereTerm *pOrTerm = &pOrWc->a[ii]; if( pOrTerm->leftCursor==iCur || (pOrTerm->eOperator & WO_AND)!=0 ){ WhereInfo *pSubWInfo; /* Info for single OR-term scan */ Expr *pOrExpr = pOrTerm->pExpr; int j1 = 0; /* Address of jump operation */ if( pAndExpr && !ExprHasProperty(pOrExpr, EP_FromJoin) ){ pAndExpr->pLeft = pOrExpr; pOrExpr = pAndExpr; } /* Loop through table entries that match term pOrTerm. */ pSubWInfo = sqlite3WhereBegin(pParse, pOrTab, pOrExpr, 0, 0, WHERE_OMIT_OPEN_CLOSE | WHERE_AND_ONLY | WHERE_FORCE_TABLE | WHERE_ONETABLE_ONLY, iCovCur); assert( pSubWInfo || pParse->nErr || db->mallocFailed ); if( pSubWInfo ){ WhereLoop *pSubLoop; explainOneScan( pParse, pOrTab, &pSubWInfo->a[0], iLevel, pLevel->iFrom, 0 ); if( (pWInfo->wctrlFlags & WHERE_DUPLICATES_OK)==0 ){ int r; int iSet = ((ii==pOrWc->nTerm-1)?-1:ii); if( HasRowid(pTab) ){ r = sqlite3ExprCodeGetColumn(pParse, pTab, -1, iCur, regRowid, 0); j1 = sqlite3VdbeAddOp4Int(v, OP_RowSetTest, regRowset, 0, r,iSet); VdbeCoverage(v); }else{ Index *pPk = sqlite3PrimaryKeyIndex(pTab); int nPk = pPk->nKeyCol; int iPk; /* Read the PK into an array of temp registers. */ r = sqlite3GetTempRange(pParse, nPk); for(iPk=0; iPk<nPk; iPk++){ int iCol = pPk->aiColumn[iPk]; sqlite3ExprCodeGetColumn(pParse, pTab, iCol, iCur, r+iPk, 0); } /* Check if the temp table already contains this key. If so, ** the row has already been included in the result set and ** can be ignored (by jumping past the Gosub below). Otherwise, ** insert the key into the temp table and proceed with processing ** the row. ** ** Use some of the same optimizations as OP_RowSetTest: If iSet ** is zero, assume that the key cannot already be present in ** the temp table. And if iSet is -1, assume that there is no ** need to insert the key into the temp table, as it will never ** be tested for. */ if( iSet ){ j1 = sqlite3VdbeAddOp4Int(v, OP_Found, regRowset, 0, r, nPk); VdbeCoverage(v); } if( iSet>=0 ){ sqlite3VdbeAddOp3(v, OP_MakeRecord, r, nPk, regRowid); sqlite3VdbeAddOp3(v, OP_IdxInsert, regRowset, regRowid, 0); if( iSet ) sqlite3VdbeChangeP5(v, OPFLAG_USESEEKRESULT); } /* Release the array of temp registers */ sqlite3ReleaseTempRange(pParse, r, nPk); } } sqlite3VdbeAddOp2(v, OP_Gosub, regReturn, iLoopBody); if( j1 ) sqlite3VdbeJumpHere(v, j1); /* The pSubWInfo->untestedTerms flag means that this OR term ** contained one or more AND term from a notReady table. The ** terms from the notReady table could not be tested and will ** need to be tested later. */ if( pSubWInfo->untestedTerms ) untestedTerms = 1; |
︙ | ︙ | |||
4762 4763 4764 4765 4766 4767 4768 | pWC = pBuilder->pWC; if( pWInfo->wctrlFlags & WHERE_AND_ONLY ) return SQLITE_OK; pWCEnd = pWC->a + pWC->nTerm; pNew = pBuilder->pNew; memset(&sSum, 0, sizeof(sSum)); pItem = pWInfo->pTabList->a + pNew->iTab; | < | 4812 4813 4814 4815 4816 4817 4818 4819 4820 4821 4822 4823 4824 4825 | pWC = pBuilder->pWC; if( pWInfo->wctrlFlags & WHERE_AND_ONLY ) return SQLITE_OK; pWCEnd = pWC->a + pWC->nTerm; pNew = pBuilder->pNew; memset(&sSum, 0, sizeof(sSum)); pItem = pWInfo->pTabList->a + pNew->iTab; iCur = pItem->iCursor; for(pTerm=pWC->a; pTerm<pWCEnd && rc==SQLITE_OK; pTerm++){ if( (pTerm->eOperator & WO_OR)!=0 && (pTerm->u.pOrInfo->indexable & pNew->maskSelf)!=0 ){ WhereClause * const pOrWC = &pTerm->u.pOrInfo->wc; |
︙ | ︙ |
Added test/whereI.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 | # 2014-03-31 # # 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. # #*********************************************************************** # The focus of this file is testing the OR optimization on WITHOUT ROWID # tables. # set testdir [file dirname $argv0] source $testdir/tester.tcl set ::testprefix whereI do_execsql_test 1.0 { CREATE TABLE t1(a, b, c, PRIMARY KEY(a)) WITHOUT ROWID; INSERT INTO t1 VALUES(1, 'a', 'z'); INSERT INTO t1 VALUES(2, 'b', 'y'); INSERT INTO t1 VALUES(3, 'c', 'x'); INSERT INTO t1 VALUES(4, 'd', 'w'); CREATE INDEX i1 ON t1(b); CREATE INDEX i2 ON t1(c); } do_eqp_test 1.1 { SELECT a FROM t1 WHERE b='b' OR c='x' } { 0 0 0 {SEARCH TABLE t1 USING INDEX i1 (b=?)} 0 0 0 {SEARCH TABLE t1 USING INDEX i2 (c=?)} } do_execsql_test 1.2 { SELECT a FROM t1 WHERE b='b' OR c='x' } {2 3} do_execsql_test 1.3 { SELECT a FROM t1 WHERE b='a' OR c='z' } {1} #---------------------------------------------------------------------- # Try that again, this time with non integer PRIMARY KEY values. # do_execsql_test 2.0 { CREATE TABLE t2(a, b, c, PRIMARY KEY(a)) WITHOUT ROWID; INSERT INTO t2 VALUES('i', 'a', 'z'); INSERT INTO t2 VALUES('ii', 'b', 'y'); INSERT INTO t2 VALUES('iii', 'c', 'x'); INSERT INTO t2 VALUES('iv', 'd', 'w'); CREATE INDEX i3 ON t2(b); CREATE INDEX i4 ON t2(c); } do_eqp_test 2.1 { SELECT a FROM t2 WHERE b='b' OR c='x' } { 0 0 0 {SEARCH TABLE t2 USING INDEX i3 (b=?)} 0 0 0 {SEARCH TABLE t2 USING INDEX i4 (c=?)} } do_execsql_test 2.2 { SELECT a FROM t2 WHERE b='b' OR c='x' } {ii iii} do_execsql_test 2.3 { SELECT a FROM t2 WHERE b='a' OR c='z' } {i} finish_test |