THE SQL Server Blog Spot on the Web

Welcome to - The SQL Server blog spot on the web Sign in | |
in Search

Davide Mauri

A place for my thoughts and experiences the Microsoft Data Platform

Lateral Thinking: Transitive Closure Clustering with SQL Server, UDA and JSON

For a feature we’re developing in Sensoria, we had to solve one of the well-know, yet hard to solve, problem with data and relationships between elements in a data set. While there are several ways to solve the same problem (just search for “transitive closure” with your own favorite search engine), I’d like to describe here a very interesting approach that not only shows how to leverage to the maximum SQL Server/Azure SQL, .NET and its newly added JSON support, but also to highlight that one key assets of an architect / developer, in a world where (so-called) AI is going to be very strong, is the human ability to find creative solutions. Thinking out-of-the-box or, in other words, practice some lateral thinking, is going to be key factor in future: let me show you one case that explains why.

The Problem

Let’s make an example to clarify the problem. Let’s say you are at a party where a lot of people have been invited, and you wonder how and if people are connected to each other via common friends. Let’s use letters to easily identify people, and let’s say we have this situation:

As you can see, people can be divided in two groups, so that each group, or cluster, will be made only of those people who are connected to each other via a common friend, friend of a friend, and so on.

This means that you have to find the transitive closure for the elements and then create groups so that the elements with the same transitive closure (said more easily: that are directly or indirectly related to each other) will be in the same group.

The obvious solution

This is a typical graph problem, and so, since we’re using SQL Azure, we tried to use the new Graph features. Unfortunately calculating the transitive closure is a feature that is not yet there, so another solution was needed.

It seemed that the only option to solve our problem was to use a Graph database (Azure Cosmos DB would have been the choice), but that would have required us to move data in/out of our database, which is Azure SQL, that in turn would have made our architecture a little bit more complex — and thus more expensive to manage and maintain—and, in addition, we would have needed to figure out how to keep the two databases in sync.

Nothing really too complex or hard, but before going that road I decided to spend some time to figure out if such solution would have been viable with the good old SQL. If yes, it would have helped us to save time and money while keeping the overall architectural complexity low (which helps to have maintenance costs low and performance high). Modeling graph using relational database it is possible and it is also quite easy, as you can write the data shown above like a set of pairs:

but performance are usually less than good when compared to Graph databases. In our case we had a very specific use case, we just need to group all the elements that are connected together, and thus we could just focus to solve this specific problem.

The creative solution

I proposed the problem to my good friend Itzik Ben-Gan that helped me to find a very nice SQL only solution that will soon be published on SQL Server Magazine, but I also decided to try a different creative approach, just to experiment a bit and keep my lateral thinking abilities trained.

At a first glance this sounds to be the perfect job for an UDA, but there is the additional problem that a user defined aggregate must return just a scalar value, which is the result of the aggregation function applied to all values that belongs to the same group. If the aggregation value is a sum, the returned scalar would be the value obtained by summing all the group values, if the aggregation function is concatenation, the resulting scalar would be a string containing all the string values in the same group concatenated one after the other.

Now what if, due to how the custom aggregation function works, the data may generate subgroups? And what if the number of such subgroups cannot be known in advance, but only after that data has been processed?

Let’s say, for example, you want to take all the orders of a customer, and create an aggregation function that split them in two groups: those who are above the customer’s order average amount and those who are below. This can be easily done in SQL, I know, so I would never create an UDA for this, but it easily and clearly explains the problem. This kind of problems cannot be solved using a UDA, it seems, since the return value must be a scalar and nothing else: no sub-grouping, since how would you fit them into a scalar value?

Unfortunately for us, this constraint is blocking problem, since we need to read all the data, and only after calculating the transitive closure of each element, we know how many groups we really have. It may be one, but it may be more than one, like in the example I described at the beginning.

Now, let’s try to think in a very creative way: what is a scalar, but can also be seen as a complex object…like an array of object? Yes: JSON is an answer. Let’s say we don’t use letters but numbers, and thus the original data can be rewritten as the following:

Now, if an aggregation function could return a “scalar” value like:

"1": [1, 2, 3, 4, 5, 6],
"3": [7, 8, 9, 10, 11]

then the problem would be elegantly solved. As you can see the two groups are correctly identified and each group has a unique number assigned that identifies it.

Now, say that the UDA is called TCC:

Once you have such JSON, transforming it into a table is a really simple:

