Many hyperlinks are disabled.
Use anonymous login
to enable hyperlinks.
Overview
Comment: | Allow an index to be used for sorting even if prior terms of the index are constrained by IN operators. |
---|---|
Downloads: | Tarball | ZIP archive |
Timelines: | family | ancestors | descendants | both | IN-with-ORDERBY |
Files: | files | file ages | folders |
SHA1: |
98bf668ab1a8683b46ee8c94cb60f821 |
User & Date: | drh 2013-02-07 21:15:14.299 |
Context
2013-02-08
| ||
16:04 | Allow the "a=?1 OR a=?2" to "a IN (?1,?2)" transformation to work on virtual tables again. This was formerly restricted because virtual tables could not optimize IN terms. (See check-in [fad88e71cf195e].) But IN terms are now used by virtual tables (as of check-in [3d65c70343]) so the restriction can now be removed. (check-in: a917c1f092 user: drh tags: IN-with-ORDERBY) | |
2013-02-07
| ||
21:15 | Allow an index to be used for sorting even if prior terms of the index are constrained by IN operators. (check-in: 98bf668ab1 user: drh tags: IN-with-ORDERBY) | |
09:33 | Fix harmless compiler warnings. (check-in: 4a7b4ee011 user: drh tags: trunk) | |
Changes
Changes to src/where.c.
︙ | ︙ | |||
3006 3007 3008 3009 3010 3011 3012 3013 3014 3015 3016 3017 3018 3019 3020 3021 3022 3023 | /* If X is the column in the index and ORDER BY clause, check to see ** if there are any X= or X IS NULL constraints in the WHERE clause. */ pConstraint = findTerm(p->pWC, base, iColumn, p->notReady, WO_EQ|WO_ISNULL|WO_IN, pIdx); if( pConstraint==0 ){ isEq = 0; }else if( (pConstraint->eOperator & WO_IN)!=0 ){ /* Constraints of the form: "X IN ..." cannot be used with an ORDER BY ** because we do not know in what order the values on the RHS of the IN ** operator will occur. */ break; }else if( (pConstraint->eOperator & WO_ISNULL)!=0 ){ uniqueNotNull = 0; isEq = 1; /* "X IS NULL" means X has only a single value */ }else if( pConstraint->prereqRight==0 ){ isEq = 1; /* Constraint "X=constant" means X has only a single value */ }else{ Expr *pRight = pConstraint->pExpr->pRight; | > > > > > | 3006 3007 3008 3009 3010 3011 3012 3013 3014 3015 3016 3017 3018 3019 3020 3021 3022 3023 3024 3025 3026 3027 3028 | /* If X is the column in the index and ORDER BY clause, check to see ** if there are any X= or X IS NULL constraints in the WHERE clause. */ pConstraint = findTerm(p->pWC, base, iColumn, p->notReady, WO_EQ|WO_ISNULL|WO_IN, pIdx); if( pConstraint==0 ){ isEq = 0; }else if( (pConstraint->eOperator & WO_IN)!=0 ){ #if 0 /* Constraints of the form: "X IN ..." cannot be used with an ORDER BY ** because we do not know in what order the values on the RHS of the IN ** operator will occur. */ break; #else if( termSortOrder ) break; isEq = 0; #endif }else if( (pConstraint->eOperator & WO_ISNULL)!=0 ){ uniqueNotNull = 0; isEq = 1; /* "X IS NULL" means X has only a single value */ }else if( pConstraint->prereqRight==0 ){ isEq = 1; /* Constraint "X=constant" means X has only a single value */ }else{ Expr *pRight = pConstraint->pExpr->pRight; |
︙ | ︙ | |||
3313 3314 3315 3316 3317 3318 3319 | /* If the index being considered is UNIQUE, and there is an equality ** constraint for all columns in the index, then this search will find ** at most a single row. In this case set the WHERE_UNIQUE flag to ** indicate this to the caller. ** ** Otherwise, if the search may find more than one row, test to see if | | | | 3318 3319 3320 3321 3322 3323 3324 3325 3326 3327 3328 3329 3330 3331 3332 3333 | /* If the index being considered is UNIQUE, and there is an equality ** constraint for all columns in the index, then this search will find ** at most a single row. In this case set the WHERE_UNIQUE flag to ** indicate this to the caller. ** ** Otherwise, if the search may find more than one row, test to see if ** there is a range constraint on indexed column (pc.plan.nEq+1) that ** can be optimized using the index. */ if( pc.plan.nEq==pProbe->nColumn && pProbe->onError!=OE_None ){ testcase( pc.plan.wsFlags & WHERE_COLUMN_IN ); testcase( pc.plan.wsFlags & WHERE_COLUMN_NULL ); if( (pc.plan.wsFlags & (WHERE_COLUMN_IN|WHERE_COLUMN_NULL))==0 ){ pc.plan.wsFlags |= WHERE_UNIQUE; if( p->i==0 || (p->aLevel[p->i-1].plan.wsFlags & WHERE_ALL_UNIQUE)!=0 ){ |
︙ | ︙ |
Changes to test/where.test.
︙ | ︙ | |||
375 376 377 378 379 380 381 | } } {1 0 4 2 1 9 3 1 16 4} do_test where-5.2 { count { SELECT * FROM t1 WHERE rowid+0 IN (1,2,3,1234) order by 1; } } {1 0 4 2 1 9 3 1 16 102} | | | > > > > > > > > > > > > > > > | 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 | } } {1 0 4 2 1 9 3 1 16 4} do_test where-5.2 { count { SELECT * FROM t1 WHERE rowid+0 IN (1,2,3,1234) order by 1; } } {1 0 4 2 1 9 3 1 16 102} do_test where-5.3a { count { SELECT * FROM t1 WHERE w IN (-1,1,2,3) order by 1; } } {1 0 4 2 1 9 3 1 16 13} do_test where-5.3b { count { SELECT * FROM t1 WHERE w IN (3,-1,1,2) order by 1; } } {1 0 4 2 1 9 3 1 16 13} do_test where-5.3c { count { SELECT * FROM t1 WHERE w IN (3,2,-1,1,2) order by 1; } } {1 0 4 2 1 9 3 1 16 13} do_test where-5.3d { count { SELECT * FROM t1 WHERE w IN (-1,1,2,3) order by 1 DESC; } } {3 1 16 2 1 9 1 0 4 14} do_test where-5.4 { count { SELECT * FROM t1 WHERE w+0 IN (-1,1,2,3) order by 1; } } {1 0 4 2 1 9 3 1 16 102} do_test where-5.5 { count { |
︙ | ︙ | |||
507 508 509 510 511 512 513 | } {1 100 4 2 99 9 3 98 16 nosort} do_test where-6.7 { cksort { SELECT * FROM t3 WHERE b>0 ORDER BY a LIMIT 3 } } {1 100 4 2 99 9 3 98 16 nosort} ifcapable subquery { | | | > > > > > | 522 523 524 525 526 527 528 529 530 531 532 533 534 535 536 537 538 539 540 541 542 543 544 545 | } {1 100 4 2 99 9 3 98 16 nosort} do_test where-6.7 { cksort { SELECT * FROM t3 WHERE b>0 ORDER BY a LIMIT 3 } } {1 100 4 2 99 9 3 98 16 nosort} ifcapable subquery { do_test where-6.8a { cksort { SELECT * FROM t3 WHERE a IN (3,5,7,1,9,4,2) ORDER BY a LIMIT 3 } } {1 100 4 2 99 9 3 98 16 nosort} do_test where-6.8b { cksort { SELECT * FROM t3 WHERE a IN (3,5,7,1,9,4,2) ORDER BY a DESC LIMIT 3 } } {9 92 100 7 94 64 5 96 36 sort} } do_test where-6.9.1 { cksort { SELECT * FROM t3 WHERE a=1 AND c>0 ORDER BY a LIMIT 3 } } {1 100 4 nosort} do_test where-6.9.1.1 { |
︙ | ︙ |
Changes to test/where2.test.
︙ | ︙ | |||
163 164 165 166 167 168 169 | SELECT * FROM t1 WHERE z IN (SELECT 10207 UNION SELECT 10006) AND y IN (SELECT 10000 UNION SELECT 10201) AND x>0 AND x<10 ORDER BY w } } {99 6 10000 10006 100 6 10201 10207 sort t1 i1zyx} } | | > > > > > > > > > > > > > > > > > > > > > > > > | | > > > > > > | 163 164 165 166 167 168 169 170 171 172 173 174 175 176 177 178 179 180 181 182 183 184 185 186 187 188 189 190 191 192 193 194 195 196 197 198 199 200 201 202 203 204 205 206 207 208 209 210 211 212 213 214 215 216 217 218 219 220 221 222 223 224 | SELECT * FROM t1 WHERE z IN (SELECT 10207 UNION SELECT 10006) AND y IN (SELECT 10000 UNION SELECT 10201) AND x>0 AND x<10 ORDER BY w } } {99 6 10000 10006 100 6 10201 10207 sort t1 i1zyx} } do_test where2-4.6a { queryplan { SELECT * FROM t1 WHERE x IN (1,2,3,4,5,6,7,8) AND y IN (10000,10001,10002,10003,10004,10005) ORDER BY x } } {99 6 10000 10006 nosort t1 i1xy} do_test where2-4.6b { queryplan { SELECT * FROM t1 WHERE x IN (1,2,3,4,5,6,7,8) AND y IN (10000,10001,10002,10003,10004,10005) ORDER BY x DESC } } {99 6 10000 10006 sort t1 i1xy} do_test where2-4.6c { queryplan { SELECT * FROM t1 WHERE x IN (1,2,3,4,5,6,7,8) AND y IN (10000,10001,10002,10003,10004,10005) ORDER BY x, y } } {99 6 10000 10006 nosort t1 i1xy} do_test where2-4.6d { queryplan { SELECT * FROM t1 WHERE x IN (1,2,3,4,5,6,7,8) AND y IN (10000,10001,10002,10003,10004,10005) ORDER BY x, y DESC } } {99 6 10000 10006 sort t1 i1xy} # Duplicate entires on the RHS of an IN operator do not cause duplicate # output rows. # do_test where2-4.6x { queryplan { SELECT * FROM t1 WHERE z IN (10207,10006,10006,10207) ORDER BY w } } {99 6 10000 10006 100 6 10201 10207 sort t1 i1zyx} do_test where2-4.6y { queryplan { SELECT * FROM t1 WHERE z IN (10207,10006,10006,10207) ORDER BY w DESC } } {100 6 10201 10207 99 6 10000 10006 sort t1 i1zyx} ifcapable compound { do_test where2-4.7 { queryplan { SELECT * FROM t1 WHERE z IN ( SELECT 10207 UNION ALL SELECT 10006 UNION ALL SELECT 10006 UNION ALL SELECT 10207) ORDER BY w |
︙ | ︙ | |||
203 204 205 206 207 208 209 | do_test where2-5.1 { queryplan { SELECT * FROM t1 WHERE w=99 ORDER BY w } } {99 6 10000 10006 nosort t1 i1w} ifcapable subquery { | | > > > > > | 233 234 235 236 237 238 239 240 241 242 243 244 245 246 247 248 249 250 251 252 253 254 255 | do_test where2-5.1 { queryplan { SELECT * FROM t1 WHERE w=99 ORDER BY w } } {99 6 10000 10006 nosort t1 i1w} ifcapable subquery { do_test where2-5.2a { queryplan { SELECT * FROM t1 WHERE w IN (99) ORDER BY w } } {99 6 10000 10006 nosort t1 i1w} do_test where2-5.2b { queryplan { SELECT * FROM t1 WHERE w IN (99) ORDER BY w DESC } } {99 6 10000 10006 sort t1 i1w} } # Verify that OR clauses get translated into IN operators. # set ::idx {} ifcapable subquery {set ::idx i1w} |
︙ | ︙ |