{"id":14562,"date":"2023-06-23T13:15:52","date_gmt":"2023-06-23T20:15:52","guid":{"rendered":"https:\/\/www.couchbase.com\/blog\/?p=14562"},"modified":"2024-03-01T09:01:33","modified_gmt":"2024-03-01T17:01:33","slug":"recursive-query-processing-in-sql-n1ql","status":"publish","type":"post","link":"https:\/\/www.couchbase.com\/blog\/recursive-query-processing-in-sql-n1ql\/","title":{"rendered":"Recursive Query Processing in SQL++ (N1QL)"},"content":{"rendered":"

It is extremely likely that you have come across issues with <\/span>hierarchical lookups or graph traversal<\/b> in your application as a developer who handles real-world use cases. And, for obvious reasons, you prefer solving them at the <\/span>database layer and not at the client-side<\/b>.<\/span><\/p>\n

What are hierarchical lookups?<\/span><\/h2>\n

Hierarchical lookup refers to the process of searching and retrieving data from a hierarchical structure, such as a <\/span>tree or a parent-child relationship<\/b>. It involves navigating through the levels or layers of the hierarchy to locate specific data elements or related information, for example, organizational charts, file systems, and category trees.<\/span><\/p>\n

Graphs are basically trees that may have cycles, so additionally, we could also cover use cases like path finding, etc provided we have additional configurations to deal with cycles.<\/span><\/p>\n

\"hierachical<\/p>\n

Consider an example using an employee collection with a hierarchical structure. Employees are organized in a manager-subordinate relationship. We’ll perform operations on this employee hierarchy using Couchbase and JavaScript UDFs to demonstrate the solution.<\/span><\/p>\n

Going from the <\/span>Employee Collection <\/span><\/i>we can retrieve:<\/span><\/p>\n

i) generic employee-level:<\/span><\/p>\n

\"\"<\/p>\n

ii) hierarchy for each employee:<\/span><\/p>\n

\"\"<\/p>\n

What this blog covers<\/span><\/h2>\n

You really like the <\/span>flexibility<\/b> of NoSQL databases, and your underlying data model is <\/span>JSON, <\/b>which is why you have chosen Couchbase for your database needs (great choice, btw :-) ).<\/span><\/p>\n

Now that you have Couchbase as your database, you want to solve the above mentioned problem. After doing some research in the <\/span>SQL++<\/span><\/a> Language Reference docs<\/span> you have come to the conclusion that there is no <\/span>Statement <\/span><\/i>or <\/span>Function <\/span><\/i>support in SQL++ to solve our problem, like the <\/span>graphLookup<\/span><\/a> API in MongoDB or <\/span>recursive CTE<\/span><\/a> in SQL databases.<\/span><\/p>\n

But <\/span>with existing infrastructure, users can emulate recursive CTE using JavaScript UDFs. <\/b>The following sections will demonstrate just how to do that and more!<\/span><\/p>\n

Solution to recursive queries<\/span><\/h2>\n

To implement this solution, we need to create a JavaScript UDF that utilizes a breadth-first search algorithm to traverse the employee hierarchy. The UDF takes an <\/span>anchor query<\/b>, a <\/span>recursive query<\/b>, and <\/span>configuration options as parameters<\/b>. The anchor query retrieves the initial set of employees, while the recursive query references the results of the previous iteration using the <\/span>$1<\/span><\/i> parameter. Configuration options allow customization, including early exit criteria, arguments for inner queries, cycle detection, explain mode for query planning, and logging options.<\/span><\/p>\n

How to use inner queries<\/h3>\n

The anchor query gets the <\/span>root level documents<\/b> from the target collection.<\/span><\/p>\n

The recursive query can use a <\/span>JOIN <\/span><\/i>clause with one side as <\/span>$1<\/span><\/i> and the other as the target collection, to exploit the parent-child relationship and perform the traversal from one level to another.<\/span><\/p>\n

In our function, <\/span>$1<\/span><\/i> does what the CTE alias does in recursive CTE.<\/span><\/p>\n

To better understand how we use SQL++ (N1QL) within JavaScript UDFs, take a look at<\/span> From N1QL to JavaScript and back<\/span><\/a>.<\/span><\/p>\n

Now let’s look at the process step by step. First of all, <\/span>does recursive query processing really need to be a recursive function?<\/b><\/p>\n

No, this would be a bad choice considering time-complexity (the same functionality in recursive might be exponential, but linear in an iterative approach) and all the other issues like frames, etc., that come along with recursion. If interested, check out this <\/span>article<\/span><\/a> on converting tail recursion functions to iterative. Also, JS UDFs have a preset <\/span>max recursion depth of 128;<\/b> this is not preferable for what we are trying to do. <\/span><\/p>\n

To put it simply, any iterative task does the following:<\/span>
\n<\/span><\/p>\n

\"\"<\/p>\n

We would like to acknowledge this <\/span>article<\/span><\/a> for its approach.<\/span><\/p>\n

Points to ponder<\/span><\/h2>\n

How do we hold the <\/span>state expression<\/b> and pass it as a parameter to the query (recursive part here)?<\/span><\/p>\n