SQLite

**   2. Full-text search using a MATCH operator on a non-docid column.
**   3. Linear scan of %_content table.
*/
static int fts3BestIndexMethod(sqlite3_vtab *pVTab, sqlite3_index_info *pInfo){
  Fts3Table *p = (Fts3Table *)pVTab;
  int i;                          /* Iterator variable */
  int iCons = -1;                 /* Index of constraint to use */

  int iLangidCons = -1;           /* Index of langid=x constraint, if present */
  int iDocidGe = -1;              /* Index of docid>=x constraint, if present */
  int iDocidLe = -1;              /* Index of docid<=x constraint, if present */
  int iIdx;

  /* By default use a full table scan. This is an expensive option,
  ** so search through the constraints to see if a more efficient 
  ** strategy is possible.
  */
  pInfo->idxNum = FTS3_FULLSCAN_SEARCH;
  pInfo->estimatedCost = 5000000;
  for(i=0; i<pInfo->nConstraint; i++){
    int bDocid;                 /* True if this constraint is on docid */
    struct sqlite3_index_constraint *pCons = &pInfo->aConstraint[i];
    if( pCons->usable==0 ) continue;

    bDocid = (pCons->iColumn<0 || pCons->iColumn==p->nColumn+1);

    /* A direct lookup on the rowid or docid column. Assign a cost of 1.0. */

    if( iCons<0 && pCons->op==SQLITE_INDEX_CONSTRAINT_EQ && bDocid ){


      pInfo->idxNum = FTS3_DOCID_SEARCH;
      pInfo->estimatedCost = 1.0;
      iCons = i;
    }

    /* A MATCH constraint. Use a full-text search.
    **

    /* Equality constraint on the langid column */
    if( pCons->op==SQLITE_INDEX_CONSTRAINT_EQ 
     && pCons->iColumn==p->nColumn + 2
    ){
      iLangidCons = i;
    }

    if( bDocid ){
      switch( pCons->op ){
        case SQLITE_INDEX_CONSTRAINT_GE:
        case SQLITE_INDEX_CONSTRAINT_GT:
          iDocidGe = i;
          break;

        case SQLITE_INDEX_CONSTRAINT_LE:
        case SQLITE_INDEX_CONSTRAINT_LT:
          iDocidLe = i;
          break;
      }
    }
  }

  iIdx = 1;
  if( iCons>=0 ){
    pInfo->aConstraintUsage[iCons].argvIndex = iIdx++;
    pInfo->aConstraintUsage[iCons].omit = 1;
  } 
  if( iLangidCons>=0 ){
    pInfo->idxNum |= FTS3_HAVE_LANGID;
    pInfo->aConstraintUsage[iLangidCons].argvIndex = iIdx++;
  } 
  if( iDocidGe>=0 ){
    pInfo->idxNum |= FTS3_HAVE_DOCID_GE;
    pInfo->aConstraintUsage[iDocidGe].argvIndex = iIdx++;
  } 
  if( iDocidLe>=0 ){
    pInfo->idxNum |= FTS3_HAVE_DOCID_LE;
    pInfo->aConstraintUsage[iDocidLe].argvIndex = iIdx++;
  } 

  /* Regardless of the strategy selected, FTS can deliver rows in rowid (or
  ** docid) order. Both ascending and descending are possible. 
  */
  if( pInfo->nOrderBy==1 ){
    struct sqlite3_index_orderby *pOrder = &pInfo->aOrderBy[0];

    }
  }else{
    rc = fts3EvalNext((Fts3Cursor *)pCursor);
  }
  assert( ((Fts3Table *)pCsr->base.pVtab)->pSegments==0 );
  return rc;
}

/*
** The following are copied from sqliteInt.h.
**
** Constants for the largest and smallest possible 64-bit signed integers.
** These macros are designed to work correctly on both 32-bit and 64-bit
** compilers.
*/
#ifndef SQLITE_AMALGAMATION
# define LARGEST_INT64  (0xffffffff|(((sqlite3_int64)0x7fffffff)<<32))
# define SMALLEST_INT64 (((sqlite3_int64)-1) - LARGEST_INT64)
#endif

