SQLite

Check-in [b16541ba5e]
Login

Many hyperlinks are disabled.
Use anonymous login to enable hyperlinks.

Overview
Comment:Correctly handle multi-column indices where multiple columns are constrained by IN operators with subqueries on the right-hand side. Ticket #1807. (CVS 3184)
Downloads: Tarball | ZIP archive
Timelines: family | ancestors | descendants | both | trunk
Files: files | file ages | folders
SHA1: b16541ba5e6a9514f9f317888117c68b6818f9cb
User & Date: drh 2006-05-11 13:26:26.000
Context
2006-05-11
13:33
Fix documentation typo: The name of the competing database engine is "Firebird", not "Firefox". (CVS 3185) (check-in: 8be6a39d71 user: drh tags: trunk)
13:26
Correctly handle multi-column indices where multiple columns are constrained by IN operators with subqueries on the right-hand side. Ticket #1807. (CVS 3184) (check-in: b16541ba5e user: drh tags: trunk)
13:25
Fix comments on the implementation of the SUM() function. (CVS 3183) (check-in: a8909f3e5f 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.207 2006/04/21 09:38:37 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.208 2006/05/11 13:26:26 drh Exp $
*/
#include "sqliteInt.h"

/*
** The number of bits in a Bitmask.  "BMS" means "BitMask Size".
*/
#define BMS  (sizeof(Bitmask)*8)
︙︙
1030
1031
1032
1033
1034
1035
1036
1037
1038
1039
1040
1041
1042
1043
1044

      pTerm = findTerm(pWC, iCur, j, notReady, WO_EQ|WO_IN, pProbe);
      if( pTerm==0 ) break;
      flags |= WHERE_COLUMN_EQ;
      if( pTerm->eOperator & WO_IN ){
        Expr *pExpr = pTerm->pExpr;
        flags |= WHERE_COLUMN_IN;
        if( pExpr->pSelect!=0 ){
          inMultiplier *= 100;
        }else if( pExpr->pList!=0 ){
          inMultiplier *= pExpr->pList->nExpr + 1;
        }
      }
    }
    cost = pProbe->aiRowEst[i] * inMultiplier * estLog(inMultiplier);
    nEq = i;








|








1030
1031
1032
1033
1034
1035
1036
1037
1038
1039
1040
1041
1042
1043
1044

      pTerm = findTerm(pWC, iCur, j, notReady, WO_EQ|WO_IN, pProbe);
      if( pTerm==0 ) break;
      flags |= WHERE_COLUMN_EQ;
      if( pTerm->eOperator & WO_IN ){
        Expr *pExpr = pTerm->pExpr;
        flags |= WHERE_COLUMN_IN;
        if( pExpr->pSelect!=0 ){
          inMultiplier *= 25;
        }else if( pExpr->pList!=0 ){
          inMultiplier *= pExpr->pList->nExpr + 1;
        }
      }
    }
    cost = pProbe->aiRowEst[i] * inMultiplier * estLog(inMultiplier);
    nEq = i;
︙︙
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

  }else{
    int iTab;
    int *aIn;
    Vdbe *v = pParse->pVdbe;

    sqlite3CodeSubselect(pParse, pX);
    iTab = pX->iTable;
    sqlite3VdbeAddOp(v, OP_Rewind, iTab, brk);
    VdbeComment((v, "# %.*s", pX->span.n, pX->span.z));
    pLevel->nIn++;
    sqliteReallocOrFree((void**)&pLevel->aInLoop,
                                 sizeof(pLevel->aInLoop[0])*3*pLevel->nIn);
    aIn = pLevel->aInLoop;
    if( aIn ){
      aIn += pLevel->nIn*3 - 3;
      aIn[0] = OP_Next;
      aIn[1] = iTab;
      aIn[2] = sqlite3VdbeAddOp(v, OP_Column, iTab, 0);
    }else{
      pLevel->nIn = 0;
    }
#endif
  }
  disableTerm(pLevel, pTerm);
}








|



|


|
|
<
|








1220
1221
1222
1223
1224
1225
1226
1227
1228
1229
1230
1231
1232
1233
1234
1235

