Full-text search

Full-text search here is about terms, not patterns. A term is a whole word, produced by an analyzer, and that is what separates this from LIKE '%…%'.

The analyzer belongs to the field

An analyzer is declared once and attached where it is needed:

DEFINE ANALYZER simple FILTERS lowercase, ascii;
DEFINE COLLECTION notes;
DEFINE FIELD body ON notes TYPE string ANALYZER simple;

It attaches to a field, not to an index. That single decision is what makes the property below hold.

There are three filters, and they are applied in the order you write them:

A name is unique like every other name, and IF NOT EXISTS says so out loud:

DEFINE ANALYZER IF NOT EXISTS simple FILTERS lowercase;

A filter the language does not have is refused where it is written, rather than accepted and ignored:

DEFINE ANALYZER stemmed FILTERS porter;

Refused — UnexpectedToken. The stemmer here is Porter2, but the filter is named for what it does rather than for who published it, and a filter the language does not have is not quietly ignored.

Matching

CREATE notes:1 = { body: 'Ada Lovelace wrote the first program', title: 'Ada' };
CREATE notes = { body: 'A note about the café on the corner' };
CREATE notes:3 = { body: 'lovelacex is not the same word' };
CREATE notes = { title: 'no body at all' };

A term is a whole word:

SELECT * FROM notes WHERE body MATCHES 'lovelace';

One row. notes:3 holds lovelacex, which is a different term — a substring search would have returned it.

The filters are what make two spellings one term:

SELECT * FROM notes WHERE body MATCHES 'cafe';

One row: ascii folded café.

Several terms mean all of them:

SELECT * FROM notes WHERE body MATCHES 'ada program';

One row. MATCHES 'ada babbage' returns none.

Stemming makes two words one term

lowercase and ascii make two spellings of one word meet. stemmer is the one that makes two words meet, which is usually what a person means by search:

DEFINE ANALYZER english FILTERS lowercase, ascii, stemmer;
DEFINE COLLECTION articles;
DEFINE FIELD body ON articles TYPE string ANALYZER english;
CREATE articles:1 = { body: 'Taking backups of a running store' };

SELECT * FROM articles WHERE body MATCHES 'backup running';

One row, from text that spells neither word the way the query does: backups and backup reduce to one term, and so do running and run.

Leaving the filter out costs recall and says nothing about it. notes above is analysed by simple, which has no stemmer:

SELECT * FROM notes WHERE body MATCHES 'programs';

No rows, from a collection that plainly contains the word program. No error, no warning — just a smaller answer than the one asked for, which is why this is worth knowing before you go looking for the bug.

The order is yours, and it decides whether the filter does anything

Porter2 is defined over lower-case words, so a chain that stems before it lowercases hands the stemmer words it declines to touch:

DEFINE ANALYZER unordered FILTERS stemmer, lowercase;
DEFINE COLLECTION drafts;
DEFINE FIELD body ON drafts TYPE string ANALYZER unordered;
CREATE drafts:1 = { body: 'Taking Backups' };

SELECT * FROM drafts WHERE body MATCHES 'backup';

No rows. Backups carries a capital, so the stemmer passed it through unchanged, and lowercasing afterwards left backups — which is not the term the query reduced to. The filter declines rather than half-stemming, because a half-stem is a term neither spelling of the word reaches.

Another language is another filter

stemmer is English, and it stems only lower-case ASCII words: a word carrying a capital, a digit, or a letter outside ASCII passes through unchanged. A filter that silently applied English rules to another language would do that damage across a whole corpus, so each language is its own filter — stemmer(russian), stemmer(german), stemmer(french) and stemmer(spanish), each the Snowball algorithm for that language, checked against that project's whole published vocabulary:

DEFINE ANALYZER french FILTERS lowercase, stemmer(french), ascii;
DEFINE ANALYZER russian FILTERS lowercase, stemmer(russian);
DEFINE COLLECTION pages;
DEFINE FIELD fr ON pages TYPE string ANALYZER french;
DEFINE FIELD ru ON pages TYPE string ANALYZER russian;
CREATE pages:1 = { fr: 'Les chevaux du café', ru: 'Важные новости' };

SELECT * FROM pages WHERE fr MATCHES 'cheval cafe' AND ru MATCHES 'важный';

