A man waiting outside Florsheim Shoes in New York City photographed by a 19-year-old Stanley Kubrick in 1947

I’ve wanted long-time to learn some basic concepts about full-text searching and maybe do so by building something however trivial. I don’t know why, but learning about how to search through a large amount of documents, books and so on seems cool to me. I hope I have the time to stick to the process.

Table of Contents

  1. Textual Searching
  2. Full-text Searching
  3. Preprocessing
  4. Postgresql data types for fulltext search
  5. Basic Text Matching
  6. Searching for phrases

Textual Searching

Textual search operators have existed in databases for years. E.g. LIKE operator in PostgreSQL was all that I’ve ever used for searching through string columns. But such operators are quite primitive to be used for modern information retrieval:

Full-text Searching

Full-text Searching (FTS) is the ability to find text documents that satisfy a query (e.g. a simple set of words) The result of the search is a list of documents that contain given query terms. The documents on the list can also be ordered (ranked) based on their similarity to query i.e. frequency of query terms in the document.

Preprocessing

In order to work with text data, first, it is important to transform the raw text into a form that can be understood and used by search algorithms. This is called preprocessing of text and in postgresql includes these steps:

Parsing documents into tokens.

Raw text is split into smaller, meaningful parts, called tokens. To make their processing easier, they are categorized by their type such as: numbers, words, complex words, email addresses etc. PostgreSQL uses a parser to perform this step.

Converting tokens into lexemes.

A lexeme is a token that has been normalized i.e. brought into its base form. Prefixes, suffixes are removed from it, upper-cases are lowered etc. Also, during this process stop words are eliminated.

Stop words are words that are commonly filtered out by search engines. Their function in text is grammatical rather than semantic: e.g. “a”, “the”, “is”, “are”, etc., so this makes them useless during searching. In short, then, tokens are raw fragments of the document text, while lexemes are words that are believed useful for indexing and searching.
PostgreSQL uses dictionaries to perform this step. They help to:

Storing preprocessed documents optimized for searching.

For example, each document can be represented as a sorted array of normalized lexemes. Along with the lexemes it is often desirable to store positional information to use for proximity ranking.

But what exactly is a document ?

A document is the unit of searching in a full text search system. The text search engine parses a document and stores its association of lexemes alongside. These associations are used to search for documents that contain query words.
For searches within PostgreSQL, a document is normally a textual field within a row of a database table. It might be also a combination (concatenation) of such fields, perhaps stored in several tables or obtained dynamically.

Two data types: tsvector and tsquery

tsvector and to_tsvector

We wrote above that a document is first preprocessed. Now, this preprocessed document should be stored somewhere. There is a particular datatype for this purpose in postgresql, tsvector. Searching and ranking are performed entirely on the tsvector representation of a document. We therefore often speak of the tsvector as being the document, but of course it is only a compact representation of the full document. 


SELECT 'a fat cat sat on a mat and ate a fat rat'::tsvector;
tsvector
----------------------------------------------------
'a' 'and' 'ate' 'cat' 'fat' 'mat' 'on' 'rat' 'sat'


*If you get confused about the double colon :: symbol in PostgreSQL: Is a synonym for CAST, which converts a value into a different data type.
E.g.: SELECT ‘2023-05-03’::date; (Converts the text ‘2022-05-03’ to a date datatype).

N.B.: tsvector itself does not perform any word normalization; it assumes the words it is given are already normalized. As you can see the following result, it can be considered non-normalized, but tsvector doesn’t care. This leads to unexpected results when searching, so be sure to normalize the input via to_tsvector.


SELECT 'The Fat Rats'::tsvector;
tsvector
--------------------
'Fat' 'Rats' 'The'

Raw document text should usually be passed through to_tsvector to normalize the words appropriately for searching. Adjacent to each lexeme, ts_vector also adds its position (location) in the document. Positional information can be used for proximity ranking. Position values can range from 1 to 16383; larger numbers are silently set to 16383.


SELECT to_tsvector('english', 'The Fat Rats');
to_tsvector
-----------------
'fat':2 'rat':3

tsquery and to_tsquery

Same is true for the query. There is a special datatype, tsquery, which stores terms (lexemes) that are to be searched for. Search terms can be combined using the Boolean operators &, |, ! (AND, OR, NOT). Another important operator is the Phrase search operator: <-> (FOLLOWED BY). Parentheses can be used to enforce grouping of these operators.

As with the to_tsvector, we need to use to_tsquery function to perform query normalization: 

SELECT to_tsquery('Fat:ab & Cats');
to_tsquery
------------------
'fat':AB & 'cat'

Basic Text Matching

Full text searching in PostgreSQL is based on the match operator @@ Match operator @@ needs two arguments, one of type tsvector and the other of type tsquery.

tsvector @@ tsquery → boolean
-- Does tsvector match tsquery?

Searching for phrases

Searching for phrases is possible with the help of the <-> (FOLLOWED BY) tsquery operator, which matches only if its arguments have matches that are adjacent and in the given order. For example:


SELECT to_tsvector('fatal error') @@ to_tsquery('fatal <-> error');
?column?
----------
true

SELECT to_tsvector('error is not fatal') @@ to_tsquery('fatal <-> error');
?column?
----------
false

Sources:

[1] Postgresql Documentation - Fulltext Search