A Couchbase Index Technique for LIKE Predicates With Wildcard

I have a query below where I want to find all documents in the travel-sample bucket having the airport name containing the string “Washington.”

SELECT airportname from `travel-sample`
where
    airportname LIKE "%Washington%"
AND type = "airport"

This is a classic problem with most of the RDBMS systems where these systems can't use the index when a LIKE predicate has a leading wildcard i.e. leading %. Elsewhere in this article, I will refer to the query above as the "slow query." I am pleased to tell you that help is on the way with Couchbase release 4.5.1, where this problem can be solved with a combination of the new SUFFIXES() function and Array Index. 

Note: To follow along with the examples in this article, please refer to the setup instructions as given here to install the travel-sample Couchbase bucket.

SUFFIXES() is a N1QL function that generates all suffixes of an input string. For example, the N1QL statement below:

select SUFFIXES("Baltimore Washington Intl") 

That returns an array of suffixes:

[
      "Baltimore Washington Intl",
      "altimore Washington Intl",
      "ltimore Washington Intl",
      "timore Washington Intl",
      "imore Washington Intl",
      "more Washington Intl",
      "ore Washington Intl",
      "re Washington Intl",
      "e Washington Intl",
      " Washington Intl",
      "Washington Intl",
      "ashington Intl",
      "shington Intl",
      "hington Intl",
      "ington Intl",
      "ngton Intl",
      "gton Intl",
      "ton Intl",
      "on Intl",
      "n Intl",
      " Intl",
      "Intl",
      "ntl",
      "tl",
      "l"
    ]

By applying the SUFFIXES() function on the airportname attribute of the documents of type 'airport,' Couchbase generates an array of suffixes for each document. You can then create an array index on the suffixes arrays and rewrite the query to leverage such index. Here is an example:

• Create an array index on the suffixes of the airportname attribute :

create index suffixes_airport_name on `travel-sample`(
       DISTINCT ARRAY array_element FOR array_element IN SUFFIXES(LOWER(airportname)) END)
       WHERE type = "airport";

• The "slow query" can be rewritten to use the suffixes_airport_name index and returns all the documents containing the airportname suffix, starting with 'washington%.' It is worth noting that in this re-written query the LIKE predicate no longer needs the leading % wildcard because the matching criterion is on the suffixes.

select airportname from `travel-sample`
where
    ANY array_element IN SUFFIXES(LOWER(airportname)) SATISFIES array_element LIKE 'washington%' END
and  type="airport";

the query returns
[
  {
    "airportname": "Ronald Reagan Washington Natl"
  },
  {
    "airportname": "Washington Dulles Intl"
  },
  {
    "airportname": "Baltimore Washington Intl"
  },
  {
    "airportname": "Washington Union Station"
  }
]

The elapsed time for this rewritten query is roughly 25ms when executed on my small VM cluster, and it is 10 times faster compared to the elapsed time of the original "slow query." I am including a portion of the explain plan to confirm that the rewritten query uses the array index. 

[
  {
        ...
            {
              "#operator": "DistinctScan",
              "scan": {
                "#operator": "IndexScan",
                "index": "suffixes_airport_name",
                "index_id": "6fc9785d59a93892",
                "keyspace": "travel-sample",
                "namespace": "default",
                "spans": [
                  {
                    "Range": {
                      "High": [
                        "\"washingtoo\""
                      ],
                      "Inclusion": 1,
                      "Low": [
                        "\"washington\""
                      ]
                    }
                  }
                ],
                "using": "gsi"
              }
            }
        ......
]

A common application of such a query is when an end user enters a partial searching string in a UI search field, e.g. searching for an airport name. After the end user has entered a few characters, the logic behind the search field issues the query and displays the matches returned as a drop-down picklist (much like what you see when you enter search terms in Google).  

Readers should be aware that the longer the input string, the longer the list of suffixes and, therefore, the index on suffixes can be large.  I recommend using this technique only on short attributes, which belong to small Reference Data collections, such as Airport, Hotel, Product Catalog, etc. 

If your documents have multi-value attribute(s) such as SKILLS, TAGS as shown in the sample document below, I recommend using the SPLIT() function instead of SUFFIXES().

candidate: {
        name: "John Doe",
        skills: "JAVA,C,NodeJS,SQL",
}

Below is a simple example of SPLIT(). When it is invoked with an input string of comma-separated words, it will return an array of words. 

SELECT SPLIT("JAVA,C,NodeJS,SQL", ",")

The select returns:

[
  {
    "$1": [
      "JAVA",
      "C",
      "NodeJS",
      "SQL"
    ]
  }
]

By creating an array index on these arrays of words, your application should be able to support word search. You should try this out yourself to see how it works.

If you have documents with long text attributes such as "Description", TOKENS() function is more suitable for parsing text paragraphs into individual words. The TOKENS() function is not available in our current GA release but will be soon.