At Superhuman, we're building the fastest email experience in the world.

This post describes the architecture of a delightful search experience that runs inside the web browser itself.

Search is one of the most frequent and important email tasks. Users expect search to have the following properties:

• Fast: Search results should appear right away and update as the user types.
• Powerful: Search should have a friendly and expressive query syntax that allows users to find the right information easily.
• Responsive: The interface should have auto-completion, and syntax-highlighting, which contribute to the perception of speed.
• Available: The search shouldn't require a network connection to function.

Search Architecture

To support the user requirements we wanted our search architecture to have the following properties:

• Local: the search should run inside the web browser itself — contributes to the Fast and Available goals.
• Composable: a query is just a composition of smaller queries — contributes to the Powerful goal.
• Flexible: it should be easy to add and remove features — contributes to the features that makes it Responsive and also makes implementation easier to break down.

As mentioned in a previous post, Superhuman caches as much emails as possible on your device, which allows the search to be Local. Let's look at the database we use to cache emails.

Database Schema

Consider this email thread:

{
 "id": "1578c94e9ecc551f",
 "messages": [
  {
   "id": "1578c94e9ecc551f",
   "subject": "Dinner in SF?",
   "from": "Conrad <conrad@superhuman.com>",
   "to": ["Bhavesh <bhavesh@superhuman.com>"],
   "cc": [],
   "bcc": [],
   "date": "2016–10–03T22:05:51.000Z",
   "attachments": {},
   "labelIds": ["INBOX", "STARRED"],
   "content": "Hey Bhavesh\n Rahul and I get back on the 3rd of   April, want to get dinner at Colibri and talk Superhuman? \nConrad"
  }
 ]
}

As a recipient of this email, I may want to find it later. I could take various approaches:

• Who sent it? from:conrad or from:rahul
• What was it about? dinner
• Or both. dinner (from:conrad or from:rahul)

To power text matching queries like these, we use a WebSQL Full Text Search table: message_search.

To power specific queries like in:inbox or has:attachment, we also use two regular WebSQL tables: threads and thread_labels.

These tables give us everything we need to make our search Composable. Let's now see how we can construct SQL queries from search queries.

Query Compiler

The Query Compiler converts a search query into SQL.

The Query Compiler is modeled after a code compiler. It has four phases:

1. Tokenize the user input
2. Generate a node list from the tokenized user input
3. Generate an abstract syntax tree from the node list
4. Generate SQL from the abstract syntax tree

Let's go through each stage with the following search query:

dinner (from:conrad or from:rahul)

1. Tokenize the user input

As a first step, we convert the user input into an array of tokens.

We use a very simple algorithm:

• Break on delimiters [\s|;|,|(|)]
• If a delimiter was a parenthesis [(|)], add it back as a token
• To allow exact string matches, ignore delimiters after an opening quote “ and before the corresponding closing quote ”

2. Generate a node list

We then convert each token into a node.

For example: dinner will become a Text node with value dinner, whereas from:conrad will become a From node with value conrad.

In Gmail syntax, search terms get joined by an And operator by default in the absence of any operator term. So in this example, we inserted an Andnode between dinner and the open parenthesis (.

3. Generate an abstract syntax tree

We then convert the node list into an abstract syntax tree.

We use the Shunting-yard algorithm to build the tree in a single pass.

4. Generate SQL

We can now recursively generate the SQL.

Each node class has a method generateSQL. This method calls the same method of its child nodes, and then combines the SQL as necessary.

To avoid SQL injection, we build the query with placeholders and a separate array of parameters.

Consider again our example: dinner (from:conrad or from:rahul)

The From node class is a subclass of the Contact node class. The Contactnode class contains the implementation details:

class Contact extends Operand {
  generateSQL() {
    sql = "SELECT thread_ids FROM messages_search WHERE ? MATCH ?"
    params = [this.key, this.left]
    return {sql, params}
  }
}

Meanwhile, the Or node combines the SQL from its children with UNION:

class Or extends Operator {
  generateSQL() {
    left = this.left.generateSQL()
    right = this.right.generateSQL()
    sql = left.sql + " UNION " + right.sql
    params = left.params.concat(right.params)
    return {sql, params}
  }
}

After the recursion is done, the final SQL looks like this:

SELECT *
FROM threads
WHERE thread_id IN (
    SELECT DISTINCT thread_id
    FROM message_search
    WHERE message_search MATCH ?
    
    INTERSECT
    
    SELECT thread_id
    FROM (
      SELECT DISTINCT thread_id
      FROM message_search
      WHERE "from" MATCH ?
      
      UNION
      
      SELECT DISTINCT thread_id
      FROM message_search
      WHERE "from" MATCH ?
    )
)
["dinner", "conrad", "rahul"]

Voilà! This SQL query is now ready for execution in WebSQL.

Advantages

Autocompletion

This kind of search architecture has many advantages. For example, consider autocompletion; no modern search is complete without it. In general, autocompletion can be hard, since user queries can be very complex. How do you know which autocompletion to suggest?

We can reuse parts of the Query Compiler to power autocompletion. When the user types, we quickly tokenize the input and create a node for just the last token. We then call generateAutoComplete on the node to get the suggestions. For example, consider the Contact node:

class Contact extends Operand {
  generateAutoComplete() {
    return this.autoCompleteTrie.search(this.left)
  }
}

Syntax Highlighting

By storing the node list in the UI, we can very easily highlight syntax:

As we saw it was extremely easy to add autocompletion and syntax highlighting using the query compiler, which makes this architecture Flexible.

Conclusion

We built a search architecture that is Local, Composable, and Flexible. This architecture makes the search Fast, Powerful, Responsive, and Available.

How have you architected search for your web app? Please leave a comment below, and please do share if you found this interesting!

— BK (Bhavesh Kakadiya), Lead Engineer, Superhuman