1236
1237
1238
1239
1240
1241
1242
1243

  }else{
    int iTab;
    int *aIn;
    Vdbe *v = pParse->pVdbe;

    sqlite3CodeSubselect(pParse, pX);
    iTab = pX->iTable;
    sqlite3VdbeAddOp(v, OP_Rewind, iTab, 0);
    VdbeComment((v, "# %.*s", pX->span.n, pX->span.z));
    pLevel->nIn++;
    sqliteReallocOrFree((void**)&pLevel->aInLoop,
                                 sizeof(pLevel->aInLoop[0])*2*pLevel->nIn);
    aIn = pLevel->aInLoop;
    if( aIn ){
      aIn += pLevel->nIn*2 - 2;
      aIn[0] = iTab;

      aIn[1] = sqlite3VdbeAddOp(v, OP_Column, iTab, 0);
    }else{
      pLevel->nIn = 0;
    }
#endif
  }
  disableTerm(pLevel, pTerm);
}
︙︙
2055
2056
2057
2058
2059
2060
2061
2062
2063

2064
2065
2066
2067
2068
2069
2070

    if( pLevel->op!=OP_Noop ){
      sqlite3VdbeAddOp(v, pLevel->op, pLevel->p1, pLevel->p2);
    }
    sqlite3VdbeResolveLabel(v, pLevel->brk);
    if( pLevel->nIn ){
      int *a;
      int j;
      for(j=pLevel->nIn, a=&pLevel->aInLoop[j*3-3]; j>0; j--, a-=3){
        sqlite3VdbeAddOp(v, a[0], a[1], a[2]);

      }
      sqliteFree(pLevel->aInLoop);
    }
    if( pLevel->iLeftJoin ){
      int addr;
      addr = sqlite3VdbeAddOp(v, OP_IfMemPos, pLevel->iLeftJoin, 0);
      sqlite3VdbeAddOp(v, OP_NullRow, pTabList->a[i].iCursor, 0);








|
|
>








2054
2055
2056
2057
2058
2059
2060
2061
2062
2063
2064
2065
2066
2067
2068
2069
2070

    if( pLevel->op!=OP_Noop ){
      sqlite3VdbeAddOp(v, pLevel->op, pLevel->p1, pLevel->p2);
    }
    sqlite3VdbeResolveLabel(v, pLevel->brk);
    if( pLevel->nIn ){
      int *a;
      int j;
      for(j=pLevel->nIn, a=&pLevel->aInLoop[j*2-2]; j>0; j--, a-=2){
        sqlite3VdbeAddOp(v, OP_Next, a[0], a[1]);
        sqlite3VdbeJumpHere(v, a[1]-1);
      }
      sqliteFree(pLevel->aInLoop);
    }
    if( pLevel->iLeftJoin ){
      int addr;
      addr = sqlite3VdbeAddOp(v, OP_IfMemPos, pLevel->iLeftJoin, 0);
      sqlite3VdbeAddOp(v, OP_NullRow, pTabList->a[i].iCursor, 0);
︙︙
Changes to test/where2.test.
︙︙
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22

#    May you share freely, never taking more than you give.
#
#***********************************************************************
# This file implements regression tests for SQLite library.  The
# focus of this file is testing the use of indices in WHERE clauses
# based on recent changes to the optimizer.
#
# $Id: where2.test,v 1.8 2006/01/17 09:35:03 danielk1977 Exp $

set testdir [file dirname $argv0]
source $testdir/tester.tcl

# Build some test data
#
do_test where2-1.0 {








|








8
9
10
11
12
13
14
15
16
17
18
19
20
21
22

#    May you share freely, never taking more than you give.
#
#***********************************************************************
# This file implements regression tests for SQLite library.  The
# focus of this file is testing the use of indices in WHERE clauses
# based on recent changes to the optimizer.
#
# $Id: where2.test,v 1.9 2006/05/11 13:26:26 drh Exp $

set testdir [file dirname $argv0]
source $testdir/tester.tcl

# Build some test data
#
do_test where2-1.0 {
︙︙
287
288
289
290
291
292
293
































































































































































294

do_test where2-7.4 {
  cksort {
    create unique index i9y on t9(y);
    select * from t8, t9 where a=1 and y=3 order by b, x
  }
} {1 2 3 2 3 nosort}

































































































































































finish_test








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


287
288
289
290
291
292
293
294
295
296
297
298
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
350
351
352
353
354
355
356
357
358
359
360
361
362
363
364
365
366
367
368
369
370
371
372
373
374
375
376
377
378
379
380
381
382
383
384
385
386
387
388
389
390
391
392
393
394
395
396
397
398
399
400
401
402
403
404
405
406
407
408
409
410
411
412
413
414
415
416
417
418
419
420
421
422
423
424
425
426
427
428
429
430
431
432
433
434
435
436
437
438
439
440
441
442
443
444
445
446
447
448
449
450
451
452
453
454

do_test where2-7.4 {
  cksort {
    create unique index i9y on t9(y);
    select * from t8, t9 where a=1 and y=3 order by b, x
  }
} {1 2 3 2 3 nosort}

# Ticket #1807.  Using IN constrains on multiple columns of
# a multi-column index.
#
ifcapable subquery {
  do_test where2-8.1 {
    execsql {
      SELECT * FROM t1 WHERE x IN (20,21) AND y IN (1,2)
    }
  } {}
  do_test where2-8.2 {
    execsql {
      SELECT * FROM t1 WHERE x IN (1,2) AND y IN (-5,-6)
    }
  } {}
  execsql {CREATE TABLE tx AS SELECT * FROM t1}
  do_test where2-8.3 {
    execsql {
      SELECT w FROM t1
       WHERE x IN (SELECT x FROM tx WHERE rowid<0)
         AND +y IN (SELECT y FROM tx WHERE rowid=1)
    }
  } {}
  do_test where2-8.4 {
    execsql {
      SELECT w FROM t1
       WHERE x IN (SELECT x FROM tx WHERE rowid=1)
         AND y IN (SELECT y FROM tx WHERE rowid<0)
    }
  } {}
  #set sqlite_where_trace 1
  do_test where2-8.5 {
    execsql {
      CREATE INDEX tx_xyz ON tx(x, y, z, w);
      SELECT w FROM tx
       WHERE x IN (SELECT x FROM t1 WHERE w BETWEEN 10 AND 20)
         AND y IN (SELECT y FROM t1 WHERE w BETWEEN 10 AND 20)
         AND z IN (SELECT z FROM t1 WHERE w BETWEEN 12 AND 14)
    }
  } {12 13 14}
  do_test where2-8.6 {
    execsql {
      SELECT w FROM tx
       WHERE x IN (SELECT x FROM t1 WHERE w BETWEEN 10 AND 20)
         AND y IN (SELECT y FROM t1 WHERE w BETWEEN 12 AND 14)
         AND z IN (SELECT z FROM t1 WHERE w BETWEEN 10 AND 20)
    }
  } {12 13 14}
  do_test where2-8.7 {
    execsql {
      SELECT w FROM tx
       WHERE x IN (SELECT x FROM t1 WHERE w BETWEEN 12 AND 14)
         AND y IN (SELECT y FROM t1 WHERE w BETWEEN 10 AND 20)
         AND z IN (SELECT z FROM t1 WHERE w BETWEEN 10 AND 20)
    }
  } {10 11 12 13 14 15}
  do_test where2-8.8 {
    execsql {
      SELECT w FROM tx
       WHERE x IN (SELECT x FROM t1 WHERE w BETWEEN 10 AND 20)
         AND y IN (SELECT y FROM t1 WHERE w BETWEEN 10 AND 20)
         AND z IN (SELECT z FROM t1 WHERE w BETWEEN 10 AND 20)
    }
  } {10 11 12 13 14 15 16 17 18 19 20}
  do_test where2-8.9 {
    execsql {
      SELECT w FROM tx
       WHERE x IN (SELECT x FROM t1 WHERE w BETWEEN 10 AND 20)
         AND y IN (SELECT y FROM t1 WHERE w BETWEEN 10 AND 20)
         AND z IN (SELECT z FROM t1 WHERE w BETWEEN 2 AND 4)
    }
  } {}
  do_test where2-8.10 {
    execsql {
      SELECT w FROM tx
       WHERE x IN (SELECT x FROM t1 WHERE w BETWEEN 10 AND 20)
         AND y IN (SELECT y FROM t1 WHERE w BETWEEN 2 AND 4)
         AND z IN (SELECT z FROM t1 WHERE w BETWEEN 10 AND 20)
    }
  } {}
  do_test where2-8.11 {
    execsql {
      SELECT w FROM tx
       WHERE x IN (SELECT x FROM t1 WHERE w BETWEEN 2 AND 4)
         AND y IN (SELECT y FROM t1 WHERE w BETWEEN 10 AND 20)
         AND z IN (SELECT z FROM t1 WHERE w BETWEEN 10 AND 20)
    }
  } {}
  do_test where2-8.12 {
    execsql {
      SELECT w FROM tx
       WHERE x IN (SELECT x FROM t1 WHERE w BETWEEN 10 AND 20)
         AND y IN (SELECT y FROM t1 WHERE w BETWEEN 10 AND 20)
         AND z IN (SELECT z FROM t1 WHERE w BETWEEN -4 AND -2)
    }
  } {}
  do_test where2-8.13 {
    execsql {
      SELECT w FROM tx
       WHERE x IN (SELECT x FROM t1 WHERE w BETWEEN 10 AND 20)
         AND y IN (SELECT y FROM t1 WHERE w BETWEEN -4 AND -2)
         AND z IN (SELECT z FROM t1 WHERE w BETWEEN 10 AND 20)
    }
  } {}
  do_test where2-8.14 {
    execsql {
      SELECT w FROM tx
       WHERE x IN (SELECT x FROM t1 WHERE w BETWEEN -4 AND -2)
         AND y IN (SELECT y FROM t1 WHERE w BETWEEN 10 AND 20)
         AND z IN (SELECT z FROM t1 WHERE w BETWEEN 10 AND 20)
    }
  } {}
  do_test where2-8.15 {
    execsql {
      SELECT w FROM tx
       WHERE x IN (SELECT x FROM t1 WHERE w BETWEEN 10 AND 20)
         AND y IN (SELECT y FROM t1 WHERE w BETWEEN 10 AND 20)
         AND z IN (SELECT z FROM t1 WHERE w BETWEEN 200 AND 300)
    }
  } {}
  do_test where2-8.16 {
    execsql {
      SELECT w FROM tx
       WHERE x IN (SELECT x FROM t1 WHERE w BETWEEN 10 AND 20)
         AND y IN (SELECT y FROM t1 WHERE w BETWEEN 200 AND 300)
         AND z IN (SELECT z FROM t1 WHERE w BETWEEN 10 AND 20)
    }
  } {}
  do_test where2-8.17 {
    execsql {
      SELECT w FROM tx
       WHERE x IN (SELECT x FROM t1 WHERE w BETWEEN 200 AND 300)
         AND y IN (SELECT y FROM t1 WHERE w BETWEEN 10 AND 20)
         AND z IN (SELECT z FROM t1 WHERE w BETWEEN 10 AND 20)
    }
  } {}
  do_test where2-8.18 {
    execsql {
      SELECT w FROM tx
       WHERE x IN (SELECT x FROM t1 WHERE +w BETWEEN 10 AND 20)
         AND y IN (SELECT y FROM t1 WHERE +w BETWEEN 10 AND 20)
         AND z IN (SELECT z FROM t1 WHERE +w BETWEEN 200 AND 300)
    }
  } {}
  do_test where2-8.19 {
    execsql {
      SELECT w FROM tx
       WHERE x IN (SELECT x FROM t1 WHERE +w BETWEEN 10 AND 20)
         AND y IN (SELECT y FROM t1 WHERE +w BETWEEN 200 AND 300)
         AND z IN (SELECT z FROM t1 WHERE +w BETWEEN 10 AND 20)
    }
  } {}
  do_test where2-8.20 {
    execsql {
      SELECT w FROM tx
       WHERE x IN (SELECT x FROM t1 WHERE +w BETWEEN 200 AND 300)
         AND y IN (SELECT y FROM t1 WHERE +w BETWEEN 10 AND 20)
         AND z IN (SELECT z FROM t1 WHERE +w BETWEEN 10 AND 20)
    }
  } {}
}  
finish_test