/ Check-in [d9676284]
Login

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

Overview
Comment:Make more aggressive use of transitivity in optimizing queries. Add a test case.
Downloads: Tarball | ZIP archive | SQL archive
Timelines: family | ancestors | descendants | both | transitive-constraints
Files: files | file ages | folders
SHA1: d96762841a461e192fb2f317d684d000376350dd
User & Date: drh 2013-01-17 15:05:17
Context
2013-01-17
16:18
Avoid unnecessary collating sequence and affinity restrictions on the use of transitivity. Add test cases to show that the restrictions are not needed. check-in: 56549f45 user: drh tags: transitive-constraints
15:05
Make more aggressive use of transitivity in optimizing queries. Add a test case. check-in: d9676284 user: drh tags: transitive-constraints
00:08
Improved comments explaining the operation of the findTerm() utility routine in where.c. Increase the maximum number of levels of transitivity from 4 to 11. check-in: fe152f8b user: drh tags: transitive-constraints
Changes
Hide Diffs Side-by-Side Diffs Ignore Whitespace Patch

Changes to src/where.c.

   659    659   ){
   660    660     WhereTerm *pTerm;            /* Term being examined as possible result */
   661    661     WhereTerm *pResult = 0;      /* The answer to return */
   662    662     WhereClause *pWCOrig = pWC;  /* Original pWC value */
   663    663     int j, k;                    /* Loop counters */
   664    664     Expr *pX;                /* Pointer to an expression */
   665    665     Parse *pParse;           /* Parsing context */
          666  +  int iOrigCol = iColumn;  /* Original value of iColumn */
   666    667     int nEquiv = 2;          /* Number of entires in aEquiv[] */
   667    668     int iEquiv = 2;          /* Number of entries of aEquiv[] processed so far */
   668    669     int aEquiv[22];          /* iCur,iColumn and up to 10 other equivalents */
   669    670   
   670    671     assert( iCur>=0 );
   671    672     aEquiv[0] = iCur;
   672    673     aEquiv[1] = iColumn;
   673    674     for(;;){
   674    675       for(pWC=pWCOrig; pWC; pWC=pWC->pOuter){
   675    676         for(pTerm=pWC->a, k=pWC->nTerm; k; k--, pTerm++){
   676    677           if( pTerm->leftCursor==iCur
   677    678             && pTerm->u.leftColumn==iColumn
   678         -          && (pTerm->eOperator & op & WO_ALL)!=0
   679    679           ){
   680         -          if( (pTerm->prereqRight & notReady)==0 ){
   681         -            if( iColumn>=0 && pIdx && (pTerm->eOperator & WO_ISNULL)==0 ){
          680  +          if( (pTerm->prereqRight & notReady)==0
          681  +           && (pTerm->eOperator & op & WO_ALL)!=0
          682  +          ){
          683  +            if( iOrigCol>=0 && pIdx && (pTerm->eOperator & WO_ISNULL)==0 ){
   682    684                 CollSeq *pColl;
   683    685                 char idxaff;
   684    686         
   685    687                 pX = pTerm->pExpr;
   686    688                 pParse = pWC->pParse;
   687         -              idxaff = pIdx->pTable->aCol[iColumn].affinity;
          689  +              idxaff = pIdx->pTable->aCol[iOrigCol].affinity;
   688    690                 if( !sqlite3IndexAffinityOk(pX, idxaff) ) continue;
   689    691         
   690    692                 /* Figure out the collation sequence required from an index for
   691    693                 ** it to be useful for optimising expression pX. Store this
   692    694                 ** value in variable pColl.
   693    695                 */
   694    696                 assert(pX->pLeft);
   695    697                 pColl = sqlite3BinaryCompareCollSeq(pParse,pX->pLeft,pX->pRight);
   696    698                 if( pColl==0 ) pColl = pParse->db->pDfltColl;
   697    699         
   698         -              for(j=0; pIdx->aiColumn[j]!=iColumn; j++){
          700  +              for(j=0; pIdx->aiColumn[j]!=iOrigCol; j++){
   699    701                   if( NEVER(j>=pIdx->nColumn) ) return 0;
   700    702                 }
   701    703                 if( sqlite3StrICmp(pColl->zName, pIdx->azColl[j]) ) continue;
   702    704               }
   703    705               pResult = pTerm;
   704    706               if( pTerm->prereqRight==0 ) goto findTerm_success;
   705    707             }
   706         -          if( (op&WO_EQ)!=0
   707         -           && (pTerm->eOperator & WO_EQUIV)!=0
          708  +          if( (pTerm->eOperator & WO_EQUIV)!=0
   708    709              && nEquiv<ArraySize(aEquiv)
   709    710             ){
   710    711               pX = sqlite3ExprSkipCollate(pTerm->pExpr->pRight);
   711    712               assert( pX->op==TK_COLUMN );
   712    713               for(j=0; j<nEquiv; j+=2){
   713    714                 if( aEquiv[j]==pX->iTable && aEquiv[j+1]==pX->iColumn ) break;
   714    715               }
................................................................................
   720    721             }
   721    722           }
   722    723         }
   723    724       }
   724    725       if( iEquiv>=nEquiv ) break;
   725    726       iCur = aEquiv[iEquiv++];
   726    727       iColumn = aEquiv[iEquiv++];
   727         -    op &= WO_EQ;
   728    728     }
   729    729   findTerm_success:
   730    730     return pResult;
   731    731   }
   732    732   
   733    733   /* Forward reference */
   734    734   static void exprAnalyze(SrcList*, WhereClause*, int);
................................................................................
  1001   1001     ** Compute the set of tables that might satisfy cases 1 or 2.
  1002   1002     */
  1003   1003     indexable = ~(Bitmask)0;
  1004   1004     chngToIN = ~(pWC->vmask);
  1005   1005     for(i=pOrWc->nTerm-1, pOrTerm=pOrWc->a; i>=0 && indexable; i--, pOrTerm++){
  1006   1006       if( (pOrTerm->eOperator & WO_SINGLE)==0 ){
  1007   1007         WhereAndInfo *pAndInfo;
  1008         -      assert( pOrTerm->eOperator==0 );
  1009   1008         assert( (pOrTerm->wtFlags & (TERM_ANDINFO|TERM_ORINFO))==0 );
  1010   1009         chngToIN = 0;
  1011   1010         pAndInfo = sqlite3DbMallocRaw(db, sizeof(*pAndInfo));
  1012   1011         if( pAndInfo ){
  1013   1012           WhereClause *pAndWC;
  1014   1013           WhereTerm *pAndTerm;
  1015   1014           int j;
................................................................................
  1287   1286       extraRight = x-1;  /* ON clause terms may not be used with an index
  1288   1287                          ** on left table of a LEFT JOIN.  Ticket #3015 */
  1289   1288     }
  1290   1289     pTerm->prereqAll = prereqAll;
  1291   1290     pTerm->leftCursor = -1;
  1292   1291     pTerm->iParent = -1;
  1293   1292     pTerm->eOperator = 0;
  1294         -  if( allowedOp(op) && (pTerm->prereqRight & prereqLeft)==0 ){
         1293  +  if( allowedOp(op) ){
  1295   1294       Expr *pLeft = sqlite3ExprSkipCollate(pExpr->pLeft);
  1296   1295       Expr *pRight = sqlite3ExprSkipCollate(pExpr->pRight);
         1296  +    u16 opMask = (pTerm->prereqRight & prereqLeft)==0 ? WO_ALL : WO_EQUIV;
  1297   1297       if( pLeft->op==TK_COLUMN ){
  1298   1298         pTerm->leftCursor = pLeft->iTable;
  1299   1299         pTerm->u.leftColumn = pLeft->iColumn;
  1300         -      pTerm->eOperator = operatorMask(op);
         1300  +      pTerm->eOperator = operatorMask(op) & opMask;
  1301   1301       }
  1302   1302       if( pRight && pRight->op==TK_COLUMN ){
  1303   1303         WhereTerm *pNew;
  1304   1304         Expr *pDup;
  1305   1305         u16 eExtraOp = 0;        /* Extra bits for pNew->eOperator */
  1306   1306         if( pTerm->leftCursor>=0 ){
  1307   1307           int idxNew;
................................................................................
  1328   1328         exprCommute(pParse, pDup);
  1329   1329         pLeft = sqlite3ExprSkipCollate(pDup->pLeft);
  1330   1330         pNew->leftCursor = pLeft->iTable;
  1331   1331         pNew->u.leftColumn = pLeft->iColumn;
  1332   1332         testcase( (prereqLeft | extraRight) != prereqLeft );
  1333   1333         pNew->prereqRight = prereqLeft | extraRight;
  1334   1334         pNew->prereqAll = prereqAll;
  1335         -      pNew->eOperator = operatorMask(pDup->op) + eExtraOp;
         1335  +      pNew->eOperator = (operatorMask(pDup->op) + eExtraOp) & opMask;
  1336   1336       }
  1337   1337     }
  1338   1338   
  1339   1339   #ifndef SQLITE_OMIT_BETWEEN_OPTIMIZATION
  1340   1340     /* If a term is the BETWEEN operator, create two new virtual terms
  1341   1341     ** that define the range that the BETWEEN implements.  For example:
  1342   1342     **

Changes to test/autoindex1.test.

   253    253     CREATE TABLE t5(a, b, c);
   254    254     EXPLAIN QUERY PLAN SELECT a FROM t5 WHERE b=10 ORDER BY c;
   255    255   } {
   256    256     0 0 0 {SCAN TABLE t5 (~100000 rows)} 
   257    257     0 0 0 {USE TEMP B-TREE FOR ORDER BY}
   258    258   }
   259    259   
          260  +# The following checks a performance issue reported on the sqlite-dev
          261  +# mailing list on 2013-01-10
          262  +#
          263  +do_execsql_test autoindex1-800 {
          264  +  CREATE TABLE accounts(
          265  +    _id INTEGER PRIMARY KEY AUTOINCREMENT,
          266  +    account_name TEXT,
          267  +    account_type TEXT,
          268  +    data_set TEXT
          269  +  );
          270  +  CREATE TABLE data(
          271  +    _id INTEGER PRIMARY KEY AUTOINCREMENT,
          272  +    package_id INTEGER REFERENCES package(_id),
          273  +    mimetype_id INTEGER REFERENCES mimetype(_id) NOT NULL,
          274  +    raw_contact_id INTEGER REFERENCES raw_contacts(_id) NOT NULL,
          275  +    is_read_only INTEGER NOT NULL DEFAULT 0,
          276  +    is_primary INTEGER NOT NULL DEFAULT 0,
          277  +    is_super_primary INTEGER NOT NULL DEFAULT 0,
          278  +    data_version INTEGER NOT NULL DEFAULT 0,
          279  +    data1 TEXT,
          280  +    data2 TEXT,
          281  +    data3 TEXT,
          282  +    data4 TEXT,
          283  +    data5 TEXT,
          284  +    data6 TEXT,
          285  +    data7 TEXT,
          286  +    data8 TEXT,
          287  +    data9 TEXT,
          288  +    data10 TEXT,
          289  +    data11 TEXT,
          290  +    data12 TEXT,
          291  +    data13 TEXT,
          292  +    data14 TEXT,
          293  +    data15 TEXT,
          294  +    data_sync1 TEXT,
          295  +    data_sync2 TEXT,
          296  +    data_sync3 TEXT,
          297  +    data_sync4 TEXT 
          298  +  );
          299  +  CREATE TABLE mimetypes(
          300  +    _id INTEGER PRIMARY KEY AUTOINCREMENT,
          301  +    mimetype TEXT NOT NULL
          302  +  );
          303  +  CREATE TABLE raw_contacts(
          304  +    _id INTEGER PRIMARY KEY AUTOINCREMENT,
          305  +    account_id INTEGER REFERENCES accounts(_id),
          306  +    sourceid TEXT,
          307  +    raw_contact_is_read_only INTEGER NOT NULL DEFAULT 0,
          308  +    version INTEGER NOT NULL DEFAULT 1,
          309  +    dirty INTEGER NOT NULL DEFAULT 0,
          310  +    deleted INTEGER NOT NULL DEFAULT 0,
          311  +    contact_id INTEGER REFERENCES contacts(_id),
          312  +    aggregation_mode INTEGER NOT NULL DEFAULT 0,
          313  +    aggregation_needed INTEGER NOT NULL DEFAULT 1,
          314  +    custom_ringtone TEXT,
          315  +    send_to_voicemail INTEGER NOT NULL DEFAULT 0,
          316  +    times_contacted INTEGER NOT NULL DEFAULT 0,
          317  +    last_time_contacted INTEGER,
          318  +    starred INTEGER NOT NULL DEFAULT 0,
          319  +    display_name TEXT,
          320  +    display_name_alt TEXT,
          321  +    display_name_source INTEGER NOT NULL DEFAULT 0,
          322  +    phonetic_name TEXT,
          323  +    phonetic_name_style TEXT,
          324  +    sort_key TEXT,
          325  +    sort_key_alt TEXT,
          326  +    name_verified INTEGER NOT NULL DEFAULT 0,
          327  +    sync1 TEXT,
          328  +    sync2 TEXT,
          329  +    sync3 TEXT,
          330  +    sync4 TEXT,
          331  +    sync_uid TEXT,
          332  +    sync_version INTEGER NOT NULL DEFAULT 1,
          333  +    has_calendar_event INTEGER NOT NULL DEFAULT 0,
          334  +    modified_time INTEGER,
          335  +    is_restricted INTEGER DEFAULT 0,
          336  +    yp_source TEXT,
          337  +    method_selected INTEGER DEFAULT 0,
          338  +    custom_vibration_type INTEGER DEFAULT 0,
          339  +    custom_ringtone_path TEXT,
          340  +    message_notification TEXT,
          341  +    message_notification_path TEXT
          342  +  );
          343  +  CREATE INDEX data_mimetype_data1_index ON data (mimetype_id,data1);
          344  +  CREATE INDEX data_raw_contact_id ON data (raw_contact_id);
          345  +  CREATE UNIQUE INDEX mime_type ON mimetypes (mimetype);
          346  +  CREATE INDEX raw_contact_sort_key1_index ON raw_contacts (sort_key);
          347  +  CREATE INDEX raw_contact_sort_key2_index ON raw_contacts (sort_key_alt);
          348  +  CREATE INDEX raw_contacts_contact_id_index ON raw_contacts (contact_id);
          349  +  CREATE INDEX raw_contacts_source_id_account_id_index
          350  +      ON raw_contacts (sourceid, account_id);
          351  +  ANALYZE sqlite_master;
          352  +  INSERT INTO sqlite_stat1
          353  +     VALUES('raw_contacts','raw_contact_sort_key2_index','1600 4');
          354  +  INSERT INTO sqlite_stat1
          355  +     VALUES('raw_contacts','raw_contact_sort_key1_index','1600 4');
          356  +  INSERT INTO sqlite_stat1
          357  +     VALUES('raw_contacts','raw_contacts_source_id_account_id_index',
          358  +            '1600 1600 1600');
          359  +  INSERT INTO sqlite_stat1
          360  +     VALUES('raw_contacts','raw_contacts_contact_id_index','1600 1');
          361  +  INSERT INTO sqlite_stat1 VALUES('mimetypes','mime_type','12 1');
          362  +  INSERT INTO sqlite_stat1
          363  +     VALUES('data','data_mimetype_data1_index','9819 2455 3');
          364  +  INSERT INTO sqlite_stat1 VALUES('data','data_raw_contact_id','9819 7');
          365  +  INSERT INTO sqlite_stat1 VALUES('accounts',NULL,'1');
          366  +  DROP TABLE IF EXISTS sqlite_stat3;
          367  +  ANALYZE sqlite_master;
          368  +  
          369  +  EXPLAIN QUERY PLAN
          370  +  SELECT * FROM 
          371  +        data JOIN mimetypes ON (data.mimetype_id=mimetypes._id) 
          372  +             JOIN raw_contacts ON (data.raw_contact_id=raw_contacts._id) 
          373  +             JOIN accounts ON (raw_contacts.account_id=accounts._id)
          374  +   WHERE mimetype_id=10 AND data14 IS NOT NULL;
          375  +} {/SEARCH TABLE data .*SEARCH TABLE raw_contacts/}
          376  +do_execsql_test autoindex1-801 {
          377  +  EXPLAIN QUERY PLAN
          378  +  SELECT * FROM 
          379  +        data JOIN mimetypes ON (data.mimetype_id=mimetypes._id) 
          380  +             JOIN raw_contacts ON (data.raw_contact_id=raw_contacts._id) 
          381  +             JOIN accounts ON (raw_contacts.account_id=accounts._id)
          382  +   WHERE mimetypes._id=10 AND data14 IS NOT NULL;
          383  +} {/SEARCH TABLE data .*SEARCH TABLE raw_contacts/}
   260    384   
   261    385   finish_test