SQLite

Check-in [c10a1b99]
Login

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

Overview
Comment:Show the creation of IN-operator Bloom filters in the EXPLAIN QUERY PLAN output.
Downloads: Tarball | ZIP archive | SQL archive
Timelines: family | ancestors | descendants | both | in-bloom
Files: files | file ages | folders
SHA3-256: c10a1b99d47a4c93bdb16e646f6a21add570d6dbb34fd91a32f8abacdb28712b
User & Date: drh 2024-07-03 20:10:42
Context
2024-07-03
20:19
When constructing an ephermeral table to use as the right-hand side of an IN operator, also construct a Bloom filter to speed membership testing. (check-in: baa83b46 user: drh tags: trunk)
20:10
Show the creation of IN-operator Bloom filters in the EXPLAIN QUERY PLAN output. (Closed-Leaf check-in: c10a1b99 user: drh tags: in-bloom)
18:56
Add a new sqlite3FaultSim() call to OP_NotFound to use for testing purposes. (check-in: 84fd275b user: drh tags: in-bloom)
Changes
Hide Diffs Unified Diffs Ignore Whitespace Patch

Changes to src/select.c.

1383
1384
1385
1386
1387
1388
1389

1390
1391
1392
1393
1394
1395
1396
        assert( sqlite3Strlen30(pDest->zAffSdst)==nResultCol );
        sqlite3VdbeAddOp4(v, OP_MakeRecord, regResult, nResultCol,
            r1, pDest->zAffSdst, nResultCol);
        sqlite3VdbeAddOp4Int(v, OP_IdxInsert, iParm, r1, regResult, nResultCol);
        if( pDest->iSDParm2 ){
          sqlite3VdbeAddOp4Int(v, OP_FilterAdd, pDest->iSDParm2, 0,
                               regResult, nResultCol);

        }
        sqlite3ReleaseTempReg(pParse, r1);
      }
      break;
    }









>







1383
1384
1385
1386
1387
1388
1389
1390
1391
1392
1393
1394
1395
1396
1397
        assert( sqlite3Strlen30(pDest->zAffSdst)==nResultCol );
        sqlite3VdbeAddOp4(v, OP_MakeRecord, regResult, nResultCol,
            r1, pDest->zAffSdst, nResultCol);
        sqlite3VdbeAddOp4Int(v, OP_IdxInsert, iParm, r1, regResult, nResultCol);
        if( pDest->iSDParm2 ){
          sqlite3VdbeAddOp4Int(v, OP_FilterAdd, pDest->iSDParm2, 0,
                               regResult, nResultCol);
          ExplainQueryPlan((pParse, 0, "CREATE BLOOM FILTER"));
        }
        sqlite3ReleaseTempReg(pParse, r1);
      }
      break;
    }


3320
3321
3322
3323
3324
3325
3326

