Many hyperlinks are disabled.
Use anonymous login
to enable hyperlinks.
Overview
Comment: | Loop through the elements on the RHS of an IN operator in reverse order when the ORDER BY clauses specifies DESC. |
---|---|
Downloads: | Tarball | ZIP archive |
Timelines: | family | ancestors | descendants | both | IN-with-ORDERBY |
Files: | files | file ages | folders |
SHA1: |
f78395c8896666bb1359b83fbcd58d5e |
User & Date: | drh 2013-02-08 18:48:23.501 |
Context
2013-02-08
| ||
20:39 | Make sure the virtual tables that take advantage of IN operators sort the RHS of the IN operator in the correct order according to the ORDER BY clause. (check-in: b016b7546d user: drh tags: IN-with-ORDERBY) | |
18:48 | Loop through the elements on the RHS of an IN operator in reverse order when the ORDER BY clauses specifies DESC. (check-in: f78395c889 user: drh tags: IN-with-ORDERBY) | |
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) | |
Changes
Changes to src/sqliteInt.h.
︙ | ︙ | |||
1961 1962 1963 1964 1965 1966 1967 1968 1969 1970 1971 1972 1973 1974 | int p1, p2; /* Operands of the opcode used to ends the loop */ union { /* Information that depends on plan.wsFlags */ struct { int nIn; /* Number of entries in aInLoop[] */ struct InLoop { int iCur; /* The VDBE cursor used by this IN operator */ int addrInTop; /* Top of the IN loop */ } *aInLoop; /* Information about each nested IN operator */ } in; /* Used when plan.wsFlags&WHERE_IN_ABLE */ Index *pCovidx; /* Possible covering index for WHERE_MULTI_OR */ } u; double rOptCost; /* "Optimal" cost for this level */ /* The following field is really not part of the current level. But | > | 1961 1962 1963 1964 1965 1966 1967 1968 1969 1970 1971 1972 1973 1974 1975 | int p1, p2; /* Operands of the opcode used to ends the loop */ union { /* Information that depends on plan.wsFlags */ struct { int nIn; /* Number of entries in aInLoop[] */ struct InLoop { int iCur; /* The VDBE cursor used by this IN operator */ int addrInTop; /* Top of the IN loop */ u8 eEndLoopOp; /* IN Loop terminator. OP_Next or OP_Prev */ } *aInLoop; /* Information about each nested IN operator */ } in; /* Used when plan.wsFlags&WHERE_IN_ABLE */ Index *pCovidx; /* Possible covering index for WHERE_MULTI_OR */ } u; double rOptCost; /* "Optimal" cost for this level */ /* The following field is really not part of the current level. But |
︙ | ︙ |
Changes to src/where.c.
︙ | ︙ | |||
3004 3005 3006 3007 3008 3009 3010 | /* 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 ){ | < < < < < < < < | 3004 3005 3006 3007 3008 3009 3010 3011 3012 3013 3014 3015 3016 3017 3018 | /* 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 ){ isEq = 0; }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; |
︙ | ︙ | |||
3782 3783 3784 3785 3786 3787 3788 3789 3790 3791 3792 3793 | iReg = iTarget; sqlite3VdbeAddOp2(v, OP_Null, 0, iReg); #ifndef SQLITE_OMIT_SUBQUERY }else{ int eType; int iTab; struct InLoop *pIn; assert( pX->op==TK_IN ); iReg = iTarget; eType = sqlite3FindInIndex(pParse, pX, 0); iTab = pX->iTable; | > | > | 3774 3775 3776 3777 3778 3779 3780 3781 3782 3783 3784 3785 3786 3787 3788 3789 3790 3791 3792 3793 3794 3795 3796 3797 3798 3799 3800 3801 3802 3803 3804 3805 3806 3807 3808 3809 3810 3811 3812 | iReg = iTarget; sqlite3VdbeAddOp2(v, OP_Null, 0, iReg); #ifndef SQLITE_OMIT_SUBQUERY }else{ int eType; int iTab; struct InLoop *pIn; u8 bRev = (pLevel->plan.wsFlags & WHERE_REVERSE)!=0; assert( pX->op==TK_IN ); iReg = iTarget; eType = sqlite3FindInIndex(pParse, pX, 0); iTab = pX->iTable; sqlite3VdbeAddOp2(v, bRev ? OP_Last : OP_Rewind, iTab, 0); assert( pLevel->plan.wsFlags & WHERE_IN_ABLE ); if( pLevel->u.in.nIn==0 ){ pLevel->addrNxt = sqlite3VdbeMakeLabel(v); } pLevel->u.in.nIn++; pLevel->u.in.aInLoop = sqlite3DbReallocOrFree(pParse->db, pLevel->u.in.aInLoop, sizeof(pLevel->u.in.aInLoop[0])*pLevel->u.in.nIn); pIn = pLevel->u.in.aInLoop; if( pIn ){ pIn += pLevel->u.in.nIn - 1; pIn->iCur = iTab; if( eType==IN_INDEX_ROWID ){ pIn->addrInTop = sqlite3VdbeAddOp2(v, OP_Rowid, iTab, iReg); }else{ pIn->addrInTop = sqlite3VdbeAddOp3(v, OP_Column, iTab, 0, iReg); } pIn->eEndLoopOp = bRev ? OP_Prev : OP_Next; sqlite3VdbeAddOp1(v, OP_IsNull, iReg); }else{ pLevel->u.in.nIn = 0; } #endif } disableTerm(pLevel, pTerm); |
︙ | ︙ | |||
5546 5547 5548 5549 5550 5551 5552 | } if( pLevel->plan.wsFlags & WHERE_IN_ABLE && pLevel->u.in.nIn>0 ){ struct InLoop *pIn; int j; sqlite3VdbeResolveLabel(v, pLevel->addrNxt); for(j=pLevel->u.in.nIn, pIn=&pLevel->u.in.aInLoop[j-1]; j>0; j--, pIn--){ sqlite3VdbeJumpHere(v, pIn->addrInTop+1); | | | 5540 5541 5542 5543 5544 5545 5546 5547 5548 5549 5550 5551 5552 5553 5554 | } if( pLevel->plan.wsFlags & WHERE_IN_ABLE && pLevel->u.in.nIn>0 ){ struct InLoop *pIn; int j; sqlite3VdbeResolveLabel(v, pLevel->addrNxt); for(j=pLevel->u.in.nIn, pIn=&pLevel->u.in.aInLoop[j-1]; j>0; j--, pIn--){ sqlite3VdbeJumpHere(v, pIn->addrInTop+1); sqlite3VdbeAddOp2(v, pIn->eEndLoopOp, pIn->iCur, pIn->addrInTop); sqlite3VdbeJumpHere(v, pIn->addrInTop-1); } sqlite3DbFree(db, pLevel->u.in.aInLoop); } sqlite3VdbeResolveLabel(v, pLevel->addrBrk); if( pLevel->iLeftJoin ){ int addr; |
︙ | ︙ |
Changes to test/where.test.
︙ | ︙ | |||
394 395 396 397 398 399 400 | 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; } | | | 394 395 396 397 398 399 400 401 402 403 404 405 406 407 408 | 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 12} 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 { |
︙ | ︙ | |||
463 464 465 466 467 468 469 470 471 472 473 474 475 476 | } } {2 1 9 8} do_test where-5.15 { count { SELECT * FROM t1 WHERE x IN (1,7) AND y IN (9,16) ORDER BY 1; } } {2 1 9 3 1 16 11} } # This procedure executes the SQL. Then it checks to see if the OP_Sort # opcode was executed. If an OP_Sort did occur, then "sort" is appended # to the result. If no OP_Sort happened, then "nosort" is appended. # # This procedure is used to check to make sure sorting is or is not | > > > > > > > > > > > > > > > > > > > > > > > > | 463 464 465 466 467 468 469 470 471 472 473 474 475 476 477 478 479 480 481 482 483 484 485 486 487 488 489 490 491 492 493 494 495 496 497 498 499 500 | } } {2 1 9 8} do_test where-5.15 { count { SELECT * FROM t1 WHERE x IN (1,7) AND y IN (9,16) ORDER BY 1; } } {2 1 9 3 1 16 11} do_test where-5.100 { db eval { SELECT w, x, y FROM t1 WHERE x IN (1,5) AND y IN (9,8,3025,1000,3969) ORDER BY x, y } } {2 1 9 54 5 3025 62 5 3969} do_test where-5.101 { db eval { SELECT w, x, y FROM t1 WHERE x IN (1,5) AND y IN (9,8,3025,1000,3969) ORDER BY x DESC, y DESC } } {62 5 3969 54 5 3025 2 1 9} do_test where-5.102 { db eval { SELECT w, x, y FROM t1 WHERE x IN (1,5) AND y IN (9,8,3025,1000,3969) ORDER BY x DESC, y } } {54 5 3025 62 5 3969 2 1 9} do_test where-5.103 { db eval { SELECT w, x, y FROM t1 WHERE x IN (1,5) AND y IN (9,8,3025,1000,3969) ORDER BY x, y DESC } } {2 1 9 62 5 3969 54 5 3025} } # This procedure executes the SQL. Then it checks to see if the OP_Sort # opcode was executed. If an OP_Sort did occur, then "sort" is appended # to the result. If no OP_Sort happened, then "nosort" is appended. # # This procedure is used to check to make sure sorting is or is not |
︙ | ︙ | |||
531 532 533 534 535 536 537 | 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 } | | | 555 556 557 558 559 560 561 562 563 564 565 566 567 568 569 | 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 nosort} } 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.
︙ | ︙ | |||
178 179 180 181 182 183 184 | 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 } | | | 178 179 180 181 182 183 184 185 186 187 188 189 190 191 192 | 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 nosort 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 } |
︙ | ︙ | |||
242 243 244 245 246 247 248 | 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 } | | | 242 243 244 245 246 247 248 249 250 251 252 253 254 255 256 | 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 nosort t1 i1w} } # Verify that OR clauses get translated into IN operators. # set ::idx {} ifcapable subquery {set ::idx i1w} do_test where2-6.1.1 { |
︙ | ︙ |