<?xml version="1.0" encoding="UTF-8"?><rss xmlns:dc="http://purl.org/dc/elements/1.1/" xmlns:content="http://purl.org/rss/1.0/modules/content/" xmlns:atom="http://www.w3.org/2005/Atom" version="2.0" xmlns:cc="http://cyber.law.harvard.edu/rss/creativeCommonsRssModule.html">
    <channel>
        <title><![CDATA[Stories by BK (Bhavesh Kakadiya) on Medium]]></title>
        <description><![CDATA[Stories by BK (Bhavesh Kakadiya) on Medium]]></description>
        <link>https://medium.com/@bkakadiya42?source=rss-89a1b832efca------2</link>
        <image>
            <url>https://cdn-images-1.medium.com/fit/c/150/150/1*I0WbQjl9-8cWAKqw4y36Jg.png</url>
            <title>Stories by BK (Bhavesh Kakadiya) on Medium</title>
            <link>https://medium.com/@bkakadiya42?source=rss-89a1b832efca------2</link>
        </image>
        <generator>Medium</generator>
        <lastBuildDate>Sat, 21 Nov 2026 09:28:53 GMT</lastBuildDate>
        <atom:link href="https://medium.com/@bkakadiya42/feed" rel="self" type="application/rss+xml"/>
        <webMaster><![CDATA[yourfriends@medium.com]]></webMaster>
        <atom:link href="http://medium.superfeedr.com/" rel="hub"/>
        <item>
            <title><![CDATA[Delightful search: more than meets the eye]]></title>
            <link>https://medium.com/superhuman-co/delightful-search-more-than-meets-the-eye-d3fa2e3ef3b6?source=rss-89a1b832efca------2</link>
            <guid isPermaLink="false">https://medium.com/p/d3fa2e3ef3b6</guid>
            <category><![CDATA[javascript]]></category>
            <category><![CDATA[sql]]></category>
            <category><![CDATA[progressive-web-app]]></category>
            <category><![CDATA[web-development]]></category>
            <category><![CDATA[search]]></category>
            <dc:creator><![CDATA[BK (Bhavesh Kakadiya)]]></dc:creator>
            <pubDate>Fri, 05 May 2017 20:17:56 GMT</pubDate>
            <atom:updated>2019-10-11T05:02:44.271Z</atom:updated>
            <content:encoded><![CDATA[<figure><img alt="" src="https://cdn-images-1.medium.com/max/1024/0*dVFnudbRK6LdRf7z." /></figure><p><em>At </em><a href="https://superhuman.com/?utm_source=medium&amp;utm_medium=blog&amp;utm_campaign=delightful-search"><em>Superhuman</em></a><em>, we’re building the fastest email experience in the world.</em></p><p><em>This post describes the architecture of a delightful search experience that runs inside the web browser itself.</em></p><p>Search is one of the most frequent and important email tasks. Users expect search to have the following properties:</p><ul><li><strong>Fast</strong>: Search results should appear right away and update as the user types.</li><li><strong>Powerful</strong>: Search should have a friendly and expressive query syntax that allows users to find the right information easily.</li><li><strong>Responsive</strong>: The interface should have auto-completion, and syntax-highlighting, which contribute to the perception of speed.</li><li><strong>Available</strong>: The search shouldn’t require a network connection to function.</li></ul><h3>Search Architecture</h3><p>To support the user requirements we wanted our search architecture to have the following properties:</p><ul><li><strong>Local</strong>: the search should run inside the web browser itself — contributes to the <em>Fast</em> and <em>Available </em>goals.</li><li><strong>Composable</strong>: a query is just a composition of smaller queries — contributes to the <em>Powerful</em> goal.</li><li><strong>Flexible</strong>: it should be easy to add and remove features — contributes to the features that makes it <em>Responsive</em> and also makes implementation easier to break down.</li></ul><p>As mentioned in a <a href="https://blog.superhuman.com/architecting-a-web-app-to-just-work-offline-part-1-8697f316c0eb">previous post</a>, Superhuman caches as much emails as possible on your device, which allows the search to be <em>Local</em>. Let’s look at the database we use to cache emails.</p><h3>Database Schema</h3><p>Consider this email thread:</p><pre>{<br> &quot;id&quot;: &quot;1578c94e9ecc551f&quot;,<br> &quot;messages&quot;: [<br>  {<br>   &quot;id&quot;: &quot;1578c94e9ecc551f&quot;,<br>   &quot;subject&quot;: &quot;Dinner in SF?&quot;,<br>   &quot;from&quot;: &quot;Conrad &lt;conrad@superhuman.com&gt;&quot;,<br>   &quot;to&quot;: [&quot;Bhavesh &lt;bhavesh@superhuman.com&gt;&quot;],<br>   &quot;cc&quot;: [],<br>   &quot;bcc&quot;: [],<br>   &quot;date&quot;: &quot;2016–10–03T22:05:51.000Z&quot;,<br>   &quot;attachments&quot;: {},<br>   &quot;labelIds&quot;: [&quot;INBOX&quot;, &quot;STARRED&quot;],<br>   &quot;content&quot;: &quot;Hey Bhavesh\n Rahul and I get back on the 3rd of   April, want to get dinner at Colibri and talk Superhuman? \nConrad&quot;<br>  }<br> ]<br>}</pre><p>As a recipient of this email, I may want to find it later. I could take various approaches:</p><ul><li>Who sent it? from:conrad or from:rahul</li><li>What was it about? dinner</li><li>Or both. dinner (from:conrad or from:rahul)</li></ul><p>To power text matching queries like these, we use a WebSQL <a href="https://sqlite.org/fts3.html">Full Text Search</a> table: message_search.</p><p>To power specific queries like in:inbox or has:attachment, we also use two regular WebSQL tables: threads and thread_labels.</p><figure><img alt="" src="https://cdn-images-1.medium.com/max/1024/1*kVlEenkXU7xaHHjriwLjVQ.png" /><figcaption>The WebSQL schema for Superhuman.</figcaption></figure><p>These tables give us everything we need to make our search <em>Composable</em>. Let’s now see how we can construct SQL queries from search queries.</p><h3>Query Compiler</h3><p>The Query Compiler converts a search query into SQL.</p><figure><img alt="" src="https://cdn-images-1.medium.com/max/1024/1*_DnJcORUH8bOIrUmPml93A.png" /></figure><p>The Query Compiler is modeled after a code compiler. It has four phases:</p><ol><li>Tokenize the user input</li><li>Generate a node list from the tokenized user input</li><li>Generate an abstract syntax tree from the node list</li><li>Generate SQL from the abstract syntax tree</li></ol><p>Let’s go through each stage with the following search query:</p><p>dinner (from:conrad or from:rahul)</p><h4>1. Tokenize the user input</h4><p>As a first step, we convert the user input into an array of tokens.</p><figure><img alt="" src="https://cdn-images-1.medium.com/max/1024/1*A1jTzDbFMg00T6tB0jaihg.png" /></figure><p>We use a very simple algorithm:</p><ul><li>Break on delimiters [\s|;|,|(|)]</li><li>If a delimiter was a parenthesis [(|)], add it back as a token</li><li>To allow exact string matches, ignore delimiters after an opening quote “ and before the corresponding closing quote ”</li></ul><h4>2. Generate a node list</h4><p>We then convert each token into a node.</p><p>For example: dinner will become a <em>Text</em> node with value dinner, whereas from:conrad will become a <em>From</em> node with value conrad.</p><figure><img alt="" src="https://cdn-images-1.medium.com/max/1024/1*neEWPYI5PCOMBE_rslK0fQ.png" /></figure><p>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 <em>And</em> node between dinner and the open parenthesis (.</p><h4>3. Generate an abstract syntax tree</h4><p>We then convert the node list into an abstract syntax tree.</p><figure><img alt="" src="https://cdn-images-1.medium.com/max/1024/1*E3wevJIlmT4gcDdElKkh8g.png" /></figure><p>We use the <a href="https://en.wikipedia.org/wiki/Shunting-yard_algorithm">Shunting-yard algorithm</a> to build the tree in a single pass.</p><h4>4. Generate SQL</h4><p>We can now recursively generate the SQL.</p><p>Each node class has a method generateSQL. This method calls the same method of its child nodes, and then combines the SQL as necessary.</p><p>To avoid <a href="https://en.wikipedia.org/wiki/SQL_injection">SQL injection</a>, we build the query with placeholders and a separate array of parameters.</p><p>Consider again our example: dinner (from:conrad or from:rahul)</p><p>The <em>From</em> node class is a subclass of the <em>Contact</em> node class. The <em>Contact</em> node class contains the implementation details:</p><pre>class Contact extends Operand {<br>  generateSQL() {<br>    sql = &quot;SELECT thread_ids FROM messages_search WHERE ? MATCH ?&quot;<br>    params = [this.key, this.left]<br>    return {sql, params}<br>  }<br>}</pre><p>Meanwhile, the <em>Or</em> node combines the SQL from its children with UNION:</p><pre>class Or extends Operator {<br>  generateSQL() {<br>    left = this.left.generateSQL()<br>    right = this.right.generateSQL()<br>    sql = left.sql + &quot; UNION &quot; + right.sql<br>    params = left.params.concat(right.params)<br>    return {sql, params}<br>  }<br>}</pre><p>After the recursion is done, the final SQL looks like this:</p><figure><img alt="" src="https://cdn-images-1.medium.com/max/1024/1*G3H5nnODP-knl-kbDEZW7A.png" /></figure><pre>SELECT *<br>FROM threads<br>WHERE thread_id IN (<br>    SELECT DISTINCT thread_id<br>    FROM message_search<br>    WHERE message_search MATCH ?<br>    <br>    INTERSECT<br>    <br>    SELECT thread_id<br>    FROM (<br>      SELECT DISTINCT thread_id<br>      FROM message_search<br>      WHERE &quot;from&quot; MATCH ?<br>      <br>      UNION<br>      <br>      SELECT DISTINCT thread_id<br>      FROM message_search<br>      WHERE &quot;from&quot; MATCH ?<br>    )<br>)</pre><pre>[&quot;dinner&quot;, &quot;conrad&quot;, &quot;rahul&quot;]</pre><p>Voilà! This SQL query is now ready for execution in WebSQL.</p><h3>Advantages</h3><h4>Autocompletion</h4><p>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?</p><p>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 <em>Contact</em> node:</p><pre>class Contact extends Operand {<br>  generateAutoComplete() {<br>    return this.autoCompleteTrie.search(this.left)<br>  }<br>}</pre><h4>Syntax Highlighting</h4><p>By storing the node list in the UI, we can very easily highlight syntax:</p><figure><img alt="" src="https://cdn-images-1.medium.com/max/1024/0*UMjavxLxzX8DIz3x." /><figcaption>Pretty cool.</figcaption></figure><p>As we saw it was extremely easy to add autocompletion and syntax highlighting using the query compiler, which makes this architecture <em>Flexible</em>.</p><h3>Conclusion</h3><p>We built a search architecture that is <em>Local, Composable, </em>and<em> Flexible</em>. This architecture makes the search <em>Fast, Powerful, Responsive, </em>and<em> Available.</em></p><p>How have you architected search for your web app? Please leave a comment below, and please do share if you found this interesting!</p><p>— BK (Bhavesh Kakadiya), Lead Engineer, <a href="https://superhuman.com/?utm_source=medium&amp;utm_medium=blog&amp;utm_campaign=delightful-search">Superhuman</a></p><p><em>At Superhuman we’re rebuilding the email experience for web &amp; mobile. Think vim / Sublime for email: blazingly fast and visually gorgeous.</em></p><p><em>Thank you to </em><a href="https://twitter.com/kosamari"><em>Mariko Kosaka</em></a><em>, </em><a href="https://www.linkedin.com/in/ravasthi/"><em>Richa Avasthi</em></a><em> for reviewing drafts of this post.</em></p><p><em>If you love solving interesting problems in elegant ways — join us! </em><a href="https://superhuman.com/jobs?utm_source=medium&amp;utm_medium=blog&amp;utm_campaign=delightful-search"><em>Learn more</em></a><em> or </em><a href="/service/mailto:bhavesh@superhuman.com"><em>email me</em></a><em>.</em></p><img src="https://medium.com/_/stat?event=post.clientViewed&referrerSource=full_rss&postId=d3fa2e3ef3b6" width="1" height="1" alt=""><hr><p><a href="https://medium.com/superhuman-co/delightful-search-more-than-meets-the-eye-d3fa2e3ef3b6">Delightful search: more than meets the eye</a> was originally published in <a href="https://medium.com/superhuman-co">Superhuman</a> on Medium, where people are continuing the conversation by highlighting and responding to this story.</p>]]></content:encoded>
        </item>
    </channel>
</rss>