One row. Each of them stems only lower-case words of its own alphabet and reads the accents, so a fold of accents goes after it: stemmer(french) stems chevaux with the French rules, and ascii then lets cafe meet café. Russian needs no fold. stemmer(english) is a second spelling of stemmer, and a language the store does not have is refused rather than read as English:

DEFINE ANALYZER dutch FILTERS lowercase, stemmer(dutch);

Refused where it is written, like any other filter the language does not have.

Chinese and Japanese need no filter (from 0.22.0-beta): each Han ideograph and Hiragana letter is a token of its own, so a word is a run of tokens and a quoted run is an exact substring:

DEFINE ANALYZER han FILTERS lowercase;
DEFINE FIELD zh ON pages TYPE string ANALYZER han;
CREATE pages:2 = { zh: '数据库很快' };
CREATE pages:3 = { zh: '据说很慢' };
SELECT id FROM pages WHERE zh MATCHES '"数据"';

One row — pages:2; pages:3 holds 据 but not the run. An n-gram filter is refused by name (NgramFilter), because what it is reached for is already here: a prefix, a piece of a word and a misspelling are MATCHES PREFIX, MATCHES INFIX and MATCHES FUZZY.

It is also not spelling correction. MATCHES asks for terms, and a misspelling is not a form of a word — backpu reduces to itself and reaches nothing.

Changing a chain means a new name

An analyzer's name is unique across the store, not per database — it describes a language rather than one tenant's data. So adding a filter to a name that is already declared does nothing at all:

DEFINE ANALYZER IF NOT EXISTS english FILTERS lowercase;

SELECT * FROM articles WHERE body MATCHES 'backup';

Still one row: the second declaration found the name and returned, and the chain in force is still the one carrying the stemmer.

That is the safe behaviour rather than an inconvenience. The postings already written were produced by the chain in force when they were written, so a redefinition that did take effect would leave an index describing text that tokenises differently today, and matching would quietly stop. A new chain is therefore a new name, and a field binds one at DEFINE FIELD.

A field with no analyzer holds no terms

SELECT * FROM notes WHERE title MATCHES 'ada';

No rows, even though the text plainly says Ada. title was never declared with an analyzer, so it was never broken into terms. This is worth knowing before you go looking for the bug.

It composes

A match is an ordinary expression in an ordinary condition:

SELECT * FROM notes WHERE body MATCHES 'lovelace' AND title = 'Ada';

The index changes the cost and not the answer

DEFINE INDEX by_body ON notes FIELDS body SEARCH;
SELECT * FROM notes WHERE body MATCHES 'lovelace';

The same one row the scan returned. The filters still apply, because they belong to the field and not to the index:

SELECT * FROM notes WHERE body MATCHES 'CAFE';

A search index reads one field. Naming two is refused rather than half done — before 0.20.0-beta the declaration was accepted and indexed the first field alone:

DEFINE INDEX by_both ON notes FIELDS body, title SEARCH;

Refused — IndexReadsOneField. Declare one index per field; a query over several of them is served by their union (see Either, and not), and a ranking over several fields is what one search over several tables is for.

What an index keeps beside its postings is declared

DEFINE INDEX by_text ON pages FIELDS fr SEARCH POSITIONS OFFSETS;
DEFINE INDEX by_ru ON pages FIELDS ru SEARCH NO SCORE;

None of them changes an answer — each is a cost paid at write time for a cheaper read. Each word comes after SEARCH, at most once, in any order.

Which tokenizer built an index

An index holds what the analyzer made of each record when the entry was written. When the code that makes terms changes — the tokenizer splits text differently, a filter folds or stems differently — every entry written before is a term the analyzer would no longer produce, and a read through it answers a subset of what the scan answers with nothing in an error state. That happened once, when 0.22.0-beta split runs of ideographs.

From 0.26.0-beta an index records the tokenizer generation that built it, and a read compares it with the build's own. An index that recorded another generation, or none — every search index written before 0.26.0-beta — is treated as one that may be stale:

• a field's SEARCH index is not answered from: MATCHES, a ranked walk, a highlight from stored offsets and a suggestion take the scan, which is exact, and USING INDEX naming it is refused. A search::score is still measured against its statistics;
• a search over several tables still reads such a member — no scan stands in for a search — and its answer can miss records;
• every read that met one carries the note needs-rebuild, naming the index and the statement that rebuilds it, and INFO FOR TABLE (for an index) and INFO FOR SEARCH (for each member) report tokenizer — the generation, or NULL when none was recorded — and rebuild, true until it is rebuilt.

A field's index is rebuilt in place:

REBUILD INDEX by_body ON notes;

After upgrading to 0.26.0-beta, rebuild every search index once — a field's with REBUILD INDEX, a search by dropping and defining it again in one transaction. Until then a field's search reads scan, and a search says it can miss records.

Writes take back the postings the record no longer earns

UPDATE notes:1 = { body: 'Grace Hopper wrote a compiler', title: 'Ada' };
SELECT * FROM notes WHERE body MATCHES 'lovelace';

No rows — and MATCHES 'hopper' now returns one. An index entry outliving the text that earned it is the failure this makes impossible.

Ranking

A score is not a property of a document. It measures one document against the collection, so it needs statistics an index maintains.

It is an ordinary expression, addressable in a projection:

SELECT search::score(body, 'hopper') AS relevance FROM notes;

…and in an ORDER BY, which is all a ranked read is:

SELECT * FROM notes ORDER BY search::score(body, 'hopper') DESC LIMIT 1;

A record holding none of the query's words scores zero, not nothing:

SELECT * FROM notes WHERE search::score(body, 'unheardof') > 0;

Weighting one field against another is multiplication

A score is an ordinary expression, so weighting a title above a body needs no syntax of its own — only arithmetic over two scores, each from a field carrying its own search index:

SELECT title, search::score(title, 'lock') * 3
            + search::score(body,  'lock') AS relevance
FROM notes ORDER BY relevance DESC;

There is no ^3 form because there is nothing for it to do that multiplication does not already do, with precedence and composition a reader already knows. Several fields ranked as one document — a word spread over a title and a body not counted twice — is a different question, and one search over several tables answers it.

A weight multiplies a score the record earned and can never manufacture one. A field the record does not match contributes exactly 0, and 0 × 3 is still 0. That is worth stating because the alternative is not a tie: the ranking divides by document length, so a record given any weight for a word it does not hold would arrive first, and the resulting order would look like a strong opinion rather than a mistake.

Where a score is refused

Rather than answered with a number that orders nothing:

SELECT search::score(title, 'ada') AS relevance FROM notes;

Refused — NoSearchIndex, naming the field. title has no search index, so there are no collection statistics to score against.

SELECT search::score(body) AS relevance FROM notes;

Refused — WrongArity, before anything runs.

A single record is scored against its table's collection, so it is not refused (from 0.22.0-beta; it was before):

SELECT search::score(body, 'hopper') AS relevance FROM notes:1;

The number is the one notes read whole gives that record — the same is true of a span, FROM notes:1..=9.

Beyond a whole word

MATCHES asks whether the text holds a whole word. That is the right question once a reader has finished typing one and has spelled it correctly, and each operator here relaxes exactly one of those two assumptions.

Each is also declared rather than automatic. A query that finds nothing is never quietly retried as a looser one, because a reader shown results for a question they did not ask cannot tell which question was answered.

Two more records, so there is something to tell apart:

CREATE notes:5 = { body: 'Ada Lovelace and Charles Babbage' };
CREATE notes:6 = { body: 'A compiler for the analytical engine' };

The word a reader has started typing

SELECT * FROM notes WHERE body MATCHES PREFIX 'lovel';

Two rows — notes:5, which holds Lovelace, and notes:3, which holds lovelacex. MATCHES 'lovelace' returns only the first, because a term is a whole word and lovelacex is a different one.

It asks for a word beginning with each word typed: still a conjunction across the query, now a disjunction inside each word.

A word ending in * asks the same thing inside an ordinary query (from 0.20.0-beta), so a search box can send what the reader typed — every finished word whole, the one being typed as a prefix:

SELECT * FROM notes WHERE body MATCHES 'ada lovel*';

One row, notes:5: it holds ada and a word beginning with lovel. The star is read only at the end of a word, and OR, NOT and a quoted phrase work around it as around any word. Before 0.20.0-beta the tokenizer dropped the asterisk, so a query string holding lovel* asked for the word lovel — a query written that way now answers more than it did.

Unlike MATCHES PREFIX, the starred word is scored. It weighs as one word over the words it begins: they share one rarity, that of the most-held among them, and a record's count is all its occurrences of any of them, so a rare misspelling under the prefix cannot outrank the common word being typed:

SELECT id, search::score(body, 'lovel*') AS relevance
FROM notes WHERE body MATCHES 'lovel*';

Two characters are refused rather than answered slowly:

