4 ** The author disclaims copyright to this source code. In place of
5 ** a legal notice, here is a blessing:
7 ** May you do good and not evil.
8 ** May you find forgiveness for yourself and forgive others.
9 ** May you share freely, never taking more than you give.
11 ******************************************************************************
13 ** This is an SQLite module implementing full-text search.
17 ** The code in this file is only compiled if:
19 ** * The FTS3 module is being built as an extension
20 ** (in which case SQLITE_CORE is not defined), or
22 ** * The FTS3 module is being built into the core of
23 ** SQLite (in which case SQLITE_ENABLE_FTS3 is defined).
26 /* The full-text index is stored in a series of b+tree (-like)
27 ** structures called segments which map terms to doclists. The
28 ** structures are like b+trees in layout, but are constructed from the
29 ** bottom up in optimal fashion and are not updatable. Since trees
30 ** are built from the bottom up, things will be described from the
35 ** The basic unit of encoding is a variable-length integer called a
36 ** varint. We encode variable-length integers in little-endian order
37 ** using seven bits * per byte as follows:
40 ** A = 0xxxxxxx 7 bits of data and one flag bit
41 ** B = 1xxxxxxx 7 bits of data and one flag bit
48 ** This is similar in concept to how sqlite encodes "varints" but
49 ** the encoding is not the same. SQLite varints are big-endian
50 ** are are limited to 9 bytes in length whereas FTS3 varints are
51 ** little-endian and can be up to 10 bytes in length (in theory).
60 **** Document lists ****
61 ** A doclist (document list) holds a docid-sorted list of hits for a
62 ** given term. Doclists hold docids and associated token positions.
63 ** A docid is the unique integer identifier for a single document.
64 ** A position is the index of a word within the document. The first
65 ** word of the document has a position of 0.
67 ** FTS3 used to optionally store character offsets using a compile-time
68 ** option. But that functionality is no longer supported.
70 ** A doclist is stored like this:
73 ** varint docid; (delta from previous doclist)
74 ** array { (position list for column 0)
75 ** varint position; (2 more than the delta from previous position)
78 ** varint POS_COLUMN; (marks start of position list for new column)
79 ** varint column; (index of new column)
81 ** varint position; (2 more than the delta from previous position)
84 ** varint POS_END; (marks end of positions for this document.
87 ** Here, array { X } means zero or more occurrences of X, adjacent in
88 ** memory. A "position" is an index of a token in the token stream
89 ** generated by the tokenizer. Note that POS_END and POS_COLUMN occur
90 ** in the same logical place as the position element, and act as sentinals
91 ** ending a position list array. POS_END is 0. POS_COLUMN is 1.
92 ** The positions numbers are not stored literally but rather as two more
93 ** than the difference from the prior position, or the just the position plus
94 ** 2 for the first position. Example:
96 ** label: A B C D E F G H I J K
97 ** value: 123 5 9 1 1 14 35 0 234 72 0
99 ** The 123 value is the first docid. For column zero in this document
100 ** there are two matches at positions 3 and 10 (5-2 and 9-2+3). The 1
101 ** at D signals the start of a new column; the 1 at E indicates that the
102 ** new column is column number 1. There are two positions at 12 and 45
103 ** (14-2 and 35-2+12). The 0 at H indicate the end-of-document. The
104 ** 234 at I is the delta to next docid (357). It has one position 70
105 ** (72-2) and then terminates with the 0 at K.
107 ** A "position-list" is the list of positions for multiple columns for
108 ** a single docid. A "column-list" is the set of positions for a single
109 ** column. Hence, a position-list consists of one or more column-lists,
110 ** a document record consists of a docid followed by a position-list and
111 ** a doclist consists of one or more document records.
113 ** A bare doclist omits the position information, becoming an
114 ** array of varint-encoded docids.
116 **** Segment leaf nodes ****
117 ** Segment leaf nodes store terms and doclists, ordered by term. Leaf
118 ** nodes are written using LeafWriter, and read using LeafReader (to
119 ** iterate through a single leaf node's data) and LeavesReader (to
120 ** iterate through a segment's entire leaf layer). Leaf nodes have
123 ** varint iHeight; (height from leaf level, always 0)
124 ** varint nTerm; (length of first term)
125 ** char pTerm[nTerm]; (content of first term)
126 ** varint nDoclist; (length of term's associated doclist)
127 ** char pDoclist[nDoclist]; (content of doclist)
129 ** (further terms are delta-encoded)
130 ** varint nPrefix; (length of prefix shared with previous term)
131 ** varint nSuffix; (length of unshared suffix)
132 ** char pTermSuffix[nSuffix];(unshared suffix of next term)
133 ** varint nDoclist; (length of term's associated doclist)
134 ** char pDoclist[nDoclist]; (content of doclist)
137 ** Here, array { X } means zero or more occurrences of X, adjacent in
140 ** Leaf nodes are broken into blocks which are stored contiguously in
141 ** the %_segments table in sorted order. This means that when the end
142 ** of a node is reached, the next term is in the node with the next
145 ** New data is spilled to a new leaf node when the current node
146 ** exceeds LEAF_MAX bytes (default 2048). New data which itself is
147 ** larger than STANDALONE_MIN (default 1024) is placed in a standalone
148 ** node (a leaf node with a single term and doclist). The goal of
149 ** these settings is to pack together groups of small doclists while
150 ** making it efficient to directly access large doclists. The
151 ** assumption is that large doclists represent terms which are more
152 ** likely to be query targets.
154 ** TODO(shess) It may be useful for blocking decisions to be more
155 ** dynamic. For instance, it may make more sense to have a 2.5k leaf
156 ** node rather than splitting into 2k and .5k nodes. My intuition is
157 ** that this might extend through 2x or 4x the pagesize.
160 **** Segment interior nodes ****
161 ** Segment interior nodes store blockids for subtree nodes and terms
162 ** to describe what data is stored by the each subtree. Interior
163 ** nodes are written using InteriorWriter, and read using
164 ** InteriorReader. InteriorWriters are created as needed when
165 ** SegmentWriter creates new leaf nodes, or when an interior node
166 ** itself grows too big and must be split. The format of interior
169 ** varint iHeight; (height from leaf level, always >0)
170 ** varint iBlockid; (block id of node's leftmost subtree)
172 ** varint nTerm; (length of first term)
173 ** char pTerm[nTerm]; (content of first term)
175 ** (further terms are delta-encoded)
176 ** varint nPrefix; (length of shared prefix with previous term)
177 ** varint nSuffix; (length of unshared suffix)
178 ** char pTermSuffix[nSuffix]; (unshared suffix of next term)
182 ** Here, optional { X } means an optional element, while array { X }
183 ** means zero or more occurrences of X, adjacent in memory.
185 ** An interior node encodes n terms separating n+1 subtrees. The
186 ** subtree blocks are contiguous, so only the first subtree's blockid
187 ** is encoded. The subtree at iBlockid will contain all terms less
188 ** than the first term encoded (or all terms if no term is encoded).
189 ** Otherwise, for terms greater than or equal to pTerm[i] but less
190 ** than pTerm[i+1], the subtree for that term will be rooted at
191 ** iBlockid+i. Interior nodes only store enough term data to
192 ** distinguish adjacent children (if the rightmost term of the left
193 ** child is "something", and the leftmost term of the right child is
194 ** "wicked", only "w" is stored).
196 ** New data is spilled to a new interior node at the same height when
197 ** the current node exceeds INTERIOR_MAX bytes (default 2048).
198 ** INTERIOR_MIN_TERMS (default 7) keeps large terms from monopolizing
199 ** interior nodes and making the tree too skinny. The interior nodes
200 ** at a given height are naturally tracked by interior nodes at
201 ** height+1, and so on.
204 **** Segment directory ****
205 ** The segment directory in table %_segdir stores meta-information for
206 ** merging and deleting segments, and also the root node of the
209 ** The root node is the top node of the segment's tree after encoding
210 ** the entire segment, restricted to ROOT_MAX bytes (default 1024).
211 ** This could be either a leaf node or an interior node. If the top
212 ** node requires more than ROOT_MAX bytes, it is flushed to %_segments
213 ** and a new root interior node is generated (which should always fit
214 ** within ROOT_MAX because it only needs space for 2 varints, the
215 ** height and the blockid of the previous root).
217 ** The meta-information in the segment directory is:
218 ** level - segment level (see below)
219 ** idx - index within level
220 ** - (level,idx uniquely identify a segment)
221 ** start_block - first leaf node
222 ** leaves_end_block - last leaf node
223 ** end_block - last block (including interior nodes)
224 ** root - contents of root node
226 ** If the root node is a leaf node, then start_block,
227 ** leaves_end_block, and end_block are all 0.
230 **** Segment merging ****
231 ** To amortize update costs, segments are grouped into levels and
232 ** merged in batches. Each increase in level represents exponentially
235 ** New documents (actually, document updates) are tokenized and
236 ** written individually (using LeafWriter) to a level 0 segment, with
237 ** incrementing idx. When idx reaches MERGE_COUNT (default 16), all
238 ** level 0 segments are merged into a single level 1 segment. Level 1
239 ** is populated like level 0, and eventually MERGE_COUNT level 1
240 ** segments are merged to a single level 2 segment (representing
241 ** MERGE_COUNT^2 updates), and so on.
243 ** A segment merge traverses all segments at a given level in
244 ** parallel, performing a straightforward sorted merge. Since segment
245 ** leaf nodes are written in to the %_segments table in order, this
246 ** merge traverses the underlying sqlite disk structures efficiently.
247 ** After the merge, all segment blocks from the merged level are
250 ** MERGE_COUNT controls how often we merge segments. 16 seems to be
251 ** somewhat of a sweet spot for insertion performance. 32 and 64 show
252 ** very similar performance numbers to 16 on insertion, though they're
253 ** a tiny bit slower (perhaps due to more overhead in merge-time
254 ** sorting). 8 is about 20% slower than 16, 4 about 50% slower than
255 ** 16, 2 about 66% slower than 16.
257 ** At query time, high MERGE_COUNT increases the number of segments
258 ** which need to be scanned and merged. For instance, with 100k docs
261 ** MERGE_COUNT segments
267 ** This appears to have only a moderate impact on queries for very
268 ** frequent terms (which are somewhat dominated by segment merge
269 ** costs), and infrequent and non-existent terms still seem to be fast
270 ** even with many segments.
272 ** TODO(shess) That said, it would be nice to have a better query-side
273 ** argument for MERGE_COUNT of 16. Also, it is possible/likely that
274 ** optimizations to things like doclist merging will swing the sweet
279 **** Handling of deletions and updates ****
280 ** Since we're using a segmented structure, with no docid-oriented
281 ** index into the term index, we clearly cannot simply update the term
282 ** index when a document is deleted or updated. For deletions, we
283 ** write an empty doclist (varint(docid) varint(POS_END)), for updates
284 ** we simply write the new doclist. Segment merges overwrite older
285 ** data for a particular docid with newer data, so deletes or updates
286 ** will eventually overtake the earlier data and knock it out. The
287 ** query logic likewise merges doclists so that newer data knocks out
292 #if !defined(SQLITE_CORE) || defined(SQLITE_ENABLE_FTS3)
294 #if defined(SQLITE_ENABLE_FTS3) && !defined(SQLITE_CORE)
295 # define SQLITE_CORE 1
307 # include "sqlite3ext.h"
308 SQLITE_EXTENSION_INIT1
311 static int fts3EvalNext(Fts3Cursor
*pCsr
);
312 static int fts3EvalStart(Fts3Cursor
*pCsr
);
313 static int fts3TermSegReaderCursor(
314 Fts3Cursor
*, const char *, int, int, Fts3MultiSegReader
**);
317 ** Write a 64-bit variable-length integer to memory starting at p[0].
318 ** The length of data written will be between 1 and FTS3_VARINT_MAX bytes.
319 ** The number of bytes written is returned.
321 int sqlite3Fts3PutVarint(char *p
, sqlite_int64 v
){
322 unsigned char *q
= (unsigned char *) p
;
323 sqlite_uint64 vu
= v
;
325 *q
++ = (unsigned char) ((vu
& 0x7f) | 0x80);
328 q
[-1] &= 0x7f; /* turn off high bit in final byte */
329 assert( q
- (unsigned char *)p
<= FTS3_VARINT_MAX
);
330 return (int) (q
- (unsigned char *)p
);
333 #define GETVARINT_STEP(v, ptr, shift, mask1, mask2, var, ret) \
334 v = (v & mask1) | ( (*ptr++) << shift ); \
335 if( (v & mask2)==0 ){ var = v; return ret; }
336 #define GETVARINT_INIT(v, ptr, shift, mask1, mask2, var, ret) \
338 if( (v & mask2)==0 ){ var = v; return ret; }
341 ** Read a 64-bit variable-length integer from memory starting at p[0].
342 ** Return the number of bytes read, or 0 on error.
343 ** The value is stored in *v.
345 int sqlite3Fts3GetVarint(const char *p
, sqlite_int64
*v
){
346 const char *pStart
= p
;
351 GETVARINT_INIT(a
, p
, 0, 0x00, 0x80, *v
, 1);
352 GETVARINT_STEP(a
, p
, 7, 0x7F, 0x4000, *v
, 2);
353 GETVARINT_STEP(a
, p
, 14, 0x3FFF, 0x200000, *v
, 3);
354 GETVARINT_STEP(a
, p
, 21, 0x1FFFFF, 0x10000000, *v
, 4);
355 b
= (a
& 0x0FFFFFFF );
357 for(shift
=28; shift
<=63; shift
+=7){
359 b
+= (c
&0x7F) << shift
;
360 if( (c
& 0x80)==0 ) break;
363 return (int)(p
- pStart
);
367 ** Similar to sqlite3Fts3GetVarint(), except that the output is truncated to a
368 ** 32-bit integer before it is returned.
370 int sqlite3Fts3GetVarint32(const char *p
, int *pi
){
373 #ifndef fts3GetVarint32
374 GETVARINT_INIT(a
, p
, 0, 0x00, 0x80, *pi
, 1);
380 GETVARINT_STEP(a
, p
, 7, 0x7F, 0x4000, *pi
, 2);
381 GETVARINT_STEP(a
, p
, 14, 0x3FFF, 0x200000, *pi
, 3);
382 GETVARINT_STEP(a
, p
, 21, 0x1FFFFF, 0x10000000, *pi
, 4);
383 a
= (a
& 0x0FFFFFFF );
384 *pi
= (int)(a
| ((u32
)(*p
& 0x0F) << 28));
389 ** Return the number of bytes required to encode v as a varint
391 int sqlite3Fts3VarintLen(sqlite3_uint64 v
){
401 ** Convert an SQL-style quoted string into a normal string by removing
402 ** the quote characters. The conversion is done in-place. If the
403 ** input does not begin with a quote character, then this routine
414 void sqlite3Fts3Dequote(char *z
){
415 char quote
; /* Quote character (if any ) */
418 if( quote
=='[' || quote
=='\'' || quote
=='"' || quote
=='`' ){
419 int iIn
= 1; /* Index of next byte to read from input */
420 int iOut
= 0; /* Index of next byte to write to output */
422 /* If the first byte was a '[', then the close-quote character is a ']' */
423 if( quote
=='[' ) quote
= ']';
425 while( ALWAYS(z
[iIn
]) ){
427 if( z
[iIn
+1]!=quote
) break;
431 z
[iOut
++] = z
[iIn
++];
439 ** Read a single varint from the doclist at *pp and advance *pp to point
440 ** to the first byte past the end of the varint. Add the value of the varint
443 static void fts3GetDeltaVarint(char **pp
, sqlite3_int64
*pVal
){
445 *pp
+= sqlite3Fts3GetVarint(*pp
, &iVal
);
450 ** When this function is called, *pp points to the first byte following a
451 ** varint that is part of a doclist (or position-list, or any other list
452 ** of varints). This function moves *pp to point to the start of that varint,
453 ** and sets *pVal by the varint value.
455 ** Argument pStart points to the first byte of the doclist that the
456 ** varint is part of.
458 static void fts3GetReverseVarint(
466 /* Pointer p now points at the first byte past the varint we are
467 ** interested in. So, unless the doclist is corrupt, the 0x80 bit is
468 ** clear on character p[-1]. */
469 for(p
= (*pp
)-2; p
>=pStart
&& *p
&0x80; p
--);
473 sqlite3Fts3GetVarint(p
, &iVal
);
478 ** The xDisconnect() virtual table method.
480 static int fts3DisconnectMethod(sqlite3_vtab
*pVtab
){
481 Fts3Table
*p
= (Fts3Table
*)pVtab
;
484 assert( p
->nPendingData
==0 );
485 assert( p
->pSegments
==0 );
487 /* Free any prepared statements held */
488 for(i
=0; i
<SizeofArray(p
->aStmt
); i
++){
489 sqlite3_finalize(p
->aStmt
[i
]);
491 sqlite3_free(p
->zSegmentsTbl
);
492 sqlite3_free(p
->zReadExprlist
);
493 sqlite3_free(p
->zWriteExprlist
);
494 sqlite3_free(p
->zContentTbl
);
495 sqlite3_free(p
->zLanguageid
);
497 /* Invoke the tokenizer destructor to free the tokenizer. */
498 p
->pTokenizer
->pModule
->xDestroy(p
->pTokenizer
);
505 ** Construct one or more SQL statements from the format string given
506 ** and then evaluate those statements. The success code is written
509 ** If *pRc is initially non-zero then this routine is a no-op.
511 static void fts3DbExec(
512 int *pRc
, /* Success code */
513 sqlite3
*db
, /* Database in which to run SQL */
514 const char *zFormat
, /* Format string for SQL */
515 ... /* Arguments to the format string */
520 va_start(ap
, zFormat
);
521 zSql
= sqlite3_vmprintf(zFormat
, ap
);
526 *pRc
= sqlite3_exec(db
, zSql
, 0, 0, 0);
532 ** The xDestroy() virtual table method.
534 static int fts3DestroyMethod(sqlite3_vtab
*pVtab
){
535 Fts3Table
*p
= (Fts3Table
*)pVtab
;
536 int rc
= SQLITE_OK
; /* Return code */
537 const char *zDb
= p
->zDb
; /* Name of database (e.g. "main", "temp") */
538 sqlite3
*db
= p
->db
; /* Database handle */
540 /* Drop the shadow tables */
541 if( p
->zContentTbl
==0 ){
542 fts3DbExec(&rc
, db
, "DROP TABLE IF EXISTS %Q.'%q_content'", zDb
, p
->zName
);
544 fts3DbExec(&rc
, db
, "DROP TABLE IF EXISTS %Q.'%q_segments'", zDb
,p
->zName
);
545 fts3DbExec(&rc
, db
, "DROP TABLE IF EXISTS %Q.'%q_segdir'", zDb
, p
->zName
);
546 fts3DbExec(&rc
, db
, "DROP TABLE IF EXISTS %Q.'%q_docsize'", zDb
, p
->zName
);
547 fts3DbExec(&rc
, db
, "DROP TABLE IF EXISTS %Q.'%q_stat'", zDb
, p
->zName
);
549 /* If everything has worked, invoke fts3DisconnectMethod() to free the
550 ** memory associated with the Fts3Table structure and return SQLITE_OK.
551 ** Otherwise, return an SQLite error code.
553 return (rc
==SQLITE_OK
? fts3DisconnectMethod(pVtab
) : rc
);
558 ** Invoke sqlite3_declare_vtab() to declare the schema for the FTS3 table
559 ** passed as the first argument. This is done as part of the xConnect()
560 ** and xCreate() methods.
562 ** If *pRc is non-zero when this function is called, it is a no-op.
563 ** Otherwise, if an error occurs, an SQLite error code is stored in *pRc
566 static void fts3DeclareVtab(int *pRc
, Fts3Table
*p
){
567 if( *pRc
==SQLITE_OK
){
568 int i
; /* Iterator variable */
569 int rc
; /* Return code */
570 char *zSql
; /* SQL statement passed to declare_vtab() */
571 char *zCols
; /* List of user defined columns */
572 const char *zLanguageid
;
574 zLanguageid
= (p
->zLanguageid
? p
->zLanguageid
: "__langid");
575 sqlite3_vtab_config(p
->db
, SQLITE_VTAB_CONSTRAINT_SUPPORT
, 1);
577 /* Create a list of user columns for the virtual table */
578 zCols
= sqlite3_mprintf("%Q, ", p
->azColumn
[0]);
579 for(i
=1; zCols
&& i
<p
->nColumn
; i
++){
580 zCols
= sqlite3_mprintf("%z%Q, ", zCols
, p
->azColumn
[i
]);
583 /* Create the whole "CREATE TABLE" statement to pass to SQLite */
584 zSql
= sqlite3_mprintf(
585 "CREATE TABLE x(%s %Q HIDDEN, docid HIDDEN, %Q HIDDEN)",
586 zCols
, p
->zName
, zLanguageid
588 if( !zCols
|| !zSql
){
591 rc
= sqlite3_declare_vtab(p
->db
, zSql
);
601 ** Create the %_stat table if it does not already exist.
603 void sqlite3Fts3CreateStatTable(int *pRc
, Fts3Table
*p
){
604 fts3DbExec(pRc
, p
->db
,
605 "CREATE TABLE IF NOT EXISTS %Q.'%q_stat'"
606 "(id INTEGER PRIMARY KEY, value BLOB);",
609 if( (*pRc
)==SQLITE_OK
) p
->bHasStat
= 1;
613 ** Create the backing store tables (%_content, %_segments and %_segdir)
614 ** required by the FTS3 table passed as the only argument. This is done
615 ** as part of the vtab xCreate() method.
617 ** If the p->bHasDocsize boolean is true (indicating that this is an
618 ** FTS4 table, not an FTS3 table) then also create the %_docsize and
619 ** %_stat tables required by FTS4.
621 static int fts3CreateTables(Fts3Table
*p
){
622 int rc
= SQLITE_OK
; /* Return code */
623 int i
; /* Iterator variable */
624 sqlite3
*db
= p
->db
; /* The database connection */
626 if( p
->zContentTbl
==0 ){
627 const char *zLanguageid
= p
->zLanguageid
;
628 char *zContentCols
; /* Columns of %_content table */
630 /* Create a list of user columns for the content table */
631 zContentCols
= sqlite3_mprintf("docid INTEGER PRIMARY KEY");
632 for(i
=0; zContentCols
&& i
<p
->nColumn
; i
++){
633 char *z
= p
->azColumn
[i
];
634 zContentCols
= sqlite3_mprintf("%z, 'c%d%q'", zContentCols
, i
, z
);
636 if( zLanguageid
&& zContentCols
){
637 zContentCols
= sqlite3_mprintf("%z, langid", zContentCols
, zLanguageid
);
639 if( zContentCols
==0 ) rc
= SQLITE_NOMEM
;
641 /* Create the content table */
643 "CREATE TABLE %Q.'%q_content'(%s)",
644 p
->zDb
, p
->zName
, zContentCols
646 sqlite3_free(zContentCols
);
649 /* Create other tables */
651 "CREATE TABLE %Q.'%q_segments'(blockid INTEGER PRIMARY KEY, block BLOB);",
655 "CREATE TABLE %Q.'%q_segdir'("
658 "start_block INTEGER,"
659 "leaves_end_block INTEGER,"
662 "PRIMARY KEY(level, idx)"
666 if( p
->bHasDocsize
){
668 "CREATE TABLE %Q.'%q_docsize'(docid INTEGER PRIMARY KEY, size BLOB);",
672 assert( p
->bHasStat
==p
->bFts4
);
674 sqlite3Fts3CreateStatTable(&rc
, p
);
680 ** Store the current database page-size in bytes in p->nPgsz.
682 ** If *pRc is non-zero when this function is called, it is a no-op.
683 ** Otherwise, if an error occurs, an SQLite error code is stored in *pRc
686 static void fts3DatabasePageSize(int *pRc
, Fts3Table
*p
){
687 if( *pRc
==SQLITE_OK
){
688 int rc
; /* Return code */
689 char *zSql
; /* SQL text "PRAGMA %Q.page_size" */
690 sqlite3_stmt
*pStmt
; /* Compiled "PRAGMA %Q.page_size" statement */
692 zSql
= sqlite3_mprintf("PRAGMA %Q.page_size", p
->zDb
);
696 rc
= sqlite3_prepare(p
->db
, zSql
, -1, &pStmt
, 0);
699 p
->nPgsz
= sqlite3_column_int(pStmt
, 0);
700 rc
= sqlite3_finalize(pStmt
);
701 }else if( rc
==SQLITE_AUTH
){
706 assert( p
->nPgsz
>0 || rc
!=SQLITE_OK
);
713 ** "Special" FTS4 arguments are column specifications of the following form:
717 ** There may not be whitespace surrounding the "=" character. The <value>
718 ** term may be quoted, but the <key> may not.
720 static int fts3IsSpecialColumn(
726 const char *zCsr
= z
;
729 if( *zCsr
=='\0' ) return 0;
733 *pnKey
= (int)(zCsr
-z
);
734 zValue
= sqlite3_mprintf("%s", &zCsr
[1]);
736 sqlite3Fts3Dequote(zValue
);
743 ** Append the output of a printf() style formatting to an existing string.
745 static void fts3Appendf(
746 int *pRc
, /* IN/OUT: Error code */
747 char **pz
, /* IN/OUT: Pointer to string buffer */
748 const char *zFormat
, /* Printf format string to append */
749 ... /* Arguments for printf format string */
751 if( *pRc
==SQLITE_OK
){
754 va_start(ap
, zFormat
);
755 z
= sqlite3_vmprintf(zFormat
, ap
);
758 char *z2
= sqlite3_mprintf("%s%s", *pz
, z
);
762 if( z
==0 ) *pRc
= SQLITE_NOMEM
;
769 ** Return a copy of input string zInput enclosed in double-quotes (") and
770 ** with all double quote characters escaped. For example:
772 ** fts3QuoteId("un \"zip\"") -> "un \"\"zip\"\""
774 ** The pointer returned points to memory obtained from sqlite3_malloc(). It
775 ** is the callers responsibility to call sqlite3_free() to release this
778 static char *fts3QuoteId(char const *zInput
){
781 nRet
= 2 + (int)strlen(zInput
)*2 + 1;
782 zRet
= sqlite3_malloc(nRet
);
787 for(i
=0; zInput
[i
]; i
++){
788 if( zInput
[i
]=='"' ) *(z
++) = '"';
798 ** Return a list of comma separated SQL expressions and a FROM clause that
799 ** could be used in a SELECT statement such as the following:
801 ** SELECT <list of expressions> FROM %_content AS x ...
803 ** to return the docid, followed by each column of text data in order
804 ** from left to write. If parameter zFunc is not NULL, then instead of
805 ** being returned directly each column of text data is passed to an SQL
806 ** function named zFunc first. For example, if zFunc is "unzip" and the
807 ** table has the three user-defined columns "a", "b", and "c", the following
808 ** string is returned:
810 ** "docid, unzip(x.'a'), unzip(x.'b'), unzip(x.'c') FROM %_content AS x"
812 ** The pointer returned points to a buffer allocated by sqlite3_malloc(). It
813 ** is the responsibility of the caller to eventually free it.
815 ** If *pRc is not SQLITE_OK when this function is called, it is a no-op (and
816 ** a NULL pointer is returned). Otherwise, if an OOM error is encountered
817 ** by this function, NULL is returned and *pRc is set to SQLITE_NOMEM. If
818 ** no error occurs, *pRc is left unmodified.
820 static char *fts3ReadExprList(Fts3Table
*p
, const char *zFunc
, int *pRc
){
826 if( p
->zContentTbl
==0 ){
830 zFree
= zFunction
= fts3QuoteId(zFunc
);
832 fts3Appendf(pRc
, &zRet
, "docid");
833 for(i
=0; i
<p
->nColumn
; i
++){
834 fts3Appendf(pRc
, &zRet
, ",%s(x.'c%d%q')", zFunction
, i
, p
->azColumn
[i
]);
836 if( p
->zLanguageid
){
837 fts3Appendf(pRc
, &zRet
, ", x.%Q", "langid");
841 fts3Appendf(pRc
, &zRet
, "rowid");
842 for(i
=0; i
<p
->nColumn
; i
++){
843 fts3Appendf(pRc
, &zRet
, ", x.'%q'", p
->azColumn
[i
]);
845 if( p
->zLanguageid
){
846 fts3Appendf(pRc
, &zRet
, ", x.%Q", p
->zLanguageid
);
849 fts3Appendf(pRc
, &zRet
, " FROM '%q'.'%q%s' AS x",
851 (p
->zContentTbl
? p
->zContentTbl
: p
->zName
),
852 (p
->zContentTbl
? "" : "_content")
858 ** Return a list of N comma separated question marks, where N is the number
859 ** of columns in the %_content table (one for the docid plus one for each
860 ** user-defined text column).
862 ** If argument zFunc is not NULL, then all but the first question mark
863 ** is preceded by zFunc and an open bracket, and followed by a closed
864 ** bracket. For example, if zFunc is "zip" and the FTS3 table has three
865 ** user-defined text columns, the following string is returned:
867 ** "?, zip(?), zip(?), zip(?)"
869 ** The pointer returned points to a buffer allocated by sqlite3_malloc(). It
870 ** is the responsibility of the caller to eventually free it.
872 ** If *pRc is not SQLITE_OK when this function is called, it is a no-op (and
873 ** a NULL pointer is returned). Otherwise, if an OOM error is encountered
874 ** by this function, NULL is returned and *pRc is set to SQLITE_NOMEM. If
875 ** no error occurs, *pRc is left unmodified.
877 static char *fts3WriteExprList(Fts3Table
*p
, const char *zFunc
, int *pRc
){
886 zFree
= zFunction
= fts3QuoteId(zFunc
);
888 fts3Appendf(pRc
, &zRet
, "?");
889 for(i
=0; i
<p
->nColumn
; i
++){
890 fts3Appendf(pRc
, &zRet
, ",%s(?)", zFunction
);
892 if( p
->zLanguageid
){
893 fts3Appendf(pRc
, &zRet
, ", ?");
900 ** This function interprets the string at (*pp) as a non-negative integer
901 ** value. It reads the integer and sets *pnOut to the value read, then
902 ** sets *pp to point to the byte immediately following the last byte of
903 ** the integer value.
905 ** Only decimal digits ('0'..'9') may be part of an integer value.
907 ** If *pp does not being with a decimal digit SQLITE_ERROR is returned and
908 ** the output value undefined. Otherwise SQLITE_OK is returned.
910 ** This function is used when parsing the "prefix=" FTS4 parameter.
912 static int fts3GobbleInt(const char **pp
, int *pnOut
){
913 const char *p
; /* Iterator pointer */
914 int nInt
= 0; /* Output value */
916 for(p
=*pp
; p
[0]>='0' && p
[0]<='9'; p
++){
917 nInt
= nInt
* 10 + (p
[0] - '0');
919 if( p
==*pp
) return SQLITE_ERROR
;
926 ** This function is called to allocate an array of Fts3Index structures
927 ** representing the indexes maintained by the current FTS table. FTS tables
928 ** always maintain the main "terms" index, but may also maintain one or
929 ** more "prefix" indexes, depending on the value of the "prefix=" parameter
930 ** (if any) specified as part of the CREATE VIRTUAL TABLE statement.
932 ** Argument zParam is passed the value of the "prefix=" option if one was
933 ** specified, or NULL otherwise.
935 ** If no error occurs, SQLITE_OK is returned and *apIndex set to point to
936 ** the allocated array. *pnIndex is set to the number of elements in the
937 ** array. If an error does occur, an SQLite error code is returned.
939 ** Regardless of whether or not an error is returned, it is the responsibility
940 ** of the caller to call sqlite3_free() on the output array to free it.
942 static int fts3PrefixParameter(
943 const char *zParam
, /* ABC in prefix=ABC parameter to parse */
944 int *pnIndex
, /* OUT: size of *apIndex[] array */
945 struct Fts3Index
**apIndex
/* OUT: Array of indexes for this table */
947 struct Fts3Index
*aIndex
; /* Allocated array */
948 int nIndex
= 1; /* Number of entries in array */
950 if( zParam
&& zParam
[0] ){
953 for(p
=zParam
; *p
; p
++){
954 if( *p
==',' ) nIndex
++;
958 aIndex
= sqlite3_malloc(sizeof(struct Fts3Index
) * nIndex
);
965 memset(aIndex
, 0, sizeof(struct Fts3Index
) * nIndex
);
967 const char *p
= zParam
;
969 for(i
=1; i
<nIndex
; i
++){
971 if( fts3GobbleInt(&p
, &nPrefix
) ) return SQLITE_ERROR
;
972 aIndex
[i
].nPrefix
= nPrefix
;
981 ** This function is called when initializing an FTS4 table that uses the
982 ** content=xxx option. It determines the number of and names of the columns
983 ** of the new FTS4 table.
985 ** The third argument passed to this function is the value passed to the
986 ** config=xxx option (i.e. "xxx"). This function queries the database for
987 ** a table of that name. If found, the output variables are populated
990 ** *pnCol: Set to the number of columns table xxx has,
992 ** *pnStr: Set to the total amount of space required to store a copy
993 ** of each columns name, including the nul-terminator.
995 ** *pazCol: Set to point to an array of *pnCol strings. Each string is
996 ** the name of the corresponding column in table xxx. The array
997 ** and its contents are allocated using a single allocation. It
998 ** is the responsibility of the caller to free this allocation
999 ** by eventually passing the *pazCol value to sqlite3_free().
1001 ** If the table cannot be found, an error code is returned and the output
1002 ** variables are undefined. Or, if an OOM is encountered, SQLITE_NOMEM is
1003 ** returned (and the output variables are undefined).
1005 static int fts3ContentColumns(
1006 sqlite3
*db
, /* Database handle */
1007 const char *zDb
, /* Name of db (i.e. "main", "temp" etc.) */
1008 const char *zTbl
, /* Name of content table */
1009 const char ***pazCol
, /* OUT: Malloc'd array of column names */
1010 int *pnCol
, /* OUT: Size of array *pazCol */
1011 int *pnStr
/* OUT: Bytes of string content */
1013 int rc
= SQLITE_OK
; /* Return code */
1014 char *zSql
; /* "SELECT *" statement on zTbl */
1015 sqlite3_stmt
*pStmt
= 0; /* Compiled version of zSql */
1017 zSql
= sqlite3_mprintf("SELECT * FROM %Q.%Q", zDb
, zTbl
);
1021 rc
= sqlite3_prepare(db
, zSql
, -1, &pStmt
, 0);
1025 if( rc
==SQLITE_OK
){
1026 const char **azCol
; /* Output array */
1027 int nStr
= 0; /* Size of all column names (incl. 0x00) */
1028 int nCol
; /* Number of table columns */
1029 int i
; /* Used to iterate through columns */
1031 /* Loop through the returned columns. Set nStr to the number of bytes of
1032 ** space required to store a copy of each column name, including the
1033 ** nul-terminator byte. */
1034 nCol
= sqlite3_column_count(pStmt
);
1035 for(i
=0; i
<nCol
; i
++){
1036 const char *zCol
= sqlite3_column_name(pStmt
, i
);
1037 nStr
+= (int)strlen(zCol
) + 1;
1040 /* Allocate and populate the array to return. */
1041 azCol
= (const char **)sqlite3_malloc(sizeof(char *) * nCol
+ nStr
);
1045 char *p
= (char *)&azCol
[nCol
];
1046 for(i
=0; i
<nCol
; i
++){
1047 const char *zCol
= sqlite3_column_name(pStmt
, i
);
1048 int n
= (int)strlen(zCol
)+1;
1054 sqlite3_finalize(pStmt
);
1056 /* Set the output variables. */
1066 ** This function is the implementation of both the xConnect and xCreate
1067 ** methods of the FTS3 virtual table.
1069 ** The argv[] array contains the following:
1071 ** argv[0] -> module name ("fts3" or "fts4")
1072 ** argv[1] -> database name
1073 ** argv[2] -> table name
1074 ** argv[...] -> "column name" and other module argument fields.
1076 static int fts3InitVtab(
1077 int isCreate
, /* True for xCreate, false for xConnect */
1078 sqlite3
*db
, /* The SQLite database connection */
1079 void *pAux
, /* Hash table containing tokenizers */
1080 int argc
, /* Number of elements in argv array */
1081 const char * const *argv
, /* xCreate/xConnect argument array */
1082 sqlite3_vtab
**ppVTab
, /* Write the resulting vtab structure here */
1083 char **pzErr
/* Write any error message here */
1085 Fts3Hash
*pHash
= (Fts3Hash
*)pAux
;
1086 Fts3Table
*p
= 0; /* Pointer to allocated vtab */
1087 int rc
= SQLITE_OK
; /* Return code */
1088 int i
; /* Iterator variable */
1089 int nByte
; /* Size of allocation used for *p */
1090 int iCol
; /* Column index */
1091 int nString
= 0; /* Bytes required to hold all column names */
1092 int nCol
= 0; /* Number of columns in the FTS table */
1093 char *zCsr
; /* Space for holding column names */
1094 int nDb
; /* Bytes required to hold database name */
1095 int nName
; /* Bytes required to hold table name */
1096 int isFts4
= (argv
[0][3]=='4'); /* True for FTS4, false for FTS3 */
1097 const char **aCol
; /* Array of column names */
1098 sqlite3_tokenizer
*pTokenizer
= 0; /* Tokenizer for this table */
1100 int nIndex
; /* Size of aIndex[] array */
1101 struct Fts3Index
*aIndex
= 0; /* Array of indexes for this table */
1103 /* The results of parsing supported FTS4 key=value options: */
1104 int bNoDocsize
= 0; /* True to omit %_docsize table */
1105 int bDescIdx
= 0; /* True to store descending indexes */
1106 char *zPrefix
= 0; /* Prefix parameter value (or NULL) */
1107 char *zCompress
= 0; /* compress=? parameter (or NULL) */
1108 char *zUncompress
= 0; /* uncompress=? parameter (or NULL) */
1109 char *zContent
= 0; /* content=? parameter (or NULL) */
1110 char *zLanguageid
= 0; /* languageid=? parameter (or NULL) */
1111 char **azNotindexed
= 0; /* The set of notindexed= columns */
1112 int nNotindexed
= 0; /* Size of azNotindexed[] array */
1114 assert( strlen(argv
[0])==4 );
1115 assert( (sqlite3_strnicmp(argv
[0], "fts4", 4)==0 && isFts4
)
1116 || (sqlite3_strnicmp(argv
[0], "fts3", 4)==0 && !isFts4
)
1119 nDb
= (int)strlen(argv
[1]) + 1;
1120 nName
= (int)strlen(argv
[2]) + 1;
1122 nByte
= sizeof(const char *) * (argc
-2);
1123 aCol
= (const char **)sqlite3_malloc(nByte
);
1125 memset((void*)aCol
, 0, nByte
);
1126 azNotindexed
= (char **)sqlite3_malloc(nByte
);
1129 memset(azNotindexed
, 0, nByte
);
1131 if( !aCol
|| !azNotindexed
){
1136 /* Loop through all of the arguments passed by the user to the FTS3/4
1137 ** module (i.e. all the column names and special arguments). This loop
1138 ** does the following:
1140 ** + Figures out the number of columns the FTSX table will have, and
1141 ** the number of bytes of space that must be allocated to store copies
1142 ** of the column names.
1144 ** + If there is a tokenizer specification included in the arguments,
1145 ** initializes the tokenizer pTokenizer.
1147 for(i
=3; rc
==SQLITE_OK
&& i
<argc
; i
++){
1148 char const *z
= argv
[i
];
1152 /* Check if this is a tokenizer specification */
1155 && 0==sqlite3_strnicmp(z
, "tokenize", 8)
1156 && 0==sqlite3Fts3IsIdChar(z
[8])
1158 rc
= sqlite3Fts3InitTokenizer(pHash
, &z
[9], &pTokenizer
, pzErr
);
1161 /* Check if it is an FTS4 special argument. */
1162 else if( isFts4
&& fts3IsSpecialColumn(z
, &nKey
, &zVal
) ){
1167 { "matchinfo", 9 }, /* 0 -> MATCHINFO */
1168 { "prefix", 6 }, /* 1 -> PREFIX */
1169 { "compress", 8 }, /* 2 -> COMPRESS */
1170 { "uncompress", 10 }, /* 3 -> UNCOMPRESS */
1171 { "order", 5 }, /* 4 -> ORDER */
1172 { "content", 7 }, /* 5 -> CONTENT */
1173 { "languageid", 10 }, /* 6 -> LANGUAGEID */
1174 { "notindexed", 10 } /* 7 -> NOTINDEXED */
1181 for(iOpt
=0; iOpt
<SizeofArray(aFts4Opt
); iOpt
++){
1182 struct Fts4Option
*pOp
= &aFts4Opt
[iOpt
];
1183 if( nKey
==pOp
->nOpt
&& !sqlite3_strnicmp(z
, pOp
->zOpt
, pOp
->nOpt
) ){
1187 if( iOpt
==SizeofArray(aFts4Opt
) ){
1188 *pzErr
= sqlite3_mprintf("unrecognized parameter: %s", z
);
1192 case 0: /* MATCHINFO */
1193 if( strlen(zVal
)!=4 || sqlite3_strnicmp(zVal
, "fts3", 4) ){
1194 *pzErr
= sqlite3_mprintf("unrecognized matchinfo: %s", zVal
);
1200 case 1: /* PREFIX */
1201 sqlite3_free(zPrefix
);
1206 case 2: /* COMPRESS */
1207 sqlite3_free(zCompress
);
1212 case 3: /* UNCOMPRESS */
1213 sqlite3_free(zUncompress
);
1219 if( (strlen(zVal
)!=3 || sqlite3_strnicmp(zVal
, "asc", 3))
1220 && (strlen(zVal
)!=4 || sqlite3_strnicmp(zVal
, "desc", 4))
1222 *pzErr
= sqlite3_mprintf("unrecognized order: %s", zVal
);
1225 bDescIdx
= (zVal
[0]=='d' || zVal
[0]=='D');
1228 case 5: /* CONTENT */
1229 sqlite3_free(zContent
);
1234 case 6: /* LANGUAGEID */
1236 sqlite3_free(zLanguageid
);
1241 case 7: /* NOTINDEXED */
1242 azNotindexed
[nNotindexed
++] = zVal
;
1251 /* Otherwise, the argument is a column name. */
1253 nString
+= (int)(strlen(z
) + 1);
1258 /* If a content=xxx option was specified, the following:
1260 ** 1. Ignore any compress= and uncompress= options.
1262 ** 2. If no column names were specified as part of the CREATE VIRTUAL
1263 ** TABLE statement, use all columns from the content table.
1265 if( rc
==SQLITE_OK
&& zContent
){
1266 sqlite3_free(zCompress
);
1267 sqlite3_free(zUncompress
);
1271 sqlite3_free((void*)aCol
);
1273 rc
= fts3ContentColumns(db
, argv
[1], zContent
, &aCol
, &nCol
, &nString
);
1275 /* If a languageid= option was specified, remove the language id
1276 ** column from the aCol[] array. */
1277 if( rc
==SQLITE_OK
&& zLanguageid
){
1279 for(j
=0; j
<nCol
; j
++){
1280 if( sqlite3_stricmp(zLanguageid
, aCol
[j
])==0 ){
1282 for(k
=j
; k
<nCol
; k
++) aCol
[k
] = aCol
[k
+1];
1290 if( rc
!=SQLITE_OK
) goto fts3_init_out
;
1293 assert( nString
==0 );
1294 aCol
[0] = "content";
1299 if( pTokenizer
==0 ){
1300 rc
= sqlite3Fts3InitTokenizer(pHash
, "simple", &pTokenizer
, pzErr
);
1301 if( rc
!=SQLITE_OK
) goto fts3_init_out
;
1303 assert( pTokenizer
);
1305 rc
= fts3PrefixParameter(zPrefix
, &nIndex
, &aIndex
);
1306 if( rc
==SQLITE_ERROR
){
1308 *pzErr
= sqlite3_mprintf("error parsing prefix parameter: %s", zPrefix
);
1310 if( rc
!=SQLITE_OK
) goto fts3_init_out
;
1312 /* Allocate and populate the Fts3Table structure. */
1313 nByte
= sizeof(Fts3Table
) + /* Fts3Table */
1314 nCol
* sizeof(char *) + /* azColumn */
1315 nIndex
* sizeof(struct Fts3Index
) + /* aIndex */
1316 nCol
* sizeof(u8
) + /* abNotindexed */
1319 nString
; /* Space for azColumn strings */
1320 p
= (Fts3Table
*)sqlite3_malloc(nByte
);
1325 memset(p
, 0, nByte
);
1328 p
->nPendingData
= 0;
1329 p
->azColumn
= (char **)&p
[1];
1330 p
->pTokenizer
= pTokenizer
;
1331 p
->nMaxPendingData
= FTS3_MAX_PENDING_DATA
;
1332 p
->bHasDocsize
= (isFts4
&& bNoDocsize
==0);
1333 p
->bHasStat
= isFts4
;
1335 p
->bDescIdx
= bDescIdx
;
1336 p
->bAutoincrmerge
= 0xff; /* 0xff means setting unknown */
1337 p
->zContentTbl
= zContent
;
1338 p
->zLanguageid
= zLanguageid
;
1341 TESTONLY( p
->inTransaction
= -1 );
1342 TESTONLY( p
->mxSavepoint
= -1 );
1344 p
->aIndex
= (struct Fts3Index
*)&p
->azColumn
[nCol
];
1345 memcpy(p
->aIndex
, aIndex
, sizeof(struct Fts3Index
) * nIndex
);
1347 for(i
=0; i
<nIndex
; i
++){
1348 fts3HashInit(&p
->aIndex
[i
].hPending
, FTS3_HASH_STRING
, 1);
1350 p
->abNotindexed
= (u8
*)&p
->aIndex
[nIndex
];
1352 /* Fill in the zName and zDb fields of the vtab structure. */
1353 zCsr
= (char *)&p
->abNotindexed
[nCol
];
1355 memcpy(zCsr
, argv
[2], nName
);
1358 memcpy(zCsr
, argv
[1], nDb
);
1361 /* Fill in the azColumn array */
1362 for(iCol
=0; iCol
<nCol
; iCol
++){
1365 z
= (char *)sqlite3Fts3NextToken(aCol
[iCol
], &n
);
1368 sqlite3Fts3Dequote(zCsr
);
1369 p
->azColumn
[iCol
] = zCsr
;
1371 assert( zCsr
<= &((char *)p
)[nByte
] );
1374 /* Fill in the abNotindexed array */
1375 for(iCol
=0; iCol
<nCol
; iCol
++){
1376 int n
= (int)strlen(p
->azColumn
[iCol
]);
1377 for(i
=0; i
<nNotindexed
; i
++){
1378 char *zNot
= azNotindexed
[i
];
1379 if( zNot
&& 0==sqlite3_strnicmp(p
->azColumn
[iCol
], zNot
, n
) ){
1380 p
->abNotindexed
[iCol
] = 1;
1382 azNotindexed
[i
] = 0;
1386 for(i
=0; i
<nNotindexed
; i
++){
1387 if( azNotindexed
[i
] ){
1388 *pzErr
= sqlite3_mprintf("no such column: %s", azNotindexed
[i
]);
1393 if( rc
==SQLITE_OK
&& (zCompress
==0)!=(zUncompress
==0) ){
1394 char const *zMiss
= (zCompress
==0 ? "compress" : "uncompress");
1396 *pzErr
= sqlite3_mprintf("missing %s parameter in fts4 constructor", zMiss
);
1398 p
->zReadExprlist
= fts3ReadExprList(p
, zUncompress
, &rc
);
1399 p
->zWriteExprlist
= fts3WriteExprList(p
, zCompress
, &rc
);
1400 if( rc
!=SQLITE_OK
) goto fts3_init_out
;
1402 /* If this is an xCreate call, create the underlying tables in the
1403 ** database. TODO: For xConnect(), it could verify that said tables exist.
1406 rc
= fts3CreateTables(p
);
1409 /* Check to see if a legacy fts3 table has been "upgraded" by the
1410 ** addition of a %_stat table so that it can use incremental merge.
1412 if( !isFts4
&& !isCreate
){
1413 int rc2
= SQLITE_OK
;
1414 fts3DbExec(&rc2
, db
, "SELECT 1 FROM %Q.'%q_stat' WHERE id=2",
1416 if( rc2
==SQLITE_OK
) p
->bHasStat
= 1;
1419 /* Figure out the page-size for the database. This is required in order to
1420 ** estimate the cost of loading large doclists from the database. */
1421 fts3DatabasePageSize(&rc
, p
);
1422 p
->nNodeSize
= p
->nPgsz
-35;
1424 /* Declare the table schema to SQLite. */
1425 fts3DeclareVtab(&rc
, p
);
1428 sqlite3_free(zPrefix
);
1429 sqlite3_free(aIndex
);
1430 sqlite3_free(zCompress
);
1431 sqlite3_free(zUncompress
);
1432 sqlite3_free(zContent
);
1433 sqlite3_free(zLanguageid
);
1434 for(i
=0; i
<nNotindexed
; i
++) sqlite3_free(azNotindexed
[i
]);
1435 sqlite3_free((void *)aCol
);
1436 sqlite3_free((void *)azNotindexed
);
1437 if( rc
!=SQLITE_OK
){
1439 fts3DisconnectMethod((sqlite3_vtab
*)p
);
1440 }else if( pTokenizer
){
1441 pTokenizer
->pModule
->xDestroy(pTokenizer
);
1444 assert( p
->pSegments
==0 );
1451 ** The xConnect() and xCreate() methods for the virtual table. All the
1452 ** work is done in function fts3InitVtab().
1454 static int fts3ConnectMethod(
1455 sqlite3
*db
, /* Database connection */
1456 void *pAux
, /* Pointer to tokenizer hash table */
1457 int argc
, /* Number of elements in argv array */
1458 const char * const *argv
, /* xCreate/xConnect argument array */
1459 sqlite3_vtab
**ppVtab
, /* OUT: New sqlite3_vtab object */
1460 char **pzErr
/* OUT: sqlite3_malloc'd error message */
1462 return fts3InitVtab(0, db
, pAux
, argc
, argv
, ppVtab
, pzErr
);
1464 static int fts3CreateMethod(
1465 sqlite3
*db
, /* Database connection */
1466 void *pAux
, /* Pointer to tokenizer hash table */
1467 int argc
, /* Number of elements in argv array */
1468 const char * const *argv
, /* xCreate/xConnect argument array */
1469 sqlite3_vtab
**ppVtab
, /* OUT: New sqlite3_vtab object */
1470 char **pzErr
/* OUT: sqlite3_malloc'd error message */
1472 return fts3InitVtab(1, db
, pAux
, argc
, argv
, ppVtab
, pzErr
);
1476 ** Set the pIdxInfo->estimatedRows variable to nRow. Unless this
1477 ** extension is currently being used by a version of SQLite too old to
1478 ** support estimatedRows. In that case this function is a no-op.
1480 static void fts3SetEstimatedRows(sqlite3_index_info
*pIdxInfo
, i64 nRow
){
1481 #if SQLITE_VERSION_NUMBER>=3008002
1482 if( sqlite3_libversion_number()>=3008002 ){
1483 pIdxInfo
->estimatedRows
= nRow
;
1489 ** Implementation of the xBestIndex method for FTS3 tables. There
1490 ** are three possible strategies, in order of preference:
1492 ** 1. Direct lookup by rowid or docid.
1493 ** 2. Full-text search using a MATCH operator on a non-docid column.
1494 ** 3. Linear scan of %_content table.
1496 static int fts3BestIndexMethod(sqlite3_vtab
*pVTab
, sqlite3_index_info
*pInfo
){
1497 Fts3Table
*p
= (Fts3Table
*)pVTab
;
1498 int i
; /* Iterator variable */
1499 int iCons
= -1; /* Index of constraint to use */
1501 int iLangidCons
= -1; /* Index of langid=x constraint, if present */
1502 int iDocidGe
= -1; /* Index of docid>=x constraint, if present */
1503 int iDocidLe
= -1; /* Index of docid<=x constraint, if present */
1506 /* By default use a full table scan. This is an expensive option,
1507 ** so search through the constraints to see if a more efficient
1508 ** strategy is possible.
1510 pInfo
->idxNum
= FTS3_FULLSCAN_SEARCH
;
1511 pInfo
->estimatedCost
= 5000000;
1512 for(i
=0; i
<pInfo
->nConstraint
; i
++){
1513 int bDocid
; /* True if this constraint is on docid */
1514 struct sqlite3_index_constraint
*pCons
= &pInfo
->aConstraint
[i
];
1515 if( pCons
->usable
==0 ){
1516 if( pCons
->op
==SQLITE_INDEX_CONSTRAINT_MATCH
){
1517 /* There exists an unusable MATCH constraint. This means that if
1518 ** the planner does elect to use the results of this call as part
1519 ** of the overall query plan the user will see an "unable to use
1520 ** function MATCH in the requested context" error. To discourage
1521 ** this, return a very high cost here. */
1522 pInfo
->idxNum
= FTS3_FULLSCAN_SEARCH
;
1523 pInfo
->estimatedCost
= 1e50
;
1524 fts3SetEstimatedRows(pInfo
, ((sqlite3_int64
)1) << 50);
1530 bDocid
= (pCons
->iColumn
<0 || pCons
->iColumn
==p
->nColumn
+1);
1532 /* A direct lookup on the rowid or docid column. Assign a cost of 1.0. */
1533 if( iCons
<0 && pCons
->op
==SQLITE_INDEX_CONSTRAINT_EQ
&& bDocid
){
1534 pInfo
->idxNum
= FTS3_DOCID_SEARCH
;
1535 pInfo
->estimatedCost
= 1.0;
1539 /* A MATCH constraint. Use a full-text search.
1541 ** If there is more than one MATCH constraint available, use the first
1542 ** one encountered. If there is both a MATCH constraint and a direct
1543 ** rowid/docid lookup, prefer the MATCH strategy. This is done even
1544 ** though the rowid/docid lookup is faster than a MATCH query, selecting
1545 ** it would lead to an "unable to use function MATCH in the requested
1548 if( pCons
->op
==SQLITE_INDEX_CONSTRAINT_MATCH
1549 && pCons
->iColumn
>=0 && pCons
->iColumn
<=p
->nColumn
1551 pInfo
->idxNum
= FTS3_FULLTEXT_SEARCH
+ pCons
->iColumn
;
1552 pInfo
->estimatedCost
= 2.0;
1556 /* Equality constraint on the langid column */
1557 if( pCons
->op
==SQLITE_INDEX_CONSTRAINT_EQ
1558 && pCons
->iColumn
==p
->nColumn
+ 2
1564 switch( pCons
->op
){
1565 case SQLITE_INDEX_CONSTRAINT_GE
:
1566 case SQLITE_INDEX_CONSTRAINT_GT
:
1570 case SQLITE_INDEX_CONSTRAINT_LE
:
1571 case SQLITE_INDEX_CONSTRAINT_LT
:
1580 pInfo
->aConstraintUsage
[iCons
].argvIndex
= iIdx
++;
1581 pInfo
->aConstraintUsage
[iCons
].omit
= 1;
1583 if( iLangidCons
>=0 ){
1584 pInfo
->idxNum
|= FTS3_HAVE_LANGID
;
1585 pInfo
->aConstraintUsage
[iLangidCons
].argvIndex
= iIdx
++;
1588 pInfo
->idxNum
|= FTS3_HAVE_DOCID_GE
;
1589 pInfo
->aConstraintUsage
[iDocidGe
].argvIndex
= iIdx
++;
1592 pInfo
->idxNum
|= FTS3_HAVE_DOCID_LE
;
1593 pInfo
->aConstraintUsage
[iDocidLe
].argvIndex
= iIdx
++;
1596 /* Regardless of the strategy selected, FTS can deliver rows in rowid (or
1597 ** docid) order. Both ascending and descending are possible.
1599 if( pInfo
->nOrderBy
==1 ){
1600 struct sqlite3_index_orderby
*pOrder
= &pInfo
->aOrderBy
[0];
1601 if( pOrder
->iColumn
<0 || pOrder
->iColumn
==p
->nColumn
+1 ){
1603 pInfo
->idxStr
= "DESC";
1605 pInfo
->idxStr
= "ASC";
1607 pInfo
->orderByConsumed
= 1;
1611 assert( p
->pSegments
==0 );
1616 ** Implementation of xOpen method.
1618 static int fts3OpenMethod(sqlite3_vtab
*pVTab
, sqlite3_vtab_cursor
**ppCsr
){
1619 sqlite3_vtab_cursor
*pCsr
; /* Allocated cursor */
1621 UNUSED_PARAMETER(pVTab
);
1623 /* Allocate a buffer large enough for an Fts3Cursor structure. If the
1624 ** allocation succeeds, zero it and return SQLITE_OK. Otherwise,
1625 ** if the allocation fails, return SQLITE_NOMEM.
1627 *ppCsr
= pCsr
= (sqlite3_vtab_cursor
*)sqlite3_malloc(sizeof(Fts3Cursor
));
1629 return SQLITE_NOMEM
;
1631 memset(pCsr
, 0, sizeof(Fts3Cursor
));
1636 ** Close the cursor. For additional information see the documentation
1637 ** on the xClose method of the virtual table interface.
1639 static int fts3CloseMethod(sqlite3_vtab_cursor
*pCursor
){
1640 Fts3Cursor
*pCsr
= (Fts3Cursor
*)pCursor
;
1641 assert( ((Fts3Table
*)pCsr
->base
.pVtab
)->pSegments
==0 );
1642 sqlite3_finalize(pCsr
->pStmt
);
1643 sqlite3Fts3ExprFree(pCsr
->pExpr
);
1644 sqlite3Fts3FreeDeferredTokens(pCsr
);
1645 sqlite3_free(pCsr
->aDoclist
);
1646 sqlite3_free(pCsr
->aMatchinfo
);
1647 assert( ((Fts3Table
*)pCsr
->base
.pVtab
)->pSegments
==0 );
1653 ** If pCsr->pStmt has not been prepared (i.e. if pCsr->pStmt==0), then
1654 ** compose and prepare an SQL statement of the form:
1656 ** "SELECT <columns> FROM %_content WHERE rowid = ?"
1658 ** (or the equivalent for a content=xxx table) and set pCsr->pStmt to
1659 ** it. If an error occurs, return an SQLite error code.
1661 ** Otherwise, set *ppStmt to point to pCsr->pStmt and return SQLITE_OK.
1663 static int fts3CursorSeekStmt(Fts3Cursor
*pCsr
, sqlite3_stmt
**ppStmt
){
1665 if( pCsr
->pStmt
==0 ){
1666 Fts3Table
*p
= (Fts3Table
*)pCsr
->base
.pVtab
;
1668 zSql
= sqlite3_mprintf("SELECT %s WHERE rowid = ?", p
->zReadExprlist
);
1669 if( !zSql
) return SQLITE_NOMEM
;
1670 rc
= sqlite3_prepare_v2(p
->db
, zSql
, -1, &pCsr
->pStmt
, 0);
1673 *ppStmt
= pCsr
->pStmt
;
1678 ** Position the pCsr->pStmt statement so that it is on the row
1679 ** of the %_content table that contains the last match. Return
1680 ** SQLITE_OK on success.
1682 static int fts3CursorSeek(sqlite3_context
*pContext
, Fts3Cursor
*pCsr
){
1684 if( pCsr
->isRequireSeek
){
1685 sqlite3_stmt
*pStmt
= 0;
1687 rc
= fts3CursorSeekStmt(pCsr
, &pStmt
);
1688 if( rc
==SQLITE_OK
){
1689 sqlite3_bind_int64(pCsr
->pStmt
, 1, pCsr
->iPrevId
);
1690 pCsr
->isRequireSeek
= 0;
1691 if( SQLITE_ROW
==sqlite3_step(pCsr
->pStmt
) ){
1694 rc
= sqlite3_reset(pCsr
->pStmt
);
1695 if( rc
==SQLITE_OK
&& ((Fts3Table
*)pCsr
->base
.pVtab
)->zContentTbl
==0 ){
1696 /* If no row was found and no error has occurred, then the %_content
1697 ** table is missing a row that is present in the full-text index.
1698 ** The data structures are corrupt. */
1699 rc
= FTS_CORRUPT_VTAB
;
1706 if( rc
!=SQLITE_OK
&& pContext
){
1707 sqlite3_result_error_code(pContext
, rc
);
1713 ** This function is used to process a single interior node when searching
1714 ** a b-tree for a term or term prefix. The node data is passed to this
1715 ** function via the zNode/nNode parameters. The term to search for is
1716 ** passed in zTerm/nTerm.
1718 ** If piFirst is not NULL, then this function sets *piFirst to the blockid
1719 ** of the child node that heads the sub-tree that may contain the term.
1721 ** If piLast is not NULL, then *piLast is set to the right-most child node
1722 ** that heads a sub-tree that may contain a term for which zTerm/nTerm is
1725 ** If an OOM error occurs, SQLITE_NOMEM is returned. Otherwise, SQLITE_OK.
1727 static int fts3ScanInteriorNode(
1728 const char *zTerm
, /* Term to select leaves for */
1729 int nTerm
, /* Size of term zTerm in bytes */
1730 const char *zNode
, /* Buffer containing segment interior node */
1731 int nNode
, /* Size of buffer at zNode */
1732 sqlite3_int64
*piFirst
, /* OUT: Selected child node */
1733 sqlite3_int64
*piLast
/* OUT: Selected child node */
1735 int rc
= SQLITE_OK
; /* Return code */
1736 const char *zCsr
= zNode
; /* Cursor to iterate through node */
1737 const char *zEnd
= &zCsr
[nNode
];/* End of interior node buffer */
1738 char *zBuffer
= 0; /* Buffer to load terms into */
1739 int nAlloc
= 0; /* Size of allocated buffer */
1740 int isFirstTerm
= 1; /* True when processing first term on page */
1741 sqlite3_int64 iChild
; /* Block id of child node to descend to */
1743 /* Skip over the 'height' varint that occurs at the start of every
1744 ** interior node. Then load the blockid of the left-child of the b-tree
1745 ** node into variable iChild.
1747 ** Even if the data structure on disk is corrupted, this (reading two
1748 ** varints from the buffer) does not risk an overread. If zNode is a
1749 ** root node, then the buffer comes from a SELECT statement. SQLite does
1750 ** not make this guarantee explicitly, but in practice there are always
1751 ** either more than 20 bytes of allocated space following the nNode bytes of
1752 ** contents, or two zero bytes. Or, if the node is read from the %_segments
1753 ** table, then there are always 20 bytes of zeroed padding following the
1754 ** nNode bytes of content (see sqlite3Fts3ReadBlock() for details).
1756 zCsr
+= sqlite3Fts3GetVarint(zCsr
, &iChild
);
1757 zCsr
+= sqlite3Fts3GetVarint(zCsr
, &iChild
);
1759 return FTS_CORRUPT_VTAB
;
1762 while( zCsr
<zEnd
&& (piFirst
|| piLast
) ){
1763 int cmp
; /* memcmp() result */
1764 int nSuffix
; /* Size of term suffix */
1765 int nPrefix
= 0; /* Size of term prefix */
1766 int nBuffer
; /* Total term size */
1768 /* Load the next term on the node into zBuffer. Use realloc() to expand
1769 ** the size of zBuffer if required. */
1771 zCsr
+= fts3GetVarint32(zCsr
, &nPrefix
);
1774 zCsr
+= fts3GetVarint32(zCsr
, &nSuffix
);
1776 if( nPrefix
<0 || nSuffix
<0 || &zCsr
[nSuffix
]>zEnd
){
1777 rc
= FTS_CORRUPT_VTAB
;
1780 if( nPrefix
+nSuffix
>nAlloc
){
1782 nAlloc
= (nPrefix
+nSuffix
) * 2;
1783 zNew
= (char *)sqlite3_realloc(zBuffer
, nAlloc
);
1791 memcpy(&zBuffer
[nPrefix
], zCsr
, nSuffix
);
1792 nBuffer
= nPrefix
+ nSuffix
;
1795 /* Compare the term we are searching for with the term just loaded from
1796 ** the interior node. If the specified term is greater than or equal
1797 ** to the term from the interior node, then all terms on the sub-tree
1798 ** headed by node iChild are smaller than zTerm. No need to search
1801 ** If the interior node term is larger than the specified term, then
1802 ** the tree headed by iChild may contain the specified term.
1804 cmp
= memcmp(zTerm
, zBuffer
, (nBuffer
>nTerm
? nTerm
: nBuffer
));
1805 if( piFirst
&& (cmp
<0 || (cmp
==0 && nBuffer
>nTerm
)) ){
1810 if( piLast
&& cmp
<0 ){
1818 if( piFirst
) *piFirst
= iChild
;
1819 if( piLast
) *piLast
= iChild
;
1822 sqlite3_free(zBuffer
);
1828 ** The buffer pointed to by argument zNode (size nNode bytes) contains an
1829 ** interior node of a b-tree segment. The zTerm buffer (size nTerm bytes)
1830 ** contains a term. This function searches the sub-tree headed by the zNode
1831 ** node for the range of leaf nodes that may contain the specified term
1832 ** or terms for which the specified term is a prefix.
1834 ** If piLeaf is not NULL, then *piLeaf is set to the blockid of the
1835 ** left-most leaf node in the tree that may contain the specified term.
1836 ** If piLeaf2 is not NULL, then *piLeaf2 is set to the blockid of the
1837 ** right-most leaf node that may contain a term for which the specified
1838 ** term is a prefix.
1840 ** It is possible that the range of returned leaf nodes does not contain
1841 ** the specified term or any terms for which it is a prefix. However, if the
1842 ** segment does contain any such terms, they are stored within the identified
1843 ** range. Because this function only inspects interior segment nodes (and
1844 ** never loads leaf nodes into memory), it is not possible to be sure.
1846 ** If an error occurs, an error code other than SQLITE_OK is returned.
1848 static int fts3SelectLeaf(
1849 Fts3Table
*p
, /* Virtual table handle */
1850 const char *zTerm
, /* Term to select leaves for */
1851 int nTerm
, /* Size of term zTerm in bytes */
1852 const char *zNode
, /* Buffer containing segment interior node */
1853 int nNode
, /* Size of buffer at zNode */
1854 sqlite3_int64
*piLeaf
, /* Selected leaf node */
1855 sqlite3_int64
*piLeaf2
/* Selected leaf node */
1857 int rc
; /* Return code */
1858 int iHeight
; /* Height of this node in tree */
1860 assert( piLeaf
|| piLeaf2
);
1862 fts3GetVarint32(zNode
, &iHeight
);
1863 rc
= fts3ScanInteriorNode(zTerm
, nTerm
, zNode
, nNode
, piLeaf
, piLeaf2
);
1864 assert( !piLeaf2
|| !piLeaf
|| rc
!=SQLITE_OK
|| (*piLeaf
<=*piLeaf2
) );
1866 if( rc
==SQLITE_OK
&& iHeight
>1 ){
1867 char *zBlob
= 0; /* Blob read from %_segments table */
1868 int nBlob
; /* Size of zBlob in bytes */
1870 if( piLeaf
&& piLeaf2
&& (*piLeaf
!=*piLeaf2
) ){
1871 rc
= sqlite3Fts3ReadBlock(p
, *piLeaf
, &zBlob
, &nBlob
, 0);
1872 if( rc
==SQLITE_OK
){
1873 rc
= fts3SelectLeaf(p
, zTerm
, nTerm
, zBlob
, nBlob
, piLeaf
, 0);
1875 sqlite3_free(zBlob
);
1880 if( rc
==SQLITE_OK
){
1881 rc
= sqlite3Fts3ReadBlock(p
, piLeaf
?*piLeaf
:*piLeaf2
, &zBlob
, &nBlob
, 0);
1883 if( rc
==SQLITE_OK
){
1884 rc
= fts3SelectLeaf(p
, zTerm
, nTerm
, zBlob
, nBlob
, piLeaf
, piLeaf2
);
1886 sqlite3_free(zBlob
);
1893 ** This function is used to create delta-encoded serialized lists of FTS3
1894 ** varints. Each call to this function appends a single varint to a list.
1896 static void fts3PutDeltaVarint(
1897 char **pp
, /* IN/OUT: Output pointer */
1898 sqlite3_int64
*piPrev
, /* IN/OUT: Previous value written to list */
1899 sqlite3_int64 iVal
/* Write this value to the list */
1901 assert( iVal
-*piPrev
> 0 || (*piPrev
==0 && iVal
==0) );
1902 *pp
+= sqlite3Fts3PutVarint(*pp
, iVal
-*piPrev
);
1907 ** When this function is called, *ppPoslist is assumed to point to the
1908 ** start of a position-list. After it returns, *ppPoslist points to the
1909 ** first byte after the position-list.
1911 ** A position list is list of positions (delta encoded) and columns for
1912 ** a single document record of a doclist. So, in other words, this
1913 ** routine advances *ppPoslist so that it points to the next docid in
1914 ** the doclist, or to the first byte past the end of the doclist.
1916 ** If pp is not NULL, then the contents of the position list are copied
1917 ** to *pp. *pp is set to point to the first byte past the last byte copied
1918 ** before this function returns.
1920 static void fts3PoslistCopy(char **pp
, char **ppPoslist
){
1921 char *pEnd
= *ppPoslist
;
1924 /* The end of a position list is marked by a zero encoded as an FTS3
1925 ** varint. A single POS_END (0) byte. Except, if the 0 byte is preceded by
1926 ** a byte with the 0x80 bit set, then it is not a varint 0, but the tail
1927 ** of some other, multi-byte, value.
1929 ** The following while-loop moves pEnd to point to the first byte that is not
1930 ** immediately preceded by a byte with the 0x80 bit set. Then increments
1931 ** pEnd once more so that it points to the byte immediately following the
1932 ** last byte in the position-list.
1936 testcase( c
!=0 && (*pEnd
)==0 );
1938 pEnd
++; /* Advance past the POS_END terminator byte */
1941 int n
= (int)(pEnd
- *ppPoslist
);
1943 memcpy(p
, *ppPoslist
, n
);
1951 ** When this function is called, *ppPoslist is assumed to point to the
1952 ** start of a column-list. After it returns, *ppPoslist points to the
1953 ** to the terminator (POS_COLUMN or POS_END) byte of the column-list.
1955 ** A column-list is list of delta-encoded positions for a single column
1956 ** within a single document within a doclist.
1958 ** The column-list is terminated either by a POS_COLUMN varint (1) or
1959 ** a POS_END varint (0). This routine leaves *ppPoslist pointing to
1960 ** the POS_COLUMN or POS_END that terminates the column-list.
1962 ** If pp is not NULL, then the contents of the column-list are copied
1963 ** to *pp. *pp is set to point to the first byte past the last byte copied
1964 ** before this function returns. The POS_COLUMN or POS_END terminator
1965 ** is not copied into *pp.
1967 static void fts3ColumnlistCopy(char **pp
, char **ppPoslist
){
1968 char *pEnd
= *ppPoslist
;
1971 /* A column-list is terminated by either a 0x01 or 0x00 byte that is
1972 ** not part of a multi-byte varint.
1974 while( 0xFE & (*pEnd
| c
) ){
1976 testcase( c
!=0 && ((*pEnd
)&0xfe)==0 );
1979 int n
= (int)(pEnd
- *ppPoslist
);
1981 memcpy(p
, *ppPoslist
, n
);
1989 ** Value used to signify the end of an position-list. This is safe because
1990 ** it is not possible to have a document with 2^31 terms.
1992 #define POSITION_LIST_END 0x7fffffff
1995 ** This function is used to help parse position-lists. When this function is
1996 ** called, *pp may point to the start of the next varint in the position-list
1997 ** being parsed, or it may point to 1 byte past the end of the position-list
1998 ** (in which case **pp will be a terminator bytes POS_END (0) or
2001 ** If *pp points past the end of the current position-list, set *pi to
2002 ** POSITION_LIST_END and return. Otherwise, read the next varint from *pp,
2003 ** increment the current value of *pi by the value read, and set *pp to
2004 ** point to the next value before returning.
2006 ** Before calling this routine *pi must be initialized to the value of
2007 ** the previous position, or zero if we are reading the first position
2008 ** in the position-list. Because positions are delta-encoded, the value
2009 ** of the previous position is needed in order to compute the value of
2010 ** the next position.
2012 static void fts3ReadNextPos(
2013 char **pp
, /* IN/OUT: Pointer into position-list buffer */
2014 sqlite3_int64
*pi
/* IN/OUT: Value read from position-list */
2017 fts3GetDeltaVarint(pp
, pi
);
2020 *pi
= POSITION_LIST_END
;
2025 ** If parameter iCol is not 0, write an POS_COLUMN (1) byte followed by
2026 ** the value of iCol encoded as a varint to *pp. This will start a new
2029 ** Set *pp to point to the byte just after the last byte written before
2030 ** returning (do not modify it if iCol==0). Return the total number of bytes
2031 ** written (0 if iCol==0).
2033 static int fts3PutColNumber(char **pp
, int iCol
){
2034 int n
= 0; /* Number of bytes written */
2036 char *p
= *pp
; /* Output pointer */
2037 n
= 1 + sqlite3Fts3PutVarint(&p
[1], iCol
);
2045 ** Compute the union of two position lists. The output written
2046 ** into *pp contains all positions of both *pp1 and *pp2 in sorted
2047 ** order and with any duplicates removed. All pointers are
2048 ** updated appropriately. The caller is responsible for insuring
2049 ** that there is enough space in *pp to hold the complete output.
2051 static void fts3PoslistMerge(
2052 char **pp
, /* Output buffer */
2053 char **pp1
, /* Left input list */
2054 char **pp2
/* Right input list */
2060 while( *p1
|| *p2
){
2061 int iCol1
; /* The current column index in pp1 */
2062 int iCol2
; /* The current column index in pp2 */
2064 if( *p1
==POS_COLUMN
) fts3GetVarint32(&p1
[1], &iCol1
);
2065 else if( *p1
==POS_END
) iCol1
= POSITION_LIST_END
;
2068 if( *p2
==POS_COLUMN
) fts3GetVarint32(&p2
[1], &iCol2
);
2069 else if( *p2
==POS_END
) iCol2
= POSITION_LIST_END
;
2073 sqlite3_int64 i1
= 0; /* Last position from pp1 */
2074 sqlite3_int64 i2
= 0; /* Last position from pp2 */
2075 sqlite3_int64 iPrev
= 0;
2076 int n
= fts3PutColNumber(&p
, iCol1
);
2080 /* At this point, both p1 and p2 point to the start of column-lists
2081 ** for the same column (the column with index iCol1 and iCol2).
2082 ** A column-list is a list of non-negative delta-encoded varints, each
2083 ** incremented by 2 before being stored. Each list is terminated by a
2084 ** POS_END (0) or POS_COLUMN (1). The following block merges the two lists
2085 ** and writes the results to buffer p. p is left pointing to the byte
2086 ** after the list written. No terminator (POS_END or POS_COLUMN) is
2087 ** written to the output.
2089 fts3GetDeltaVarint(&p1
, &i1
);
2090 fts3GetDeltaVarint(&p2
, &i2
);
2092 fts3PutDeltaVarint(&p
, &iPrev
, (i1
<i2
) ? i1
: i2
);
2095 fts3ReadNextPos(&p1
, &i1
);
2096 fts3ReadNextPos(&p2
, &i2
);
2098 fts3ReadNextPos(&p1
, &i1
);
2100 fts3ReadNextPos(&p2
, &i2
);
2102 }while( i1
!=POSITION_LIST_END
|| i2
!=POSITION_LIST_END
);
2103 }else if( iCol1
<iCol2
){
2104 p1
+= fts3PutColNumber(&p
, iCol1
);
2105 fts3ColumnlistCopy(&p
, &p1
);
2107 p2
+= fts3PutColNumber(&p
, iCol2
);
2108 fts3ColumnlistCopy(&p
, &p2
);
2119 ** This function is used to merge two position lists into one. When it is
2120 ** called, *pp1 and *pp2 must both point to position lists. A position-list is
2121 ** the part of a doclist that follows each document id. For example, if a row
2124 ** 'a b c'|'x y z'|'a b b a'
2126 ** Then the position list for this row for token 'b' would consist of:
2128 ** 0x02 0x01 0x02 0x03 0x03 0x00
2130 ** When this function returns, both *pp1 and *pp2 are left pointing to the
2131 ** byte following the 0x00 terminator of their respective position lists.
2133 ** If isSaveLeft is 0, an entry is added to the output position list for
2134 ** each position in *pp2 for which there exists one or more positions in
2135 ** *pp1 so that (pos(*pp2)>pos(*pp1) && pos(*pp2)-pos(*pp1)<=nToken). i.e.
2136 ** when the *pp1 token appears before the *pp2 token, but not more than nToken
2139 ** e.g. nToken==1 searches for adjacent positions.
2141 static int fts3PoslistPhraseMerge(
2142 char **pp
, /* IN/OUT: Preallocated output buffer */
2143 int nToken
, /* Maximum difference in token positions */
2144 int isSaveLeft
, /* Save the left position */
2145 int isExact
, /* If *pp1 is exactly nTokens before *pp2 */
2146 char **pp1
, /* IN/OUT: Left input list */
2147 char **pp2
/* IN/OUT: Right input list */
2155 /* Never set both isSaveLeft and isExact for the same invocation. */
2156 assert( isSaveLeft
==0 || isExact
==0 );
2158 assert( p
!=0 && *p1
!=0 && *p2
!=0 );
2159 if( *p1
==POS_COLUMN
){
2161 p1
+= fts3GetVarint32(p1
, &iCol1
);
2163 if( *p2
==POS_COLUMN
){
2165 p2
+= fts3GetVarint32(p2
, &iCol2
);
2171 sqlite3_int64 iPrev
= 0;
2172 sqlite3_int64 iPos1
= 0;
2173 sqlite3_int64 iPos2
= 0;
2177 p
+= sqlite3Fts3PutVarint(p
, iCol1
);
2180 assert( *p1
!=POS_END
&& *p1
!=POS_COLUMN
);
2181 assert( *p2
!=POS_END
&& *p2
!=POS_COLUMN
);
2182 fts3GetDeltaVarint(&p1
, &iPos1
); iPos1
-= 2;
2183 fts3GetDeltaVarint(&p2
, &iPos2
); iPos2
-= 2;
2186 if( iPos2
==iPos1
+nToken
2187 || (isExact
==0 && iPos2
>iPos1
&& iPos2
<=iPos1
+nToken
)
2189 sqlite3_int64 iSave
;
2190 iSave
= isSaveLeft
? iPos1
: iPos2
;
2191 fts3PutDeltaVarint(&p
, &iPrev
, iSave
+2); iPrev
-= 2;
2195 if( (!isSaveLeft
&& iPos2
<=(iPos1
+nToken
)) || iPos2
<=iPos1
){
2196 if( (*p2
&0xFE)==0 ) break;
2197 fts3GetDeltaVarint(&p2
, &iPos2
); iPos2
-= 2;
2199 if( (*p1
&0xFE)==0 ) break;
2200 fts3GetDeltaVarint(&p1
, &iPos1
); iPos1
-= 2;
2209 fts3ColumnlistCopy(0, &p1
);
2210 fts3ColumnlistCopy(0, &p2
);
2211 assert( (*p1
&0xFE)==0 && (*p2
&0xFE)==0 );
2212 if( 0==*p1
|| 0==*p2
) break;
2215 p1
+= fts3GetVarint32(p1
, &iCol1
);
2217 p2
+= fts3GetVarint32(p2
, &iCol2
);
2220 /* Advance pointer p1 or p2 (whichever corresponds to the smaller of
2221 ** iCol1 and iCol2) so that it points to either the 0x00 that marks the
2222 ** end of the position list, or the 0x01 that precedes the next
2223 ** column-number in the position list.
2225 else if( iCol1
<iCol2
){
2226 fts3ColumnlistCopy(0, &p1
);
2229 p1
+= fts3GetVarint32(p1
, &iCol1
);
2231 fts3ColumnlistCopy(0, &p2
);
2234 p2
+= fts3GetVarint32(p2
, &iCol2
);
2238 fts3PoslistCopy(0, &p2
);
2239 fts3PoslistCopy(0, &p1
);
2251 ** Merge two position-lists as required by the NEAR operator. The argument
2252 ** position lists correspond to the left and right phrases of an expression
2255 ** "phrase 1" NEAR "phrase number 2"
2257 ** Position list *pp1 corresponds to the left-hand side of the NEAR
2258 ** expression and *pp2 to the right. As usual, the indexes in the position
2259 ** lists are the offsets of the last token in each phrase (tokens "1" and "2"
2260 ** in the example above).
2262 ** The output position list - written to *pp - is a copy of *pp2 with those
2263 ** entries that are not sufficiently NEAR entries in *pp1 removed.
2265 static int fts3PoslistNearMerge(
2266 char **pp
, /* Output buffer */
2267 char *aTmp
, /* Temporary buffer space */
2268 int nRight
, /* Maximum difference in token positions */
2269 int nLeft
, /* Maximum difference in token positions */
2270 char **pp1
, /* IN/OUT: Left input list */
2271 char **pp2
/* IN/OUT: Right input list */
2281 fts3PoslistPhraseMerge(&pTmp1
, nRight
, 0, 0, pp1
, pp2
);
2282 aTmp2
= pTmp2
= pTmp1
;
2285 fts3PoslistPhraseMerge(&pTmp2
, nLeft
, 1, 0, pp2
, pp1
);
2286 if( pTmp1
!=aTmp
&& pTmp2
!=aTmp2
){
2287 fts3PoslistMerge(pp
, &aTmp
, &aTmp2
);
2288 }else if( pTmp1
!=aTmp
){
2289 fts3PoslistCopy(pp
, &aTmp
);
2290 }else if( pTmp2
!=aTmp2
){
2291 fts3PoslistCopy(pp
, &aTmp2
);
2300 ** An instance of this function is used to merge together the (potentially
2301 ** large number of) doclists for each term that matches a prefix query.
2302 ** See function fts3TermSelectMerge() for details.
2304 typedef struct TermSelect TermSelect
;
2306 char *aaOutput
[16]; /* Malloc'd output buffers */
2307 int anOutput
[16]; /* Size each output buffer in bytes */
2311 ** This function is used to read a single varint from a buffer. Parameter
2312 ** pEnd points 1 byte past the end of the buffer. When this function is
2313 ** called, if *pp points to pEnd or greater, then the end of the buffer
2314 ** has been reached. In this case *pp is set to 0 and the function returns.
2316 ** If *pp does not point to or past pEnd, then a single varint is read
2317 ** from *pp. *pp is then set to point 1 byte past the end of the read varint.
2319 ** If bDescIdx is false, the value read is added to *pVal before returning.
2320 ** If it is true, the value read is subtracted from *pVal before this
2321 ** function returns.
2323 static void fts3GetDeltaVarint3(
2324 char **pp
, /* IN/OUT: Point to read varint from */
2325 char *pEnd
, /* End of buffer */
2326 int bDescIdx
, /* True if docids are descending */
2327 sqlite3_int64
*pVal
/* IN/OUT: Integer value */
2333 *pp
+= sqlite3Fts3GetVarint(*pp
, &iVal
);
2343 ** This function is used to write a single varint to a buffer. The varint
2344 ** is written to *pp. Before returning, *pp is set to point 1 byte past the
2345 ** end of the value written.
2347 ** If *pbFirst is zero when this function is called, the value written to
2348 ** the buffer is that of parameter iVal.
2350 ** If *pbFirst is non-zero when this function is called, then the value
2351 ** written is either (iVal-*piPrev) (if bDescIdx is zero) or (*piPrev-iVal)
2352 ** (if bDescIdx is non-zero).
2354 ** Before returning, this function always sets *pbFirst to 1 and *piPrev
2355 ** to the value of parameter iVal.
2357 static void fts3PutDeltaVarint3(
2358 char **pp
, /* IN/OUT: Output pointer */
2359 int bDescIdx
, /* True for descending docids */
2360 sqlite3_int64
*piPrev
, /* IN/OUT: Previous value written to list */
2361 int *pbFirst
, /* IN/OUT: True after first int written */
2362 sqlite3_int64 iVal
/* Write this value to the list */
2364 sqlite3_int64 iWrite
;
2365 if( bDescIdx
==0 || *pbFirst
==0 ){
2366 iWrite
= iVal
- *piPrev
;
2368 iWrite
= *piPrev
- iVal
;
2370 assert( *pbFirst
|| *piPrev
==0 );
2371 assert( *pbFirst
==0 || iWrite
>0 );
2372 *pp
+= sqlite3Fts3PutVarint(*pp
, iWrite
);
2379 ** This macro is used by various functions that merge doclists. The two
2380 ** arguments are 64-bit docid values. If the value of the stack variable
2381 ** bDescDoclist is 0 when this macro is invoked, then it returns (i1-i2).
2382 ** Otherwise, (i2-i1).
2384 ** Using this makes it easier to write code that can merge doclists that are
2385 ** sorted in either ascending or descending order.
2387 #define DOCID_CMP(i1, i2) ((bDescDoclist?-1:1) * (i1-i2))
2390 ** This function does an "OR" merge of two doclists (output contains all
2391 ** positions contained in either argument doclist). If the docids in the
2392 ** input doclists are sorted in ascending order, parameter bDescDoclist
2393 ** should be false. If they are sorted in ascending order, it should be
2394 ** passed a non-zero value.
2396 ** If no error occurs, *paOut is set to point at an sqlite3_malloc'd buffer
2397 ** containing the output doclist and SQLITE_OK is returned. In this case
2398 ** *pnOut is set to the number of bytes in the output doclist.
2400 ** If an error occurs, an SQLite error code is returned. The output values
2401 ** are undefined in this case.
2403 static int fts3DoclistOrMerge(
2404 int bDescDoclist
, /* True if arguments are desc */
2405 char *a1
, int n1
, /* First doclist */
2406 char *a2
, int n2
, /* Second doclist */
2407 char **paOut
, int *pnOut
/* OUT: Malloc'd doclist */
2409 sqlite3_int64 i1
= 0;
2410 sqlite3_int64 i2
= 0;
2411 sqlite3_int64 iPrev
= 0;
2412 char *pEnd1
= &a1
[n1
];
2413 char *pEnd2
= &a2
[n2
];
2423 /* Allocate space for the output. Both the input and output doclists
2424 ** are delta encoded. If they are in ascending order (bDescDoclist==0),
2425 ** then the first docid in each list is simply encoded as a varint. For
2426 ** each subsequent docid, the varint stored is the difference between the
2427 ** current and previous docid (a positive number - since the list is in
2428 ** ascending order).
2430 ** The first docid written to the output is therefore encoded using the
2431 ** same number of bytes as it is in whichever of the input lists it is
2432 ** read from. And each subsequent docid read from the same input list
2433 ** consumes either the same or less bytes as it did in the input (since
2434 ** the difference between it and the previous value in the output must
2435 ** be a positive value less than or equal to the delta value read from
2436 ** the input list). The same argument applies to all but the first docid
2437 ** read from the 'other' list. And to the contents of all position lists
2438 ** that will be copied and merged from the input to the output.
2440 ** However, if the first docid copied to the output is a negative number,
2441 ** then the encoding of the first docid from the 'other' input list may
2442 ** be larger in the output than it was in the input (since the delta value
2443 ** may be a larger positive integer than the actual docid).
2445 ** The space required to store the output is therefore the sum of the
2446 ** sizes of the two inputs, plus enough space for exactly one of the input
2449 ** A symetric argument may be made if the doclists are in descending
2452 aOut
= sqlite3_malloc(n1
+n2
+FTS3_VARINT_MAX
-1);
2453 if( !aOut
) return SQLITE_NOMEM
;
2456 fts3GetDeltaVarint3(&p1
, pEnd1
, 0, &i1
);
2457 fts3GetDeltaVarint3(&p2
, pEnd2
, 0, &i2
);
2459 sqlite3_int64 iDiff
= DOCID_CMP(i1
, i2
);
2461 if( p2
&& p1
&& iDiff
==0 ){
2462 fts3PutDeltaVarint3(&p
, bDescDoclist
, &iPrev
, &bFirstOut
, i1
);
2463 fts3PoslistMerge(&p
, &p1
, &p2
);
2464 fts3GetDeltaVarint3(&p1
, pEnd1
, bDescDoclist
, &i1
);
2465 fts3GetDeltaVarint3(&p2
, pEnd2
, bDescDoclist
, &i2
);
2466 }else if( !p2
|| (p1
&& iDiff
<0) ){
2467 fts3PutDeltaVarint3(&p
, bDescDoclist
, &iPrev
, &bFirstOut
, i1
);
2468 fts3PoslistCopy(&p
, &p1
);
2469 fts3GetDeltaVarint3(&p1
, pEnd1
, bDescDoclist
, &i1
);
2471 fts3PutDeltaVarint3(&p
, bDescDoclist
, &iPrev
, &bFirstOut
, i2
);
2472 fts3PoslistCopy(&p
, &p2
);
2473 fts3GetDeltaVarint3(&p2
, pEnd2
, bDescDoclist
, &i2
);
2478 *pnOut
= (int)(p
-aOut
);
2479 assert( *pnOut
<=n1
+n2
+FTS3_VARINT_MAX
-1 );
2484 ** This function does a "phrase" merge of two doclists. In a phrase merge,
2485 ** the output contains a copy of each position from the right-hand input
2486 ** doclist for which there is a position in the left-hand input doclist
2487 ** exactly nDist tokens before it.
2489 ** If the docids in the input doclists are sorted in ascending order,
2490 ** parameter bDescDoclist should be false. If they are sorted in ascending
2491 ** order, it should be passed a non-zero value.
2493 ** The right-hand input doclist is overwritten by this function.
2495 static void fts3DoclistPhraseMerge(
2496 int bDescDoclist
, /* True if arguments are desc */
2497 int nDist
, /* Distance from left to right (1=adjacent) */
2498 char *aLeft
, int nLeft
, /* Left doclist */
2499 char *aRight
, int *pnRight
/* IN/OUT: Right/output doclist */
2501 sqlite3_int64 i1
= 0;
2502 sqlite3_int64 i2
= 0;
2503 sqlite3_int64 iPrev
= 0;
2504 char *pEnd1
= &aLeft
[nLeft
];
2505 char *pEnd2
= &aRight
[*pnRight
];
2510 char *aOut
= aRight
;
2515 fts3GetDeltaVarint3(&p1
, pEnd1
, 0, &i1
);
2516 fts3GetDeltaVarint3(&p2
, pEnd2
, 0, &i2
);
2519 sqlite3_int64 iDiff
= DOCID_CMP(i1
, i2
);
2522 sqlite3_int64 iPrevSave
= iPrev
;
2523 int bFirstOutSave
= bFirstOut
;
2525 fts3PutDeltaVarint3(&p
, bDescDoclist
, &iPrev
, &bFirstOut
, i1
);
2526 if( 0==fts3PoslistPhraseMerge(&p
, nDist
, 0, 1, &p1
, &p2
) ){
2529 bFirstOut
= bFirstOutSave
;
2531 fts3GetDeltaVarint3(&p1
, pEnd1
, bDescDoclist
, &i1
);
2532 fts3GetDeltaVarint3(&p2
, pEnd2
, bDescDoclist
, &i2
);
2533 }else if( iDiff
<0 ){
2534 fts3PoslistCopy(0, &p1
);
2535 fts3GetDeltaVarint3(&p1
, pEnd1
, bDescDoclist
, &i1
);
2537 fts3PoslistCopy(0, &p2
);
2538 fts3GetDeltaVarint3(&p2
, pEnd2
, bDescDoclist
, &i2
);
2542 *pnRight
= (int)(p
- aOut
);
2546 ** Argument pList points to a position list nList bytes in size. This
2547 ** function checks to see if the position list contains any entries for
2548 ** a token in position 0 (of any column). If so, it writes argument iDelta
2549 ** to the output buffer pOut, followed by a position list consisting only
2550 ** of the entries from pList at position 0, and terminated by an 0x00 byte.
2551 ** The value returned is the number of bytes written to pOut (if any).
2553 int sqlite3Fts3FirstFilter(
2554 sqlite3_int64 iDelta
, /* Varint that may be written to pOut */
2555 char *pList
, /* Position list (no 0x00 term) */
2556 int nList
, /* Size of pList in bytes */
2557 char *pOut
/* Write output here */
2560 int bWritten
= 0; /* True once iDelta has been written */
2562 char *pEnd
= &pList
[nList
];
2566 nOut
+= sqlite3Fts3PutVarint(&pOut
[nOut
], iDelta
);
2567 pOut
[nOut
++] = 0x02;
2570 fts3ColumnlistCopy(0, &p
);
2573 while( p
<pEnd
&& *p
==0x01 ){
2576 p
+= sqlite3Fts3GetVarint(p
, &iCol
);
2579 nOut
+= sqlite3Fts3PutVarint(&pOut
[nOut
], iDelta
);
2582 pOut
[nOut
++] = 0x01;
2583 nOut
+= sqlite3Fts3PutVarint(&pOut
[nOut
], iCol
);
2584 pOut
[nOut
++] = 0x02;
2586 fts3ColumnlistCopy(0, &p
);
2589 pOut
[nOut
++] = 0x00;
2597 ** Merge all doclists in the TermSelect.aaOutput[] array into a single
2598 ** doclist stored in TermSelect.aaOutput[0]. If successful, delete all
2599 ** other doclists (except the aaOutput[0] one) and return SQLITE_OK.
2601 ** If an OOM error occurs, return SQLITE_NOMEM. In this case it is
2602 ** the responsibility of the caller to free any doclists left in the
2603 ** TermSelect.aaOutput[] array.
2605 static int fts3TermSelectFinishMerge(Fts3Table
*p
, TermSelect
*pTS
){
2610 /* Loop through the doclists in the aaOutput[] array. Merge them all
2611 ** into a single doclist.
2613 for(i
=0; i
<SizeofArray(pTS
->aaOutput
); i
++){
2614 if( pTS
->aaOutput
[i
] ){
2616 aOut
= pTS
->aaOutput
[i
];
2617 nOut
= pTS
->anOutput
[i
];
2618 pTS
->aaOutput
[i
] = 0;
2623 int rc
= fts3DoclistOrMerge(p
->bDescIdx
,
2624 pTS
->aaOutput
[i
], pTS
->anOutput
[i
], aOut
, nOut
, &aNew
, &nNew
2626 if( rc
!=SQLITE_OK
){
2631 sqlite3_free(pTS
->aaOutput
[i
]);
2633 pTS
->aaOutput
[i
] = 0;
2640 pTS
->aaOutput
[0] = aOut
;
2641 pTS
->anOutput
[0] = nOut
;
2646 ** Merge the doclist aDoclist/nDoclist into the TermSelect object passed
2647 ** as the first argument. The merge is an "OR" merge (see function
2648 ** fts3DoclistOrMerge() for details).
2650 ** This function is called with the doclist for each term that matches
2651 ** a queried prefix. It merges all these doclists into one, the doclist
2652 ** for the specified prefix. Since there can be a very large number of
2653 ** doclists to merge, the merging is done pair-wise using the TermSelect
2656 ** This function returns SQLITE_OK if the merge is successful, or an
2657 ** SQLite error code (SQLITE_NOMEM) if an error occurs.
2659 static int fts3TermSelectMerge(
2660 Fts3Table
*p
, /* FTS table handle */
2661 TermSelect
*pTS
, /* TermSelect object to merge into */
2662 char *aDoclist
, /* Pointer to doclist */
2663 int nDoclist
/* Size of aDoclist in bytes */
2665 if( pTS
->aaOutput
[0]==0 ){
2666 /* If this is the first term selected, copy the doclist to the output
2667 ** buffer using memcpy(). */
2668 pTS
->aaOutput
[0] = sqlite3_malloc(nDoclist
);
2669 pTS
->anOutput
[0] = nDoclist
;
2670 if( pTS
->aaOutput
[0] ){
2671 memcpy(pTS
->aaOutput
[0], aDoclist
, nDoclist
);
2673 return SQLITE_NOMEM
;
2676 char *aMerge
= aDoclist
;
2677 int nMerge
= nDoclist
;
2680 for(iOut
=0; iOut
<SizeofArray(pTS
->aaOutput
); iOut
++){
2681 if( pTS
->aaOutput
[iOut
]==0 ){
2683 pTS
->aaOutput
[iOut
] = aMerge
;
2684 pTS
->anOutput
[iOut
] = nMerge
;
2690 int rc
= fts3DoclistOrMerge(p
->bDescIdx
, aMerge
, nMerge
,
2691 pTS
->aaOutput
[iOut
], pTS
->anOutput
[iOut
], &aNew
, &nNew
2693 if( rc
!=SQLITE_OK
){
2694 if( aMerge
!=aDoclist
) sqlite3_free(aMerge
);
2698 if( aMerge
!=aDoclist
) sqlite3_free(aMerge
);
2699 sqlite3_free(pTS
->aaOutput
[iOut
]);
2700 pTS
->aaOutput
[iOut
] = 0;
2704 if( (iOut
+1)==SizeofArray(pTS
->aaOutput
) ){
2705 pTS
->aaOutput
[iOut
] = aMerge
;
2706 pTS
->anOutput
[iOut
] = nMerge
;
2715 ** Append SegReader object pNew to the end of the pCsr->apSegment[] array.
2717 static int fts3SegReaderCursorAppend(
2718 Fts3MultiSegReader
*pCsr
,
2721 if( (pCsr
->nSegment
%16)==0 ){
2722 Fts3SegReader
**apNew
;
2723 int nByte
= (pCsr
->nSegment
+ 16)*sizeof(Fts3SegReader
*);
2724 apNew
= (Fts3SegReader
**)sqlite3_realloc(pCsr
->apSegment
, nByte
);
2726 sqlite3Fts3SegReaderFree(pNew
);
2727 return SQLITE_NOMEM
;
2729 pCsr
->apSegment
= apNew
;
2731 pCsr
->apSegment
[pCsr
->nSegment
++] = pNew
;
2736 ** Add seg-reader objects to the Fts3MultiSegReader object passed as the
2739 ** This function returns SQLITE_OK if successful, or an SQLite error code
2742 static int fts3SegReaderCursor(
2743 Fts3Table
*p
, /* FTS3 table handle */
2744 int iLangid
, /* Language id */
2745 int iIndex
, /* Index to search (from 0 to p->nIndex-1) */
2746 int iLevel
, /* Level of segments to scan */
2747 const char *zTerm
, /* Term to query for */
2748 int nTerm
, /* Size of zTerm in bytes */
2749 int isPrefix
, /* True for a prefix search */
2750 int isScan
, /* True to scan from zTerm to EOF */
2751 Fts3MultiSegReader
*pCsr
/* Cursor object to populate */
2753 int rc
= SQLITE_OK
; /* Error code */
2754 sqlite3_stmt
*pStmt
= 0; /* Statement to iterate through segments */
2755 int rc2
; /* Result of sqlite3_reset() */
2757 /* If iLevel is less than 0 and this is not a scan, include a seg-reader
2758 ** for the pending-terms. If this is a scan, then this call must be being
2759 ** made by an fts4aux module, not an FTS table. In this case calling
2760 ** Fts3SegReaderPending might segfault, as the data structures used by
2761 ** fts4aux are not completely populated. So it's easiest to filter these
2762 ** calls out here. */
2763 if( iLevel
<0 && p
->aIndex
){
2764 Fts3SegReader
*pSeg
= 0;
2765 rc
= sqlite3Fts3SegReaderPending(p
, iIndex
, zTerm
, nTerm
, isPrefix
, &pSeg
);
2766 if( rc
==SQLITE_OK
&& pSeg
){
2767 rc
= fts3SegReaderCursorAppend(pCsr
, pSeg
);
2771 if( iLevel
!=FTS3_SEGCURSOR_PENDING
){
2772 if( rc
==SQLITE_OK
){
2773 rc
= sqlite3Fts3AllSegdirs(p
, iLangid
, iIndex
, iLevel
, &pStmt
);
2776 while( rc
==SQLITE_OK
&& SQLITE_ROW
==(rc
= sqlite3_step(pStmt
)) ){
2777 Fts3SegReader
*pSeg
= 0;
2779 /* Read the values returned by the SELECT into local variables. */
2780 sqlite3_int64 iStartBlock
= sqlite3_column_int64(pStmt
, 1);
2781 sqlite3_int64 iLeavesEndBlock
= sqlite3_column_int64(pStmt
, 2);
2782 sqlite3_int64 iEndBlock
= sqlite3_column_int64(pStmt
, 3);
2783 int nRoot
= sqlite3_column_bytes(pStmt
, 4);
2784 char const *zRoot
= sqlite3_column_blob(pStmt
, 4);
2786 /* If zTerm is not NULL, and this segment is not stored entirely on its
2787 ** root node, the range of leaves scanned can be reduced. Do this. */
2788 if( iStartBlock
&& zTerm
){
2789 sqlite3_int64
*pi
= (isPrefix
? &iLeavesEndBlock
: 0);
2790 rc
= fts3SelectLeaf(p
, zTerm
, nTerm
, zRoot
, nRoot
, &iStartBlock
, pi
);
2791 if( rc
!=SQLITE_OK
) goto finished
;
2792 if( isPrefix
==0 && isScan
==0 ) iLeavesEndBlock
= iStartBlock
;
2795 rc
= sqlite3Fts3SegReaderNew(pCsr
->nSegment
+1,
2796 (isPrefix
==0 && isScan
==0),
2797 iStartBlock
, iLeavesEndBlock
,
2798 iEndBlock
, zRoot
, nRoot
, &pSeg
2800 if( rc
!=SQLITE_OK
) goto finished
;
2801 rc
= fts3SegReaderCursorAppend(pCsr
, pSeg
);
2806 rc2
= sqlite3_reset(pStmt
);
2807 if( rc
==SQLITE_DONE
) rc
= rc2
;
2813 ** Set up a cursor object for iterating through a full-text index or a
2814 ** single level therein.
2816 int sqlite3Fts3SegReaderCursor(
2817 Fts3Table
*p
, /* FTS3 table handle */
2818 int iLangid
, /* Language-id to search */
2819 int iIndex
, /* Index to search (from 0 to p->nIndex-1) */
2820 int iLevel
, /* Level of segments to scan */
2821 const char *zTerm
, /* Term to query for */
2822 int nTerm
, /* Size of zTerm in bytes */
2823 int isPrefix
, /* True for a prefix search */
2824 int isScan
, /* True to scan from zTerm to EOF */
2825 Fts3MultiSegReader
*pCsr
/* Cursor object to populate */
2827 assert( iIndex
>=0 && iIndex
<p
->nIndex
);
2828 assert( iLevel
==FTS3_SEGCURSOR_ALL
2829 || iLevel
==FTS3_SEGCURSOR_PENDING
2832 assert( iLevel
<FTS3_SEGDIR_MAXLEVEL
);
2833 assert( FTS3_SEGCURSOR_ALL
<0 && FTS3_SEGCURSOR_PENDING
<0 );
2834 assert( isPrefix
==0 || isScan
==0 );
2836 memset(pCsr
, 0, sizeof(Fts3MultiSegReader
));
2837 return fts3SegReaderCursor(
2838 p
, iLangid
, iIndex
, iLevel
, zTerm
, nTerm
, isPrefix
, isScan
, pCsr
2843 ** In addition to its current configuration, have the Fts3MultiSegReader
2844 ** passed as the 4th argument also scan the doclist for term zTerm/nTerm.
2846 ** SQLITE_OK is returned if no error occurs, otherwise an SQLite error code.
2848 static int fts3SegReaderCursorAddZero(
2849 Fts3Table
*p
, /* FTS virtual table handle */
2851 const char *zTerm
, /* Term to scan doclist of */
2852 int nTerm
, /* Number of bytes in zTerm */
2853 Fts3MultiSegReader
*pCsr
/* Fts3MultiSegReader to modify */
2855 return fts3SegReaderCursor(p
,
2856 iLangid
, 0, FTS3_SEGCURSOR_ALL
, zTerm
, nTerm
, 0, 0,pCsr
2861 ** Open an Fts3MultiSegReader to scan the doclist for term zTerm/nTerm. Or,
2862 ** if isPrefix is true, to scan the doclist for all terms for which
2863 ** zTerm/nTerm is a prefix. If successful, return SQLITE_OK and write
2864 ** a pointer to the new Fts3MultiSegReader to *ppSegcsr. Otherwise, return
2865 ** an SQLite error code.
2867 ** It is the responsibility of the caller to free this object by eventually
2868 ** passing it to fts3SegReaderCursorFree()
2870 ** SQLITE_OK is returned if no error occurs, otherwise an SQLite error code.
2871 ** Output parameter *ppSegcsr is set to 0 if an error occurs.
2873 static int fts3TermSegReaderCursor(
2874 Fts3Cursor
*pCsr
, /* Virtual table cursor handle */
2875 const char *zTerm
, /* Term to query for */
2876 int nTerm
, /* Size of zTerm in bytes */
2877 int isPrefix
, /* True for a prefix search */
2878 Fts3MultiSegReader
**ppSegcsr
/* OUT: Allocated seg-reader cursor */
2880 Fts3MultiSegReader
*pSegcsr
; /* Object to allocate and return */
2881 int rc
= SQLITE_NOMEM
; /* Return code */
2883 pSegcsr
= sqlite3_malloc(sizeof(Fts3MultiSegReader
));
2886 int bFound
= 0; /* True once an index has been found */
2887 Fts3Table
*p
= (Fts3Table
*)pCsr
->base
.pVtab
;
2890 for(i
=1; bFound
==0 && i
<p
->nIndex
; i
++){
2891 if( p
->aIndex
[i
].nPrefix
==nTerm
){
2893 rc
= sqlite3Fts3SegReaderCursor(p
, pCsr
->iLangid
,
2894 i
, FTS3_SEGCURSOR_ALL
, zTerm
, nTerm
, 0, 0, pSegcsr
2896 pSegcsr
->bLookup
= 1;
2900 for(i
=1; bFound
==0 && i
<p
->nIndex
; i
++){
2901 if( p
->aIndex
[i
].nPrefix
==nTerm
+1 ){
2903 rc
= sqlite3Fts3SegReaderCursor(p
, pCsr
->iLangid
,
2904 i
, FTS3_SEGCURSOR_ALL
, zTerm
, nTerm
, 1, 0, pSegcsr
2906 if( rc
==SQLITE_OK
){
2907 rc
= fts3SegReaderCursorAddZero(
2908 p
, pCsr
->iLangid
, zTerm
, nTerm
, pSegcsr
2916 rc
= sqlite3Fts3SegReaderCursor(p
, pCsr
->iLangid
,
2917 0, FTS3_SEGCURSOR_ALL
, zTerm
, nTerm
, isPrefix
, 0, pSegcsr
2919 pSegcsr
->bLookup
= !isPrefix
;
2923 *ppSegcsr
= pSegcsr
;
2928 ** Free an Fts3MultiSegReader allocated by fts3TermSegReaderCursor().
2930 static void fts3SegReaderCursorFree(Fts3MultiSegReader
*pSegcsr
){
2931 sqlite3Fts3SegReaderFinish(pSegcsr
);
2932 sqlite3_free(pSegcsr
);
2936 ** This function retrieves the doclist for the specified term (or term
2937 ** prefix) from the database.
2939 static int fts3TermSelect(
2940 Fts3Table
*p
, /* Virtual table handle */
2941 Fts3PhraseToken
*pTok
, /* Token to query for */
2942 int iColumn
, /* Column to query (or -ve for all columns) */
2943 int *pnOut
, /* OUT: Size of buffer at *ppOut */
2944 char **ppOut
/* OUT: Malloced result buffer */
2946 int rc
; /* Return code */
2947 Fts3MultiSegReader
*pSegcsr
; /* Seg-reader cursor for this term */
2948 TermSelect tsc
; /* Object for pair-wise doclist merging */
2949 Fts3SegFilter filter
; /* Segment term filter configuration */
2951 pSegcsr
= pTok
->pSegcsr
;
2952 memset(&tsc
, 0, sizeof(TermSelect
));
2954 filter
.flags
= FTS3_SEGMENT_IGNORE_EMPTY
| FTS3_SEGMENT_REQUIRE_POS
2955 | (pTok
->isPrefix
? FTS3_SEGMENT_PREFIX
: 0)
2956 | (pTok
->bFirst
? FTS3_SEGMENT_FIRST
: 0)
2957 | (iColumn
<p
->nColumn
? FTS3_SEGMENT_COLUMN_FILTER
: 0);
2958 filter
.iCol
= iColumn
;
2959 filter
.zTerm
= pTok
->z
;
2960 filter
.nTerm
= pTok
->n
;
2962 rc
= sqlite3Fts3SegReaderStart(p
, pSegcsr
, &filter
);
2963 while( SQLITE_OK
==rc
2964 && SQLITE_ROW
==(rc
= sqlite3Fts3SegReaderStep(p
, pSegcsr
))
2966 rc
= fts3TermSelectMerge(p
, &tsc
, pSegcsr
->aDoclist
, pSegcsr
->nDoclist
);
2969 if( rc
==SQLITE_OK
){
2970 rc
= fts3TermSelectFinishMerge(p
, &tsc
);
2972 if( rc
==SQLITE_OK
){
2973 *ppOut
= tsc
.aaOutput
[0];
2974 *pnOut
= tsc
.anOutput
[0];
2977 for(i
=0; i
<SizeofArray(tsc
.aaOutput
); i
++){
2978 sqlite3_free(tsc
.aaOutput
[i
]);
2982 fts3SegReaderCursorFree(pSegcsr
);
2988 ** This function counts the total number of docids in the doclist stored
2989 ** in buffer aList[], size nList bytes.
2991 ** If the isPoslist argument is true, then it is assumed that the doclist
2992 ** contains a position-list following each docid. Otherwise, it is assumed
2993 ** that the doclist is simply a list of docids stored as delta encoded
2996 static int fts3DoclistCountDocids(char *aList
, int nList
){
2997 int nDoc
= 0; /* Return value */
2999 char *aEnd
= &aList
[nList
]; /* Pointer to one byte after EOF */
3000 char *p
= aList
; /* Cursor */
3003 while( (*p
++)&0x80 ); /* Skip docid varint */
3004 fts3PoslistCopy(0, &p
); /* Skip over position list */
3012 ** Advance the cursor to the next row in the %_content table that
3013 ** matches the search criteria. For a MATCH search, this will be
3014 ** the next row that matches. For a full-table scan, this will be
3015 ** simply the next row in the %_content table. For a docid lookup,
3016 ** this routine simply sets the EOF flag.
3018 ** Return SQLITE_OK if nothing goes wrong. SQLITE_OK is returned
3019 ** even if we reach end-of-file. The fts3EofMethod() will be called
3020 ** subsequently to determine whether or not an EOF was hit.
3022 static int fts3NextMethod(sqlite3_vtab_cursor
*pCursor
){
3024 Fts3Cursor
*pCsr
= (Fts3Cursor
*)pCursor
;
3025 if( pCsr
->eSearch
==FTS3_DOCID_SEARCH
|| pCsr
->eSearch
==FTS3_FULLSCAN_SEARCH
){
3026 if( SQLITE_ROW
!=sqlite3_step(pCsr
->pStmt
) ){
3028 rc
= sqlite3_reset(pCsr
->pStmt
);
3030 pCsr
->iPrevId
= sqlite3_column_int64(pCsr
->pStmt
, 0);
3034 rc
= fts3EvalNext((Fts3Cursor
*)pCursor
);
3036 assert( ((Fts3Table
*)pCsr
->base
.pVtab
)->pSegments
==0 );
3041 ** The following are copied from sqliteInt.h.
3043 ** Constants for the largest and smallest possible 64-bit signed integers.
3044 ** These macros are designed to work correctly on both 32-bit and 64-bit
3047 #ifndef SQLITE_AMALGAMATION
3048 # define LARGEST_INT64 (0xffffffff|(((sqlite3_int64)0x7fffffff)<<32))
3049 # define SMALLEST_INT64 (((sqlite3_int64)-1) - LARGEST_INT64)
3053 ** If the numeric type of argument pVal is "integer", then return it
3054 ** converted to a 64-bit signed integer. Otherwise, return a copy of
3055 ** the second parameter, iDefault.
3057 static sqlite3_int64
fts3DocidRange(sqlite3_value
*pVal
, i64 iDefault
){
3059 int eType
= sqlite3_value_numeric_type(pVal
);
3060 if( eType
==SQLITE_INTEGER
){
3061 return sqlite3_value_int64(pVal
);
3068 ** This is the xFilter interface for the virtual table. See
3069 ** the virtual table xFilter method documentation for additional
3072 ** If idxNum==FTS3_FULLSCAN_SEARCH then do a full table scan against
3073 ** the %_content table.
3075 ** If idxNum==FTS3_DOCID_SEARCH then do a docid lookup for a single entry
3076 ** in the %_content table.
3078 ** If idxNum>=FTS3_FULLTEXT_SEARCH then use the full text index. The
3079 ** column on the left-hand side of the MATCH operator is column
3080 ** number idxNum-FTS3_FULLTEXT_SEARCH, 0 indexed. argv[0] is the right-hand
3081 ** side of the MATCH operator.
3083 static int fts3FilterMethod(
3084 sqlite3_vtab_cursor
*pCursor
, /* The cursor used for this query */
3085 int idxNum
, /* Strategy index */
3086 const char *idxStr
, /* Unused */
3087 int nVal
, /* Number of elements in apVal */
3088 sqlite3_value
**apVal
/* Arguments for the indexing scheme */
3091 char *zSql
; /* SQL statement used to access %_content */
3093 Fts3Table
*p
= (Fts3Table
*)pCursor
->pVtab
;
3094 Fts3Cursor
*pCsr
= (Fts3Cursor
*)pCursor
;
3096 sqlite3_value
*pCons
= 0; /* The MATCH or rowid constraint, if any */
3097 sqlite3_value
*pLangid
= 0; /* The "langid = ?" constraint, if any */
3098 sqlite3_value
*pDocidGe
= 0; /* The "docid >= ?" constraint, if any */
3099 sqlite3_value
*pDocidLe
= 0; /* The "docid <= ?" constraint, if any */
3102 UNUSED_PARAMETER(idxStr
);
3103 UNUSED_PARAMETER(nVal
);
3105 eSearch
= (idxNum
& 0x0000FFFF);
3106 assert( eSearch
>=0 && eSearch
<=(FTS3_FULLTEXT_SEARCH
+p
->nColumn
) );
3107 assert( p
->pSegments
==0 );
3109 /* Collect arguments into local variables */
3111 if( eSearch
!=FTS3_FULLSCAN_SEARCH
) pCons
= apVal
[iIdx
++];
3112 if( idxNum
& FTS3_HAVE_LANGID
) pLangid
= apVal
[iIdx
++];
3113 if( idxNum
& FTS3_HAVE_DOCID_GE
) pDocidGe
= apVal
[iIdx
++];
3114 if( idxNum
& FTS3_HAVE_DOCID_LE
) pDocidLe
= apVal
[iIdx
++];
3115 assert( iIdx
==nVal
);
3117 /* In case the cursor has been used before, clear it now. */
3118 sqlite3_finalize(pCsr
->pStmt
);
3119 sqlite3_free(pCsr
->aDoclist
);
3120 sqlite3Fts3ExprFree(pCsr
->pExpr
);
3121 memset(&pCursor
[1], 0, sizeof(Fts3Cursor
)-sizeof(sqlite3_vtab_cursor
));
3123 /* Set the lower and upper bounds on docids to return */
3124 pCsr
->iMinDocid
= fts3DocidRange(pDocidGe
, SMALLEST_INT64
);
3125 pCsr
->iMaxDocid
= fts3DocidRange(pDocidLe
, LARGEST_INT64
);
3128 pCsr
->bDesc
= (idxStr
[0]=='D');
3130 pCsr
->bDesc
= p
->bDescIdx
;
3132 pCsr
->eSearch
= (i16
)eSearch
;
3134 if( eSearch
!=FTS3_DOCID_SEARCH
&& eSearch
!=FTS3_FULLSCAN_SEARCH
){
3135 int iCol
= eSearch
-FTS3_FULLTEXT_SEARCH
;
3136 const char *zQuery
= (const char *)sqlite3_value_text(pCons
);
3138 if( zQuery
==0 && sqlite3_value_type(pCons
)!=SQLITE_NULL
){
3139 return SQLITE_NOMEM
;
3143 if( pLangid
) pCsr
->iLangid
= sqlite3_value_int(pLangid
);
3145 assert( p
->base
.zErrMsg
==0 );
3146 rc
= sqlite3Fts3ExprParse(p
->pTokenizer
, pCsr
->iLangid
,
3147 p
->azColumn
, p
->bFts4
, p
->nColumn
, iCol
, zQuery
, -1, &pCsr
->pExpr
,
3150 if( rc
!=SQLITE_OK
){
3154 rc
= fts3EvalStart(pCsr
);
3155 sqlite3Fts3SegmentsClose(p
);
3156 if( rc
!=SQLITE_OK
) return rc
;
3157 pCsr
->pNextId
= pCsr
->aDoclist
;
3161 /* Compile a SELECT statement for this cursor. For a full-table-scan, the
3162 ** statement loops through all rows of the %_content table. For a
3163 ** full-text query or docid lookup, the statement retrieves a single
3166 if( eSearch
==FTS3_FULLSCAN_SEARCH
){
3167 zSql
= sqlite3_mprintf(
3168 "SELECT %s ORDER BY rowid %s",
3169 p
->zReadExprlist
, (pCsr
->bDesc
? "DESC" : "ASC")
3172 rc
= sqlite3_prepare_v2(p
->db
, zSql
, -1, &pCsr
->pStmt
, 0);
3177 }else if( eSearch
==FTS3_DOCID_SEARCH
){
3178 rc
= fts3CursorSeekStmt(pCsr
, &pCsr
->pStmt
);
3179 if( rc
==SQLITE_OK
){
3180 rc
= sqlite3_bind_value(pCsr
->pStmt
, 1, pCons
);
3183 if( rc
!=SQLITE_OK
) return rc
;
3185 return fts3NextMethod(pCursor
);
3189 ** This is the xEof method of the virtual table. SQLite calls this
3190 ** routine to find out if it has reached the end of a result set.
3192 static int fts3EofMethod(sqlite3_vtab_cursor
*pCursor
){
3193 return ((Fts3Cursor
*)pCursor
)->isEof
;
3197 ** This is the xRowid method. The SQLite core calls this routine to
3198 ** retrieve the rowid for the current row of the result set. fts3
3199 ** exposes %_content.docid as the rowid for the virtual table. The
3200 ** rowid should be written to *pRowid.
3202 static int fts3RowidMethod(sqlite3_vtab_cursor
*pCursor
, sqlite_int64
*pRowid
){
3203 Fts3Cursor
*pCsr
= (Fts3Cursor
*) pCursor
;
3204 *pRowid
= pCsr
->iPrevId
;
3209 ** This is the xColumn method, called by SQLite to request a value from
3210 ** the row that the supplied cursor currently points to.
3214 ** (iCol < p->nColumn) -> The value of the iCol'th user column.
3215 ** (iCol == p->nColumn) -> Magic column with the same name as the table.
3216 ** (iCol == p->nColumn+1) -> Docid column
3217 ** (iCol == p->nColumn+2) -> Langid column
3219 static int fts3ColumnMethod(
3220 sqlite3_vtab_cursor
*pCursor
, /* Cursor to retrieve value from */
3221 sqlite3_context
*pCtx
, /* Context for sqlite3_result_xxx() calls */
3222 int iCol
/* Index of column to read value from */
3224 int rc
= SQLITE_OK
; /* Return Code */
3225 Fts3Cursor
*pCsr
= (Fts3Cursor
*) pCursor
;
3226 Fts3Table
*p
= (Fts3Table
*)pCursor
->pVtab
;
3228 /* The column value supplied by SQLite must be in range. */
3229 assert( iCol
>=0 && iCol
<=p
->nColumn
+2 );
3231 if( iCol
==p
->nColumn
+1 ){
3232 /* This call is a request for the "docid" column. Since "docid" is an
3233 ** alias for "rowid", use the xRowid() method to obtain the value.
3235 sqlite3_result_int64(pCtx
, pCsr
->iPrevId
);
3236 }else if( iCol
==p
->nColumn
){
3237 /* The extra column whose name is the same as the table.
3238 ** Return a blob which is a pointer to the cursor. */
3239 sqlite3_result_blob(pCtx
, &pCsr
, sizeof(pCsr
), SQLITE_TRANSIENT
);
3240 }else if( iCol
==p
->nColumn
+2 && pCsr
->pExpr
){
3241 sqlite3_result_int64(pCtx
, pCsr
->iLangid
);
3243 /* The requested column is either a user column (one that contains
3244 ** indexed data), or the language-id column. */
3245 rc
= fts3CursorSeek(0, pCsr
);
3247 if( rc
==SQLITE_OK
){
3248 if( iCol
==p
->nColumn
+2 ){
3250 if( p
->zLanguageid
){
3251 iLangid
= sqlite3_column_int(pCsr
->pStmt
, p
->nColumn
+1);
3253 sqlite3_result_int(pCtx
, iLangid
);
3254 }else if( sqlite3_data_count(pCsr
->pStmt
)>(iCol
+1) ){
3255 sqlite3_result_value(pCtx
, sqlite3_column_value(pCsr
->pStmt
, iCol
+1));
3260 assert( ((Fts3Table
*)pCsr
->base
.pVtab
)->pSegments
==0 );
3265 ** This function is the implementation of the xUpdate callback used by
3266 ** FTS3 virtual tables. It is invoked by SQLite each time a row is to be
3267 ** inserted, updated or deleted.
3269 static int fts3UpdateMethod(
3270 sqlite3_vtab
*pVtab
, /* Virtual table handle */
3271 int nArg
, /* Size of argument array */
3272 sqlite3_value
**apVal
, /* Array of arguments */
3273 sqlite_int64
*pRowid
/* OUT: The affected (or effected) rowid */
3275 return sqlite3Fts3UpdateMethod(pVtab
, nArg
, apVal
, pRowid
);
3279 ** Implementation of xSync() method. Flush the contents of the pending-terms
3280 ** hash-table to the database.
3282 static int fts3SyncMethod(sqlite3_vtab
*pVtab
){
3284 /* Following an incremental-merge operation, assuming that the input
3285 ** segments are not completely consumed (the usual case), they are updated
3286 ** in place to remove the entries that have already been merged. This
3287 ** involves updating the leaf block that contains the smallest unmerged
3288 ** entry and each block (if any) between the leaf and the root node. So
3289 ** if the height of the input segment b-trees is N, and input segments
3290 ** are merged eight at a time, updating the input segments at the end
3291 ** of an incremental-merge requires writing (8*(1+N)) blocks. N is usually
3292 ** small - often between 0 and 2. So the overhead of the incremental
3293 ** merge is somewhere between 8 and 24 blocks. To avoid this overhead
3294 ** dwarfing the actual productive work accomplished, the incremental merge
3295 ** is only attempted if it will write at least 64 leaf blocks. Hence
3298 ** Of course, updating the input segments also involves deleting a bunch
3299 ** of blocks from the segments table. But this is not considered overhead
3300 ** as it would also be required by a crisis-merge that used the same input
3303 const u32 nMinMerge
= 64; /* Minimum amount of incr-merge work to do */
3305 Fts3Table
*p
= (Fts3Table
*)pVtab
;
3306 int rc
= sqlite3Fts3PendingTermsFlush(p
);
3308 if( rc
==SQLITE_OK
&& p
->bAutoincrmerge
==1 && p
->nLeafAdd
>(nMinMerge
/16) ){
3309 int mxLevel
= 0; /* Maximum relative level value in db */
3310 int A
; /* Incr-merge parameter A */
3312 rc
= sqlite3Fts3MaxLevel(p
, &mxLevel
);
3313 assert( rc
==SQLITE_OK
|| mxLevel
==0 );
3314 A
= p
->nLeafAdd
* mxLevel
;
3316 if( A
>(int)nMinMerge
) rc
= sqlite3Fts3Incrmerge(p
, A
, 8);
3318 sqlite3Fts3SegmentsClose(p
);
3323 ** Implementation of xBegin() method. This is a no-op.
3325 static int fts3BeginMethod(sqlite3_vtab
*pVtab
){
3326 Fts3Table
*p
= (Fts3Table
*)pVtab
;
3327 UNUSED_PARAMETER(pVtab
);
3328 assert( p
->pSegments
==0 );
3329 assert( p
->nPendingData
==0 );
3330 assert( p
->inTransaction
!=1 );
3331 TESTONLY( p
->inTransaction
= 1 );
3332 TESTONLY( p
->mxSavepoint
= -1; );
3338 ** Implementation of xCommit() method. This is a no-op. The contents of
3339 ** the pending-terms hash-table have already been flushed into the database
3340 ** by fts3SyncMethod().
3342 static int fts3CommitMethod(sqlite3_vtab
*pVtab
){
3343 TESTONLY( Fts3Table
*p
= (Fts3Table
*)pVtab
);
3344 UNUSED_PARAMETER(pVtab
);
3345 assert( p
->nPendingData
==0 );
3346 assert( p
->inTransaction
!=0 );
3347 assert( p
->pSegments
==0 );
3348 TESTONLY( p
->inTransaction
= 0 );
3349 TESTONLY( p
->mxSavepoint
= -1; );
3354 ** Implementation of xRollback(). Discard the contents of the pending-terms
3355 ** hash-table. Any changes made to the database are reverted by SQLite.
3357 static int fts3RollbackMethod(sqlite3_vtab
*pVtab
){
3358 Fts3Table
*p
= (Fts3Table
*)pVtab
;
3359 sqlite3Fts3PendingTermsClear(p
);
3360 assert( p
->inTransaction
!=0 );
3361 TESTONLY( p
->inTransaction
= 0 );
3362 TESTONLY( p
->mxSavepoint
= -1; );
3367 ** When called, *ppPoslist must point to the byte immediately following the
3368 ** end of a position-list. i.e. ( (*ppPoslist)[-1]==POS_END ). This function
3369 ** moves *ppPoslist so that it instead points to the first byte of the
3370 ** same position list.
3372 static void fts3ReversePoslist(char *pStart
, char **ppPoslist
){
3373 char *p
= &(*ppPoslist
)[-2];
3376 while( p
>pStart
&& (c
=*p
--)==0 );
3377 while( p
>pStart
&& (*p
& 0x80) | c
){
3380 if( p
>pStart
){ p
= &p
[2]; }
3386 ** Helper function used by the implementation of the overloaded snippet(),
3387 ** offsets() and optimize() SQL functions.
3389 ** If the value passed as the third argument is a blob of size
3390 ** sizeof(Fts3Cursor*), then the blob contents are copied to the
3391 ** output variable *ppCsr and SQLITE_OK is returned. Otherwise, an error
3392 ** message is written to context pContext and SQLITE_ERROR returned. The
3393 ** string passed via zFunc is used as part of the error message.
3395 static int fts3FunctionArg(
3396 sqlite3_context
*pContext
, /* SQL function call context */
3397 const char *zFunc
, /* Function name */
3398 sqlite3_value
*pVal
, /* argv[0] passed to function */
3399 Fts3Cursor
**ppCsr
/* OUT: Store cursor handle here */
3402 if( sqlite3_value_type(pVal
)!=SQLITE_BLOB
3403 || sqlite3_value_bytes(pVal
)!=sizeof(Fts3Cursor
*)
3405 char *zErr
= sqlite3_mprintf("illegal first argument to %s", zFunc
);
3406 sqlite3_result_error(pContext
, zErr
, -1);
3408 return SQLITE_ERROR
;
3410 memcpy(&pRet
, sqlite3_value_blob(pVal
), sizeof(Fts3Cursor
*));
3416 ** Implementation of the snippet() function for FTS3
3418 static void fts3SnippetFunc(
3419 sqlite3_context
*pContext
, /* SQLite function call context */
3420 int nVal
, /* Size of apVal[] array */
3421 sqlite3_value
**apVal
/* Array of arguments */
3423 Fts3Cursor
*pCsr
; /* Cursor handle passed through apVal[0] */
3424 const char *zStart
= "<b>";
3425 const char *zEnd
= "</b>";
3426 const char *zEllipsis
= "<b>...</b>";
3428 int nToken
= 15; /* Default number of tokens in snippet */
3430 /* There must be at least one argument passed to this function (otherwise
3431 ** the non-overloaded version would have been called instead of this one).
3436 sqlite3_result_error(pContext
,
3437 "wrong number of arguments to function snippet()", -1);
3440 if( fts3FunctionArg(pContext
, "snippet", apVal
[0], &pCsr
) ) return;
3443 case 6: nToken
= sqlite3_value_int(apVal
[5]);
3444 case 5: iCol
= sqlite3_value_int(apVal
[4]);
3445 case 4: zEllipsis
= (const char*)sqlite3_value_text(apVal
[3]);
3446 case 3: zEnd
= (const char*)sqlite3_value_text(apVal
[2]);
3447 case 2: zStart
= (const char*)sqlite3_value_text(apVal
[1]);
3449 if( !zEllipsis
|| !zEnd
|| !zStart
){
3450 sqlite3_result_error_nomem(pContext
);
3451 }else if( SQLITE_OK
==fts3CursorSeek(pContext
, pCsr
) ){
3452 sqlite3Fts3Snippet(pContext
, pCsr
, zStart
, zEnd
, zEllipsis
, iCol
, nToken
);
3457 ** Implementation of the offsets() function for FTS3
3459 static void fts3OffsetsFunc(
3460 sqlite3_context
*pContext
, /* SQLite function call context */
3461 int nVal
, /* Size of argument array */
3462 sqlite3_value
**apVal
/* Array of arguments */
3464 Fts3Cursor
*pCsr
; /* Cursor handle passed through apVal[0] */
3466 UNUSED_PARAMETER(nVal
);
3469 if( fts3FunctionArg(pContext
, "offsets", apVal
[0], &pCsr
) ) return;
3471 if( SQLITE_OK
==fts3CursorSeek(pContext
, pCsr
) ){
3472 sqlite3Fts3Offsets(pContext
, pCsr
);
3477 ** Implementation of the special optimize() function for FTS3. This
3478 ** function merges all segments in the database to a single segment.
3479 ** Example usage is:
3481 ** SELECT optimize(t) FROM t LIMIT 1;
3483 ** where 't' is the name of an FTS3 table.
3485 static void fts3OptimizeFunc(
3486 sqlite3_context
*pContext
, /* SQLite function call context */
3487 int nVal
, /* Size of argument array */
3488 sqlite3_value
**apVal
/* Array of arguments */
3490 int rc
; /* Return code */
3491 Fts3Table
*p
; /* Virtual table handle */
3492 Fts3Cursor
*pCursor
; /* Cursor handle passed through apVal[0] */
3494 UNUSED_PARAMETER(nVal
);
3497 if( fts3FunctionArg(pContext
, "optimize", apVal
[0], &pCursor
) ) return;
3498 p
= (Fts3Table
*)pCursor
->base
.pVtab
;
3501 rc
= sqlite3Fts3Optimize(p
);
3505 sqlite3_result_text(pContext
, "Index optimized", -1, SQLITE_STATIC
);
3508 sqlite3_result_text(pContext
, "Index already optimal", -1, SQLITE_STATIC
);
3511 sqlite3_result_error_code(pContext
, rc
);
3517 ** Implementation of the matchinfo() function for FTS3
3519 static void fts3MatchinfoFunc(
3520 sqlite3_context
*pContext
, /* SQLite function call context */
3521 int nVal
, /* Size of argument array */
3522 sqlite3_value
**apVal
/* Array of arguments */
3524 Fts3Cursor
*pCsr
; /* Cursor handle passed through apVal[0] */
3525 assert( nVal
==1 || nVal
==2 );
3526 if( SQLITE_OK
==fts3FunctionArg(pContext
, "matchinfo", apVal
[0], &pCsr
) ){
3527 const char *zArg
= 0;
3529 zArg
= (const char *)sqlite3_value_text(apVal
[1]);
3531 sqlite3Fts3Matchinfo(pContext
, pCsr
, zArg
);
3536 ** This routine implements the xFindFunction method for the FTS3
3539 static int fts3FindFunctionMethod(
3540 sqlite3_vtab
*pVtab
, /* Virtual table handle */
3541 int nArg
, /* Number of SQL function arguments */
3542 const char *zName
, /* Name of SQL function */
3543 void (**pxFunc
)(sqlite3_context
*,int,sqlite3_value
**), /* OUT: Result */
3544 void **ppArg
/* Unused */
3548 void (*xFunc
)(sqlite3_context
*,int,sqlite3_value
**);
3550 { "snippet", fts3SnippetFunc
},
3551 { "offsets", fts3OffsetsFunc
},
3552 { "optimize", fts3OptimizeFunc
},
3553 { "matchinfo", fts3MatchinfoFunc
},
3555 int i
; /* Iterator variable */
3557 UNUSED_PARAMETER(pVtab
);
3558 UNUSED_PARAMETER(nArg
);
3559 UNUSED_PARAMETER(ppArg
);
3561 for(i
=0; i
<SizeofArray(aOverload
); i
++){
3562 if( strcmp(zName
, aOverload
[i
].zName
)==0 ){
3563 *pxFunc
= aOverload
[i
].xFunc
;
3568 /* No function of the specified name was found. Return 0. */
3573 ** Implementation of FTS3 xRename method. Rename an fts3 table.
3575 static int fts3RenameMethod(
3576 sqlite3_vtab
*pVtab
, /* Virtual table handle */
3577 const char *zName
/* New name of table */
3579 Fts3Table
*p
= (Fts3Table
*)pVtab
;
3580 sqlite3
*db
= p
->db
; /* Database connection */
3581 int rc
; /* Return Code */
3583 /* As it happens, the pending terms table is always empty here. This is
3584 ** because an "ALTER TABLE RENAME TABLE" statement inside a transaction
3585 ** always opens a savepoint transaction. And the xSavepoint() method
3586 ** flushes the pending terms table. But leave the (no-op) call to
3587 ** PendingTermsFlush() in in case that changes.
3589 assert( p
->nPendingData
==0 );
3590 rc
= sqlite3Fts3PendingTermsFlush(p
);
3592 if( p
->zContentTbl
==0 ){
3594 "ALTER TABLE %Q.'%q_content' RENAME TO '%q_content';",
3595 p
->zDb
, p
->zName
, zName
3599 if( p
->bHasDocsize
){
3601 "ALTER TABLE %Q.'%q_docsize' RENAME TO '%q_docsize';",
3602 p
->zDb
, p
->zName
, zName
3607 "ALTER TABLE %Q.'%q_stat' RENAME TO '%q_stat';",
3608 p
->zDb
, p
->zName
, zName
3612 "ALTER TABLE %Q.'%q_segments' RENAME TO '%q_segments';",
3613 p
->zDb
, p
->zName
, zName
3616 "ALTER TABLE %Q.'%q_segdir' RENAME TO '%q_segdir';",
3617 p
->zDb
, p
->zName
, zName
3623 ** The xSavepoint() method.
3625 ** Flush the contents of the pending-terms table to disk.
3627 static int fts3SavepointMethod(sqlite3_vtab
*pVtab
, int iSavepoint
){
3629 UNUSED_PARAMETER(iSavepoint
);
3630 assert( ((Fts3Table
*)pVtab
)->inTransaction
);
3631 assert( ((Fts3Table
*)pVtab
)->mxSavepoint
< iSavepoint
);
3632 TESTONLY( ((Fts3Table
*)pVtab
)->mxSavepoint
= iSavepoint
);
3633 if( ((Fts3Table
*)pVtab
)->bIgnoreSavepoint
==0 ){
3634 rc
= fts3SyncMethod(pVtab
);
3640 ** The xRelease() method.
3644 static int fts3ReleaseMethod(sqlite3_vtab
*pVtab
, int iSavepoint
){
3645 TESTONLY( Fts3Table
*p
= (Fts3Table
*)pVtab
);
3646 UNUSED_PARAMETER(iSavepoint
);
3647 UNUSED_PARAMETER(pVtab
);
3648 assert( p
->inTransaction
);
3649 assert( p
->mxSavepoint
>= iSavepoint
);
3650 TESTONLY( p
->mxSavepoint
= iSavepoint
-1 );
3655 ** The xRollbackTo() method.
3657 ** Discard the contents of the pending terms table.
3659 static int fts3RollbackToMethod(sqlite3_vtab
*pVtab
, int iSavepoint
){
3660 Fts3Table
*p
= (Fts3Table
*)pVtab
;
3661 UNUSED_PARAMETER(iSavepoint
);
3662 assert( p
->inTransaction
);
3663 assert( p
->mxSavepoint
>= iSavepoint
);
3664 TESTONLY( p
->mxSavepoint
= iSavepoint
);
3665 sqlite3Fts3PendingTermsClear(p
);
3669 static const sqlite3_module fts3Module
= {
3671 /* xCreate */ fts3CreateMethod
,
3672 /* xConnect */ fts3ConnectMethod
,
3673 /* xBestIndex */ fts3BestIndexMethod
,
3674 /* xDisconnect */ fts3DisconnectMethod
,
3675 /* xDestroy */ fts3DestroyMethod
,
3676 /* xOpen */ fts3OpenMethod
,
3677 /* xClose */ fts3CloseMethod
,
3678 /* xFilter */ fts3FilterMethod
,
3679 /* xNext */ fts3NextMethod
,
3680 /* xEof */ fts3EofMethod
,
3681 /* xColumn */ fts3ColumnMethod
,
3682 /* xRowid */ fts3RowidMethod
,
3683 /* xUpdate */ fts3UpdateMethod
,
3684 /* xBegin */ fts3BeginMethod
,
3685 /* xSync */ fts3SyncMethod
,
3686 /* xCommit */ fts3CommitMethod
,
3687 /* xRollback */ fts3RollbackMethod
,
3688 /* xFindFunction */ fts3FindFunctionMethod
,
3689 /* xRename */ fts3RenameMethod
,
3690 /* xSavepoint */ fts3SavepointMethod
,
3691 /* xRelease */ fts3ReleaseMethod
,
3692 /* xRollbackTo */ fts3RollbackToMethod
,
3696 ** This function is registered as the module destructor (called when an
3697 ** FTS3 enabled database connection is closed). It frees the memory
3698 ** allocated for the tokenizer hash table.
3700 static void hashDestroy(void *p
){
3701 Fts3Hash
*pHash
= (Fts3Hash
*)p
;
3702 sqlite3Fts3HashClear(pHash
);
3703 sqlite3_free(pHash
);
3707 ** The fts3 built-in tokenizers - "simple", "porter" and "icu"- are
3708 ** implemented in files fts3_tokenizer1.c, fts3_porter.c and fts3_icu.c
3709 ** respectively. The following three forward declarations are for functions
3710 ** declared in these files used to retrieve the respective implementations.
3712 ** Calling sqlite3Fts3SimpleTokenizerModule() sets the value pointed
3713 ** to by the argument to point to the "simple" tokenizer implementation.
3716 void sqlite3Fts3SimpleTokenizerModule(sqlite3_tokenizer_module
const**ppModule
);
3717 void sqlite3Fts3PorterTokenizerModule(sqlite3_tokenizer_module
const**ppModule
);
3718 #ifdef SQLITE_ENABLE_FTS4_UNICODE61
3719 void sqlite3Fts3UnicodeTokenizer(sqlite3_tokenizer_module
const**ppModule
);
3721 #ifdef SQLITE_ENABLE_ICU
3722 void sqlite3Fts3IcuTokenizerModule(sqlite3_tokenizer_module
const**ppModule
);
3726 ** Initialize the fts3 extension. If this extension is built as part
3727 ** of the sqlite library, then this function is called directly by
3728 ** SQLite. If fts3 is built as a dynamically loadable extension, this
3729 ** function is called by the sqlite3_extension_init() entry point.
3731 int sqlite3Fts3Init(sqlite3
*db
){
3733 Fts3Hash
*pHash
= 0;
3734 const sqlite3_tokenizer_module
*pSimple
= 0;
3735 const sqlite3_tokenizer_module
*pPorter
= 0;
3736 #ifdef SQLITE_ENABLE_FTS4_UNICODE61
3737 const sqlite3_tokenizer_module
*pUnicode
= 0;
3740 #ifdef SQLITE_ENABLE_ICU
3741 const sqlite3_tokenizer_module
*pIcu
= 0;
3742 sqlite3Fts3IcuTokenizerModule(&pIcu
);
3745 #ifdef SQLITE_ENABLE_FTS4_UNICODE61
3746 sqlite3Fts3UnicodeTokenizer(&pUnicode
);
3750 rc
= sqlite3Fts3InitTerm(db
);
3751 if( rc
!=SQLITE_OK
) return rc
;
3754 rc
= sqlite3Fts3InitAux(db
);
3755 if( rc
!=SQLITE_OK
) return rc
;
3757 sqlite3Fts3SimpleTokenizerModule(&pSimple
);
3758 sqlite3Fts3PorterTokenizerModule(&pPorter
);
3760 /* Allocate and initialize the hash-table used to store tokenizers. */
3761 pHash
= sqlite3_malloc(sizeof(Fts3Hash
));
3765 sqlite3Fts3HashInit(pHash
, FTS3_HASH_STRING
, 1);
3768 /* Load the built-in tokenizers into the hash table */
3769 if( rc
==SQLITE_OK
){
3770 if( sqlite3Fts3HashInsert(pHash
, "simple", 7, (void *)pSimple
)
3771 || sqlite3Fts3HashInsert(pHash
, "porter", 7, (void *)pPorter
)
3773 #ifdef SQLITE_ENABLE_FTS4_UNICODE61
3774 || sqlite3Fts3HashInsert(pHash
, "unicode61", 10, (void *)pUnicode
)
3776 #ifdef SQLITE_ENABLE_ICU
3777 || (pIcu
&& sqlite3Fts3HashInsert(pHash
, "icu", 4, (void *)pIcu
))
3785 if( rc
==SQLITE_OK
){
3786 rc
= sqlite3Fts3ExprInitTestInterface(db
);
3790 /* Create the virtual table wrapper around the hash-table and overload
3791 ** the two scalar functions. If this is successful, register the
3792 ** module with sqlite.
3795 && SQLITE_OK
==(rc
= sqlite3Fts3InitHashTable(db
, pHash
, "fts3_tokenizer"))
3796 && SQLITE_OK
==(rc
= sqlite3_overload_function(db
, "snippet", -1))
3797 && SQLITE_OK
==(rc
= sqlite3_overload_function(db
, "offsets", 1))
3798 && SQLITE_OK
==(rc
= sqlite3_overload_function(db
, "matchinfo", 1))
3799 && SQLITE_OK
==(rc
= sqlite3_overload_function(db
, "matchinfo", 2))
3800 && SQLITE_OK
==(rc
= sqlite3_overload_function(db
, "optimize", 1))
3802 rc
= sqlite3_create_module_v2(
3803 db
, "fts3", &fts3Module
, (void *)pHash
, hashDestroy
3805 if( rc
==SQLITE_OK
){
3806 rc
= sqlite3_create_module_v2(
3807 db
, "fts4", &fts3Module
, (void *)pHash
, 0
3810 if( rc
==SQLITE_OK
){
3811 rc
= sqlite3Fts3InitTok(db
, (void *)pHash
);
3817 /* An error has occurred. Delete the hash table and return the error code. */
3818 assert( rc
!=SQLITE_OK
);
3820 sqlite3Fts3HashClear(pHash
);
3821 sqlite3_free(pHash
);
3827 ** Allocate an Fts3MultiSegReader for each token in the expression headed
3830 ** An Fts3SegReader object is a cursor that can seek or scan a range of
3831 ** entries within a single segment b-tree. An Fts3MultiSegReader uses multiple
3832 ** Fts3SegReader objects internally to provide an interface to seek or scan
3833 ** within the union of all segments of a b-tree. Hence the name.
3835 ** If the allocated Fts3MultiSegReader just seeks to a single entry in a
3836 ** segment b-tree (if the term is not a prefix or it is a prefix for which
3837 ** there exists prefix b-tree of the right length) then it may be traversed
3838 ** and merged incrementally. Otherwise, it has to be merged into an in-memory
3839 ** doclist and then traversed.
3841 static void fts3EvalAllocateReaders(
3842 Fts3Cursor
*pCsr
, /* FTS cursor handle */
3843 Fts3Expr
*pExpr
, /* Allocate readers for this expression */
3844 int *pnToken
, /* OUT: Total number of tokens in phrase. */
3845 int *pnOr
, /* OUT: Total number of OR nodes in expr. */
3846 int *pRc
/* IN/OUT: Error code */
3848 if( pExpr
&& SQLITE_OK
==*pRc
){
3849 if( pExpr
->eType
==FTSQUERY_PHRASE
){
3851 int nToken
= pExpr
->pPhrase
->nToken
;
3853 for(i
=0; i
<nToken
; i
++){
3854 Fts3PhraseToken
*pToken
= &pExpr
->pPhrase
->aToken
[i
];
3855 int rc
= fts3TermSegReaderCursor(pCsr
,
3856 pToken
->z
, pToken
->n
, pToken
->isPrefix
, &pToken
->pSegcsr
3858 if( rc
!=SQLITE_OK
){
3863 assert( pExpr
->pPhrase
->iDoclistToken
==0 );
3864 pExpr
->pPhrase
->iDoclistToken
= -1;
3866 *pnOr
+= (pExpr
->eType
==FTSQUERY_OR
);
3867 fts3EvalAllocateReaders(pCsr
, pExpr
->pLeft
, pnToken
, pnOr
, pRc
);
3868 fts3EvalAllocateReaders(pCsr
, pExpr
->pRight
, pnToken
, pnOr
, pRc
);
3874 ** Arguments pList/nList contain the doclist for token iToken of phrase p.
3875 ** It is merged into the main doclist stored in p->doclist.aAll/nAll.
3877 ** This function assumes that pList points to a buffer allocated using
3878 ** sqlite3_malloc(). This function takes responsibility for eventually
3879 ** freeing the buffer.
3881 static void fts3EvalPhraseMergeToken(
3882 Fts3Table
*pTab
, /* FTS Table pointer */
3883 Fts3Phrase
*p
, /* Phrase to merge pList/nList into */
3884 int iToken
, /* Token pList/nList corresponds to */
3885 char *pList
, /* Pointer to doclist */
3886 int nList
/* Number of bytes in pList */
3888 assert( iToken
!=p
->iDoclistToken
);
3891 sqlite3_free(p
->doclist
.aAll
);
3892 p
->doclist
.aAll
= 0;
3893 p
->doclist
.nAll
= 0;
3896 else if( p
->iDoclistToken
<0 ){
3897 p
->doclist
.aAll
= pList
;
3898 p
->doclist
.nAll
= nList
;
3901 else if( p
->doclist
.aAll
==0 ){
3902 sqlite3_free(pList
);
3912 if( p
->iDoclistToken
<iToken
){
3913 pLeft
= p
->doclist
.aAll
;
3914 nLeft
= p
->doclist
.nAll
;
3917 nDiff
= iToken
- p
->iDoclistToken
;
3919 pRight
= p
->doclist
.aAll
;
3920 nRight
= p
->doclist
.nAll
;
3923 nDiff
= p
->iDoclistToken
- iToken
;
3926 fts3DoclistPhraseMerge(pTab
->bDescIdx
, nDiff
, pLeft
, nLeft
, pRight
,&nRight
);
3927 sqlite3_free(pLeft
);
3928 p
->doclist
.aAll
= pRight
;
3929 p
->doclist
.nAll
= nRight
;
3932 if( iToken
>p
->iDoclistToken
) p
->iDoclistToken
= iToken
;
3936 ** Load the doclist for phrase p into p->doclist.aAll/nAll. The loaded doclist
3937 ** does not take deferred tokens into account.
3939 ** SQLITE_OK is returned if no error occurs, otherwise an SQLite error code.
3941 static int fts3EvalPhraseLoad(
3942 Fts3Cursor
*pCsr
, /* FTS Cursor handle */
3943 Fts3Phrase
*p
/* Phrase object */
3945 Fts3Table
*pTab
= (Fts3Table
*)pCsr
->base
.pVtab
;
3949 for(iToken
=0; rc
==SQLITE_OK
&& iToken
<p
->nToken
; iToken
++){
3950 Fts3PhraseToken
*pToken
= &p
->aToken
[iToken
];
3951 assert( pToken
->pDeferred
==0 || pToken
->pSegcsr
==0 );
3953 if( pToken
->pSegcsr
){
3956 rc
= fts3TermSelect(pTab
, pToken
, p
->iColumn
, &nThis
, &pThis
);
3957 if( rc
==SQLITE_OK
){
3958 fts3EvalPhraseMergeToken(pTab
, p
, iToken
, pThis
, nThis
);
3961 assert( pToken
->pSegcsr
==0 );
3968 ** This function is called on each phrase after the position lists for
3969 ** any deferred tokens have been loaded into memory. It updates the phrases
3970 ** current position list to include only those positions that are really
3971 ** instances of the phrase (after considering deferred tokens). If this
3972 ** means that the phrase does not appear in the current row, doclist.pList
3973 ** and doclist.nList are both zeroed.
3975 ** SQLITE_OK is returned if no error occurs, otherwise an SQLite error code.
3977 static int fts3EvalDeferredPhrase(Fts3Cursor
*pCsr
, Fts3Phrase
*pPhrase
){
3978 int iToken
; /* Used to iterate through phrase tokens */
3979 char *aPoslist
= 0; /* Position list for deferred tokens */
3980 int nPoslist
= 0; /* Number of bytes in aPoslist */
3981 int iPrev
= -1; /* Token number of previous deferred token */
3983 assert( pPhrase
->doclist
.bFreeList
==0 );
3985 for(iToken
=0; iToken
<pPhrase
->nToken
; iToken
++){
3986 Fts3PhraseToken
*pToken
= &pPhrase
->aToken
[iToken
];
3987 Fts3DeferredToken
*pDeferred
= pToken
->pDeferred
;
3992 int rc
= sqlite3Fts3DeferredTokenList(pDeferred
, &pList
, &nList
);
3993 if( rc
!=SQLITE_OK
) return rc
;
3996 sqlite3_free(aPoslist
);
3997 pPhrase
->doclist
.pList
= 0;
3998 pPhrase
->doclist
.nList
= 0;
4001 }else if( aPoslist
==0 ){
4007 char *p1
= aPoslist
;
4011 fts3PoslistPhraseMerge(&aOut
, iToken
-iPrev
, 0, 1, &p1
, &p2
);
4012 sqlite3_free(aPoslist
);
4014 nPoslist
= (int)(aOut
- aPoslist
);
4016 sqlite3_free(aPoslist
);
4017 pPhrase
->doclist
.pList
= 0;
4018 pPhrase
->doclist
.nList
= 0;
4027 int nMaxUndeferred
= pPhrase
->iDoclistToken
;
4028 if( nMaxUndeferred
<0 ){
4029 pPhrase
->doclist
.pList
= aPoslist
;
4030 pPhrase
->doclist
.nList
= nPoslist
;
4031 pPhrase
->doclist
.iDocid
= pCsr
->iPrevId
;
4032 pPhrase
->doclist
.bFreeList
= 1;
4039 if( nMaxUndeferred
>iPrev
){
4041 p2
= pPhrase
->doclist
.pList
;
4042 nDistance
= nMaxUndeferred
- iPrev
;
4044 p1
= pPhrase
->doclist
.pList
;
4046 nDistance
= iPrev
- nMaxUndeferred
;
4049 aOut
= (char *)sqlite3_malloc(nPoslist
+8);
4051 sqlite3_free(aPoslist
);
4052 return SQLITE_NOMEM
;
4055 pPhrase
->doclist
.pList
= aOut
;
4056 if( fts3PoslistPhraseMerge(&aOut
, nDistance
, 0, 1, &p1
, &p2
) ){
4057 pPhrase
->doclist
.bFreeList
= 1;
4058 pPhrase
->doclist
.nList
= (int)(aOut
- pPhrase
->doclist
.pList
);
4061 pPhrase
->doclist
.pList
= 0;
4062 pPhrase
->doclist
.nList
= 0;
4064 sqlite3_free(aPoslist
);
4072 ** Maximum number of tokens a phrase may have to be considered for the
4073 ** incremental doclists strategy.
4075 #define MAX_INCR_PHRASE_TOKENS 4
4078 ** This function is called for each Fts3Phrase in a full-text query
4079 ** expression to initialize the mechanism for returning rows. Once this
4080 ** function has been called successfully on an Fts3Phrase, it may be
4081 ** used with fts3EvalPhraseNext() to iterate through the matching docids.
4083 ** If parameter bOptOk is true, then the phrase may (or may not) use the
4084 ** incremental loading strategy. Otherwise, the entire doclist is loaded into
4085 ** memory within this call.
4087 ** SQLITE_OK is returned if no error occurs, otherwise an SQLite error code.
4089 static int fts3EvalPhraseStart(Fts3Cursor
*pCsr
, int bOptOk
, Fts3Phrase
*p
){
4090 Fts3Table
*pTab
= (Fts3Table
*)pCsr
->base
.pVtab
;
4091 int rc
= SQLITE_OK
; /* Error code */
4094 /* Determine if doclists may be loaded from disk incrementally. This is
4095 ** possible if the bOptOk argument is true, the FTS doclists will be
4096 ** scanned in forward order, and the phrase consists of
4097 ** MAX_INCR_PHRASE_TOKENS or fewer tokens, none of which are are "^first"
4098 ** tokens or prefix tokens that cannot use a prefix-index. */
4100 int bIncrOk
= (bOptOk
4101 && pCsr
->bDesc
==pTab
->bDescIdx
4102 && p
->nToken
<=MAX_INCR_PHRASE_TOKENS
&& p
->nToken
>0
4103 && p
->nToken
<=MAX_INCR_PHRASE_TOKENS
&& p
->nToken
>0
4105 && pTab
->bNoIncrDoclist
==0
4108 for(i
=0; bIncrOk
==1 && i
<p
->nToken
; i
++){
4109 Fts3PhraseToken
*pToken
= &p
->aToken
[i
];
4110 if( pToken
->bFirst
|| (pToken
->pSegcsr
!=0 && !pToken
->pSegcsr
->bLookup
) ){
4113 if( pToken
->pSegcsr
) bHaveIncr
= 1;
4116 if( bIncrOk
&& bHaveIncr
){
4117 /* Use the incremental approach. */
4118 int iCol
= (p
->iColumn
>= pTab
->nColumn
? -1 : p
->iColumn
);
4119 for(i
=0; rc
==SQLITE_OK
&& i
<p
->nToken
; i
++){
4120 Fts3PhraseToken
*pToken
= &p
->aToken
[i
];
4121 Fts3MultiSegReader
*pSegcsr
= pToken
->pSegcsr
;
4123 rc
= sqlite3Fts3MsrIncrStart(pTab
, pSegcsr
, iCol
, pToken
->z
, pToken
->n
);
4128 /* Load the full doclist for the phrase into memory. */
4129 rc
= fts3EvalPhraseLoad(pCsr
, p
);
4133 assert( rc
!=SQLITE_OK
|| p
->nToken
<1 || p
->aToken
[0].pSegcsr
==0 || p
->bIncr
);
4138 ** This function is used to iterate backwards (from the end to start)
4139 ** through doclists. It is used by this module to iterate through phrase
4140 ** doclists in reverse and by the fts3_write.c module to iterate through
4141 ** pending-terms lists when writing to databases with "order=desc".
4143 ** The doclist may be sorted in ascending (parameter bDescIdx==0) or
4144 ** descending (parameter bDescIdx==1) order of docid. Regardless, this
4145 ** function iterates from the end of the doclist to the beginning.
4147 void sqlite3Fts3DoclistPrev(
4148 int bDescIdx
, /* True if the doclist is desc */
4149 char *aDoclist
, /* Pointer to entire doclist */
4150 int nDoclist
, /* Length of aDoclist in bytes */
4151 char **ppIter
, /* IN/OUT: Iterator pointer */
4152 sqlite3_int64
*piDocid
, /* IN/OUT: Docid pointer */
4153 int *pnList
, /* OUT: List length pointer */
4154 u8
*pbEof
/* OUT: End-of-file flag */
4158 assert( nDoclist
>0 );
4159 assert( *pbEof
==0 );
4160 assert( p
|| *piDocid
==0 );
4161 assert( !p
|| (p
>aDoclist
&& p
<&aDoclist
[nDoclist
]) );
4164 sqlite3_int64 iDocid
= 0;
4166 char *pDocid
= aDoclist
;
4167 char *pEnd
= &aDoclist
[nDoclist
];
4170 while( pDocid
<pEnd
){
4171 sqlite3_int64 iDelta
;
4172 pDocid
+= sqlite3Fts3GetVarint(pDocid
, &iDelta
);
4173 iDocid
+= (iMul
* iDelta
);
4175 fts3PoslistCopy(0, &pDocid
);
4176 while( pDocid
<pEnd
&& *pDocid
==0 ) pDocid
++;
4177 iMul
= (bDescIdx
? -1 : 1);
4180 *pnList
= (int)(pEnd
- pNext
);
4184 int iMul
= (bDescIdx
? -1 : 1);
4185 sqlite3_int64 iDelta
;
4186 fts3GetReverseVarint(&p
, aDoclist
, &iDelta
);
4187 *piDocid
-= (iMul
* iDelta
);
4193 fts3ReversePoslist(aDoclist
, &p
);
4194 *pnList
= (int)(pSave
- p
);
4201 ** Iterate forwards through a doclist.
4203 void sqlite3Fts3DoclistNext(
4204 int bDescIdx
, /* True if the doclist is desc */
4205 char *aDoclist
, /* Pointer to entire doclist */
4206 int nDoclist
, /* Length of aDoclist in bytes */
4207 char **ppIter
, /* IN/OUT: Iterator pointer */
4208 sqlite3_int64
*piDocid
, /* IN/OUT: Docid pointer */
4209 u8
*pbEof
/* OUT: End-of-file flag */
4213 assert( nDoclist
>0 );
4214 assert( *pbEof
==0 );
4215 assert( p
|| *piDocid
==0 );
4216 assert( !p
|| (p
>=aDoclist
&& p
<=&aDoclist
[nDoclist
]) );
4220 p
+= sqlite3Fts3GetVarint(p
, piDocid
);
4222 fts3PoslistCopy(0, &p
);
4223 if( p
>=&aDoclist
[nDoclist
] ){
4227 p
+= sqlite3Fts3GetVarint(p
, &iVar
);
4228 *piDocid
+= ((bDescIdx
? -1 : 1) * iVar
);
4236 ** Advance the iterator pDL to the next entry in pDL->aAll/nAll. Set *pbEof
4237 ** to true if EOF is reached.
4239 static void fts3EvalDlPhraseNext(
4244 char *pIter
; /* Used to iterate through aAll */
4245 char *pEnd
= &pDL
->aAll
[pDL
->nAll
]; /* 1 byte past end of aAll */
4247 if( pDL
->pNextDocid
){
4248 pIter
= pDL
->pNextDocid
;
4254 /* We have already reached the end of this doclist. EOF. */
4257 sqlite3_int64 iDelta
;
4258 pIter
+= sqlite3Fts3GetVarint(pIter
, &iDelta
);
4259 if( pTab
->bDescIdx
==0 || pDL
->pNextDocid
==0 ){
4260 pDL
->iDocid
+= iDelta
;
4262 pDL
->iDocid
-= iDelta
;
4265 fts3PoslistCopy(0, &pIter
);
4266 pDL
->nList
= (int)(pIter
- pDL
->pList
);
4268 /* pIter now points just past the 0x00 that terminates the position-
4269 ** list for document pDL->iDocid. However, if this position-list was
4270 ** edited in place by fts3EvalNearTrim(), then pIter may not actually
4271 ** point to the start of the next docid value. The following line deals
4272 ** with this case by advancing pIter past the zero-padding added by
4273 ** fts3EvalNearTrim(). */
4274 while( pIter
<pEnd
&& *pIter
==0 ) pIter
++;
4276 pDL
->pNextDocid
= pIter
;
4277 assert( pIter
>=&pDL
->aAll
[pDL
->nAll
] || *pIter
);
4283 ** Helper type used by fts3EvalIncrPhraseNext() and incrPhraseTokenNext().
4285 typedef struct TokenDoclist TokenDoclist
;
4286 struct TokenDoclist
{
4288 sqlite3_int64 iDocid
;
4294 ** Token pToken is an incrementally loaded token that is part of a
4295 ** multi-token phrase. Advance it to the next matching document in the
4296 ** database and populate output variable *p with the details of the new
4297 ** entry. Or, if the iterator has reached EOF, set *pbEof to true.
4299 ** If an error occurs, return an SQLite error code. Otherwise, return
4302 static int incrPhraseTokenNext(
4303 Fts3Table
*pTab
, /* Virtual table handle */
4304 Fts3Phrase
*pPhrase
, /* Phrase to advance token of */
4305 int iToken
, /* Specific token to advance */
4306 TokenDoclist
*p
, /* OUT: Docid and doclist for new entry */
4307 u8
*pbEof
/* OUT: True if iterator is at EOF */
4311 if( pPhrase
->iDoclistToken
==iToken
){
4312 assert( p
->bIgnore
==0 );
4313 assert( pPhrase
->aToken
[iToken
].pSegcsr
==0 );
4314 fts3EvalDlPhraseNext(pTab
, &pPhrase
->doclist
, pbEof
);
4315 p
->pList
= pPhrase
->doclist
.pList
;
4316 p
->nList
= pPhrase
->doclist
.nList
;
4317 p
->iDocid
= pPhrase
->doclist
.iDocid
;
4319 Fts3PhraseToken
*pToken
= &pPhrase
->aToken
[iToken
];
4320 assert( pToken
->pDeferred
==0 );
4321 assert( pToken
->pSegcsr
|| pPhrase
->iDoclistToken
>=0 );
4322 if( pToken
->pSegcsr
){
4323 assert( p
->bIgnore
==0 );
4324 rc
= sqlite3Fts3MsrIncrNext(
4325 pTab
, pToken
->pSegcsr
, &p
->iDocid
, &p
->pList
, &p
->nList
4327 if( p
->pList
==0 ) *pbEof
= 1;
4338 ** The phrase iterator passed as the second argument:
4340 ** * features at least one token that uses an incremental doclist, and
4342 ** * does not contain any deferred tokens.
4344 ** Advance it to the next matching documnent in the database and populate
4345 ** the Fts3Doclist.pList and nList fields.
4347 ** If there is no "next" entry and no error occurs, then *pbEof is set to
4348 ** 1 before returning. Otherwise, if no error occurs and the iterator is
4349 ** successfully advanced, *pbEof is set to 0.
4351 ** If an error occurs, return an SQLite error code. Otherwise, return
4354 static int fts3EvalIncrPhraseNext(
4355 Fts3Cursor
*pCsr
, /* FTS Cursor handle */
4356 Fts3Phrase
*p
, /* Phrase object to advance to next docid */
4357 u8
*pbEof
/* OUT: Set to 1 if EOF */
4360 Fts3Doclist
*pDL
= &p
->doclist
;
4361 Fts3Table
*pTab
= (Fts3Table
*)pCsr
->base
.pVtab
;
4364 /* This is only called if it is guaranteed that the phrase has at least
4365 ** one incremental token. In which case the bIncr flag is set. */
4366 assert( p
->bIncr
==1 );
4368 if( p
->nToken
==1 && p
->bIncr
){
4369 rc
= sqlite3Fts3MsrIncrNext(pTab
, p
->aToken
[0].pSegcsr
,
4370 &pDL
->iDocid
, &pDL
->pList
, &pDL
->nList
4372 if( pDL
->pList
==0 ) bEof
= 1;
4374 int bDescDoclist
= pCsr
->bDesc
;
4375 struct TokenDoclist a
[MAX_INCR_PHRASE_TOKENS
];
4377 memset(a
, 0, sizeof(a
));
4378 assert( p
->nToken
<=MAX_INCR_PHRASE_TOKENS
);
4379 assert( p
->iDoclistToken
<MAX_INCR_PHRASE_TOKENS
);
4383 sqlite3_int64 iMax
= 0; /* Largest docid for all iterators */
4384 int i
; /* Used to iterate through tokens */
4386 /* Advance the iterator for each token in the phrase once. */
4387 for(i
=0; rc
==SQLITE_OK
&& i
<p
->nToken
&& bEof
==0; i
++){
4388 rc
= incrPhraseTokenNext(pTab
, p
, i
, &a
[i
], &bEof
);
4389 if( a
[i
].bIgnore
==0 && (bMaxSet
==0 || DOCID_CMP(iMax
, a
[i
].iDocid
)<0) ){
4394 assert( rc
!=SQLITE_OK
|| a
[p
->nToken
-1].bIgnore
==0 );
4395 assert( rc
!=SQLITE_OK
|| bMaxSet
);
4397 /* Keep advancing iterators until they all point to the same document */
4398 for(i
=0; i
<p
->nToken
; i
++){
4399 while( rc
==SQLITE_OK
&& bEof
==0
4400 && a
[i
].bIgnore
==0 && DOCID_CMP(a
[i
].iDocid
, iMax
)<0
4402 rc
= incrPhraseTokenNext(pTab
, p
, i
, &a
[i
], &bEof
);
4403 if( DOCID_CMP(a
[i
].iDocid
, iMax
)>0 ){
4410 /* Check if the current entries really are a phrase match */
4413 int nByte
= a
[p
->nToken
-1].nList
;
4414 char *aDoclist
= sqlite3_malloc(nByte
+1);
4415 if( !aDoclist
) return SQLITE_NOMEM
;
4416 memcpy(aDoclist
, a
[p
->nToken
-1].pList
, nByte
+1);
4418 for(i
=0; i
<(p
->nToken
-1); i
++){
4419 if( a
[i
].bIgnore
==0 ){
4420 char *pL
= a
[i
].pList
;
4421 char *pR
= aDoclist
;
4422 char *pOut
= aDoclist
;
4423 int nDist
= p
->nToken
-1-i
;
4424 int res
= fts3PoslistPhraseMerge(&pOut
, nDist
, 0, 1, &pL
, &pR
);
4426 nList
= (int)(pOut
- aDoclist
);
4429 if( i
==(p
->nToken
-1) ){
4431 pDL
->pList
= aDoclist
;
4436 sqlite3_free(aDoclist
);
4446 ** Attempt to move the phrase iterator to point to the next matching docid.
4447 ** If an error occurs, return an SQLite error code. Otherwise, return
4450 ** If there is no "next" entry and no error occurs, then *pbEof is set to
4451 ** 1 before returning. Otherwise, if no error occurs and the iterator is
4452 ** successfully advanced, *pbEof is set to 0.
4454 static int fts3EvalPhraseNext(
4455 Fts3Cursor
*pCsr
, /* FTS Cursor handle */
4456 Fts3Phrase
*p
, /* Phrase object to advance to next docid */
4457 u8
*pbEof
/* OUT: Set to 1 if EOF */
4460 Fts3Doclist
*pDL
= &p
->doclist
;
4461 Fts3Table
*pTab
= (Fts3Table
*)pCsr
->base
.pVtab
;
4464 rc
= fts3EvalIncrPhraseNext(pCsr
, p
, pbEof
);
4465 }else if( pCsr
->bDesc
!=pTab
->bDescIdx
&& pDL
->nAll
){
4466 sqlite3Fts3DoclistPrev(pTab
->bDescIdx
, pDL
->aAll
, pDL
->nAll
,
4467 &pDL
->pNextDocid
, &pDL
->iDocid
, &pDL
->nList
, pbEof
4469 pDL
->pList
= pDL
->pNextDocid
;
4471 fts3EvalDlPhraseNext(pTab
, pDL
, pbEof
);
4479 ** If *pRc is not SQLITE_OK when this function is called, it is a no-op.
4480 ** Otherwise, fts3EvalPhraseStart() is called on all phrases within the
4481 ** expression. Also the Fts3Expr.bDeferred variable is set to true for any
4482 ** expressions for which all descendent tokens are deferred.
4484 ** If parameter bOptOk is zero, then it is guaranteed that the
4485 ** Fts3Phrase.doclist.aAll/nAll variables contain the entire doclist for
4486 ** each phrase in the expression (subject to deferred token processing).
4487 ** Or, if bOptOk is non-zero, then one or more tokens within the expression
4488 ** may be loaded incrementally, meaning doclist.aAll/nAll is not available.
4490 ** If an error occurs within this function, *pRc is set to an SQLite error
4491 ** code before returning.
4493 static void fts3EvalStartReaders(
4494 Fts3Cursor
*pCsr
, /* FTS Cursor handle */
4495 Fts3Expr
*pExpr
, /* Expression to initialize phrases in */
4496 int *pRc
/* IN/OUT: Error code */
4498 if( pExpr
&& SQLITE_OK
==*pRc
){
4499 if( pExpr
->eType
==FTSQUERY_PHRASE
){
4501 int nToken
= pExpr
->pPhrase
->nToken
;
4502 for(i
=0; i
<nToken
; i
++){
4503 if( pExpr
->pPhrase
->aToken
[i
].pDeferred
==0 ) break;
4505 pExpr
->bDeferred
= (i
==nToken
);
4506 *pRc
= fts3EvalPhraseStart(pCsr
, 1, pExpr
->pPhrase
);
4508 fts3EvalStartReaders(pCsr
, pExpr
->pLeft
, pRc
);
4509 fts3EvalStartReaders(pCsr
, pExpr
->pRight
, pRc
);
4510 pExpr
->bDeferred
= (pExpr
->pLeft
->bDeferred
&& pExpr
->pRight
->bDeferred
);
4516 ** An array of the following structures is assembled as part of the process
4517 ** of selecting tokens to defer before the query starts executing (as part
4518 ** of the xFilter() method). There is one element in the array for each
4519 ** token in the FTS expression.
4521 ** Tokens are divided into AND/NEAR clusters. All tokens in a cluster belong
4522 ** to phrases that are connected only by AND and NEAR operators (not OR or
4523 ** NOT). When determining tokens to defer, each AND/NEAR cluster is considered
4524 ** separately. The root of a tokens AND/NEAR cluster is stored in
4525 ** Fts3TokenAndCost.pRoot.
4527 typedef struct Fts3TokenAndCost Fts3TokenAndCost
;
4528 struct Fts3TokenAndCost
{
4529 Fts3Phrase
*pPhrase
; /* The phrase the token belongs to */
4530 int iToken
; /* Position of token in phrase */
4531 Fts3PhraseToken
*pToken
; /* The token itself */
4532 Fts3Expr
*pRoot
; /* Root of NEAR/AND cluster */
4533 int nOvfl
; /* Number of overflow pages to load doclist */
4534 int iCol
; /* The column the token must match */
4538 ** This function is used to populate an allocated Fts3TokenAndCost array.
4540 ** If *pRc is not SQLITE_OK when this function is called, it is a no-op.
4541 ** Otherwise, if an error occurs during execution, *pRc is set to an
4542 ** SQLite error code.
4544 static void fts3EvalTokenCosts(
4545 Fts3Cursor
*pCsr
, /* FTS Cursor handle */
4546 Fts3Expr
*pRoot
, /* Root of current AND/NEAR cluster */
4547 Fts3Expr
*pExpr
, /* Expression to consider */
4548 Fts3TokenAndCost
**ppTC
, /* Write new entries to *(*ppTC)++ */
4549 Fts3Expr
***ppOr
, /* Write new OR root to *(*ppOr)++ */
4550 int *pRc
/* IN/OUT: Error code */
4552 if( *pRc
==SQLITE_OK
){
4553 if( pExpr
->eType
==FTSQUERY_PHRASE
){
4554 Fts3Phrase
*pPhrase
= pExpr
->pPhrase
;
4556 for(i
=0; *pRc
==SQLITE_OK
&& i
<pPhrase
->nToken
; i
++){
4557 Fts3TokenAndCost
*pTC
= (*ppTC
)++;
4558 pTC
->pPhrase
= pPhrase
;
4561 pTC
->pToken
= &pPhrase
->aToken
[i
];
4562 pTC
->iCol
= pPhrase
->iColumn
;
4563 *pRc
= sqlite3Fts3MsrOvfl(pCsr
, pTC
->pToken
->pSegcsr
, &pTC
->nOvfl
);
4565 }else if( pExpr
->eType
!=FTSQUERY_NOT
){
4566 assert( pExpr
->eType
==FTSQUERY_OR
4567 || pExpr
->eType
==FTSQUERY_AND
4568 || pExpr
->eType
==FTSQUERY_NEAR
4570 assert( pExpr
->pLeft
&& pExpr
->pRight
);
4571 if( pExpr
->eType
==FTSQUERY_OR
){
4572 pRoot
= pExpr
->pLeft
;
4576 fts3EvalTokenCosts(pCsr
, pRoot
, pExpr
->pLeft
, ppTC
, ppOr
, pRc
);
4577 if( pExpr
->eType
==FTSQUERY_OR
){
4578 pRoot
= pExpr
->pRight
;
4582 fts3EvalTokenCosts(pCsr
, pRoot
, pExpr
->pRight
, ppTC
, ppOr
, pRc
);
4588 ** Determine the average document (row) size in pages. If successful,
4589 ** write this value to *pnPage and return SQLITE_OK. Otherwise, return
4590 ** an SQLite error code.
4592 ** The average document size in pages is calculated by first calculating
4593 ** determining the average size in bytes, B. If B is less than the amount
4594 ** of data that will fit on a single leaf page of an intkey table in
4595 ** this database, then the average docsize is 1. Otherwise, it is 1 plus
4596 ** the number of overflow pages consumed by a record B bytes in size.
4598 static int fts3EvalAverageDocsize(Fts3Cursor
*pCsr
, int *pnPage
){
4599 if( pCsr
->nRowAvg
==0 ){
4600 /* The average document size, which is required to calculate the cost
4601 ** of each doclist, has not yet been determined. Read the required
4602 ** data from the %_stat table to calculate it.
4604 ** Entry 0 of the %_stat table is a blob containing (nCol+1) FTS3
4605 ** varints, where nCol is the number of columns in the FTS3 table.
4606 ** The first varint is the number of documents currently stored in
4607 ** the table. The following nCol varints contain the total amount of
4608 ** data stored in all rows of each column of the table, from left
4612 Fts3Table
*p
= (Fts3Table
*)pCsr
->base
.pVtab
;
4613 sqlite3_stmt
*pStmt
;
4614 sqlite3_int64 nDoc
= 0;
4615 sqlite3_int64 nByte
= 0;
4619 rc
= sqlite3Fts3SelectDoctotal(p
, &pStmt
);
4620 if( rc
!=SQLITE_OK
) return rc
;
4621 a
= sqlite3_column_blob(pStmt
, 0);
4624 pEnd
= &a
[sqlite3_column_bytes(pStmt
, 0)];
4625 a
+= sqlite3Fts3GetVarint(a
, &nDoc
);
4627 a
+= sqlite3Fts3GetVarint(a
, &nByte
);
4629 if( nDoc
==0 || nByte
==0 ){
4630 sqlite3_reset(pStmt
);
4631 return FTS_CORRUPT_VTAB
;
4635 pCsr
->nRowAvg
= (int)(((nByte
/ nDoc
) + p
->nPgsz
) / p
->nPgsz
);
4636 assert( pCsr
->nRowAvg
>0 );
4637 rc
= sqlite3_reset(pStmt
);
4638 if( rc
!=SQLITE_OK
) return rc
;
4641 *pnPage
= pCsr
->nRowAvg
;
4646 ** This function is called to select the tokens (if any) that will be
4647 ** deferred. The array aTC[] has already been populated when this is
4650 ** This function is called once for each AND/NEAR cluster in the
4651 ** expression. Each invocation determines which tokens to defer within
4652 ** the cluster with root node pRoot. See comments above the definition
4653 ** of struct Fts3TokenAndCost for more details.
4655 ** If no error occurs, SQLITE_OK is returned and sqlite3Fts3DeferToken()
4656 ** called on each token to defer. Otherwise, an SQLite error code is
4659 static int fts3EvalSelectDeferred(
4660 Fts3Cursor
*pCsr
, /* FTS Cursor handle */
4661 Fts3Expr
*pRoot
, /* Consider tokens with this root node */
4662 Fts3TokenAndCost
*aTC
, /* Array of expression tokens and costs */
4663 int nTC
/* Number of entries in aTC[] */
4665 Fts3Table
*pTab
= (Fts3Table
*)pCsr
->base
.pVtab
;
4666 int nDocSize
= 0; /* Number of pages per doc loaded */
4667 int rc
= SQLITE_OK
; /* Return code */
4668 int ii
; /* Iterator variable for various purposes */
4669 int nOvfl
= 0; /* Total overflow pages used by doclists */
4670 int nToken
= 0; /* Total number of tokens in cluster */
4672 int nMinEst
= 0; /* The minimum count for any phrase so far. */
4673 int nLoad4
= 1; /* (Phrases that will be loaded)^4. */
4675 /* Tokens are never deferred for FTS tables created using the content=xxx
4676 ** option. The reason being that it is not guaranteed that the content
4677 ** table actually contains the same data as the index. To prevent this from
4678 ** causing any problems, the deferred token optimization is completely
4679 ** disabled for content=xxx tables. */
4680 if( pTab
->zContentTbl
){
4684 /* Count the tokens in this AND/NEAR cluster. If none of the doclists
4685 ** associated with the tokens spill onto overflow pages, or if there is
4686 ** only 1 token, exit early. No tokens to defer in this case. */
4687 for(ii
=0; ii
<nTC
; ii
++){
4688 if( aTC
[ii
].pRoot
==pRoot
){
4689 nOvfl
+= aTC
[ii
].nOvfl
;
4693 if( nOvfl
==0 || nToken
<2 ) return SQLITE_OK
;
4695 /* Obtain the average docsize (in pages). */
4696 rc
= fts3EvalAverageDocsize(pCsr
, &nDocSize
);
4697 assert( rc
!=SQLITE_OK
|| nDocSize
>0 );
4700 /* Iterate through all tokens in this AND/NEAR cluster, in ascending order
4701 ** of the number of overflow pages that will be loaded by the pager layer
4702 ** to retrieve the entire doclist for the token from the full-text index.
4703 ** Load the doclists for tokens that are either:
4705 ** a. The cheapest token in the entire query (i.e. the one visited by the
4706 ** first iteration of this loop), or
4708 ** b. Part of a multi-token phrase.
4710 ** After each token doclist is loaded, merge it with the others from the
4711 ** same phrase and count the number of documents that the merged doclist
4712 ** contains. Set variable "nMinEst" to the smallest number of documents in
4713 ** any phrase doclist for which 1 or more token doclists have been loaded.
4714 ** Let nOther be the number of other phrases for which it is certain that
4715 ** one or more tokens will not be deferred.
4717 ** Then, for each token, defer it if loading the doclist would result in
4718 ** loading N or more overflow pages into memory, where N is computed as:
4720 ** (nMinEst + 4^nOther - 1) / (4^nOther)
4722 for(ii
=0; ii
<nToken
&& rc
==SQLITE_OK
; ii
++){
4723 int iTC
; /* Used to iterate through aTC[] array. */
4724 Fts3TokenAndCost
*pTC
= 0; /* Set to cheapest remaining token. */
4726 /* Set pTC to point to the cheapest remaining token. */
4727 for(iTC
=0; iTC
<nTC
; iTC
++){
4728 if( aTC
[iTC
].pToken
&& aTC
[iTC
].pRoot
==pRoot
4729 && (!pTC
|| aTC
[iTC
].nOvfl
<pTC
->nOvfl
)
4736 if( ii
&& pTC
->nOvfl
>=((nMinEst
+(nLoad4
/4)-1)/(nLoad4
/4))*nDocSize
){
4737 /* The number of overflow pages to load for this (and therefore all
4738 ** subsequent) tokens is greater than the estimated number of pages
4739 ** that will be loaded if all subsequent tokens are deferred.
4741 Fts3PhraseToken
*pToken
= pTC
->pToken
;
4742 rc
= sqlite3Fts3DeferToken(pCsr
, pToken
, pTC
->iCol
);
4743 fts3SegReaderCursorFree(pToken
->pSegcsr
);
4744 pToken
->pSegcsr
= 0;
4746 /* Set nLoad4 to the value of (4^nOther) for the next iteration of the
4747 ** for-loop. Except, limit the value to 2^24 to prevent it from
4748 ** overflowing the 32-bit integer it is stored in. */
4749 if( ii
<12 ) nLoad4
= nLoad4
*4;
4751 if( ii
==0 || (pTC
->pPhrase
->nToken
>1 && ii
!=nToken
-1) ){
4752 /* Either this is the cheapest token in the entire query, or it is
4753 ** part of a multi-token phrase. Either way, the entire doclist will
4754 ** (eventually) be loaded into memory. It may as well be now. */
4755 Fts3PhraseToken
*pToken
= pTC
->pToken
;
4758 rc
= fts3TermSelect(pTab
, pToken
, pTC
->iCol
, &nList
, &pList
);
4759 assert( rc
==SQLITE_OK
|| pList
==0 );
4760 if( rc
==SQLITE_OK
){
4762 fts3EvalPhraseMergeToken(pTab
, pTC
->pPhrase
, pTC
->iToken
,pList
,nList
);
4763 nCount
= fts3DoclistCountDocids(
4764 pTC
->pPhrase
->doclist
.aAll
, pTC
->pPhrase
->doclist
.nAll
4766 if( ii
==0 || nCount
<nMinEst
) nMinEst
= nCount
;
4777 ** This function is called from within the xFilter method. It initializes
4778 ** the full-text query currently stored in pCsr->pExpr. To iterate through
4779 ** the results of a query, the caller does:
4781 ** fts3EvalStart(pCsr);
4783 ** fts3EvalNext(pCsr);
4784 ** if( pCsr->bEof ) break;
4785 ** ... return row pCsr->iPrevId to the caller ...
4788 static int fts3EvalStart(Fts3Cursor
*pCsr
){
4789 Fts3Table
*pTab
= (Fts3Table
*)pCsr
->base
.pVtab
;
4794 /* Allocate a MultiSegReader for each token in the expression. */
4795 fts3EvalAllocateReaders(pCsr
, pCsr
->pExpr
, &nToken
, &nOr
, &rc
);
4797 /* Determine which, if any, tokens in the expression should be deferred. */
4798 #ifndef SQLITE_DISABLE_FTS4_DEFERRED
4799 if( rc
==SQLITE_OK
&& nToken
>1 && pTab
->bFts4
){
4800 Fts3TokenAndCost
*aTC
;
4802 aTC
= (Fts3TokenAndCost
*)sqlite3_malloc(
4803 sizeof(Fts3TokenAndCost
) * nToken
4804 + sizeof(Fts3Expr
*) * nOr
* 2
4806 apOr
= (Fts3Expr
**)&aTC
[nToken
];
4812 Fts3TokenAndCost
*pTC
= aTC
;
4813 Fts3Expr
**ppOr
= apOr
;
4815 fts3EvalTokenCosts(pCsr
, 0, pCsr
->pExpr
, &pTC
, &ppOr
, &rc
);
4816 nToken
= (int)(pTC
-aTC
);
4817 nOr
= (int)(ppOr
-apOr
);
4819 if( rc
==SQLITE_OK
){
4820 rc
= fts3EvalSelectDeferred(pCsr
, 0, aTC
, nToken
);
4821 for(ii
=0; rc
==SQLITE_OK
&& ii
<nOr
; ii
++){
4822 rc
= fts3EvalSelectDeferred(pCsr
, apOr
[ii
], aTC
, nToken
);
4831 fts3EvalStartReaders(pCsr
, pCsr
->pExpr
, &rc
);
4836 ** Invalidate the current position list for phrase pPhrase.
4838 static void fts3EvalInvalidatePoslist(Fts3Phrase
*pPhrase
){
4839 if( pPhrase
->doclist
.bFreeList
){
4840 sqlite3_free(pPhrase
->doclist
.pList
);
4842 pPhrase
->doclist
.pList
= 0;
4843 pPhrase
->doclist
.nList
= 0;
4844 pPhrase
->doclist
.bFreeList
= 0;
4848 ** This function is called to edit the position list associated with
4849 ** the phrase object passed as the fifth argument according to a NEAR
4850 ** condition. For example:
4852 ** abc NEAR/5 "def ghi"
4854 ** Parameter nNear is passed the NEAR distance of the expression (5 in
4855 ** the example above). When this function is called, *paPoslist points to
4856 ** the position list, and *pnToken is the number of phrase tokens in, the
4857 ** phrase on the other side of the NEAR operator to pPhrase. For example,
4858 ** if pPhrase refers to the "def ghi" phrase, then *paPoslist points to
4859 ** the position list associated with phrase "abc".
4861 ** All positions in the pPhrase position list that are not sufficiently
4862 ** close to a position in the *paPoslist position list are removed. If this
4863 ** leaves 0 positions, zero is returned. Otherwise, non-zero.
4865 ** Before returning, *paPoslist is set to point to the position lsit
4866 ** associated with pPhrase. And *pnToken is set to the number of tokens in
4869 static int fts3EvalNearTrim(
4870 int nNear
, /* NEAR distance. As in "NEAR/nNear". */
4871 char *aTmp
, /* Temporary space to use */
4872 char **paPoslist
, /* IN/OUT: Position list */
4873 int *pnToken
, /* IN/OUT: Tokens in phrase of *paPoslist */
4874 Fts3Phrase
*pPhrase
/* The phrase object to trim the doclist of */
4876 int nParam1
= nNear
+ pPhrase
->nToken
;
4877 int nParam2
= nNear
+ *pnToken
;
4883 assert( pPhrase
->doclist
.pList
);
4885 p2
= pOut
= pPhrase
->doclist
.pList
;
4886 res
= fts3PoslistNearMerge(
4887 &pOut
, aTmp
, nParam1
, nParam2
, paPoslist
, &p2
4890 nNew
= (int)(pOut
- pPhrase
->doclist
.pList
) - 1;
4891 assert( pPhrase
->doclist
.pList
[nNew
]=='\0' );
4892 assert( nNew
<=pPhrase
->doclist
.nList
&& nNew
>0 );
4893 memset(&pPhrase
->doclist
.pList
[nNew
], 0, pPhrase
->doclist
.nList
- nNew
);
4894 pPhrase
->doclist
.nList
= nNew
;
4895 *paPoslist
= pPhrase
->doclist
.pList
;
4896 *pnToken
= pPhrase
->nToken
;
4903 ** This function is a no-op if *pRc is other than SQLITE_OK when it is called.
4904 ** Otherwise, it advances the expression passed as the second argument to
4905 ** point to the next matching row in the database. Expressions iterate through
4906 ** matching rows in docid order. Ascending order if Fts3Cursor.bDesc is zero,
4907 ** or descending if it is non-zero.
4909 ** If an error occurs, *pRc is set to an SQLite error code. Otherwise, if
4910 ** successful, the following variables in pExpr are set:
4912 ** Fts3Expr.bEof (non-zero if EOF - there is no next row)
4913 ** Fts3Expr.iDocid (valid if bEof==0. The docid of the next row)
4915 ** If the expression is of type FTSQUERY_PHRASE, and the expression is not
4916 ** at EOF, then the following variables are populated with the position list
4917 ** for the phrase for the visited row:
4919 ** FTs3Expr.pPhrase->doclist.nList (length of pList in bytes)
4920 ** FTs3Expr.pPhrase->doclist.pList (pointer to position list)
4922 ** It says above that this function advances the expression to the next
4923 ** matching row. This is usually true, but there are the following exceptions:
4925 ** 1. Deferred tokens are not taken into account. If a phrase consists
4926 ** entirely of deferred tokens, it is assumed to match every row in
4927 ** the db. In this case the position-list is not populated at all.
4929 ** Or, if a phrase contains one or more deferred tokens and one or
4930 ** more non-deferred tokens, then the expression is advanced to the
4931 ** next possible match, considering only non-deferred tokens. In other
4932 ** words, if the phrase is "A B C", and "B" is deferred, the expression
4933 ** is advanced to the next row that contains an instance of "A * C",
4934 ** where "*" may match any single token. The position list in this case
4935 ** is populated as for "A * C" before returning.
4937 ** 2. NEAR is treated as AND. If the expression is "x NEAR y", it is
4938 ** advanced to point to the next row that matches "x AND y".
4940 ** See fts3EvalTestDeferredAndNear() for details on testing if a row is
4941 ** really a match, taking into account deferred tokens and NEAR operators.
4943 static void fts3EvalNextRow(
4944 Fts3Cursor
*pCsr
, /* FTS Cursor handle */
4945 Fts3Expr
*pExpr
, /* Expr. to advance to next matching row */
4946 int *pRc
/* IN/OUT: Error code */
4948 if( *pRc
==SQLITE_OK
){
4949 int bDescDoclist
= pCsr
->bDesc
; /* Used by DOCID_CMP() macro */
4950 assert( pExpr
->bEof
==0 );
4953 switch( pExpr
->eType
){
4955 case FTSQUERY_AND
: {
4956 Fts3Expr
*pLeft
= pExpr
->pLeft
;
4957 Fts3Expr
*pRight
= pExpr
->pRight
;
4958 assert( !pLeft
->bDeferred
|| !pRight
->bDeferred
);
4960 if( pLeft
->bDeferred
){
4961 /* LHS is entirely deferred. So we assume it matches every row.
4962 ** Advance the RHS iterator to find the next row visited. */
4963 fts3EvalNextRow(pCsr
, pRight
, pRc
);
4964 pExpr
->iDocid
= pRight
->iDocid
;
4965 pExpr
->bEof
= pRight
->bEof
;
4966 }else if( pRight
->bDeferred
){
4967 /* RHS is entirely deferred. So we assume it matches every row.
4968 ** Advance the LHS iterator to find the next row visited. */
4969 fts3EvalNextRow(pCsr
, pLeft
, pRc
);
4970 pExpr
->iDocid
= pLeft
->iDocid
;
4971 pExpr
->bEof
= pLeft
->bEof
;
4973 /* Neither the RHS or LHS are deferred. */
4974 fts3EvalNextRow(pCsr
, pLeft
, pRc
);
4975 fts3EvalNextRow(pCsr
, pRight
, pRc
);
4976 while( !pLeft
->bEof
&& !pRight
->bEof
&& *pRc
==SQLITE_OK
){
4977 sqlite3_int64 iDiff
= DOCID_CMP(pLeft
->iDocid
, pRight
->iDocid
);
4978 if( iDiff
==0 ) break;
4980 fts3EvalNextRow(pCsr
, pLeft
, pRc
);
4982 fts3EvalNextRow(pCsr
, pRight
, pRc
);
4985 pExpr
->iDocid
= pLeft
->iDocid
;
4986 pExpr
->bEof
= (pLeft
->bEof
|| pRight
->bEof
);
4992 Fts3Expr
*pLeft
= pExpr
->pLeft
;
4993 Fts3Expr
*pRight
= pExpr
->pRight
;
4994 sqlite3_int64 iCmp
= DOCID_CMP(pLeft
->iDocid
, pRight
->iDocid
);
4996 assert( pLeft
->bStart
|| pLeft
->iDocid
==pRight
->iDocid
);
4997 assert( pRight
->bStart
|| pLeft
->iDocid
==pRight
->iDocid
);
4999 if( pRight
->bEof
|| (pLeft
->bEof
==0 && iCmp
<0) ){
5000 fts3EvalNextRow(pCsr
, pLeft
, pRc
);
5001 }else if( pLeft
->bEof
|| (pRight
->bEof
==0 && iCmp
>0) ){
5002 fts3EvalNextRow(pCsr
, pRight
, pRc
);
5004 fts3EvalNextRow(pCsr
, pLeft
, pRc
);
5005 fts3EvalNextRow(pCsr
, pRight
, pRc
);
5008 pExpr
->bEof
= (pLeft
->bEof
&& pRight
->bEof
);
5009 iCmp
= DOCID_CMP(pLeft
->iDocid
, pRight
->iDocid
);
5010 if( pRight
->bEof
|| (pLeft
->bEof
==0 && iCmp
<0) ){
5011 pExpr
->iDocid
= pLeft
->iDocid
;
5013 pExpr
->iDocid
= pRight
->iDocid
;
5019 case FTSQUERY_NOT
: {
5020 Fts3Expr
*pLeft
= pExpr
->pLeft
;
5021 Fts3Expr
*pRight
= pExpr
->pRight
;
5023 if( pRight
->bStart
==0 ){
5024 fts3EvalNextRow(pCsr
, pRight
, pRc
);
5025 assert( *pRc
!=SQLITE_OK
|| pRight
->bStart
);
5028 fts3EvalNextRow(pCsr
, pLeft
, pRc
);
5029 if( pLeft
->bEof
==0 ){
5032 && DOCID_CMP(pLeft
->iDocid
, pRight
->iDocid
)>0
5034 fts3EvalNextRow(pCsr
, pRight
, pRc
);
5037 pExpr
->iDocid
= pLeft
->iDocid
;
5038 pExpr
->bEof
= pLeft
->bEof
;
5043 Fts3Phrase
*pPhrase
= pExpr
->pPhrase
;
5044 fts3EvalInvalidatePoslist(pPhrase
);
5045 *pRc
= fts3EvalPhraseNext(pCsr
, pPhrase
, &pExpr
->bEof
);
5046 pExpr
->iDocid
= pPhrase
->doclist
.iDocid
;
5054 ** If *pRc is not SQLITE_OK, or if pExpr is not the root node of a NEAR
5055 ** cluster, then this function returns 1 immediately.
5057 ** Otherwise, it checks if the current row really does match the NEAR
5058 ** expression, using the data currently stored in the position lists
5059 ** (Fts3Expr->pPhrase.doclist.pList/nList) for each phrase in the expression.
5061 ** If the current row is a match, the position list associated with each
5062 ** phrase in the NEAR expression is edited in place to contain only those
5063 ** phrase instances sufficiently close to their peers to satisfy all NEAR
5064 ** constraints. In this case it returns 1. If the NEAR expression does not
5065 ** match the current row, 0 is returned. The position lists may or may not
5066 ** be edited if 0 is returned.
5068 static int fts3EvalNearTest(Fts3Expr
*pExpr
, int *pRc
){
5071 /* The following block runs if pExpr is the root of a NEAR query.
5072 ** For example, the query:
5074 ** "w" NEAR "x" NEAR "y" NEAR "z"
5076 ** which is represented in tree form as:
5079 ** +--NEAR--+ <-- root of NEAR query
5087 ** The right-hand child of a NEAR node is always a phrase. The
5088 ** left-hand child may be either a phrase or a NEAR node. There are
5089 ** no exceptions to this - it's the way the parser in fts3_expr.c works.
5092 && pExpr
->eType
==FTSQUERY_NEAR
5094 && (pExpr
->pParent
==0 || pExpr
->pParent
->eType
!=FTSQUERY_NEAR
)
5097 int nTmp
= 0; /* Bytes of temp space */
5098 char *aTmp
; /* Temp space for PoslistNearMerge() */
5100 /* Allocate temporary working space. */
5101 for(p
=pExpr
; p
->pLeft
; p
=p
->pLeft
){
5102 nTmp
+= p
->pRight
->pPhrase
->doclist
.nList
;
5104 nTmp
+= p
->pPhrase
->doclist
.nList
;
5108 aTmp
= sqlite3_malloc(nTmp
*2);
5110 *pRc
= SQLITE_NOMEM
;
5113 char *aPoslist
= p
->pPhrase
->doclist
.pList
;
5114 int nToken
= p
->pPhrase
->nToken
;
5116 for(p
=p
->pParent
;res
&& p
&& p
->eType
==FTSQUERY_NEAR
; p
=p
->pParent
){
5117 Fts3Phrase
*pPhrase
= p
->pRight
->pPhrase
;
5118 int nNear
= p
->nNear
;
5119 res
= fts3EvalNearTrim(nNear
, aTmp
, &aPoslist
, &nToken
, pPhrase
);
5122 aPoslist
= pExpr
->pRight
->pPhrase
->doclist
.pList
;
5123 nToken
= pExpr
->pRight
->pPhrase
->nToken
;
5124 for(p
=pExpr
->pLeft
; p
&& res
; p
=p
->pLeft
){
5126 Fts3Phrase
*pPhrase
;
5127 assert( p
->pParent
&& p
->pParent
->pLeft
==p
);
5128 nNear
= p
->pParent
->nNear
;
5130 p
->eType
==FTSQUERY_NEAR
? p
->pRight
->pPhrase
: p
->pPhrase
5132 res
= fts3EvalNearTrim(nNear
, aTmp
, &aPoslist
, &nToken
, pPhrase
);
5144 ** This function is a helper function for fts3EvalTestDeferredAndNear().
5145 ** Assuming no error occurs or has occurred, It returns non-zero if the
5146 ** expression passed as the second argument matches the row that pCsr
5147 ** currently points to, or zero if it does not.
5149 ** If *pRc is not SQLITE_OK when this function is called, it is a no-op.
5150 ** If an error occurs during execution of this function, *pRc is set to
5151 ** the appropriate SQLite error code. In this case the returned value is
5154 static int fts3EvalTestExpr(
5155 Fts3Cursor
*pCsr
, /* FTS cursor handle */
5156 Fts3Expr
*pExpr
, /* Expr to test. May or may not be root. */
5157 int *pRc
/* IN/OUT: Error code */
5159 int bHit
= 1; /* Return value */
5160 if( *pRc
==SQLITE_OK
){
5161 switch( pExpr
->eType
){
5165 fts3EvalTestExpr(pCsr
, pExpr
->pLeft
, pRc
)
5166 && fts3EvalTestExpr(pCsr
, pExpr
->pRight
, pRc
)
5167 && fts3EvalNearTest(pExpr
, pRc
)
5170 /* If the NEAR expression does not match any rows, zero the doclist for
5171 ** all phrases involved in the NEAR. This is because the snippet(),
5172 ** offsets() and matchinfo() functions are not supposed to recognize
5173 ** any instances of phrases that are part of unmatched NEAR queries.
5174 ** For example if this expression:
5176 ** ... MATCH 'a OR (b NEAR c)'
5178 ** is matched against a row containing:
5182 ** then any snippet() should ony highlight the "a" term, not the "b"
5183 ** (as "b" is part of a non-matching NEAR clause).
5186 && pExpr
->eType
==FTSQUERY_NEAR
5187 && (pExpr
->pParent
==0 || pExpr
->pParent
->eType
!=FTSQUERY_NEAR
)
5190 for(p
=pExpr
; p
->pPhrase
==0; p
=p
->pLeft
){
5191 if( p
->pRight
->iDocid
==pCsr
->iPrevId
){
5192 fts3EvalInvalidatePoslist(p
->pRight
->pPhrase
);
5195 if( p
->iDocid
==pCsr
->iPrevId
){
5196 fts3EvalInvalidatePoslist(p
->pPhrase
);
5203 int bHit1
= fts3EvalTestExpr(pCsr
, pExpr
->pLeft
, pRc
);
5204 int bHit2
= fts3EvalTestExpr(pCsr
, pExpr
->pRight
, pRc
);
5205 bHit
= bHit1
|| bHit2
;
5211 fts3EvalTestExpr(pCsr
, pExpr
->pLeft
, pRc
)
5212 && !fts3EvalTestExpr(pCsr
, pExpr
->pRight
, pRc
)
5217 #ifndef SQLITE_DISABLE_FTS4_DEFERRED
5219 && (pExpr
->iDocid
==pCsr
->iPrevId
|| pExpr
->bDeferred
)
5221 Fts3Phrase
*pPhrase
= pExpr
->pPhrase
;
5222 assert( pExpr
->bDeferred
|| pPhrase
->doclist
.bFreeList
==0 );
5223 if( pExpr
->bDeferred
){
5224 fts3EvalInvalidatePoslist(pPhrase
);
5226 *pRc
= fts3EvalDeferredPhrase(pCsr
, pPhrase
);
5227 bHit
= (pPhrase
->doclist
.pList
!=0);
5228 pExpr
->iDocid
= pCsr
->iPrevId
;
5232 bHit
= (pExpr
->bEof
==0 && pExpr
->iDocid
==pCsr
->iPrevId
);
5242 ** This function is called as the second part of each xNext operation when
5243 ** iterating through the results of a full-text query. At this point the
5244 ** cursor points to a row that matches the query expression, with the
5245 ** following caveats:
5247 ** * Up until this point, "NEAR" operators in the expression have been
5248 ** treated as "AND".
5250 ** * Deferred tokens have not yet been considered.
5252 ** If *pRc is not SQLITE_OK when this function is called, it immediately
5253 ** returns 0. Otherwise, it tests whether or not after considering NEAR
5254 ** operators and deferred tokens the current row is still a match for the
5255 ** expression. It returns 1 if both of the following are true:
5257 ** 1. *pRc is SQLITE_OK when this function returns, and
5259 ** 2. After scanning the current FTS table row for the deferred tokens,
5260 ** it is determined that the row does *not* match the query.
5262 ** Or, if no error occurs and it seems the current row does match the FTS
5265 static int fts3EvalTestDeferredAndNear(Fts3Cursor
*pCsr
, int *pRc
){
5268 if( rc
==SQLITE_OK
){
5270 /* If there are one or more deferred tokens, load the current row into
5271 ** memory and scan it to determine the position list for each deferred
5272 ** token. Then, see if this row is really a match, considering deferred
5273 ** tokens and NEAR operators (neither of which were taken into account
5274 ** earlier, by fts3EvalNextRow()).
5276 if( pCsr
->pDeferred
){
5277 rc
= fts3CursorSeek(0, pCsr
);
5278 if( rc
==SQLITE_OK
){
5279 rc
= sqlite3Fts3CacheDeferredDoclists(pCsr
);
5282 bMiss
= (0==fts3EvalTestExpr(pCsr
, pCsr
->pExpr
, &rc
));
5284 /* Free the position-lists accumulated for each deferred token above. */
5285 sqlite3Fts3FreeDeferredDoclists(pCsr
);
5288 return (rc
==SQLITE_OK
&& bMiss
);
5292 ** Advance to the next document that matches the FTS expression in
5293 ** Fts3Cursor.pExpr.
5295 static int fts3EvalNext(Fts3Cursor
*pCsr
){
5296 int rc
= SQLITE_OK
; /* Return Code */
5297 Fts3Expr
*pExpr
= pCsr
->pExpr
;
5298 assert( pCsr
->isEof
==0 );
5303 if( pCsr
->isRequireSeek
==0 ){
5304 sqlite3_reset(pCsr
->pStmt
);
5306 assert( sqlite3_data_count(pCsr
->pStmt
)==0 );
5307 fts3EvalNextRow(pCsr
, pExpr
, &rc
);
5308 pCsr
->isEof
= pExpr
->bEof
;
5309 pCsr
->isRequireSeek
= 1;
5310 pCsr
->isMatchinfoNeeded
= 1;
5311 pCsr
->iPrevId
= pExpr
->iDocid
;
5312 }while( pCsr
->isEof
==0 && fts3EvalTestDeferredAndNear(pCsr
, &rc
) );
5315 /* Check if the cursor is past the end of the docid range specified
5316 ** by Fts3Cursor.iMinDocid/iMaxDocid. If so, set the EOF flag. */
5317 if( rc
==SQLITE_OK
&& (
5318 (pCsr
->bDesc
==0 && pCsr
->iPrevId
>pCsr
->iMaxDocid
)
5319 || (pCsr
->bDesc
!=0 && pCsr
->iPrevId
<pCsr
->iMinDocid
)
5328 ** Restart interation for expression pExpr so that the next call to
5329 ** fts3EvalNext() visits the first row. Do not allow incremental
5330 ** loading or merging of phrase doclists for this iteration.
5332 ** If *pRc is other than SQLITE_OK when this function is called, it is
5333 ** a no-op. If an error occurs within this function, *pRc is set to an
5334 ** SQLite error code before returning.
5336 static void fts3EvalRestart(
5341 if( pExpr
&& *pRc
==SQLITE_OK
){
5342 Fts3Phrase
*pPhrase
= pExpr
->pPhrase
;
5345 fts3EvalInvalidatePoslist(pPhrase
);
5346 if( pPhrase
->bIncr
){
5348 for(i
=0; i
<pPhrase
->nToken
; i
++){
5349 Fts3PhraseToken
*pToken
= &pPhrase
->aToken
[i
];
5350 assert( pToken
->pDeferred
==0 );
5351 if( pToken
->pSegcsr
){
5352 sqlite3Fts3MsrIncrRestart(pToken
->pSegcsr
);
5355 *pRc
= fts3EvalPhraseStart(pCsr
, 0, pPhrase
);
5357 pPhrase
->doclist
.pNextDocid
= 0;
5358 pPhrase
->doclist
.iDocid
= 0;
5365 fts3EvalRestart(pCsr
, pExpr
->pLeft
, pRc
);
5366 fts3EvalRestart(pCsr
, pExpr
->pRight
, pRc
);
5371 ** After allocating the Fts3Expr.aMI[] array for each phrase in the
5372 ** expression rooted at pExpr, the cursor iterates through all rows matched
5373 ** by pExpr, calling this function for each row. This function increments
5374 ** the values in Fts3Expr.aMI[] according to the position-list currently
5375 ** found in Fts3Expr.pPhrase->doclist.pList for each of the phrase
5376 ** expression nodes.
5378 static void fts3EvalUpdateCounts(Fts3Expr
*pExpr
){
5380 Fts3Phrase
*pPhrase
= pExpr
->pPhrase
;
5381 if( pPhrase
&& pPhrase
->doclist
.pList
){
5383 char *p
= pPhrase
->doclist
.pList
;
5389 while( 0xFE & (*p
| c
) ){
5390 if( (c
&0x80)==0 ) iCnt
++;
5394 /* aMI[iCol*3 + 1] = Number of occurrences
5395 ** aMI[iCol*3 + 2] = Number of rows containing at least one instance
5397 pExpr
->aMI
[iCol
*3 + 1] += iCnt
;
5398 pExpr
->aMI
[iCol
*3 + 2] += (iCnt
>0);
5399 if( *p
==0x00 ) break;
5401 p
+= fts3GetVarint32(p
, &iCol
);
5405 fts3EvalUpdateCounts(pExpr
->pLeft
);
5406 fts3EvalUpdateCounts(pExpr
->pRight
);
5411 ** Expression pExpr must be of type FTSQUERY_PHRASE.
5413 ** If it is not already allocated and populated, this function allocates and
5414 ** populates the Fts3Expr.aMI[] array for expression pExpr. If pExpr is part
5415 ** of a NEAR expression, then it also allocates and populates the same array
5416 ** for all other phrases that are part of the NEAR expression.
5418 ** SQLITE_OK is returned if the aMI[] array is successfully allocated and
5419 ** populated. Otherwise, if an error occurs, an SQLite error code is returned.
5421 static int fts3EvalGatherStats(
5422 Fts3Cursor
*pCsr
, /* Cursor object */
5423 Fts3Expr
*pExpr
/* FTSQUERY_PHRASE expression */
5425 int rc
= SQLITE_OK
; /* Return code */
5427 assert( pExpr
->eType
==FTSQUERY_PHRASE
);
5428 if( pExpr
->aMI
==0 ){
5429 Fts3Table
*pTab
= (Fts3Table
*)pCsr
->base
.pVtab
;
5430 Fts3Expr
*pRoot
; /* Root of NEAR expression */
5431 Fts3Expr
*p
; /* Iterator used for several purposes */
5433 sqlite3_int64 iPrevId
= pCsr
->iPrevId
;
5434 sqlite3_int64 iDocid
;
5437 /* Find the root of the NEAR expression */
5439 while( pRoot
->pParent
&& pRoot
->pParent
->eType
==FTSQUERY_NEAR
){
5440 pRoot
= pRoot
->pParent
;
5442 iDocid
= pRoot
->iDocid
;
5444 assert( pRoot
->bStart
);
5446 /* Allocate space for the aMSI[] array of each FTSQUERY_PHRASE node */
5447 for(p
=pRoot
; p
; p
=p
->pLeft
){
5448 Fts3Expr
*pE
= (p
->eType
==FTSQUERY_PHRASE
?p
:p
->pRight
);
5449 assert( pE
->aMI
==0 );
5450 pE
->aMI
= (u32
*)sqlite3_malloc(pTab
->nColumn
* 3 * sizeof(u32
));
5451 if( !pE
->aMI
) return SQLITE_NOMEM
;
5452 memset(pE
->aMI
, 0, pTab
->nColumn
* 3 * sizeof(u32
));
5455 fts3EvalRestart(pCsr
, pRoot
, &rc
);
5457 while( pCsr
->isEof
==0 && rc
==SQLITE_OK
){
5460 /* Ensure the %_content statement is reset. */
5461 if( pCsr
->isRequireSeek
==0 ) sqlite3_reset(pCsr
->pStmt
);
5462 assert( sqlite3_data_count(pCsr
->pStmt
)==0 );
5464 /* Advance to the next document */
5465 fts3EvalNextRow(pCsr
, pRoot
, &rc
);
5466 pCsr
->isEof
= pRoot
->bEof
;
5467 pCsr
->isRequireSeek
= 1;
5468 pCsr
->isMatchinfoNeeded
= 1;
5469 pCsr
->iPrevId
= pRoot
->iDocid
;
5470 }while( pCsr
->isEof
==0
5471 && pRoot
->eType
==FTSQUERY_NEAR
5472 && fts3EvalTestDeferredAndNear(pCsr
, &rc
)
5475 if( rc
==SQLITE_OK
&& pCsr
->isEof
==0 ){
5476 fts3EvalUpdateCounts(pRoot
);
5481 pCsr
->iPrevId
= iPrevId
;
5486 /* Caution: pRoot may iterate through docids in ascending or descending
5487 ** order. For this reason, even though it seems more defensive, the
5488 ** do loop can not be written:
5490 ** do {...} while( pRoot->iDocid<iDocid && rc==SQLITE_OK );
5492 fts3EvalRestart(pCsr
, pRoot
, &rc
);
5494 fts3EvalNextRow(pCsr
, pRoot
, &rc
);
5495 assert( pRoot
->bEof
==0 );
5496 }while( pRoot
->iDocid
!=iDocid
&& rc
==SQLITE_OK
);
5497 fts3EvalTestDeferredAndNear(pCsr
, &rc
);
5504 ** This function is used by the matchinfo() module to query a phrase
5505 ** expression node for the following information:
5507 ** 1. The total number of occurrences of the phrase in each column of
5508 ** the FTS table (considering all rows), and
5510 ** 2. For each column, the number of rows in the table for which the
5511 ** column contains at least one instance of the phrase.
5513 ** If no error occurs, SQLITE_OK is returned and the values for each column
5514 ** written into the array aiOut as follows:
5516 ** aiOut[iCol*3 + 1] = Number of occurrences
5517 ** aiOut[iCol*3 + 2] = Number of rows containing at least one instance
5521 ** * If a phrase consists entirely of deferred tokens, then all output
5522 ** values are set to the number of documents in the table. In other
5523 ** words we assume that very common tokens occur exactly once in each
5524 ** column of each row of the table.
5526 ** * If a phrase contains some deferred tokens (and some non-deferred
5527 ** tokens), count the potential occurrence identified by considering
5528 ** the non-deferred tokens instead of actual phrase occurrences.
5530 ** * If the phrase is part of a NEAR expression, then only phrase instances
5531 ** that meet the NEAR constraint are included in the counts.
5533 int sqlite3Fts3EvalPhraseStats(
5534 Fts3Cursor
*pCsr
, /* FTS cursor handle */
5535 Fts3Expr
*pExpr
, /* Phrase expression */
5536 u32
*aiOut
/* Array to write results into (see above) */
5538 Fts3Table
*pTab
= (Fts3Table
*)pCsr
->base
.pVtab
;
5542 if( pExpr
->bDeferred
&& pExpr
->pParent
->eType
!=FTSQUERY_NEAR
){
5543 assert( pCsr
->nDoc
>0 );
5544 for(iCol
=0; iCol
<pTab
->nColumn
; iCol
++){
5545 aiOut
[iCol
*3 + 1] = (u32
)pCsr
->nDoc
;
5546 aiOut
[iCol
*3 + 2] = (u32
)pCsr
->nDoc
;
5549 rc
= fts3EvalGatherStats(pCsr
, pExpr
);
5550 if( rc
==SQLITE_OK
){
5551 assert( pExpr
->aMI
);
5552 for(iCol
=0; iCol
<pTab
->nColumn
; iCol
++){
5553 aiOut
[iCol
*3 + 1] = pExpr
->aMI
[iCol
*3 + 1];
5554 aiOut
[iCol
*3 + 2] = pExpr
->aMI
[iCol
*3 + 2];
5563 ** The expression pExpr passed as the second argument to this function
5564 ** must be of type FTSQUERY_PHRASE.
5566 ** The returned value is either NULL or a pointer to a buffer containing
5567 ** a position-list indicating the occurrences of the phrase in column iCol
5568 ** of the current row.
5570 ** More specifically, the returned buffer contains 1 varint for each
5571 ** occurrence of the phrase in the column, stored using the normal (delta+2)
5572 ** compression and is terminated by either an 0x01 or 0x00 byte. For example,
5573 ** if the requested column contains "a b X c d X X" and the position-list
5574 ** for 'X' is requested, the buffer returned may contain:
5576 ** 0x04 0x05 0x03 0x01 or 0x04 0x05 0x03 0x00
5578 ** This function works regardless of whether or not the phrase is deferred,
5579 ** incremental, or neither.
5581 int sqlite3Fts3EvalPhrasePoslist(
5582 Fts3Cursor
*pCsr
, /* FTS3 cursor object */
5583 Fts3Expr
*pExpr
, /* Phrase to return doclist for */
5584 int iCol
, /* Column to return position list for */
5585 char **ppOut
/* OUT: Pointer to position list */
5587 Fts3Phrase
*pPhrase
= pExpr
->pPhrase
;
5588 Fts3Table
*pTab
= (Fts3Table
*)pCsr
->base
.pVtab
;
5591 sqlite3_int64 iDocid
;
5593 /* If this phrase is applies specifically to some column other than
5594 ** column iCol, return a NULL pointer. */
5596 assert( iCol
>=0 && iCol
<pTab
->nColumn
);
5597 if( (pPhrase
->iColumn
<pTab
->nColumn
&& pPhrase
->iColumn
!=iCol
) ){
5601 iDocid
= pExpr
->iDocid
;
5602 pIter
= pPhrase
->doclist
.pList
;
5603 if( iDocid
!=pCsr
->iPrevId
|| pExpr
->bEof
){
5604 int bDescDoclist
= pTab
->bDescIdx
; /* For DOCID_CMP macro */
5605 int iMul
; /* +1 if csr dir matches index dir, else -1 */
5609 Fts3Expr
*p
; /* Used to iterate from pExpr to root */
5610 Fts3Expr
*pNear
; /* Most senior NEAR ancestor (or pExpr) */
5612 /* Check if this phrase descends from an OR expression node. If not,
5613 ** return NULL. Otherwise, the entry that corresponds to docid
5614 ** pCsr->iPrevId may lie earlier in the doclist buffer. Or, if the
5615 ** tree that the node is part of has been marked as EOF, but the node
5616 ** itself is not EOF, then it may point to an earlier entry. */
5618 for(p
=pExpr
->pParent
; p
; p
=p
->pParent
){
5619 if( p
->eType
==FTSQUERY_OR
) bOr
= 1;
5620 if( p
->eType
==FTSQUERY_NEAR
) pNear
= p
;
5621 if( p
->bEof
) bTreeEof
= 1;
5623 if( bOr
==0 ) return SQLITE_OK
;
5625 /* This is the descendent of an OR node. In this case we cannot use
5626 ** an incremental phrase. Load the entire doclist for the phrase
5627 ** into memory in this case. */
5628 if( pPhrase
->bIncr
){
5630 int bEofSave
= pExpr
->bEof
;
5631 fts3EvalRestart(pCsr
, pExpr
, &rc
);
5632 while( rc
==SQLITE_OK
&& !pExpr
->bEof
){
5633 fts3EvalNextRow(pCsr
, pExpr
, &rc
);
5634 if( bEofSave
==0 && pExpr
->iDocid
==iDocid
) break;
5636 pIter
= pPhrase
->doclist
.pList
;
5637 assert( rc
!=SQLITE_OK
|| pPhrase
->bIncr
==0 );
5638 if( rc
!=SQLITE_OK
) return rc
;
5641 iMul
= ((pCsr
->bDesc
==bDescDoclist
) ? 1 : -1);
5644 && (DOCID_CMP(pNear
->iDocid
, pCsr
->iPrevId
) * iMul
)<0
5647 fts3EvalNextRow(pCsr
, pExpr
, &rc
);
5648 if( rc
!=SQLITE_OK
) return rc
;
5649 iDocid
= pExpr
->iDocid
;
5650 pIter
= pPhrase
->doclist
.pList
;
5653 bEof
= (pPhrase
->doclist
.nAll
==0);
5654 assert( bDescDoclist
==0 || bDescDoclist
==1 );
5655 assert( pCsr
->bDesc
==0 || pCsr
->bDesc
==1 );
5658 if( pCsr
->bDesc
==bDescDoclist
){
5661 /* This expression is already at EOF. So position it to point to the
5662 ** last entry in the doclist at pPhrase->doclist.aAll[]. Variable
5663 ** iDocid is already set for this entry, so all that is required is
5664 ** to set pIter to point to the first byte of the last position-list
5667 ** It would also be correct to set pIter and iDocid to zero. In
5668 ** this case, the first call to sqltie3Fts4DoclistPrev() below
5669 ** would also move the iterator to point to the last entry in the
5670 ** doclist. However, this is expensive, as to do so it has to
5671 ** iterate through the entire doclist from start to finish (since
5672 ** it does not know the docid for the last entry). */
5673 pIter
= &pPhrase
->doclist
.aAll
[pPhrase
->doclist
.nAll
-1];
5674 fts3ReversePoslist(pPhrase
->doclist
.aAll
, &pIter
);
5676 while( (pIter
==0 || DOCID_CMP(iDocid
, pCsr
->iPrevId
)>0 ) && bEof
==0 ){
5677 sqlite3Fts3DoclistPrev(
5678 bDescDoclist
, pPhrase
->doclist
.aAll
, pPhrase
->doclist
.nAll
,
5679 &pIter
, &iDocid
, &dummy
, &bEof
5687 while( (pIter
==0 || DOCID_CMP(iDocid
, pCsr
->iPrevId
)<0 ) && bEof
==0 ){
5688 sqlite3Fts3DoclistNext(
5689 bDescDoclist
, pPhrase
->doclist
.aAll
, pPhrase
->doclist
.nAll
,
5690 &pIter
, &iDocid
, &bEof
5696 if( bEof
|| iDocid
!=pCsr
->iPrevId
) pIter
= 0;
5698 if( pIter
==0 ) return SQLITE_OK
;
5702 pIter
+= fts3GetVarint32(pIter
, &iThis
);
5706 while( iThis
<iCol
){
5707 fts3ColumnlistCopy(0, &pIter
);
5708 if( *pIter
==0x00 ) return 0;
5710 pIter
+= fts3GetVarint32(pIter
, &iThis
);
5713 *ppOut
= ((iCol
==iThis
)?pIter
:0);
5718 ** Free all components of the Fts3Phrase structure that were allocated by
5719 ** the eval module. Specifically, this means to free:
5721 ** * the contents of pPhrase->doclist, and
5722 ** * any Fts3MultiSegReader objects held by phrase tokens.
5724 void sqlite3Fts3EvalPhraseCleanup(Fts3Phrase
*pPhrase
){
5727 sqlite3_free(pPhrase
->doclist
.aAll
);
5728 fts3EvalInvalidatePoslist(pPhrase
);
5729 memset(&pPhrase
->doclist
, 0, sizeof(Fts3Doclist
));
5730 for(i
=0; i
<pPhrase
->nToken
; i
++){
5731 fts3SegReaderCursorFree(pPhrase
->aToken
[i
].pSegcsr
);
5732 pPhrase
->aToken
[i
].pSegcsr
= 0;
5739 ** Return SQLITE_CORRUPT_VTAB.
5742 int sqlite3Fts3Corrupt(){
5743 return SQLITE_CORRUPT_VTAB
;
5749 ** Initialize API pointer table, if required.
5752 __declspec(dllexport
)
5754 int sqlite3_fts3_init(
5757 const sqlite3_api_routines
*pApi
5759 SQLITE_EXTENSION_INIT2(pApi
)
5760 return sqlite3Fts3Init(db
);