Simon Willison's Weblog: full-text-search

Hybrid full-text search and vector search with SQLite

2024-10-04T16:22:09+00:00

Hybrid full-text search and vector search with SQLite

As part of Alex’s work on his sqlite-vec SQLite extension - adding fast vector lookups to SQLite - he’s been investigating hybrid search, where search results from both vector similarity and traditional full-text search are combined together.

The most promising approach looks to be Reciprocal Rank Fusion, which combines the top ranked items from both approaches. Here’s Alex’s SQL query:

-- the sqlite-vec KNN vector search results
with vec_matches as (
  select
    article_id,
    row_number() over (order by distance) as rank_number,
    distance
  from vec_articles
  where
    headline_embedding match lembed(:query)
    and k = :k
),
-- the FTS5 search results
fts_matches as (
  select
    rowid,
    row_number() over (order by rank) as rank_number,
    rank as score
  from fts_articles
  where headline match :query
  limit :k
),
-- combine FTS5 + vector search results with RRF
final as (
  select
    articles.id,
    articles.headline,
    vec_matches.rank_number as vec_rank,
    fts_matches.rank_number as fts_rank,
    -- RRF algorithm
    (
      coalesce(1.0 / (:rrf_k + fts_matches.rank_number), 0.0) * :weight_fts +
      coalesce(1.0 / (:rrf_k + vec_matches.rank_number), 0.0) * :weight_vec
    ) as combined_rank,
    vec_matches.distance as vec_distance,
    fts_matches.score as fts_score
  from fts_matches
  full outer join vec_matches on vec_matches.article_id = fts_matches.rowid
  join articles on articles.rowid = coalesce(fts_matches.rowid, vec_matches.article_id)
  order by combined_rank desc
)
select * from final;

I’ve been puzzled in the past over how to best do that because the distance scores from vector similarity and the relevance scores from FTS are meaningless in comparison to each other. RRF doesn’t even attempt to compare them - it uses them purely for row_number() ranking within each set and combines the results based on that.

Tags: full-text-search, search, sql, sqlite, alex-garcia, vector-search, embeddings, rag

tantivy-cli

2024-06-13T06:03:00+00:00

tantivy-cli

I tried out this Rust based search engine today and I was very impressed.

Tantivy is the core project - it's an open source (MIT) Rust library that implements Lucene-style full text search, with a very full set of features: BM25 ranking, faceted search, range queries, incremental indexing etc.

tantivy-cli offers a CLI wrapper around the Rust library. It's not actually as full-featured as I hoped: it's intended as more of a demo than a full exposure of the library's features. The JSON API server it runs can only be used to run simple keyword or phrase searches for example, no faceting or filtering.

Tantivy's performance is fantastic. I was able to index the entire contents of my link blog in a fraction of a second.

I found this post from 2017 where Tantivy creator Paul Masurel described the initial architecture of his new search side-project that he created to help him learn Rust. Paul went on to found Quickwit, an impressive looking analytics platform that uses Tantivy as one of its core components.

The Python bindings for Tantivy look well maintained, wrapping the Rust library using maturin. Those are probably the best way for a developer like myself to really start exploring what it can do.

Also notable: the Hacker News thread has dozens of posts from happy Tantivy users reporting successful use on their projects.

Via Hacker News

Tags: cli, full-text-search, search, rust

Weeknotes: datasette-dump, sqlite-backup, talks

2020-09-11T04:47:54+00:00

I spent some time this week digging into Python's sqlite3 internals. I also gave two talks and recorded a third, due to air at PyGotham in October.

sqlite-dump and datasette-backup

I'm running an increasing number of Datasette instances with mutable database files - databases that are updated through a variety of different mechanisms. So I need to start thinking about backups.

Prior to this most of my database files had been relatively disposable: they're built from other sources of data (often by scheduled GitHub Actions) so backups weren't necessary since I could always rebuild them from their point of truth.

Creating a straight copy of a SQLite database file isn't enough for robust backups, because the file may be accepting writes while you are creating the copy.

SQLite has various mechanisms for backups. There's an online backup API and more recent SQLite versions support a VACUUM INTO command which also optimizes the backed up database.

I figured it would be useful to expose this functionality by a Datasette plugin - one that could allow automated backups to be directly fetched from Datasette over HTTPS. So I started work on datasette-backup.

For the first backup mode, I decided to take advantage of the connection.iterdump() method that's built into Python's sqlite3 module. This method is an iterator that outputs plain text SQL that can recreate a database. Crucially it's a streaming-compatible mechanism - unlike VACUUM INTO which would require me to create a temporary file the same as the database I was backing up.

I started experimenting with it, and ran into a big problem. I make extensive use of SQLite full-text search, but the .sql dumps generated by .iterdump() break with constraint errors if they include any FTS tables.

After a bit of digging I came across a 13 year old comment about this in the cPython source code itself!

The implementation for .iterdump() turns out to be entirely in Python, and way less complicated than I had expected. So I decided to see if I could get FTS table exports working.

In a classic case of yak shaving, I decided to create a Python library called sqlite-dump to solve this problem. And since my existing cookiecutter templates only cover Datasette Plugins or Click apps I first needed to create a new python-lib template in order to create the library I needed for my plugin.

I got it working! Install the datasette-backup plugin on any Datasette instance to get a /-/backup/name-of-database.sql URL that will produce a streaming SQL dump of any attached database.

A weird bug with SQLite FTS and triggers

While working on datasette-backup I noticed a weird issue with some of my SQLite full-text search enabled databases: they kept getting bigger. Way bigger than I would expect them to.