dbo.TCC([Person], [IsFriendOf]) AS Result
cte2 AS (
CAST(J1.[key] AS INT) AS groupid,
CAST(J2.[value] AS INT) AS id
OPENJSON(cte.[result]) J1
OPENJSON(j1.[value]) J2

And the result will be

Problem solved!

Now, this is exactly what I have built in the last days. You can find the fully working code and example data here:


What I love of the solution, beside performances that will be discussed later, is how it helps to make the solution easy, elegant and simple. All the complexity is hidden and encapsulated into the UDA, data doesn’t need to move around different systems, which help to reduce friction and thus costs, and there is no need to learn a new language, like Gremlin, to solve our small and very specific problem.


What about performances? Well, this is one of the very few occasion where you can actually beat the database optimizer. Thanks to the fact that the UDA allows you to scan data only once, you can load each number into a list and add all the numbers into that list only if they are connected. If they are not connected, just create a new list. If you discover at some point that the two list have a common number (or friend to follow the original example) you merge them into one.

This is just the perfect use case of the HashSet that has a constant search time — O(1) — but that unfortunately cannot be used in a SQLCLR object since it is marked as MayLeakOnAbort.

The other object that offers the same constant search time is a Dictionary and the ContainsKey method which can be used in SQLCLR. So I’ve built the entire algorithm around a dictionary — a key-value pair — whose value is always set to true (could also have been anything else, since I don’t use such value at all), and the number that belong to the group represented by the dictionary is stored as a key.

Performance are great as you can see in the comparison chart here:

The values on the horizontal axis describes how the random test data was built. 2000x100 means that data was generated so that the resulting groups would have been 2000, each one with 100 elements in it. The SQL solution used is the best one we’ve been able to find (big thanks to Itzik, of course, that came up with a very elegant and clever solution). Of course, if you can came up with a better one, let me know.


Lateral thinking is our secret weapon. If you are afraid of AI coming to steal your job, don’t be, and try to solve problems in the most creative way, using your technical knowledge, intuition, gut feeling and your ability to invent a solution where it doesn’t even seem to exists.

The very first solution I tried was so slow that after minutes, even on small data sets, it was still running.

But then, in couple of days I’ve been able to find such solution, that is just what we need right now: it allows us to keep overall architecture complexity low and give us amazing performance, all of that also allowing us to spare money (we’re 100% on the cloud, so we pay for each bit we use…in this case means several thousands per year).

If in future we need some more complex graph support, extending our platform to use Cosmos DB (or any other Graph Database) will be inevitable and we’ll gladly embrace it, be assured: the message here is not about which is the best technology to do what, but that one should always try to look for a solution different than the obvious one. It just may be the best one for the target use case.

Published Sunday, November 12, 2017 6:31 PM by Davide Mauri

Comment Notification

If you would like to receive an email when updates are made to this post, please register here

Subscribe to this post's comments using RSS



wBob said:

Hey David, I worked up a graph database example using the new MATCH clause just for fun.  What do you think?

April 10, 2018 2:34 PM

Dennie said:

July 17, 2018 1:24 AM

Saim Thomus said:

I think you know about the Telstra is the largest telecommunication company. Which is operating all types of telecommunication network and voice process? This is the Internet Service of Telstra if you are Telstra internet user and having any types of issues then don’t worry we are here for your Support. We are offering phone number you can dial it anytime on the Telstra Support Phone Number 1-800-789-560. Your Query could be like.

September 26, 2018 4:19 AM

Florence Joe said:

This is so easily explained and is very useful. Thanks David for sharing such informative and easy solution for this. I wanna ask to finding a way to execute the query dynamically? That would be really helpful.

October 26, 2018 12:22 AM

Chris said:

Looks like you nailed it David! Another information that I can share to my fellow IT guys.

November 5, 2018 2:17 AM

Wayne Ben said:

It seems damn easy man. You have just solved this in amazing way. This is the thing my mind has stuck for so long and just randomly while doing searching i found your post on search engine. Thanks again. Keep sharing such informative things.

November 5, 2018 9:45 PM

Preeti Tyagi said:

Hire the premium Dehradun escorts to enjoy the real high profile independent escorts in Dehradun. The right time to enjoy top class escorts services.

December 26, 2018 12:11 AM

City Night said:

City Night is premium independent Dehradun escorts service provider, with her you can enjoy the real erotic taste of beautiful call girls in Dehradun.

December 26, 2018 11:16 PM

Arslan mike said:

I actually am typical to the blog page and I must say I admire your write-ups. This article has in fact highs my curiosity. I will save your website and keep maintaining checking for fresh information <a href=""></a>

January 13, 2019 12:19 AM

Chandigarh Escorts said:

We are the best Chandigarh escorts service provider in Chandigarh, Why go somewhere else when all your desired full fill here.

January 28, 2019 1:47 AM

Aaric said:

you can get amazing coupons from this website

February 8, 2019 5:47 AM

alicetaylor said:

You’ve written nice post, I am gonna bookmark this page, thanks for info. I actually appreciate your own position and I will be sure to come back here.

March 3, 2019 8:13 PM

Shimla Escorts said:

Hi guys! If you are alone and want female companionship, then please follow me on the links given below. I like to have sexual relationship daily with different persons. If you are interested in me

March 8, 2019 2:16 AM

Escorts service ludhiana said:

Escorts service ludhiana

Hi I am Dia Roy Independent Ludhiana Escorts in Ludhiana .Passionate hearts of males are always found to be filled with insurmountable passions and fantasies and such lively desires and the wish for charming girls and pretty ladies is always the most innate one among such thoughts

April 5, 2019 3:38 AM

Escorts service jalandhar said:

Escorts service jalandhar

Hi I am Miss Alisha Independent Jalandhar Escorts in Jalandhar. Provide  Top class Jalandhar escorts services. The Jalandhar call girls are not only beautiful but also educated and polished.

April 5, 2019 3:39 AM

Escorts service Jammu said:

Escorts service Jammu

Hello guys! I am Sneha Independent escorts in Jammu. a innocent charm combined with a knowing mind and a naughty imagination. I am here to offer you good moment of Jammu Escorts Service , I will not dissapoint your expectation.I am open for all your fantasy , let's meet and you will never forget me !

April 5, 2019 3:39 AM

Escorts service Patna said:

Escorts service Patna

Hello friends I am madam Maya escorts service provider in patna. Our call girls in Patna have wide range of call girls for you. You may chose as per your wish and enjoy there beauty. you will never feel like stranger or wired with these baby , madam  maya is always available for your entertainment.

April 5, 2019 3:39 AM

Escorts service Ludhiana said:

Escorts service Ludhiana

Hi I am Harnoor Kaur Independent Ludhiana Escorts Provider hot and sexy Ludhiana Call Girls . The ludhiana Escorts service can fulfil all your sexual fantasies. Not only that, they are ready to be good friends and accompany you to trips and parties

April 5, 2019 3:40 AM

Akron Junk Removals said:

This was a great article!

May 9, 2020 6:30 PM

Akron Auto Glass Pros said:

Great site! Love the content

May 9, 2020 6:33 PM

Healthcare Essay Writing Services said:

Custom Healthcare Essay Writing Services is very popular for students in search for healthcare assignment writing services and healthcare research paper services.

June 11, 2020 5:24 AM

Best escort girl in Ludhiana said:

Escort Service in ludhiana provide enjoyable Model Call Girls in ludhiana. Here Best escort girl in Ludhiana More info :

August 12, 2020 9:01 PM

Best escorts Girl in Ludhiana said:

Our Ludhiana escorts service agency is one of the best escorts service agency in Punjab. Hot and beautiful escorts girls are available for fun in nightlife. Our escorts service agency provide VIP and Independent Models escort service in Ludhiana.

Read more:

August 13, 2020 7:10 PM

gyjrose said:, headquartered in Knoxville, TN, is an online coupon platform company founded in 2018. Our mission is to provide you with options for an affordable lifestyle in terms of both time and money without compromising quality. We are dedicated to presenting you with a great variety of the most up-to-date and competitive deals offered by our partners.

September 10, 2020 1:06 AM

Escorts in Ludhiana said:

September 14, 2020 5:08 AM

Our Education said:

This article will outline all the different strategies you should be aware of when it comes to soccer.

September 19, 2020 4:27 AM

gyjrose said:

thats a wonderful article

September 22, 2020 8:48 PM

akgvgae said:

This is awesome thanks for share us. Fantastic... I will share your blog with other people. Thank you so much...

Please visit our website to ant consultancy firm services in Dubai :

September 27, 2020 11:43 PM

cac pvt ltd said:

Hi, After reading this amazing post i am too delighted to share my know-how here with friends.


September 28, 2020 2:06 AM

grdtllc said:

Hi, After reading this amazing post i am too delighted to share my know-how here with friends.


September 29, 2020 2:58 AM

jainoncor said:

Hi, thanks for sharing this amazing post with us.


September 29, 2020 3:23 AM

WelgrowTravels said:

Your look is so unique as compared to other people I’ve read stuff from.

I appreciate you for posting when you’ve got the opportunity.


September 30, 2020 11:22 PM

Thesundaypost said:

Hello there, much obliged for imparting this astonishing post to us.

September 30, 2020 11:54 PM

magnumtele said:

hey!!! I read this blog truly it is nice.

October 1, 2020 12:18 AM

sitaramdiwanchand said:

This is very helpful for us.

October 1, 2020 12:34 AM

Astron healthcare said:

Thanks for share this great post with us.

October 1, 2020 12:45 AM

Astron International said:

Thanks for sharing this nice article.

October 1, 2020 12:54 AM

AKGVG & Associates said:

This is amazing post.

October 1, 2020 2:14 AM

premiumhomez said:

thanks for share this information with us.


October 12, 2020 4:23 AM

Alina Chopra said:

October 14, 2020 1:15 AM

Shwetachopra said:

High Class Andheri escorts Services Affordable Rate 100% Satisfaction with Call Girls in Andheri.

October 14, 2020 3:27 AM

kangaroo auto care said:

October 14, 2020 5:23 AM

unidirection said:

Study abroad Consulatant In Dubai make Your Study abrod Dream Come true With us.


October 15, 2020 5:19 AM

Leave a Comment


About Davide Mauri

Director of Software Development & Cloud Infrastructure @ Sensoria, an innovative smart garments and wearable company. After more than 15 year playing with the Microsoft Data Platform, with a specific focus on High Performance databases, Business Intelligence, Data Science and Data Architectures, he's now applying all his skills to IoT, defining architectures to crunch numbers, create nice user experiences and provide meaningful insights, all leveraging Microsoft Azure cloud. MVP on Data Platform since 2006 he has a very strong background development and love both the ER model and OO principles. He is also a fan of Agile Methodology and Automation, which he tries to apply everywhere he can, to make sure that "people think, machines do".

This Blog


Privacy Statement