More Than LIKE: Efficient JSON Searching With N1QL

Enterprise applications require both exact search (equality, range predicate) and pattern search (LIKE or text search). The B-Tree based indexes in databases help perform an exact search in milliseconds. Pattern search is a whole different problem. Predicates of patterns (name LIKE "%turin%") will scan the whole index — unsuitable for application use. Recognizing the need for speed, we've introduced a TOKENS() functions in Couchbase 4.6 which retuns an array of tokens from each field or document. We then index the array using the array indexing in Couchbase N1QL. This transforms the pattern search problem to a simple equality look up, improves the performance by orders of magnitude.

Introduction

Whether you’re booking a hotel in Turin or Timbuktu, Milan or Malibu, you need to search based on various criteria: location, dates, rooms, number of people, their age and more. The numerical requirements (number of rooms, number of people in the party), date ranges (check-in and checkout dates) are exact predicates. The target place to visit could be a search within a city name, region name, nearby places, or interesting landmarks.

Here is the problem.  

• How do you make this query run really, really quickly?  

• How do you get thousands of users searching and buying your product and service concurrently?

Search is a broad term. So, we divide searches into distinct types.

1. Exact search with one or more predicates.

2. Pattern search to find a word or a pattern within a larger string.

3. Fuzzy search — text search with a lot of text data.

Of course, all of these search operations have to come back with results in milliseconds and not seconds.

In Couchbase:

• For exact searches, you can use B-tree- or skip-list-based global secondary indexes with a simple or composite index to achieve your goals.

• For full-text search, which requires heavy text processing — stemming, scoring, and more — you can use Couchbase full-text search (FTS).

The hotel search problem doesn’t fall nicely into either category completely. Exact predicates require exact index; search predicates require FTS index. Using only index scans, you’ll get too much data, and you’d need filter further. On the other hand, if you search using full-text index, you’ll need to filter further for dates, rooms, etc. This second level of filtering will slow things down significantly.

Real world problems like you saw above are not always clean cut. You want the exact search for numerical and date range; you want the string search with smaller data like city, neighborhood, region.

Here is the problem. How do you make this query run really, really quickly? How do you get thousands of users searching and buying your product and service concurrently?

Let’s use sample Hotel documents in the Couchbase travel-sample data set to explore the use case.

1

select hotel, meta().id as dockey 

2

from `travel-sample` hotel 

3

where hotel.type = "hotel"

4

limit 1;

1