I eventually noticed that the licenses_fts table in my github-to-sqlite demo database had 7 rows in it, but the accompanying licenses_fts_docsize table had 9,141. I would expect it to only have 7 as well.

I was stumped as to what was going on, so I turned to the official SQLite forum. I only recently discovered how useful this is as a resource. Dan Kennedy, one of the three core SQLite maintainers, replied within an hour and gave me some useful hints. The root cause turned out to be the way SQLite triggers work: by default, SQLite runs in recursive_triggers=off mode (for backwards compatibility with older databases). This means that an INSERT OR REPLACE update to a table that is backed by full-text search may not correctly trigger the updates needed on the FTS table itself.

Since there doesn't appear to be any disadvantage to running with recursive_triggers=on I've now set that as the default for sqlite-utils, as-of version 2.17.

I then added a sqlite-utils rebuild-fts data.db command in version 2.18 which can rebuild the FTS tables in a database and fix the _fts_docsize problem.

Talks

I presented Build your own data warehouse for personal analytics with SQLite and Datasette at PyCon AU last week. The video is here and includes my first public demo of Dogsheep Beta, my new combined search engine for personal analytics data imported using my Dogsheep family of tools. I took questions in this Google Doc, and filled out more detailed answers after the talk.

I gave a talk at PyRVA a couple of days called Rapid data analysis with SQLite and Datasette. Here's the video and Google Doc for that one.

I also pre-recorded my talk for PyGotham: Datasette - an ecosystem of tools for working with Small Data. The conference is in the first week of October and I'll be hanging out there during the talk answering questions and chatting about the project, safe from the stress of also having to present it live!

TIL this week

Releases this week

datasette-dns 0.1a1 - 2020-09-10
datasette-dns 0.1a0 - 2020-09-10
dogsheep-beta 0.7a0 - 2020-09-09
sqlite-utils 2.18 - 2020-09-08
sqlite-utils 2.17 - 2020-09-07
datasette-backup 0.1 - 2020-09-07
sqlite-dump 0.1.1 - 2020-09-07
sqlite-dump 0.1 - 2020-09-07
sqlite-dump 0.1a - 2020-09-06
datasette-backup 0.1a - 2020-09-06
datasette-block-robots 0.3 - 2020-09-06
datasette-block-robots 0.2 - 2020-09-05
dogsheep-beta 0.6 - 2020-09-05
dogsheep-beta 0.5 - 2020-09-04

Tags: full-text-search, speaking, sqlite, datasette, weeknotes, sqlite-utils

sqlite-utils 2.14

2020-08-01T21:19:04+00:00

sqlite-utils 2.14

I finally figured out porter stemming with SQLite full-text search today—it turns out it’s as easy as adding tokenize=’porter’ to the CREATE VIRTUAL TABLE statement. So I just shipped sqlite-utils 2.14 with a tokenize= option (plus the ability to insert binary file data from stdin).

Via @simonw

Tags: full-text-search, projects, search, sqlite, sqlite-utils

datasette-search-all: a new plugin for searching multiple Datasette tables at once

2020-03-09T00:59:37+00:00

I just released a new plugin for Datasette, and it's pretty fun. datasette-search-all is a plugin written mostly in JavaScript that executes the same search query against every searchable table in every database connected to your Datasette instance.

You can try it out on my FARA (Foreign Agents Registration Act) search site, fara.datasettes.com - see Deploying a data API using GitHub Actions and Cloud Run for background on that project.

Here's a search for manafort across all four FARA tables (derived from CSVs originally pulled from the Justice Department bulk data site).

I've been planning to build cross-table search for Datasette for quite a while now. It's a potentially very difficult problem: searching a single table is easy, but the moment you attempt to search multiple tables you run into a number of challenges:

Different tables have different columns. How do you present those in a single search interface?
Full-text search relevance scores make sense within a single table (due to the statistics they rely on, see Exploring search relevance algorithms with SQLite) but cannot be compared across multiple tables.

I have an idea for how I can address these, but it involves creating a single separate full-text index table that incorporates text from many different tables, along with a complex set of indexing mechanisms (maybe driven by triggers) for keeping it up to date.

But maybe I was overthinking this?

While I stewed on the ideal way to solve this problem, projects like my FARA site were stuck without cross-table search. Then this morning I realized that there was another way: I could build pretty much the simplest thing that could possibly work (always a good plan in my experience).

Here's how the new plugin works: it scans through every table attached to Datasette looking for tables that are configured for full-text search. Then it presents a UI which can excute searches against ALL of those tables, and present the top five results from each one.

The scanning-for-searchable-tables happens in Python, but the actual searching is all in client-side JavaScript. The searches run in parallel, which means the user sees results from the fastest (smallest) tables first, then the larger, slower tables drop in at the bottom.

It's stupidly simple, but I really like the result. It's also a neat demonstration of running parallel SQL queries from JavaScript, a technique which I'm keen to apply to all sorts of other interesting problems.

JavaScript style

The JavaScript I wrote for this project is unconventional for 2020: it's a block of inline script on the page, using no libraries or frameworks, but taking advantage of modern niceties like backtick template literals and fetch().

The code is messy, short and extremely easy to change in the future. It doesn't require running a build tool. I'm pretty happy with it.

Adding a search form to the homepage

The other thing the plugin does is add a search box to the Datasette homepage (as seen on the FARA site) - but only if the attached databases contain at least one FTS-configured searchable table.

There are two parts to the implementation here. The first is a extra_template_vars() plugin hook which injects a searchable_tables variable into the hompage context - code here.