SELECT * FROM notes WHERE body MATCHES PREFIX 'lo';

Refused — PrefixTooShort. Two characters reach a large fraction of an English vocabulary: an answer nobody can use, paid for in full, on the query a frustrated reader retries. The refusal is raised before an access path is chosen, so adding an index can never change whether the statement runs.

A piece of a word

SELECT * FROM notes WHERE body MATCHES INFIX 'pile';

Two rows — the two records holding compiler. MATCHES INFIX asks for a term containing each piece typed, wherever it sits in the word. The piece is folded by the field's analyzer and not stemmed, because a piece of a word stems into nothing; so over a stemming analyzer it is looked for inside stems, and a field meant for this kind of search is better analyzed without a stemmer. The floor is the prefix floor — under three characters is PrefixTooShort.

No n-gram enters the analysis. A SEARCH index keeps every suffix of every term it holds, three characters and longer, beside the term itself, so a piece is a range read over suffixes and the index grows with the vocabulary rather than with the text. An index built before 0.20.0-beta holds no suffixes, and the scan answers — the same records — until REBUILD INDEX.

The word they meant rather than the one they typed

babbag is not a word this collection holds, and MATCHES says so:

SELECT * FROM notes WHERE body MATCHES 'babbag';

No rows. MATCHES FUZZY asks for a term within a few edits instead — none for a word under three letters, one up to five, two beyond (from 0.22.0-beta):

SELECT * FROM notes WHERE body MATCHES FUZZY 'babbag';

One row. An edit is an insertion, a deletion or a substitution — or, from 0.20.0-beta, two adjacent letters swapped, which is the commonest typing mistake there is and now costs one edit rather than two:

SELECT * FROM notes WHERE body MATCHES FUZZY 'babbgae';

One row, babbage with its a and g the wrong way round.

The first two characters are not fuzzy (three until 0.22.0-beta), and that is the limit worth knowing before relying on it:

SELECT * FROM notes WHERE body MATCHES FUZZY 'xabbage';

No rows, though xabbage is a single edit from babbage just as babbag is. The mistake is inside the part the operator does not vary. That is the price of not walking the whole term dictionary for every word of every query — and a first letter is the character people mistype least, having usually just read it.

A misspelling is measured against the word the text held, not only against its stem (from 0.22.0-beta). A SEARCH index over a stemming analyzer keeps each word as written beside the stem it became, so trasnactoin finds transaction where, measured against transact, it found nothing. In a ranked FROM SEARCH a corrected word weighs less than the word itself — one over one plus its edits — so the exact word ranks first.

The same weighing ranks a field read (from 0.26.0-beta). A search::score over a field the statement asks MATCHES FUZZY of measures each word as that read reached it: the terms within the edit budget share one rarity, that of the most-held among them, and each occurrence counts one over one plus its edits:

SELECT id, search::score(body, 'babbag') AS relevance FROM notes
 WHERE body MATCHES FUZZY 'babbag' ORDER BY relevance DESC;

5: { relevance: 0.9838218046657289 }
(1 record(s), via index)

Before, it scored the spelling as typed, which a misspelling's record does not hold, so every record it found scored 0 and a ranked fuzzy read came back in store order.

Either, and not

An unquoted query is a conjunction: every word must be held. OR unions the word beside it, and NOT excludes the word after it.

SELECT * FROM notes WHERE body MATCHES 'hopper OR babbage';

Two rows, one for each name.

SELECT * FROM notes WHERE body MATCHES 'compiler NOT hopper';

One row — notes:6, which holds compiler and not hopper. notes:1 holds both and is excluded.

An OR across two fields is served by both indexes. A condition offering no conjunct one index could serve alone used to read the whole table; when every side of an OR has an index worth reading, the read is the union of their records, each tested again against the whole condition:

DEFINE FIELD summary ON notes TYPE string ANALYZER simple;
DEFINE INDEX by_summary ON notes FIELDS summary SEARCH;
UPDATE notes:6 MERGE { summary: 'Babbage designed it' };

EXPLAIN SELECT * FROM notes WHERE body MATCHES 'hopper' OR summary MATCHES 'babbage';

{ access: 'index', exact: true, index: 'by_body, by_summary', shape: 'union', table: 'notes' }

One side with no index leaves the read a scan, because a union missing a side is not a superset of the answer.

