Index: ext/fts5/fts5.c ================================================================== --- ext/fts5/fts5.c +++ ext/fts5/fts5.c @@ -154,14 +154,29 @@ ** Virtual-table cursor object. ** ** iSpecial: ** If this is a 'special' query (refer to function fts5SpecialMatch()), ** then this variable contains the result of the query. +** +** iFirstRowid, iLastRowid: +** These variables are only used for FTS5_PLAN_MATCH cursors. Assuming the +** cursor iterates in ascending order of rowids, iFirstRowid is the lower +** limit of rowids to return, and iLastRowid the upper. In other words, the +** WHERE clause in the user's query might have been: +** +** MATCH AND rowid BETWEEN $iFirstRowid AND $iLastRowid +** +** If the cursor iterates in descending order of rowid, iFirstRowid +** is the upper limit (i.e. the "first" rowid visited) and iLastRowid +** the lower. */ struct Fts5Cursor { sqlite3_vtab_cursor base; /* Base class used by SQLite core */ - int idxNum; /* idxNum passed to xFilter() */ + int ePlan; /* FTS5_PLAN_XXX value */ + int bDesc; /* True for "ORDER BY rowid DESC" queries */ + i64 iFirstRowid; /* Return no rowids earlier than this */ + i64 iLastRowid; /* Return no rowids later than this */ sqlite3_stmt *pStmt; /* Statement used to read %_content */ Fts5Expr *pExpr; /* Expression for MATCH queries */ Fts5Sorter *pSorter; /* Sorter for "ORDER BY rank" queries */ int csrflags; /* Mask of cursor flags (see below) */ Fts5Cursor *pNext; /* Next cursor in Fts5Cursor.pCsr list */ @@ -179,22 +194,49 @@ i64 iCsrId; /* Cursor id */ Fts5Auxiliary *pAux; /* Currently executing extension function */ Fts5Auxdata *pAuxdata; /* First in linked list of saved aux-data */ int *aColumnSize; /* Values for xColumnSize() */ + /* Cache used by auxiliary functions xInst() and xInstCount() */ int nInstCount; /* Number of phrase instances */ int *aInst; /* 3 integers per phrase instance */ }; +/* +** Bits that make up the "idxNum" parameter passed indirectly by +** xBestIndex() to xFilter(). +*/ +#define FTS5_BI_MATCH 0x0001 /* MATCH ? */ +#define FTS5_BI_RANK 0x0002 /* rank MATCH ? */ +#define FTS5_BI_ROWID_EQ 0x0004 /* rowid == ? */ +#define FTS5_BI_ROWID_LE 0x0008 /* rowid <= ? */ +#define FTS5_BI_ROWID_GE 0x0010 /* rowid >= ? */ + +#define FTS5_BI_ORDER_RANK 0x0020 +#define FTS5_BI_ORDER_ROWID 0x0040 +#define FTS5_BI_ORDER_DESC 0x0080 + /* ** Values for Fts5Cursor.csrflags */ #define FTS5CSR_REQUIRE_CONTENT 0x01 #define FTS5CSR_REQUIRE_DOCSIZE 0x02 #define FTS5CSR_EOF 0x04 #define FTS5CSR_FREE_ZRANK 0x08 #define FTS5CSR_REQUIRE_RESEEK 0x10 + +#define BitFlagAllTest(x,y) (((x) & (y))==(y)) +#define BitFlagTest(x,y) (((x) & (y))!=0) + +/* +** Constants for the largest and smallest possible 64-bit signed integers. +** These are copied from sqliteInt.h. +*/ +#ifndef SQLITE_AMALGAMATION +# define LARGEST_INT64 (0xffffffff|(((i64)0x7fffffff)<<32)) +# define SMALLEST_INT64 (((i64)-1) - LARGEST_INT64) +#endif /* ** Macros to Set(), Clear() and Test() cursor flags. */ #define CsrFlagSet(pCsr, flag) ((pCsr)->csrflags |= (flag)) @@ -392,98 +434,144 @@ ){ return fts5InitVtab(1, db, pAux, argc, argv, ppVtab, pzErr); } /* -** The three query plans xBestIndex may choose between. +** The different query plans. */ #define FTS5_PLAN_SCAN 1 /* No usable constraint */ #define FTS5_PLAN_MATCH 2 /* ( MATCH ?) */ #define FTS5_PLAN_SORTED_MATCH 3 /* ( MATCH ? ORDER BY rank) */ #define FTS5_PLAN_ROWID 4 /* (rowid = ?) */ #define FTS5_PLAN_SOURCE 5 /* A source cursor for SORTED_MATCH */ #define FTS5_PLAN_SPECIAL 6 /* An internal query */ -#define FTS5_PLAN(idxNum) ((idxNum) & 0x7) - -#define FTS5_ORDER_DESC 8 /* ORDER BY rowid DESC */ -#define FTS5_ORDER_ASC 16 /* ORDER BY rowid ASC */ - -/* -** Search the object passed as the first argument for a usable constraint -** on column iCol using operator eOp. If one is found, return its index in -** the pInfo->aConstraint[] array. If no such constraint is found, return -** a negative value. -*/ -static int fts5FindConstraint(sqlite3_index_info *pInfo, int eOp, int iCol){ - int i; - for(i=0; inConstraint; i++){ - struct sqlite3_index_constraint *p = &pInfo->aConstraint[i]; - if( p->usable && p->iColumn==iCol && p->op==eOp ) return i; - } - return -1; -} - -/* -** Implementation of the xBestIndex method for FTS5 tables. There -** are three possible strategies, in order of preference: -** -** 1. Full-text search using a MATCH operator. -** 2. A by-rowid lookup. -** 3. A full-table scan. +/* +** Implementation of the xBestIndex method for FTS5 tables. Within the +** WHERE constraint, it searches for the following: +** +** 1. A MATCH constraint against the special column. +** 2. A MATCH constraint against the "rank" column. +** 3. An == constraint against the rowid column. +** 4. A < or <= constraint against the rowid column. +** 5. A > or >= constraint against the rowid column. +** +** Within the ORDER BY, either: +** +** 5. ORDER BY rank [ASC|DESC] +** 6. ORDER BY rowid [ASC|DESC] +** +** Costs are assigned as follows: +** +** a) If an unusable MATCH operator is present in the WHERE clause, the +** cost is unconditionally set to 1e50 (a really big number). +** +** a) If a MATCH operator is present, the cost depends on the other +** constraints also present. As follows: +** +** * No other constraints: cost=1000.0 +** * One rowid range constraint: cost=750.0 +** * Both rowid range constraints: cost=500.0 +** * An == rowid constraint: cost=100.0 +** +** b) Otherwise, if there is no MATCH: +** +** * No other constraints: cost=1000000.0 +** * One rowid range constraint: cost=750000.0 +** * Both rowid range constraints: cost=250000.0 +** * An == rowid constraint: cost=10.0 +** +** Costs are not modified by the ORDER BY clause. */ static int fts5BestIndexMethod(sqlite3_vtab *pVTab, sqlite3_index_info *pInfo){ Fts5Table *pTab = (Fts5Table*)pVTab; Fts5Config *pConfig = pTab->pConfig; - int iCons; - int ePlan = FTS5_PLAN_SCAN; - int iRankMatch; - - iCons = fts5FindConstraint(pInfo,SQLITE_INDEX_CONSTRAINT_MATCH,pConfig->nCol); - if( iCons>=0 ){ - ePlan = FTS5_PLAN_MATCH; - pInfo->estimatedCost = 1.0; - }else{ - iCons = fts5FindConstraint(pInfo, SQLITE_INDEX_CONSTRAINT_EQ, -1); - if( iCons>=0 ){ - ePlan = FTS5_PLAN_ROWID; - pInfo->estimatedCost = 2.0; - } - } - - if( iCons>=0 ){ - pInfo->aConstraintUsage[iCons].argvIndex = 1; - pInfo->aConstraintUsage[iCons].omit = 1; - }else{ - pInfo->estimatedCost = 10000000.0; - } - + int idxFlags = 0; /* Parameter passed through to xFilter() */ + int bHasMatch; + int iNext; + int i; + + struct Constraint { + int op; /* Mask against sqlite3_index_constraint.op */ + int fts5op; /* FTS5 mask for idxFlags */ + int iCol; /* 0==rowid, 1==tbl, 2==rank */ + int omit; /* True to omit this if found */ + int iConsIndex; /* Index in pInfo->aConstraint[] */ + } aConstraint[] = { + {SQLITE_INDEX_CONSTRAINT_MATCH, FTS5_BI_MATCH, 1, 1, -1}, + {SQLITE_INDEX_CONSTRAINT_MATCH, FTS5_BI_RANK, 2, 1, -1}, + {SQLITE_INDEX_CONSTRAINT_EQ, FTS5_BI_ROWID_EQ, 0, 0, -1}, + {SQLITE_INDEX_CONSTRAINT_LT|SQLITE_INDEX_CONSTRAINT_LE, + FTS5_BI_ROWID_LE, 0, 0, -1}, + {SQLITE_INDEX_CONSTRAINT_GT|SQLITE_INDEX_CONSTRAINT_GE, + FTS5_BI_ROWID_GE, 0, 0, -1}, + }; + + int aColMap[3]; + aColMap[0] = -1; + aColMap[1] = pConfig->nCol; + aColMap[2] = pConfig->nCol+1; + + /* Set idxFlags flags for all WHERE clause terms that will be used. */ + for(i=0; inConstraint; i++){ + struct sqlite3_index_constraint *p = &pInfo->aConstraint[i]; + int j; + for(j=0; jiColumn==aColMap[pC->iCol] && p->op & pC->op ){ + if( p->usable ){ + pC->iConsIndex = i; + idxFlags |= pC->fts5op; + }else if( j==0 ){ + /* As there exists an unusable MATCH constraint this is an + ** unusable plan. Set a prohibitively high cost. */ + pInfo->estimatedCost = 1e50; + return SQLITE_OK; + } + } + } + } + + /* Set idxFlags flags for the ORDER BY clause */ if( pInfo->nOrderBy==1 ){ int iSort = pInfo->aOrderBy[0].iColumn; - if( iSort<0 ){ - /* ORDER BY rowid [ASC|DESC] */ - pInfo->orderByConsumed = 1; - }else if( iSort==(pConfig->nCol+1) && ePlan==FTS5_PLAN_MATCH ){ - /* ORDER BY rank [ASC|DESC] */ + if( iSort==(pConfig->nCol+1) && BitFlagTest(idxFlags, FTS5_BI_MATCH) ){ + idxFlags |= FTS5_BI_ORDER_RANK; + }else if( iSort==-1 ){ + idxFlags |= FTS5_BI_ORDER_ROWID; + } + if( BitFlagTest(idxFlags, FTS5_BI_ORDER_RANK|FTS5_BI_ORDER_ROWID) ){ pInfo->orderByConsumed = 1; - ePlan = FTS5_PLAN_SORTED_MATCH; - } - - if( pInfo->orderByConsumed ){ - ePlan |= pInfo->aOrderBy[0].desc ? FTS5_ORDER_DESC : FTS5_ORDER_ASC; - } - } - - iRankMatch = fts5FindConstraint( - pInfo, SQLITE_INDEX_CONSTRAINT_MATCH, pConfig->nCol+1 - ); - if( iRankMatch>=0 ){ - pInfo->aConstraintUsage[iRankMatch].argvIndex = 1 + (iCons>=0); - pInfo->aConstraintUsage[iRankMatch].omit = 1; - } - - pInfo->idxNum = ePlan; + if( pInfo->aOrderBy[0].desc ){ + idxFlags |= FTS5_BI_ORDER_DESC; + } + } + } + + /* Calculate the estimated cost based on the flags set in idxFlags. */ + bHasMatch = BitFlagTest(idxFlags, FTS5_BI_MATCH); + if( BitFlagTest(idxFlags, FTS5_BI_ROWID_EQ) ){ + pInfo->estimatedCost = bHasMatch ? 100.0 : 10.0; + }else if( BitFlagAllTest(idxFlags, FTS5_BI_ROWID_LE|FTS5_BI_ROWID_GE) ){ + pInfo->estimatedCost = bHasMatch ? 500.0 : 250000.0; + }else if( BitFlagTest(idxFlags, FTS5_BI_ROWID_LE|FTS5_BI_ROWID_GE) ){ + pInfo->estimatedCost = bHasMatch ? 750.0 : 750000.0; + }else{ + pInfo->estimatedCost = bHasMatch ? 1000.0 : 1000000.0; + } + + /* Assign argvIndex values to each constraint in use. */ + iNext = 1; + for(i=0; iiConsIndex>=0 ){ + pInfo->aConstraintUsage[pC->iConsIndex].argvIndex = iNext++; + pInfo->aConstraintUsage[pC->iConsIndex].omit = pC->omit; + } + } + + pInfo->idxNum = idxFlags; return SQLITE_OK; } /* ** Implementation of xOpen method. @@ -509,13 +597,13 @@ } *ppCsr = (sqlite3_vtab_cursor*)pCsr; return rc; } -static int fts5StmtType(int idxNum){ - if( FTS5_PLAN(idxNum)==FTS5_PLAN_SCAN ){ - return (idxNum&FTS5_ORDER_DESC) ? FTS5_STMT_SCAN_DESC : FTS5_STMT_SCAN_ASC; +static int fts5StmtType(Fts5Cursor *pCsr){ + if( pCsr->ePlan==FTS5_PLAN_SCAN ){ + return (pCsr->bDesc) ? FTS5_STMT_SCAN_DESC : FTS5_STMT_SCAN_ASC; } return FTS5_STMT_LOOKUP; } /* @@ -542,20 +630,20 @@ Fts5Auxdata *pData; Fts5Auxdata *pNext; fts5CsrNewrow(pCsr); if( pCsr->pStmt ){ - int eStmt = fts5StmtType(pCsr->idxNum); + int eStmt = fts5StmtType(pCsr); sqlite3Fts5StorageStmtRelease(pTab->pStorage, eStmt, pCsr->pStmt); } if( pCsr->pSorter ){ Fts5Sorter *pSorter = pCsr->pSorter; sqlite3_finalize(pSorter->pStmt); sqlite3_free(pSorter); } - if( pCsr->idxNum!=FTS5_PLAN_SOURCE ){ + if( pCsr->ePlan!=FTS5_PLAN_SOURCE ){ sqlite3Fts5ExprFree(pCsr->pExpr); } for(pData=pCsr->pAuxdata; pData; pData=pNext){ pNext = pData->pNext; @@ -620,11 +708,11 @@ ** open on table pTab. */ static void fts5TripCursors(Fts5Table *pTab){ Fts5Cursor *pCsr; for(pCsr=pTab->pGlobal->pCsr; pCsr; pCsr=pCsr->pNext){ - if( FTS5_PLAN(pCsr->idxNum)==FTS5_PLAN_MATCH + if( pCsr->ePlan==FTS5_PLAN_MATCH && pCsr->base.pVtab==(sqlite3_vtab*)pTab ){ CsrFlagSet(pCsr, FTS5CSR_REQUIRE_RESEEK); } } @@ -645,22 +733,16 @@ static int fts5CursorReseek(Fts5Cursor *pCsr, int *pbSkip){ int rc = SQLITE_OK; assert( *pbSkip==0 ); if( CsrFlagTest(pCsr, FTS5CSR_REQUIRE_RESEEK) ){ Fts5Table *pTab = (Fts5Table*)(pCsr->base.pVtab); - int bDesc = ((pCsr->idxNum & FTS5_ORDER_DESC) ? 1 : 0); + int bDesc = pCsr->bDesc; i64 iRowid = sqlite3Fts5ExprRowid(pCsr->pExpr); - rc = sqlite3Fts5ExprFirst(pCsr->pExpr, pTab->pIndex, bDesc); - while( rc==SQLITE_OK && sqlite3Fts5ExprEof(pCsr->pExpr)==0 ){ - i64 ii = sqlite3Fts5ExprRowid(pCsr->pExpr); - if( ii==iRowid ) break; - if( (bDesc && iiiRowid) ){ - *pbSkip = 1; - break; - } - rc = sqlite3Fts5ExprNext(pCsr->pExpr); + rc = sqlite3Fts5ExprFirst(pCsr->pExpr, pTab->pIndex, iRowid, bDesc); + if( rc==SQLITE_OK && iRowid!=sqlite3Fts5ExprRowid(pCsr->pExpr) ){ + *pbSkip = 1; } CsrFlagClear(pCsr, FTS5CSR_REQUIRE_RESEEK); fts5CsrNewrow(pCsr); if( sqlite3Fts5ExprEof(pCsr->pExpr) ){ @@ -679,20 +761,20 @@ ** even if we reach end-of-file. The fts5EofMethod() will be called ** subsequently to determine whether or not an EOF was hit. */ static int fts5NextMethod(sqlite3_vtab_cursor *pCursor){ Fts5Cursor *pCsr = (Fts5Cursor*)pCursor; - int ePlan = FTS5_PLAN(pCsr->idxNum); + int ePlan = pCsr->ePlan; int bSkip = 0; int rc; if( (rc = fts5CursorReseek(pCsr, &bSkip)) || bSkip ) return rc; switch( ePlan ){ case FTS5_PLAN_MATCH: case FTS5_PLAN_SOURCE: - rc = sqlite3Fts5ExprNext(pCsr->pExpr); + rc = sqlite3Fts5ExprNext(pCsr->pExpr, pCsr->iLastRowid); if( sqlite3Fts5ExprEof(pCsr->pExpr) ){ CsrFlagSet(pCsr, FTS5CSR_EOF); } fts5CsrNewrow(pCsr); break; @@ -775,12 +857,13 @@ return rc; } static int fts5CursorFirst(Fts5Table *pTab, Fts5Cursor *pCsr, int bDesc){ int rc; - rc = sqlite3Fts5ExprFirst(pCsr->pExpr, pTab->pIndex, bDesc); - if( sqlite3Fts5ExprEof(pCsr->pExpr) ){ + Fts5Expr *pExpr = pCsr->pExpr; + rc = sqlite3Fts5ExprFirst(pExpr, pTab->pIndex, pCsr->iFirstRowid, bDesc); + if( sqlite3Fts5ExprEof(pExpr) ){ CsrFlagSet(pCsr, FTS5CSR_EOF); } fts5CsrNewrow(pCsr); return rc; } @@ -802,11 +885,11 @@ while( z[0]==' ' ) z++; for(n=0; z[n] && z[n]!=' '; n++); assert( pTab->base.zErrMsg==0 ); - pCsr->idxNum = FTS5_PLAN_SPECIAL; + pCsr->ePlan = FTS5_PLAN_SPECIAL; if( 0==sqlite3_strnicmp("reads", z, n) ){ pCsr->iSpecial = sqlite3Fts5IndexReads(pTab->pIndex); } else if( 0==sqlite3_strnicmp("id", z, n) ){ @@ -924,10 +1007,20 @@ pCsr->zRankArgs = 0; } } return rc; } + +static i64 fts5GetRowidLimit(sqlite3_value *pVal, i64 iDefault){ + if( pVal ){ + int eType = sqlite3_value_numeric_type(pVal); + if( eType==SQLITE_INTEGER ){ + return sqlite3_value_int64(pVal); + } + } + return iDefault; +} /* ** This is the xFilter interface for the virtual table. See ** the virtual table xFilter method documentation for additional ** information. @@ -945,74 +1038,110 @@ int nVal, /* Number of elements in apVal */ sqlite3_value **apVal /* Arguments for the indexing scheme */ ){ Fts5Table *pTab = (Fts5Table*)(pCursor->pVtab); Fts5Cursor *pCsr = (Fts5Cursor*)pCursor; - int bDesc = ((idxNum & FTS5_ORDER_DESC) ? 1 : 0); - int rc = SQLITE_OK; + int rc = SQLITE_OK; /* Error code */ + int iVal = 0; /* Counter for apVal[] */ + int bDesc; /* True if ORDER BY [rank|rowid] DESC */ + int bOrderByRank; /* True if ORDER BY rank */ + sqlite3_value *pMatch = 0; /* MATCH ? expression (or NULL) */ + sqlite3_value *pRank = 0; /* rank MATCH ? expression (or NULL) */ + sqlite3_value *pRowidEq = 0; /* rowid = ? expression (or NULL) */ + sqlite3_value *pRowidLe = 0; /* rowid <= ? expression (or NULL) */ + sqlite3_value *pRowidGe = 0; /* rowid >= ? expression (or NULL) */ char **pzErrmsg = pTab->pConfig->pzErrmsg; - assert( pzErrmsg==0 || pzErrmsg==&pTab->base.zErrMsg ); - pTab->pConfig->pzErrmsg = &pTab->base.zErrMsg; - - assert( nVal<=2 ); assert( pCsr->pStmt==0 ); assert( pCsr->pExpr==0 ); assert( pCsr->csrflags==0 ); assert( pCsr->pRank==0 ); assert( pCsr->zRank==0 ); assert( pCsr->zRankArgs==0 ); + + assert( pzErrmsg==0 || pzErrmsg==&pTab->base.zErrMsg ); + pTab->pConfig->pzErrmsg = &pTab->base.zErrMsg; + + /* Decode the arguments passed through to this function. + ** + ** Note: The following set of if(...) statements must be in the same + ** order as the corresponding entries in the struct at the top of + ** fts5BestIndexMethod(). */ + if( BitFlagTest(idxNum, FTS5_BI_MATCH) ) pMatch = apVal[iVal++]; + if( BitFlagTest(idxNum, FTS5_BI_RANK) ) pRank = apVal[iVal++]; + if( BitFlagTest(idxNum, FTS5_BI_ROWID_EQ) ) pRowidEq = apVal[iVal++]; + if( BitFlagTest(idxNum, FTS5_BI_ROWID_LE) ) pRowidLe = apVal[iVal++]; + if( BitFlagTest(idxNum, FTS5_BI_ROWID_GE) ) pRowidGe = apVal[iVal++]; + assert( iVal==nVal ); + bOrderByRank = ((idxNum & FTS5_BI_ORDER_RANK) ? 1 : 0); + pCsr->bDesc = bDesc = ((idxNum & FTS5_BI_ORDER_DESC) ? 1 : 0); + + /* Set the cursor upper and lower rowid limits. Only some strategies + ** actually use them. This is ok, as the xBestIndex() method leaves the + ** sqlite3_index_constraint.omit flag clear for range constraints + ** on the rowid field. */ + if( pRowidEq ){ + pRowidLe = pRowidGe = pRowidEq; + } + if( bDesc ){ + pCsr->iFirstRowid = fts5GetRowidLimit(pRowidLe, LARGEST_INT64); + pCsr->iLastRowid = fts5GetRowidLimit(pRowidGe, SMALLEST_INT64); + }else{ + pCsr->iLastRowid = fts5GetRowidLimit(pRowidLe, LARGEST_INT64); + pCsr->iFirstRowid = fts5GetRowidLimit(pRowidGe, SMALLEST_INT64); + } if( pTab->pSortCsr ){ /* If pSortCsr is non-NULL, then this call is being made as part of ** processing for a "... MATCH ORDER BY rank" query (ePlan is ** set to FTS5_PLAN_SORTED_MATCH). pSortCsr is the cursor that will ** return results to the user for this query. The current cursor ** (pCursor) is used to execute the query issued by function ** fts5CursorFirstSorted() above. */ - assert( FTS5_PLAN(idxNum)==FTS5_PLAN_SCAN ); - pCsr->idxNum = FTS5_PLAN_SOURCE; + assert( pRowidEq==0 && pRowidLe==0 && pRowidGe==0 && pRank==0 ); + assert( nVal==0 && pMatch==0 && bOrderByRank==0 && bDesc==0 ); + assert( pCsr->iLastRowid==LARGEST_INT64 ); + assert( pCsr->iFirstRowid==SMALLEST_INT64 ); + pCsr->ePlan = FTS5_PLAN_SOURCE; pCsr->pExpr = pTab->pSortCsr->pExpr; rc = fts5CursorFirst(pTab, pCsr, bDesc); - }else{ - int ePlan = FTS5_PLAN(idxNum); - pCsr->idxNum = idxNum; - if( ePlan==FTS5_PLAN_MATCH || ePlan==FTS5_PLAN_SORTED_MATCH ){ - const char *zExpr = (const char*)sqlite3_value_text(apVal[0]); - - rc = fts5CursorParseRank(pTab->pConfig, pCsr, (nVal==2 ? apVal[1] : 0)); - if( rc==SQLITE_OK ){ - if( zExpr[0]=='*' ){ - /* The user has issued a query of the form "MATCH '*...'". This - ** indicates that the MATCH expression is not a full text query, - ** but a request for an internal parameter. */ - rc = fts5SpecialMatch(pTab, pCsr, &zExpr[1]); - }else{ - char **pzErr = &pTab->base.zErrMsg; - rc = sqlite3Fts5ExprNew(pTab->pConfig, zExpr, &pCsr->pExpr, pzErr); - if( rc==SQLITE_OK ){ - if( ePlan==FTS5_PLAN_MATCH ){ - rc = fts5CursorFirst(pTab, pCsr, bDesc); - }else{ - rc = fts5CursorFirstSorted(pTab, pCsr, bDesc); - } + }else if( pMatch ){ + const char *zExpr = (const char*)sqlite3_value_text(apVal[0]); + + rc = fts5CursorParseRank(pTab->pConfig, pCsr, pRank); + if( rc==SQLITE_OK ){ + if( zExpr[0]=='*' ){ + /* The user has issued a query of the form "MATCH '*...'". This + ** indicates that the MATCH expression is not a full text query, + ** but a request for an internal parameter. */ + rc = fts5SpecialMatch(pTab, pCsr, &zExpr[1]); + }else{ + char **pzErr = &pTab->base.zErrMsg; + rc = sqlite3Fts5ExprNew(pTab->pConfig, zExpr, &pCsr->pExpr, pzErr); + if( rc==SQLITE_OK ){ + if( bOrderByRank ){ + pCsr->ePlan = FTS5_PLAN_SORTED_MATCH; + rc = fts5CursorFirstSorted(pTab, pCsr, bDesc); + }else{ + pCsr->ePlan = FTS5_PLAN_MATCH; + rc = fts5CursorFirst(pTab, pCsr, bDesc); } } } - }else{ - /* This is either a full-table scan (ePlan==FTS5_PLAN_SCAN) or a lookup - ** by rowid (ePlan==FTS5_PLAN_ROWID). */ - int eStmt = fts5StmtType(idxNum); - rc = sqlite3Fts5StorageStmt( - pTab->pStorage, eStmt, &pCsr->pStmt, &pTab->base.zErrMsg - ); - if( rc==SQLITE_OK ){ - if( ePlan==FTS5_PLAN_ROWID ){ - sqlite3_bind_value(pCsr->pStmt, 1, apVal[0]); - } - rc = fts5NextMethod(pCursor); + } + }else{ + /* This is either a full-table scan (ePlan==FTS5_PLAN_SCAN) or a lookup + ** by rowid (ePlan==FTS5_PLAN_ROWID). */ + pCsr->ePlan = (pRowidEq ? FTS5_PLAN_ROWID : FTS5_PLAN_SCAN); + rc = sqlite3Fts5StorageStmt( + pTab->pStorage, fts5StmtType(pCsr), &pCsr->pStmt, &pTab->base.zErrMsg + ); + if( rc==SQLITE_OK ){ + if( pCsr->ePlan==FTS5_PLAN_ROWID ){ + sqlite3_bind_value(pCsr->pStmt, 1, apVal[0]); } + rc = fts5NextMethod(pCursor); } } pTab->pConfig->pzErrmsg = pzErrmsg; return rc; @@ -1029,13 +1158,13 @@ /* ** Return the rowid that the cursor currently points to. */ static i64 fts5CursorRowid(Fts5Cursor *pCsr){ - assert( FTS5_PLAN(pCsr->idxNum)==FTS5_PLAN_MATCH - || FTS5_PLAN(pCsr->idxNum)==FTS5_PLAN_SORTED_MATCH - || FTS5_PLAN(pCsr->idxNum)==FTS5_PLAN_SOURCE + assert( pCsr->ePlan==FTS5_PLAN_MATCH + || pCsr->ePlan==FTS5_PLAN_SORTED_MATCH + || pCsr->ePlan==FTS5_PLAN_SOURCE ); if( pCsr->pSorter ){ return pCsr->pSorter->iRowid; }else{ return sqlite3Fts5ExprRowid(pCsr->pExpr); @@ -1048,11 +1177,11 @@ ** exposes %_content.docid as the rowid for the virtual table. The ** rowid should be written to *pRowid. */ static int fts5RowidMethod(sqlite3_vtab_cursor *pCursor, sqlite_int64 *pRowid){ Fts5Cursor *pCsr = (Fts5Cursor*)pCursor; - int ePlan = FTS5_PLAN(pCsr->idxNum); + int ePlan = pCsr->ePlan; assert( CsrFlagTest(pCsr, FTS5CSR_EOF)==0 ); switch( ePlan ){ case FTS5_PLAN_SPECIAL: *pRowid = 0; @@ -1080,11 +1209,11 @@ int rc = SQLITE_OK; /* If the cursor does not yet have a statement handle, obtain one now. */ if( pCsr->pStmt==0 ){ Fts5Table *pTab = (Fts5Table*)(pCsr->base.pVtab); - int eStmt = fts5StmtType(pCsr->idxNum); + int eStmt = fts5StmtType(pCsr); rc = sqlite3Fts5StorageStmt( pTab->pStorage, eStmt, &pCsr->pStmt, &pTab->base.zErrMsg ); assert( CsrFlagTest(pCsr, FTS5CSR_REQUIRE_CONTENT) ); } @@ -1611,11 +1740,13 @@ Fts5Cursor *pNew = 0; rc = fts5OpenMethod(pCsr->base.pVtab, (sqlite3_vtab_cursor**)&pNew); if( rc==SQLITE_OK ){ Fts5Config *pConf = pTab->pConfig; - pNew->idxNum = FTS5_PLAN_MATCH; + pNew->ePlan = FTS5_PLAN_MATCH; + pNew->iFirstRowid = SMALLEST_INT64; + pNew->iLastRowid = LARGEST_INT64; pNew->base.pVtab = (sqlite3_vtab*)pTab; rc = sqlite3Fts5ExprPhraseExpr(pConf, pCsr->pExpr, iPhrase, &pNew->pExpr); } if( rc==SQLITE_OK ){ @@ -1759,11 +1890,11 @@ Fts5Cursor *pCsr = (Fts5Cursor*)pCursor; int rc = SQLITE_OK; assert( CsrFlagTest(pCsr, FTS5CSR_EOF)==0 ); - if( pCsr->idxNum==FTS5_PLAN_SPECIAL ){ + if( pCsr->ePlan==FTS5_PLAN_SPECIAL ){ if( iCol==pConfig->nCol ){ sqlite3_result_int64(pCtx, pCsr->iSpecial); } }else @@ -1774,15 +1905,15 @@ ** auxiliary function. */ sqlite3_result_int64(pCtx, pCsr->iCsrId); }else if( iCol==pConfig->nCol+1 ){ /* The value of the "rank" column. */ - if( FTS5_PLAN(pCsr->idxNum)==FTS5_PLAN_SOURCE ){ + if( pCsr->ePlan==FTS5_PLAN_SOURCE ){ fts5PoslistBlob(pCtx, pCsr); }else if( - FTS5_PLAN(pCsr->idxNum)==FTS5_PLAN_MATCH - || FTS5_PLAN(pCsr->idxNum)==FTS5_PLAN_SORTED_MATCH + pCsr->ePlan==FTS5_PLAN_MATCH + || pCsr->ePlan==FTS5_PLAN_SORTED_MATCH ){ if( pCsr->pRank || SQLITE_OK==(rc = fts5FindRankFunction(pCsr)) ){ fts5ApiInvoke(pCsr->pRank, pCsr, pCtx, pCsr->nRankArg, pCsr->apRankArg); } } Index: ext/fts5/fts5Int.h ================================================================== --- ext/fts5/fts5Int.h +++ ext/fts5/fts5Int.h @@ -564,12 +564,12 @@ ** ){ ** // The document with rowid iRowid matches the expression! ** i64 iRowid = sqlite3Fts5ExprRowid(pExpr); ** } */ -int sqlite3Fts5ExprFirst(Fts5Expr*, Fts5Index *pIdx, int bDesc); -int sqlite3Fts5ExprNext(Fts5Expr*); +int sqlite3Fts5ExprFirst(Fts5Expr*, Fts5Index *pIdx, i64 iMin, int bDesc); +int sqlite3Fts5ExprNext(Fts5Expr*, i64 iMax); int sqlite3Fts5ExprEof(Fts5Expr*); i64 sqlite3Fts5ExprRowid(Fts5Expr*); void sqlite3Fts5ExprFree(Fts5Expr*); Index: ext/fts5/fts5_expr.c ================================================================== --- ext/fts5/fts5_expr.c +++ ext/fts5/fts5_expr.c @@ -1191,25 +1191,38 @@ } /* ** Begin iterating through the set of documents in index pIdx matched by -** the MATCH expression passed as the first argument. If the "bDesc" parameter -** is passed a non-zero value, iteration is in descending rowid order. Or, -** if it is zero, in ascending order. +** the MATCH expression passed as the first argument. If the "bDesc" +** parameter is passed a non-zero value, iteration is in descending rowid +** order. Or, if it is zero, in ascending order. +** +** If iterating in ascending rowid order (bDesc==0), the first document +** visited is that with the smallest rowid that is larger than or equal +** to parameter iFirst. Or, if iterating in ascending order (bDesc==1), +** then the first document visited must have a rowid smaller than or +** equal to iFirst. ** ** Return SQLITE_OK if successful, or an SQLite error code otherwise. It ** is not considered an error if the query does not match any documents. */ -int sqlite3Fts5ExprFirst(Fts5Expr *p, Fts5Index *pIdx, int bDesc){ +int sqlite3Fts5ExprFirst(Fts5Expr *p, Fts5Index *pIdx, i64 iFirst, int bDesc){ Fts5ExprNode *pRoot = p->pRoot; int rc = SQLITE_OK; if( pRoot ){ p->pIndex = pIdx; p->bDesc = bDesc; rc = fts5ExprNodeFirst(p, pRoot); + /* If not at EOF but the current rowid occurs earlier than iFirst in + ** the iteration order, move to document iFirst or later. */ + if( pRoot->bEof==0 && fts5RowidCmp(p, pRoot->iRowid, iFirst)<0 ){ + rc = fts5ExprNodeNext(p, pRoot, 1, iFirst); + } + + /* If the iterator is not at a real match, skip forward until it is. */ while( pRoot->bNomatch && rc==SQLITE_OK && pRoot->bEof==0 ){ rc = fts5ExprNodeNext(p, pRoot, 0, 0); } } return rc; @@ -1219,16 +1232,19 @@ ** Move to the next document ** ** Return SQLITE_OK if successful, or an SQLite error code otherwise. It ** is not considered an error if the query does not match any documents. */ -int sqlite3Fts5ExprNext(Fts5Expr *p){ +int sqlite3Fts5ExprNext(Fts5Expr *p, i64 iLast){ int rc; Fts5ExprNode *pRoot = p->pRoot; do { rc = fts5ExprNodeNext(p, pRoot, 0, 0); }while( pRoot->bNomatch && pRoot->bEof==0 && rc==SQLITE_OK ); + if( fts5RowidCmp(p, pRoot->iRowid, iLast)>0 ){ + pRoot->bEof = 1; + } return rc; } int sqlite3Fts5ExprEof(Fts5Expr *p){ return (p->pRoot==0 || p->pRoot->bEof); Index: ext/fts5/test/fts5ah.test ================================================================== --- ext/fts5/test/fts5ah.test +++ ext/fts5/test/fts5ah.test @@ -101,10 +101,50 @@ } {1} do_execsql_test 1.6.$tn.3 $q [lsort -int -incr $res] do_execsql_test 1.6.$tn.4 "$q ORDER BY rowid DESC" [lsort -int -decr $res] } + +#------------------------------------------------------------------------- +# Now test that adding range constraints on the rowid field reduces the +# number of pages loaded from disk. +# +foreach {tn fraction tail cnt} { + 1 0.6 {rowid > 5000} 5000 + 2 0.2 {rowid > 9000} 1000 + 3 0.2 {rowid < 1000} 999 + 4 0.2 {rowid BETWEEN 4000 AND 5000} 1001 + 5 0.6 {rowid >= 5000} 5001 + 6 0.2 {rowid >= 9000} 1001 + 7 0.2 {rowid <= 1000} 1000 + 8 0.6 {rowid > '5000'} 5000 + 9 0.2 {rowid > '9000'} 1000 + 10 0.1 {rowid = 444} 1 +} { + set q "SELECT rowid FROM t1 WHERE t1 MATCH 'x' AND $tail" + set n [execsql_reads $q] + set ret [llength [execsql $q]] + + do_test "1.7.$tn.asc.(n=$n ret=$ret)" { + expr {$n < ($fraction*$nReadX) && $ret==$cnt} + } {1} + + set q "SELECT rowid FROM t1 WHERE t1 MATCH 'x' AND $tail ORDER BY rowid DESC" + set n [execsql_reads $q] + set ret [llength [execsql $q]] + do_test "1.7.$tn.desc.(n=$n ret=$ret)" { + expr {$n < 2*$fraction*$nReadX && $ret==$cnt} + } {1} +} + +do_execsql_test 1.8.1 { + SELECT count(*) FROM t1 WHERE t1 MATCH 'x' AND +rowid < 'text'; +} {10000} +do_execsql_test 1.8.2 { + SELECT count(*) FROM t1 WHERE t1 MATCH 'x' AND rowid < 'text'; +} {10000} + #db eval {SELECT rowid, fts5_decode(rowid, block) aS r FROM t1_data} {puts $r} finish_test Index: ext/fts5/test/fts5plan.test ================================================================== --- ext/fts5/test/fts5plan.test +++ ext/fts5/test/fts5plan.test @@ -22,40 +22,40 @@ do_eqp_test 1.1 { SELECT * FROM t1, f1 WHERE f1 MATCH t1.x } { 0 0 0 {SCAN TABLE t1} - 0 1 1 {SCAN TABLE f1 VIRTUAL TABLE INDEX 2:} + 0 1 1 {SCAN TABLE f1 VIRTUAL TABLE INDEX 1:} } do_eqp_test 1.2 { SELECT * FROM t1, f1 WHERE f1 > t1.x } { - 0 0 1 {SCAN TABLE f1 VIRTUAL TABLE INDEX 1:} + 0 0 1 {SCAN TABLE f1 VIRTUAL TABLE INDEX 0:} 0 1 0 {SCAN TABLE t1} } do_eqp_test 1.3 { SELECT * FROM f1 WHERE f1 MATCH ? ORDER BY ff } { - 0 0 0 {SCAN TABLE f1 VIRTUAL TABLE INDEX 2:} + 0 0 0 {SCAN TABLE f1 VIRTUAL TABLE INDEX 1:} 0 0 0 {USE TEMP B-TREE FOR ORDER BY} } do_eqp_test 1.4 { SELECT * FROM f1 ORDER BY rank } { - 0 0 0 {SCAN TABLE f1 VIRTUAL TABLE INDEX 1:} + 0 0 0 {SCAN TABLE f1 VIRTUAL TABLE INDEX 0:} 0 0 0 {USE TEMP B-TREE FOR ORDER BY} } do_eqp_test 1.5 { SELECT * FROM f1 WHERE rank MATCH ? } { - 0 0 0 {SCAN TABLE f1 VIRTUAL TABLE INDEX 1:} + 0 0 0 {SCAN TABLE f1 VIRTUAL TABLE INDEX 2:} } finish_test