/*
** If the numeric type of argument pVal is "integer", then return it
** converted to a 64-bit signed integer. Otherwise, return a copy of
** the second parameter, iDefault.
*/
static sqlite3_int64 fts3DocidRange(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.
**
** If idxNum==FTS3_FULLSCAN_SEARCH then do a full table scan against

  int idxNum,                     /* Strategy index */
  const char *idxStr,             /* Unused */
  int nVal,                       /* Number of elements in apVal */
  sqlite3_value **apVal           /* Arguments for the indexing scheme */
){
  int rc;
  char *zSql;                     /* SQL statement used to access %_content */
  int eSearch;;
  Fts3Table *p = (Fts3Table *)pCursor->pVtab;
  Fts3Cursor *pCsr = (Fts3Cursor *)pCursor;

  sqlite3_value *pCons = 0;       /* The MATCH or rowid constraint, if any */
  sqlite3_value *pLangid = 0;     /* The "langid = ?" constraint, if any */
  sqlite3_value *pDocidGe = 0;    /* The "docid >= ?" constraint, if any */
  sqlite3_value *pDocidLe = 0;    /* The "docid <= ?" constraint, if any */
  int iIdx;

  UNUSED_PARAMETER(idxStr);
  UNUSED_PARAMETER(nVal);

  eSearch = (idxNum & 0x0000FFFF);
  assert( eSearch>=0 && eSearch<=(FTS3_FULLTEXT_SEARCH+p->nColumn) );
  assert( p->pSegments==0 );

  /* Collect arguments into local variables */
  iIdx = 0;
  if( eSearch!=FTS3_FULLSCAN_SEARCH ) pCons = apVal[iIdx++];
  if( idxNum & FTS3_HAVE_LANGID ) pLangid = apVal[iIdx++];
  if( idxNum & FTS3_HAVE_DOCID_GE ) pDocidGe = apVal[iIdx++];
  if( idxNum & FTS3_HAVE_DOCID_LE ) pDocidLe = apVal[iIdx++];
  assert( iIdx==nVal );

  /* In case the cursor has been used before, clear it now. */
  sqlite3_finalize(pCsr->pStmt);
  sqlite3_free(pCsr->aDoclist);
  sqlite3Fts3ExprFree(pCsr->pExpr);
  memset(&pCursor[1], 0, sizeof(Fts3Cursor)-sizeof(sqlite3_vtab_cursor));

  /* Set the lower and upper bounds on docids to return */
  pCsr->iMinDocid = fts3DocidRange(pDocidGe, SMALLEST_INT64);
  pCsr->iMaxDocid = fts3DocidRange(pDocidLe, LARGEST_INT64);

  if( idxStr ){
    pCsr->bDesc = (idxStr[0]=='D');
  }else{
    pCsr->bDesc = p->bDescIdx;
  }
  pCsr->eSearch = (i16)eSearch;

  if( eSearch!=FTS3_DOCID_SEARCH && eSearch!=FTS3_FULLSCAN_SEARCH ){
    int iCol = eSearch-FTS3_FULLTEXT_SEARCH;
    const char *zQuery = (const char *)sqlite3_value_text(pCons);

    if( zQuery==0 && sqlite3_value_type(pCons)!=SQLITE_NULL ){
      return SQLITE_NOMEM;
    }

    pCsr->iLangid = 0;
    if( pLangid ) pCsr->iLangid = sqlite3_value_int(pLangid);

    assert( p->base.zErrMsg==0 );
    rc = sqlite3Fts3ExprParse(p->pTokenizer, pCsr->iLangid,
        p->azColumn, p->bFts4, p->nColumn, iCol, zQuery, -1, &pCsr->pExpr, 
        &p->base.zErrMsg
    );
    if( rc!=SQLITE_OK ){

  }

  /* Compile a SELECT statement for this cursor. For a full-table-scan, the
  ** statement loops through all rows of the %_content table. For a
  ** full-text query or docid lookup, the statement retrieves a single
  ** row by docid.
  */
  if( eSearch==FTS3_FULLSCAN_SEARCH ){
    zSql = sqlite3_mprintf(
        "SELECT %s ORDER BY rowid %s",
        p->zReadExprlist, (pCsr->bDesc ? "DESC" : "ASC")
    );
    if( zSql ){
      rc = sqlite3_prepare_v2(p->db, zSql, -1, &pCsr->pStmt, 0);
      sqlite3_free(zSql);
    }else{
      rc = SQLITE_NOMEM;
    }
  }else if( eSearch==FTS3_DOCID_SEARCH ){
    rc = fts3CursorSeekStmt(pCsr, &pCsr->pStmt);
    if( rc==SQLITE_OK ){
      rc = sqlite3_bind_value(pCsr->pStmt, 1, pCons);
    }
  }
  if( rc!=SQLITE_OK ) return rc;

  return fts3NextMethod(pCursor);
}

      fts3EvalNextRow(pCsr, pExpr, &rc);
      pCsr->isEof = pExpr->bEof;
      pCsr->isRequireSeek = 1;
      pCsr->isMatchinfoNeeded = 1;
      pCsr->iPrevId = pExpr->iDocid;
    }while( pCsr->isEof==0 && fts3EvalTestDeferredAndNear(pCsr, &rc) );
  }

  /* Check if the cursor is past the end of the docid range specified
  ** by Fts3Cursor.iMinDocid/iMaxDocid. If so, set the EOF flag.  */
  if( rc==SQLITE_OK && (
        (pCsr->bDesc==0 && pCsr->iPrevId>pCsr->iMaxDocid)
     || (pCsr->bDesc!=0 && pCsr->iPrevId<pCsr->iMinDocid)
  )){
    pCsr->isEof = 1;
  }

  return rc;
}

