SQLite
Check-in [d96762841a461e192fb2f317d684d000376350dd]
Not logged in
Overview
SHA1 Hash:d96762841a461e192fb2f317d684d000376350dd
Date: 2013-01-17 15:05:17
User: drh
Comment:Make more aggressive use of transitivity in optimizing queries. Add a test case.
Tags And Properties
Changes
Hide Diffs Unified Diffs Ignore Whitespace Patch

Changes to src/where.c

659
660
661
662
663
664
665

666
667
668
669
670
671
672
673
674
675
676
677


678
679
680
681
682
683
684
685
686
687
688
689
690
691
692
693
694
695
696
697
698
699
700
701
702
703
704
705
706
707
708
709
710
711
712
713
714
...
720
721
722
723
724
725
726
727
728
729
730
731
732
733
734
....
1001
1002
1003
1004
1005
1006
1007
1008
1009
1010
1011
1012
1013
1014
1015
....
1287
1288
1289
1290
1291
1292
1293
1294
1295
1296

1297
1298
1299
1300
1301
1302
1303
1304
1305
1306
1307
....
1328
1329
1330
1331
1332
1333
1334
1335
1336
1337
1338
1339
1340
1341
1342
){
  WhereTerm *pTerm;            /* Term being examined as possible result */
  WhereTerm *pResult = 0;      /* The answer to return */
  WhereClause *pWCOrig = pWC;  /* Original pWC value */
  int j, k;                    /* Loop counters */
  Expr *pX;                /* Pointer to an expression */
  Parse *pParse;           /* Parsing context */

  int nEquiv = 2;          /* Number of entires in aEquiv[] */
  int iEquiv = 2;          /* Number of entries of aEquiv[] processed so far */
  int aEquiv[22];          /* iCur,iColumn and up to 10 other equivalents */

  assert( iCur>=0 );
  aEquiv[0] = iCur;
  aEquiv[1] = iColumn;
  for(;;){
    for(pWC=pWCOrig; pWC; pWC=pWC->pOuter){
      for(pTerm=pWC->a, k=pWC->nTerm; k; k--, pTerm++){
        if( pTerm->leftCursor==iCur
          && pTerm->u.leftColumn==iColumn


          && (pTerm->eOperator & op & WO_ALL)!=0
        ){
          if( (pTerm->prereqRight & notReady)==0 ){
            if( iColumn>=0 && pIdx && (pTerm->eOperator & WO_ISNULL)==0 ){
              CollSeq *pColl;
              char idxaff;
      
              pX = pTerm->pExpr;
              pParse = pWC->pParse;
              idxaff = pIdx->pTable->aCol[iColumn].affinity;
              if( !sqlite3IndexAffinityOk(pX, idxaff) ) continue;
      
              /* Figure out the collation sequence required from an index for
              ** it to be useful for optimising expression pX. Store this
              ** value in variable pColl.
              */
              assert(pX->pLeft);
              pColl = sqlite3BinaryCompareCollSeq(pParse,pX->pLeft,pX->pRight);
              if( pColl==0 ) pColl = pParse->db->pDfltColl;
      
              for(j=0; pIdx->aiColumn[j]!=iColumn; j++){
                if( NEVER(j>=pIdx->nColumn) ) return 0;
              }
              if( sqlite3StrICmp(pColl->zName, pIdx->azColl[j]) ) continue;
            }
            pResult = pTerm;
            if( pTerm->prereqRight==0 ) goto findTerm_success;
          }
          if( (op&WO_EQ)!=0
           && (pTerm->eOperator & WO_EQUIV)!=0
           && nEquiv<ArraySize(aEquiv)
          ){
            pX = sqlite3ExprSkipCollate(pTerm->pExpr->pRight);
            assert( pX->op==TK_COLUMN );
            for(j=0; j<nEquiv; j+=2){
              if( aEquiv[j]==pX->iTable && aEquiv[j+1]==pX->iColumn ) break;
            }
................................................................................
          }
        }
      }
    }
    if( iEquiv>=nEquiv ) break;
    iCur = aEquiv[iEquiv++];
    iColumn = aEquiv[iEquiv++];
    op &= WO_EQ;
  }
findTerm_success:
  return pResult;
}