The operators are uppercase, and that is load-bearing rather than a style choice. They are recognised on the query as written, before analysis, because the analyzer keeps only alphanumerics and stems what is left — by the time terms exist an operator would be a word like any other. Requiring capitals is what keeps salt or pepper meaning three words, so a query written before these operators existed still asks what it asked.

Excluding without requiring is refused:

SELECT * FROM notes WHERE body MATCHES 'NOT babbage';

Refused — NegationWithoutTerm. A search index enumerates the records that hold a word, so NOT babbage names the complement of a posting list — every record in the table, which the index cannot produce. The two honest answers are reading the whole table or refusing, and this store refuses. Add a word to match and the exclusion applies to it.

"Did you mean" — a suggestion, never a substitution

A read answers with a suggestion beside its records when a term the query named is one the collection does not hold:

SELECT * FROM notes WHERE body MATCHES 'babbage OR hoppr';

5: { body: 'Ada Lovelace and Charles Babbage' }
(1 record(s), via index)
did you mean: hoppr -> hopper

The suggestion never enters the executed query. This read answered with the records holding babbage, unioned with those holding hoppr — none — and it would answer with exactly those whether or not a correction had been found. A store that quietly re-ran the query with the corrected word would answer a question nobody asked, and the answer would look right.

The trigger is a term the collection does not hold, not an empty answer. A query with one word misspelled usually still returns rows, as this one does, so a suggestion that waited for emptiness would stay silent in the common case and speak only in the rare one.

An excluded term is left alone. NOT hoppr asks for the records without that word and gets exactly them, and correcting an exclusion is the one direction of error that removes records the reader wanted.

A suggestion needs a term dictionary, and only a SEARCH index has one. Over an unindexed field there is no suggestion at all — which is not the same as "nothing is near", a confident negative nobody checked.

Where in the text it matched

SELECT search::highlight(body) AS marks FROM notes WHERE body MATCHES 'lovelace';

5: { marks: [{ end: 12, start: 4 }] }
(1 record(s), via index)

An array of { start, end } byte ranges into the field's text: one per token this read's own query reached, ordered by position.

It takes the field alone, and that is the point. The query is not repeated in the projection — it is whatever this statement asked of that field. A second copy could disagree with the WHERE in its spelling or, invisibly, in the operator it implies, since MATCHES and MATCHES FUZZY reach different terms from the same word. A highlight that disagrees with its own filter is worse than none: it says a record matched somewhere it did not.

The marks cover the text that matched, not the characters that were typed. Over un Café ici a search for cafe marks Café; over a vector store a fuzzy search for vectr marks vector. Neither typed string occurs in the text it marks. The offsets come from re-analysing the field with the analyzer that field declares — the same analyzer that decided it matched — so the marked token is by construction the token the operator reached. An index declared with OFFSETS stores those ranges, and a whole-word query is then marked from the index rather than by analysing the text again — the same marks either way.

The best few, without scoring the rest

A ranked read with a LIMIT does not score every record in the table:

EXPLAIN SELECT title, search::score(body, 'compiler') AS relevance
FROM notes ORDER BY search::score(body, 'compiler') DESC LIMIT 2;

{ access: 'ordered', exact: true, index: 'by_body', shape: 'scored', table: 'notes' }

The read walks the postings of the query's own terms, and stops walking a term once the most that term could still contribute falls below the score already sitting in last place. access: 'ordered' with shape: 'scored' is what that looks like from outside.

exact: true is the part worth reading: the bound changes the cost and not the answer, which is the same promise the index itself makes. The rows are the ones scoring the whole table would have put first.

Take the LIMIT away and there is no bound to stop at, so every record is scored:

EXPLAIN SELECT * FROM notes ORDER BY search::score(body, 'compiler') DESC;

{ access: 'scan', exact: true, table: 'notes' }

Why a record ranked where it did

SELECT id, search::explain(body, 'compiler hopper') AS why
FROM notes WHERE body MATCHES 'compiler' LIMIT 2;

search::explain answers the score search::score would, with what it was made of: the collection's documents and average_length, the record's length, and one entry under terms per word asked — how often the record held it, how many documents hold it, its weight (rarity) and its contribution. A starred word is one entry under prefixes, naming the words of this record it blended. A word the record does not hold is listed with held: 0 and contributes nothing, which is the answer to "why did this not rank": notes:6 holds compiler and not hopper.

The contributions add up to the score exactly, so an explanation cannot describe a different score from the one the read ordered by. It needs what a score needs — a search index on the field — and is refused without one in the same words.