hd_keywords *fts3 FTS3 source [file join $::DOC pages fancyformat.tcl] fancyformat_document "SQLite FTS3 Extension" {} {

Overview

[h1 "Introduction to FTS3"]

The FTS3 extension module allows users to create special tables with a built-in full-text index (hereafter "FTS3 tables"). The full-text index allows the user to efficiently query the database for all rows that contain one or more instances specified word (hereafter a "token", even if the table contains many large documents.

For example, if each of the 517430 documents in the "Enron E-Mail Dataset" is inserted into both the FTS3 table and the ordinary SQLite table created using the following SQL script: [Code { CREATE VIRTUAL TABLE enrondata1 USING fts3(content TEXT); /* FTS3 table */ CREATE TABLE enrondata2(content TEXT); /* Ordinary table */ }]

Then either of the two queries below may be executed to find the number of documents in the database that contain the word "linux" (351). Using one desktop PC hardware configuration, the query on the FTS3 table returns in approximately 0.03 seconds, versus 22.5 for querying the ordinary table. [Code { SELECT count(*) FROM enrondata1 WHERE content MATCH 'linux'; /* 0.03 seconds */ SELECT count(*) FROM enrondata2 WHERE content LIKE '%linux%'; /* 22.5 seconds */ }]

Of course, the two queries above are not entirely equivalent. For example the LIKE query matches rows that contain terms such as "linuxophobe" or "EnterpriseLinux" (as it happens, the Enron E-Mail Dataset does not actually contain any such terms), whereas the MATCH query on the FTS3 table selects only those rows that contain "linux" as a discreet token. Both searches are case-insensitive. The FTS3 table consumes around 2006 MB on disk compared to just 1453 MB for the ordinary table. Using the same hardware configuration used to perform the SELECT queries above, the FTS3 table took just over 39 minutes to populate, versus 25 for the ordinary table.

Check if the numbers are still valid using the refactored version. [h2 "Creating and Destroying FTS3 Tables"]

Like other virtual table types, new FTS3 tables are created using a \[CREATE VIRTUAL TABLE\] statement. The module name, which follows the USING keyword, is "fts3". The virtual table module arguments may be left empty, in which case an FTS3 table with a single user-defined column named "content" is created. Alternatively, the module arguments may be passed a list of comma separated column names.

If column names are explicitly provided for the FTS3 table as part of the CREATE VIRTUAL TABLE statement, then a datatype name may be optionally specified for each column. However, this is pure syntactic sugar, the supplied typenames are not used by FTS3 or the SQLite core for any purpose. The same applies to any constraints specified along with an FTS3 column name - they are parsed but not used or recorded by the system in any way. [Code { -- Create an FTS3 table named "data" with one column - "content": CREATE VIRTUAL TABLE data USING fts3(); -- Create an FTS3 table named "pages" with three columns: CREATE VIRTUAL TABLE pages USING fts3(title, keywords, body); -- Create an FTS3 table named "mail" with two columns. Datatypes -- and column constraints are specified along with each column. These -- are completely ignored by FTS3 and SQLite. CREATE VIRTUAL TABLE mail USING fts3( subject VARCHAR(256) NOT NULL, body TEXT CHECK(length(body)<10240) ); }]

As well as a list of columns, the module arguments passed to a CREATE VIRTUAL TABLE statement used to create an FTS3 table may be used to specify a \[custom tokenizer\]. This is done by specifying a string of the form "tokenize=<tokenizer name>" in place of a column name. A tokenizer specification may be placed anywhere in the column list, but at most one tokenizer declaration is allowed for each CREATE VIRTUAL TABLE statement. The second and subsequent tokenizer declaration are interpreted as column names. \[custom tokenizer|See below\] for a detailed description of implementing and using a custom tokenizer. [Code { -- Create an FTS3 table named "papers" with two columns that uses -- the custom tokenizer "porter". CREATE VIRTUAL TABLE papers USING fts3(author, document, tokenize=porter); -- Create an FTS3 table with a single column - "content" - that uses -- the "simple" tokenizer. CREATE VIRTUAL TABLE data USING fts3(tokenize=simple); }]

FTS3 tables may be dropped from the database using an ordinary \[DROP TABLE\] statement. For example: [Code { -- Create, then immediately drop, an FTS3 table. CREATE VIRTUAL TABLE data USING fts3(); DROP TABLE data; }] [h2 "Populating FTS3 Tables"]

FTS3 tables are populated using \[INSERT\], \[UPDATE\] and \[DELETE\] statements in the same way as ordinary SQLite tables are.

As well as the columns named by the user (or the "content" column if no module arguments where specified as part of the \[CREATE VIRTUAL TABLE\] statement), each FTS3 table has a "rowid" column that behaves like an \[INTEGER PRIMARY KEY\], except that values remain unchanged if the database is rebuilt using the \[VACUUM\] command. For FTS3 tables, "docid" is allowed as an alias along with the usual "rowid", "oid" and "_oid_" identifiers. Attempting to insert or update a row with a docid value that already exists in the table is an error, just as it would be with an ordinary SQLite table. [Code { -- Create an FTS3 table CREATE VIRTUAL TABLE pages USING fts3(title, body); -- Insert a row with a specific docid value. INSERT INTO pages(docid, title, body) VALUES(53, 'Home Page', 'SQLite is a software...'); -- Insert a row and allow FTS3 to assign a docid value using the same algorithm as -- SQLite uses for ordinary tables. In this case the new docid will be 54, -- one greater than the largest docid currently present in the table. INSERT INTO pages(title, body) VALUES('Download', 'All SQLite source code...'); -- Change the title of the row just inserted. UPDATE pages SET title = 'Download SQLite' WHERE rowid = last_insert_rowid(); -- Delete the entire table contents. DELETE FROM pages; }]

To support full-text queries, FTS3 maintains an inverted index that maps from each unique term or word that appears in the dataset to the locations in which it appears within the table contents. For the curious, a complete description of the \[segment btree|data structure\] used to store this index within the database file is described below. A feature of this data structure is that at any time the database may contain not one index b-tree, but several different b-trees that are incrementally merged as rows are inserted, updated and deleted. This technique improves performance when writing to an FTS3 table, but causes some overhead for full-text queries that use the index. Executing an SQL statement of the form "SELECT optimize(<fts3-table>) FROM <fts3-table>" causes FTS3 to merge all existing index b-trees into a single large b-tree containing the entire index. This can be an expensive operation, but may speed up future queries.

For example, to optimize the full-text index for an FTS3 table named "docs": [Code { -- Optimize the internal structure of FTS3 table "docs". SELECT optimize(docs) FROM docs LIMIT 1; }]

The statement above may appear syntacticly incorrect to some. Refer to the section describing the \[snippets()|FTS3 auxillary functions\] for a description of why it is not.

The optimize() function returns a text value. If the index was already optimized when it was called the text is "Index already optimal". Otherwise if the index was not already optimized, it is made so and the text "Index optimized" returned. [h2 "Querying FTS3 Tables" {} {simple fts3 queries}]

Some note clarifying what is meant by a "term", and how that relates to the specific tokenizer used by the FTS3 table in question.

As for all other SQLite tables, virtual or otherwise, data is retrieved from FTS3 tables using a \[SELECT\] statement.

FTS3 tables can be queried efficiently using SELECT statements of two different forms:

If neither of the two query strategies enumerated above can be used, all queries on FTS3 tables are implemented using a linear scan of the entire table. If the table contains large amounts of data, this may be an impractically approach (the first example on this page shows that a linear scan of 1.5 GB of data takes around 30 seconds using a modern PC). [Code { -- The examples in this block assume the following FTS3 table: CREATE VIRTUAL TABLE mail USING fts3(subject, body); SELECT * FROM mail WHERE rowid = 15; -- Fast. Rowid lookup. SELECT * FROM mail WHERE body MATCH 'sqlite'; -- Fast. Full-text query. SELECT * FROM mail WHERE mail MATCH 'search'; -- Fast. Full-text query. SELECT * FROM mail WHERE rowid BETWEEN 15 AND 20; -- Slow. Linear scan. SELECT * FROM mail WHERE subject = 'database'; -- Slow. Linear scan. SELECT * FROM mail WHERE subject MATCH 'database'; -- Fast. Full-text query. }]

In all of the full-text queries above, the right-hand operand of the MATCH operator is a string consisting of a single word. In this case, the MATCH expression evaluates to true for all documents that contain one or more instances of the specified word ("sqlite", "search" or "database", depending on which example you look at). Specifying a single word as the right-hand operand of the MATCH operator results in the simplest (and most common) type of full-text query possible. However more complicated queries are possible, including phrase searches, term-prefix searches and searches for documents containing combinations of terms occuring within a defined proximity of each other. The various ways in which the full-text index may be queried are \[FTS3 MATCH|described below\].

The paragraph above notes that a MATCH operator with a simple word as the right-hand operand evaluates to true for all documents that contain the specified term. In this context, the "document" may refer to either the data stored in a single column of a row of an FTS3 table, or to the contents of all columns in a single row, depending on the identifier used as the left-hand operand to the MATCH operator. If the identifier specified as the left-hand operand of the MATCH operator is an FTS3 table column name, then the document that the search term must be contained in is the value stored in the specified column. However, if the identifier is the name of the FTS3 table itself, then the MATCH operator evaluates to true for each row of the FTS3 table for which any column contains the search term. The following example demonstrates this: [Code { -- Example schema CREATE VIRTUAL TABLE mail USING fts3(subject, body); -- Example table population INSERT INTO mail(docid, subject, body) VALUES(1, 'software feedback', 'found it too slow'); INSERT INTO mail(docid, subject, body) VALUES(2, 'software feedback', 'no feedback'); INSERT INTO mail(docid, subject, body) VALUES(3, 'slow lunch order', 'was a software problem'); -- Example queries SELECT * FROM mail WHERE subject MATCH 'software'; -- Selects rows 1 and 2 SELECT * FROM mail WHERE body MATCH 'feedback'; -- Selects row 2 SELECT * FROM mail WHERE mail MATCH 'software'; -- Selects rows 1, 2 and 3 SELECT * FROM mail WHERE mail MATCH 'slow'; -- Selects rows 1 and 3 }]

At first glance, the final two full-text queries in the example above seem to be syntacticly incorrect, as there is a table name ("mail") used as an SQL expression. The reason this is acceptable is that each FTS3 table actually has a \[sqlite3_declare_vtab|HIDDEN\] column with the same name as the table itself (in this case, "mail"). The value stored in this column is not meaningful to the application, but can be used as the left-hand operand to a MATCH operator. This special column may also be passed as an argument to the \[snippets()|FTS3 auxillary functions\].

The following example illustrates the above. The expressions "docs", "docs.docs" and "main.docs.docs" all refer to column "docs". However, the expression "main.docs" does not refer to any column. It could be used to refer to a table, but a table name is not allowed in the context in which it is used below. [Code { -- Example schema CREATE VIRTUAL TABLE docs USING fts3(content); -- Example queries SELECT * FROM docs WHERE docs MATCH 'sqlite'; -- OK. SELECT * FROM docs WHERE docs.docs MATCH 'sqlite'; -- OK. SELECT * FROM docs WHERE main.docs.docs MATCH 'sqlite'; -- OK. SELECT * FROM docs WHERE main.docs MATCH 'sqlite'; -- Error. }] [h2 "Summary"]

From the users point of view, FTS3 tables are similar to ordinary SQLite tables in many ways. Data may be added to, modified within and removed from FTS3 tables using the INSERT, UPDATE and DELETE commands just as it may be with ordinary tables. Similarly, the SELECT command may be used to query data. The following list summarizes the differences between FTS3 and ordinary tables:

  1. As with all virtual table types, it is not possible to create indices or triggers attached to FTS3 tables. Nor is it possible to use the ALTER TABLE command to add extra columns to FTS3 tables (although it is possible to use ALTER TABLE to rename an FTS3 table).

  2. Data-types specified as part of the "CREATE VIRTUAL TABLE" statement used to create an FTS3 table are ignored completely. Instead of the normal rules for applying type \[affinity\] to inserted values, all values inserted into FTS3 table columns (except the special rowid column) are converted to type TEXT before being stored.

  3. FTS3 tables permit the special alias "docid" to be used to refer to the rowid column supported by all \[virtual tables\].

  4. The \[FTS3 MATCH\] operator is supported for queries based on the built-in full-text index.

  5. The FTS3 auxillary functions, \[snippets|snippets() and offsets()\], are available to support full-text queries.

  6. Each FTS3 table has a \[sqlite3_declare_vtab()|HIDDEN column\] with the same name as the table itself. The value contained in each row for the special column is only useful when used on the left-hand side of a \[FTS3 MATCH|MATCH\] operator, or when specified as an argument to one of the \[snippets|FTS3 auxillary functions\].

[h1 "Compiling and Enabling FTS3"]

Although FTS3 is distributed as part of the SQLite source code, it is not enabled by default. To build SQLite with FTS3 functionality enabled, define the preprocessor macro \[SQLITE_ENABLE_FTS3\] when compiling. New applications should also define the \[SQLITE_ENABLE_FTS3_PARENTHESIS\] macro to enable the advanced query syntax (see below). Usually, this is done by adding the following two switches to the compiler command line: [Code { -DSQLITE_ENABLE_FTS3 -DSQLITE_ENABLE_FTS3_PARENTHESIS }]

If using the amalgamation autoconf based build system, setting the CPPFLAGS environment variable while running the 'configure' script is an easy way to set these macros. For example, the following command: [Code { CPPFLAGS="-DSQLITE_ENABLE_FTS3 -DSQLITE_ENABLE_FTS3_PARENTHESIS" ./configure <configure options> }]

where <configure options> are those options normally passed to the configure script, if any.

Because FTS3 is a virtual table, it is incompatible with the \[SQLITE_OMIT_VIRTUALTABLE\] option.

If an SQLite build does not include FTS3, then any attempt to prepare an SQL statement to create an FTS3 table or to drop or access an existing FTS3 table in any way will fail. The error message returned will be similar to "no such module: fts3". [h1 "Full-text Index Queries" {} {FTS3 MATCH}]

The most useful thing about FTS3 tables is the queries that may be performed using the built-in full-text index. Full-text queries are performed by specifying a clause of the form "<column> MATCH <full-text query expression>" to the WHERE clause of a SELECT statement that reads data from an FTS3 table. \[simple fts3 queries|Simple FTS3 queries\] that return all documents that contain a given term are described above. In that discussion the right-hand operand of the MATCH operator was assumed to be a string consisting of a single term. This section describes the more complex query types supported by FTS3 tables, and how they may be utilized by specifying more a more complex query expression as the right-hand operand of a MATCH operator.

Where should the column selection syntax go?

FTS3 tables support three basic query types:

[Code { -- Query for all documents containing the term "linux": SELECT * FROM docs WHERE docs MATCH 'linux'; -- Query for all documents containing a term with the prefix "lin". This will match -- all documents that contain "linux", but also those that contain terms "linear", --"linker", "linguistic" and so on. SELECT * FROM docs WHERE docs MATCH 'lin*'; }] [Code { -- Query for all documents that contain the phrase "linux applications". SELECT * FROM docs WHERE docs MATCH '"linux applications"'; -- Query for all documents that contain a phrase that matches "lin* app*". As well as -- "linux applications", this will match common phrases such as "linoleum appliances" -- or "link apprentice". SELECT * FROM docs WHERE docs MATCH '"lin* app*"'; }] [Code { -- Virtual table declaration. CREATE VIRTUAL TABLE docs USING fts3(); -- Virtual table data. INSERT INTO docs VALUES('SQLite is an ACID compliant embedded relational database management system'); -- Search for a document that contains the terms "sqlite" and "database" with -- not more than 10 intervening terms. This matches the only document in -- table docs (since there are only six terms between "SQLite" and "database" -- in the document). SELECT * FROM docs WHERE docs MATCH 'sqlite NEAR database'; -- Search for a document that contains the terms "sqlite" and "database" with -- not more than 6 intervening terms. This also matches the only document in -- table docs. Note that the order in which the terms appear in the document -- does not have to be the same as the order in which they appear in the query. SELECT * FROM docs WHERE docs MATCH 'database NEAR/6 sqlite'; -- Search for a document that contains the terms "sqlite" and "database" with -- not more than 5 intervening terms. This query matches no documents. SELECT * FROM docs WHERE docs MATCH 'database NEAR/5 sqlite'; -- Search for a document that contains the phrase "ACID compliant" and the term -- "database" with not more than 2 terms separating the two. This matches the -- document stored in table docs. SELECT * FROM docs WHERE docs MATCH 'database NEAR/2 "ACID compliant"'; -- Search for a document that contains the phrase "ACID compliant" and the term -- "sqlite" with not more than 2 terms separating the two. This also matches -- the only document stored in table docs. SELECT * FROM docs WHERE docs MATCH '"ACID compliant" NEAR/2 sqlite'; }] [Code { -- The following query selects documents that contains an instance of the term -- "sqlite" separated by two or fewer terms from an instance of the term "acid", -- which is in turn separated by two or fewer terms from an instance of the term -- "relational". As it happens, the only document in table docs satisfies this criteria. SELECT * FROM docs WHERE docs MATCH 'sqlite NEAR/2 acid NEAR/2 relational'; -- This query matches no documents. There is an instance of the term "sqlite" with -- sufficient proximity to an instance of "acid" but it is not sufficiently close -- to an instance of the term "relational". SELECT * FROM docs WHERE docs MATCH 'acid NEAR/2 sqlite NEAR/2 relational'; }]

Phrase and NEAR queries may not span multiple columns within a row.

The three basic query types described above may be used to query the full-text index for the set of documents that match the specified criteria. Using the FTS3 query expression language it is possible to perform various set operations on the results of basic queries. There are currently three supported operations:

[h2 "Set Operations Using The Enhanced MATCH Syntax"] [h2 "Set Operations Using The Standard MATCH Syntax"] [h1 "Auxillary functions - Snippets and Offsets" {} snippets offsets] [h1 "Custom Tokenizers" customtokenizer {custom tokenizer}] [h1 "Data Structures" {} {segment btree}]

This section describes at a high-level the way the FTS3 module stores its index and content in the database. It is not necessary to read or understand the material in this section in order to use FTS3 in an application. However, it may be useful to application developers attempting to analyze and understand FTS3 performance characteristics, or to developers contemplating enhancements to the existing FTS3 feature set.

For each FTS3 virtual table in a database, three real (non-virtual) tables are created to store the underlying data. The real tables are named "%_content", "%_segdir" and "%_segments", where "%" is replaced by the name supplied by the user for the FTS3 virtual table.

The leftmost column of the "%_content" table is an INTEGER PRIMARY KEY field named "docid". Following this is one column for each column of the FTS3 virtual table as declared by the user, named by prepending the column name supplied by the user with "cN", where N is the index of the column within the table, numbered from left to right starting with 1. Data types supplied as part of the virtual table declaration are not used as part of the %_content table declaration. For example: [Code { -- Virtual table declaration CREATE VIRTUAL TABLE abc USING FTS3(a NUMBER, b TEXT, c); -- Corresponding %_content table declaration CREATE TABLE abc_content(docid INTEGER PRIMARY KEY, c1a, c2b, c2c); }]

The %_content table contains the unadulterated data inserted by the user into the FTS3 virtual table by the user. If the user does not explicitly supply a "docid" value when inserting records, one is selected automatically by the system.

The two remaining tables, %_segments and %_segdir, are used to store the full-text index. Conceptually, this index is a lookup table that maps each term (word) to the set of docid values corresponding to records in the %_content table that contain one or more occurrences of the term. To retrieve all documents that contain a specified term, the FTS3 module queries this index to determine the set of docid values for records that contain the term, then retrieves the required documents from the %_content table. Regardless of the schema of the FTS3 virtual table, the %_segments and %_segdir tables are always created as follows: [Code { CREATE TABLE %_segments( blockid INTEGER PRIMARY KEY, -- B-tree node id block blob -- B-tree node data ); CREATE TABLE %_segdir( level INTEGER, idx INTEGER, start_block INTEGER, -- Blockid of first node in %_segments leaves_end_block INTEGER, -- Blockid of last leaf node in %_segments end_block INTEGER, -- Blockid of last node in %_segments root BLOB, -- B-tree root node PRIMARY KEY(level, idx) ); }]

The schema depicted above is not designed to store the full-text index directly. Instead, it is used to one or more b-tree structures. There is one b-tree for each row in the %_segdir table. The %_segdir table row contains the root node and various meta-data associated with the b-tree structure, and the %_segments table contains all other (non-root) b-tree nodes. Each b-tree is referred to as a "segment". Once it has been created, a segment b-tree is never updated (although it may be deleted altogether).

The keys used by each segment b-tree are terms (words). As well as the key, each segment b-tree entry has an associated "doclist" (document list). A doclist consists of zero or more entries, where each entry consists of:

Entries within a doclist are sorted by docid. Positions within a doclist entry are stored in ascending order.

The contents of the logical full-text index is found by merging the contents of all segment b-trees. If a term is present in more than one segment b-tree, then it maps to the union of each individual doclist. If, for a single term, the same docid occurs in more than one doclist, then only the doclist that is part of the most recently created segment b-tree is considered valid.

Multiple b-tree structures are used instead of a single b-tree to reduce the cost of inserting records into FTS3 tables. When a new record is inserted into an FTS3 table that already contains a lot of data, it is likely that many of the terms in the new record are already present in a large number of existing records. If a single b-tree were used, then large doclist structures would have to be loaded from the database, amended to include the new docid and term-offset list, then written back to the database. Using multiple b-tree tables allows this to be avoided by creating a new b-tree which can be merged with the existing b-tree (or b-trees) later on. Merging of b-tree structures can be performed as a background task, or once a certain number of separate b-tree structures have been accumulated. Of course, this scheme makes queries more expensive (as the FTS3 code may have to look up individual terms in more than one b-tree and merge the results), but it has been found that in practice this overhead is often negligible. [h2 "Variable Length Integer (varint) Format"]

Integer values stored as part of segment b-tree nodes are encoded using the FTS3 varint format. This encoding is similar, but not identical, to the the SQLite varint format.

An encoded FTS3 varint consumes between one and ten bytes of space. The number of bytes required is determined by the sign and magnitude of the integer value encoded. More accurately, the number of bytes used to store the encoded integer depends on the position of the most significant set bit in the 64-bit twos-compliment representation of the integer value. Negative values always have the most significant bit set (the sign bit), and so are always stored using the full ten bytes. Positive integer values may be stored using less space.

The final byte of an encoded FTS3 varint has its most significant bit cleared. All preceding bytes have the most significant bit set. Data is stored in the remaining seven least signficant bits of each byte. The first byte of the encoded representation contains the least significant seven bits of the encoded integer value. The second byte of the encoded representation, if it is present, contains the seven next least significant bits of the integer value, and so on. The following table contains examples of encoded integer values: [Table] [Tr]DecimalHexadecimalEncoded Representation [Tr]430x000000000000002B0x2B [Tr]2008150x000000000003106F0x9C 0xA0 0x0C [Tr]-10xFFFFFFFFFFFFFFFF0xFF 0xFF 0xFF 0xFF 0xFF 0xFF 0xFF 0xFF 0xFF 0x01 [h2 "Segment B-Tree Format"]

Segment b-trees are prefix-compressed b+-trees. There is one segment b-tree for each row in the %_segdir table (see above). The root node of the segment b-tree is stored as a blob in the "root" field of the corresponding row of the %_segdir table. All other nodes (if any exist) are stored in the "blob" column of the %_segments table. Nodes within the %_segments table are identified by the integer value in the blockid field of the corresponding row. The following table describes the fields of the %_segdir table: [Table] [Tr]Column Interpretion [Tr]level Between them, the contents of the "level" and "idx" fields define the relative age of the segment b-tree. The smaller the value stored in the "level" field, the more recently the segment b-tree was created. If two segment b-trees are of the same "level", the segment with the larger value stored in the "idx" column is more recent. The PRIMARY KEY constraint on the %_segdir table prevents any two segments from having the same value for both the "level" and "idx" fields. [Tr]idx See above. [Tr]start_block The blockid that corresponds to the node with the smallest blockid that belongs to this segment b-tree. Or zero if the entire segment b-tree fits on the root node. If it exists, this node is always a leaf node. [Tr]leaves_end_block The blockid that corresponds to the leaf node with the largest blockid that belongs to this segment b-tree. Or zero if the entire segment b-tree fits on the root node. [Tr]end_block The blockid that corresponds to the interior node with the largest blockid that belongs to this segment b-tree. Or zero if the entire segment b-tree fits on the root node. If it exists, this node is always an interior node. [Tr]root Blob containing the root node of the segment b-tree.

Apart from the root node, the nodes that make up a single segment b-tree are always stored using a contiguous sequence of blockids. Furthermore, the nodes that make up a single level of the b-tree are themselves stored as a contiguous block, in b-tree order. The contiguous sequence of blockids used to store the b-tree leaves are allocated starting with the blockid value stored in the "start_block" column of the corresponding %_segdir row, and finishing at the blockid value stored in the "leaves_end_block" field of the same row. It is therefore possible to iterate through all the leaves of a segment b-tree, in key order, by traversing the %_segments table in blockid order from "start_block" to "leaves_end_block". [h3 "Segment B-Tree Leaf Nodes"]

The following diagram depicts the format of a segment b-tree leaf node. [Fig fts3_leaf_node.png "Segment B-Tree Leaf Node Format"]

The first term stored on each node ("Term 1" in the figure above) is stored verbatim. Each subsequent term is prefix-compressed with respect to its predecessor. Terms are stored within a page in sorted (memcmp) order. [h3 "Segment B-Tree Interior Nodes"]

The following diagram depicts the format of a segment b-tree interior (non-leaf) node. [Fig fts3_interior_node.png "Segment B-Tree Interior Node Format"] [h2 "Doclist Format"]

A doclist consists of an array of 64-bit signed integers, serialized using the FTS3 varint format. Each doclist entry is made up of a series of two or more integers, as follows:

  1. The docid value. The first entry in a doclist contains the literal docid value. The first field of each subsequent doclist entry contains the difference between the new docid and the previous one (always a positive number).
  2. Zero or more term-offset lists. A term-offset list is present for each column of the FTS3 virtual table that contains the term. A term-offset list consists of the following:
    1. Constant value 1. This field is omitted for any term-offset list associated with column 0.
    2. The column number (1 for the second leftmost column, etc.). This field is omitted for any term-offset list associated with column 0.
    3. A list of term-offsets, sorted from smallest to largest. Instead of storing the term-offset value literally, each integer stored is the difference between the current term-offset and the previous one (or zero if the current term-offset is the first), plus 2.
  3. Constant value 0.
[Fig fts3_doclist2.png "FTS3 Doclist Format"] [Fig fts3_doclist.png "FTS3 Doclist Entry Format"]

For doclists for which the term appears in more than one column of the FTS3 virtual table, term-offset lists within the doclist are stored in column number order. This ensures that the term-offset list associated with column 0 (if any) is always first, allowing the first two fields of the term-offset list to be omitted in this case. }