/ Check-in [386701de]
Login

Many hyperlinks are disabled.
Use anonymous login to enable hyperlinks.

Overview
Comment:Optimize handling of equality and range constraints on the "term" column of an fts4aux table.
Downloads: Tarball | ZIP archive | SQL archive
Timelines: family | ancestors | descendants | both | trunk
Files: files | file ages | folders
SHA1:386701ded2bcee5309ec9f285d94e6eb1eade193
User & Date: dan 2011-02-02 17:30:43
Context
2011-02-02
19:17
Fix minor problems with the output of "PRAGMA wal_checkpoint". In both code and tests. check-in: aef61036 user: dan tags: trunk
17:30
Optimize handling of equality and range constraints on the "term" column of an fts4aux table. check-in: 386701de user: dan tags: trunk
16:34
Merge in the blocking-checkpoint enhancement, including the new sqlite3_wal_checkpoint_v2() interface and the PRAGMA wal_checkpoint(full) statement. check-in: bac7342c user: drh tags: trunk
Changes
Hide Diffs Unified Diffs Show Whitespace Changes Patch

Changes to ext/fts3/fts3.c.

2048
2049
2050
2051
2052
2053
2054

2055
2056
2057
2058
2059
2060
2061
....
2063
2064
2065
2066
2067
2068
2069


2070
2071
2072
2073

2074
2075
2076
2077
2078
2079
2080
2081
....
2113
2114
2115
2116
2117
2118
2119
2120
2121
2122
2123
2124
2125
2126
2127
....
2150
2151
2152
2153
2154
2155
2156
2157
2158
2159
2160
2161
2162
2163
2164

