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