All-in-SQL Hybrid Search in DuckDB: Integrating Full Text and Embedding Methods

Demo: Movies Dataset

For this blog, we’ll be using the Kaggle Movies dataset [1], the same one we used in the embedding search blog.

To load the dataset you have two options :

1. Using MotherDuck public datasets through shares. Any MotherDuck user has access to the sample_data database where the movies dataset is present under sample_data.kaggle.movies. Plus you leverage the power of the Cloud through MotherDuck
2. Read from a public AWS S3 bucket where we maintain our open datasets (see snippet below). The file is ~ 500 MB.

Let’s first load in the dataset:

create table movies as select title, overview
FROM 's3://us-prd-motherduck-open-datasets/movies/parquet/movies.parquet';

describe movies;

| column_name | column_type | null | key  | default | extra |
|-------------|-------------|------|------|---------|-------|
| title       | VARCHAR     | YES  | NULL | NULL    | NULL  |
| overview    | VARCHAR     | YES  | NULL | NULL    | NULL  |
|             |             |      |      |         |       |

Stemmer

Stemming is a process of simplifying words by removing common word endings from them. For example, the word running would be converted to run, cats to cat. This makes the search for keywords in their different forms much easier. DuckDB provides various stemmers, and defaults to stemmer = porter. There is also an option to disable this process of simplifying words by passing stemmer = none to the argument.

Stopwords

Stopwords are commonly used words in a language, and are often removed from the search context in keyword based search systems as they add very little value. In English, “a”, “is”, “the”, “are” are examples of some stopwords. The FTS extension defaults to using English stopwords, stopwords = ‘english’.

For our example dataset, let’s build the index for the columns title and overview using the title as the document identifier since this is a unique identifier for the rows in our table, while using the defaults for the optional arguments.

pragma create_fts_index(movies, title, title, overview)

Upon executing this, a few tables are created on the same database as the input_table but in another schema, which is usually the name of the input_table with a prefix as fts_main_<input_table>. These newly created tables hold the inverted index for the full text search.

select database, schema, name, column_names FROM (show all tables)

| database | schema          | name      | column_names             | column_types              |
| -------- | --------------- | --------- | ------------------------ | ------------------------- |
| memory   | fts_main_movies | dict      | [termid, term, df]       | [BIGINT, VARCHAR, BIGINT] |
| memory   | fts_main_movies | docs      | [docid, name, len]       | [BIGINT, VARCHAR, BIGINT] |
| memory   | fts_main_movies | fields    | [fieldid, field]         | [BIGINT, VARCHAR]         |
| memory   | fts_main_movies | stats     | [num_docs, avgdl]        | [BIGINT, DOUBLE]          |
| memory   | fts_main_movies | stopwords | [sw]                     | [VARCHAR]                 |
| memory   | fts_main_movies | terms     | [docid, fieldid, termid] | [BIGINT, BIGINT, BIGINT]  |
| memory   | main            | movies    | [title, overview]        | [VARCHAR, VARCHAR]        |

Exploring some of the newly created tables, we can see the effects of the parameters we chose when creating the FTS index. Below are some notes to understand each created table:

| schema          | name      | column_names             |     | description                                                                                                             |
| --------------- | --------- | ------------------------ | --- | ----------------------------------------------------------------------------------------------------------------------- |
| fts_main_movies | dict      | [termid, term, df]       |     | stores a mapping of all the terms (keywords in the docs) to a termid                                                    |
| fts_main_movies | docs      | [docid, name, len]       |     | creates a map of the input_id stored here as name to an internal docid for the FTS index along with the document length |
| fts_main_movies | fields    | [fieldid, field]         |     | maps a fieldid to the table columns given in input_values that were indexed                                             |
| fts_main_movies | stats     | [num_docs, avgdl]        |     | stats used to calculate the similarity scores                                                                           |
| fts_main_movies | stopwords | [sw]                     |     | lists all the stopwords for this index, corresponding to the chosen option when creating the index                      |
| fts_main_movies | terms     | [docid, fieldid, termid] |     | maps the document docid to the field with fieldid (column) to the term with termid                                      |
| main            | movies    | [title, overview]        |     | table that is indexed for the full text search

