From 85eeb692f3f5b4917ac26894bcfc25223f7506c7 Mon Sep 17 00:00:00 2001 From: drh Date: Wed, 21 Dec 2005 03:16:42 +0000 Subject: [PATCH] Progress toward decending indices. (CVS 2839) FossilOrigin-Name: 112a34b8dcceb39540cb0cd629e264a867400bfb --- manifest | 16 ++++++++-------- manifest.uuid | 2 +- src/build.c | 15 +++++++-------- src/where.c | 51 ++++++++++++++++++++++++++++++++++++--------------- 4 files changed, 52 insertions(+), 32 deletions(-) diff --git a/manifest b/manifest index e400b55a20..898f81d356 100644 --- a/manifest +++ b/manifest @@ -1,5 +1,5 @@ -C Include\ssqlite3_release_memory()\scode\swhen\sSQLITE_MEMDEBUG\sis\snot\sdefined.\s(CVS\s2838) -D 2005-12-20T14:38:00 +C Progress\stoward\sdecending\sindices.\s(CVS\s2839) +D 2005-12-21T03:16:43 F Makefile.in e3c6b3a38d734d41574c04f2fc90d18de2b87102 F Makefile.linux-gcc aee18d8a05546dcf1888bd4547e442008a49a092 F README 9c4e2d6706bdcc3efdd773ce752a8cdab4f90028 @@ -36,7 +36,7 @@ F src/attach.c ee70131f128d31a9c6dcb8824e8471c91b18601a F src/auth.c 31e2304bef67f44d635655f44234387ea7d21454 F src/btree.c 300fd8342f4d9f75829a8a96d60578592f3dee79 F src/btree.h 8ff86378bb5af0cde282614c16bf0c0190b6d216 -F src/build.c 178a5c36365b5ec89a4a29a74186583f503c10fa +F src/build.c 502479f9b9b5cc0f7f629289f82e98c54c1789d5 F src/callback.c 62066afd516f220575e81b1a1239ab92a2eae252 F src/complete.c df1681cef40dec33a286006981845f87b194e7a4 F src/date.c bb079317bff6a2b78aba5c0d2ddae5f6f03acfb7 @@ -91,7 +91,7 @@ F src/vdbeapi.c b270b680cbc5d20b5a1abfdb08339667985df94e F src/vdbeaux.c c38276e0c95d9ed9c35bab195faea3d57e787aea F src/vdbefifo.c 9efb94c8c3f4c979ebd0028219483f88e57584f5 F src/vdbemem.c deba8d6e3727643924b210a8c531a496c2b8d386 -F src/where.c 269569f380ddc018518f67765fe2f0d3c8760e28 +F src/where.c 4db62a60cda1c267947b975daf177b3c99e90d2b F tclinstaller.tcl 046e3624671962dc50f0481d7c25b38ef803eb42 F test/all.test 55706917a12cd616440d50c35323747b4a9f03c3 F test/alter.test 9d6837a3d946b73df692b7cef2a7644d2e2f6bc6 @@ -329,7 +329,7 @@ F www/tclsqlite.tcl ddcf912ea48695603c8ed7efb29f0812ef8d1b49 F www/vdbe.tcl 87a31ace769f20d3627a64fa1fade7fed47b90d0 F www/version3.tcl a99cf5f6d8bd4d5537584a2b342f0fb9fa601d8b F www/whentouse.tcl 97e2b5cd296f7d8057e11f44427dea8a4c2db513 -P c2c5285442f4558dfca61b52f31b5a9cbefaed10 -R c41e18b7f54b841b391c4a1c2c7de45d -U danielk1977 -Z 694bd7f2618622c7a35a61895f0abc86 +P 77a37ceca7792e6cda6810e3387e6dda14a5c7ec +R 72d096b7221b434491091a1e91cf3acd +U drh +Z db01996f6f52833d4c472a9960d2c37e diff --git a/manifest.uuid b/manifest.uuid index 32b49ebf0e..f358883775 100644 --- a/manifest.uuid +++ b/manifest.uuid @@ -1 +1 @@ -77a37ceca7792e6cda6810e3387e6dda14a5c7ec \ No newline at end of file +112a34b8dcceb39540cb0cd629e264a867400bfb \ No newline at end of file diff --git a/src/build.c b/src/build.c index 32d4bfd054..f771fb689c 100644 --- a/src/build.c +++ b/src/build.c @@ -22,7 +22,7 @@ ** COMMIT ** ROLLBACK ** -** $Id: build.c,v 1.358 2005/12/16 01:06:17 drh Exp $ +** $Id: build.c,v 1.359 2005/12/21 03:16:43 drh Exp $ */ #include "sqliteInt.h" #include @@ -2113,7 +2113,6 @@ void sqlite3CreateIndex( int iDb; /* Index of the database that is being written */ Token *pName = 0; /* Unqualified name of the index to create */ struct ExprList_item *pListItem; /* For looping over pList */ - CollSeq *pCollSeq; /* Collating sequence for one index column */ if( pParse->nErr || sqlite3Tsd()->mallocFailed ) goto exit_create_index; @@ -2277,7 +2276,7 @@ void sqlite3CreateIndex( for(i=0, pListItem=pList->a; inExpr; i++, pListItem++){ const char *zColName = pListItem->zName; Column *pTabCol; - int sortOrder; + int requestedSortOrder; for(j=0, pTabCol=pTab->aCol; jnCol; j++, pTabCol++){ if( sqlite3StrICmp(zColName, pTabCol->zName)==0 ) break; } @@ -2299,11 +2298,11 @@ void sqlite3CreateIndex( ){ goto exit_create_index; } - sortOrder = pListItem->sortOrder; - pDb->descIndex |= sortOrder; - sortOrder &= sortOrderMask; - pIndex->keyInfo.aSortOrder[i] = sortOrder; - descSeen |= sortOrder; + requestedSortOrder = pListItem->sortOrder; + pDb->descIndex |= requestedSortOrder; + requestedSortOrder &= sortOrderMask; + pIndex->keyInfo.aSortOrder[i] = requestedSortOrder; + descSeen |= requestedSortOrder; } pIndex->keyInfo.nField = pList->nExpr; sqlite3DefaultRowEst(pIndex); diff --git a/src/where.c b/src/where.c index d643bde05f..71ad86ef16 100644 --- a/src/where.c +++ b/src/where.c @@ -16,7 +16,7 @@ ** so is applicable. Because this module is responsible for selecting ** indices, you might also think of this module as the "query optimizer". ** -** $Id: where.c,v 1.187 2005/12/07 06:27:44 danielk1977 Exp $ +** $Id: where.c,v 1.188 2005/12/21 03:16:43 drh Exp $ */ #include "sqliteInt.h" @@ -785,7 +785,7 @@ static int isSortingIndex( int *pbRev /* Set to 1 if ORDER BY is DESC */ ){ int i, j; /* Loop counters */ - int sortOrder = SQLITE_SO_ASC; /* Which direction we are sorting */ + int sortOrder = 0; /* XOR of index and ORDER BY sort direction */ int nTerm; /* Number of ORDER BY terms */ struct ExprList_item *pTerm; /* A term of the ORDER BY clause */ sqlite3 *db = pParse->db; @@ -800,6 +800,7 @@ static int isSortingIndex( for(i=j=0, pTerm=pOrderBy->a; jnColumn; i++){ Expr *pExpr; /* The expression of the ORDER BY pTerm */ CollSeq *pColl; /* The collating sequence of pExpr */ + int termSortOrder; /* Sort order for this term */ pExpr = pTerm->pExpr; if( pExpr->op!=TK_COLUMN || pExpr->iTable!=base ){ @@ -823,14 +824,18 @@ static int isSortingIndex( return 0; } } + assert( pIdx->keyInfo.aSortOrder!=0 ); + assert( pTerm->sortOrder==0 || pTerm->sortOrder==1 ); + assert( pIdx->keyInfo.aSortOrder[i]==0 || pIdx->keyInfo.aSortOrder[i]==1 ); + termSortOrder = pIdx->keyInfo.aSortOrder[i] ^ pTerm->sortOrder; if( i>nEqCol ){ - if( pTerm->sortOrder!=sortOrder ){ + if( termSortOrder!=sortOrder ){ /* Indices can only be used if all ORDER BY terms past the ** equality constraints are all either DESC or ASC. */ return 0; } }else{ - sortOrder = pTerm->sortOrder; + sortOrder = termSortOrder; } j++; pTerm++; @@ -840,7 +845,7 @@ static int isSortingIndex( ** are covered. */ if( j>=nTerm ){ - *pbRev = sortOrder==SQLITE_SO_DESC; + *pbRev = sortOrder!=0; return 1; } return 0; @@ -1710,7 +1715,9 @@ WhereInfo *sqlite3WhereBegin( */ int start; int nEq = pLevel->nEq; - int leFlag=0, geFlag=0; + int topEq=0; /* True if top limit uses ==. False is strictly < */ + int btmEq=0; /* True if btm limit uses ==. False if strictly > */ + int topOp, btmOp; /* Operators for the top and bottom search bounds */ int testOp; int topLimit = (pLevel->flags & WHERE_TOP_LIMIT)!=0; int btmLimit = (pLevel->flags & WHERE_BTM_LIMIT)!=0; @@ -1728,6 +1735,20 @@ WhereInfo *sqlite3WhereBegin( sqlite3VdbeAddOp(v, OP_Dup, nEq-1, 0); } + /* Figure out what comparison operators to use for top and bottom + ** search bounds. For an ascending index, the bottom bound is a > or >= + ** operator and the top bound is a < or <= operator. For a descending + ** index the operators are reversed. + */ + if( pIdx->keyInfo.aSortOrder[nEq]==SQLITE_SO_ASC ){ + topOp = WO_LT|WO_LE; + btmOp = WO_GT|WO_GE; + }else{ + topOp = WO_GT|WO_GE; + btmOp = WO_LT|WO_LE; + SWAP(int, topLimit, btmLimit); + } + /* Generate the termination key. This is the key value that ** will end the search. There is no termination key if there ** are no equality terms and no "X<..." term. @@ -1738,24 +1759,24 @@ WhereInfo *sqlite3WhereBegin( if( topLimit ){ Expr *pX; int k = pIdx->aiColumn[j]; - pTerm = findTerm(&wc, iCur, k, notReady, WO_LT|WO_LE, pIdx); + pTerm = findTerm(&wc, iCur, k, notReady, topOp, pIdx); assert( pTerm!=0 ); pX = pTerm->pExpr; assert( (pTerm->flags & TERM_CODED)==0 ); sqlite3ExprCode(pParse, pX->pRight); - leFlag = pX->op==TK_LE; + topEq = pTerm->operator & (WO_LE|WO_GE); disableTerm(pLevel, pTerm); testOp = OP_IdxGE; }else{ testOp = nEq>0 ? OP_IdxGE : OP_Noop; - leFlag = 1; + topEq = 1; } if( testOp!=OP_Noop ){ int nCol = nEq + topLimit; pLevel->iMem = pParse->nMem++; buildIndexProbe(v, nCol, brk, pIdx); if( bRev ){ - int op = leFlag ? OP_MoveLe : OP_MoveLt; + int op = topEq ? OP_MoveLe : OP_MoveLt; sqlite3VdbeAddOp(v, op, iIdxCur, brk); }else{ sqlite3VdbeAddOp(v, OP_MemStore, pLevel->iMem, 1); @@ -1776,15 +1797,15 @@ WhereInfo *sqlite3WhereBegin( if( btmLimit ){ Expr *pX; int k = pIdx->aiColumn[j]; - pTerm = findTerm(&wc, iCur, k, notReady, WO_GT|WO_GE, pIdx); + pTerm = findTerm(&wc, iCur, k, notReady, btmOp, pIdx); assert( pTerm!=0 ); pX = pTerm->pExpr; assert( (pTerm->flags & TERM_CODED)==0 ); sqlite3ExprCode(pParse, pX->pRight); - geFlag = pX->op==TK_GE; + btmEq = pTerm->operator & (WO_LE|WO_GE); disableTerm(pLevel, pTerm); }else{ - geFlag = 1; + btmEq = 1; } if( nEq>0 || btmLimit ){ int nCol = nEq + btmLimit; @@ -1794,7 +1815,7 @@ WhereInfo *sqlite3WhereBegin( sqlite3VdbeAddOp(v, OP_MemStore, pLevel->iMem, 1); testOp = OP_IdxLT; }else{ - int op = geFlag ? OP_MoveGe : OP_MoveGt; + int op = btmEq ? OP_MoveGe : OP_MoveGt; sqlite3VdbeAddOp(v, op, iIdxCur, brk); } }else if( bRev ){ @@ -1811,7 +1832,7 @@ WhereInfo *sqlite3WhereBegin( if( testOp!=OP_Noop ){ sqlite3VdbeAddOp(v, OP_MemLoad, pLevel->iMem, 0); sqlite3VdbeAddOp(v, testOp, iIdxCur, brk); - if( (leFlag && !bRev) || (!geFlag && bRev) ){ + if( (topEq && !bRev) || (!btmEq && bRev) ){ sqlite3VdbeChangeP3(v, -1, "+", P3_STATIC); } } -- 2.47.2