The second is a custom index.html template which ships with the plugin. When Datasette renders a template it looks first in the local --template-dirs folder (if that option was used), secondly in all of the installed plugins and finally in the Datasette set of default templates.

The new index.html template starts with {% extends "default:index.html" %}, which means it extends the default template that shipped with Datasette. It then redefines the description_source_license block from that template to conditionally show the search form.

I'm not at all happy with abusing description_source_license in this way - it just happens to be a block located at the top of that page. As I write more plugins that customize the Datasette UI in some way I continually run into this problem: plugins need to add markup to pages in specific points, but they also need to do so in a way that won't over-ride what other plugins are up to.

I'm beginning to formulate an idea for how Datasette can better support this, but until that's ready I'll be stuck with hacks like the one used here.

Using this with datasette-configure-fts and datasette-upload-csvs

The datasette-configure-fts plugin provides a simple UI for configuring search for different tables, by selecting which columns should be searchable.

Combining this with datasette-search-all is really powerful. It means you can dump a bunch of CSVs into Datasette (maybe using datasette-upload-csvs), select some columns and then run searches across all of those different data sources in one place.

Not bad for 93 lines of JavaScript and a bit of Python glue!

Tags: full-text-search, javascript, plugins, projects, search, datasette

sqlite-utils 1.11

2019-09-03T01:05:41+00:00

sqlite-utils 1.11

Amjith Ramanujam contributed an excellent new feature to sqlite-utils, which I’ve now released as part of version 1.11. Previously you could enable SQLite full-text-search on a table using the .enable_fts() method (or the “sqlite-utils enable-fts” CLI command) but it wouldn’t reflect future changes to the table—you had to use populate_fts() any time you inserted new records. Thanks to Amjith you can now pass create_triggers=True (or --create-triggers) to cause sqlite-utils to automatically add triggers that keeps the FTS index up-to-date any time a row is inserted, updated or deleted from the table.

Tags: cli, full-text-search, projects, sqlite, sqlite-utils

Exploring search relevance algorithms with SQLite

2019-01-07T03:29:29+00:00

SQLite isn’t just a fast, high quality embedded database: it also incorporates a powerful full-text search engine in the form of the FTS4 and FTS5 extensions. You’ve probably used these a bunch of times already: many iOS, Android and desktop applications use SQLite under-the-hood and use it to implement their built-in search.

I’ve been using these capabilities for basic search in Datasette for over a year now, but I’ve recently started digging into some of their more advanced features. It turns out hacking around with SQLite is a great way to learn more about how fundamental information retrieval algorithms work under the hood.

Today I’m releasing sqlite-fts4 - a Python package that provides a collection of custom SQL functions for working with SQLite’s FTS4 module. It includes some neat tools for introspecting how relevancy ranking algorithms actually work.

Why not just use FTS5?

If it’s available to you FTS5 is usually the best option: it has a good ranking algorithm built in. I described how to use it to build fast autocomplete search for your website for the 2018 24 ways advent calendar. You can join directly against a virtual table and order by a pre-calculated relevance score accessible through that table.

What makes FTS4 interesting is that it doesn’t include a scoring mechanism: it instead exposes raw statistical data to you in a way that lets you build your own ranking functions.

You probably don’t need to do this - unless you are stuck on an older SQLite version that doesn’t support the latest features. But… if you’re interested in understanding more about how search actually works, the need to implement a ranking function is an excellent learning learning opportunity.

I’ll be demonstrating these functions using a hosted Datasette instance running at datasette-sqlite-fts4.datasette.io (with the data from my 24 ways article). You can play with them out there, or if you want to use your own Datasette instance you can enable these custom SQL functions by pip installing my new datasette-sqlite-fts4 plugin.

Raw FTS4 matchinfo() data

When using FTS4, the only scoring help SQLite gives you is the bulit-in matchinfo() function. For each document in your search result set, this function will expose raw statistical data that can be used to calculate a score.

Let’s try it out using the following query:

select
    *, matchinfo(articles_fts, "pcx")
from
    articles_fts
where
    articles_fts match :search

Run matchinfo() in Datasette

The pcx here is called the format string - it lets SQLite know what information about the match you would like to see.

The results are returned as a binary string! For the first matching document, we get back the following:

\x02\x00\x00\x00\x03\x00\x00\x00\x00\x00\x00\x00\x02\x00\x00\x00\x02\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x01\x00\x00\x00\xa3\x00\x00\x00\x1f\x00\x00\x00\x00\x00\x00\x00\x02\x00\x00\x00\x02\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x02\x00\x00\x00\\\x00\x00\x00\x15\x00\x00\x00

SQLite’s C heritage is showing through here.

decode_matchinfo() to decode the binary

The first step in working with matchinfo is to decode that binary string. It’s actually a sequence of unsigned 32 bit integers. We can turn it into a Python list of integers using the following:

struct.unpack("I" * (len(matchinfo) // 4), matchinfo)

sqlite-fts4 exposes a SQL function called decode_matchinfo() which does exactly this. Let’s expand our example to use it:

select
    title, author,
    decode_matchinfo(matchinfo(articles_fts, "pcx")),
    matchinfo(articles_fts, "pcx")
from
    articles_fts
where
    articles_fts match :search

Run decode_matchinfo() in Datasette

The matchinfo for our first matching document now looks like this:

[2, 3, 0, 2, 2, 0, 0, 0, 1, 163, 31, 0, 2, 2, 0, 0, 0, 2, 92, 21]

Better, but still obscure. What does it mean?

The anwser lies in the SQLite matchinfo documentation. In our format string, we requested p, c and x:

p requests a single integer representing the number of search terms we are matching. Since our search query is jquery maps this is 2.
c requests the number of searchable columns in our table. We created articles_fts with 3 columns, so it’s 3. That’s the second integer in the list.
x is much more interesting: it returns 3 integer values for each term/column combination. Since we have 2 terms and 3 columns that means we get back 6 * 3 = 18 integers. If you count the items in the array above you’ll see there are 18 left after you remove the first two. Each triple represents the number of times the term appears in the current column, the number of times it appears in this column across every row and the number of total documents that match the term in this column at least once.

Search relevancy scores are usually calculated against exactly this kind of collection of statistics: we rank based on how rare the matching terms are across the rest of the corpus.

annotate_matchinfo() to annotate the integers

Having a list of integers made things easier, but still not easy enough. That’s where annotate_matchinfo() comes in. This custom SQL function expands the matchinfo list of integers into a giant JSON object describing exactly what each of the results means.

We’ll try it out like this:

select
    title, author,
    decode_matchinfo(matchinfo(articles_fts, "pcx")),
    json_object("pre", annotate_matchinfo(matchinfo(articles_fts, "pcx"), "pcx"))
from
    articles_fts
where
    articles_fts match :search

Run annotate_matchinfo() in Datasette

Note that we have to provide the format string twice, so that annotate_matchinfo() knows the requested order of the binary matchinfo data.

This returns a JSON object that looks like this:

{
  "p": {
    "title": "Number of matchable phrases in the query",
    "value": 2,
    "idx": 0
  },
  "c": {
    "title": "Number of user defined columns in the FTS table",
    "value": 3,
    "idx": 1
  },
  "x": {
    "title": "Details for each phrase/column combination"
    "value": [
      ...
      {
        "phrase_index": 0,
        "column_index": 2,
        "hits_this_column_this_row": 1,
        "hits_this_column_all_rows": 163,
        "docs_with_hits": 31,
        "idxs": [8, 9, 10]
      },
      {
        "phrase_index": 1,
        "column_index": 0,
        "hits_this_column_this_row": 0,
        "hits_this_column_all_rows": 2,
        "docs_with_hits": 2,
        "idxs": [11, 12, 13]
      }...
    ],
  }
}

Try it out with pcxnalyb to see the complete set of format string options.

You may be wondering why I wrapped that function call in json_object("pre", ...). This is a Datasette trick: I recently added the ability to pretty-print JSON to my datasette-html-json plugin - see that package’s README for details.

Building ranking functions

These statistics are everything we need to calculate relevance scores. sqlite-fts4 implements two such functions: rank_score() is a simple TF/IDF function. rank_bm25() is much more interesting - it’s an implementation of the Okapi BM25, inspired by the one that ships with the peewee ORM.

Let’s try them both out:

select
    title, author,
    rank_score(matchinfo(articles_fts, "pcx")) as score,
    rank_bm25(matchinfo(articles_fts, "pcnalx")) as bm25,
    json_object("pre", annotate_matchinfo(matchinfo(articles_fts, "pcxnalyb"), "pcxnalyb"))
from
    articles_fts
where
    articles_fts match :search
order by bm25

Try rank_score() and rank_bm25() in Datasette

You can switch the order by clause between bm25 and score to compare the two.

bm25() is definitely a better option. It’s the default algorithm used these days by Elasticsearch, and they wrote up an excellent explanation of how it works on their blog.

Take a look at the source code for the ranking functions to see how they are implemented. They work against the data structure returned by annotate_matchinfo() to try and make it clear what is going on.

Building the rank_bm25() function took me longer than I expected: I was comparing my results against bm25() from peewee to ensure I was getting them right, but I couldn’t get them to match. After some furious debugging I finally figured out the problem: peewee had a rare bug! I reported it to Charles Leifer and he analyzed it and turned around a fix in a matter of hours - it turns out the C library that peewee had ported to Python had the same problem.

Next steps

I’m really impressed with the flexibility that FTS4 provides - it turns out FTS5 isn’t the only worthwhile option for search in SQLite

I’m thinking about ways to expose some of the bm25 tuning parameters (in particular the magic B and K1 constants explained by the Elasticsearch article) and I plan to upgrade Datasette’s search functionality to make ranking available as a first-class feature on the searchable table view.

I’m also generally excited about SQLite as a learning tool for exploring different search ranking mechanisms. Once you’ve decoded that binary matchinfo string it’s impressive how much you can get done with the underlying data.

Tags: full-text-search, projects, search, sqlite, datasette

Datasette: Full-text search

2018-05-12T12:09:24+00:00

Datasette: Full-text search

I wrote some documentation for Datasette’s full-text search feature, which detects tables which have been configured to use the SQLite FTS module and adds a search input box and support for a _search= querystring parameter.

Tags: full-text-search, search, sqlite, datasette

Implementing faceted search with Django and PostgreSQL

2017-10-05T14:12:27+00:00

I’ve added a faceted search engine to this blog, powered by PostgreSQL. It supports regular text search (proper search, not just SQL"like" queries), filter by tag, filter by date, filter by content type (entries vs blogmarks vs quotation) and any combination of the above. Some example searches:

It also provides facet counts, so you can tell how many results you will get back before you apply one of these filters - and get a general feeling for the shape of the corpus as you navigate it.

I love this kind of search interface, because the counts tell you so much more about the underlying data. Turns out I was most active in quoting people talking about JavaScript back in 2007, for example.

I usually build faceted search engines using either Solr or Elasticsearch (though the first version of search on this blog was actually powered by Hyper Estraier) - but I’m hosting this blog as simply and inexpensively as possible on Heroku and I don’t want to shell out for a SaaS search solution or run an Elasticsearch instance somewhere myself. I thought I’d have to go back to using Google Custom Search.

Then I read Postgres full-text search is Good Enough! by Rachid Belaid - closely followed by Postgres Full-Text Search With Django by Nathan Shafer - and I decided to have a play with the new PostgreSQL search functionality that was introduced in Django 1.10.

… and wow! Full-text search is yet another example of a feature that’s been in PostgreSQL for nearly a decade now, incrementally improving with every release to the point where it’s now really, really good.

At its most basic level a search system needs to handle four things:

It needs to take user input and find matching documents.
It needs to understand and ignore stopwords (common words like “the” and “and”) and apply stemming - knowing that “ridicule” and “ridiculous” should be treated as the same root, for example. Both of these features need to be language-aware.
It needs to be able to apply relevance ranking, calculating which documents are the best match for a search query.
It needs to be fast - working against some kind of index rather than scanning every available document in full.

Modern PostgreSQL ticks all of those boxes. Let’s put it to work.

Simple search without an index

Here’s how to execute a full-text search query against a simple text column:

from blog.models import Entry
from django.contrib.postgres.search import SearchVector

results = Entry.objects.annotate(
    searchable=SearchVector('body')
).filter(searchable='django')

The generated SQL looks something like this:

SELECT "blog_entry"."id", ...,
to_tsvector(COALESCE("blog_entry"."body", %s)) AS "searchable"
FROM "blog_entry"
WHERE to_tsvector(COALESCE("blog_entry"."body", "django"))
    @@ (plainto_tsquery("django")) = true
ORDER BY "blog_entry"."created" DESC

The SearchVector class constructs a stemmed, stopword-removed representation of the body column ready to be searched. The resulting queryset contains entries that are a match for “django”.

My blog entries are stored as HTML, but I don’t want search to include those HTML tags. One (extremely un-performant) solution is to use Django’s Func helper to apply a regular expression inside PostgreSQL to strip tags before they are considered for search:

from django.db.models import Value, F, Func

results = Entry.objects.annotate(
    searchable=SearchVector(
        Func(
            F('body'), Value('<.*?>'), Value(''), Value('g'),
            function='regexp_replace'
        )
    )
).filter(searchable='http')

Update 6th October 8:23pm UTC - it turns out this step is entirely unnecessary. Paolo Melchiorre points out that the PostgreSQL ts_vector() function already handles tag removal. Sure enough, executing SELECT to_tsvector('<div>Hey look what happens to <blockquote>this tag</blockquote></div>') using SQL Fiddle returns 'happen':4 'hey':1 'look':2 'tag':7, with the tags already stripped.

This works, but performance isn’t great. PostgreSQL ends up having to scan every row and construct a list of search vectors for each one every time you execute a query.

If you want it to go fast, you need to add a special search vector column to your table and then create the appropriate index on it. As of Django 1.11 this is trivial:

from django.contrib.postgres.search import SearchVectorField
from django.contrib.postgres.indexes import GinIndex

class Entry(models.Model):
    # ...
    search_document = SearchVectorField(null=True)

    class Meta:
        indexes = [
            GinIndex(fields=['search_document'])
        ]

Django’s migration system will automatically add both the field and the special GIN index.

What’s trickier is populating that search_document field. Django does not yet support a easy method to populate it directly in your initial INSERT call, instead recommending that you populated with a SQL UPDATE statement after the fact. Here is a one-liner that will populate the field for everything in that table (and strip tags at the same time):

def strip_tags_func(field):
    return Func(
        F(field), Value('<.*?>'), Value(''), Value('g'),
        function='regexp_replace'
    )
 
Entry.objects.update(
    search_document=(
        SearchVector('title', weight='A') +
        SearchVector(strip_tags_func('body'), weight='C')
    )
)

I’m using a neat feature of the SearchVector class here: it can be concatenated together using the + operator, and each component can be assigned a weight of A, B, C or D. These weights affect ranking calculations later on.

Updates using signals

We could just set this up to run periodically (as I did in my initial implementation), but we can get better real-time results by ensuring this field gets updated automatically when the rest of the model is modified. Some people solve this with PostgreSQL triggers, but I’m still more comfortable handling this kind of thing in python code - so I opted to use Django’s signals mechanism instead.

Since I need to run search queries across three different types of blog content - Entries, Blogmarks and Quotations - I added a method to each model that returns the text fragments corresponding to each of the weight values. Here’s that method for my Quotation model:

class Quotation(models.Model):
    quotation = models.TextField()
    source = models.CharField(max_length=255)
    tags = models.ManyToManyField(Tag, blank=True)

    def index_components(self):
        return {
            'A': self.quotation,
            'B': ' '.join(self.tags.values_list('tag', flat=True)),
            'C': self.source,
        }

As you can see, I’m including the tags that have been assigned to the quotation in the searchable document.

Here are my signals - loaded once via an import statement in my blog application’s AppConfig.ready() method:

@receiver(post_save)
def on_save(sender, **kwargs):
    if not issubclass(sender, BaseModel):
        return
    transaction.on_commit(make_updater(kwargs['instance']))

@receiver(m2m_changed)
def on_m2m_changed(sender, **kwargs):
    instance = kwargs['instance']
    model = kwargs['model']
    if model is Tag:
        transaction.on_commit(make_updater(instance))
    elif isinstance(instance, Tag):
        for obj in model.objects.filter(pk__in=kwargs['pk_set']):
            transaction.on_commit(make_updater(obj))

def make_updater(instance):
    components = instance.index_components()
    pk = instance.pk

    def on_commit():
        search_vectors = []
        for weight, text in components.items():
            search_vectors.append(
                SearchVector(Value(text, output_field=models.TextField()), weight=weight)
            )
        instance.__class__.objects.filter(pk=pk).update(
            search_document=reduce(operator.add, search_vectors)
        )
    return on_commit

(The full code can be found here).

The on_save method is pretty straightforward - it checks if the model that was just saved has my BaseModel as a base class, then it calls make_updater to get a function to be executed by the transaction.on_commit hook.

The on_m2m_changed handler is significantly more complicated. There are a number of scenarios in which this will be called - I’m reasonably confident that the idiom I use here will capture all of the modifications that should trigger a re-indexing operation.

Running a search now looks like this:

results = Entry.objects.filter(
    search_document=SearchQuery('django')
)

We need one more thing though: we need to sort our search results by relevance. PostgreSQL has pretty good relevance built in, and sorting by the relevance score can be done by applying a Django ORM annotation:

query = SearchQuery('ibm')

results = Entry.objects.filter(
    search_document=query
).annotate(
    rank=SearchRank(F('search_document'), query)
).order_by('-rank')

We now have basic full text search implemented against a single Django model, making use of a GIN index. This is lightning fast.

Searching multiple tables using queryset.union()

My site has three types of content, represented in three different models and hence three different underlying database tables.

I’m using an abstract base model to define common fields shared by all three: the created date, the slug (used to construct permalink urls) and the search_document field populated above.

As of Django 1.11 It’s possible to combine queries across different tables using the SQL union operator.

Here’s what that looks like for running a search across three tables, all with the same search_document search vector field. I need to use .values() to restrict the querysets I am unioning to the same subset of fields:

query = SearchQuery('django')
rank_annotation = SearchRank(F('search_document'), query)
qs = Blogmark.objects.annotate(
    rank=rank_annotation,
).filter(
    search_document=query
).values('pk', 'created', 'rank').union(
    Entry.objects.annotate(
        rank=rank_annotation,
    ).filter(
        search_document=query
    ).values('pk', 'created', 'rank'),
    Quotation.objects.annotate(
        rank=rank_annotation,
    ).filter(
        search_document=query
    ).values('pk', 'created', 'rank'),
).order_by('-rank')[:5]

# Output
<QuerySet [
    {'pk': 186, 'rank': 0.875179, 'created': datetime.datetime(2008, 4, 8, 13, 48, 18, tzinfo=<UTC>)},
    {'pk': 134, 'rank': 0.842655, 'created': datetime.datetime(2007, 10, 20, 13, 46, 56, tzinfo=<UTC>)},
    {'pk': 1591, 'rank': 0.804502, 'created': datetime.datetime(2009, 9, 28, 23, 32, 4, tzinfo=<UTC>)},
    {'pk': 5093, 'rank': 0.788616, 'created': datetime.datetime(2010, 2, 26, 19, 22, 47, tzinfo=<UTC>)},
    {'pk': 2598, 'rank': 0.786928, 'created': datetime.datetime(2007, 1, 26, 12, 38, 46, tzinfo=<UTC>)}
]>

This is not enough information though - I have the primary keys, but I don’t know which type of model they belong to. In order to retrieve the actual resulting objects from the database I need to know which type of content is represented by each of those results.

I can achieve that using another annotation:

qs = Blogmark.objects.annotate(
    rank=rank_annotation,
    type=models.Value('blogmark', output_field=models.CharField())
).filter(
    search_document=query
).values('pk', 'type', 'rank').union(
    Entry.objects.annotate(
        rank=rank_annotation,
        type=models.Value('entry', output_field=models.CharField())
    ).filter(
        search_document=query
    ).values('pk', 'type', 'rank'),
    Quotation.objects.annotate(
        rank=rank_annotation,
        type=models.Value('quotation', output_field=models.CharField())
    ).filter(
        search_document=query
    ).values('pk', 'type', 'rank'),
).order_by('-rank')[:5]

# Output:
<QuerySet [
    {'pk': 186, 'type': u'quotation', 'rank': 0.875179},
    {'pk': 134, 'type': u'quotation', 'rank': 0.842655},
    {'pk': 1591, 'type': u'entry', 'rank': 0.804502},
    {'pk': 5093, 'type': u'blogmark', 'rank': 0.788616},
    {'pk': 2598, 'type': u'blogmark', 'rank': 0.786928}
]>

Now I just need to write function which can take a list of types and primary keys and return the full objects from the database:

def load_mixed_objects(dicts):
    """
    Takes a list of dictionaries, each of which must at least have a 'type'
    and a 'pk' key. Returns a list of ORM objects of those various types.
    Each returned ORM object has a .original_dict attribute populated.
    """
    to_fetch = {}
    for d in dicts:
        to_fetch.setdefault(d['type'], set()).add(d['pk'])
    fetched = {}
    for key, model in (
        ('blogmark', Blogmark),
        ('entry', Entry),
        ('quotation', Quotation),
    ):
        ids = to_fetch.get(key) or []
        objects = model.objects.prefetch_related('tags').filter(pk__in=ids)
        for obj in objects:
            fetched[(key, obj.pk)] = obj
    # Build list in same order as dicts argument
    to_return = []
    for d in dicts:
        item = fetched.get((d['type'], d['pk'])) or None
        if item:
            item.original_dict = d
        to_return.append(item)
    return to_return

One last challenge: when I add filtering by type, I’m going to want to selectively union together only a subset of these querysets. I need a queryset to start unions against, but I don’t yet know which queryset I will be using. I can abuse Django’s queryset.none() method to crate an empty ValuesQuerySet in the correct shape like this

qs = Entry.objects.annotate(
    type=models.Value('empty', output_field=models.CharField()),
    rank=rank_annotation
).values('pk', 'type', 'rank').none()

Now I can progressively build up my union in a loop like this:

for klass in (Entry, Blogmark, Quotation):
    qs = qs.union(klass.objects.annotate(
        rank=rank_annotation,
        type=models.Value('quotation', output_field=models.CharField())
    ).filter(
        search_document=query
    ).values('pk', 'type', 'rank'))

The Django ORM is smart enough to compile away the empty queryset when it constructs the SQL, which ends up looking something like this:

(((SELECT "blog_entry"."id",
            "entry" AS "type",
            ts_rank("blog_entry"."search_document", plainto_tsquery(%s)) AS "rank"
     FROM "blog_entry"
     WHERE "blog_entry"."search_document" @@ (plainto_tsquery(%s)) = TRUE
     ORDER BY "blog_entry"."created" DESC))
 UNION
   (SELECT "blog_blogmark"."id",
           "blogmark" AS "type",
           ts_rank("blog_blogmark"."search_document", plainto_tsquery(%s)) AS "rank"
    FROM "blog_blogmark"
    WHERE "blog_blogmark"."search_document" @@ (plainto_tsquery(%s)) = TRUE
    ORDER BY "blog_blogmark"."created" DESC))
UNION
  (SELECT "blog_quotation"."id",
          "quotation" AS "type",
          ts_rank("blog_quotation"."search_document", plainto_tsquery(%s)) AS "rank"
   FROM "blog_quotation"
   WHERE "blog_quotation"."search_document" @@ (plainto_tsquery(%s)) = TRUE
   ORDER BY "blog_quotation"."created" DESC)

Applying filters

So far, our search engine can only handle user-entered query strings. If I am going to build a faceted search interface I need to be able to handle filtering as well. I want the ability to filter by year, tag and type.

The key difference between filtering and querying (borrowing these definitions from Elasticsearch) is that querying is loose - it involves stemming and stopwords - while filtering is exact. Additionally, querying affects the calculated relevance score while filtering does not - a document either matches the filter or it doesn’t.

Since PostgreSQL is a relational database, filtering can be handled by simply constructing extra SQL where clauses using the Django ORM.

Each of the filters I need requires a slightly different approach. Filtering by type is easy - I just selectively include or exclude that model from my union queryset.

Year and month work like this:

selected_year = request.GET.get('year', '')
selected_month = request.GET.get('month', '')
if selected_year:
    qs = qs.filter(created__year=int(selected_year))
if selected_month:
    qs = qs.filter(created__month=int(selected_month))

Tags involve a join through a many-2-many relationship against the Tags table. We want to be able to apply more than one tag, for example this search for all items tagged both python and javascript. Django’s ORM makes this easy:

selected_tags = request.GET.getlist('tag')
for tag in selected_tags:
    qs = qs.filter(tags__tag=tag)

Adding facet counts

There is just one more ingredient needed to complete our faceted search: facet counts!

Again, the way we calculate these is different for each of our filters. For types, we need to call .count() on a separate queryset for each of the types we are searching:

queryset = make_queryset(Entry, 'entry')
type_counts['entry'] = queryset.count()

(the make_queryset function is defined here)

For years we can do this:

from django.db.models.functions import TruncYear

for row in queryset.order_by().annotate(
    year=TruncYear('created')
).values('year').annotate(n=models.Count('pk')):
    year_counts[row['year']] = year_counts.get(
        row['year'], 0
    ) + row['n']

Tags are trickiest. Let’s take advantage of he fact that Django’s ORM knows how to construct sub-selects if you pass another queryset to the __in operator.

tag_counts = {}
type_name = 'entry'
queryset = make_queryset(Entry, 'entry')
for tag, count in Tag.objects.filter(**{
    '%s__in' % type_name: queryset
}).annotate(
    n=models.Count('tag')
).values_list('tag', 'n'):
    tag_counts[tag] = tag_counts.get(tag, 0) + count

Rendering it all in a template

Having constructed the various facets counts in the view function, the template is really simple:

{% if type_counts %}
    <h3>Types</h3>
    <ul>
        {% for t in type_counts %}
            <li><a href="{% add_qsarg "type" t.type %}">{{ t.type }}</a> {{ t.n }}</a></li>
        {% endfor %}
    </ul>
{% endif %}
{% if year_counts %}
    <h3>Years</h3>
    <ul>
        {% for t in year_counts %}
            <li><a href="{% add_qsarg "year" t.year|date:"Y" %}">{{ t.year|date:"Y" }}</a> {{ t.n }}</a></li>
        {% endfor %}
    </ul>
{% endif %}
{% if tag_counts %}
    <h3>Tags</h3>
    <ul>
        {% for t in tag_counts %}
            <li><a href="{% add_qsarg "tag" t.tag %}">{{ t.tag }}</a> {{ t.n }}</a></li>
        {% endfor %}
    </ul>
{% endif %}

I am using custom templates tags here to add arguments to the current URL. I’ve built systems like this in the past where the URLs are instead generated in the view logic, which I think I prefer. As always, perfect is the enemy of shipped.

And because the results are just a Django queryset, we can use Django’s pagination helpers for the pagination links.

The final implementation

The full current version of the code at time of writing can be seen here. You can follow my initial implementation of this feature through the following commits: 7e3a0217 c7e7b30c 7f6b524c a16ddb5e 7055c7e1 74c194d9 f3ffc100 6c24d9fd cb88c2d4 2c262c75 776a562a b8484c50 0b361c78 1322ada2 79b1b13d 3955f41b 3f5ca052.

And that’s how I built faceted search on top of PostgreSQL and Django! I don’t have my blog comments up and running yet, so please post any thoughts or feedback over on this GitHub issue or over on this thread on Hacker News.

Update 9th September 2021: A few years after implementing this I started to notice performance issues with my blog, which turned out to be caused by search engine crawlers hitting every possible combination of facets, triggering a ton of expensive SQL queries. I excluded /search from being crawled using robots.txt which fixed the problem.

Tags: django, full-text-search, orm, postgresql, projects, search, facetedsearch

A fast, fuzzy, full-text index using Redis

2010-05-05T17:51:00+00:00

A fast, fuzzy, full-text index using Redis

Interesting twist on building a reverse-index using Redis sets: this one indexes only the metaphones of the words, resulting in a phonetic fuzzy search.

Tags: full-text-search, redis, search, recovered, fuzzy, metaphone

Digg Search: Now With 99.987% Less Suck

2009-04-10T22:17:57+00:00

Digg Search: Now With 99.987% Less Suck

Really nice implementation of faceted search, still using Lucene and Solr under the hood.

Tags: digg, facets, full-text-search, lucene, search, solr

Sphinx 0.9.9-rc2 is out

2009-04-08T13:59:26+00:00

Sphinx 0.9.9-rc2 is out

Interesting new feature: the Sphinx search server now supports the MySQL binary protocol, so you can talk to it using a regular MySQL client library and fire off search queries using SELECT syntax and the new SphinxQL query language.

Tags: full-text-search, mysql, search, sphinx-search, sql

Guardian + Lucene = Similar Articles + Categorisation

2009-03-11T12:53:39+00:00

Guardian + Lucene = Similar Articles + Categorisation

Alf Eaton loaded 13,000 Guardian articles tagged Science in to Solr and Lucene and is using Solr’s MoreLikeThisHandler to find related articles and automatically apply Guardian tags to Nature News articles.

Tags: alf-eaton, full-text-search, guardian, lucene, naturenews, openplatform, search, solr, tagging

Xapian performance comparision with Whoosh

2009-02-14T13:15:15+00:00

Xapian performance comparision with Whoosh

Whoosh appears to be around four times slower than Xapian for indexing and empty cache searches, but Xapian with a full cache blows Whoosh out of the water (5408 searches/second compared to 26.3). Considering how fast Xapian is, that’s still a pretty impressive result for the pure-Python Whoosh.

Tags: full-text-search, python, richard-boulton, search, whoosh, xapian

Tokyo Cabinet and Tokyo Tyrant Presentation

2009-02-14T11:34:58+00:00

Tokyo Cabinet and Tokyo Tyrant Presentation

By Tokyo Cabinet author Mikio Hirabayashi. The third leg of the Tokyo tripod is Tokyo Dystopia, a full-text search engine which is presumably a modern replacement for Mikio’s older hyperestraier engine.

Tags: full-text-search, hyperestraier, mikiohirabayashi, tokyocabinet, tokyodystopia, tokyotyrant

Whoosh

2009-02-12T12:49:59+00:00

Whoosh

A brand new, pure-python full text indexing engine (think Lucene). Claims to offer performance in the same league as wrappers to C or Java libraries. If this works as well as it claims it will be an excellent tool for adding search to projects that wish to avoid a dependency on an external engine.

Tags: full-text-search, lucene, open-source, python, search, whoosh

How-to: Full-text search in Google App Engine

2008-06-27T08:25:35+00:00

How-to: Full-text search in Google App Engine

Use search.SearchableModel instead of db.Model—it’s pretty rough at the moment which is probably why it’s still undocumented.

Tags: full-text-search, google-app-engine, python, search

PostgreSQL 8.3 beta 4 release notes

2007-12-12T00:43:58+00:00

PostgreSQL 8.3 beta 4 release notes

In addition to the huge speed improvements, 8.3 adds support for XML, UUID and ENUM data types and brings full text (tsearch2) in to the core database engine.

Tags: beta, databases, enum, full-text-search, postgresql, tsearch2, uuid, xml

Opera 9.5 alpha, Kestrel, released

2007-09-16T20:34:34+00:00

Opera 9.5 alpha, Kestrel, released

“With history search, Opera creates a full-text index of each and every page you visit, and when you go to the address bar, you can simply start entering words you know have been on pages you’ve visited before, and items matching your search show up.” I just tried this; it’s magic. I’m switching back to Opera from Camino.

Tags: browsers, camino, full-text-search, history, kestrel, opera, search

django-sphinx

2007-09-09T00:35:19+00:00

django-sphinx

More code from Curse Gaming; this time a really nice API for adding Sphinx full-text search to a Django model.

Via David Cramer

Tags: cursegaming, david-cramer, django, full-text-search, orm, python, search, sphinx-search

SQLite Keynote

2006-10-21T23:44:28+00:00

SQLite Keynote

SQLite 3.3.8 has full text indexing!

Tags: full-text-search, sqlite, d-richard-hipp