3327
3328
3329
3330
3331
3332
3333
      sqlite3VdbeAddOp4(v, OP_MakeRecord, pIn->iSdst, pIn->nSdst,
          r1, pDest->zAffSdst, pIn->nSdst);
      sqlite3VdbeAddOp4Int(v, OP_IdxInsert, pDest->iSDParm, r1,
                           pIn->iSdst, pIn->nSdst);
      if( pDest->iSDParm2>0 ){
        sqlite3VdbeAddOp4Int(v, OP_FilterAdd, pDest->iSDParm2, 0,
                             pIn->iSdst, pIn->nSdst);

      }
      sqlite3ReleaseTempReg(pParse, r1);
      break;
    }

    /* If this is a scalar select that is part of an expression, then
    ** store the results in the appropriate memory cell and break out







>







3321
3322
3323
3324
3325
3326
3327
3328
3329
3330
3331
3332
3333
3334
3335
      sqlite3VdbeAddOp4(v, OP_MakeRecord, pIn->iSdst, pIn->nSdst,
          r1, pDest->zAffSdst, pIn->nSdst);
      sqlite3VdbeAddOp4Int(v, OP_IdxInsert, pDest->iSDParm, r1,
                           pIn->iSdst, pIn->nSdst);
      if( pDest->iSDParm2>0 ){
        sqlite3VdbeAddOp4Int(v, OP_FilterAdd, pDest->iSDParm2, 0,
                             pIn->iSdst, pIn->nSdst);
        ExplainQueryPlan((pParse, 0, "CREATE BLOOM FILTER"));
      }
      sqlite3ReleaseTempReg(pParse, r1);
      break;
    }

    /* If this is a scalar select that is part of an expression, then
    ** store the results in the appropriate memory cell and break out

Changes to test/autoindex1.test.

181
182
183
184
185
186
187
188

189
190
191
192
193
194
195
do_eqp_test autoindex1-500.1 {
  SELECT b FROM t501
   WHERE t501.a IN (SELECT x FROM t502 WHERE y=?);
} {
  QUERY PLAN
  |--SEARCH t501 USING INTEGER PRIMARY KEY (rowid=?)
  `--LIST SUBQUERY xxxxxx
     `--SCAN t502

}
do_eqp_test autoindex1-501 {
  SELECT b FROM t501
   WHERE t501.a IN (SELECT x FROM t502 WHERE y=t501.b);
} {
  QUERY PLAN
  |--SCAN t501







|
>







181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
do_eqp_test autoindex1-500.1 {
  SELECT b FROM t501
   WHERE t501.a IN (SELECT x FROM t502 WHERE y=?);
} {
  QUERY PLAN
  |--SEARCH t501 USING INTEGER PRIMARY KEY (rowid=?)
  `--LIST SUBQUERY xxxxxx
     |--SCAN t502
     `--CREATE BLOOM FILTER
}
do_eqp_test autoindex1-501 {
  SELECT b FROM t501
   WHERE t501.a IN (SELECT x FROM t502 WHERE y=t501.b);
} {
  QUERY PLAN
  |--SCAN t501

Changes to test/eqp.test.

307
308
309
310
311
312
313
314

315
316
317
318
319
320
321

det 3.3.1 {
  SELECT * FROM t1 WHERE y IN (SELECT y FROM t2)
} {
  QUERY PLAN
  |--SCAN t1
  `--LIST SUBQUERY xxxxxx
     `--SCAN t2

}
det 3.3.2 {
  SELECT * FROM t1 WHERE y IN (SELECT y FROM t2 WHERE t1.x!=t2.x)
} {
  QUERY PLAN
  |--SCAN t1
  `--CORRELATED LIST SUBQUERY xxxxxx







|
>







307
308
309
310
311
312
313
314
315
316
317
318
319
320
321
322

det 3.3.1 {
  SELECT * FROM t1 WHERE y IN (SELECT y FROM t2)
} {
  QUERY PLAN
  |--SCAN t1
  `--LIST SUBQUERY xxxxxx
     |--SCAN t2
     `--CREATE BLOOM FILTER
}
det 3.3.2 {
  SELECT * FROM t1 WHERE y IN (SELECT y FROM t2 WHERE t1.x!=t2.x)
} {
  QUERY PLAN
  |--SCAN t1
  `--CORRELATED LIST SUBQUERY xxxxxx

Changes to test/pushdown.test.

271
272
273
274
275
276
277
278

279
280
281
282

283
284
285

286
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
  |--CO-ROUTINE t0
  |  `--COMPOUND QUERY
  |     |--LEFT-MOST SUBQUERY
  |     |  |--SEARCH t01 USING INDEX t01x (w=? AND x=? AND y>? AND y<?)
  |     |  `--LIST SUBQUERY xxxxxx
  |     |     |--MATERIALIZE k
  |     |     |  `--SCAN 3 CONSTANT ROWS
  |     |     `--SCAN k

  |     `--UNION ALL
  |        |--SEARCH t02 USING INDEX t02x (w=? AND x=? AND y>? AND y<?)
  |        `--LIST SUBQUERY xxxxxx
  |           `--SCAN k

  |--SEARCH t0
  `--LIST SUBQUERY xxxxxx
     `--SCAN k

}
# ^^^^--- The key feature above is that the SEARCH for each subquery
# uses all three fields of the index w, x, and y.  Prior to the push-down
# of "expr IN table", only the w term of the index would be used.  Similar
# for the following tests:
#
do_eqp_test 6.2 {
  SELECT max(z) FROM t0 WHERE w=123 AND x IN v1 AND y BETWEEN 44 AND 55;
} {
  QUERY PLAN
  |--CO-ROUTINE t0
  |  `--COMPOUND QUERY
  |     |--LEFT-MOST SUBQUERY
  |     |  |--SEARCH t01 USING INDEX t01x (w=? AND x=? AND y>? AND y<?)
  |     |  `--LIST SUBQUERY xxxxxx
  |     |     |--CO-ROUTINE v1
  |     |     |  `--SCAN 3 CONSTANT ROWS
  |     |     `--SCAN v1

  |     `--UNION ALL
  |        |--SEARCH t02 USING INDEX t02x (w=? AND x=? AND y>? AND y<?)
  |        `--LIST SUBQUERY xxxxxx
  |           |--CO-ROUTINE v1
  |           |  `--SCAN 3 CONSTANT ROWS
  |           `--SCAN v1

  |--SEARCH t0
  `--LIST SUBQUERY xxxxxx
     |--CO-ROUTINE v1
     |  `--SCAN 3 CONSTANT ROWS
     `--SCAN v1

}
do_eqp_test 6.3 {
  SELECT max(z) FROM t0 WHERE w=123 AND x IN k1 AND y BETWEEN 44 AND 55;
} {
  QUERY PLAN
  |--CO-ROUTINE t0
  |  `--COMPOUND QUERY
  |     |--LEFT-MOST SUBQUERY
  |     |  |--SEARCH t01 USING INDEX t01x (w=? AND x=? AND y>? AND y<?)
  |     |  `--LIST SUBQUERY xxxxxx
  |     |     `--SCAN k1

  |     `--UNION ALL
  |        |--SEARCH t02 USING INDEX t02x (w=? AND x=? AND y>? AND y<?)
  |        `--LIST SUBQUERY xxxxxx
  |           `--SCAN k1

  |--SEARCH t0
  `--LIST SUBQUERY xxxxxx
     `--SCAN k1

}

finish_test







|
>



|
>


|
>

















|
>





|
>




|
>










|
>



|
>


|
>



271
272
273
274
275
276
277
278
279
280
281
282
283
284
285
286
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
  |--CO-ROUTINE t0
  |  `--COMPOUND QUERY
  |     |--LEFT-MOST SUBQUERY
  |     |  |--SEARCH t01 USING INDEX t01x (w=? AND x=? AND y>? AND y<?)
  |     |  `--LIST SUBQUERY xxxxxx
  |     |     |--MATERIALIZE k
  |     |     |  `--SCAN 3 CONSTANT ROWS
  |     |     |--SCAN k
  |     |     `--CREATE BLOOM FILTER
  |     `--UNION ALL
  |        |--SEARCH t02 USING INDEX t02x (w=? AND x=? AND y>? AND y<?)
  |        `--LIST SUBQUERY xxxxxx
  |           |--SCAN k
  |           `--CREATE BLOOM FILTER
  |--SEARCH t0
  `--LIST SUBQUERY xxxxxx
     |--SCAN k
     `--CREATE BLOOM FILTER
}
# ^^^^--- The key feature above is that the SEARCH for each subquery
# uses all three fields of the index w, x, and y.  Prior to the push-down
# of "expr IN table", only the w term of the index would be used.  Similar
# for the following tests:
#
do_eqp_test 6.2 {
  SELECT max(z) FROM t0 WHERE w=123 AND x IN v1 AND y BETWEEN 44 AND 55;
} {
  QUERY PLAN
  |--CO-ROUTINE t0
  |  `--COMPOUND QUERY
  |     |--LEFT-MOST SUBQUERY
  |     |  |--SEARCH t01 USING INDEX t01x (w=? AND x=? AND y>? AND y<?)
  |     |  `--LIST SUBQUERY xxxxxx
  |     |     |--CO-ROUTINE v1
  |     |     |  `--SCAN 3 CONSTANT ROWS
  |     |     |--SCAN v1
  |     |     `--CREATE BLOOM FILTER
  |     `--UNION ALL
  |        |--SEARCH t02 USING INDEX t02x (w=? AND x=? AND y>? AND y<?)
  |        `--LIST SUBQUERY xxxxxx
  |           |--CO-ROUTINE v1
  |           |  `--SCAN 3 CONSTANT ROWS
  |           |--SCAN v1
  |           `--CREATE BLOOM FILTER
  |--SEARCH t0
  `--LIST SUBQUERY xxxxxx
     |--CO-ROUTINE v1
     |  `--SCAN 3 CONSTANT ROWS
     |--SCAN v1
     `--CREATE BLOOM FILTER
}
do_eqp_test 6.3 {
  SELECT max(z) FROM t0 WHERE w=123 AND x IN k1 AND y BETWEEN 44 AND 55;
} {
  QUERY PLAN
  |--CO-ROUTINE t0
  |  `--COMPOUND QUERY
  |     |--LEFT-MOST SUBQUERY
  |     |  |--SEARCH t01 USING INDEX t01x (w=? AND x=? AND y>? AND y<?)
  |     |  `--LIST SUBQUERY xxxxxx
  |     |     |--SCAN k1
  |     |     `--CREATE BLOOM FILTER
  |     `--UNION ALL
  |        |--SEARCH t02 USING INDEX t02x (w=? AND x=? AND y>? AND y<?)
  |        `--LIST SUBQUERY xxxxxx
  |           |--SCAN k1
  |           `--CREATE BLOOM FILTER
  |--SEARCH t0
  `--LIST SUBQUERY xxxxxx
     |--SCAN k1
     `--CREATE BLOOM FILTER
}

finish_test

Changes to test/rowvalue4.test.

232
233
234
235
236
237
238
239

240
241

242
243
244
245
246
247
248
  SELECT * FROM d2 WHERE 
    (a, b) IN (SELECT x, y FROM d1) AND
    (c) IN (SELECT y FROM d1)
} {
  QUERY PLAN
  |--SEARCH d2 USING INDEX d2ab (a=? AND b=?)
  |--LIST SUBQUERY xxxxxx
  |  `--SCAN d1

  `--LIST SUBQUERY xxxxxx
     `--SCAN d1

}

do_execsql_test 6.0 {
  CREATE TABLE e1(a, b, c, d, e);
  CREATE INDEX e1ab ON e1(a, b);
  CREATE INDEX e1cde ON e1(c, d, e);
}







|
>

|
>







232
233
234
235
236
237
238
239
240
241
242
243
244
245
246
247
248
249
250
  SELECT * FROM d2 WHERE 
    (a, b) IN (SELECT x, y FROM d1) AND
    (c) IN (SELECT y FROM d1)
} {
  QUERY PLAN
  |--SEARCH d2 USING INDEX d2ab (a=? AND b=?)
  |--LIST SUBQUERY xxxxxx
  |  |--SCAN d1
  |  `--CREATE BLOOM FILTER
  `--LIST SUBQUERY xxxxxx
     |--SCAN d1
     `--CREATE BLOOM FILTER
}

do_execsql_test 6.0 {
  CREATE TABLE e1(a, b, c, d, e);
  CREATE INDEX e1ab ON e1(a, b);
  CREATE INDEX e1cde ON e1(c, d, e);
}