int sqlite3Fts3SegReaderCursor(
  Fts3Table *p,                   /* FTS3 table handle */
  int iLevel,                     /* Level of segments to scan */
  const char *zTerm,              /* Term to query for */
  int nTerm,                      /* Size of zTerm in bytes */
  int isPrefix,                   /* True for a prefix search */

  Fts3SegReaderCursor *pCsr       /* Cursor object to populate */
){
  int rc = SQLITE_OK;
  int rc2;
  int iAge = 0;
  sqlite3_stmt *pStmt = 0;
  Fts3SegReader *pPending = 0;
................................................................................
  assert( iLevel==FTS3_SEGCURSOR_ALL 
      ||  iLevel==FTS3_SEGCURSOR_PENDING 
      ||  iLevel>=0
  );
  assert( FTS3_SEGCURSOR_PENDING<0 );
  assert( FTS3_SEGCURSOR_ALL<0 );
  assert( iLevel==FTS3_SEGCURSOR_ALL || (zTerm==0 && isPrefix==1) );



  memset(pCsr, 0, sizeof(Fts3SegReaderCursor));

  /* If iLevel is less than 0, include a seg-reader for the pending-terms. */

  if( iLevel<0 ){
    rc = sqlite3Fts3SegReaderPending(p, zTerm, nTerm, isPrefix, &pPending);
    if( rc==SQLITE_OK && pPending ){
      int nByte = (sizeof(Fts3SegReader *) * 16);
      pCsr->apSegment = (Fts3SegReader **)sqlite3_malloc(nByte);
      if( pCsr->apSegment==0 ){
        rc = SQLITE_NOMEM;
      }else{
................................................................................

      /* If zTerm is not NULL, and this segment is not stored entirely on its
      ** root node, the range of leaves scanned can be reduced. Do this. */
      if( iStartBlock && zTerm ){
        sqlite3_int64 *pi = (isPrefix ? &iLeavesEndBlock : 0);
        rc = fts3SelectLeaf(p, zTerm, nTerm, zRoot, nRoot, &iStartBlock, pi);
        if( rc!=SQLITE_OK ) goto finished;
        if( isPrefix==0 ) iLeavesEndBlock = iStartBlock;
      }
  
      rc = sqlite3Fts3SegReaderNew(iAge, iStartBlock, iLeavesEndBlock,
          iEndBlock, zRoot, nRoot, &pCsr->apSegment[pCsr->nSegment]
      );
      if( rc!=SQLITE_OK ) goto finished;
      pCsr->nSegment++;
................................................................................

  pSegcsr = sqlite3_malloc(sizeof(Fts3SegReaderCursor));
  if( pSegcsr ){
    Fts3Table *p = (Fts3Table *)pCsr->base.pVtab;
    int i;
    int nCost = 0;
    rc = sqlite3Fts3SegReaderCursor(
        p, FTS3_SEGCURSOR_ALL, zTerm, nTerm, isPrefix, pSegcsr);
  
    for(i=0; rc==SQLITE_OK && i<pSegcsr->nSegment; i++){
      rc = sqlite3Fts3SegReaderCost(pCsr, pSegcsr->apSegment[i], &nCost);
    }
    pSegcsr->nCost = nCost;
  }








>







 







>
>




>
|







 







|







 







|







2048
2049
2050
2051
2052
2053
2054
2055
2056
2057
2058
2059
2060
2061
2062
....
2064
2065
2066
2067
2068
2069
2070
2071
2072
2073
2074
2075
2076
2077
2078
2079
2080
2081
2082
2083
2084
2085
....
2117
2118
2119
2120
2121
2122
2123
2124
2125
2126
2127
2128
2129
2130
2131
....
2154
2155
2156
2157
2158
2159
2160
2161
2162
2163
2164
2165
2166
2167
2168

int sqlite3Fts3SegReaderCursor(
  Fts3Table *p,                   /* FTS3 table handle */
  int iLevel,                     /* Level of segments to scan */
  const char *zTerm,              /* Term to query for */
  int nTerm,                      /* Size of zTerm in bytes */
  int isPrefix,                   /* True for a prefix search */
  int isScan,                     /* True to scan from zTerm to EOF */
  Fts3SegReaderCursor *pCsr       /* Cursor object to populate */
){
  int rc = SQLITE_OK;
  int rc2;
  int iAge = 0;
  sqlite3_stmt *pStmt = 0;
  Fts3SegReader *pPending = 0;
................................................................................
  assert( iLevel==FTS3_SEGCURSOR_ALL 
      ||  iLevel==FTS3_SEGCURSOR_PENDING 
      ||  iLevel>=0
  );
  assert( FTS3_SEGCURSOR_PENDING<0 );
  assert( FTS3_SEGCURSOR_ALL<0 );
  assert( iLevel==FTS3_SEGCURSOR_ALL || (zTerm==0 && isPrefix==1) );
  assert( isPrefix==0 || isScan==0 );


  memset(pCsr, 0, sizeof(Fts3SegReaderCursor));

  /* If iLevel is less than 0, include a seg-reader for the pending-terms. */
  assert( isScan==0 || fts3HashCount(&p->pendingTerms)==0 );
  if( iLevel<0 && isScan==0 ){
    rc = sqlite3Fts3SegReaderPending(p, zTerm, nTerm, isPrefix, &pPending);
    if( rc==SQLITE_OK && pPending ){
      int nByte = (sizeof(Fts3SegReader *) * 16);
      pCsr->apSegment = (Fts3SegReader **)sqlite3_malloc(nByte);
      if( pCsr->apSegment==0 ){
        rc = SQLITE_NOMEM;
      }else{
................................................................................

      /* If zTerm is not NULL, and this segment is not stored entirely on its
      ** root node, the range of leaves scanned can be reduced. Do this. */
      if( iStartBlock && zTerm ){
        sqlite3_int64 *pi = (isPrefix ? &iLeavesEndBlock : 0);
        rc = fts3SelectLeaf(p, zTerm, nTerm, zRoot, nRoot, &iStartBlock, pi);
        if( rc!=SQLITE_OK ) goto finished;
        if( isPrefix==0 && isScan==0 ) iLeavesEndBlock = iStartBlock;
      }
 
      rc = sqlite3Fts3SegReaderNew(iAge, iStartBlock, iLeavesEndBlock,
          iEndBlock, zRoot, nRoot, &pCsr->apSegment[pCsr->nSegment]
      );
      if( rc!=SQLITE_OK ) goto finished;
      pCsr->nSegment++;
................................................................................

  pSegcsr = sqlite3_malloc(sizeof(Fts3SegReaderCursor));
  if( pSegcsr ){
    Fts3Table *p = (Fts3Table *)pCsr->base.pVtab;
    int i;
    int nCost = 0;
    rc = sqlite3Fts3SegReaderCursor(
        p, FTS3_SEGCURSOR_ALL, zTerm, nTerm, isPrefix, 0, pSegcsr);
  
    for(i=0; rc==SQLITE_OK && i<pSegcsr->nSegment; i++){
      rc = sqlite3Fts3SegReaderCost(pCsr, pSegcsr->apSegment[i], &nCost);
    }
    pSegcsr->nCost = nCost;
  }

Changes to ext/fts3/fts3Int.h.

306
307
308
309
310
311
312
313
314
315
316
317
318
319

320
321
322
323
324
325
326
#define FTS3_SEGCURSOR_PENDING -1
#define FTS3_SEGCURSOR_ALL     -2

int sqlite3Fts3SegReaderStart(Fts3Table*, Fts3SegReaderCursor*, Fts3SegFilter*);
int sqlite3Fts3SegReaderStep(Fts3Table *, Fts3SegReaderCursor *);
void sqlite3Fts3SegReaderFinish(Fts3SegReaderCursor *);
int sqlite3Fts3SegReaderCursor(
    Fts3Table *, int, const char *, int, int, Fts3SegReaderCursor *);

/* Flags allowed as part of the 4th argument to SegmentReaderIterate() */
#define FTS3_SEGMENT_REQUIRE_POS   0x00000001
#define FTS3_SEGMENT_IGNORE_EMPTY  0x00000002
#define FTS3_SEGMENT_COLUMN_FILTER 0x00000004
#define FTS3_SEGMENT_PREFIX        0x00000008


/* Type passed as 4th argument to SegmentReaderIterate() */
struct Fts3SegFilter {
  const char *zTerm;
  int nTerm;
  int iCol;
  int flags;







|






>







306
307
308
309
310
311
312
313
314
315
316
317
318
319
320
321
322
323
324
325
326
327
#define FTS3_SEGCURSOR_PENDING -1
#define FTS3_SEGCURSOR_ALL     -2

int sqlite3Fts3SegReaderStart(Fts3Table*, Fts3SegReaderCursor*, Fts3SegFilter*);
int sqlite3Fts3SegReaderStep(Fts3Table *, Fts3SegReaderCursor *);
void sqlite3Fts3SegReaderFinish(Fts3SegReaderCursor *);
int sqlite3Fts3SegReaderCursor(
    Fts3Table *, int, const char *, int, int, int, Fts3SegReaderCursor *);

/* Flags allowed as part of the 4th argument to SegmentReaderIterate() */
#define FTS3_SEGMENT_REQUIRE_POS   0x00000001
#define FTS3_SEGMENT_IGNORE_EMPTY  0x00000002
#define FTS3_SEGMENT_COLUMN_FILTER 0x00000004
#define FTS3_SEGMENT_PREFIX        0x00000008
#define FTS3_SEGMENT_SCAN          0x00000010

/* Type passed as 4th argument to SegmentReaderIterate() */
struct Fts3SegFilter {
  const char *zTerm;
  int nTerm;
  int iCol;
  int flags;

Changes to ext/fts3/fts3_aux.c.

24
25
26
27
28
29
30
31

32
33

34
35
36
37
38
39
40
41
42
...
110
111
112
113
114
115
116




117
118
119
120
121
122
123




124
125
126
127
128
129
130
131



























132
133
134
135
136
137
138
...
153
154
155
156
157
158
159


160
161
162
163
164
165
166
...
171
172
173
174
175
176
177









178
179
180
181
182
183
184
...
212
213
214
215
216
217
218

219









220

221
222
223

224

225















226


227
228
229
230
231
232
233
struct Fts3auxTable {
  sqlite3_vtab base;              /* Base class used by SQLite core */
  Fts3Table *pFts3Tab;
};

struct Fts3auxCursor {
  sqlite3_vtab_cursor base;       /* Base class used by SQLite core */


  Fts3SegFilter filter;
  Fts3SegReaderCursor csr;

  int isEof;

  sqlite3_int64 iRowid;
  sqlite3_int64 nDoc;
  sqlite3_int64 nOcc;
};

/*
** Schema of the terms table.
................................................................................
    sqlite3_finalize(pFts3->aStmt[i]);
  }
  sqlite3_free(pFts3->zSegmentsTbl);
  sqlite3_free(p);
  return SQLITE_OK;
}





/*
** xBestIndex - Analyze a WHERE and ORDER BY clause.
*/
static int fts3auxBestIndexMethod(
  sqlite3_vtab *pVTab, 
  sqlite3_index_info *pInfo
){





  /* This vtab delivers always results in "ORDER BY term ASC" order. */
  if( pInfo->nOrderBy==1 
   && pInfo->aOrderBy[0].iColumn==0 
   && pInfo->aOrderBy[0].desc==0
  ){
    pInfo->orderByConsumed = 1;
  }




























  pInfo->estimatedCost = 20000;
  return SQLITE_OK;
}

/*
** xOpen - Open a cursor.
................................................................................
*/
static int fts3auxCloseMethod(sqlite3_vtab_cursor *pCursor){
  Fts3Table *pFts3 = ((Fts3auxTable *)pCursor->pVtab)->pFts3Tab;
  Fts3auxCursor *pCsr = (Fts3auxCursor *)pCursor;

  sqlite3Fts3SegmentsClose(pFts3);
  sqlite3Fts3SegReaderFinish(&pCsr->csr);


  sqlite3_free(pCsr);
  return SQLITE_OK;
}

/*
** xNext - Advance the cursor to the next row, if any.
*/
................................................................................

  rc = sqlite3Fts3SegReaderStep(pFts3, &pCsr->csr);
  if( rc==SQLITE_ROW ){
    int i;
    int isIgnore = 1;
    int nDoclist = pCsr->csr.nDoclist;
    char *aDoclist = pCsr->csr.aDoclist;










    /* Now count the number of documents and positions in the doclist
    ** in pCsr->csr.aDoclist[]. Store the number of documents in pCsr->nDoc
    ** and the number of occurrences in pCsr->nOcc.  */
    pCsr->nDoc = 0;
    pCsr->nOcc = 0;
    i = 0;
................................................................................
  const char *idxStr,             /* Unused */
  int nVal,                       /* Number of elements in apVal */
  sqlite3_value **apVal           /* Arguments for the indexing scheme */
){
  Fts3auxCursor *pCsr = (Fts3auxCursor *)pCursor;
  Fts3Table *pFts3 = ((Fts3auxTable *)pCursor->pVtab)->pFts3Tab;
  int rc;











  sqlite3Fts3SegReaderFinish(&pCsr->csr);

  memset(&pCsr->csr, 0, sizeof(Fts3SegReaderCursor));
  pCsr->isEof = 0;
  pCsr->iRowid = 0;

  pCsr->filter.flags = FTS3_SEGMENT_REQUIRE_POS|FTS3_SEGMENT_IGNORE_EMPTY;

















  rc = sqlite3Fts3SegReaderCursor(pFts3, FTS3_SEGCURSOR_ALL, 0, 0,1,&pCsr->csr);


  if( rc==SQLITE_OK ){
    rc = sqlite3Fts3SegReaderStart(pFts3, &pCsr->csr, &pCsr->filter);
  }

  if( rc==SQLITE_OK ) rc = fts3auxNextMethod(pCursor);
  return rc;
}







<
>

|
>

<







 







>
>
>
>







>
>
>
>








>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>







 







>
>







 







>
>
>
>
>
>
>
>
>







 







>

>
>
>
>
>
>
>
>
>

>
|
<
<
>

>

>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
|
>
>







24
25
26
27
28
29
30

31
32
33
34
35

36
37
38
39
40
41
42
...
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
...
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
...
208
209
210
211
212
213
214
215
216
217
218
219
220
221
222
223
224
225
226
227
228
229
230
...
258
259
260
261
262
263
264
265
266
267
268
269
270
271
272
273
274
275
276
277
278


279
280
281
282
283
284
285
286
287
288
289
290
291
292
293
294
295
296
297
298
299
300
301
302
303
304
305
306
307
struct Fts3auxTable {
  sqlite3_vtab base;              /* Base class used by SQLite core */
  Fts3Table *pFts3Tab;
};

struct Fts3auxCursor {
  sqlite3_vtab_cursor base;       /* Base class used by SQLite core */

  Fts3SegReaderCursor csr;        /* Must be right after "base" */
  Fts3SegFilter filter;
  char *zStop;
  int nStop;
  int isEof;

  sqlite3_int64 iRowid;
  sqlite3_int64 nDoc;
  sqlite3_int64 nOcc;
};

/*
** Schema of the terms table.
................................................................................
    sqlite3_finalize(pFts3->aStmt[i]);
  }
  sqlite3_free(pFts3->zSegmentsTbl);
  sqlite3_free(p);
  return SQLITE_OK;
}

#define FTS4AUX_EQ_CONSTRAINT 1
#define FTS4AUX_GE_CONSTRAINT 2
#define FTS4AUX_LE_CONSTRAINT 4

/*
** xBestIndex - Analyze a WHERE and ORDER BY clause.
*/
static int fts3auxBestIndexMethod(
  sqlite3_vtab *pVTab, 
  sqlite3_index_info *pInfo
){
  int i;
  int iEq = -1;
  int iGe = -1;
  int iLe = -1;

  /* This vtab delivers always results in "ORDER BY term ASC" order. */
  if( pInfo->nOrderBy==1 
   && pInfo->aOrderBy[0].iColumn==0 
   && pInfo->aOrderBy[0].desc==0
  ){
    pInfo->orderByConsumed = 1;
  }

  /* Search for equality and range constraints on the "term" column. */
  for(i=0; i<pInfo->nConstraint; i++){
    if( pInfo->aConstraint[i].usable && pInfo->aConstraint[i].iColumn==0 ){
      int op = pInfo->aConstraint[i].op;
      if( op==SQLITE_INDEX_CONSTRAINT_EQ ) iEq = i;
      if( op==SQLITE_INDEX_CONSTRAINT_LT ) iLe = i;
      if( op==SQLITE_INDEX_CONSTRAINT_LE ) iLe = i;
      if( op==SQLITE_INDEX_CONSTRAINT_GT ) iGe = i;
      if( op==SQLITE_INDEX_CONSTRAINT_GE ) iGe = i;
    }
  }

  if( iEq>=0 ){
    pInfo->idxNum = FTS4AUX_EQ_CONSTRAINT;
    pInfo->aConstraintUsage[iEq].argvIndex = 1;
  }else{
    pInfo->idxNum = 0;
    if( iGe>=0 ){
      pInfo->idxNum += FTS4AUX_GE_CONSTRAINT;
      pInfo->aConstraintUsage[iGe].argvIndex = 1;
    }
    if( iLe>=0 ){
      pInfo->idxNum += FTS4AUX_LE_CONSTRAINT;
      pInfo->aConstraintUsage[iLe].argvIndex = 1 + (iGe>=0);
    }
  }

  pInfo->estimatedCost = 20000;
  return SQLITE_OK;
}

/*
** xOpen - Open a cursor.
................................................................................
*/
static int fts3auxCloseMethod(sqlite3_vtab_cursor *pCursor){
  Fts3Table *pFts3 = ((Fts3auxTable *)pCursor->pVtab)->pFts3Tab;
  Fts3auxCursor *pCsr = (Fts3auxCursor *)pCursor;

  sqlite3Fts3SegmentsClose(pFts3);
  sqlite3Fts3SegReaderFinish(&pCsr->csr);
  sqlite3_free((void *)pCsr->filter.zTerm);
  sqlite3_free(pCsr->zStop);
  sqlite3_free(pCsr);
  return SQLITE_OK;
}

/*
** xNext - Advance the cursor to the next row, if any.
*/
................................................................................

  rc = sqlite3Fts3SegReaderStep(pFts3, &pCsr->csr);
  if( rc==SQLITE_ROW ){
    int i;
    int isIgnore = 1;
    int nDoclist = pCsr->csr.nDoclist;
    char *aDoclist = pCsr->csr.aDoclist;

    if( pCsr->zStop ){
      int n = (pCsr->nStop<pCsr->csr.nTerm) ? pCsr->nStop : pCsr->csr.nTerm;
      int mc = memcmp(pCsr->zStop, pCsr->csr.zTerm, n);
      if( mc<0 || (mc==0 && pCsr->csr.nTerm>pCsr->nStop) ){
        pCsr->isEof = 1;
        return SQLITE_OK;
      }
    }

    /* Now count the number of documents and positions in the doclist
    ** in pCsr->csr.aDoclist[]. Store the number of documents in pCsr->nDoc
    ** and the number of occurrences in pCsr->nOcc.  */
    pCsr->nDoc = 0;
    pCsr->nOcc = 0;
    i = 0;
................................................................................
  const char *idxStr,             /* Unused */
  int nVal,                       /* Number of elements in apVal */
  sqlite3_value **apVal           /* Arguments for the indexing scheme */
){
  Fts3auxCursor *pCsr = (Fts3auxCursor *)pCursor;
  Fts3Table *pFts3 = ((Fts3auxTable *)pCursor->pVtab)->pFts3Tab;
  int rc;
  int isScan;

  assert( idxStr==0 );
  assert( idxNum==FTS4AUX_EQ_CONSTRAINT || idxNum==0
       || idxNum==FTS4AUX_LE_CONSTRAINT || idxNum==FTS4AUX_GE_CONSTRAINT
       || idxNum==(FTS4AUX_LE_CONSTRAINT|FTS4AUX_GE_CONSTRAINT)
  );
  isScan = (idxNum!=FTS4AUX_EQ_CONSTRAINT);

  /* In case this cursor is being reused, close and zero it. */
  testcase(pCsr->filter.zTerm);
  sqlite3Fts3SegReaderFinish(&pCsr->csr);
  sqlite3_free((void *)pCsr->filter.zTerm);
  memset(&pCsr->csr, 0, ((u8*)&pCsr[1]) - (u8*)&pCsr->csr);



  pCsr->filter.flags = FTS3_SEGMENT_REQUIRE_POS|FTS3_SEGMENT_IGNORE_EMPTY;
  if( isScan ) pCsr->filter.flags |= FTS3_SEGMENT_SCAN;

  if( idxNum&(FTS4AUX_EQ_CONSTRAINT|FTS4AUX_GE_CONSTRAINT) ){
    const char *zStr = sqlite3_value_text(apVal[0]);
    if( zStr ){
      pCsr->filter.zTerm = sqlite3_mprintf("%s", zStr);
      pCsr->filter.nTerm = sqlite3_value_bytes(apVal[0]);
      if( pCsr->filter.zTerm==0 ) return SQLITE_NOMEM;
    }
  }
  if( idxNum&FTS4AUX_LE_CONSTRAINT ){
    int iIdx = (idxNum&FTS4AUX_GE_CONSTRAINT) ? 1 : 0;
    pCsr->zStop = sqlite3_mprintf("%s", sqlite3_value_text(apVal[iIdx]));
    pCsr->nStop = sqlite3_value_bytes(apVal[iIdx]);
    if( pCsr->zStop==0 ) return SQLITE_NOMEM;
  }

  rc = sqlite3Fts3SegReaderCursor(pFts3, FTS3_SEGCURSOR_ALL,
      pCsr->filter.zTerm, pCsr->filter.nTerm, 0, isScan, &pCsr->csr
  );
  if( rc==SQLITE_OK ){
    rc = sqlite3Fts3SegReaderStart(pFts3, &pCsr->csr, &pCsr->filter);
  }

  if( rc==SQLITE_OK ) rc = fts3auxNextMethod(pCursor);
  return rc;
}

Changes to ext/fts3/fts3_write.c.

2062
2063
2064
2065
2066
2067
2068

2069
2070
2071
2072
2073
2074
2075
....
2097
2098
2099
2100
2101
2102
2103
2104
2105
2106
2107
2108
2109
2110
2111
....
2224
2225
2226
2227
2228
2229
2230
2231
2232
2233
2234
2235
2236
2237
2238
){
  int rc = SQLITE_OK;

  int isIgnoreEmpty =  (pCsr->pFilter->flags & FTS3_SEGMENT_IGNORE_EMPTY);
  int isRequirePos =   (pCsr->pFilter->flags & FTS3_SEGMENT_REQUIRE_POS);
  int isColFilter =    (pCsr->pFilter->flags & FTS3_SEGMENT_COLUMN_FILTER);
  int isPrefix =       (pCsr->pFilter->flags & FTS3_SEGMENT_PREFIX);


  Fts3SegReader **apSegment = pCsr->apSegment;
  int nSegment = pCsr->nSegment;
  Fts3SegFilter *pFilter = pCsr->pFilter;

  if( pCsr->nSegment==0 ) return SQLITE_OK;

................................................................................
    /* If this is a prefix-search, and if the term that apSegment[0] points
    ** to does not share a suffix with pFilter->zTerm/nTerm, then all 
    ** required callbacks have been made. In this case exit early.
    **
    ** Similarly, if this is a search for an exact match, and the first term
    ** of segment apSegment[0] is not a match, exit early.
    */
    if( pFilter->zTerm ){
      if( pCsr->nTerm<pFilter->nTerm 
       || (!isPrefix && pCsr->nTerm>pFilter->nTerm)
       || memcmp(pCsr->zTerm, pFilter->zTerm, pFilter->nTerm) 
      ){
        break;
      }
    }
................................................................................
  int rc;                         /* Return code */
  int iIdx;                       /* Index of new segment */
  int iNewLevel = 0;              /* Level to create new segment at */
  SegmentWriter *pWriter = 0;     /* Used to write the new, merged, segment */
  Fts3SegFilter filter;           /* Segment term filter condition */
  Fts3SegReaderCursor csr;        /* Cursor to iterate through level(s) */

  rc = sqlite3Fts3SegReaderCursor(p, iLevel, 0, 0, 1, &csr);
  if( rc!=SQLITE_OK || csr.nSegment==0 ) goto finished;

  if( iLevel==FTS3_SEGCURSOR_ALL ){
    /* This call is to merge all segments in the database to a single
    ** segment. The level of the new segment is equal to the the numerically 
    ** greatest segment level currently present in the database. The index
    ** of the new segment is always 0.  */







>







 







|







 







|







2062
2063
2064
2065
2066
2067
2068
2069
2070
2071
2072
2073
2074
2075
2076
....
2098
2099
2100
2101
2102
2103
2104
2105
2106
2107
2108
2109
2110
2111
2112
....
2225
2226
2227
2228
2229
2230
2231
2232
2233
2234
2235
2236
2237
2238
2239
){
  int rc = SQLITE_OK;

  int isIgnoreEmpty =  (pCsr->pFilter->flags & FTS3_SEGMENT_IGNORE_EMPTY);
  int isRequirePos =   (pCsr->pFilter->flags & FTS3_SEGMENT_REQUIRE_POS);
  int isColFilter =    (pCsr->pFilter->flags & FTS3_SEGMENT_COLUMN_FILTER);
  int isPrefix =       (pCsr->pFilter->flags & FTS3_SEGMENT_PREFIX);
  int isScan =         (pCsr->pFilter->flags & FTS3_SEGMENT_SCAN);

  Fts3SegReader **apSegment = pCsr->apSegment;
  int nSegment = pCsr->nSegment;
  Fts3SegFilter *pFilter = pCsr->pFilter;

  if( pCsr->nSegment==0 ) return SQLITE_OK;

................................................................................
    /* If this is a prefix-search, and if the term that apSegment[0] points
    ** to does not share a suffix with pFilter->zTerm/nTerm, then all 
    ** required callbacks have been made. In this case exit early.
    **
    ** Similarly, if this is a search for an exact match, and the first term
    ** of segment apSegment[0] is not a match, exit early.
    */
    if( pFilter->zTerm && !isScan ){
      if( pCsr->nTerm<pFilter->nTerm 
       || (!isPrefix && pCsr->nTerm>pFilter->nTerm)
       || memcmp(pCsr->zTerm, pFilter->zTerm, pFilter->nTerm) 
      ){
        break;
      }
    }
................................................................................
  int rc;                         /* Return code */
  int iIdx;                       /* Index of new segment */
  int iNewLevel = 0;              /* Level to create new segment at */
  SegmentWriter *pWriter = 0;     /* Used to write the new, merged, segment */
  Fts3SegFilter filter;           /* Segment term filter condition */
  Fts3SegReaderCursor csr;        /* Cursor to iterate through level(s) */

  rc = sqlite3Fts3SegReaderCursor(p, iLevel, 0, 0, 1, 0, &csr);
  if( rc!=SQLITE_OK || csr.nSegment==0 ) goto finished;

  if( iLevel==FTS3_SEGCURSOR_ALL ){
    /* This call is to merge all segments in the database to a single
    ** segment. The level of the new segment is equal to the the numerically 
    ** greatest segment level currently present in the database. The index
    ** of the new segment is always 0.  */

Changes to test/fts3aux1.test.

51
52
53
54
55
56
57
58












































































































































































































































































59
  INSERT INTO t1 SELECT * FROM t1;
  INSERT INTO t1 SELECT * FROM t1;
  INSERT INTO t1 SELECT * FROM t1;
  INSERT INTO t1 SELECT * FROM t1;
  INSERT INTO t1 SELECT * FROM t1;
  SELECT * FROM terms;
} {a 256 1024    b 256 768}













































































































































































































































































finish_test








>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>

51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
206
207
208
209
210
211
212
213
214
215
216
217
218
219
220
221
222
223
224
225
226
227
228
229
230
231
232
233
234
235
236
237
238
239
240
241
242
243
244
245
246
247
248
249
250
251
252
253
254
255
256
257
258
259
260
261
262
263
264
265
266
267
268
269
270
271
272
273
274
275
276
277
278
279
280
281
282
283
284
285
286
287
288
289
290
291
292
293
294
295
296
297
298
299
300
301
302
303
304
305
306
307
308
309
310
311
312
313
314
315
316
317
318
319
320
321
322
323
324
325
326
327
  INSERT INTO t1 SELECT * FROM t1;
  INSERT INTO t1 SELECT * FROM t1;
  INSERT INTO t1 SELECT * FROM t1;
  INSERT INTO t1 SELECT * FROM t1;
  INSERT INTO t1 SELECT * FROM t1;
  SELECT * FROM terms;
} {a 256 1024    b 256 768}

#-------------------------------------------------------------------------
# The following tests verify that the fts4aux module uses the full-text
# index to reduce the number of rows scanned in the following circumstances:
#
#   * when there is equality comparison against the term column using the 
#     BINARY collating sequence. 
#
#   * when there is a range constraint on the term column using the BINARY 
#     collating sequence. 
#
# And also uses the full-text index to optimize ORDER BY clauses of the 
# form "ORDER BY term ASC" or equivalent.
#
# Test organization is:
#
#   fts3aux1-2.1.*: equality constraints.
#   fts3aux1-2.2.*: range constraints.
#   fts3aux1-2.3.*: ORDER BY optimization.
# 

do_execsql_test 2.0 {
  DROP TABLE t1;
  DROP TABLE terms;

  CREATE VIRTUAL TABLE x1 USING fts4(x);
  INSERT INTO x1(x1) VALUES('nodesize=24');
  CREATE VIRTUAL TABLE terms USING fts4aux(x1);

  INSERT INTO x1 VALUES('braes brag bragged bragger bragging');
  INSERT INTO x1 VALUES('brags braid braided braiding braids');
  INSERT INTO x1 VALUES('brain brainchild brained braining brains');
  INSERT INTO x1 VALUES('brainstem brainstems brainstorm brainstorms'); 
}

proc rec {varname x} {
  global $varname
  incr $varname
  return 1
}
db func rec rec

# Use EQP to show that the WHERE expression "term='braid'" uses a different
# index number (1) than "+term='braid'" (0).
#
do_execsql_test 2.1.1.1 {
  EXPLAIN QUERY PLAN SELECT * FROM terms WHERE term='braid'
} { 0 0 0 {SCAN TABLE terms VIRTUAL TABLE INDEX 1: (~0 rows)} }
do_execsql_test 2.1.1.2 {
  EXPLAIN QUERY PLAN SELECT * FROM terms WHERE +term='braid'
} {0 0 0 {SCAN TABLE terms VIRTUAL TABLE INDEX 0: (~0 rows)}}

# Now show that using "term='braid'" means the virtual table returns
# only 1 row to SQLite, but "+term='braid'" means all 19 are returned.
#
do_test 2.1.2.1 {
  set cnt 0
  execsql { SELECT * FROM terms WHERE rec('cnt', term) AND term='braid' }
  set cnt
} {1}
do_test 2.1.2.2 {
  set cnt 0
  execsql { SELECT * FROM terms WHERE rec('cnt', term) AND +term='braid' }
  set cnt
} {19}

# Similar to the test immediately above, but using a term ("breakfast") that 
# is not featured in the dataset.
#
do_test 2.1.3.1 {
  set cnt 0
  execsql { SELECT * FROM terms WHERE rec('cnt', term) AND term='breakfast' }
  set cnt
} {0}
do_test 2.1.3.2 {
  set cnt 0
  execsql { SELECT * FROM terms WHERE rec('cnt', term) AND +term='breakfast' }
  set cnt
} {19}

do_execsql_test 2.1.4.1 { SELECT * FROM terms WHERE term='braid'  } {braid 1 1}
do_execsql_test 2.1.4.2 { SELECT * FROM terms WHERE +term='braid' } {braid 1 1}
do_execsql_test 2.1.4.3 { SELECT * FROM terms WHERE term='breakfast'  } {}
do_execsql_test 2.1.4.4 { SELECT * FROM terms WHERE +term='breakfast' } {}

do_execsql_test 2.1.4.5 { SELECT * FROM terms WHERE term='cba'  } {}
do_execsql_test 2.1.4.6 { SELECT * FROM terms WHERE +term='cba' } {}
do_execsql_test 2.1.4.7 { SELECT * FROM terms WHERE term='abc'  } {}
do_execsql_test 2.1.4.8 { SELECT * FROM terms WHERE +term='abc' } {}

do_execsql_test 2.2.1.1 {
  EXPLAIN QUERY PLAN SELECT * FROM terms WHERE term>'brain'
} { 0 0 0 {SCAN TABLE terms VIRTUAL TABLE INDEX 2: (~0 rows)} }
do_execsql_test 2.2.1.2 {
  EXPLAIN QUERY PLAN SELECT * FROM terms WHERE +term>'brain'
} { 0 0 0 {SCAN TABLE terms VIRTUAL TABLE INDEX 0: (~0 rows)} }

do_execsql_test 2.2.1.3 {
  EXPLAIN QUERY PLAN SELECT * FROM terms WHERE term<'brain'
} { 0 0 0 {SCAN TABLE terms VIRTUAL TABLE INDEX 4: (~0 rows)} }
do_execsql_test 2.2.1.4 {
  EXPLAIN QUERY PLAN SELECT * FROM terms WHERE +term<'brain'
} { 0 0 0 {SCAN TABLE terms VIRTUAL TABLE INDEX 0: (~0 rows)} }

do_execsql_test 2.2.1.5 {
  EXPLAIN QUERY PLAN SELECT * FROM terms WHERE term BETWEEN 'brags' AND 'brain'
} { 0 0 0 {SCAN TABLE terms VIRTUAL TABLE INDEX 6: (~0 rows)} }
do_execsql_test 2.2.1.6 {
  EXPLAIN QUERY PLAN SELECT * FROM terms WHERE +term BETWEEN 'brags' AND 'brain'
} { 0 0 0 {SCAN TABLE terms VIRTUAL TABLE INDEX 0: (~0 rows)} }

do_test 2.2.2.1 {
  set cnt 0
  execsql { SELECT * FROM terms WHERE rec('cnt', term) AND term>'brain' }
  set cnt
} {9}
do_test 2.2.2.2 {
  set cnt 0
  execsql { SELECT * FROM terms WHERE rec('cnt', term) AND +term>'brain' }
  set cnt
} {19}
do_execsql_test 2.2.2.3 {
  SELECT * FROM terms WHERE rec('cnt', term) AND term>'brain'
} {
  brainchild 1 1 brained 1 1 braining 1 1 brains 1 1 
  brainstem 1 1 brainstems 1 1 brainstorm 1 1 brainstorms 1 1
}
do_execsql_test 2.2.2.4 {
  SELECT * FROM terms WHERE rec('cnt', term) AND +term>'brain'
} {
  brainchild 1 1 brained 1 1 braining 1 1 brains 1 1 
  brainstem 1 1 brainstems 1 1 brainstorm 1 1 brainstorms 1 1
}
do_execsql_test 2.2.2.5 {
  SELECT * FROM terms WHERE rec('cnt', term) AND term>='brain'
} {
  brain 1 1
  brainchild 1 1 brained 1 1 braining 1 1 brains 1 1 
  brainstem 1 1 brainstems 1 1 brainstorm 1 1 brainstorms 1 1
}
do_execsql_test 2.2.2.6 {
  SELECT * FROM terms WHERE rec('cnt', term) AND +term>='brain'
} {
  brain 1 1
  brainchild 1 1 brained 1 1 braining 1 1 brains 1 1 
  brainstem 1 1 brainstems 1 1 brainstorm 1 1 brainstorms 1 1
}

do_execsql_test 2.2.2.7 {
  SELECT * FROM terms WHERE term>='abc'
} {
  braes 1 1 brag 1 1 bragged 1 1 bragger 1 1 
  bragging 1 1 brags 1 1 braid 1 1 braided 1 1 
  braiding 1 1 braids 1 1 brain 1 1 brainchild 1 1 
  brained 1 1 braining 1 1 brains 1 1 brainstem 1 1 
  brainstems 1 1 brainstorm 1 1 brainstorms 1 1
}
do_execsql_test 2.2.2.8 {
  SELECT * FROM terms WHERE +term>='abc'
} {
  braes 1 1 brag 1 1 bragged 1 1 bragger 1 1 
  bragging 1 1 brags 1 1 braid 1 1 braided 1 1 
  braiding 1 1 braids 1 1 brain 1 1 brainchild 1 1 
  brained 1 1 braining 1 1 brains 1 1 brainstem 1 1 
  brainstems 1 1 brainstorm 1 1 brainstorms 1 1
}

do_execsql_test 2.2.2.9 {
  SELECT * FROM terms WHERE term>='brainstorms'
} {brainstorms 1 1}
do_execsql_test 2.2.2.10 {
  SELECT * FROM terms WHERE term>='brainstorms'
} {brainstorms 1 1}
do_execsql_test 2.2.2.11 { SELECT * FROM terms WHERE term>'brainstorms' } {}
do_execsql_test 2.2.2.12 { SELECT * FROM terms WHERE term>'brainstorms' } {}

do_execsql_test 2.2.2.13 { SELECT * FROM terms WHERE term>'cba' } {}
do_execsql_test 2.2.2.14 { SELECT * FROM terms WHERE term>'cba' } {}

do_test 2.2.3.1 {
  set cnt 0
  execsql { SELECT * FROM terms WHERE rec('cnt', term) AND term<'brain' }
  set cnt
} {11}
do_test 2.2.3.2 {
  set cnt 0
  execsql { SELECT * FROM terms WHERE rec('cnt', term) AND +term<'brain' }
  set cnt
} {19}
do_execsql_test 2.2.3.3 {
  SELECT * FROM terms WHERE rec('cnt', term) AND term<'brain'
} {
  braes 1 1 brag 1 1 bragged 1 1 bragger 1 1 bragging 1 1 
  brags 1 1 braid 1 1 braided 1 1 braiding 1 1 braids 1 1
}
do_execsql_test 2.2.3.4 {
  SELECT * FROM terms WHERE rec('cnt', term) AND +term<'brain'
} {
  braes 1 1 brag 1 1 bragged 1 1 bragger 1 1 bragging 1 1 
  brags 1 1 braid 1 1 braided 1 1 braiding 1 1 braids 1 1
}
do_execsql_test 2.2.3.5 {
  SELECT * FROM terms WHERE rec('cnt', term) AND term<='brain'
} {
  braes 1 1 brag 1 1 bragged 1 1 bragger 1 1 bragging 1 1 
  brags 1 1 braid 1 1 braided 1 1 braiding 1 1 braids 1 1
  brain 1 1
}
do_execsql_test 2.2.3.6 {
  SELECT * FROM terms WHERE rec('cnt', term) AND +term<='brain'
} {
  braes 1 1 brag 1 1 bragged 1 1 bragger 1 1 bragging 1 1 
  brags 1 1 braid 1 1 braided 1 1 braiding 1 1 braids 1 1
  brain 1 1
}

do_test 2.2.4.1 {
  set cnt 0
  execsql { 
    SELECT * FROM terms 
    WHERE rec('cnt', term) AND term BETWEEN 'brags' AND 'brain' 
  }
  set cnt
} {6}
do_test 2.2.4.2 {
  set cnt 0
  execsql { 
    SELECT * FROM terms 
    WHERE rec('cnt', term) AND +term BETWEEN 'brags' AND 'brain' 
  }
  set cnt
} {19}
do_execsql_test 2.2.4.3 {
  SELECT * FROM terms 
  WHERE rec('cnt', term) AND term BETWEEN 'brags' AND 'brain' 
} {
  brags 1 1 braid 1 1 braided 1 1 braiding 1 1 braids 1 1 brain 1 1 
}
do_execsql_test 2.2.4.4 {
  SELECT * FROM terms 
  WHERE rec('cnt', term) AND +term BETWEEN 'brags' AND 'brain' 
} {
  brags 1 1 braid 1 1 braided 1 1 braiding 1 1 braids 1 1 brain 1 1 
}
do_execsql_test 2.2.4.5 {
  SELECT * FROM terms 
  WHERE rec('cnt', term) AND term > 'brags' AND term < 'brain' 
} {
  braid 1 1 braided 1 1 braiding 1 1 braids 1 1
}
do_execsql_test 2.2.4.6 {
  SELECT * FROM terms 
  WHERE rec('cnt', term) AND +term > 'brags' AND +term < 'brain' 
} {
  braid 1 1 braided 1 1 braiding 1 1 braids 1 1
}

do_execsql_test 2.3.1.1 {
  EXPLAIN QUERY PLAN SELECT * FROM terms ORDER BY term ASC;
} {
  0 0 0 {SCAN TABLE terms VIRTUAL TABLE INDEX 0: (~0 rows)} 
}
do_execsql_test 2.3.1.2 {
  EXPLAIN QUERY PLAN SELECT * FROM terms ORDER BY term DESC;
} {
  0 0 0 {SCAN TABLE terms VIRTUAL TABLE INDEX 0: (~0 rows)} 
  0 0 0 {USE TEMP B-TREE FOR ORDER BY}
}

finish_test