A note for the curious ones: these tables can be queried, inspected and used in other queries downstream.

Fused Metric for Ranking

The crux of any search algorithm is to have a metric to rank the dataset for a given query, from which the top N values are retrieved when listed in descending order. For hybrid search we would require a metric that fuses scores from both search modes. Two of the most commonly used fusion metrics are: (i) convex combination and (ii) reciprocal ranked fusion.

Reciprocal Ranked Fusion (RRF)

RRF sums the reciprocals of the ranks of documents, where the rank of the document is the row number when sorted in descending order using a ranking score. To adjust the importance of the low ranked documents a constant k is added to the rank. This gives the formula for RRF as:

Convex Combination (weighted normalized scores)

This method reportedly performs better than RRF when calibrated. It is expressed as a linear function that sums the normalized scores weighted against a parameter ⍺. The calibration of the parameter requires a good amount of annotated dataset, but with a lack of it we could use a default value of 0.8 as suggested in this paper [3] for in domain datasets. Which gives:

In this post, we will focus on using Convex Combination as it reportedly performs better, beyond the suggested value for ⍺, it is customizable for any use-case in hand, with a few annotated samples the parameter can be tuned.

wiht fts as (
    select 
        title, 
        overview, 
        fts_main_movies.match_bm25(
            title,
            'an adventure across the galaxy for the ultimate power struggle',
            fields := 'overview'
        ) as score
    from movies
),
embd as (
    select 
        title, 
        overview, 
        array_cosine_similarity(overview_embeddings, cast([0.343.., ...] as float[1536])) as score
    from movies
),
normalized_scores as (
    select 
        fts.title, 
        fts.overview, 
        fts.score as raw_fts_score, 
        embd.score as raw_embd_score,
        (fts.score / (select max(score) from fts)) as norm_fts_score,
        ((embd.score + 1) / (select max(score) + 1 from embd)) as norm_embd_score
    from 
        fts
    inner join
        embd 
    on fts.title = embd.title
)
select 
    title,
    raw_fts_score, 
    raw_embd_score, 
    norm_fts_score, 
    norm_embd_score, 
    -- (alpha * norm_embd_score + (1-alpha) * norm_fts_score)
    (0.8*norm_embd_score + 0.2*norm_fts_score) AS score_cc
from 
    normalized_scores
order by 
    score_cc desc
limit 5;

We get the following top 5 results:

| title                                   | overview                                                                | norm_fts_score | norm_embd_score | score_cc   |
| --------------------------------------- | ----------------------------------------------------------------------- | -------------- | --------------- | ---------- |
| Threads of Destiny                      | 94 years after The Battle of Yavin, the New Republic has been resurrec… | 0.99462122     | 1.0             | 0.99892424 |
| Stargate: The Ark of Truth              | SG-1 searches for an ancient weapon which could help them defeat the O… | 0.98650582     | 0.97546876      | 0.97767617 |
| Star Trek                               | The fate of the galaxy rests in the hands of bitter rivals. One, James… | 0.89687036     | 0.98548452      | 0.96776169 |
| Mighty Morphin Power Rangers: The Movie | Power up with six incredible teens who out-maneuver and defeat evil ev… | 1.0            | 0.94973698      | 0.95978958 |
| Ratchet & Clank                         | Ratchet and Clank tells the story of two unlikely heroes as they strug… | 0.83376640     | 0.95988163      | 0.93465858 |

Comparing the hybrid results above with FTS, we notice that the top result differs after reranking and that the ranking is not determined solely by a single score. We also observe a new result in the top 5 that wasn’t present in the FTS-only search.