/*
** Restart interation for expression pExpr so that the next call to
** fts3EvalNext() visits the first row. Do not allow incremental 
** loading or merging of phrase doclists for this iteration.

  char *pNextId;                  /* Pointer into the body of aDoclist */
  char *aDoclist;                 /* List of docids for full-text queries */
  int nDoclist;                   /* Size of buffer at aDoclist */
  u8 bDesc;                       /* True to sort in descending order */
  int eEvalmode;                  /* An FTS3_EVAL_XX constant */
  int nRowAvg;                    /* Average size of database rows, in pages */
  sqlite3_int64 nDoc;             /* Documents in table */
  i64 iMinDocid;                  /* Minimum docid to return */
  i64 iMaxDocid;                  /* Maximum docid to return */
  int isMatchinfoNeeded;          /* True when aMatchinfo[] needs filling in */
  u32 *aMatchinfo;                /* Information about most recent match */
  int nMatchinfo;                 /* Number of elements in aMatchinfo[] */
  char *zMatchinfo;               /* Matchinfo specification */
};

#define FTS3_EVAL_FILTER    0

** indicating that all columns should be searched,
** then eSearch would be set to FTS3_FULLTEXT_SEARCH+4.
*/
#define FTS3_FULLSCAN_SEARCH 0    /* Linear scan of %_content table */
#define FTS3_DOCID_SEARCH    1    /* Lookup by rowid on %_content table */
#define FTS3_FULLTEXT_SEARCH 2    /* Full-text index search */

/*
** The lower 16-bits of the sqlite3_index_info.idxNum value set by
** the xBestIndex() method contains the Fts3Cursor.eSearch value described
** above. The upper 16-bits contain a combination of the following
** bits, used to describe extra constraints on full-text searches.
*/
#define FTS3_HAVE_LANGID    0x00010000      /* languageid=? */
#define FTS3_HAVE_DOCID_GE  0x00020000      /* docid>=? */
#define FTS3_HAVE_DOCID_LE  0x00040000      /* docid<=? */

struct Fts3Doclist {
  char *aAll;                    /* Array containing doclist (or NULL) */
  int nAll;                      /* Size of a[] in bytes */
  char *pNextDocid;              /* Pointer to next docid */

