Many hyperlinks are disabled.
Use anonymous login
to enable hyperlinks.
Overview
Comment: | Make sure dependencies on the right-hand side of IN operators are checked correctly. Ticket #1433. (CVS 2706) |
---|---|
Downloads: | Tarball | ZIP archive |
Timelines: | family | ancestors | descendants | both | trunk |
Files: | files | file ages | folders |
SHA1: |
21740794ab81924442f358a6adbbe6d5 |
User & Date: | drh 2005-09-17 13:07:13.000 |
Context
2005-09-17
| ||
13:29 | Bug fix in the ORDER BY optimizer. Ticket #1435. (CVS 2707) (check-in: 553b7ba8f8 user: drh tags: trunk) | |
13:07 | Make sure dependencies on the right-hand side of IN operators are checked correctly. Ticket #1433. (CVS 2706) (check-in: 21740794ab user: drh tags: trunk) | |
02:34 | Updates to the FAQ. (CVS 2705) (check-in: 0eaf430d95 user: drh tags: trunk) | |
Changes
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.173 2005/09/17 13:07:13 drh Exp $ */ #include "sqliteInt.h" /* ** The number of bits in a Bitmask. "BMS" means "BitMask Size". */ #define BMS (sizeof(Bitmask)*8) |
︙ | ︙ | |||
299 300 301 302 303 304 305 | ** the header comment on that routine for additional information. ** The sqlite3ExprResolveNames() routines looks for column names and ** sets their opcodes to TK_COLUMN and their Expr.iTable fields to ** the VDBE cursor number of the table. This routine just has to ** translate the cursor numbers into bitmask values and OR all ** the bitmasks together. */ | | > < < | < < < < < > > > > > > > > > > > > > | 299 300 301 302 303 304 305 306 307 308 309 310 311 312 313 314 315 316 317 318 319 320 321 322 323 324 325 326 327 328 329 330 331 332 333 334 335 336 337 338 339 340 341 342 343 344 345 346 347 348 349 | ** the header comment on that routine for additional information. ** The sqlite3ExprResolveNames() routines looks for column names and ** sets their opcodes to TK_COLUMN and their Expr.iTable fields to ** the VDBE cursor number of the table. This routine just has to ** translate the cursor numbers into bitmask values and OR all ** the bitmasks together. */ static Bitmask exprListTableUsage(ExprMaskSet*, ExprList*); static Bitmask exprSelectTableUsage(ExprMaskSet*, Select*); static Bitmask exprTableUsage(ExprMaskSet *pMaskSet, Expr *p){ Bitmask mask = 0; if( p==0 ) return 0; if( p->op==TK_COLUMN ){ mask = getMask(pMaskSet, p->iTable); return mask; } mask = exprTableUsage(pMaskSet, p->pRight); mask |= exprTableUsage(pMaskSet, p->pLeft); mask |= exprListTableUsage(pMaskSet, p->pList); mask |= exprSelectTableUsage(pMaskSet, p->pSelect); return mask; } static Bitmask exprListTableUsage(ExprMaskSet *pMaskSet, ExprList *pList){ int i; Bitmask mask = 0; if( pList ){ for(i=0; i<pList->nExpr; i++){ mask |= exprTableUsage(pMaskSet, pList->a[i].pExpr); } } return mask; } static Bitmask exprSelectTableUsage(ExprMaskSet *pMaskSet, Select *pS){ Bitmask mask; if( pS==0 ){ mask = 0; }else{ mask = exprListTableUsage(pMaskSet, pS->pEList); mask |= exprListTableUsage(pMaskSet, pS->pGroupBy); mask |= exprListTableUsage(pMaskSet, pS->pOrderBy); mask |= exprTableUsage(pMaskSet, pS->pWhere); mask |= exprTableUsage(pMaskSet, pS->pHaving); } return mask; } /* ** Return TRUE if the given operator is one of the operators that is ** allowed for an indexable WHERE clause term. The allowed operators are ** "=", "<", ">", "<=", ">=", and "IN". */ |
︙ | ︙ | |||
538 539 540 541 542 543 544 | Bitmask prereqLeft; Bitmask prereqAll; int nPattern; int isComplete; if( sqlite3_malloc_failed ) return; prereqLeft = exprTableUsage(pMaskSet, pExpr->pLeft); | > > > > > | > > | 545 546 547 548 549 550 551 552 553 554 555 556 557 558 559 560 561 562 563 564 565 566 567 568 569 570 571 572 573 | Bitmask prereqLeft; Bitmask prereqAll; int nPattern; int isComplete; if( sqlite3_malloc_failed ) return; prereqLeft = exprTableUsage(pMaskSet, pExpr->pLeft); if( pExpr->op==TK_IN ){ assert( pExpr->pRight==0 ); pTerm->prereqRight = exprListTableUsage(pMaskSet, pExpr->pList) | exprSelectTableUsage(pMaskSet, pExpr->pSelect); }else{ pTerm->prereqRight = exprTableUsage(pMaskSet, pExpr->pRight); } pTerm->prereqAll = prereqAll = exprTableUsage(pMaskSet, pExpr); pTerm->leftCursor = -1; pTerm->iParent = -1; pTerm->operator = 0; if( allowedOp(pExpr->op) && (pTerm->prereqRight & prereqLeft)==0 ){ Expr *pLeft = pExpr->pLeft; Expr *pRight = pExpr->pRight; assert( prereqAll == (pTerm->prereqRight | prereqLeft) ); /* ticket 1433 */ if( pLeft->op==TK_COLUMN ){ pTerm->leftCursor = pLeft->iTable; pTerm->leftColumn = pLeft->iColumn; pTerm->operator = operatorMask(pExpr->op); } if( pRight && pRight->op==TK_COLUMN ){ WhereTerm *pNew; |
︙ | ︙ | |||
604 605 606 607 608 609 610 | } pTerm->nChild = 2; } #endif /* SQLITE_OMIT_BETWEEN_OPTIMIZATION */ #ifndef SQLITE_OMIT_OR_OPTIMIZATION /* Attempt to convert OR-connected terms into an IN operator so that | | > > > > > > | 618 619 620 621 622 623 624 625 626 627 628 629 630 631 632 633 634 635 636 637 638 | } pTerm->nChild = 2; } #endif /* SQLITE_OMIT_BETWEEN_OPTIMIZATION */ #ifndef SQLITE_OMIT_OR_OPTIMIZATION /* Attempt to convert OR-connected terms into an IN operator so that ** they can make use of indices. Example: ** ** x = expr1 OR expr2 = x OR x = expr3 ** ** is converted into ** ** x IN (expr1,expr2,expr3) */ else if( pExpr->op==TK_OR ){ int ok; int i, j; int iColumn, iCursor; WhereClause sOr; WhereTerm *pOrTerm; |
︙ | ︙ |
Added test/tkt1443.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 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 135 136 137 138 139 140 141 142 143 144 145 146 147 148 149 150 151 152 153 154 155 156 157 158 159 160 161 162 163 164 165 166 167 168 169 170 | # 2005 September 17 # # 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. # #*********************************************************************** # This file implements regression tests for SQLite library. # # This file implements tests to verify that ticket #1433 has been # fixed. # # The problem in ticket #1433 was that the dependencies on the right-hand # side of an IN operator were not being checked correctly. So in an # expression of the form: # # t1.x IN (1,t2.b,3) # # the optimizer was missing the fact that the right-hand side of the IN # depended on table t2. It was checking dependencies based on the # Expr.pRight field rather than Expr.pList and Expr.pSelect. # # Such a bug could be verifed using a less elaborate test case. But # this test case (from the original bug poster) exercises so many different # parts of the system all at once, that it seemed like a good one to # include in the test suite. # # $Id: tkt1443.test,v 1.1 2005/09/17 13:07:13 drh Exp $ set testdir [file dirname $argv0] source $testdir/tester.tcl # Construct the sample database. # do_test tkt1433-1.0 { sqlite3 db :memory: execsql { CREATE TABLE Items( itemId integer primary key, item str unique ); INSERT INTO "Items" VALUES(0, 'ALL'); INSERT INTO "Items" VALUES(1, 'double:source'); INSERT INTO "Items" VALUES(2, 'double'); INSERT INTO "Items" VALUES(3, 'double:runtime'); INSERT INTO "Items" VALUES(4, '.*:runtime'); CREATE TABLE Labels( labelId INTEGER PRIMARY KEY, label STR UNIQUE ); INSERT INTO "Labels" VALUES(0, 'ALL'); INSERT INTO "Labels" VALUES(1, 'localhost@rpl:linux'); INSERT INTO "Labels" VALUES(2, 'localhost@rpl:branch'); CREATE TABLE LabelMap( itemId INTEGER, labelId INTEGER, branchId integer ); INSERT INTO "LabelMap" VALUES(1, 1, 1); INSERT INTO "LabelMap" VALUES(2, 1, 1); INSERT INTO "LabelMap" VALUES(3, 1, 1); INSERT INTO "LabelMap" VALUES(1, 2, 2); INSERT INTO "LabelMap" VALUES(2, 2, 3); INSERT INTO "LabelMap" VALUES(3, 2, 3); CREATE TABLE Users ( userId INTEGER PRIMARY KEY, user STRING UNIQUE, salt BINARY, password STRING ); INSERT INTO "Users" VALUES(1, 'test', 'æ$d', '43ba0f45014306bd6df529551ffdb3df'); INSERT INTO "Users" VALUES(2, 'limited', 'ª>S', 'cf07c8348fdf675cc1f7696b7d45191b'); CREATE TABLE UserGroups ( userGroupId INTEGER PRIMARY KEY, userGroup STRING UNIQUE ); INSERT INTO "UserGroups" VALUES(1, 'test'); INSERT INTO "UserGroups" VALUES(2, 'limited'); CREATE TABLE UserGroupMembers ( userGroupId INTEGER, userId INTEGER ); INSERT INTO "UserGroupMembers" VALUES(1, 1); INSERT INTO "UserGroupMembers" VALUES(2, 2); CREATE TABLE Permissions ( userGroupId INTEGER, labelId INTEGER NOT NULL, itemId INTEGER NOT NULL, write INTEGER, capped INTEGER, admin INTEGER ); INSERT INTO "Permissions" VALUES(1, 0, 0, 1, 0, 1); INSERT INTO "Permissions" VALUES(2, 2, 4, 0, 0, 0); } } {} # Run the query with an index # do_test tkt1443-1.1 { execsql { select distinct Items.Item as trove, UP.pattern as pattern from ( select Permissions.labelId as labelId, PerItems.item as pattern from Users, UserGroupMembers, Permissions left outer join Items as PerItems on Permissions.itemId = PerItems.itemId where Users.user = 'limited' and Users.userId = UserGroupMembers.userId and UserGroupMembers.userGroupId = Permissions.userGroupId ) as UP join LabelMap on ( UP.labelId = 0 or UP.labelId = LabelMap.labelId ), Labels, Items where Labels.label = 'localhost@rpl:branch' and Labels.labelId = LabelMap.labelId and LabelMap.itemId = Items.itemId ORDER BY +trove, +pattern } } {double .*:runtime double:runtime .*:runtime double:source .*:runtime} # Create an index and rerun the query. # Verify that the results are the same # do_test tkt1443-1.2 { execsql { CREATE UNIQUE INDEX PermissionsIdx ON Permissions(userGroupId, labelId, itemId); select distinct Items.Item as trove, UP.pattern as pattern from ( select Permissions.labelId as labelId, PerItems.item as pattern from Users, UserGroupMembers, Permissions left outer join Items as PerItems on Permissions.itemId = PerItems.itemId where Users.user = 'limited' and Users.userId = UserGroupMembers.userId and UserGroupMembers.userGroupId = Permissions.userGroupId ) as UP join LabelMap on ( UP.labelId = 0 or UP.labelId = LabelMap.labelId ), Labels, Items where Labels.label = 'localhost@rpl:branch' and Labels.labelId = LabelMap.labelId and LabelMap.itemId = Items.itemId ORDER BY +trove, +pattern } } {double .*:runtime double:runtime .*:runtime double:source .*:runtime} finish_test |