[

2

  {

3

     "dockey": "hotel_10025",

4

     "hotel": {

5

      "address": "Capstone Road, ME7 3JE",

6

      "alias": null,

7

      "checkin": null,

8

      "checkout": null,

9

      "city": "Medway",

10

      "country": "United Kingdom",

11

      "description": "40 bed summer hostel about 3 miles from Gillingham, housed in a distinctive converted Oast House in a semi-rural setting.",

Now, let’s see some common questions from your application and how these questions can be translated to queries.

1. Find all the hotel information for "Medway Youth Hostel"

* This is an exact search of the predicate (hotel.name = "Medway Youth Hostel")

1

Query:

2

​

3

SELECT hotel 

4

FROM `travel-sample` hotel

5

WHERE hotel.type = "hotel"

6

AND hotel.name = "Medway Youth Hostel";

7

​

8

Index:

9

​

10

CREATE INDEX idx_hotel_typename 

11

ON `travel-sample`(name) WHERE type = "hotel";

2. Find all the hotels in "Medway", "United Kingdom"

* This is an exact search with the predicate: ( hotel.country = “United Kingdom”
AND hotel.city = “Medway” )

1

Query:

2

​

3

SELECT hotel 

4

FROM `travel-sample` hotel

5

WHERE hotel.type = "hotel" 

6

AND hotel.country = "United Kingdom"

7

AND hotel.city = "Medway"

8

​

9

Index:

10

​

11

CREATE INDEX idx_hotel_typecountryname 

3. Find all the hotels liked (in the field public_field) by the a person with a name (first or last) Vallie

    * public_likes is an array of field. It has names of the peopel who liked the hotel.

* This is a pattern search. We're looking for a first name or last name Vallie.

1

      "public_likes": [

2

        "Julius Tromp I",

3

        "Corrine Hilll",

4

        "Jaeden McKenzie",

5

        "Vallie Ryan",

6

        "Brian Kilback",

7

        "Lilian McLaughlin",

8

        "Ms. Moses Feeney",

9

        "Elnora Trantow"

10

      ]

So we use the array predicate to search through array elements. To make this search faster, we create an array index on public_likes. This index scan will still fetch all the elements from the index and apply the LIKE "%vallie%" on top of it.

1

Query:

2

​

3

SELECT hotel 

4

FROM `travel-sample` hotel

5

WHERE hotel.type = "hotel"

6

AND ANY p IN hotel.public_likes 

7

        SATISFIES LOWER(p) LIKE "%vallie%"

8

    END

9

​

10

Index:

11

​

4. Find all the hotels that mention architecture anywhere in the document. This anywhere -- could be in keyname (attribute name), any value — in name, description, reviews, etc.

This has a pattern search. Search for architecture anywhere in the document is a pattern search.Index: This query can use a primary index.

1

SELECT COUNT(1) totalcount FROM `travel-sample` hotel

2

WHERE ANY v WITHIN OBJECT_PAIRS(hotel) 

3

          SATISFIES LOWER(v)  LIKE "%architecture%"

4

      END

5

{

6

    "requestID": "426b993e-a214-4e5f-824e-aef2ebfd3262",

7

    "signature": {

8

        "$1": "number"

9

    },

10

    "results": [

11

        {

While this query works, it takes 12.13 seconds to find the 41 documents which have the word architecture somewhere in the document. Too slow and too expensive.

Here is where the TOKENS come into the picture. TOKENS() function takes a JSON document or an expression, analyzes all of name value pairs, arrays, objects and returns an array of values of basic types: numeric, strings, boolean, null.

1

SELECT TOKENS(hotel)

2

FROM `travel-sample` hotel

3

WHERE hotel.type = 'hotel' 

4

LIMIT 1;

5

​

6

[

7

  {

8

    "$1": [

9

      null,

10

      false,

11

      true,

Once we get this array, we can use the array indexing, to index the result of TOKENS and query them:

1

CREATE INDEX idx_travel_tokens ON `travel-sample`

2

(DISTINCT ARRAY s for s IN TOKENS(`travel-sample`, {"case":"lower", "names": true}) END) 

3

​

4

select count(1) FROM `travel-sample` h 

5

WHERE ANY s IN tokens(h, {"case":"lower", "names": true}) SATISFIES s = 'architecture' END;

6

{

7

    "requestID": "dd6cfb24-ae5f-4667-a332-fc21ec48f808",

8

    "signature": {

9

        "$1": "number"

10

    },

11

    "results": [

Let’s look at the query plan. It chose the tokens right index and more importantly, the predicates were pushed correctly into index scans (reported here as spans). The appropriate index is selected and the predicate looking for architecture is pushed down to index scan.

1

      "~children": [

2

        {

3

          "#operator": "DistinctScan",

4

          "scan": {

5

            "#operator": "IndexScan",

6

            "index": "idx_travel_tokens",

7

            "index_id": "9f370cd078ebd2eb",

8

            "keyspace": "travel-sample",

9

            "namespace": "default",

10

            "spans": [

11

              {

1. Finally, let’s put all of this together to answer this question: Find all the hotels in United Kingdom which have vacancies and with a website.

• We can check for (country = ‘United Kingdom’ and vacancy = true) easily via composite index.

• Having a “website” needs to be defined well.

• When you get information from hotels, unless you go through a ETL process to save the information in an exact field and format, you’d have this information anywhere in the hotel document.

1
Example:
2
"url": "http://www.yha.org.uk",
3
"Website": "http://www.yha.org.uk”
4
“Http”: "www.yha.org.uk"
5
“Http address”: "www.yha.org.uk"
6
“Web” : "Our website: http://www.yha.org.uk "
7
“Contact” : 
8
     “Phone” : "+44 482 492 292",
9
     “Web” : "http://www.yha.org.uk",
10
     “Mail” : "help@yha.org.uk"
11
   }

Problem: You’d need to search in every field name, every object, every array.

1

Query:

2

EXPLAIN 

3

SELECT * 

4

FROM `travel-sample` hotel 

5

WHERE country = "United Kingdom"

6

AND vacancy = true

7

AND ANY v IN TOKENS(hotel, {"case":"lower", "name":true})

8

        SATISFIES v = "http"

9

    END

10

AND type = "hotel"

11

​

In this case, we push down all of the predicates to the index scan. 

The query runs in about 233 milliseconds!

1

SELECT * 

2

FROM `travel-sample` hotel 

3

WHERE country = "United Kingdom" 

4

AND vacancy = true 

5

AND ANY v IN TOKENS(hotel, {"case":"lower", "name":true}) SATISFIES v = "http" 

6

    END 

7

AND type = "hotel";

8

​

9

Results (partially shows for brevity):

10

​

11

{

TOKENS() Function

This function is explained in detail in Couchbase documentation. The important thing to note is that first expression passed into token can be anything: constant literal, simple JSON value, JSON key name or the whole document itself.

TOKENS (Expression, Options)

You can invoke TOKENS() simply with the expressions or with the option. The function always returns an array of tokens it extracted for the given (implied) options.

TOKENS(address)  

This returns an array of values including the attribute (key) names. It retrieves the data in their basic types and returns 

Options can take the following options. Each invocation of TOKENS() can choose one or more of the options, passed in as JSON.

{"name": true}: Valid values are true or false. Default is true.

{"case":"lower"}: Valid values are "upper" and "lower".  Default is neither — return the case in the data.

{"specials": true}:  Preserves strings with special characters such as email addresses, URLs, and hyphenated phone numbers. The default is false. 

Let's use all of the options on TOKENS() to see what it produces.

1

Query:

2

​

3

SELECT 

4

TOKENS ({"info":"Name is keshav email is keshav@couchbase.com Blog is http://planetnosql.com twitter handle is @rkeshavmurthy"}, 

5

{"specials":true, "names":true, "case":"lower"}) AS words

6

​

7

Result:

8

​

9

[

10

  {

11

    "words": [

With names set to true, you'll get the field name, in this case info.

With specials set to true, you'll get delimited words as well as special works like keshav@couchbase.com or @rkeshavmurthy as a single word to index. 

With case set to lower, all of the results will be in the lower case

Let's look at an example usage on the travel-sample data.

1

SELECT TOKENS(url) AS defaulttoken, 

2

       TOKENS(url, {"specials":true, "case":"UPPER"}) AS specialtoken

3

FROM `travel-sample` h WHERE h.type = 'hotel' 

4

LIMIT 1;

5

​

6

[

7

  {

8

    "defaulttoken": [

9

      "uk",

10

      "www",

11

      "http",

In this case, TOKENS() converted all of the URL data into UPPER case and added the full URL in addition to delimited words.

Use {"case":"lower"} or  {"case":"upper"} to have case insensitive search. Index creation and querying can use this and other parameters in combination. As you saw in the examples, these parameters should be passed within the query predicates as well. The parameters and values have to match exactly for N1QL to pick up and use the index correctly.

Here is an example of how you can create the index and use it your applicaiton.

1

Index definition:

2

​

3

CREATE INDEX idx_url_upper_special on `travel-sample`(

4

  DISTINCT ARRAY v for v in 

5

       tokens(url, {"specials":true, "case":"UPPER"}) 

6

  END ) where type = 'hotel' ;

7

​

8

Query:

9

​

10

SELECT name, address, url

11

FROM `travel-sample` h

Summary

Couchbase 4.6 has introduced a new way to split the JSON document into simpler values using TOKENS(). Using the flexible array indexing in Couchbase, you can now create secondary indexes for scalar and array values. This is a high-performance alternative to the LIKE predicate. Its performance is so much more likable.

References

1. Couchbase  : http://www.couchbase.com

2. N1QL:  http://query.couchbase.com

3. Couchbase Full Text Search:  http://developer.couchbase.com/documentation/server/current/fts/full-text-intro.html

4. SPLIT and CONQUER: https://dzone.com/articles/split-and-conquer-efficient-string-search-with-n1q

5. A Couchbase Index Technique for LIKE Predicates With Wildcard:  https://dzone.com/articles/a-couchbase-index-technique-for-like-predicates-wi