SQLite

Check-in [21740794ab]
Login

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: 21740794ab81924442f358a6adbbe6d5590cf58d
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
Unified Diff Ignore Whitespace Patch
Changes to src/where.c.
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.172 2005/09/16 02:38:11 drh Exp $
*/
#include "sqliteInt.h"

/*
** The number of bits in a Bitmask.  "BMS" means "BitMask Size".
*/
#define BMS  (sizeof(Bitmask)*8)







|







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
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
** 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 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);
  if( p->pSelect ){
    Select *pS = p->pSelect;
    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;
}
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;













}

/*
** 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".
*/







|
>










<
<
|
<
<
<
<
<











>
>
>
>
>
>
>
>
>
>
>
>
>







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





545

546
547
548
549
550
551
552

553
554
555
556
557
558
559
  Bitmask prereqLeft;
  Bitmask prereqAll;
  int nPattern;
  int isComplete;

  if( sqlite3_malloc_failed ) return;
  prereqLeft = exprTableUsage(pMaskSet, pExpr->pLeft);





  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;

    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;







>
>
>
>
>
|
>







>







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
611






612
613
614
615
616
617
618
    }
    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.






  */
  else if( pExpr->op==TK_OR ){
    int ok;
    int i, j;
    int iColumn, iCursor;
    WhereClause sOr;
    WhereTerm *pOrTerm;







|
>
>
>
>
>
>







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