/* Forward reference */
static void exprAnalyze(SrcList*, WhereClause*, int);
................................................................................
  ** Compute the set of tables that might satisfy cases 1 or 2.
  */
  indexable = ~(Bitmask)0;
  chngToIN = ~(pWC->vmask);
  for(i=pOrWc->nTerm-1, pOrTerm=pOrWc->a; i>=0 && indexable; i--, pOrTerm++){
    if( (pOrTerm->eOperator & WO_SINGLE)==0 ){
      WhereAndInfo *pAndInfo;
      assert( pOrTerm->eOperator==0 );
      assert( (pOrTerm->wtFlags & (TERM_ANDINFO|TERM_ORINFO))==0 );
      chngToIN = 0;
      pAndInfo = sqlite3DbMallocRaw(db, sizeof(*pAndInfo));
      if( pAndInfo ){
        WhereClause *pAndWC;
        WhereTerm *pAndTerm;
        int j;
................................................................................
    extraRight = x-1;  /* ON clause terms may not be used with an index
                       ** on left table of a LEFT JOIN.  Ticket #3015 */
  }
  pTerm->prereqAll = prereqAll;
  pTerm->leftCursor = -1;
  pTerm->iParent = -1;
  pTerm->eOperator = 0;
  if( allowedOp(op) && (pTerm->prereqRight & prereqLeft)==0 ){
    Expr *pLeft = sqlite3ExprSkipCollate(pExpr->pLeft);
    Expr *pRight = sqlite3ExprSkipCollate(pExpr->pRight);

    if( pLeft->op==TK_COLUMN ){
      pTerm->leftCursor = pLeft->iTable;
      pTerm->u.leftColumn = pLeft->iColumn;
      pTerm->eOperator = operatorMask(op);
    }
    if( pRight && pRight->op==TK_COLUMN ){
      WhereTerm *pNew;
      Expr *pDup;
      u16 eExtraOp = 0;        /* Extra bits for pNew->eOperator */
      if( pTerm->leftCursor>=0 ){
        int idxNew;
................................................................................
      exprCommute(pParse, pDup);
      pLeft = sqlite3ExprSkipCollate(pDup->pLeft);
      pNew->leftCursor = pLeft->iTable;
      pNew->u.leftColumn = pLeft->iColumn;
      testcase( (prereqLeft | extraRight) != prereqLeft );
      pNew->prereqRight = prereqLeft | extraRight;
      pNew->prereqAll = prereqAll;
      pNew->eOperator = operatorMask(pDup->op) + eExtraOp;
    }
  }

#ifndef SQLITE_OMIT_BETWEEN_OPTIMIZATION
  /* If a term is the BETWEEN operator, create two new virtual terms
  ** that define the range that the BETWEEN implements.  For example:
  **







>












>
>
|
|
<
|





|










|







<
|







 







<







 







<







 







|


>



|







 







|







659
660
661
662
663
664
665
666
667
668
669
670
671
672
673
674
675
676
677
678
679
680
681
682

683
684
685
686
687
688
689
690
691
692
693
694
695
696
697
698
699
700
701
702
703
704
705
706
707

708
709
710
711
712
713
714
715
...
721
722
723
724
725
726
727

728
729
730
731
732
733
734
....
1001
1002
1003
1004
1005
1006
1007

1008
1009
1010
1011
1012
1013
1014
....
1286
1287
1288
1289
1290
1291
1292
1293
1294
1295
1296
1297
1298
1299
1300
1301
1302
1303
1304
1305
1306
1307
....
1328
1329
1330
1331
1332
1333
1334
1335
1336
1337
1338
1339
1340
1341
1342
){
  WhereTerm *pTerm;            /* Term being examined as possible result */
  WhereTerm *pResult = 0;      /* The answer to return */
  WhereClause *pWCOrig = pWC;  /* Original pWC value */
  int j, k;                    /* Loop counters */
  Expr *pX;                /* Pointer to an expression */
  Parse *pParse;           /* Parsing context */
  int iOrigCol = iColumn;  /* Original value of iColumn */
  int nEquiv = 2;          /* Number of entires in aEquiv[] */
  int iEquiv = 2;          /* Number of entries of aEquiv[] processed so far */
  int aEquiv[22];          /* iCur,iColumn and up to 10 other equivalents */

  assert( iCur>=0 );
  aEquiv[0] = iCur;
  aEquiv[1] = iColumn;
  for(;;){
    for(pWC=pWCOrig; pWC; pWC=pWC->pOuter){
      for(pTerm=pWC->a, k=pWC->nTerm; k; k--, pTerm++){
        if( pTerm->leftCursor==iCur
          && pTerm->u.leftColumn==iColumn
        ){
          if( (pTerm->prereqRight & notReady)==0
           && (pTerm->eOperator & op & WO_ALL)!=0
          ){

            if( iOrigCol>=0 && pIdx && (pTerm->eOperator & WO_ISNULL)==0 ){
              CollSeq *pColl;
              char idxaff;
      
              pX = pTerm->pExpr;
              pParse = pWC->pParse;
              idxaff = pIdx->pTable->aCol[iOrigCol].affinity;
              if( !sqlite3IndexAffinityOk(pX, idxaff) ) continue;
      
              /* Figure out the collation sequence required from an index for
              ** it to be useful for optimising expression pX. Store this
              ** value in variable pColl.
              */
              assert(pX->pLeft);
              pColl = sqlite3BinaryCompareCollSeq(pParse,pX->pLeft,pX->pRight);
              if( pColl==0 ) pColl = pParse->db->pDfltColl;
      
              for(j=0; pIdx->aiColumn[j]!=iOrigCol; j++){
                if( NEVER(j>=pIdx->nColumn) ) return 0;
              }
              if( sqlite3StrICmp(pColl->zName, pIdx->azColl[j]) ) continue;
            }
            pResult = pTerm;
            if( pTerm->prereqRight==0 ) goto findTerm_success;
          }

          if( (pTerm->eOperator & WO_EQUIV)!=0
           && nEquiv<ArraySize(aEquiv)
          ){
            pX = sqlite3ExprSkipCollate(pTerm->pExpr->pRight);
            assert( pX->op==TK_COLUMN );
            for(j=0; j<nEquiv; j+=2){
              if( aEquiv[j]==pX->iTable && aEquiv[j+1]==pX->iColumn ) break;
            }
................................................................................
          }
        }
      }
    }
    if( iEquiv>=nEquiv ) break;
    iCur = aEquiv[iEquiv++];
    iColumn = aEquiv[iEquiv++];

  }
findTerm_success:
  return pResult;
}

/* Forward reference */
static void exprAnalyze(SrcList*, WhereClause*, int);
................................................................................
  ** Compute the set of tables that might satisfy cases 1 or 2.
  */
  indexable = ~(Bitmask)0;
  chngToIN = ~(pWC->vmask);
  for(i=pOrWc->nTerm-1, pOrTerm=pOrWc->a; i>=0 && indexable; i--, pOrTerm++){
    if( (pOrTerm->eOperator & WO_SINGLE)==0 ){
      WhereAndInfo *pAndInfo;

      assert( (pOrTerm->wtFlags & (TERM_ANDINFO|TERM_ORINFO))==0 );
      chngToIN = 0;
      pAndInfo = sqlite3DbMallocRaw(db, sizeof(*pAndInfo));
      if( pAndInfo ){
        WhereClause *pAndWC;
        WhereTerm *pAndTerm;
        int j;
................................................................................
    extraRight = x-1;  /* ON clause terms may not be used with an index
                       ** on left table of a LEFT JOIN.  Ticket #3015 */
  }
  pTerm->prereqAll = prereqAll;
  pTerm->leftCursor = -1;
  pTerm->iParent = -1;
  pTerm->eOperator = 0;
  if( allowedOp(op) ){
    Expr *pLeft = sqlite3ExprSkipCollate(pExpr->pLeft);
    Expr *pRight = sqlite3ExprSkipCollate(pExpr->pRight);
    u16 opMask = (pTerm->prereqRight & prereqLeft)==0 ? WO_ALL : WO_EQUIV;
    if( pLeft->op==TK_COLUMN ){
      pTerm->leftCursor = pLeft->iTable;
      pTerm->u.leftColumn = pLeft->iColumn;
      pTerm->eOperator = operatorMask(op) & opMask;
    }
    if( pRight && pRight->op==TK_COLUMN ){
      WhereTerm *pNew;
      Expr *pDup;
      u16 eExtraOp = 0;        /* Extra bits for pNew->eOperator */
      if( pTerm->leftCursor>=0 ){
        int idxNew;
................................................................................
      exprCommute(pParse, pDup);
      pLeft = sqlite3ExprSkipCollate(pDup->pLeft);
      pNew->leftCursor = pLeft->iTable;
      pNew->u.leftColumn = pLeft->iColumn;
      testcase( (prereqLeft | extraRight) != prereqLeft );
      pNew->prereqRight = prereqLeft | extraRight;
      pNew->prereqAll = prereqAll;
      pNew->eOperator = (operatorMask(pDup->op) + eExtraOp) & opMask;
    }
  }

#ifndef SQLITE_OMIT_BETWEEN_OPTIMIZATION
  /* If a term is the BETWEEN operator, create two new virtual terms
  ** that define the range that the BETWEEN implements.  For example:
  **

Changes to test/autoindex1.test

253
254
255
256
257
258
259


260


























































































































261
  CREATE TABLE t5(a, b, c);
  EXPLAIN QUERY PLAN SELECT a FROM t5 WHERE b=10 ORDER BY c;
} {
  0 0 0 {SCAN TABLE t5 (~100000 rows)} 
  0 0 0 {USE TEMP B-TREE FOR ORDER BY}
}






























































































































finish_test







>
>
|
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>

253
254
255
256
257
258
259
260
261
262
263
264
265
266
267
268
269
270
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
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
  CREATE TABLE t5(a, b, c);
  EXPLAIN QUERY PLAN SELECT a FROM t5 WHERE b=10 ORDER BY c;
} {
  0 0 0 {SCAN TABLE t5 (~100000 rows)} 
  0 0 0 {USE TEMP B-TREE FOR ORDER BY}
}

# The following checks a performance issue reported on the sqlite-dev
# mailing list on 2013-01-10
#
do_execsql_test autoindex1-800 {
  CREATE TABLE accounts(
    _id INTEGER PRIMARY KEY AUTOINCREMENT,
    account_name TEXT,
    account_type TEXT,
    data_set TEXT
  );
  CREATE TABLE data(
    _id INTEGER PRIMARY KEY AUTOINCREMENT,
    package_id INTEGER REFERENCES package(_id),
    mimetype_id INTEGER REFERENCES mimetype(_id) NOT NULL,
    raw_contact_id INTEGER REFERENCES raw_contacts(_id) NOT NULL,
    is_read_only INTEGER NOT NULL DEFAULT 0,
    is_primary INTEGER NOT NULL DEFAULT 0,
    is_super_primary INTEGER NOT NULL DEFAULT 0,
    data_version INTEGER NOT NULL DEFAULT 0,
    data1 TEXT,
    data2 TEXT,
    data3 TEXT,
    data4 TEXT,
    data5 TEXT,
    data6 TEXT,
    data7 TEXT,
    data8 TEXT,
    data9 TEXT,
    data10 TEXT,
    data11 TEXT,
    data12 TEXT,
    data13 TEXT,
    data14 TEXT,
    data15 TEXT,
    data_sync1 TEXT,
    data_sync2 TEXT,
    data_sync3 TEXT,
    data_sync4 TEXT 
  );
  CREATE TABLE mimetypes(
    _id INTEGER PRIMARY KEY AUTOINCREMENT,
    mimetype TEXT NOT NULL
  );
  CREATE TABLE raw_contacts(
    _id INTEGER PRIMARY KEY AUTOINCREMENT,
    account_id INTEGER REFERENCES accounts(_id),
    sourceid TEXT,
    raw_contact_is_read_only INTEGER NOT NULL DEFAULT 0,
    version INTEGER NOT NULL DEFAULT 1,
    dirty INTEGER NOT NULL DEFAULT 0,
    deleted INTEGER NOT NULL DEFAULT 0,
    contact_id INTEGER REFERENCES contacts(_id),
    aggregation_mode INTEGER NOT NULL DEFAULT 0,
    aggregation_needed INTEGER NOT NULL DEFAULT 1,
    custom_ringtone TEXT,
    send_to_voicemail INTEGER NOT NULL DEFAULT 0,
    times_contacted INTEGER NOT NULL DEFAULT 0,
    last_time_contacted INTEGER,
    starred INTEGER NOT NULL DEFAULT 0,
    display_name TEXT,
    display_name_alt TEXT,
    display_name_source INTEGER NOT NULL DEFAULT 0,
    phonetic_name TEXT,
    phonetic_name_style TEXT,
    sort_key TEXT,
    sort_key_alt TEXT,
    name_verified INTEGER NOT NULL DEFAULT 0,
    sync1 TEXT,
    sync2 TEXT,
    sync3 TEXT,
    sync4 TEXT,
    sync_uid TEXT,
    sync_version INTEGER NOT NULL DEFAULT 1,
    has_calendar_event INTEGER NOT NULL DEFAULT 0,
    modified_time INTEGER,
    is_restricted INTEGER DEFAULT 0,
    yp_source TEXT,
    method_selected INTEGER DEFAULT 0,
    custom_vibration_type INTEGER DEFAULT 0,
    custom_ringtone_path TEXT,
    message_notification TEXT,
    message_notification_path TEXT
  );
  CREATE INDEX data_mimetype_data1_index ON data (mimetype_id,data1);
  CREATE INDEX data_raw_contact_id ON data (raw_contact_id);
  CREATE UNIQUE INDEX mime_type ON mimetypes (mimetype);
  CREATE INDEX raw_contact_sort_key1_index ON raw_contacts (sort_key);
  CREATE INDEX raw_contact_sort_key2_index ON raw_contacts (sort_key_alt);
  CREATE INDEX raw_contacts_contact_id_index ON raw_contacts (contact_id);
  CREATE INDEX raw_contacts_source_id_account_id_index
      ON raw_contacts (sourceid, account_id);
  ANALYZE sqlite_master;
  INSERT INTO sqlite_stat1
     VALUES('raw_contacts','raw_contact_sort_key2_index','1600 4');
  INSERT INTO sqlite_stat1
     VALUES('raw_contacts','raw_contact_sort_key1_index','1600 4');
  INSERT INTO sqlite_stat1
     VALUES('raw_contacts','raw_contacts_source_id_account_id_index',
            '1600 1600 1600');
  INSERT INTO sqlite_stat1
     VALUES('raw_contacts','raw_contacts_contact_id_index','1600 1');
  INSERT INTO sqlite_stat1 VALUES('mimetypes','mime_type','12 1');
  INSERT INTO sqlite_stat1
     VALUES('data','data_mimetype_data1_index','9819 2455 3');
  INSERT INTO sqlite_stat1 VALUES('data','data_raw_contact_id','9819 7');
  INSERT INTO sqlite_stat1 VALUES('accounts',NULL,'1');
  DROP TABLE IF EXISTS sqlite_stat3;
  ANALYZE sqlite_master;
  
  EXPLAIN QUERY PLAN
  SELECT * FROM 
        data JOIN mimetypes ON (data.mimetype_id=mimetypes._id) 
             JOIN raw_contacts ON (data.raw_contact_id=raw_contacts._id) 
             JOIN accounts ON (raw_contacts.account_id=accounts._id)
   WHERE mimetype_id=10 AND data14 IS NOT NULL;
} {/SEARCH TABLE data .*SEARCH TABLE raw_contacts/}
do_execsql_test autoindex1-801 {
  EXPLAIN QUERY PLAN
  SELECT * FROM 
        data JOIN mimetypes ON (data.mimetype_id=mimetypes._id) 
             JOIN raw_contacts ON (data.raw_contact_id=raw_contacts._id) 
             JOIN accounts ON (raw_contacts.account_id=accounts._id)
   WHERE mimetypes._id=10 AND data14 IS NOT NULL;
} {/SEARCH TABLE data .*SEARCH TABLE raw_contacts/}

finish_test