Posts Tagged ‘expression index’

Full-text search with PostgreSQL

I spent some time experimenting with PostgresSQL’s full-text search functionality, which has been available to some degree since v8.3. If Postgres is already being used as a data store, this functionality is attractive as it provides a simple way to implement non-trivial search without the need to build out additional infrastructure and code (e.g. an Elasticsearch cluster + application code to load data into Elasticsearch and keep it up-to-date).

I experimented with basic querying and ranking using the Lexiio database, the definitions table in particular provides a good dataset to work with, containing 604,076 term definitions.

Querying

Below is a sample query where we search for the phrase “to break into small pieces”, rank each item in the result set, and order the results based on their rank.

SELECT id, definition
FROM definitions
WHERE to_tsvector('english', definition) @@ plainto_tsquery('english', 'to break into small pieces')

Understanding this query is mostly about understanding some vendor-specific SQL.

  • The tsvector type represents is a sorted list of lexemes. to_tsvector(…) is a function to convert raw text to a tsvector.
  • The tsquery type represents lexemes to be searched for and the operators combining them. to_tsquery(…) is a function to convert raw text to a tsquery.
  • @@ is the match operator, this is a binary operator which take a tsvector and a tsquery

PostgreSQL full-text search query

To get a better understanding of of these types, it can be helpful to run the conversion functions with a few phrases.

SELECT to_tsvector('english', 'to break into small pieces');

"'break':2 'piec':5 'small':4"
SELECT plainto_tsquery('english', 'to break into small pieces');

"'break' & 'small' & 'piec'"

Ranking

The ranking of a full-text search match can be computed with either ts_rank(…), which provides a standard ranking, or ts_rank_cd(…), which gives a coverage density ranking (where ranking is also based on term proximity and cooccurrence, as described in “Relevance ranking for one to three term queries”).

SELECT
id,
definition,
ts_rank(
to_tsvector('english', definition),
plainto_tsquery('english', 'to break into small pieces')
)
AS rank
FROM definitions
WHERE to_tsvector('english', definition) @@ plainto_tsquery('english', 'to break into small pieces')
ORDER BY rank DESC

Higher rank values correspond to more relevant search results.

Here’s the result set, with rankings, for the query above:

+--------+-----------------------------------------------------------------------------------------------------------------------------------------------------------------+----------+ | id | definition | rank | +--------+-----------------------------------------------------------------------------------------------------------------------------------------------------------------+----------+ | 568352 | # {{transitive}} To [[break]] small pieces from. | 0.26833 | +--------+-----------------------------------------------------------------------------------------------------------------------------------------------------------------+----------+ | 135231 | # Resistant to chipping (breaking into small pieces). | 0.266913 | +--------+-----------------------------------------------------------------------------------------------------------------------------------------------------------------+----------+ | 572891 | # {{transitive}} To break into small pieces or fragments. | 0.266913 | +--------+-----------------------------------------------------------------------------------------------------------------------------------------------------------------+----------+ | 568348 | # {{transitive}} To [[break]] into small pieces. | 0.266913 | +--------+-----------------------------------------------------------------------------------------------------------------------------------------------------------------+----------+ | 176962 | # To break into crumbs or small pieces with the fingers; to [[crumble]]. | 0.25948 | +--------+-----------------------------------------------------------------------------------------------------------------------------------------------------------------+----------+ | 50744 | # A small piece of [[detailing]] added to break up the [[surface]] of an [[object]] and add [[visual]] interest, particularly in [[movie]] [[special effect]]s. | 0.25134 | +--------+-----------------------------------------------------------------------------------------------------------------------------------------------------------------+----------+ | 568350 | # {{transitive}} To [[break]] open or [[crush]] to small pieces by impact or stress. | 0.25134 | +--------+-----------------------------------------------------------------------------------------------------------------------------------------------------------------+----------+ | 572890 | # {{transitive}} To break into [[fragment]]s or small pieces. | 0.25134 | +--------+-----------------------------------------------------------------------------------------------------------------------------------------------------------------+----------+ | 547405 | # {{surgery}} The [[operation]] of breaking a [[stone]] in the [[bladder]] into small pieces capable of being [[void]]ed. | 0.221355 | +--------+-----------------------------------------------------------------------------------------------------------------------------------------------------------------+----------+

Indexing

Without an index the above query takes ~5.3 seconds on my local machine (i7-4790K @ 3.7GHz, Intel 730 Series SSD, DDR3 1600 RAM w/ more than enough available to PG).

A Generalized Inverted Index (GIN) is recommended for full-text search. A GIN index can be created directly on a tsvector column or, in this case where there’s an existing text column, an expression index can be created using the to_tsvector() function.

CREATE INDEX ix_def
ON definitions
USING GIN(to_tsvector('english', definition));

With this index, performance improves drastically, with query times ~13 milliseconds.

Is it worth trying?

Maybe. If you’re not using Postgres as the data store for what needs to be searched over (i.e. you’d have to continually ETL data into Postgres), you already have a sophisticated search solution in place, or you’re operating at a scale where you need a clustered solution, probably not. However, if you’re using Postgres, and looking to implement search in an application or move beyond simple substring search, what Postgres is offering is fairly powerful and worth trying out.