Search and suggest on your own database

A search page and a type-ahead box need two predicates and an index. Storm's search and suggest take the input as the user typed it, match it the same way on every database, and find rows through related tables. There is no second system to run or keep in sync.

01The task

The front desk of a pet clinic looks up owners all day. It has two boxes. The search page takes a few words, such as davis madison, and lists every owner they match. The box at the top suggests owners while the receptionist types, six at a time.

Both boxes receive raw input: several words, any case, sometimes a quote or a stray %. Written by hand, that means splitting the words, lowering them, escaping the LIKE wildcards, building an OR per column and an AND per word, and handling the empty box. It also means a query that reads the whole table once the data grows. The model for this tutorial:

data class Owner(
    @PK val id: Int = 0,
    val firstName: String,
    val lastName: String,
    val address: Address,
    val telephone: String?
) : Entity<Int>

data class Address(val street: String, @FK val city: City)

data class Pet(
    @PK val id: Int = 0,
    val name: String,
    @FK val owner: Owner
) : Entity<Int>

02The search page

search takes the input as the box received it and the columns to match. It returns a predicate, so it goes in where and combines with other conditions through and and or:

interface OwnerRepository : EntityRepository<Owner, Int> {

    // "davis madison": every word must match the last name or the city
    fun find(input: String): List<Owner> =
        select()
            .where(search(input, Owner_.lastName, Owner_.address.city.name))
            .orderBy(Owner_.lastName)
            .resultList
}

SELECT o.id, o.first_name, o.last_name, …, c.name
FROM owner o
LEFT JOIN city c ON o.city_id = c.id
WHERE (LOWER(o.last_name) LIKE LOWER(?) ESCAPE '!' OR LOWER(c.name) LIKE LOWER(?) ESCAPE '!')
  AND (LOWER(o.last_name) LIKE LOWER(?) ESCAPE '!' OR LOWER(c.name) LIKE LOWER(?) ESCAPE '!')
ORDER BY o.last_name
-- binds '%davis%' and '%madison%': one AND per word, one OR per column

Every word has to occur in at least one of the columns. Matching ignores case and treats the input as literal text, so 50% looks for a percent sign. The city name sits on another table; the path Owner_.address.city.name joins it. The statement is the same on every database Storm supports.

03Suggestions while typing

A type-ahead box queries on inputs like da and van b, far more often than a search page, so each query has to stay cheap. suggest takes the same input and columns and matches every word at the start of a word: van b finds "Van den Berg" and not "Sullivan". A word starts at the beginning of the value or after a space, hyphen, apostrophe, parenthesis, slash, colon, period or comma, so marie finds "Anne-Marie" and brien finds "O'Brien". orderFirst puts the closest matches on top:

// "dav" as the receptionist types: owners first, best match on top
fun suggestions(input: String): List<Owner> =
    select()
        .where(suggest(input, Owner_.lastName, Owner_.firstName))
        .orderFirst(Owner_.lastName eqIgnoreCase input)
        .orderFirst(Owner_.lastName startsWithIgnoreCase input)
        .orderBy(Owner_.lastName)
        .limit(6)
        .resultList

-- PostgreSQL renders a word start as one regular expression
SELECT o.id, o.first_name, o.last_name, …
FROM owner o
WHERE LOWER(o.last_name) ~ LOWER(?) OR LOWER(o.first_name) ~ LOWER(?)
ORDER BY CASE WHEN LOWER(o.last_name) = LOWER(?) THEN 0 ELSE 1 END,
         CASE WHEN LOWER(o.last_name) LIKE LOWER(?) ESCAPE '!' THEN 0 ELSE 1 END,
         o.last_name
LIMIT 6
-- the word binds as '(^|[- ''(/:.,])dav': the value's start, or after a space or punctuation

The two functions read input the same way and differ in what an empty or very short box means:

The short-word rule keeps the first keystrokes from reading and sorting a large part of the table. Once one word reaches three characters, the others are tested only on the rows that word found: for van d, van finds the rows and d narrows them.

04Finding owners through their pets

The receptionist often remembers the dog, not the owner. Semi-join the pets and name the pet's column next to the owner's. Each owner comes back once, however many pets match, and an owner without pets is still found by name:

// "davis leo": the owner named Davis who has a pet called Leo
fun find(input: String): List<Owner> =
    select()
        .semiJoin<Pet>().on<Owner>()
        .where(search(input, Owner_.lastName, Pet_.name))
        .resultList

SELECT o.id, o.first_name, o.last_name, …
FROM owner o
WHERE o.id IN (
  SELECT o.id FROM owner o WHERE LOWER(o.last_name) LIKE LOWER(?) ESCAPE '!'
UNION
  SELECT p.owner_id FROM pet p WHERE LOWER(p.name) LIKE LOWER(?) ESCAPE '!'
) AND o.id IN (
  -- the same two branches for the second word
)
-- each branch reads its own table through its own index; no join, no DISTINCT

Each word is matched on its own, so leo max finds the owner of both a Leo and a Max. A word renders as an IN over a UNION with a branch per table, so the database reads each table through its own index instead of joining owners to every pet. A further semiJoin<Visit>().on<Pet>() with Visit_.description finds owners by what their pets came in for.

05Match forms and noise words

Each column can state how a word matches it: anywhere, wordStart, prefix or exact, plus IgnoreCase variants of the last two. Some words narrow nothing. In a Dutch clinic, van starts a large share of last names and also occurs inside "Sullivan", so it costs the most to test and drops owners who lack it. Pass a set of words to ignore after the input:

val nameNoise = setOf("van", "de", "der", "den")

fun suggestions(input: String): List<Owner> =
    select()
        .semiJoin<Pet>().on<Owner>()
        .where(suggest(
            input,
            nameNoise,                                // words that narrow nothing
            wordStart(Owner_.lastName),
            wordStart(Pet_.name).withoutFallback(),  // pets join in from three characters
            exact(Owner_.telephone),                // a whole number, on an ordinary index
        ))
        .orderBy(Owner_.lastName)
        .limit(6)
        .resultList

With that box, van berg matches on berg alone, and a quoted "van" still counts. A telephone number matches only whole, which an ordinary index serves. withoutFallback() keeps the pets out of the statement until a word reaches three characters: for le, the query reads only the owners, and pets join in at leo. Pet names that merely start with "le" would rank below the owners' own names anyway, and reading them is the expensive part.

06The index that keeps it fast

search and suggest compare LOWER(column) against a pattern that can start anywhere in the value. An ordinary B-tree index cannot serve that. On PostgreSQL, a trigram index over the same expression serves both the LIKE and the word-start expression:

-- a migration; PostgreSQL ships the trigram extension
CREATE EXTENSION IF NOT EXISTS pg_trgm;

CREATE INDEX owner_last_name_trgm  ON owner USING gin (LOWER(last_name) gin_trgm_ops);
CREATE INDEX owner_first_name_trgm ON owner USING gin (LOWER(first_name) gin_trgm_ops);
CREATE INDEX pet_name_trgm         ON pet   USING gin (LOWER(name) gin_trgm_ops);
CREATE INDEX owner_telephone       ON owner (telephone);

Storm renders the predicate the same way for every input, so the index matches without changes to the query. prefix and exact compare the bare column, which an ordinary index serves on any database. On a database without a substring index, a word-suffix table kept by a trigger gives wordStart an ordinary index to use; the search docs show the table and the query.

Storm also checks this for you. Spring Boot and Ktor load the schema when they validate it at startup, and once a slow threshold is set, a search that turns out slow carries advice naming the index it lacks:

SQL slow (SELECT Owner): 412 ms in database, 6 rows, OwnerController.kt:31
	SELECT o.id, o.first_name, o.last_name, … FROM owner o WHERE LOWER(o.last_name) ~ LOWER(?) …
	shape: 56f85e0581c8f643  parameters: 3
	advice: no index on owner serves wordStart(last_name), so the database reads owner in full to match it.
		fix: a trigram index on LOWER(last_name) serves it.
		see: https://orm.st/docs/advice#unindexed-search

The advice tutorial covers where that line comes from. For accents, wrap a column in a SqlFunction over an accent-removing database function, so "muller" finds "Müller" through an index on the same expression; see Ignoring Accents.

07What it does not do

search matches words. It does not score relevance, stem words, or correct typos the way a search engine or a full-text index does. You state the ranking with orderFirst, and for full-text features you can call the database's own full-text search from a SQL template. For looking up owners, pets, products or orders by name, the database you already run is enough.

08Keep going

The reference documentation covers the mechanics in depth: