Efficient pattern matching LIKE queries with SUFFIXES()<\/h2>\n
Pattern matching is a widely used functionality in SQL queries, and is typically achieved using the LIKE operator. Especially, efficient wildcard matching is very important. LIKE \u2018foo%\u2019 can be implemented efficiently with a standard index, but not LIKE \u2018%foo%\u2019. Such pattern matching with leading wildcard is vital, for every application that has a search box to match partial words or to smart-suggest matching text. For example,<\/p>\n
- \n
- A travel booking site, that wants to pop-up matching airports as the user starts to enter few letters of the airport name.<\/li>\n
- A user finding all e-mails with a specific word or partial word in the subject.<\/li>\n
- Finding all topics of a forum or blog posts with specific keywords in the title.<\/li>\n<\/ul>\n
In Couchbase Server 4.5.1, N1QL addresses this problem by adding a new string function SUFFIXES(), and combining that with the Array Indexing functionality introduced in Couchbase Server 4.5. Together, it brings magnitude difference to performance of LIKE queries with leading wildcards such as LIKE “%foo%”. Core functionality of SUFFIXES() is very simple, basically it produces an array of all possible suffix substrings of a given string. For example,<\/p>\n
SUFFIXES(\"N1QL\") = [ \"N1QL\", \"1QL\", \"QL\", \"L\" ]<\/code><\/pre>\nFollowing picture depicts a\u00a0unique technique to combine
SUFFIXES()<\/code> function with Array Indexing to magically boostLIKE<\/code> query performance.<\/p>\n![\"\"](\"https:\/\/www.couchbase.com\/blog\/wp-content\/uploads\/2016\/10\/suffixes1.png\")
<\/p>\n- \n
- Step1 (in blue) shows the array of suffix substrings generated by
SUFFIXES()<\/code> fordoc1.title<\/code><\/li>\n- Step2 (in yellow) shows the Array Index created with the suffix substrings generated in step1. Note that the index-entry for
\"wood\"<\/code> points todoc1<\/code> anddoc4<\/code>, as that is one of the suffix substrings of titles of both the documents. Similarly,\"ood\"<\/code> points todoc1<\/code>,doc4<\/code>, anddoc8<\/code>.<\/li>\n- Step3 (in green) runs a query equivalent to
SELECT title FROM bucket WHERE title LIKE \"%wood%\"<\/code>. The LIKE predicate is transformed to use the Array Index using the ANY construct. See documentation for more details on using array indexing.\n- \n
- Note that, the leading wildcard is removed in the new
LIKE \"wood%\"<\/code> predicate.<\/li>\n- This is accurate transformation, because the array index lookup for
\"wood\"<\/code> points to all documents whose title has\u00a0trailing substring\"wood\"<\/code><\/li>\n<\/ul>\n<\/li>\n- In Step4, N1QL looks-up in the Array Index to find all documents matching
\"wood%\"<\/code>. That returns{doc1, doc3, doc4}<\/code>, because\n- \n
- the index lookup produces a span, which gets documents from
\"wood\"<\/code> to\"wooe\"<\/code><\/li>\ndoc1<\/code> anddoc4<\/code> are matched because of index entry “wood” that is generated by the SUFFIXES() when creating the array index.<\/li>\ndoc3<\/code> is matched because of its corresponding index-entry for\"woodland\"<\/code><\/li>\n<\/ul>\n<\/li>\n- Finally, in step5, N1QL returns the query results.<\/li>\n<\/ol>\n
Let’s see a working example with the
travel-sample<\/code> documents, which showed a 12x boost in performance for the query.<\/p>\n- \n
- Assume a document with a string field whose value is few words of text or a phrase. For example, title of a landmark, address of a place, name of restaurant, \u00a0full name of a person\/place etc., For this explanation, we consider
title<\/code> oflandmark<\/code> documents intravel-sample<\/code>.<\/li>\n- Create secondary index on
title<\/code> field usingSUFFIXES()<\/code> as:\nCREATE INDEX idx_title_suffix \r\n ON `travel-sample`(DISTINCT ARRAY s FOR s IN SUFFIXES(title) END)\r\n WHERE type = \"landmark\";<\/code><\/pre>\nSUFFIXES(title)<\/code> generates all possible suffix substrings oftitle<\/code>, and the index will have entries for each of those substrings, all referencing to corresponding documents.<\/li>\n- Now consider following query, which finds all docs with substring
\"land\"<\/code> intitle<\/code>.\u00a0This query produces following plan, and runs in roughly 120ms in my laptop. You can clearly see, it fetches alllandmark<\/code> documents, and then applies theLIKE \"%land%\"<\/code>predicate to find all matching documents.\nEXPLAIN SELECT * FROM `travel-sample` USE INDEX(def_type) WHERE type = \"landmark\" AND title LIKE \"%land%\";\r\n[\r\n {\r\n \"plan\": {\r\n \"#operator\": \"Sequence\",\r\n \"~children\": [\r\n {\r\n \"#operator\": \"IndexScan\",\r\n \"index\": \"def_type\",\r\n \"index_id\": \"e23b6a21e21f6f2\",\r\n \"keyspace\": \"travel-sample\",\r\n \"namespace\": \"default\",\r\n \"spans\": [\r\n {\r\n \"Range\": {\r\n \"High\": [\r\n \"\"landmark\"\"\r\n ],\r\n \"Inclusion\": 3,\r\n \"Low\": [\r\n \"\"landmark\"\"\r\n ]\r\n }\r\n }\r\n ],\r\n \"using\": \"gsi\"\r\n },\r\n {\r\n \"#operator\": \"Fetch\",\r\n \"keyspace\": \"travel-sample\",\r\n \"namespace\": \"default\"\r\n },\r\n {\r\n \"#operator\": \"Parallel\",\r\n \"~child\": {\r\n \"#operator\": \"Sequence\",\r\n \"~children\": [\r\n {\r\n \"#operator\": \"Filter\",\r\n \"condition\": \"(((`travel-sample`.`type`) = \"landmark\") and ((`travel-sample`.`title`) like \"%land%\"))\"\r\n }\r\n ]\r\n }<\/code><\/pre>\n<\/li>\n- In Couchbase 4.5.1, this query can be rewritten to leverage the array index
idx_title_suffix<\/code> created in (2) above.\nEXPLAIN SELECT title FROM `travel-sample` USE INDEX(idx_title_suffix) WHERE type = \"landmark\" AND \r\nANY s IN SUFFIXES(title) SATISFIES s LIKE \"land%\" END;\r\n[\r\n {\r\n \"plan\": {\r\n \"#operator\": \"Sequence\",\r\n \"~children\": [\r\n {\r\n \"#operator\": \"DistinctScan\",\r\n \"scan\": {\r\n \"#operator\": \"IndexScan\",\r\n \"index\": \"idx_title_suffix\",\r\n \"index_id\": \"75b20d4b253214d1\",\r\n \"keyspace\": \"travel-sample\",\r\n \"namespace\": \"default\",\r\n \"spans\": [\r\n {\r\n \"Range\": {\r\n \"High\": [\r\n \"\"lane\"\"\r\n ],\r\n \"Inclusion\": 1,\r\n \"Low\": [\r\n \"\"land\"\"\r\n ]\r\n }\r\n }\r\n ],\r\n \"using\": \"gsi\"\r\n }\r\n },\r\n {\r\n \"#operator\": \"Fetch\",\r\n \"keyspace\": \"travel-sample\",\r\n \"namespace\": \"default\"\r\n },\r\n {\r\n \"#operator\": \"Parallel\",\r\n \"~child\": {\r\n \"#operator\": \"Sequence\",\r\n \"~children\": [\r\n {\r\n \"#operator\": \"Filter\",\r\n \"condition\": \"(((`travel-sample`.`type`) = \"landmark\") and any `s` in suffixes((`travel-sample`.`title`)) satisfies (`s` like \"land%\") end)\"\r\n },\r\n<\/code><\/pre>\n<\/li>\n<\/ol>\nNote that:<\/p>\n
- \n
- The new query in (4) uses
LIKE \u201cland%\u201d<\/code>, instead ofLIKE \u201c%land%\u201d<\/code>. The former predicate with no leading wildcard'%'<\/code> produces much more efficient index lookup than the later one which can\u2019t pushdown the predicate to index.<\/li>\n- the array index
idx_title_suffix<\/code> is created with all possible suffix substrings oftitle<\/code>, and hence lookup for any suffix substring of title can find successful match.<\/li>\n- in the above 4.5.1 query plan in (4), N1QL pushes down the LIKE predicate to the index lookup, and avoids additional pattern-matching string processing. This query ran in 18ms.<\/li>\n
- Infact, with following covering Array Index, the query ran in 10ms, which is 12x faster.<\/li>\n<\/ul>\n
CREATE INDEX idx_title_suffix_cover\r\n ON `travel-sample`(DISTINCT ARRAY s FOR s IN SUFFIXES(title) END, title)\r\n WHERE type = \"landmark\";<\/code><\/pre>\nSee this blog<\/a> for details on a real-world application of this feature.<\/p>\n
Enhancements to UPDATE to work with Nested Arrays<\/h2>\n
Enterprise applications often have complex data, and need to model JSON documents with multiple levels of nested objects and arrays. N1QL supports complex expressions and language constructs to navigate and query such documents with nested arrays. N1QL also supports Array Indexing<\/a>, with which secondary indexes can be created on array elements, and subsequently queried.
\nIn Couchbase Server 4.5.1, theUPDATE<\/code> statement syntax is improved to navigate nested arrays in documents, and update specific fields in nested array elements. TheFOR<\/code>-clause of theUPDATE<\/code> statement is enhanced to evaluate functions and expressions, and the new syntax supports multiple nestedFOR<\/code> expressions to access and update fields in nested arrays.
\nConsider following document with nested array like:<\/p>\n{ \r\n items: [\r\n {\r\n subitems: [\r\n {\r\n name: \"N1QL\"\r\n },\r\n {\r\n name: \"GSI\"\r\n }\r\n ] \r\n }\r\n ],\r\n docType: \"couchbase\" \r\n}<\/code><\/pre>\nThe new
UPDATE<\/code> syntax in 4.5.1 can be used in different ways to access & update nested arrays:<\/p>\n- \n
- \n
UPDATE default SET s.newField = 'newValue' \r\nFOR s IN ARRAY_FLATTEN(items[*].subitems, 1) END; <\/code><\/pre>\n<\/li>\n- \n
UPDATE default \r\nSET s.newField = 'newValue' \r\nFOR s IN ARRAY_FLATTEN(ARRAY i.subitems FOR i IN items END, 1) END; <\/code><\/pre>\n<\/li>\n- \n
UPDATE default \r\nSET i.subitems = ( ARRAY OBJECT_ADD(s, 'newField', 'newValue') \r\n FOR s IN i.subitems END ) FOR i IN items END; <\/code><\/pre>\n<\/li>\n<\/ul>\nNote that:<\/p>\n
- \n
- The
SET<\/code>-clause evaluates functions such asOBJECT_ADD()<\/code> andARRAY_FLATTEN()<\/code><\/li>\nFOR<\/code> constructs can be used in nested fashion with expressions to process array elements at different nest-levels.<\/li>\n<\/ul>\nFor a working example, consider the sample bucket
travel-sample<\/code> \u00a0shipped with 4.5.1.<\/p>\n- \n
- First, let\u2019s add a nested array of special flights to the array schedule in
travel-sample<\/code> bucket, for some documents.\nUPDATE `travel-sample` \r\nSET schedule[0] = {\"day\" : 7, \"special_flights\" : \r\n [ {\"flight\" : \"AI444\", \"utc\" : \"4:44:44\"}, \r\n {\"flight\" : \"AI333\", \"utc\" : \"3:33:33\"} \r\n ] } \r\nWHERE type = \"route\" AND destinationairport = \"CDG\" AND sourceairport = \"TLV\";<\/code><\/pre>\n<\/li>\n- following UPDATE statement \u00a0adds a 3rd field to each special flight:\n
UPDATE `travel-sample`\r\nSET i.special_flights = ( ARRAY OBJECT_ADD(s, 'newField', 'newValue' ) \r\n FOR s IN i.special_flights END ) \r\n FOR i IN schedule END\r\nWHERE type = \"route\" AND destinationairport = \"CDG\" AND sourceairport = \"TLV\";\r\n\r\n\r\nSELECT schedule[0] from `travel-sample` \r\nWHERE type = \"route\" AND destinationairport = \"CDG\" AND sourceairport = \"TLV\" LIMIT 1;\r\n[\r\n {\r\n \"$1\": {\r\n \"day\": 7,\r\n \"special_flights\": [\r\n {\r\n \"flight\": \"AI444\",\r\n \"newField\": \"newValue\",\r\n \"utc\": \"4:44:44\"\r\n },\r\n {\r\n \"flight\": \"AI333\",\r\n \"newField\": \"newValue\",\r\n \"utc\": \"3:33:33\"\r\n }\r\n ]\r\n }\r\n }\r\n]<\/code><\/pre>\n<\/li>\n<\/ol>\nThere are many more important N1QL enhanements and Performance features in Couchbase Server 4.5.1 release. Will write about them in my next blog\/part2<\/a>.<\/p>\n
- following UPDATE statement \u00a0adds a 3rd field to each special flight:\n
- \n
- the array index
- Create secondary index on
- This is accurate transformation, because the array index lookup for
- Step2 (in yellow) shows the Array Index created with the suffix substrings generated in step1. Note that the index-entry for
- Step1 (in blue) shows the array of suffix substrings generated by