Index: VERSION ================================================================== --- VERSION +++ VERSION @@ -1,1 +1,1 @@ -3.8.4.1 +3.8.5 Index: configure ================================================================== --- configure +++ configure @@ -1,8 +1,8 @@ #! /bin/sh # Guess values for system-dependent variables and create Makefiles. -# Generated by GNU Autoconf 2.62 for sqlite 3.8.4.1. +# Generated by GNU Autoconf 2.62 for sqlite 3.8.5. # # Copyright (C) 1992, 1993, 1994, 1995, 1996, 1998, 1999, 2000, 2001, # 2002, 2003, 2004, 2005, 2006, 2007, 2008 Free Software Foundation, Inc. # This configure script is free software; the Free Software Foundation # gives unlimited permission to copy, distribute and modify it. @@ -741,12 +741,12 @@ SHELL=${CONFIG_SHELL-/bin/sh} # Identity of this package. PACKAGE_NAME='sqlite' PACKAGE_TARNAME='sqlite' -PACKAGE_VERSION='3.8.4.1' -PACKAGE_STRING='sqlite 3.8.4.1' +PACKAGE_VERSION='3.8.5' +PACKAGE_STRING='sqlite 3.8.5' PACKAGE_BUGREPORT='' # Factoring default headers for most tests. ac_includes_default="\ #include @@ -1481,11 +1481,11 @@ # if test "$ac_init_help" = "long"; then # Omit some internal or obsolete options to make the list less imposing. # This message is too long to be a string in the A/UX 3.1 sh. cat <<_ACEOF -\`configure' configures sqlite 3.8.4.1 to adapt to many kinds of systems. +\`configure' configures sqlite 3.8.5 to adapt to many kinds of systems. Usage: $0 [OPTION]... [VAR=VALUE]... To assign environment variables (e.g., CC, CFLAGS...), specify them as VAR=VALUE. See below for descriptions of some of the useful variables. @@ -1546,11 +1546,11 @@ _ACEOF fi if test -n "$ac_init_help"; then case $ac_init_help in - short | recursive ) echo "Configuration of sqlite 3.8.4.1:";; + short | recursive ) echo "Configuration of sqlite 3.8.5:";; esac cat <<\_ACEOF Optional Features: --disable-option-checking ignore unrecognized --enable/--with options @@ -1662,11 +1662,11 @@ fi test -n "$ac_init_help" && exit $ac_status if $ac_init_version; then cat <<\_ACEOF -sqlite configure 3.8.4.1 +sqlite configure 3.8.5 generated by GNU Autoconf 2.62 Copyright (C) 1992, 1993, 1994, 1995, 1996, 1998, 1999, 2000, 2001, 2002, 2003, 2004, 2005, 2006, 2007, 2008 Free Software Foundation, Inc. This configure script is free software; the Free Software Foundation @@ -1676,11 +1676,11 @@ fi cat >config.log <<_ACEOF This file contains any messages produced by compilers while running configure, to aid debugging if configure makes a mistake. -It was created by sqlite $as_me 3.8.4.1, which was +It was created by sqlite $as_me 3.8.5, which was generated by GNU Autoconf 2.62. Invocation command line was $ $0 $@ _ACEOF @@ -14019,11 +14019,11 @@ # Save the log message, to keep $[0] and so on meaningful, and to # report actual input values of CONFIG_FILES etc. instead of their # values after options handling. ac_log=" -This file was extended by sqlite $as_me 3.8.4.1, which was +This file was extended by sqlite $as_me 3.8.5, which was generated by GNU Autoconf 2.62. Invocation command line was CONFIG_FILES = $CONFIG_FILES CONFIG_HEADERS = $CONFIG_HEADERS CONFIG_LINKS = $CONFIG_LINKS @@ -14072,11 +14072,11 @@ Report bugs to ." _ACEOF cat >>$CONFIG_STATUS <<_ACEOF || ac_write_fail=1 ac_cs_version="\\ -sqlite config.status 3.8.4.1 +sqlite config.status 3.8.5 configured by $0, generated by GNU Autoconf 2.62, with options \\"`$as_echo "$ac_configure_args" | sed 's/^ //; s/[\\""\`\$]/\\\\&/g'`\\" Copyright (C) 2008 Free Software Foundation, Inc. This config.status script is free software; the Free Software Foundation Index: src/btree.c ================================================================== --- src/btree.c +++ src/btree.c @@ -744,24 +744,36 @@ ** Determine whether or not a cursor has moved from the position it ** was last placed at. Cursors can move when the row they are pointing ** at is deleted out from under them. ** ** This routine returns an error code if something goes wrong. The -** integer *pHasMoved is set to one if the cursor has moved and 0 if not. +** integer *pHasMoved is set as follows: +** +** 0: The cursor is unchanged +** 1: The cursor is still pointing at the same row, but the pointers +** returned by sqlite3BtreeKeyFetch() or sqlite3BtreeDataFetch() +** might now be invalid because of a balance() or other change to the +** b-tree. +** 2: The cursor is no longer pointing to the row. The row might have +** been deleted out from under the cursor. */ int sqlite3BtreeCursorHasMoved(BtCursor *pCur, int *pHasMoved){ int rc; + if( pCur->eState==CURSOR_VALID ){ + *pHasMoved = 0; + return SQLITE_OK; + } rc = restoreCursorPosition(pCur); if( rc ){ - *pHasMoved = 1; + *pHasMoved = 2; return rc; } if( pCur->eState!=CURSOR_VALID || NEVER(pCur->skipNext!=0) ){ + *pHasMoved = 2; + }else{ *pHasMoved = 1; - }else{ - *pHasMoved = 0; } return SQLITE_OK; } #ifndef SQLITE_OMIT_AUTOVACUUM @@ -2159,10 +2171,11 @@ sqlite3PagerSetCachesize(pBt->pPager, mxPage); sqlite3BtreeLeave(p); return SQLITE_OK; } +#if SQLITE_MAX_MMAP_SIZE>0 /* ** Change the limit on the amount of the database file that may be ** memory mapped. */ int sqlite3BtreeSetMmapLimit(Btree *p, sqlite3_int64 szMmap){ @@ -2171,10 +2184,11 @@ sqlite3BtreeEnter(p); sqlite3PagerSetMmapLimit(pBt->pPager, szMmap); sqlite3BtreeLeave(p); return SQLITE_OK; } +#endif /* SQLITE_MAX_MMAP_SIZE>0 */ /* ** Change the way data is synced to disk in order to increase or decrease ** how well the database resists damage due to OS crashes and power ** failures. Level 1 is the same as asynchronous (no syncs() occur and @@ -4184,14 +4198,17 @@ assert( pCur!=0 && pCur->iPage>=0 && pCur->apPage[pCur->iPage]); assert( pCur->eState==CURSOR_VALID ); assert( sqlite3_mutex_held(pCur->pBtree->db->mutex) ); assert( cursorHoldsMutex(pCur) ); assert( pCur->aiIdx[pCur->iPage]apPage[pCur->iPage]->nCell ); + assert( pCur->info.nSize>0 ); +#if 0 if( pCur->info.nSize==0 ){ btreeParseCell(pCur->apPage[pCur->iPage], pCur->aiIdx[pCur->iPage], &pCur->info); } +#endif *pAmt = pCur->info.nLocal; return (void*)(pCur->info.pCell + pCur->info.nHeader); } @@ -7420,10 +7437,19 @@ rc = clearDatabasePage(pBt, (Pgno)iTable, 0, pnChange); } sqlite3BtreeLeave(p); return rc; } + +/* +** Delete all information from the single table that pCur is open on. +** +** This routine only work for pCur on an ephemeral table. +*/ +int sqlite3BtreeClearTableOfCursor(BtCursor *pCur){ + return sqlite3BtreeClearTable(pCur->pBtree, pCur->pgnoRoot, 0); +} /* ** Erase all information in a table and add the root of the table to ** the freelist. Except, the root of the principle table (the one on ** page 1) is never added to the freelist. Index: src/btree.h ================================================================== --- src/btree.h +++ src/btree.h @@ -61,11 +61,13 @@ #define BTREE_SINGLE 4 /* The file contains at most 1 b-tree */ #define BTREE_UNORDERED 8 /* Use of a hash implementation is OK */ int sqlite3BtreeClose(Btree*); int sqlite3BtreeSetCacheSize(Btree*,int); -int sqlite3BtreeSetMmapLimit(Btree*,sqlite3_int64); +#if SQLITE_MAX_MMAP_SIZE>0 + int sqlite3BtreeSetMmapLimit(Btree*,sqlite3_int64); +#endif int sqlite3BtreeSetPagerFlags(Btree*,unsigned); int sqlite3BtreeSyncDisabled(Btree*); int sqlite3BtreeSetPageSize(Btree *p, int nPagesize, int nReserve, int eFix); int sqlite3BtreeGetPageSize(Btree*); int sqlite3BtreeMaxPageCount(Btree*,int); @@ -111,10 +113,11 @@ #define BTREE_INTKEY 1 /* Table has only 64-bit signed integer keys */ #define BTREE_BLOBKEY 2 /* Table has keys only - no data */ int sqlite3BtreeDropTable(Btree*, int, int*); int sqlite3BtreeClearTable(Btree*, int, int*); +int sqlite3BtreeClearTableOfCursor(BtCursor*); void sqlite3BtreeTripAllCursors(Btree*, int); void sqlite3BtreeGetMeta(Btree *pBtree, int idx, u32 *pValue); int sqlite3BtreeUpdateMeta(Btree*, int idx, u32 value); Index: src/expr.c ================================================================== --- src/expr.c +++ src/expr.c @@ -31,10 +31,11 @@ ** SELECT * FROM t1 WHERE (select a from t1); */ char sqlite3ExprAffinity(Expr *pExpr){ int op; pExpr = sqlite3ExprSkipCollate(pExpr); + if( pExpr->flags & EP_Generic ) return SQLITE_AFF_NONE; op = pExpr->op; if( op==TK_SELECT ){ assert( pExpr->flags&EP_xIsSelect ); return sqlite3ExprAffinity(pExpr->x.pSelect->pEList->a[0].pExpr); } @@ -63,11 +64,15 @@ ** implements the COLLATE operator. ** ** If a memory allocation error occurs, that fact is recorded in pParse->db ** and the pExpr parameter is returned unchanged. */ -Expr *sqlite3ExprAddCollateToken(Parse *pParse, Expr *pExpr, Token *pCollName){ +Expr *sqlite3ExprAddCollateToken( + Parse *pParse, /* Parsing context */ + Expr *pExpr, /* Add the "COLLATE" clause to this expression */ + const Token *pCollName /* Name of collating sequence */ +){ if( pCollName->n>0 ){ Expr *pNew = sqlite3ExprAlloc(pParse->db, TK_COLLATE, pCollName, 1); if( pNew ){ pNew->pLeft = pExpr; pNew->flags |= EP_Collate|EP_Skip; @@ -116,10 +121,11 @@ sqlite3 *db = pParse->db; CollSeq *pColl = 0; Expr *p = pExpr; while( p ){ int op = p->op; + if( p->flags & EP_Generic ) break; if( op==TK_CAST || op==TK_UPLUS ){ p = p->pLeft; continue; } if( op==TK_COLLATE || (op==TK_REGISTER && p->op2==TK_COLLATE) ){ @@ -947,11 +953,10 @@ struct ExprList_item *pItem, *pOldItem; int i; if( p==0 ) return 0; pNew = sqlite3DbMallocRaw(db, sizeof(*pNew) ); if( pNew==0 ) return 0; - pNew->iECursor = 0; pNew->nExpr = i = p->nExpr; if( (flags & EXPRDUP_REDUCE)==0 ) for(i=1; inExpr; i+=i){} pNew->a = pItem = sqlite3DbMallocRaw(db, i*sizeof(p->a[0]) ); if( pItem==0 ){ sqlite3DbFree(db, pNew); @@ -1060,11 +1065,10 @@ pNew->iLimit = 0; pNew->iOffset = 0; pNew->selFlags = p->selFlags & ~SF_UsesEphemeral; pNew->addrOpenEphm[0] = -1; pNew->addrOpenEphm[1] = -1; - pNew->addrOpenEphm[2] = -1; pNew->nSelectRow = p->nSelectRow; pNew->pWith = withDup(db, p->pWith); return pNew; } #else @@ -1628,11 +1632,10 @@ eType = IN_INDEX_EPH; if( prNotFound ){ *prNotFound = rMayHaveNull = ++pParse->nMem; sqlite3VdbeAddOp2(v, OP_Null, 0, *prNotFound); }else{ - testcase( pParse->nQueryLoop>0 ); pParse->nQueryLoop = 0; if( pX->pLeft->iColumn<0 && !ExprHasProperty(pX, EP_xIsSelect) ){ eType = IN_INDEX_ROWID; } } @@ -2333,11 +2336,11 @@ */ void sqlite3ExprCodeMove(Parse *pParse, int iFrom, int iTo, int nReg){ int i; struct yColCache *p; assert( iFrom>=iTo+nReg || iFrom+nReg<=iTo ); - sqlite3VdbeAddOp3(pParse->pVdbe, OP_Move, iFrom, iTo, nReg-1); + sqlite3VdbeAddOp3(pParse->pVdbe, OP_Move, iFrom, iTo, nReg); for(i=0, p=pParse->aColCache; iiReg; if( x>=iFrom && xiReg += iTo-iFrom; } @@ -2734,11 +2737,11 @@ pDef->funcFlags & (OPFLAG_LENGTHARG|OPFLAG_TYPEOFARG); } } sqlite3ExprCachePush(pParse); /* Ticket 2ea2425d34be */ - sqlite3ExprCodeExprList(pParse, pFarg, r1, + sqlite3ExprCodeExprList(pParse, pFarg, r1, SQLITE_ECEL_DUP|SQLITE_ECEL_FACTOR); sqlite3ExprCachePop(pParse, 1); /* Ticket 2ea2425d34be */ }else{ r1 = 0; } Index: src/os_unix.c ================================================================== --- src/os_unix.c +++ src/os_unix.c @@ -321,10 +321,11 @@ return geteuid() ? 0 : fchown(fd,uid,gid); } /* Forward reference */ static int openDirectory(const char*, int*); +static int unixGetpagesize(void); /* ** Many system calls are accessed through pointer-to-functions so that ** they may be overridden at runtime to facilitate fault injection during ** testing and sandboxing. The following array holds the names and pointers @@ -443,10 +444,13 @@ #else { "mremap", (sqlite3_syscall_ptr)0, 0 }, #endif #define osMremap ((void*(*)(void*,size_t,size_t,int,...))aSyscall[23].pCurrent) #endif + + { "getpagesize", (sqlite3_syscall_ptr)unixGetpagesize, 0 }, +#define osGetpagesize ((int(*)(void))aSyscall[24].pCurrent) }; /* End of the overrideable system calls */ /* ** This is the xSetSystemCall() method of sqlite3_vfs for all of the @@ -4103,10 +4107,40 @@ #endif return rc; } +/* +** Return the system page size. +** +** This function should not be called directly by other code in this file. +** Instead, it should be called via macro osGetpagesize(). +*/ +static int unixGetpagesize(void){ +#if defined(_BSD_SOURCE) + return getpagesize(); +#else + return (int)sysconf(_SC_PAGESIZE); +#endif +} + +/* +** Return the minimum number of 32KB shm regions that should be mapped at +** a time, assuming that each mapping must be an integer multiple of the +** current system page-size. +** +** Usually, this is 1. The exception seems to be systems that are configured +** to use 64KB pages - in this case each mapping must cover at least two +** shm regions. +*/ +static int unixShmRegionPerMap(void){ + int shmsz = 32*1024; /* SHM region size */ + int pgsz = osGetpagesize(); /* System page size */ + assert( ((pgsz-1)&pgsz)==0 ); /* Page size must be a power of 2 */ + if( pgszpInode->pShmNode; assert( unixMutexHeld() ); if( p && p->nRef==0 ){ + int nShmPerMap = unixShmRegionPerMap(); int i; assert( p->pInode==pFd->pInode ); sqlite3_mutex_free(p->mutex); - for(i=0; inRegion; i++){ + for(i=0; inRegion; i+=nShmPerMap){ if( p->h>=0 ){ osMunmap(p->apRegion[i], p->szRegion); }else{ sqlite3_free(p->apRegion[i]); } @@ -4324,10 +4359,12 @@ ){ unixFile *pDbFd = (unixFile*)fd; unixShm *p; unixShmNode *pShmNode; int rc = SQLITE_OK; + int nShmPerMap = unixShmRegionPerMap(); + int nReqRegion; /* If the shared-memory file has not yet been opened, open it now. */ if( pDbFd->pShm==0 ){ rc = unixOpenSharedMemory(pDbFd); if( rc!=SQLITE_OK ) return rc; @@ -4339,13 +4376,16 @@ assert( szRegion==pShmNode->szRegion || pShmNode->nRegion==0 ); assert( pShmNode->pInode==pDbFd->pInode ); assert( pShmNode->h>=0 || pDbFd->pInode->bProcessLock==1 ); assert( pShmNode->h<0 || pDbFd->pInode->bProcessLock==0 ); - if( pShmNode->nRegion<=iRegion ){ + /* Minimum number of regions required to be mapped. */ + nReqRegion = ((iRegion+nShmPerMap) / nShmPerMap) * nShmPerMap; + + if( pShmNode->nRegionszRegion = szRegion; if( pShmNode->h>=0 ){ @@ -4390,21 +4430,23 @@ } } /* Map the requested memory region into this processes address space. */ apNew = (char **)sqlite3_realloc( - pShmNode->apRegion, (iRegion+1)*sizeof(char *) + pShmNode->apRegion, nReqRegion*sizeof(char *) ); if( !apNew ){ rc = SQLITE_IOERR_NOMEM; goto shmpage_out; } pShmNode->apRegion = apNew; - while(pShmNode->nRegion<=iRegion){ + while( pShmNode->nRegionh>=0 ){ - pMem = osMmap(0, szRegion, + pMem = osMmap(0, nMap, pShmNode->isReadonly ? PROT_READ : PROT_READ|PROT_WRITE, MAP_SHARED, pShmNode->h, szRegion*(i64)pShmNode->nRegion ); if( pMem==MAP_FAILED ){ rc = unixLogError(SQLITE_IOERR_SHMMAP, "mmap", pShmNode->zFilename); @@ -4416,12 +4458,15 @@ rc = SQLITE_NOMEM; goto shmpage_out; } memset(pMem, 0, szRegion); } - pShmNode->apRegion[pShmNode->nRegion] = pMem; - pShmNode->nRegion++; + + for(i=0; iapRegion[pShmNode->nRegion+i] = &((char*)pMem)[szRegion*i]; + } + pShmNode->nRegion += nShmPerMap; } } shmpage_out: if( pShmNode->nRegion>iRegion ){ @@ -4631,23 +4676,10 @@ pFd->mmapSize = 0; pFd->mmapSizeActual = 0; } } -/* -** Return the system page size. -*/ -static int unixGetPagesize(void){ -#if HAVE_MREMAP - return 512; -#elif defined(_BSD_SOURCE) - return getpagesize(); -#else - return (int)sysconf(_SC_PAGESIZE); -#endif -} - /* ** Attempt to set the size of the memory mapping maintained by file ** descriptor pFd to nNew bytes. Any existing mapping is discarded. ** ** If successful, this function sets the following variables: @@ -4680,12 +4712,16 @@ assert( MAP_FAILED!=0 ); if( (pFd->ctrlFlags & UNIXFILE_RDONLY)==0 ) flags |= PROT_WRITE; if( pOrig ){ - const int szSyspage = unixGetPagesize(); +#if HAVE_MREMAP + i64 nReuse = pFd->mmapSize; +#else + const int szSyspage = osGetpagesize(); i64 nReuse = (pFd->mmapSize & ~(szSyspage-1)); +#endif u8 *pReq = &pOrig[nReuse]; /* Unmap any pages of the existing mapping that cannot be reused. */ if( nReuse!=nOrig ){ osMunmap(pReq, nOrig-nReuse); @@ -7427,11 +7463,11 @@ }; unsigned int i; /* Loop counter */ /* Double-check that the aSyscall[] array has been constructed ** correctly. See ticket [bb3a86e890c8e96ab] */ - assert( ArraySize(aSyscall)==24 ); + assert( ArraySize(aSyscall)==25 ); /* Register all VFSes defined in the aVfs[] array */ for(i=0; i<(sizeof(aVfs)/sizeof(sqlite3_vfs)); i++){ sqlite3_vfs_register(&aVfs[i], i==0); } Index: src/parse.y ================================================================== --- src/parse.y +++ src/parse.y @@ -1018,10 +1018,37 @@ ** simplify to constants 0 (false) and 1 (true), respectively, ** regardless of the value of expr1. */ A.pExpr = sqlite3PExpr(pParse, TK_INTEGER, 0, 0, &sqlite3IntTokens[N]); sqlite3ExprDelete(pParse->db, X.pExpr); + }else if( Y->nExpr==1 ){ + /* Expressions of the form: + ** + ** expr1 IN (?1) + ** expr1 NOT IN (?2) + ** + ** with exactly one value on the RHS can be simplified to something + ** like this: + ** + ** expr1 == ?1 + ** expr1 <> ?2 + ** + ** But, the RHS of the == or <> is marked with the EP_Generic flag + ** so that it may not contribute to the computation of comparison + ** affinity or the collating sequence to use for comparison. Otherwise, + ** the semantics would be subtly different from IN or NOT IN. + */ + Expr *pRHS = Y->a[0].pExpr; + Y->a[0].pExpr = 0; + sqlite3ExprListDelete(pParse->db, Y); + /* pRHS cannot be NULL because a malloc error would have been detected + ** before now and control would have never reached this point */ + if( ALWAYS(pRHS) ){ + pRHS->flags &= ~EP_Collate; + pRHS->flags |= EP_Generic; + } + A.pExpr = sqlite3PExpr(pParse, N ? TK_NE : TK_EQ, X.pExpr, pRHS, 0); }else{ A.pExpr = sqlite3PExpr(pParse, TK_IN, X.pExpr, 0, 0); if( A.pExpr ){ A.pExpr->x.pList = Y; sqlite3ExprSetHeight(pParse, A.pExpr); Index: src/pragma.c ================================================================== --- src/pragma.c +++ src/pragma.c @@ -1873,11 +1873,11 @@ sqlite3VdbeChangeP5(v, (u8)i); addr = sqlite3VdbeAddOp1(v, OP_IsNull, 2); VdbeCoverage(v); sqlite3VdbeAddOp4(v, OP_String8, 0, 3, 0, sqlite3MPrintf(db, "*** in database %s ***\n", db->aDb[i].zName), P4_DYNAMIC); - sqlite3VdbeAddOp2(v, OP_Move, 2, 4); + sqlite3VdbeAddOp3(v, OP_Move, 2, 4, 1); sqlite3VdbeAddOp3(v, OP_Concat, 4, 3, 2); sqlite3VdbeAddOp2(v, OP_ResultRow, 2, 1); sqlite3VdbeJumpHere(v, addr); /* Make sure all the indices are constructed correctly. Index: src/printf.c ================================================================== --- src/printf.c +++ src/printf.c @@ -132,24 +132,10 @@ *val = (*val - d)*10.0; return (char)digit; } #endif /* SQLITE_OMIT_FLOATING_POINT */ -/* -** Append N space characters to the given string buffer. -*/ -void sqlite3AppendSpace(StrAccum *pAccum, int N){ - static const char zSpaces[] = " "; - while( N>=(int)sizeof(zSpaces)-1 ){ - sqlite3StrAccumAppend(pAccum, zSpaces, sizeof(zSpaces)-1); - N -= sizeof(zSpaces)-1; - } - if( N>0 ){ - sqlite3StrAccumAppend(pAccum, zSpaces, N); - } -} - /* ** Set the StrAccum object to an error mode. */ static void setStrAccumError(StrAccum *p, u8 eError){ p->accError = eError; @@ -235,15 +221,13 @@ }else{ bArgList = useIntern = 0; } for(; (c=(*fmt))!=0; ++fmt){ if( c!='%' ){ - int amt; bufpt = (char *)fmt; - amt = 1; - while( (c=(*++fmt))!='%' && c!=0 ) amt++; - sqlite3StrAccumAppend(pAccum, bufpt, amt); + while( (c=(*++fmt))!='%' && c!=0 ){}; + sqlite3StrAccumAppend(pAccum, bufpt, (int)(fmt - bufpt)); if( c==0 ) break; } if( (c=(*++fmt))==0 ){ sqlite3StrAccumAppend(pAccum, "%", 1); break; @@ -420,14 +404,12 @@ } *(--bufpt) = zOrd[x*2+1]; *(--bufpt) = zOrd[x*2]; } { - register const char *cset; /* Use registers for speed */ - register int base; - cset = &aDigits[infop->charset]; - base = infop->base; + const char *cset = &aDigits[infop->charset]; + u8 base = infop->base; do{ /* Convert to ascii */ *(--bufpt) = cset[longvalue%base]; longvalue = longvalue/base; }while( longvalue>0 ); } @@ -727,77 +709,102 @@ /* ** The text of the conversion is pointed to by "bufpt" and is ** "length" characters long. The field width is "width". Do ** the output. */ - if( !flag_leftjustify ){ - register int nspace; - nspace = width-length; - if( nspace>0 ){ - sqlite3AppendSpace(pAccum, nspace); - } - } - if( length>0 ){ - sqlite3StrAccumAppend(pAccum, bufpt, length); - } - if( flag_leftjustify ){ - register int nspace; - nspace = width-length; - if( nspace>0 ){ - sqlite3AppendSpace(pAccum, nspace); - } - } + width -= length; + if( width>0 && !flag_leftjustify ) sqlite3AppendSpace(pAccum, width); + sqlite3StrAccumAppend(pAccum, bufpt, length); + if( width>0 && flag_leftjustify ) sqlite3AppendSpace(pAccum, width); + if( zExtra ) sqlite3_free(zExtra); }/* End for loop over the format string */ } /* End of function */ /* -** Append N bytes of text from z to the StrAccum object. +** Enlarge the memory allocation on a StrAccum object so that it is +** able to accept at least N more bytes of text. +** +** Return the number of bytes of text that StrAccum is able to accept +** after the attempted enlargement. The value returned might be zero. +*/ +static int sqlite3StrAccumEnlarge(StrAccum *p, int N){ + char *zNew; + assert( p->nChar+N >= p->nAlloc ); /* Only called if really needed */ + if( p->accError ){ + testcase(p->accError==STRACCUM_TOOBIG); + testcase(p->accError==STRACCUM_NOMEM); + return 0; + } + if( !p->useMalloc ){ + N = p->nAlloc - p->nChar - 1; + setStrAccumError(p, STRACCUM_TOOBIG); + return N; + }else{ + char *zOld = (p->zText==p->zBase ? 0 : p->zText); + i64 szNew = p->nChar; + szNew += N + 1; + if( szNew > p->mxAlloc ){ + sqlite3StrAccumReset(p); + setStrAccumError(p, STRACCUM_TOOBIG); + return 0; + }else{ + p->nAlloc = (int)szNew; + } + if( p->useMalloc==1 ){ + zNew = sqlite3DbRealloc(p->db, zOld, p->nAlloc); + }else{ + zNew = sqlite3_realloc(zOld, p->nAlloc); + } + if( zNew ){ + if( zOld==0 && p->nChar>0 ) memcpy(zNew, p->zText, p->nChar); + p->zText = zNew; + }else{ + sqlite3StrAccumReset(p); + setStrAccumError(p, STRACCUM_NOMEM); + return 0; + } + } + return N; +} + +/* +** Append N space characters to the given string buffer. +*/ +void sqlite3AppendSpace(StrAccum *p, int N){ + if( p->nChar+N >= p->nAlloc && (N = sqlite3StrAccumEnlarge(p, N))<=0 ) return; + while( (N--)>0 ) p->zText[p->nChar++] = ' '; +} + +/* +** The StrAccum "p" is not large enough to accept N new bytes of z[]. +** So enlarge if first, then do the append. +** +** This is a helper routine to sqlite3StrAccumAppend() that does special-case +** work (enlarging the buffer) using tail recursion, so that the +** sqlite3StrAccumAppend() routine can use fast calling semantics. +*/ +static void enlargeAndAppend(StrAccum *p, const char *z, int N){ + N = sqlite3StrAccumEnlarge(p, N); + if( N>0 ){ + memcpy(&p->zText[p->nChar], z, N); + p->nChar += N; + } +} + +/* +** Append N bytes of text from z to the StrAccum object. Increase the +** size of the memory allocation for StrAccum if necessary. */ void sqlite3StrAccumAppend(StrAccum *p, const char *z, int N){ assert( z!=0 ); assert( p->zText!=0 || p->nChar==0 || p->accError ); assert( N>=0 ); assert( p->accError==0 || p->nAlloc==0 ); if( p->nChar+N >= p->nAlloc ){ - char *zNew; - if( p->accError ){ - testcase(p->accError==STRACCUM_TOOBIG); - testcase(p->accError==STRACCUM_NOMEM); - return; - } - if( !p->useMalloc ){ - N = p->nAlloc - p->nChar - 1; - setStrAccumError(p, STRACCUM_TOOBIG); - if( N<=0 ){ - return; - } - }else{ - char *zOld = (p->zText==p->zBase ? 0 : p->zText); - i64 szNew = p->nChar; - szNew += N + 1; - if( szNew > p->mxAlloc ){ - sqlite3StrAccumReset(p); - setStrAccumError(p, STRACCUM_TOOBIG); - return; - }else{ - p->nAlloc = (int)szNew; - } - if( p->useMalloc==1 ){ - zNew = sqlite3DbRealloc(p->db, zOld, p->nAlloc); - }else{ - zNew = sqlite3_realloc(zOld, p->nAlloc); - } - if( zNew ){ - if( zOld==0 && p->nChar>0 ) memcpy(zNew, p->zText, p->nChar); - p->zText = zNew; - }else{ - sqlite3StrAccumReset(p); - setStrAccumError(p, STRACCUM_NOMEM); - return; - } - } + enlargeAndAppend(p,z,N); + return; } assert( p->zText ); memcpy(&p->zText[p->nChar], z, N); p->nChar += N; } Index: src/select.c ================================================================== --- src/select.c +++ src/select.c @@ -12,10 +12,38 @@ ** This file contains C code routines that are called by the parser ** to handle SELECT statements in SQLite. */ #include "sqliteInt.h" +/* +** An instance of the following object is used to record information about +** how to process the DISTINCT keyword, to simplify passing that information +** into the selectInnerLoop() routine. +*/ +typedef struct DistinctCtx DistinctCtx; +struct DistinctCtx { + u8 isTnct; /* True if the DISTINCT keyword is present */ + u8 eTnctType; /* One of the WHERE_DISTINCT_* operators */ + int tabTnct; /* Ephemeral table used for DISTINCT processing */ + int addrTnct; /* Address of OP_OpenEphemeral opcode for tabTnct */ +}; + +/* +** An instance of the following object is used to record information about +** the ORDER BY (or GROUP BY) clause of query is being coded. +*/ +typedef struct SortCtx SortCtx; +struct SortCtx { + ExprList *pOrderBy; /* The ORDER BY (or GROUP BY clause) */ + int nOBSat; /* Number of ORDER BY terms satisfied by indices */ + int iECursor; /* Cursor number for the sorter */ + int regReturn; /* Register holding block-output return address */ + int labelBkOut; /* Start label for the block-output subroutine */ + int addrSortIndex; /* Address of the OP_SorterOpen or OP_OpenEphemeral */ + u8 sortFlags; /* Zero or more SORTFLAG_* bits */ +}; +#define SORTFLAG_UseSorter 0x01 /* Use SorterOpen instead of OpenEphemeral */ /* ** Delete all the content of a Select structure but do not deallocate ** the select structure itself. */ @@ -85,11 +113,10 @@ pNew->pLimit = pLimit; pNew->pOffset = pOffset; assert( pOffset==0 || pLimit!=0 ); pNew->addrOpenEphm[0] = -1; pNew->addrOpenEphm[1] = -1; - pNew->addrOpenEphm[2] = -1; if( db->mallocFailed ) { clearSelect(db, pNew); if( pNew!=&standin ) sqlite3DbFree(db, pNew); pNew = 0; }else{ @@ -417,38 +444,79 @@ } } return 0; } +/* Forward reference */ +static KeyInfo *keyInfoFromExprList( + Parse *pParse, /* Parsing context */ + ExprList *pList, /* Form the KeyInfo object from this ExprList */ + int iStart, /* Begin with this column of pList */ + int nExtra /* Add this many extra columns to the end */ +); + /* -** Insert code into "v" that will push the record on the top of the -** stack into the sorter. +** Insert code into "v" that will push the record in register regData +** into the sorter. */ static void pushOntoSorter( Parse *pParse, /* Parser context */ - ExprList *pOrderBy, /* The ORDER BY clause */ + SortCtx *pSort, /* Information about the ORDER BY clause */ Select *pSelect, /* The whole SELECT statement */ int regData /* Register holding data to be sorted */ ){ Vdbe *v = pParse->pVdbe; - int nExpr = pOrderBy->nExpr; + int nExpr = pSort->pOrderBy->nExpr; int regBase = sqlite3GetTempRange(pParse, nExpr+2); int regRecord = sqlite3GetTempReg(pParse); + int nOBSat = pSort->nOBSat; int op; sqlite3ExprCacheClear(pParse); - sqlite3ExprCodeExprList(pParse, pOrderBy, regBase, 0); - sqlite3VdbeAddOp2(v, OP_Sequence, pOrderBy->iECursor, regBase+nExpr); + sqlite3ExprCodeExprList(pParse, pSort->pOrderBy, regBase, 0); + sqlite3VdbeAddOp2(v, OP_Sequence, pSort->iECursor, regBase+nExpr); sqlite3ExprCodeMove(pParse, regData, regBase+nExpr+1, 1); - sqlite3VdbeAddOp3(v, OP_MakeRecord, regBase, nExpr + 2, regRecord); - if( pSelect->selFlags & SF_UseSorter ){ + sqlite3VdbeAddOp3(v, OP_MakeRecord, regBase+nOBSat, nExpr+2-nOBSat, regRecord); + if( nOBSat>0 ){ + int regPrevKey; /* The first nOBSat columns of the previous row */ + int addrFirst; /* Address of the OP_IfNot opcode */ + int addrJmp; /* Address of the OP_Jump opcode */ + VdbeOp *pOp; /* Opcode that opens the sorter */ + int nKey; /* Number of sorting key columns, including OP_Sequence */ + KeyInfo *pKI; /* Original KeyInfo on the sorter table */ + + regPrevKey = pParse->nMem+1; + pParse->nMem += pSort->nOBSat; + nKey = nExpr - pSort->nOBSat + 1; + addrFirst = sqlite3VdbeAddOp1(v, OP_IfNot, regBase+nExpr); VdbeCoverage(v); + sqlite3VdbeAddOp3(v, OP_Compare, regPrevKey, regBase, pSort->nOBSat); + pOp = sqlite3VdbeGetOp(v, pSort->addrSortIndex); + if( pParse->db->mallocFailed ) return; + pOp->p2 = nKey + 1; + pKI = pOp->p4.pKeyInfo; + memset(pKI->aSortOrder, 0, pKI->nField); /* Makes OP_Jump below testable */ + sqlite3VdbeChangeP4(v, -1, (char*)pKI, P4_KEYINFO); + pOp->p4.pKeyInfo = keyInfoFromExprList(pParse, pSort->pOrderBy, nOBSat, 1); + addrJmp = sqlite3VdbeCurrentAddr(v); + sqlite3VdbeAddOp3(v, OP_Jump, addrJmp+1, 0, addrJmp+1); VdbeCoverage(v); + pSort->labelBkOut = sqlite3VdbeMakeLabel(v); + pSort->regReturn = ++pParse->nMem; + sqlite3VdbeAddOp2(v, OP_Gosub, pSort->regReturn, pSort->labelBkOut); + sqlite3VdbeAddOp1(v, OP_ResetSorter, pSort->iECursor); + sqlite3VdbeJumpHere(v, addrFirst); + sqlite3VdbeAddOp3(v, OP_Move, regBase, regPrevKey, pSort->nOBSat); + sqlite3VdbeJumpHere(v, addrJmp); + } + if( pSort->sortFlags & SORTFLAG_UseSorter ){ op = OP_SorterInsert; }else{ op = OP_IdxInsert; } - sqlite3VdbeAddOp2(v, op, pOrderBy->iECursor, regRecord); - sqlite3ReleaseTempReg(pParse, regRecord); - sqlite3ReleaseTempRange(pParse, regBase, nExpr+2); + sqlite3VdbeAddOp2(v, op, pSort->iECursor, regRecord); + if( nOBSat==0 ){ + sqlite3ReleaseTempReg(pParse, regRecord); + sqlite3ReleaseTempRange(pParse, regBase, nExpr+2); + } if( pSelect->iLimit ){ int addr1, addr2; int iLimit; if( pSelect->iOffset ){ iLimit = pSelect->iOffset+1; @@ -457,12 +525,12 @@ } addr1 = sqlite3VdbeAddOp1(v, OP_IfZero, iLimit); VdbeCoverage(v); sqlite3VdbeAddOp2(v, OP_AddImm, iLimit, -1); addr2 = sqlite3VdbeAddOp0(v, OP_Goto); sqlite3VdbeJumpHere(v, addr1); - sqlite3VdbeAddOp1(v, OP_Last, pOrderBy->iECursor); - sqlite3VdbeAddOp1(v, OP_Delete, pOrderBy->iECursor); + sqlite3VdbeAddOp1(v, OP_Last, pSort->iECursor); + sqlite3VdbeAddOp1(v, OP_Delete, pSort->iECursor); sqlite3VdbeJumpHere(v, addr2); } } /* @@ -471,11 +539,11 @@ static void codeOffset( Vdbe *v, /* Generate code into this VM */ int iOffset, /* Register holding the offset counter */ int iContinue /* Jump here to skip the current record */ ){ - if( iOffset>0 && iContinue!=0 ){ + if( iOffset>0 ){ int addr; sqlite3VdbeAddOp2(v, OP_AddImm, iOffset, -1); addr = sqlite3VdbeAddOp1(v, OP_IfNeg, iOffset); VdbeCoverage(v); sqlite3VdbeAddOp2(v, OP_Goto, 0, iContinue); VdbeComment((v, "skip OFFSET records")); @@ -532,23 +600,10 @@ return 0; } } #endif -/* -** An instance of the following object is used to record information about -** how to process the DISTINCT keyword, to simplify passing that information -** into the selectInnerLoop() routine. -*/ -typedef struct DistinctCtx DistinctCtx; -struct DistinctCtx { - u8 isTnct; /* True if the DISTINCT keyword is present */ - u8 eTnctType; /* One of the WHERE_DISTINCT_* operators */ - int tabTnct; /* Ephemeral table used for DISTINCT processing */ - int addrTnct; /* Address of OP_OpenEphemeral opcode for tabTnct */ -}; - /* ** This routine generates the code for the inside of the inner loop ** of a SELECT. ** ** If srcTab is negative, then the pEList expressions @@ -559,11 +614,11 @@ static void selectInnerLoop( Parse *pParse, /* The parser context */ Select *p, /* The complete select statement being coded */ ExprList *pEList, /* List of values being extracted */ int srcTab, /* Pull data from this table */ - ExprList *pOrderBy, /* If not NULL, sort results using this key */ + SortCtx *pSort, /* If not NULL, info on how to process ORDER BY */ DistinctCtx *pDistinct, /* If not NULL, info on how to process DISTINCT */ SelectDest *pDest, /* How to dispose of the results */ int iContinue, /* Jump here to continue with next row */ int iBreak /* Jump here to break out of the inner loop */ ){ @@ -576,11 +631,13 @@ int nResultCol; /* Number of result columns */ assert( v ); assert( pEList!=0 ); hasDistinct = pDistinct ? pDistinct->eTnctType : WHERE_DISTINCT_NOOP; - if( pOrderBy==0 && !hasDistinct ){ + if( pSort && pSort->pOrderBy==0 ) pSort = 0; + if( pSort==0 && !hasDistinct ){ + assert( iContinue!=0 ); codeOffset(v, p->iOffset, iContinue); } /* Pull the requested columns. */ @@ -666,11 +723,11 @@ assert( pDistinct->eTnctType==WHERE_DISTINCT_UNORDERED ); codeDistinct(pParse, pDistinct->tabTnct, iContinue, nResultCol, regResult); break; } } - if( pOrderBy==0 ){ + if( pSort==0 ){ codeOffset(v, p->iOffset, iContinue); } } switch( eDest ){ @@ -697,32 +754,33 @@ } #endif /* SQLITE_OMIT_COMPOUND_SELECT */ /* Store the result as data using a unique key. */ - case SRT_DistTable: + case SRT_Fifo: + case SRT_DistFifo: case SRT_Table: case SRT_EphemTab: { int r1 = sqlite3GetTempReg(pParse); testcase( eDest==SRT_Table ); testcase( eDest==SRT_EphemTab ); sqlite3VdbeAddOp3(v, OP_MakeRecord, regResult, nResultCol, r1); #ifndef SQLITE_OMIT_CTE - if( eDest==SRT_DistTable ){ - /* If the destination is DistTable, then cursor (iParm+1) is open + if( eDest==SRT_DistFifo ){ + /* If the destination is DistFifo, then cursor (iParm+1) is open ** on an ephemeral index. If the current row is already present ** in the index, do not write it to the output. If not, add the ** current row to the index and proceed with writing it to the ** output table as well. */ int addr = sqlite3VdbeCurrentAddr(v) + 4; sqlite3VdbeAddOp4Int(v, OP_Found, iParm+1, addr, r1, 0); VdbeCoverage(v); sqlite3VdbeAddOp2(v, OP_IdxInsert, iParm+1, r1); - assert( pOrderBy==0 ); + assert( pSort==0 ); } #endif - if( pOrderBy ){ - pushOntoSorter(pParse, pOrderBy, p, r1); + if( pSort ){ + pushOntoSorter(pParse, pSort, p, r1); }else{ int r2 = sqlite3GetTempReg(pParse); sqlite3VdbeAddOp2(v, OP_NewRowid, iParm, r2); sqlite3VdbeAddOp3(v, OP_Insert, iParm, r1, r2); sqlite3VdbeChangeP5(v, OPFLAG_APPEND); @@ -739,16 +797,16 @@ */ case SRT_Set: { assert( nResultCol==1 ); pDest->affSdst = sqlite3CompareAffinity(pEList->a[0].pExpr, pDest->affSdst); - if( pOrderBy ){ + if( pSort ){ /* At first glance you would think we could optimize out the ** ORDER BY in this case since the order of entries in the set ** does not matter. But there might be a LIMIT clause, in which ** case the order does matter */ - pushOntoSorter(pParse, pOrderBy, p, regResult); + pushOntoSorter(pParse, pSort, p, regResult); }else{ int r1 = sqlite3GetTempReg(pParse); sqlite3VdbeAddOp4(v, OP_MakeRecord, regResult,1,r1, &pDest->affSdst, 1); sqlite3ExprCacheAffinityChange(pParse, regResult, 1); sqlite3VdbeAddOp2(v, OP_IdxInsert, iParm, r1); @@ -769,12 +827,12 @@ ** store the results in the appropriate memory cell and break out ** of the scan loop. */ case SRT_Mem: { assert( nResultCol==1 ); - if( pOrderBy ){ - pushOntoSorter(pParse, pOrderBy, p, regResult); + if( pSort ){ + pushOntoSorter(pParse, pSort, p, regResult); }else{ sqlite3ExprCodeMove(pParse, regResult, iParm, 1); /* The LIMIT clause will jump out of the loop for us */ } break; @@ -783,14 +841,14 @@ case SRT_Coroutine: /* Send data to a co-routine */ case SRT_Output: { /* Return the results */ testcase( eDest==SRT_Coroutine ); testcase( eDest==SRT_Output ); - if( pOrderBy ){ + if( pSort ){ int r1 = sqlite3GetTempReg(pParse); sqlite3VdbeAddOp3(v, OP_MakeRecord, regResult, nResultCol, r1); - pushOntoSorter(pParse, pOrderBy, p, r1); + pushOntoSorter(pParse, pSort, p, r1); sqlite3ReleaseTempReg(pParse, r1); }else if( eDest==SRT_Coroutine ){ sqlite3VdbeAddOp1(v, OP_Yield, pDest->iSDParm); }else{ sqlite3VdbeAddOp2(v, OP_ResultRow, regResult, nResultCol); @@ -863,11 +921,11 @@ /* Jump to the end of the loop if the LIMIT is reached. Except, if ** there is a sorter, in which case the sorter has already limited ** the output for us. */ - if( pOrderBy==0 && p->iLimit ){ + if( pSort==0 && p->iLimit ){ sqlite3VdbeAddOp3(v, OP_IfZero, p->iLimit, iBreak, -1); VdbeCoverage(v); } } /* @@ -934,27 +992,32 @@ ** ** Space to hold the KeyInfo structure is obtain from malloc. The calling ** function is responsible for seeing that this structure is eventually ** freed. */ -static KeyInfo *keyInfoFromExprList(Parse *pParse, ExprList *pList, int nExtra){ +static KeyInfo *keyInfoFromExprList( + Parse *pParse, /* Parsing context */ + ExprList *pList, /* Form the KeyInfo object from this ExprList */ + int iStart, /* Begin with this column of pList */ + int nExtra /* Add this many extra columns to the end */ +){ int nExpr; KeyInfo *pInfo; struct ExprList_item *pItem; sqlite3 *db = pParse->db; int i; nExpr = pList->nExpr; - pInfo = sqlite3KeyInfoAlloc(db, nExpr+nExtra, 1); + pInfo = sqlite3KeyInfoAlloc(db, nExpr+nExtra-iStart, 1); if( pInfo ){ assert( sqlite3KeyInfoIsWriteable(pInfo) ); - for(i=0, pItem=pList->a; ia+iStart; ipExpr); if( !pColl ) pColl = db->pDfltColl; - pInfo->aColl[i] = pColl; - pInfo->aSortOrder[i] = pItem->sortOrder; + pInfo->aColl[i-iStart] = pColl; + pInfo->aSortOrder[i-iStart] = pItem->sortOrder; } } return pInfo; } @@ -1052,50 +1115,60 @@ ** routine generates the code needed to do that. */ static void generateSortTail( Parse *pParse, /* Parsing context */ Select *p, /* The SELECT statement */ - Vdbe *v, /* Generate code into this VDBE */ + SortCtx *pSort, /* Information on the ORDER BY clause */ int nColumn, /* Number of columns of data */ SelectDest *pDest /* Write the sorted results here */ ){ + Vdbe *v = pParse->pVdbe; /* The prepared statement */ int addrBreak = sqlite3VdbeMakeLabel(v); /* Jump here to exit loop */ int addrContinue = sqlite3VdbeMakeLabel(v); /* Jump here for next cycle */ int addr; + int addrOnce = 0; int iTab; int pseudoTab = 0; - ExprList *pOrderBy = p->pOrderBy; - + ExprList *pOrderBy = pSort->pOrderBy; int eDest = pDest->eDest; int iParm = pDest->iSDParm; - int regRow; int regRowid; + int nKey; - iTab = pOrderBy->iECursor; + if( pSort->labelBkOut ){ + sqlite3VdbeAddOp2(v, OP_Gosub, pSort->regReturn, pSort->labelBkOut); + sqlite3VdbeAddOp2(v, OP_Goto, 0, addrBreak); + sqlite3VdbeResolveLabel(v, pSort->labelBkOut); + addrOnce = sqlite3CodeOnce(pParse); VdbeCoverage(v); + } + iTab = pSort->iECursor; regRow = sqlite3GetTempReg(pParse); if( eDest==SRT_Output || eDest==SRT_Coroutine ){ pseudoTab = pParse->nTab++; sqlite3VdbeAddOp3(v, OP_OpenPseudo, pseudoTab, regRow, nColumn); regRowid = 0; }else{ regRowid = sqlite3GetTempReg(pParse); } - if( p->selFlags & SF_UseSorter ){ + nKey = pOrderBy->nExpr - pSort->nOBSat; + if( pSort->sortFlags & SORTFLAG_UseSorter ){ int regSortOut = ++pParse->nMem; int ptab2 = pParse->nTab++; - sqlite3VdbeAddOp3(v, OP_OpenPseudo, ptab2, regSortOut, pOrderBy->nExpr+2); + sqlite3VdbeAddOp3(v, OP_OpenPseudo, ptab2, regSortOut, nKey+2); + if( addrOnce ) sqlite3VdbeJumpHere(v, addrOnce); addr = 1 + sqlite3VdbeAddOp2(v, OP_SorterSort, iTab, addrBreak); VdbeCoverage(v); codeOffset(v, p->iOffset, addrContinue); sqlite3VdbeAddOp2(v, OP_SorterData, iTab, regSortOut); - sqlite3VdbeAddOp3(v, OP_Column, ptab2, pOrderBy->nExpr+1, regRow); + sqlite3VdbeAddOp3(v, OP_Column, ptab2, nKey+1, regRow); sqlite3VdbeChangeP5(v, OPFLAG_CLEARCACHE); }else{ + if( addrOnce ) sqlite3VdbeJumpHere(v, addrOnce); addr = 1 + sqlite3VdbeAddOp2(v, OP_Sort, iTab, addrBreak); VdbeCoverage(v); codeOffset(v, p->iOffset, addrContinue); - sqlite3VdbeAddOp3(v, OP_Column, iTab, pOrderBy->nExpr+1, regRow); + sqlite3VdbeAddOp3(v, OP_Column, iTab, nKey+1, regRow); } switch( eDest ){ case SRT_Table: case SRT_EphemTab: { testcase( eDest==SRT_Table ); @@ -1146,15 +1219,16 @@ sqlite3ReleaseTempReg(pParse, regRowid); /* The bottom of the loop */ sqlite3VdbeResolveLabel(v, addrContinue); - if( p->selFlags & SF_UseSorter ){ + if( pSort->sortFlags & SORTFLAG_UseSorter ){ sqlite3VdbeAddOp2(v, OP_SorterNext, iTab, addr); VdbeCoverage(v); }else{ sqlite3VdbeAddOp2(v, OP_Next, iTab, addr); VdbeCoverage(v); } + if( pSort->regReturn ) sqlite3VdbeAddOp1(v, OP_Return, pSort->regReturn); sqlite3VdbeResolveLabel(v, addrBreak); if( eDest==SRT_Output || eDest==SRT_Coroutine ){ sqlite3VdbeAddOp2(v, OP_Close, pseudoTab, 0); } } @@ -1832,11 +1906,11 @@ int addrCont, addrBreak; /* CONTINUE and BREAK addresses */ int iCurrent = 0; /* The Current table */ int regCurrent; /* Register holding Current table */ int iQueue; /* The Queue table */ int iDistinct = 0; /* To ensure unique results if UNION */ - int eDest = SRT_Table; /* How to write to Queue */ + int eDest = SRT_Fifo; /* How to write to Queue */ SelectDest destQueue; /* SelectDest targetting the Queue table */ int i; /* Loop counter */ int rc; /* Result code */ ExprList *pOrderBy; /* The ORDER BY clause */ Expr *pLimit, *pOffset; /* Saved LIMIT and OFFSET */ @@ -1864,17 +1938,17 @@ } } /* Allocate cursors numbers for Queue and Distinct. The cursor number for ** the Distinct table must be exactly one greater than Queue in order - ** for the SRT_DistTable and SRT_DistQueue destinations to work. */ + ** for the SRT_DistFifo and SRT_DistQueue destinations to work. */ iQueue = pParse->nTab++; if( p->op==TK_UNION ){ - eDest = pOrderBy ? SRT_DistQueue : SRT_DistTable; + eDest = pOrderBy ? SRT_DistQueue : SRT_DistFifo; iDistinct = pParse->nTab++; }else{ - eDest = pOrderBy ? SRT_Queue : SRT_Table; + eDest = pOrderBy ? SRT_Queue : SRT_Fifo; } sqlite3SelectDestInit(&destQueue, eDest, iQueue); /* Allocate cursors for Current, Queue, and Distinct. */ regCurrent = ++pParse->nMem; @@ -1936,10 +2010,11 @@ /* Keep running the loop until the Queue is empty */ sqlite3VdbeAddOp2(v, OP_Goto, 0, addrTop); sqlite3VdbeResolveLabel(v, addrBreak); end_of_recursive_query: + sqlite3ExprListDelete(pParse->db, p->pOrderBy); p->pOrderBy = pOrderBy; p->pLimit = pLimit; p->pOffset = pOffset; return; } @@ -4307,11 +4382,11 @@ if( pE->x.pList==0 || pE->x.pList->nExpr!=1 ){ sqlite3ErrorMsg(pParse, "DISTINCT aggregates must have exactly one " "argument"); pFunc->iDistinct = -1; }else{ - KeyInfo *pKeyInfo = keyInfoFromExprList(pParse, pE->x.pList, 0); + KeyInfo *pKeyInfo = keyInfoFromExprList(pParse, pE->x.pList, 0, 0); sqlite3VdbeAddOp4(v, OP_OpenEphemeral, pFunc->iDistinct, 0, 0, (char*)pKeyInfo, P4_KEYINFO); } } } @@ -4462,16 +4537,15 @@ Vdbe *v; /* The virtual machine under construction */ int isAgg; /* True for select lists like "count(*)" */ ExprList *pEList; /* List of columns to extract. */ SrcList *pTabList; /* List of tables to select from */ Expr *pWhere; /* The WHERE clause. May be NULL */ - ExprList *pOrderBy; /* The ORDER BY clause. May be NULL */ ExprList *pGroupBy; /* The GROUP BY clause. May be NULL */ Expr *pHaving; /* The HAVING clause. May be NULL */ int rc = 1; /* Value to return from this function */ - int addrSortIndex; /* Address of an OP_OpenEphemeral instruction */ DistinctCtx sDistinct; /* Info on how to code the DISTINCT keyword */ + SortCtx sSort; /* Info on how to code the ORDER BY clause */ AggInfo sAggInfo; /* Information used by aggregate queries */ int iEnd; /* Address of the end of the query */ sqlite3 *db; /* The database connection */ #ifndef SQLITE_OMIT_EXPLAIN @@ -4484,21 +4558,28 @@ return 1; } if( sqlite3AuthCheck(pParse, SQLITE_SELECT, 0, 0, 0) ) return 1; memset(&sAggInfo, 0, sizeof(sAggInfo)); + assert( p->pOrderBy==0 || pDest->eDest!=SRT_DistFifo ); + assert( p->pOrderBy==0 || pDest->eDest!=SRT_Fifo ); + assert( p->pOrderBy==0 || pDest->eDest!=SRT_DistQueue ); + assert( p->pOrderBy==0 || pDest->eDest!=SRT_Queue ); if( IgnorableOrderby(pDest) ){ assert(pDest->eDest==SRT_Exists || pDest->eDest==SRT_Union || - pDest->eDest==SRT_Except || pDest->eDest==SRT_Discard); + pDest->eDest==SRT_Except || pDest->eDest==SRT_Discard || + pDest->eDest==SRT_Queue || pDest->eDest==SRT_DistFifo || + pDest->eDest==SRT_DistQueue || pDest->eDest==SRT_Fifo); /* If ORDER BY makes no difference in the output then neither does ** DISTINCT so it can be removed too. */ sqlite3ExprListDelete(db, p->pOrderBy); p->pOrderBy = 0; p->selFlags &= ~SF_Distinct; } sqlite3SelectPrep(pParse, p, 0); - pOrderBy = p->pOrderBy; + memset(&sSort, 0, sizeof(sSort)); + sSort.pOrderBy = p->pOrderBy; pTabList = p->pSrc; pEList = p->pEList; if( pParse->nErr || db->mallocFailed ){ goto select_end; } @@ -4616,11 +4697,11 @@ goto select_end; } pParse->nHeight -= sqlite3SelectExprHeight(p); pTabList = p->pSrc; if( !IgnorableOrderby(pDest) ){ - pOrderBy = p->pOrderBy; + sSort.pOrderBy = p->pOrderBy; } } pEList = p->pEList; #endif pWhere = p->pWhere; @@ -4643,13 +4724,13 @@ ** will cause elements to come out in the correct order. This is ** an optimization - the correct answer should result regardless. ** Use the SQLITE_GroupByOrder flag with SQLITE_TESTCTRL_OPTIMIZER ** to disable this optimization for testing purposes. */ - if( sqlite3ExprListCompare(p->pGroupBy, pOrderBy, -1)==0 + if( sqlite3ExprListCompare(p->pGroupBy, sSort.pOrderBy, -1)==0 && OptimizationEnabled(db, SQLITE_GroupByOrder) ){ - pOrderBy = 0; + sSort.pOrderBy = 0; } /* If the query is DISTINCT with an ORDER BY but is not an aggregate, and ** if the select-list is the same as the ORDER BY list, then this query ** can be rewritten as a GROUP BY. In other words, this: @@ -4664,16 +4745,16 @@ ** used for both the ORDER BY and DISTINCT processing. As originally ** written the query must use a temp-table for at least one of the ORDER ** BY and DISTINCT, and an index or separate temp-table for the other. */ if( (p->selFlags & (SF_Distinct|SF_Aggregate))==SF_Distinct - && sqlite3ExprListCompare(pOrderBy, p->pEList, -1)==0 + && sqlite3ExprListCompare(sSort.pOrderBy, p->pEList, -1)==0 ){ p->selFlags &= ~SF_Distinct; p->pGroupBy = sqlite3ExprListDup(db, p->pEList, 0); pGroupBy = p->pGroupBy; - pOrderBy = 0; + sSort.pOrderBy = 0; /* Notice that even thought SF_Distinct has been cleared from p->selFlags, ** the sDistinct.isTnct is still set. Hence, isTnct represents the ** original setting of the SF_Distinct flag, not the current setting */ assert( sDistinct.isTnct ); } @@ -4683,20 +4764,20 @@ ** extracted in pre-sorted order. If that is the case, then the ** OP_OpenEphemeral instruction will be changed to an OP_Noop once ** we figure out that the sorting index is not needed. The addrSortIndex ** variable is used to facilitate that change. */ - if( pOrderBy ){ + if( sSort.pOrderBy ){ KeyInfo *pKeyInfo; - pKeyInfo = keyInfoFromExprList(pParse, pOrderBy, 0); - pOrderBy->iECursor = pParse->nTab++; - p->addrOpenEphm[2] = addrSortIndex = + pKeyInfo = keyInfoFromExprList(pParse, sSort.pOrderBy, 0, 0); + sSort.iECursor = pParse->nTab++; + sSort.addrSortIndex = sqlite3VdbeAddOp4(v, OP_OpenEphemeral, - pOrderBy->iECursor, pOrderBy->nExpr+2, 0, + sSort.iECursor, sSort.pOrderBy->nExpr+2, 0, (char*)pKeyInfo, P4_KEYINFO); }else{ - addrSortIndex = -1; + sSort.addrSortIndex = -1; } /* If the output is destined for a temporary table, open that table. */ if( pDest->eDest==SRT_EphemTab ){ @@ -4706,22 +4787,22 @@ /* Set the limiter. */ iEnd = sqlite3VdbeMakeLabel(v); p->nSelectRow = LARGEST_INT64; computeLimitRegisters(pParse, p, iEnd); - if( p->iLimit==0 && addrSortIndex>=0 ){ - sqlite3VdbeGetOp(v, addrSortIndex)->opcode = OP_SorterOpen; - p->selFlags |= SF_UseSorter; + if( p->iLimit==0 && sSort.addrSortIndex>=0 ){ + sqlite3VdbeGetOp(v, sSort.addrSortIndex)->opcode = OP_SorterOpen; + sSort.sortFlags |= SORTFLAG_UseSorter; } /* Open a virtual index to use for the distinct set. */ if( p->selFlags & SF_Distinct ){ sDistinct.tabTnct = pParse->nTab++; sDistinct.addrTnct = sqlite3VdbeAddOp4(v, OP_OpenEphemeral, sDistinct.tabTnct, 0, 0, - (char*)keyInfoFromExprList(pParse, p->pEList, 0), + (char*)keyInfoFromExprList(pParse, p->pEList,0,0), P4_KEYINFO); sqlite3VdbeChangeP5(v, BTREE_UNORDERED); sDistinct.eTnctType = WHERE_DISTINCT_UNORDERED; }else{ sDistinct.eTnctType = WHERE_DISTINCT_NOOP; @@ -4730,32 +4811,36 @@ if( !isAgg && pGroupBy==0 ){ /* No aggregate functions and no GROUP BY clause */ u16 wctrlFlags = (sDistinct.isTnct ? WHERE_WANT_DISTINCT : 0); /* Begin the database scan. */ - pWInfo = sqlite3WhereBegin(pParse, pTabList, pWhere, pOrderBy, p->pEList, - wctrlFlags, 0); + pWInfo = sqlite3WhereBegin(pParse, pTabList, pWhere, sSort.pOrderBy, + p->pEList, wctrlFlags, 0); if( pWInfo==0 ) goto select_end; if( sqlite3WhereOutputRowCount(pWInfo) < p->nSelectRow ){ p->nSelectRow = sqlite3WhereOutputRowCount(pWInfo); } if( sDistinct.isTnct && sqlite3WhereIsDistinct(pWInfo) ){ sDistinct.eTnctType = sqlite3WhereIsDistinct(pWInfo); } - if( pOrderBy && sqlite3WhereIsOrdered(pWInfo) ) pOrderBy = 0; + if( sSort.pOrderBy ){ + sSort.nOBSat = sqlite3WhereIsOrdered(pWInfo); + if( sSort.nOBSat==sSort.pOrderBy->nExpr ){ + sSort.pOrderBy = 0; + } + } /* If sorting index that was created by a prior OP_OpenEphemeral ** instruction ended up not being needed, then change the OP_OpenEphemeral ** into an OP_Noop. */ - if( addrSortIndex>=0 && pOrderBy==0 ){ - sqlite3VdbeChangeToNoop(v, addrSortIndex); - p->addrOpenEphm[2] = -1; + if( sSort.addrSortIndex>=0 && sSort.pOrderBy==0 ){ + sqlite3VdbeChangeToNoop(v, sSort.addrSortIndex); } /* Use the standard inner loop. */ - selectInnerLoop(pParse, p, pEList, -1, pOrderBy, &sDistinct, pDest, + selectInnerLoop(pParse, p, pEList, -1, &sSort, &sDistinct, pDest, sqlite3WhereContinueLabel(pWInfo), sqlite3WhereBreakLabel(pWInfo)); /* End the database scan loop. */ @@ -4807,11 +4892,11 @@ sNC.pAggInfo = &sAggInfo; sAggInfo.mnReg = pParse->nMem+1; sAggInfo.nSortingColumn = pGroupBy ? pGroupBy->nExpr+1 : 0; sAggInfo.pGroupBy = pGroupBy; sqlite3ExprAnalyzeAggList(&sNC, pEList); - sqlite3ExprAnalyzeAggList(&sNC, pOrderBy); + sqlite3ExprAnalyzeAggList(&sNC, sSort.pOrderBy); if( pHaving ){ sqlite3ExprAnalyzeAggregates(&sNC, pHaving); } sAggInfo.nAccumulator = sAggInfo.nColumn; for(i=0; inTab++; - pKeyInfo = keyInfoFromExprList(pParse, pGroupBy, 0); + pKeyInfo = keyInfoFromExprList(pParse, pGroupBy, 0, 0); addrSortingIdx = sqlite3VdbeAddOp4(v, OP_SorterOpen, sAggInfo.sortingIdx, sAggInfo.nSortingColumn, 0, (char*)pKeyInfo, P4_KEYINFO); /* Initialize memory locations used by GROUP BY aggregate processing @@ -4870,14 +4955,14 @@ ** This might involve two separate loops with an OP_Sort in between, or ** it might be a single loop that uses an index to extract information ** in the right order to begin with. */ sqlite3VdbeAddOp2(v, OP_Gosub, regReset, addrReset); - pWInfo = sqlite3WhereBegin(pParse, pTabList, pWhere, pGroupBy, 0, + pWInfo = sqlite3WhereBegin(pParse, pTabList, pWhere, pGroupBy, 0, WHERE_GROUPBY, 0); if( pWInfo==0 ) goto select_end; - if( sqlite3WhereIsOrdered(pWInfo) ){ + if( sqlite3WhereIsOrdered(pWInfo)==pGroupBy->nExpr ){ /* The optimizer is able to deliver rows in group by order so ** we do not have to sort. The OP_OpenEphemeral table will be ** cancelled later because we still need to use the pKeyInfo */ groupBySort = 0; @@ -5024,11 +5109,11 @@ sqlite3VdbeAddOp2(v, OP_IfPos, iUseFlag, addrOutputRow+2); VdbeCoverage(v); VdbeComment((v, "Groupby result generator entry point")); sqlite3VdbeAddOp1(v, OP_Return, regOutputRow); finalizeAggFunctions(pParse, &sAggInfo); sqlite3ExprIfFalse(pParse, pHaving, addrOutputRow+1, SQLITE_JUMPIFNULL); - selectInnerLoop(pParse, p, p->pEList, -1, pOrderBy, + selectInnerLoop(pParse, p, p->pEList, -1, &sSort, &sDistinct, pDest, addrOutputRow+1, addrSetAbort); sqlite3VdbeAddOp1(v, OP_Return, regOutputRow); VdbeComment((v, "end groupby result generator")); @@ -5156,20 +5241,20 @@ sqlite3ExprListDelete(db, pDel); goto select_end; } updateAccumulator(pParse, &sAggInfo); assert( pMinMax==0 || pMinMax->nExpr==1 ); - if( sqlite3WhereIsOrdered(pWInfo) ){ + if( sqlite3WhereIsOrdered(pWInfo)>0 ){ sqlite3VdbeAddOp2(v, OP_Goto, 0, sqlite3WhereBreakLabel(pWInfo)); VdbeComment((v, "%s() by index", (flag==WHERE_ORDERBY_MIN?"min":"max"))); } sqlite3WhereEnd(pWInfo); finalizeAggFunctions(pParse, &sAggInfo); } - pOrderBy = 0; + sSort.pOrderBy = 0; sqlite3ExprIfFalse(pParse, pHaving, addrEnd, SQLITE_JUMPIFNULL); selectInnerLoop(pParse, p, p->pEList, -1, 0, 0, pDest, addrEnd, addrEnd); sqlite3ExprListDelete(db, pDel); } @@ -5182,13 +5267,13 @@ } /* If there is an ORDER BY clause, then we need to sort the results ** and send them to the callback one by one. */ - if( pOrderBy ){ - explainTempTable(pParse, "ORDER BY"); - generateSortTail(pParse, p, v, pEList->nExpr, pDest); + if( sSort.pOrderBy ){ + explainTempTable(pParse, sSort.nOBSat>0 ? "RIGHT PART OF ORDER BY":"ORDER BY"); + generateSortTail(pParse, p, &sSort, pEList->nExpr, pDest); } /* Jump here to skip this query */ sqlite3VdbeResolveLabel(v, iEnd); Index: src/shell.c ================================================================== --- src/shell.c +++ src/shell.c @@ -1193,11 +1193,12 @@ const char *z; /* Used to check if this is an EXPLAIN */ int *abYield = 0; /* True if op is an OP_Yield */ int nAlloc = 0; /* Allocated size of p->aiIndent[], abYield */ int iOp; /* Index of operation in p->aiIndent[] */ - const char *azNext[] = { "Next", "Prev", "VPrev", "VNext", "SorterNext", 0 }; + const char *azNext[] = { "Next", "Prev", "VPrev", "VNext", "SorterNext", + "NextIfOpen", "PrevIfOpen", 0 }; const char *azYield[] = { "Yield", "SeekLt", "SeekGt", "RowSetRead", "Rewind", 0 }; const char *azGoto[] = { "Goto", 0 }; /* Try to figure out if this is really an EXPLAIN statement. If this ** cannot be verified, return early. */ Index: src/sqliteInt.h ================================================================== --- src/sqliteInt.h +++ src/sqliteInt.h @@ -1892,12 +1892,12 @@ #define EP_Error 0x000008 /* Expression contains one or more errors */ #define EP_Distinct 0x000010 /* Aggregate function with DISTINCT keyword */ #define EP_VarSelect 0x000020 /* pSelect is correlated, not constant */ #define EP_DblQuoted 0x000040 /* token.z was originally in "..." */ #define EP_InfixFunc 0x000080 /* True for an infix function: LIKE, GLOB, etc */ -#define EP_Collate 0x000100 /* Tree contains a TK_COLLATE opeartor */ - /* unused 0x000200 */ +#define EP_Collate 0x000100 /* Tree contains a TK_COLLATE operator */ +#define EP_Generic 0x000200 /* Ignore COLLATE or affinity on this tree */ #define EP_IntValue 0x000400 /* Integer value contained in u.iValue */ #define EP_xIsSelect 0x000800 /* x.pSelect is valid (otherwise x.pList is) */ #define EP_Skip 0x001000 /* COLLATE, AS, or UNLIKELY */ #define EP_Reduced 0x002000 /* Expr struct EXPR_REDUCEDSIZE bytes only */ #define EP_TokenOnly 0x004000 /* Expr struct EXPR_TOKENONLYSIZE bytes only */ @@ -1957,11 +1957,10 @@ ** of the result column in the form: DATABASE.TABLE.COLUMN. This later ** form is used for name resolution with nested FROM clauses. */ struct ExprList { int nExpr; /* Number of expressions on the list */ - int iECursor; /* VDBE Cursor associated with this ExprList */ struct ExprList_item { /* For each expression in the list */ Expr *pExpr; /* The list of expressions */ char *zName; /* Token associated with this expression */ char *zSpan; /* Original text of the expression */ u8 sortOrder; /* 1 for DESC or 0 for ASC */ @@ -2181,11 +2180,11 @@ struct Select { ExprList *pEList; /* The fields of the result */ u8 op; /* One of: TK_UNION TK_ALL TK_INTERSECT TK_EXCEPT */ u16 selFlags; /* Various SF_* values */ int iLimit, iOffset; /* Memory registers holding LIMIT & OFFSET counters */ - int addrOpenEphm[3]; /* OP_OpenEphem opcodes related to this select */ + int addrOpenEphm[2]; /* OP_OpenEphem opcodes related to this select */ u64 nSelectRow; /* Estimated number of result rows */ SrcList *pSrc; /* The FROM clause */ Expr *pWhere; /* The WHERE clause */ ExprList *pGroupBy; /* The GROUP BY clause */ Expr *pHaving; /* The HAVING clause */ @@ -2205,13 +2204,13 @@ #define SF_Resolved 0x0002 /* Identifiers have been resolved */ #define SF_Aggregate 0x0004 /* Contains aggregate functions */ #define SF_UsesEphemeral 0x0008 /* Uses the OpenEphemeral opcode */ #define SF_Expanded 0x0010 /* sqlite3SelectExpand() called on this */ #define SF_HasTypeInfo 0x0020 /* FROM subqueries have Table metadata */ -#define SF_UseSorter 0x0040 /* Sort using a sorter */ + /* 0x0040 NOT USED */ #define SF_Values 0x0080 /* Synthesized from VALUES clause */ -#define SF_Materialize 0x0100 /* NOT USED */ + /* 0x0100 NOT USED */ #define SF_NestedFrom 0x0200 /* Part of a parenthesized FROM clause */ #define SF_MaybeConvert 0x0400 /* Need convertCompoundSelectToSubquery() */ #define SF_Recursive 0x0800 /* The recursive part of a recursive CTE */ #define SF_Compound 0x1000 /* Part of a compound query */ @@ -2260,17 +2259,19 @@ ** of the co-routine is stored in register pDest->iSDParm ** and the result row is stored in pDest->nDest registers ** starting with pDest->iSdst. ** ** SRT_Table Store results in temporary table pDest->iSDParm. -** This is like SRT_EphemTab except that the table -** is assumed to already be open. +** SRT_Fifo This is like SRT_EphemTab except that the table +** is assumed to already be open. SRT_Fifo has +** the additional property of being able to ignore +** the ORDER BY clause. ** -** SRT_DistTable Store results in a temporary table pDest->iSDParm. +** SRT_DistFifo Store results in a temporary table pDest->iSDParm. ** But also use temporary table pDest->iSDParm+1 as ** a record of all prior results and ignore any duplicate -** rows. Name means: "Distinct Table". +** rows. Name means: "Distinct Fifo". ** ** SRT_Queue Store results in priority queue pDest->iSDParm (really ** an index). Append a sequence number so that all entries ** are distinct. ** @@ -2280,23 +2281,24 @@ */ #define SRT_Union 1 /* Store result as keys in an index */ #define SRT_Except 2 /* Remove result from a UNION index */ #define SRT_Exists 3 /* Store 1 if the result is not empty */ #define SRT_Discard 4 /* Do not save the results anywhere */ +#define SRT_Fifo 5 /* Store result as data with an automatic rowid */ +#define SRT_DistFifo 6 /* Like SRT_Fifo, but unique results only */ +#define SRT_Queue 7 /* Store result in an queue */ +#define SRT_DistQueue 8 /* Like SRT_Queue, but unique results only */ /* The ORDER BY clause is ignored for all of the above */ -#define IgnorableOrderby(X) ((X->eDest)<=SRT_Discard) +#define IgnorableOrderby(X) ((X->eDest)<=SRT_DistQueue) -#define SRT_Output 5 /* Output each row of result */ -#define SRT_Mem 6 /* Store result in a memory cell */ -#define SRT_Set 7 /* Store results as keys in an index */ -#define SRT_EphemTab 8 /* Create transient tab and store like SRT_Table */ -#define SRT_Coroutine 9 /* Generate a single row of result */ -#define SRT_Table 10 /* Store result as data with an automatic rowid */ -#define SRT_DistTable 11 /* Like SRT_Table, but unique results only */ -#define SRT_Queue 12 /* Store result in an queue */ -#define SRT_DistQueue 13 /* Like SRT_Queue, but unique results only */ +#define SRT_Output 9 /* Output each row of result */ +#define SRT_Mem 10 /* Store result in a memory cell */ +#define SRT_Set 11 /* Store results as keys in an index */ +#define SRT_EphemTab 12 /* Create transient tab and store like SRT_Table */ +#define SRT_Coroutine 13 /* Generate a single row of result */ +#define SRT_Table 14 /* Store result as data with an automatic rowid */ /* ** An instance of this object describes where to put of the results of ** a SELECT statement. */ @@ -2390,12 +2392,10 @@ int rc; /* Return code from execution */ u8 colNamesSet; /* TRUE after OP_ColumnName has been issued to pVdbe */ u8 checkSchema; /* Causes schema cookie check after an error */ u8 nested; /* Number of nested calls to the parser/code generator */ u8 nTempReg; /* Number of temporary registers in aTempReg[] */ - u8 nColCache; /* Number of entries in aColCache[] */ - u8 iColCache; /* Next entry in aColCache[] to replace */ u8 isMultiWrite; /* True if statement may modify/insert multiple rows */ u8 mayAbort; /* True if statement may throw an ABORT exception */ u8 hasCompound; /* Need to invoke convertCompoundSelectToSubquery() */ u8 okConstFactor; /* OK to factor out constants */ int aTempReg[8]; /* Holding area for temporary registers */ @@ -3290,11 +3290,11 @@ const char *sqlite3ErrStr(int); int sqlite3ReadSchema(Parse *pParse); CollSeq *sqlite3FindCollSeq(sqlite3*,u8 enc, const char*,int); CollSeq *sqlite3LocateCollSeq(Parse *pParse, const char*zName); CollSeq *sqlite3ExprCollSeq(Parse *pParse, Expr *pExpr); -Expr *sqlite3ExprAddCollateToken(Parse *pParse, Expr*, Token*); +Expr *sqlite3ExprAddCollateToken(Parse *pParse, Expr*, const Token*); Expr *sqlite3ExprAddCollateString(Parse*,Expr*,const char*); Expr *sqlite3ExprSkipCollate(Expr*); int sqlite3CheckCollSeq(Parse *, CollSeq *); int sqlite3CheckObjectName(Parse *, const char *); void sqlite3VdbeSetChanges(sqlite3 *, int); Index: src/test_syscall.c ================================================================== --- src/test_syscall.c +++ src/test_syscall.c @@ -65,10 +65,15 @@ ** Return true if the named system call exists. Or false otherwise. ** ** test_syscall list ** Return a list of all system calls. The list is constructed using ** the xNextSystemCall() VFS method. +** +** test_syscall pagesize PGSZ +** If PGSZ is a power of two greater than 256, install a wrapper around +** OS function getpagesize() that reports the system page size as PGSZ. +** Or, if PGSZ is less than zero, remove any wrapper already installed. */ #include "sqliteInt.h" #include "sqlite3.h" #include "tcl.h" @@ -87,11 +92,13 @@ static struct TestSyscallGlobal { int bPersist; /* 1 for persistent errors, 0 for transient */ int nCount; /* Fail after this many more calls */ int nFail; /* Number of failures that have occurred */ -} gSyscall = { 0, 0 }; + int pgsz; + sqlite3_syscall_ptr orig_getpagesize; +} gSyscall = { 0, 0, 0, 0, 0 }; static int ts_open(const char *, int, int); static int ts_close(int fd); static int ts_access(const char *zPath, int mode); static char *ts_getcwd(char *zPath, size_t nPath); @@ -647,10 +654,49 @@ pVfs = sqlite3_vfs_find(0); Tcl_SetObjResult(interp, Tcl_NewStringObj(pVfs->zName, -1)); return TCL_OK; } + +static int ts_getpagesize(void){ + return gSyscall.pgsz; +} + +static int test_syscall_pagesize( + void * clientData, + Tcl_Interp *interp, + int objc, + Tcl_Obj *CONST objv[] +){ + sqlite3_vfs *pVfs = sqlite3_vfs_find(0); + int pgsz; + if( objc!=3 ){ + Tcl_WrongNumArgs(interp, 2, objv, "PGSZ"); + return TCL_ERROR; + } + if( Tcl_GetIntFromObj(interp, objv[2], &pgsz) ){ + return TCL_ERROR; + } + + if( pgsz<0 ){ + if( gSyscall.orig_getpagesize ){ + pVfs->xSetSystemCall(pVfs, "getpagesize", gSyscall.orig_getpagesize); + } + }else{ + if( pgsz<512 || (pgsz & (pgsz-1)) ){ + Tcl_AppendResult(interp, "pgsz out of range", 0); + return TCL_ERROR; + } + gSyscall.orig_getpagesize = pVfs->xGetSystemCall(pVfs, "getpagesize"); + gSyscall.pgsz = pgsz; + pVfs->xSetSystemCall( + pVfs, "getpagesize", (sqlite3_syscall_ptr)ts_getpagesize + ); + } + + return TCL_OK; +} static int test_syscall( void * clientData, Tcl_Interp *interp, int objc, @@ -666,10 +712,11 @@ { "reset", test_syscall_reset }, { "errno", test_syscall_errno }, { "exists", test_syscall_exists }, { "list", test_syscall_list }, { "defaultvfs", test_syscall_defaultvfs }, + { "pagesize", test_syscall_pagesize }, { 0, 0 } }; int iCmd; int rc; Index: src/vdbe.c ================================================================== --- src/vdbe.c +++ src/vdbe.c @@ -307,10 +307,33 @@ u8 affinity, u8 enc ){ applyAffinity((Mem *)pVal, affinity, enc); } + +/* +** Return the numeric type for pMem, either MEM_Int or MEM_Real or both or +** none. +** +** Unlike applyNumericAffinity(), this routine does not modify pMem->flags. +** But it does set pMem->r and pMem->u.i appropriately. +*/ +static u16 numericType(Mem *pMem){ + if( pMem->flags & (MEM_Int|MEM_Real) ){ + return pMem->flags & (MEM_Int|MEM_Real); + } + if( pMem->flags & (MEM_Str|MEM_Blob) ){ + if( sqlite3AtoF(pMem->z, &pMem->r, pMem->n, pMem->enc)==0 ){ + return 0; + } + if( sqlite3Atoi64(pMem->z, &pMem->u.i, pMem->n, pMem->enc)==SQLITE_OK ){ + return MEM_Int; + } + return MEM_Real; + } + return 0; +} #ifdef SQLITE_DEBUG /* ** Write a nice string representation of the contents of cell pMem ** into buffer zBuf, length nBuf. @@ -1078,14 +1101,15 @@ } /* Opcode: Move P1 P2 P3 * * ** Synopsis: r[P2@P3]=r[P1@P3] ** -** Move the values in register P1..P1+P3 over into -** registers P2..P2+P3. Registers P1..P1+P3 are +** Move the P3 values in register P1..P1+P3-1 over into +** registers P2..P2+P3-1. Registers P1..P1+P3-1 are ** left holding a NULL. It is an error for register ranges -** P1..P1+P3 and P2..P2+P3 to overlap. +** P1..P1+P3-1 and P2..P2+P3-1 to overlap. It is an error +** for P3 to be less than 1. */ case OP_Move: { char *zMalloc; /* Holding variable for allocated memory */ int n; /* Number of registers left to copy */ int p1; /* Register to copy from */ @@ -1092,11 +1116,11 @@ int p2; /* Register to copy to */ n = pOp->p3; p1 = pOp->p1; p2 = pOp->p2; - assert( n>=0 && p1>0 && p2>0 ); + assert( n>0 && p1>0 && p2>0 ); assert( p1+n<=p2 || p2+n<=p1 ); pIn1 = &aMem[p1]; pOut = &aMem[p2]; do{ @@ -1116,11 +1140,11 @@ pIn1->xDel = 0; pIn1->zMalloc = zMalloc; REGISTER_TRACE(p2++, pOut); pIn1++; pOut++; - }while( n-- ); + }while( --n ); break; } /* Opcode: Copy P1 P2 P3 * * ** Synopsis: r[P2@P3+1]=r[P1@P3+1] @@ -1348,24 +1372,26 @@ case OP_Subtract: /* same as TK_MINUS, in1, in2, out3 */ case OP_Multiply: /* same as TK_STAR, in1, in2, out3 */ case OP_Divide: /* same as TK_SLASH, in1, in2, out3 */ case OP_Remainder: { /* same as TK_REM, in1, in2, out3 */ char bIntint; /* Started out as two integer operands */ - int flags; /* Combined MEM_* flags from both inputs */ + u16 flags; /* Combined MEM_* flags from both inputs */ + u16 type1; /* Numeric type of left operand */ + u16 type2; /* Numeric type of right operand */ i64 iA; /* Integer value of left operand */ i64 iB; /* Integer value of right operand */ double rA; /* Real value of left operand */ double rB; /* Real value of right operand */ pIn1 = &aMem[pOp->p1]; - applyNumericAffinity(pIn1); + type1 = numericType(pIn1); pIn2 = &aMem[pOp->p2]; - applyNumericAffinity(pIn2); + type2 = numericType(pIn2); pOut = &aMem[pOp->p3]; flags = pIn1->flags | pIn2->flags; if( (flags & MEM_Null)!=0 ) goto arithmetic_result_is_null; - if( (pIn1->flags & pIn2->flags & MEM_Int)==MEM_Int ){ + if( (type1 & type2 & MEM_Int)!=0 ){ iA = pIn1->u.i; iB = pIn2->u.i; bIntint = 1; switch( pOp->opcode ){ case OP_Add: if( sqlite3AddInt64(&iB,iA) ) goto fp_math; break; @@ -1417,11 +1443,11 @@ if( sqlite3IsNaN(rB) ){ goto arithmetic_result_is_null; } pOut->r = rB; MemSetTypeFlag(pOut, MEM_Real); - if( (flags & MEM_Real)==0 && !bIntint ){ + if( ((type1|type2)&MEM_Real)==0 && !bIntint ){ sqlite3VdbeIntegerAffinity(pOut); } #endif } break; @@ -1993,10 +2019,11 @@ aPermute = pOp->p4.ai; break; } /* Opcode: Compare P1 P2 P3 P4 P5 +** Synopsis: r[P1@P3] <-> r[P2@P3] ** ** Compare two vectors of registers in reg(P1)..reg(P1+P3-1) (call this ** vector "A") and in reg(P2)..reg(P2+P3-1) ("B"). Save the result of ** the comparison for use by the next OP_Jump instruct. ** @@ -3328,10 +3355,11 @@ assert( pOp->p1>=0 ); assert( pOp->p2>=0 ); pCx = allocateCursor(p, pOp->p1, pOp->p2, -1, 1); if( pCx==0 ) goto no_mem; pCx->nullRow = 1; + pCx->isEphemeral = 1; rc = sqlite3BtreeOpen(db->pVfs, 0, db, &pCx->pBt, BTREE_OMIT_JOURNAL | BTREE_SINGLE | pOp->p5, vfsFlags); if( rc==SQLITE_OK ){ rc = sqlite3BtreeBeginTrans(pCx->pBt, 1); } @@ -3818,11 +3846,11 @@ pC->seekResult = res; break; } /* Opcode: Sequence P1 P2 * * * -** Synopsis: r[P2]=rowid +** Synopsis: r[P2]=cursor[P1].ctr++ ** ** Find the next available sequence number for cursor P1. ** Write the sequence number into register P2. ** The sequence number on the cursor is incremented after this ** instruction. @@ -4509,10 +4537,11 @@ VdbeCursor *pC; int res; pC = p->apCsr[pOp->p1]; assert( isSorter(pC) ); + res = 0; rc = sqlite3VdbeSorterNext(db, pC, &res); goto next_tail; case OP_PrevIfOpen: /* jump */ case OP_NextIfOpen: /* jump */ if( p->apCsr[pOp->p1]==0 ) break; @@ -4866,10 +4895,33 @@ aMem[pOp->p3].u.i += nChange; } } break; } + +/* Opcode: ResetSorter P1 * * * * +** +** Delete all contents from the ephemeral table or sorter +** that is open on cursor P1. +** +** This opcode only works for cursors used for sorting and +** opened with OP_OpenEphemeral or OP_SorterOpen. +*/ +case OP_ResetSorter: { + VdbeCursor *pC; + + assert( pOp->p1>=0 && pOp->p1nCursor ); + pC = p->apCsr[pOp->p1]; + assert( pC!=0 ); + if( pC->pSorter ){ + sqlite3VdbeSorterReset(db, pC->pSorter); + }else{ + assert( pC->isEphemeral ); + rc = sqlite3BtreeClearTableOfCursor(pC->pCursor); + } + break; +} /* Opcode: CreateTable P1 P2 * * * ** Synopsis: r[P2]=root iDb=P1 ** ** Allocate a new table in the main database file if P1==0 or in the Index: src/vdbeInt.h ================================================================== --- src/vdbeInt.h +++ src/vdbeInt.h @@ -70,10 +70,11 @@ u16 nHdrParsed; /* Number of header fields parsed so far */ i8 iDb; /* Index of cursor database in db->aDb[] (or -1) */ u8 nullRow; /* True if pointing to a row with no data */ u8 rowidIsValid; /* True if lastRowid is valid */ u8 deferredMoveto; /* A call to sqlite3BtreeMoveto() is needed */ + Bool isEphemeral:1; /* True for an ephemeral table */ Bool useRandomRowid:1;/* Generate new record numbers semi-randomly */ Bool isTable:1; /* True if a table requiring integer keys */ Bool isOrdered:1; /* True if the underlying table is BTREE_UNORDERED */ sqlite3_vtab_cursor *pVtabCursor; /* The cursor for a virtual table */ i64 seqCount; /* Sequence counter */ @@ -435,10 +436,11 @@ void sqlite3VdbeFrameDelete(VdbeFrame*); int sqlite3VdbeFrameRestore(VdbeFrame *); int sqlite3VdbeTransferError(Vdbe *p); int sqlite3VdbeSorterInit(sqlite3 *, VdbeCursor *); +void sqlite3VdbeSorterReset(sqlite3 *, VdbeSorter *); void sqlite3VdbeSorterClose(sqlite3 *, VdbeCursor *); int sqlite3VdbeSorterRowkey(const VdbeCursor *, Mem *); int sqlite3VdbeSorterNext(sqlite3 *, const VdbeCursor *, int *); int sqlite3VdbeSorterRewind(sqlite3 *, const VdbeCursor *, int *); int sqlite3VdbeSorterWrite(sqlite3 *, const VdbeCursor *, Mem *); Index: src/vdbeaux.c ================================================================== --- src/vdbeaux.c +++ src/vdbeaux.c @@ -781,11 +781,13 @@ assert( addrnOp ); if( addr<0 ){ addr = p->nOp - 1; } pOp = &p->aOp[addr]; - assert( pOp->p4type==P4_NOTUSED || pOp->p4type==P4_INT32 ); + assert( pOp->p4type==P4_NOTUSED + || pOp->p4type==P4_INT32 + || pOp->p4type==P4_KEYINFO ); freeP4(db, pOp->p4type, pOp->p4.p); pOp->p4.p = 0; if( n==P4_INT32 ){ /* Note: this cast is safe, because the origin data point was an int ** that was cast to a (const char *). */ @@ -2731,11 +2733,11 @@ int hasMoved; int rc = sqlite3BtreeCursorHasMoved(p->pCursor, &hasMoved); if( rc ) return rc; if( hasMoved ){ p->cacheStatus = CACHE_STALE; - p->nullRow = 1; + if( hasMoved==2 ) p->nullRow = 1; } } return SQLITE_OK; } Index: src/vdbesort.c ================================================================== --- src/vdbesort.c +++ src/vdbesort.c @@ -595,15 +595,17 @@ ** Free all resources owned by the object indicated by argument pThread. All ** fields of *pThread are zeroed before returning. */ static void vdbeSorterThreadCleanup(sqlite3 *db, SorterThread *pThread){ sqlite3DbFree(db, pThread->pUnpacked); + pThread->pUnpacked = 0; vdbeSorterRecordFree(0, pThread->pList); + pThread->pList = 0; if( pThread->pTemp1 ){ sqlite3OsCloseFree(pThread->pTemp1); + pThread->pTemp1 = 0; } - memset(pThread, 0, sizeof(SorterThread)); } /* ** Join all threads. */ @@ -640,41 +642,58 @@ if( pNew ){ pNew->nTree = N; pNew->aIter = (VdbeSorterIter*)&pNew[1]; pNew->aTree = (int*)&pNew->aIter[N]; } - return pNew; } + +/* +** Reset a merger +*/ +static void vdbeSorterMergerReset(SorterMerger *pMerger){ + int i; + if( pMerger ){ + for(i=0; inTree; i++){ + vdbeSorterIterZero(&pMerger->aIter[i]); + } + } +} + /* ** Free the SorterMerger object passed as the only argument. */ static void vdbeSorterMergerFree(SorterMerger *pMerger){ - if( pMerger ){ - int i; - for(i=0; inTree; i++){ - vdbeSorterIterZero(&pMerger->aIter[i]); - } - sqlite3_free(pMerger); + vdbeSorterMergerReset(pMerger); + sqlite3_free(pMerger); +} + +/* +** Reset a sorting cursor back to its original empty state. +*/ +void sqlite3VdbeSorterReset(sqlite3 *db, VdbeSorter *pSorter){ + int i; + vdbeSorterJoinAll(pSorter, SQLITE_OK); + for(i=0; iaThread[i]; + vdbeSorterThreadCleanup(db, pThread); } + vdbeSorterRecordFree(0, pSorter->pRecord); + vdbeSorterMergerReset(pSorter->pMerger); + pSorter->pRecord = 0; + pSorter->nInMemory = 0; + pSorter->bUsePMA = 0; } /* ** Free any cursor components allocated by sqlite3VdbeSorterXXX routines. */ void sqlite3VdbeSorterClose(sqlite3 *db, VdbeCursor *pCsr){ VdbeSorter *pSorter = pCsr->pSorter; if( pSorter ){ - int i; - vdbeSorterJoinAll(pSorter, SQLITE_OK); - for(i=0; iaThread[i]; - vdbeSorterThreadCleanup(db, pThread); - } - - vdbeSorterRecordFree(0, pSorter->pRecord); + sqlite3VdbeSorterReset(db, pSorter); vdbeSorterMergerFree(pSorter->pMerger); sqlite3DbFree(db, pSorter); pCsr->pSorter = 0; } } Index: src/where.c ================================================================== --- src/where.c +++ src/where.c @@ -37,18 +37,19 @@ /* ** Return TRUE if the WHERE clause returns rows in ORDER BY order. ** Return FALSE if the output needs to be sorted. */ int sqlite3WhereIsOrdered(WhereInfo *pWInfo){ - return pWInfo->bOBSat!=0; + return pWInfo->nOBSat; } /* ** Return the VDBE address or label to jump to in order to continue ** immediately with the next row of a WHERE clause. */ int sqlite3WhereContinueLabel(WhereInfo *pWInfo){ + assert( pWInfo->iContinue!=0 ); return pWInfo->iContinue; } /* ** Return the VDBE address or label to jump to in order to break @@ -3034,12 +3035,15 @@ ** a single iteration. This means that the first row returned ** should not have a NULL value stored in 'x'. If column 'x' is ** the first one after the nEq equality constraints in the index, ** this requires some special handling. */ + assert( pWInfo->pOrderBy==0 + || pWInfo->pOrderBy->nExpr==1 + || (pWInfo->wctrlFlags&WHERE_ORDERBY_MIN)==0 ); if( (pWInfo->wctrlFlags&WHERE_ORDERBY_MIN)!=0 - && (pWInfo->bOBSat!=0) + && pWInfo->nOBSat>0 && (pIdx->nKeyCol>nEq) ){ assert( pLoop->u.btree.nSkip==0 ); bSeekPastNull = 1; nExtraReg = 1; @@ -3206,12 +3210,11 @@ pLevel->op = OP_Prev; }else{ pLevel->op = OP_Next; } pLevel->p1 = iIdxCur; - assert( (WHERE_UNQ_WANTED>>16)==1 ); - pLevel->p3 = (pLoop->wsFlags>>16)&1; + pLevel->p3 = (pLoop->wsFlags&WHERE_UNQ_WANTED)!=0 ? 1:0; if( (pLoop->wsFlags & WHERE_CONSTRAINT)==0 ){ pLevel->p5 = SQLITE_STMTSTATUS_FULLSCAN_STEP; }else{ assert( pLevel->p5==0 ); } @@ -4008,10 +4011,12 @@ nIn = 46; assert( 46==sqlite3LogEst(25) ); }else if( ALWAYS(pExpr->x.pList && pExpr->x.pList->nExpr) ){ /* "x IN (value, value, ...)" */ nIn = sqlite3LogEst(pExpr->x.pList->nExpr); } + assert( nIn>0 ); /* RHS always has 2 or more terms... The parser + ** changes "x IN (?)" into "x=?". */ pNew->rRun += nIn; pNew->u.btree.nEq++; pNew->nOut = nRowEst + nInMul + nIn; }else if( pTerm->eOperator & (WO_EQ) ){ assert( @@ -4504,12 +4509,12 @@ assert( pNew->nLTerm<=pNew->nLSlot ); pNew->u.vtab.idxNum = pIdxInfo->idxNum; pNew->u.vtab.needFree = pIdxInfo->needToFreeIdxStr; pIdxInfo->needToFreeIdxStr = 0; pNew->u.vtab.idxStr = pIdxInfo->idxStr; - pNew->u.vtab.isOrdered = (u8)((pIdxInfo->nOrderBy!=0) - && pIdxInfo->orderByConsumed); + pNew->u.vtab.isOrdered = (i8)(pIdxInfo->orderByConsumed ? + pIdxInfo->nOrderBy : 0); pNew->rSetup = 0; pNew->rRun = sqlite3LogEstFromDouble(pIdxInfo->estimatedCost); pNew->nOut = sqlite3LogEst(pIdxInfo->estimatedRows); whereLoopInsert(pBuilder, pNew); if( pNew->u.vtab.needFree ){ @@ -4666,25 +4671,25 @@ } /* ** Examine a WherePath (with the addition of the extra WhereLoop of the 5th ** parameters) to see if it outputs rows in the requested ORDER BY -** (or GROUP BY) without requiring a separate sort operation. Return: +** (or GROUP BY) without requiring a separate sort operation. Return N: ** -** 0: ORDER BY is not satisfied. Sorting required -** 1: ORDER BY is satisfied. Omit sorting -** -1: Unknown at this time +** N>0: N terms of the ORDER BY clause are satisfied +** N==0: No terms of the ORDER BY clause are satisfied +** N<0: Unknown yet how many terms of ORDER BY might be satisfied. ** ** Note that processing for WHERE_GROUPBY and WHERE_DISTINCTBY is not as ** strict. With GROUP BY and DISTINCT the only requirement is that ** equivalent rows appear immediately adjacent to one another. GROUP BY ** and DISTINT do not require rows to appear in any particular order as long ** as equivelent rows are grouped together. Thus for GROUP BY and DISTINCT ** the pOrderBy terms can be matched in any order. With ORDER BY, the ** pOrderBy terms must be matched in strict left-to-right order. */ -static int wherePathSatisfiesOrderBy( +static i8 wherePathSatisfiesOrderBy( WhereInfo *pWInfo, /* The WHERE clause */ ExprList *pOrderBy, /* ORDER BY or GROUP BY or DISTINCT clause to check */ WherePath *pPath, /* The WherePath to check */ u16 wctrlFlags, /* Might contain WHERE_GROUPBY or WHERE_DISTINCTBY */ u16 nLoop, /* Number of entries in pPath->aLoop[] */ @@ -4864,28 +4869,28 @@ if( !pColl ) pColl = db->pDfltColl; if( sqlite3StrICmp(pColl->zName, pIndex->azColl[j])!=0 ) continue; } isMatch = 1; break; + } + if( isMatch && (pWInfo->wctrlFlags & WHERE_GROUPBY)==0 ){ + /* Make sure the sort order is compatible in an ORDER BY clause. + ** Sort order is irrelevant for a GROUP BY clause. */ + if( revSet ){ + if( (rev ^ revIdx)!=pOrderBy->a[i].sortOrder ) isMatch = 0; + }else{ + rev = revIdx ^ pOrderBy->a[i].sortOrder; + if( rev ) *pRevMask |= MASKBIT(iLoop); + revSet = 1; + } } if( isMatch ){ if( iColumn<0 ){ testcase( distinctColumns==0 ); distinctColumns = 1; } obSat |= MASKBIT(i); - if( (pWInfo->wctrlFlags & WHERE_GROUPBY)==0 ){ - /* Make sure the sort order is compatible in an ORDER BY clause. - ** Sort order is irrelevant for a GROUP BY clause. */ - if( revSet ){ - if( (rev ^ revIdx)!=pOrderBy->a[i].sortOrder ) return 0; - }else{ - rev = revIdx ^ pOrderBy->a[i].sortOrder; - if( rev ) *pRevMask |= MASKBIT(iLoop); - revSet = 1; - } - } }else{ /* No match found */ if( j==0 || j0; i--){ + Bitmask m = MASKBIT(i) - 1; + if( (obSat&m)==m ) return i; + } + return 0; + } return -1; } #ifdef WHERETRACE_ENABLED /* For debugging use only: */ @@ -4951,15 +4962,15 @@ Parse *pParse; /* Parsing context */ sqlite3 *db; /* The database connection */ int iLoop; /* Loop counter over the terms of the join */ int ii, jj; /* Loop counters */ int mxI = 0; /* Index of next entry to replace */ + int nOrderBy; /* Number of ORDER BY clause terms */ LogEst rCost; /* Cost of a path */ LogEst nOut; /* Number of outputs */ LogEst mxCost = 0; /* Maximum cost of a set of paths */ LogEst mxOut = 0; /* Maximum nOut value on the set of paths */ - LogEst rSortCost; /* Cost to do a sort */ int nTo, nFrom; /* Number of valid entries in aTo[] and aFrom[] */ WherePath *aFrom; /* All nFrom paths at the previous level */ WherePath *aTo; /* The nTo best paths at the current level */ WherePath *pFrom; /* An element of aFrom[] that we are working on */ WherePath *pTo; /* An element of aTo[] that we are working on */ @@ -4997,20 +5008,16 @@ aFrom[0].nRow = MIN(pParse->nQueryLoop, 46); assert( 46==sqlite3LogEst(25) ); nFrom = 1; /* Precompute the cost of sorting the final result set, if the caller ** to sqlite3WhereBegin() was concerned about sorting */ - rSortCost = 0; if( pWInfo->pOrderBy==0 || nRowEst==0 ){ - aFrom[0].isOrderedValid = 1; + aFrom[0].isOrdered = 0; + nOrderBy = 0; }else{ - /* TUNING: Estimated cost of sorting is 48*N*log2(N) where N is the - ** number of output rows. The 48 is the expected size of a row to sort. - ** FIXME: compute a better estimate of the 48 multiplier based on the - ** result set expressions. */ - rSortCost = nRowEst + estLog(nRowEst); - WHERETRACE(0x002,("---- sort cost=%-3d\n", rSortCost)); + aFrom[0].isOrdered = -1; + nOrderBy = pWInfo->pOrderBy->nExpr; } /* Compute successively longer WherePaths using the previous generation ** of WherePaths as the basis for the next. Keep track of the mxChoice ** best paths at each generation */ @@ -5018,43 +5025,48 @@ nTo = 0; for(ii=0, pFrom=aFrom; iipLoops; pWLoop; pWLoop=pWLoop->pNextLoop){ Bitmask maskNew; Bitmask revMask = 0; - u8 isOrderedValid = pFrom->isOrderedValid; - u8 isOrdered = pFrom->isOrdered; + i8 isOrdered = pFrom->isOrdered; if( (pWLoop->prereq & ~pFrom->maskLoop)!=0 ) continue; if( (pWLoop->maskSelf & pFrom->maskLoop)!=0 ) continue; /* At this point, pWLoop is a candidate to be the next loop. ** Compute its cost */ rCost = sqlite3LogEstAdd(pWLoop->rSetup,pWLoop->rRun + pFrom->nRow); rCost = sqlite3LogEstAdd(rCost, pFrom->rCost); nOut = pFrom->nRow + pWLoop->nOut; maskNew = pFrom->maskLoop | pWLoop->maskSelf; - if( !isOrderedValid ){ - switch( wherePathSatisfiesOrderBy(pWInfo, + if( isOrdered<0 ){ + isOrdered = wherePathSatisfiesOrderBy(pWInfo, pWInfo->pOrderBy, pFrom, pWInfo->wctrlFlags, - iLoop, pWLoop, &revMask) ){ - case 1: /* Yes. pFrom+pWLoop does satisfy the ORDER BY clause */ - isOrdered = 1; - isOrderedValid = 1; - break; - case 0: /* No. pFrom+pWLoop will require a separate sort */ - isOrdered = 0; - isOrderedValid = 1; - rCost = sqlite3LogEstAdd(rCost, rSortCost); - break; - default: /* Cannot tell yet. Try again on the next iteration */ - break; + iLoop, pWLoop, &revMask); + if( isOrdered>=0 && isOrderedwctrlFlags & WHERE_WANT_DISTINCT ){ + rSortCost += 16; + } + WHERETRACE(0x002, + ("---- sort cost=%-3d (%d/%d) increases cost %3d to %-3d\n", + rSortCost, (nOrderBy-isOrdered), nOrderBy, rCost, + sqlite3LogEstAdd(rCost,rSortCost))); + rCost = sqlite3LogEstAdd(rCost, rSortCost); } }else{ revMask = pFrom->revLoop; } /* Check to see if pWLoop should be added to the mxChoice best so far */ for(jj=0, pTo=aTo; jjmaskLoop==maskNew - && pTo->isOrderedValid==isOrderedValid + && ((pTo->isOrdered^isOrdered)&80)==0 && ((pTo->rCost<=rCost && pTo->nRow<=nOut) || (pTo->rCost>=rCost && pTo->nRow>=nOut)) ){ testcase( jj==nTo-1 ); break; @@ -5064,11 +5076,11 @@ if( nTo>=mxChoice && rCost>=mxCost ){ #ifdef WHERETRACE_ENABLED /* 0x4 */ if( sqlite3WhereTrace&0x4 ){ sqlite3DebugPrintf("Skip %s cost=%-3d,%3d order=%c\n", wherePathName(pFrom, iLoop, pWLoop), rCost, nOut, - isOrderedValid ? (isOrdered ? 'Y' : 'N') : '?'); + isOrdered>=0 ? isOrdered+'0' : '?'); } #endif continue; } /* Add a new Path to the aTo[] set */ @@ -5082,24 +5094,24 @@ pTo = &aTo[jj]; #ifdef WHERETRACE_ENABLED /* 0x4 */ if( sqlite3WhereTrace&0x4 ){ sqlite3DebugPrintf("New %s cost=%-3d,%3d order=%c\n", wherePathName(pFrom, iLoop, pWLoop), rCost, nOut, - isOrderedValid ? (isOrdered ? 'Y' : 'N') : '?'); + isOrdered>=0 ? isOrdered+'0' : '?'); } #endif }else{ if( pTo->rCost<=rCost && pTo->nRow<=nOut ){ #ifdef WHERETRACE_ENABLED /* 0x4 */ if( sqlite3WhereTrace&0x4 ){ sqlite3DebugPrintf( "Skip %s cost=%-3d,%3d order=%c", wherePathName(pFrom, iLoop, pWLoop), rCost, nOut, - isOrderedValid ? (isOrdered ? 'Y' : 'N') : '?'); + isOrdered>=0 ? isOrdered+'0' : '?'); sqlite3DebugPrintf(" vs %s cost=%-3d,%d order=%c\n", wherePathName(pTo, iLoop+1, 0), pTo->rCost, pTo->nRow, - pTo->isOrderedValid ? (pTo->isOrdered ? 'Y' : 'N') : '?'); + pTo->isOrdered>=0 ? pTo->isOrdered+'0' : '?'); } #endif testcase( pTo->rCost==rCost ); continue; } @@ -5108,23 +5120,22 @@ #ifdef WHERETRACE_ENABLED /* 0x4 */ if( sqlite3WhereTrace&0x4 ){ sqlite3DebugPrintf( "Update %s cost=%-3d,%3d order=%c", wherePathName(pFrom, iLoop, pWLoop), rCost, nOut, - isOrderedValid ? (isOrdered ? 'Y' : 'N') : '?'); + isOrdered>=0 ? isOrdered+'0' : '?'); sqlite3DebugPrintf(" was %s cost=%-3d,%3d order=%c\n", wherePathName(pTo, iLoop+1, 0), pTo->rCost, pTo->nRow, - pTo->isOrderedValid ? (pTo->isOrdered ? 'Y' : 'N') : '?'); + pTo->isOrdered>=0 ? pTo->isOrdered+'0' : '?'); } #endif } /* pWLoop is a winner. Add it to the set of best so far */ pTo->maskLoop = pFrom->maskLoop | pWLoop->maskSelf; pTo->revLoop = revMask; pTo->nRow = nOut; pTo->rCost = rCost; - pTo->isOrderedValid = isOrderedValid; pTo->isOrdered = isOrdered; memcpy(pTo->aLoop, pFrom->aLoop, sizeof(WhereLoop*)*iLoop); pTo->aLoop[iLoop] = pWLoop; if( nTo>=mxChoice ){ mxI = 0; @@ -5145,12 +5156,12 @@ if( sqlite3WhereTrace>=2 ){ sqlite3DebugPrintf("---- after round %d ----\n", iLoop); for(ii=0, pTo=aTo; iirCost, pTo->nRow, - pTo->isOrderedValid ? (pTo->isOrdered ? 'Y' : 'N') : '?'); - if( pTo->isOrderedValid && pTo->isOrdered ){ + pTo->isOrdered>=0 ? (pTo->isOrdered+'0') : '?'); + if( pTo->isOrdered>0 ){ sqlite3DebugPrintf(" rev=0x%llx\n", pTo->revLoop); }else{ sqlite3DebugPrintf("\n"); } } @@ -5189,17 +5200,22 @@ && nRowEst ){ Bitmask notUsed; int rc = wherePathSatisfiesOrderBy(pWInfo, pWInfo->pResultSet, pFrom, WHERE_DISTINCTBY, nLoop-1, pFrom->aLoop[nLoop-1], ¬Used); - if( rc==1 ) pWInfo->eDistinct = WHERE_DISTINCT_ORDERED; + if( rc==pWInfo->pResultSet->nExpr ){ + pWInfo->eDistinct = WHERE_DISTINCT_ORDERED; + } } - if( pFrom->isOrdered ){ + if( pWInfo->pOrderBy ){ if( pWInfo->wctrlFlags & WHERE_DISTINCTBY ){ - pWInfo->eDistinct = WHERE_DISTINCT_ORDERED; + if( pFrom->isOrdered==pWInfo->pOrderBy->nExpr ){ + pWInfo->eDistinct = WHERE_DISTINCT_ORDERED; + } }else{ - pWInfo->bOBSat = 1; + pWInfo->nOBSat = pFrom->isOrdered; + if( pWInfo->nOBSat<0 ) pWInfo->nOBSat = 0; pWInfo->revMask = pFrom->revLoop; } } pWInfo->nRowOut = pFrom->nRow; @@ -5280,11 +5296,11 @@ pLoop->nOut = (LogEst)1; pWInfo->a[0].pWLoop = pLoop; pLoop->maskSelf = getMask(&pWInfo->sMaskSet, iCur); pWInfo->a[0].iTabCur = iCur; pWInfo->nRowOut = 1; - if( pWInfo->pOrderBy ) pWInfo->bOBSat = 1; + if( pWInfo->pOrderBy ) pWInfo->nOBSat = pWInfo->pOrderBy->nExpr; if( pWInfo->wctrlFlags & WHERE_WANT_DISTINCT ){ pWInfo->eDistinct = WHERE_DISTINCT_UNIQUE; } #ifdef SQLITE_DEBUG pLoop->cId = '0'; @@ -5384,11 +5400,11 @@ */ WhereInfo *sqlite3WhereBegin( Parse *pParse, /* The parser context */ SrcList *pTabList, /* FROM clause: A list of all tables to be scanned */ Expr *pWhere, /* The WHERE clause */ - ExprList *pOrderBy, /* An ORDER BY clause, or NULL */ + ExprList *pOrderBy, /* An ORDER BY (or GROUP BY) clause, or NULL */ ExprList *pResultSet, /* Result set of the query */ u16 wctrlFlags, /* One of the WHERE_* flags defined in sqliteInt.h */ int iIdxCur /* If WHERE_ONETABLE_ONLY is set, index cursor number */ ){ int nByteWInfo; /* Num. bytes allocated for WhereInfo struct */ @@ -5406,10 +5422,14 @@ /* Variable initialization */ db = pParse->db; memset(&sWLB, 0, sizeof(sWLB)); + + /* An ORDER/GROUP BY clause of more than 63 terms cannot be optimized */ + testcase( pOrderBy && pOrderBy->nExpr==BMS-1 ); + if( pOrderBy && pOrderBy->nExpr>=BMS ) pOrderBy = 0; sWLB.pOrderBy = pOrderBy; /* Disable the DISTINCT optimization if SQLITE_DistinctOpt is set via ** sqlite3_test_ctrl(SQLITE_TESTCTRL_OPTIMIZATIONS,...) */ if( OptimizationDisabled(db, SQLITE_DistinctOpt) ){ @@ -5450,11 +5470,11 @@ pWInfo->nLevel = nTabList; pWInfo->pParse = pParse; pWInfo->pTabList = pTabList; pWInfo->pOrderBy = pOrderBy; pWInfo->pResultSet = pResultSet; - pWInfo->iBreak = sqlite3VdbeMakeLabel(v); + pWInfo->iBreak = pWInfo->iContinue = sqlite3VdbeMakeLabel(v); pWInfo->wctrlFlags = wctrlFlags; pWInfo->savedNQueryLoop = pParse->nQueryLoop; pMaskSet = &pWInfo->sMaskSet; sWLB.pWInfo = pWInfo; sWLB.pWC = &pWInfo->sWC; @@ -5484,11 +5504,11 @@ } /* Special case: No FROM clause */ if( nTabList==0 ){ - if( pOrderBy ) pWInfo->bOBSat = 1; + if( pOrderBy ) pWInfo->nOBSat = pOrderBy->nExpr; if( wctrlFlags & WHERE_WANT_DISTINCT ){ pWInfo->eDistinct = WHERE_DISTINCT_UNIQUE; } } @@ -5595,12 +5615,12 @@ } #ifdef WHERETRACE_ENABLED /* !=0 */ if( sqlite3WhereTrace ){ int ii; sqlite3DebugPrintf("---- Solution nRow=%d", pWInfo->nRowOut); - if( pWInfo->bOBSat ){ - sqlite3DebugPrintf(" ORDERBY=0x%llx", pWInfo->revMask); + if( pWInfo->nOBSat>0 ){ + sqlite3DebugPrintf(" ORDERBY=%d,0x%llx", pWInfo->nOBSat, pWInfo->revMask); } switch( pWInfo->eDistinct ){ case WHERE_DISTINCT_UNIQUE: { sqlite3DebugPrintf(" DISTINCT=unique"); break; Index: src/whereInt.h ================================================================== --- src/whereInt.h +++ src/whereInt.h @@ -119,11 +119,11 @@ Index *pIndex; /* Index used, or NULL */ } btree; struct { /* Information for virtual tables */ int idxNum; /* Index number */ u8 needFree; /* True if sqlite3_free(idxStr) is needed */ - u8 isOrdered; /* True if satisfies ORDER BY */ + i8 isOrdered; /* True if satisfies ORDER BY */ u16 omitMask; /* Terms that may be omitted */ char *idxStr; /* Index identifier string */ } vtab; } u; u32 wsFlags; /* WHERE_* flags describing the plan */ @@ -181,12 +181,11 @@ struct WherePath { Bitmask maskLoop; /* Bitmask of all WhereLoop objects in this path */ Bitmask revLoop; /* aLoop[]s that should be reversed for ORDER BY */ LogEst nRow; /* Estimated number of rows generated by this path */ LogEst rCost; /* Total cost of this path */ - u8 isOrdered; /* True if this path satisfies ORDER BY */ - u8 isOrderedValid; /* True if the isOrdered field is valid */ + i8 isOrdered; /* No. of ORDER BY terms satisfied. -1 for unknown */ WhereLoop **aLoop; /* Array of WhereLoop objects implementing this path */ }; /* ** The query generator uses an array of instances of this structure to @@ -396,11 +395,11 @@ ExprList *pResultSet; /* Result set. DISTINCT operates on these */ WhereLoop *pLoops; /* List of all WhereLoop objects */ Bitmask revMask; /* Mask of ORDER BY terms that need reversing */ LogEst nRowOut; /* Estimated number of output rows */ u16 wctrlFlags; /* Flags originally passed to sqlite3WhereBegin() */ - u8 bOBSat; /* ORDER BY satisfied by indices */ + i8 nOBSat; /* Number of ORDER BY terms satisfied by indices */ u8 okOnePass; /* Ok to use one-pass algorithm for UPDATE/DELETE */ u8 untestedTerms; /* Not all WHERE terms resolved by outer loop */ u8 eDistinct; /* One of the WHERE_DISTINCT_* values below */ u8 nLevel; /* Number of nested loop */ int iTop; /* The very beginning of the WHERE loop */ Index: test/distinct.test ================================================================== --- test/distinct.test +++ test/distinct.test @@ -160,11 +160,11 @@ } foreach {tn sql temptables res} { 1 "a, b FROM t1" {} {A B a b} 2 "b, a FROM t1" {} {B A b a} - 3 "a, b, c FROM t1" {hash} {a b c A B C} + 3 "a, b, c FROM t1" {hash} {A B C a b c} 4 "a, b, c FROM t1 ORDER BY a, b, c" {btree} {A B C a b c} 5 "b FROM t1 WHERE a = 'a'" {} {b} 6 "b FROM t1 ORDER BY +b COLLATE binary" {btree hash} {B b} 7 "a FROM t1" {} {A a} 8 "b COLLATE nocase FROM t1" {} {b} Index: test/in4.test ================================================================== --- test/in4.test +++ test/in4.test @@ -156,7 +156,184 @@ execsql { SELECT * FROM t3 WHERE x IN (1, 2) OR y IN ()} } {1 1 1} do_test in4-3.12 { execsql { SELECT * FROM t3 WHERE x IN (1, 2) AND y IN ()} } {} + +# Tests for "... IN (?)" and "... NOT IN (?)". In other words, tests +# for when the RHS of IN is a single expression. This should work the +# same as the == and <> operators. +# +do_execsql_test in4-3.21 { + SELECT * FROM t3 WHERE x=10 AND y IN (10); +} {10 10 10} +do_execsql_test in4-3.22 { + SELECT * FROM t3 WHERE x IN (10) AND y=10; +} {10 10 10} +do_execsql_test in4-3.23 { + SELECT * FROM t3 WHERE x IN (10) AND y IN (10); +} {10 10 10} +do_execsql_test in4-3.24 { + SELECT * FROM t3 WHERE x=1 AND y NOT IN (10); +} {1 1 1} +do_execsql_test in4-3.25 { + SELECT * FROM t3 WHERE x NOT IN (10) AND y=1; +} {1 1 1} +do_execsql_test in4-3.26 { + SELECT * FROM t3 WHERE x NOT IN (10) AND y NOT IN (10); +} {1 1 1} + +# The query planner recognizes that "x IN (?)" only generates a +# single match and can use this information to optimize-out ORDER BY +# clauses. +# +do_execsql_test in4-3.31 { + DROP INDEX t3i1; + CREATE UNIQUE INDEX t3xy ON t3(x,y); + + SELECT *, '|' FROM t3 A, t3 B + WHERE A.x=10 AND A.y IN (10) + AND B.x=1 AND B.y IN (1); +} {10 10 10 1 1 1 |} +do_execsql_test in4-3.32 { + EXPLAIN QUERY PLAN + SELECT *, '|' FROM t3 A, t3 B + WHERE A.x=10 AND A.y IN (10) + AND B.x=1 AND B.y IN (1); +} {~/B-TREE/} ;# No separate sorting pass +do_execsql_test in4-3.33 { + SELECT *, '|' FROM t3 A, t3 B + WHERE A.x IN (10) AND A.y=10 + AND B.x IN (1) AND B.y=1; +} {10 10 10 1 1 1 |} +do_execsql_test in4-3.34 { + EXPLAIN QUERY PLAN + SELECT *, '|' FROM t3 A, t3 B + WHERE A.x IN (10) AND A.y=10 + AND B.x IN (1) AND B.y=1; +} {~/B-TREE/} ;# No separate sorting pass + +# An expression of the form "x IN (?,?)" creates an ephemeral table to +# hold the list of values on the RHS. But "x IN (?)" does not create +# an ephemeral table. +# +do_execsql_test in4-3.41 { + SELECT * FROM t3 WHERE x IN (10,11); +} {10 10 10} +do_execsql_test in4-3.42 { + EXPLAIN + SELECT * FROM t3 WHERE x IN (10,11); +} {/OpenEphemeral/} +do_execsql_test in4-3.43 { + SELECT * FROM t3 WHERE x IN (10); +} {10 10 10} +do_execsql_test in4-3.44 { + EXPLAIN + SELECT * FROM t3 WHERE x IN (10); +} {~/OpenEphemeral/} +do_execsql_test in4-3.45 { + SELECT * FROM t3 WHERE x NOT IN (10,11); +} {1 1 1} +do_execsql_test in4-3.46 { + EXPLAIN + SELECT * FROM t3 WHERE x NOT IN (10,11); +} {/OpenEphemeral/} +do_execsql_test in4-3.47 { + SELECT * FROM t3 WHERE x NOT IN (10); +} {1 1 1} +do_execsql_test in4-3.48 { + EXPLAIN + SELECT * FROM t3 WHERE x NOT IN (10); +} {~/OpenEphemeral/} + +# Make sure that when "x IN (?)" is converted into "x==?" that collating +# sequence and affinity computations do not get messed up. +# +do_execsql_test in4-4.1 { + CREATE TABLE t4a(a TEXT, b TEXT COLLATE nocase, c); + INSERT INTO t4a VALUES('ABC','abc',1); + INSERT INTO t4a VALUES('def','xyz',2); + INSERT INTO t4a VALUES('ghi','ghi',3); + SELECT c FROM t4a WHERE a=b ORDER BY c; +} {3} +do_execsql_test in4-4.2 { + SELECT c FROM t4a WHERE b=a ORDER BY c; +} {1 3} +do_execsql_test in4-4.3 { + SELECT c FROM t4a WHERE (a||'')=b ORDER BY c; +} {1 3} +do_execsql_test in4-4.4 { + SELECT c FROM t4a WHERE (a||'')=(b||'') ORDER BY c; +} {3} +do_execsql_test in4-4.5 { + SELECT c FROM t4a WHERE a IN (b) ORDER BY c; +} {3} +do_execsql_test in4-4.6 { + SELECT c FROM t4a WHERE (a||'') IN (b) ORDER BY c; +} {3} + + +do_execsql_test in4-4.11 { + CREATE TABLE t4b(a TEXT, b NUMERIC, c); + INSERT INTO t4b VALUES('1.0',1,4); + SELECT c FROM t4b WHERE a=b; +} {4} +do_execsql_test in4-4.12 { + SELECT c FROM t4b WHERE b=a; +} {4} +do_execsql_test in4-4.13 { + SELECT c FROM t4b WHERE +a=b; +} {4} +do_execsql_test in4-4.14 { + SELECT c FROM t4b WHERE a=+b; +} {} +do_execsql_test in4-4.15 { + SELECT c FROM t4b WHERE +b=a; +} {} +do_execsql_test in4-4.16 { + SELECT c FROM t4b WHERE b=+a; +} {4} +do_execsql_test in4-4.17 { + SELECT c FROM t4b WHERE a IN (b); +} {} +do_execsql_test in4-4.18 { + SELECT c FROM t4b WHERE b IN (a); +} {4} +do_execsql_test in4-4.19 { + SELECT c FROM t4b WHERE +b IN (a); +} {} + +do_execsql_test in4-5.1 { + CREATE TABLE t5(c INTEGER PRIMARY KEY, d TEXT COLLATE nocase); + INSERT INTO t5 VALUES(17, 'fuzz'); + SELECT 1 FROM t5 WHERE 'fuzz' IN (d); -- match + SELECT 2 FROM t5 WHERE 'FUZZ' IN (d); -- no match + SELECT 3 FROM t5 WHERE d IN ('fuzz'); -- match + SELECT 4 FROM t5 WHERE d IN ('FUZZ'); -- match +} {1 3 4} + +# An expression of the form "x IN (y)" can be used as "x=y" by the +# query planner when computing transitive constraints or to run the +# query using an index on y. +# +do_execsql_test in4-6.1 { + CREATE TABLE t6a(a INTEGER PRIMARY KEY, b); + INSERT INTO t6a VALUES(1,2),(3,4),(5,6); + CREATE TABLE t6b(c INTEGER PRIMARY KEY, d); + INSERT INTO t6b VALUES(4,44),(5,55),(6,66); + + SELECT * FROM t6a, t6b WHERE a=3 AND b IN (c); +} {3 4 4 44} +do_execsql_test in4-6.1-eqp { + EXPLAIN QUERY PLAN + SELECT * FROM t6a, t6b WHERE a=3 AND b IN (c); +} {~/SCAN/} +do_execsql_test in4-6.2 { + SELECT * FROM t6a, t6b WHERE a=3 AND c IN (b); +} {3 4 4 44} +do_execsql_test in4-6.2-eqp { + EXPLAIN QUERY PLAN + SELECT * FROM t6a, t6b WHERE a=3 AND c IN (b); +} {~/SCAN/} + finish_test Index: test/limit.test ================================================================== --- test/limit.test +++ test/limit.test @@ -613,7 +613,27 @@ db eval {SELECT z FROM v13c LIMIT 2 OFFSET 7} } {32} do_test limit-13.81 { db eval {SELECT z FROM v13c LIMIT 1 OFFSET 8} } {} + +do_execsql_test limit-14.1 { + SELECT 123 LIMIT 1 OFFSET 0 +} {123} +do_execsql_test limit-14.2 { + SELECT 123 LIMIT 1 OFFSET 1 +} {} +do_execsql_test limit-14.3 { + SELECT 123 LIMIT 0 OFFSET 0 +} {} +do_execsql_test limit-14.4 { + SELECT 123 LIMIT 0 OFFSET 1 +} {} +do_execsql_test limit-14.6 { + SELECT 123 LIMIT -1 OFFSET 0 +} {123} +do_execsql_test limit-14.7 { + SELECT 123 LIMIT -1 OFFSET 1 +} {} + finish_test Index: test/orderby5.test ================================================================== --- test/orderby5.test +++ test/orderby5.test @@ -62,14 +62,32 @@ } {~/B-TREE/} do_execsql_test 1.7 { EXPLAIN QUERY PLAN SELECT DISTINCT c, b, a FROM t1 WHERE +a=0; } {/B-TREE/} -do_execsql_test 2.1 { + +# In some cases, it is faster to do repeated index lookups than it is to +# sort. But in other cases, it is faster to sort than to do repeated index +# lookups. +# +do_execsql_test 2.1a { + CREATE TABLE t2(a,b,c); + CREATE INDEX t2bc ON t2(b,c); + ANALYZE; + INSERT INTO sqlite_stat1 VALUES('t1','t1bc','1000000 10 9'); + INSERT INTO sqlite_stat1 VALUES('t2','t2bc','100 10 5'); + ANALYZE sqlite_master; + + EXPLAIN QUERY PLAN + SELECT * FROM t2 WHERE a=0 ORDER BY a, b, c; +} {~/B-TREE/} +do_execsql_test 2.1b { EXPLAIN QUERY PLAN SELECT * FROM t1 WHERE a=0 ORDER BY a, b, c; -} {~/B-TREE/} +} {/B-TREE/} + + do_execsql_test 2.2 { EXPLAIN QUERY PLAN SELECT * FROM t1 WHERE +a=0 ORDER BY a, b, c; } {/B-TREE/} do_execsql_test 2.3 { ADDED test/orderby6.test Index: test/orderby6.test ================================================================== --- test/orderby6.test +++ test/orderby6.test @@ -0,0 +1,183 @@ +# 2014-03-21 +# +# The author disclaims copyright to this source code. In place of +# a legal notice, here is a blessing: +# +# May you do good and not evil. +# May you find forgiveness for yourself and forgive others. +# May you share freely, never taking more than you give. +# +#*********************************************************************** +# This file implements regression tests for SQLite library. The +# focus of this file is testing that the block-sort optimization. +# + + +set testdir [file dirname $argv0] +source $testdir/tester.tcl +set ::testprefix orderby6 + +# Run all tests twice. Once with a normal table and a second time +# with a WITHOUT ROWID table +# +foreach {tn rowidclause} {1 {} 2 {WITHOUT ROWID}} { + + # Construct a table with 1000 rows and a split primary key + # + reset_db + do_test $tn.1 { + db eval "CREATE TABLE t1(a,b,c,PRIMARY KEY(b,c)) $rowidclause;" + db eval { + WITH RECURSIVE + cnt(x) AS (VALUES(1) UNION ALL SELECT x+1 FROM cnt WHERE x<1000) + INSERT INTO t1 SELECT x, x%40, x/40 FROM cnt; + } + } {} + + # Run various ORDER BY queries that can benefit from block-sort. + # Compare the output to the same output using a full-sort enforced + # by adding + to each term of the ORDER BY clause. + # + do_execsql_test $tn.2 { + SELECT b,a,c FROM t1 ORDER BY b,a,c; + } [db eval {SELECT b,a,c FROM t1 ORDER BY +b,+a,+c}] + do_execsql_test $tn.3 { + SELECT b,a,c FROM t1 ORDER BY b,c DESC,a; + } [db eval {SELECT b,a,c FROM t1 ORDER BY +b,+c DESC,+a}] + do_execsql_test $tn.4 { + SELECT b,a,c FROM t1 ORDER BY b DESC,c,a; + } [db eval {SELECT b,a,c FROM t1 ORDER BY +b DESC,+c,+a}] + do_execsql_test $tn.5 { + SELECT b,a,c FROM t1 ORDER BY b DESC,a,c; + } [db eval {SELECT b,a,c FROM t1 ORDER BY +b DESC,+a,+c}] + + # LIMIT and OFFSET clauses on block-sort queries. + # + do_execsql_test $tn.11 { + SELECT a FROM t1 ORDER BY b, a LIMIT 10 OFFSET 20; + } {840 880 920 960 1000 1 41 81 121 161} + do_execsql_test $tn.11x { + SELECT a FROM t1 ORDER BY +b, a LIMIT 10 OFFSET 20; + } {840 880 920 960 1000 1 41 81 121 161} + + do_execsql_test $tn.12 { + SELECT a FROM t1 ORDER BY b DESC, a LIMIT 10 OFFSET 20; + } {839 879 919 959 999 38 78 118 158 198} + do_execsql_test $tn.12 { + SELECT a FROM t1 ORDER BY +b DESC, a LIMIT 10 OFFSET 20; + } {839 879 919 959 999 38 78 118 158 198} + + do_execsql_test $tn.13 { + SELECT a FROM t1 ORDER BY b, a DESC LIMIT 10 OFFSET 45; + } {161 121 81 41 1 962 922 882 842 802} + do_execsql_test $tn.13x { + SELECT a FROM t1 ORDER BY +b, a DESC LIMIT 10 OFFSET 45; + } {161 121 81 41 1 962 922 882 842 802} + + do_execsql_test $tn.14 { + SELECT a FROM t1 ORDER BY b DESC, a LIMIT 10 OFFSET 45; + } {838 878 918 958 998 37 77 117 157 197} + do_execsql_test $tn.14x { + SELECT a FROM t1 ORDER BY +b DESC, a LIMIT 10 OFFSET 45; + } {838 878 918 958 998 37 77 117 157 197} + + # Many test cases where the LIMIT+OFFSET window is in various + # alignments with block-sort boundaries. + # + foreach {tx limit offset orderby} { + 1 10 24 {+b,+a} + 2 10 25 {+b,+a} + 3 10 26 {+b,+a} + 4 10 39 {+b,+a} + 5 10 40 {+b,+a} + 6 10 41 {+b,+a} + 7 27 24 {+b,+a} + 8 27 49 {+b,+a} + 11 10 24 {+b DESC,+a} + 12 10 25 {+b DESC,+a} + 13 10 26 {+b DESC,+a} + 14 10 39 {+b DESC,+a} + 15 10 40 {+b DESC,+a} + 16 10 41 {+b DESC,+a} + 17 27 24 {+b DESC,+a} + 18 27 49 {+b DESC,+a} + 21 10 24 {+b,+a DESC} + 22 10 25 {+b,+a DESC} + 23 10 26 {+b,+a DESC} + 24 10 39 {+b,+a DESC} + 25 10 40 {+b,+a DESC} + 26 10 41 {+b,+a DESC} + 27 27 24 {+b,+a DESC} + 28 27 49 {+b,+a DESC} + 31 10 24 {+b DESC,+a DESC} + 32 10 25 {+b DESC,+a DESC} + 33 10 26 {+b DESC,+a DESC} + 34 10 39 {+b DESC,+a DESC} + 35 10 40 {+b DESC,+a DESC} + 36 10 41 {+b DESC,+a DESC} + 37 27 24 {+b DESC,+a DESC} + 38 27 49 {+b DESC,+a DESC} + } { + set sql1 "SELECT a FROM t1 ORDER BY $orderby LIMIT $limit OFFSET $offset;" + set sql2 [string map {+ {}} $sql1] + # puts $sql2\n$sql1\n[db eval $sql2] + do_test $tn.21.$tx {db eval $::sql2} [db eval $sql1] + } + + ######################################################################## + # A second test table, t2, has many columns open to sorting. + do_test $tn.31 { + db eval "CREATE TABLE t2(a,b,c,d,e,f,PRIMARY KEY(b,c,d,e,f)) $rowidclause;" + db eval { + WITH RECURSIVE + cnt(x) AS (VALUES(0) UNION ALL SELECT x+1 FROM cnt WHERE x<242) + INSERT INTO t2 SELECT x, x%3, (x/3)%3, (x/9)%3, (x/27)%3, (x/81)%3 + FROM cnt; + } + } {} + + do_execsql_test $tn.32 { + SELECT a FROM t2 ORDER BY b,c,d,e,f; + } [db eval {SELECT a FROM t2 ORDER BY +b,+c,+d,+e,+f;}] + do_execsql_test $tn.33 { + SELECT a FROM t2 ORDER BY b,c,d,e,+f; + } [db eval {SELECT a FROM t2 ORDER BY +b,+c,+d,+e,+f;}] + do_execsql_test $tn.34 { + SELECT a FROM t2 ORDER BY b,c,d,+e,+f; + } [db eval {SELECT a FROM t2 ORDER BY +b,+c,+d,+e,+f;}] + do_execsql_test $tn.35 { + SELECT a FROM t2 ORDER BY b,c,+d,+e,+f; + } [db eval {SELECT a FROM t2 ORDER BY +b,+c,+d,+e,+f;}] + do_execsql_test $tn.36 { + SELECT a FROM t2 ORDER BY b,+c,+d,+e,+f; + } [db eval {SELECT a FROM t2 ORDER BY +b,+c,+d,+e,+f;}] + + do_execsql_test $tn.37 { + SELECT a FROM t2 ORDER BY b,c,d,e,f DESC; + } [db eval {SELECT a FROM t2 ORDER BY +b,+c,+d,+e,+f DESC;}] + do_execsql_test $tn.38 { + SELECT a FROM t2 ORDER BY b,c,d,e DESC,f; + } [db eval {SELECT a FROM t2 ORDER BY +b,+c,+d,+e DESC,+f;}] + do_execsql_test $tn.39 { + SELECT a FROM t2 ORDER BY b,c,d DESC,e,f; + } [db eval {SELECT a FROM t2 ORDER BY +b,+c,+d DESC,+e,+f;}] + do_execsql_test $tn.40 { + SELECT a FROM t2 ORDER BY b,c DESC,d,e,f; + } [db eval {SELECT a FROM t2 ORDER BY +b,+c DESC,+d,+e,+f;}] + do_execsql_test $tn.41 { + SELECT a FROM t2 ORDER BY b DESC,c,d,e,f; + } [db eval {SELECT a FROM t2 ORDER BY +b DESC,+c,+d,+e,+f;}] + + do_execsql_test $tn.42 { + SELECT a FROM t2 ORDER BY b DESC,c DESC,d,e,f LIMIT 31; + } [db eval {SELECT a FROM t2 ORDER BY +b DESC,+c DESC,+d,+e,+f LIMIT 31}] + do_execsql_test $tn.43 { + SELECT a FROM t2 ORDER BY b,c,d,e,f DESC LIMIT 8 OFFSET 7; + } [db eval {SELECT a FROM t2 ORDER BY +b,+c,+d,+e,+f DESC LIMIT 8 OFFSET 7}] + + +} + + + +finish_test Index: test/syscall.test ================================================================== --- test/syscall.test +++ test/syscall.test @@ -59,10 +59,11 @@ foreach s { open close access getcwd stat fstat ftruncate fcntl read pread write pwrite fchmod fallocate pread64 pwrite64 unlink openDirectory mkdir rmdir statvfs fchown umask mmap munmap mremap + getpagesize } { if {[test_syscall exists $s]} {lappend syscall_list $s} } do_test 3.1 { lsort [test_syscall list] } [lsort $syscall_list] ADDED test/tkt-a8a0d2996a.test Index: test/tkt-a8a0d2996a.test ================================================================== --- test/tkt-a8a0d2996a.test +++ test/tkt-a8a0d2996a.test @@ -0,0 +1,93 @@ +# 2014-03-24 +# +# The author disclaims copyright to this source code. In place of +# a legal notice, here is a blessing: +# +# May you do good and not evil. +# May you find forgiveness for yourself and forgive others. +# May you share freely, never taking more than you give. +# +#*********************************************************************** +# +# Tests to verify that arithmetic operators do not change the type of +# input operands. Ticket [a8a0d2996a] +# + +set testdir [file dirname $argv0] +source $testdir/tester.tcl +set testprefix tkt-a8a0d2996a + +do_execsql_test 1.0 { + CREATE TABLE t(x,y); + INSERT INTO t VALUES('1','1'); + SELECT typeof(x), typeof(y) FROM t WHERE 1=x+0 AND y=='1'; +} {text text} +do_execsql_test 1.1 { + SELECT typeof(x), typeof(y) FROM t WHERE 1=x-0 AND y=='1'; +} {text text} +do_execsql_test 1.2 { + SELECT typeof(x), typeof(y) FROM t WHERE 1=x*1 AND y=='1'; +} {text text} +do_execsql_test 1.3 { + SELECT typeof(x), typeof(y) FROM t WHERE 1=x/1 AND y=='1'; +} {text text} +do_execsql_test 1.4 { + SELECT typeof(x), typeof(y) FROM t WHERE 1=x%4 AND y=='1'; +} {text text} + +do_execsql_test 2.0 { + UPDATE t SET x='1xyzzy'; + SELECT typeof(x), typeof(y) FROM t WHERE 1=x+0 AND y=='1'; +} {text text} +do_execsql_test 2.1 { + SELECT typeof(x), typeof(y) FROM t WHERE 1=x-0 AND y=='1'; +} {text text} +do_execsql_test 2.2 { + SELECT typeof(x), typeof(y) FROM t WHERE 1=x*1 AND y=='1'; +} {text text} +do_execsql_test 2.3 { + SELECT typeof(x), typeof(y) FROM t WHERE 1=x/1 AND y=='1'; +} {text text} +do_execsql_test 2.4 { + SELECT typeof(x), typeof(y) FROM t WHERE 1=x%4 AND y=='1'; +} {text text} + + +do_execsql_test 3.0 { + UPDATE t SET x='1.0'; + SELECT typeof(x), typeof(y) FROM t WHERE 1=x+0 AND y=='1'; +} {text text} +do_execsql_test 3.1 { + SELECT typeof(x), typeof(y) FROM t WHERE 1=x-0 AND y=='1'; +} {text text} +do_execsql_test 3.2 { + SELECT typeof(x), typeof(y) FROM t WHERE 1=x*1 AND y=='1'; +} {text text} +do_execsql_test 3.3 { + SELECT typeof(x), typeof(y) FROM t WHERE 1=x/1 AND y=='1'; +} {text text} +do_execsql_test 3.4 { + SELECT typeof(x), typeof(y) FROM t WHERE 1=x%4 AND y=='1'; +} {text text} + +do_execsql_test 4.0 { + SELECT 1+1.; +} {2.0} +do_execsql_test 4.1 { + SELECT '1.23e64'/'1.0000e+62'; +} {123.0} +do_execsql_test 4.2 { + SELECT '100x'+'-2y'; +} {98} +do_execsql_test 4.3 { + SELECT '100x'+'4.5y'; +} {104.5} +do_execsql_test 4.4 { + SELECT '-9223372036854775807x'-'1x'; +} {-9.22337203685478e+18} +do_execsql_test 4.5 { + SELECT '9223372036854775806x'+'1x'; +} {9.22337203685478e+18} +do_execsql_test 4.6 { + SELECT '1234x'/'10y'; +} {123.4} ADDED test/wal64k.test Index: test/wal64k.test ================================================================== --- test/wal64k.test +++ test/wal64k.test @@ -0,0 +1,47 @@ +# 2010 April 13 +# +# The author disclaims copyright to this source code. In place of +# a legal notice, here is a blessing: +# +# May you do good and not evil. +# May you find forgiveness for yourself and forgive others. +# May you share freely, never taking more than you give. +# +#*********************************************************************** +# This file implements regression tests for SQLite library. The +# focus of this file is testing the operation of the library in +# "PRAGMA journal_mode=WAL" mode. +# + +set testdir [file dirname $argv0] +source $testdir/tester.tcl +set testprefix wal64k + +ifcapable !wal {finish_test ; return } + +db close +test_syscall pagesize 65536 +sqlite3 db test.db + +do_execsql_test 1.0 { + PRAGMA journal_mode = WAL; + CREATE TABLE t1(x); + CREATE INDEX i1 ON t1(x); +} {wal} +do_test 1.1 { file size test.db-shm } {65536} + +do_test 1.2 { + execsql BEGIN + while {[file size test.db-shm]==65536} { + execsql { INSERT INTO t1 VALUES( randstr(900,1100) ) } + } + execsql COMMIT + file size test.db-shm +} {131072} + +integrity_check 1.3 + +db close +test_syscall pagesize -1 +finish_test + Index: test/whereG.test ================================================================== --- test/whereG.test +++ test/whereG.test @@ -93,11 +93,11 @@ SELECT DISTINCT aname FROM album, composer, track WHERE cname LIKE '%bach%' AND composer.cid=track.cid AND album.aid=track.aid; -} {/.*track.*composer.*album.*/} +} {/.*track.*(composer.*album|album.*composer).*/} do_execsql_test whereG-1.6 { SELECT DISTINCT aname FROM album, composer, track WHERE cname LIKE '%bach%' AND composer.cid=track.cid @@ -108,11 +108,11 @@ SELECT DISTINCT aname FROM album, composer, track WHERE cname LIKE '%bach%' AND unlikely(composer.cid=track.cid) AND unlikely(album.aid=track.aid); -} {/.*track.*composer.*album.*/} +} {/.*track.*(composer.*album|album.*composer).*/} do_execsql_test whereG-1.8 { SELECT DISTINCT aname FROM album, composer, track WHERE cname LIKE '%bach%' AND unlikely(composer.cid=track.cid) Index: test/with2.test ================================================================== --- test/with2.test +++ test/with2.test @@ -383,9 +383,36 @@ WITH ss(x) AS ( VALUES(7) UNION ALL SELECT x+7 FROM ss WHERE x<49 ) SELECT x FROM ss ) } {14 28 42} +#------------------------------------------------------------------------- +# At one point the following was causing an assertion failure and a +# memory leak. +# +do_execsql_test 8.1 { + CREATE TABLE t7(y); + INSERT INTO t7 VALUES(NULL); + CREATE VIEW v AS SELECT * FROM t7 ORDER BY y; +} + +do_execsql_test 8.2 { + WITH q(a) AS ( + SELECT 1 + UNION + SELECT a+1 FROM q, v WHERE a<5 + ) + SELECT * FROM q; +} {1 2 3 4 5} + +do_execsql_test 8.3 { + WITH q(a) AS ( + SELECT 1 + UNION ALL + SELECT a+1 FROM q, v WHERE a<5 + ) + SELECT * FROM q; +} {1 2 3 4 5} finish_test