  sqlite3_int64 iDocid;          /* Current docid (if pList!=0) */

# 2012 March 26
#
# 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.
#
#*************************************************************************
#

set testdir [file dirname $argv0]
source $testdir/tester.tcl
source $testdir/fts3_common.tcl
set ::testprefix fts4docid

# If SQLITE_ENABLE_FTS3 is defined, omit this file.
ifcapable !fts3 {
  finish_test
  return
}

# Initialize a table with pseudo-randomly generated data.
#
do_execsql_test 1.0 { CREATE VIRTUAL TABLE t1 USING fts4; }
do_test 1.1 {
  foreach {docid content} {
    0  {F N K B T I K V B A}    1  {D M J E S P H E L O}
    2  {W U T Q T Q T L H G}    3  {D W H M B R S Z B K}
    4  {F Q I N P Q J L Z D}    5  {J O Q E Y A O E L B}
    6  {O V R A C R K C Y H}    7  {Z J H T Q Q O R A G}
    8  {L K J W G D Y W B M}    9  {K E Y I A Q R Q T S}
    10 {N P H Y Z M R T I C}    11 {E X H O I S E S Z F}
    12 {B Y Q T J X C L L J}    13 {Q D C U U A Q E Z U}
    14 {S I T C J R X S J M}    15 {M X M K E X L H Q Y}
    16 {O W E I C H U Y S Y}    17 {P V V E M T H C C S}
    18 {L Y A M I E N M X O}    19 {S Y R U L S Q Y F P}
    20 {U J S T T J J S V X}    21 {T E I W P O V A A P}
    22 {W D K H D H F G O J}    23 {T X Y P G M J U I L}
    24 {F V X E B C N B K W}    25 {E B A Y N N T Z I C}
    26 {G E E B C P U D H G}    27 {J D J K N S B Q T M}
    28 {Q T G M D O D Y V G}    29 {P X W I W V P W Z G}
  } {
    execsql { INSERT INTO t1(docid, content) VALUES($docid, $content) }
  }
} {}

# Quick test regarding affinites and the docid/rowid column.
do_execsql_test 2.1.1 { SELECT docid FROM t1 WHERE docid = 5 } {5}
do_execsql_test 2.1.2 { SELECT docid FROM t1 WHERE docid = '5' } {5}
do_execsql_test 2.1.3 { SELECT docid FROM t1 WHERE docid = +5 } {5}
do_execsql_test 2.1.4 { SELECT docid FROM t1 WHERE docid = +'5' } {5}
do_execsql_test 2.1.5 { SELECT docid FROM t1 WHERE docid < 5 } {0 1 2 3 4}
do_execsql_test 2.1.6 { SELECT docid FROM t1 WHERE docid < '5' } {0 1 2 3 4}

do_execsql_test 2.2.1 { SELECT rowid FROM t1 WHERE rowid = 5 } {5}
do_execsql_test 2.2.2 { SELECT rowid FROM t1 WHERE rowid = '5' } {5}
do_execsql_test 2.2.3 { SELECT rowid FROM t1 WHERE rowid = +5 } {5}
do_execsql_test 2.2.4 { SELECT rowid FROM t1 WHERE rowid = +'5' } {5}
do_execsql_test 2.2.5 { SELECT rowid FROM t1 WHERE rowid < 5 } {0 1 2 3 4}
do_execsql_test 2.2.6 { SELECT rowid FROM t1 WHERE rowid < '5' } {0 1 2 3 4}

#-------------------------------------------------------------------------
# Now test a bunch of full-text queries featuring range constraints on
# the docid field. Each query is run so that the range constraint:
#
#   * is on the docid field,
#   * is on the docid field with a unary +,
#   * is on the rowid field,
#   * is on the rowid field with a unary +.
#
# Queries are run with both "ORDER BY docid DESC" and "ORDER BY docid ASC"
# clauses.
#
foreach {tn where result} {
  1 {WHERE t1 MATCH 'O' AND xxx < 17}                {1 5 6 7 11 16}
  2 {WHERE t1 MATCH 'O' AND xxx < 4123456789123456}  {1 5 6 7 11 16 18 21 22 28}
  3 {WHERE t1 MATCH 'O' AND xxx < 1}                 {}
  4 {WHERE t1 MATCH 'O' AND xxx < -4123456789123456} {}

  5 {WHERE t1 MATCH 'O' AND xxx > 17}                {18 21 22 28}
  6 {WHERE t1 MATCH 'O' AND xxx > 4123456789123456}  {}
  7 {WHERE t1 MATCH 'O' AND xxx > 1}                 {5 6 7 11 16 18 21 22 28}
  8 {WHERE t1 MATCH 'O' AND xxx > -4123456789123456} {1 5 6 7 11 16 18 21 22 28}

  9 {WHERE t1 MATCH '"Q T"' AND xxx < 27}  {2 9 12}
  10 {WHERE t1 MATCH '"Q T"' AND xxx <= 27} {2 9 12 27}
  11 {WHERE t1 MATCH '"Q T"' AND xxx > 27}  {28}
  12 {WHERE t1 MATCH '"Q T"' AND xxx >= 27} {27 28}
} {
  foreach {tn2 ref order} {
    1  docid "ORDER BY docid ASC"
    2 +docid "ORDER BY docid ASC"
    3  rowid "ORDER BY docid ASC"
    4 +rowid "ORDER BY docid ASC"

    5  docid "ORDER BY docid DESC"
    6 +docid "ORDER BY docid DESC"
    7  rowid "ORDER BY docid DESC"
    8 +rowid "ORDER BY docid DESC"
  } {
    set w [string map "xxx $ref" $where]
    set q "SELECT docid FROM t1 $w $order"

    if {$tn2<5} {
      set r [lsort -integer -increasing $result] 
    } else {
      set r [lsort -integer -decreasing $result] 
    }

    do_execsql_test 3.$tn.$tn2 $q $r
  }
}

finish_test