Understanding and Avoiding Cartesian Explosion In C#
We as developers write many queries to perform CRUD operations on the database. Most developers however are prone to writing their queries the way they are used to, using their favorite or their project's choice of ORM, blind to the performance implications some of their queries may carry, We particularly perform the Read/Get queries on the database very often. This makes understanding the Cartesian Explosion especially crucial to avoid unwanted performance degradations in our application because the problem occurs in these kinds of queries. Our aim in this article will be to understand what Cartesian Explosion is and how we can avoid it in our codes/queries. We will do this by going through practical examples in a while, but first, let's understand what a Cartesian Explosion is.
Cartesian Product
The term Cartesian Explosion is derived from Mathematics. Namely from something called “A Cartesian Product”, a Cartesian Product is
“the set of all ordered pairs (x, y) such that x belongs to A and y belongs to B. For example, if A = {1, 2} and B = {3, 4, 5}, then the Cartesian Product of A and B is {(1, 3), (1, 4), (1, 5), (2, 3), (2, 4), (2, 5)}.”
So as mentioned in the quote above, it basically is every possible combination that can be achieved with the elements of 2 or more sets.
Cartesian Explosion
A Cartesian Explosion in a Relational Database is when a query returns rows that are exponentially more than what is necessary, These can have huge performance setbacks in the magnitude that corresponds to the size and the number of tables being queried on. It primarily occurs when there is a poorly written query, particularly during join operations that have poor/insufficient join conditions which we will go through in this Article. To demonstrate and visualize the problem, Our ORM(Object-Relational-Mapping) of choice will be Entity Framework Core, and we will be using LINQ(Language-Integrated Query) to perform the database operations.
Suppose we have the tables and relationships above, We have Users, Posts, and comments. Now Let's say, We want to get A User with their Posts, When we get their posts we also want to retrieve the comments on their posts. But for now, let's just get Users with their Posts.
context.Users.Include(x => x.Posts).ToList();
//We Materialize the query using ToList() here
//otherwise the query wouldn't runThis creates the below query in SQL,
SELECT [u].[Id], [u].[Name], [p].[Id], [p].[UserId]
FROM [Users] AS [u]
LEFT JOIN [Posts] AS [p] ON [u].[Id] = [p].[UserId]
ORDER BY [u].[Id]
There is nothing wrong with the Query above in this context, there is no cartesian explosion whatsoever, We just return Every User with their Posts, If they do have one. Now, something to note here in the query above, however, is the duplicate of cells. We are joining the Users Table with Posts, which in our case is not a problem at all, since there are only a few rows in the table and because we are only duplicating the Name. But what if the User’s table had many columns and in some of these columns we had relatively large data stored? then if the posts table had 500,000 posts, we would be duplicating these cells 500,000 times and another 500,000 for every extra cell, which as you can imagine can be very unnecessary and have a big impact on the performance (I see online that this also is being referred to as a Cartesian Explosion, but I prefer not to).
In the cases where there indeed are many rows, we can approach the problem two different ways, Let's see what they are.
//1. We can just select the necessary columns, using select.
users = context.Users.Include(x => x.Posts).Select(x => new User {
Id = x.Id,
Posts = x.Posts.ToList()
})
.ToList();
//2. We can simply use AsSplitQuery()
users = context.Users.Include(x => x.Posts)
.AsSplitQuery()
.ToList();Let’s see the SQL Queries produced by both of the approaches above.
-- 1. We are Essentially creating a left join, but instead of selecting
-- all of the columns in the Users Table, We pick what we need.
SELECT [u].[Id], [p].[Id], [p].[UserId]
FROM [Users] AS [u]
LEFT JOIN [Posts] AS [p] ON [u].[Id] = [p].[UserId]
ORDER BY [u].[Id]
-- 2. With Split Query, It is essentially doing exactly just that,
-- It splits the query into two. it first get The Users, and then runs a
-- Inner Join, to only return Posts of the Users that Exist in the Users Table.
SELECT [u].[Id], [u].[Name]
FROM [Users] AS [u]
ORDER BY [u].[Id]
SELECT [p].[Id], [p].[UserId], [u].[Id]
FROM [Users] AS [u]
INNER JOIN [Posts] AS [p] ON [u].[Id] = [p].[UserId]
ORDER BY [u].[Id], [p].[Id]These are the two approaches we can use to counter the problem, but there are some differences between them, The first one runs a single query, therefore It means that every Property we include in the select will inevitably be duplicated. The second one Runs two separate queries, meaning it has multiple trips to the database, Returning users as a whole without duplicating their column values, and returning their related posts.
Get Mahmut Kasimoglu’s stories in your inbox
Join Medium for free to get updates from this writer.
So when to choose either? If the task at hand requires you to only work on the existing user's Posts and you don’t need the values in the property of the user itself, then you should use the first approach, this way we also get rid of doing multiple trips to the database. But if you need to also access the value of the user, then go with the second approach.
Now Let's also include the comments on the posts.
context.Users.Include(x => x.Posts)
.ThenInclude(x => x.Comments)
.ToList(); -- generated query
SELECT [u].[Id], [u].[Name], [t].[Id], [t].[UserId], [t].[Id0], [t].[PostId], [t].[UserId0]
FROM [Users] AS [u]
LEFT JOIN (
SELECT [p].[Id], [p].[UserId], [c].[Id] AS [Id0], [c].[PostId], [c].[UserId] AS [UserId0]
FROM [Posts] AS [p]
LEFT JOIN [Comments] AS [c] ON [p].[Id] = [c].[PostId]
) AS [t] ON [u].[Id] = [t].[UserId]
ORDER BY [u].[Id], [t].[Id]
Again, here this query is perfectly normal in this context, and everything I mentioned in the first query still applies. We are doing what is called a hierarchical joining, And we have the right joining conditions. The only thing to keep in mind here again is if there are many rows, this time we will have two tables worth of duplicate Items, so it starts to make more impact on the performance than our initial query. But again, here we have no problem regarding a cartesian explosion, as 4 rows are exactly the number of rows we are expecting.
Okay, since we got those out of the way, we can finally start looking at a scenario that causes Cartesian Explosion, To make this more simple, I am going to use A filter that only targets Mary.
var users = context.Users.Include(x => x.Posts)
.Include(x => x.Comments)
.First(x => x.Id == 2);Okay so, we are now running a query that Includes both A User’s, Posts and a User’s Comments. Notice that I said A User’s Comments, meaning that comments that a User has made, not the Comments a User has on their Posts. We know the ID of Mary is 2 so we just use her ID as the filter.
Here is the SQL generated
SELECT [t].[Id], [t].[Name], [p].[Id], [p].[UserId], [c].[Id], [c].[PostId], [c].[UserId]
FROM (
SELECT TOP(1) [u].[Id], [u].[Name]
FROM [Users] AS [u]
WHERE [u].[Id] = 2
) AS [t]
LEFT JOIN [Posts] AS [p] ON [t].[Id] = [p].[UserId]
LEFT JOIN [Comments] AS [c] ON [t].[Id] = [c].[UserId]
ORDER BY [t].[Id], [p].[Id]So what is the problem with this query? The problem is that this time we are joining both Posts And Comments with Users on the same level, this is bad because there is no relationship between Posts and Comments in this context, So what the database has to do in this case is something called a Cross Join aka Cartesian Join, exactly what we saw at the beginning of this article regarding Cartesian Products. In this case, it generates a query result with every possible combination on both Join’s results which are the Posts and Comments.
So with the data that we have in our Table, we know that Mary has a Single post, And has posted 3 comments. So the result will be 3 x 1, and that would equal 3 rows in total. This is not a problem at this point, since 3 rows is a reasonable amount of rows, but the problem starts to arise when there is more than 1 matching row on each of the joins. so suppose Mary had 2 posts instead of 1 (3x2), then we would have ended up with 6 rows instead of 3. So the total number of rows essentially is equal to the number of rows each joins on the same level returns and multiplied by each other. This starts becoming exponential as the number of rows in each join grows especially when the number of joins on the same level is being performed. Now since we understand how it works let's look at the query result.
So let’s decipher the query result above, we know that Mary has only one Post, with the ID of 12. We also know that Mary has a total of three comments. The first Join that involves the post returns a single row, and the second join that involves the comments returns 3 rows. Then the query combines every combination possible with the rows in this query, hence the result above. Now let’s take a hypothetical scenario where Mary is an Influencer and has 500 posts. She also is an avid commenter, who loves to comment on other people's photos so she also has 500 comments. In that scenario, the database would have to generate every possible combination with these two result sets. That would have been 500 x 500, which is equal to a whopping 250,000 rows! and that is just the total in 2 Tables, now Imagine if we had another 500 on another table that we are joining on the same level, we would have to multiply 250,000 by another 500, and that would result in 125 Million rows… while here we are only dealing with a total of 1500 rows of data, now combine this with the duplication of the cells we mentioned above, I know, a Disaster. That is how a seemingly innocent query can be secretly deadly to the performance, and to reiterate my previous point, this is why it is crucial to understand the importance of cartesian explosions properly.
So what is the solution to this?
Again, our best friend AsSplitQuery (in this case) comes to the rescue, Instead of performing joins on all these tables, it instead splits the query into multiple different queries. Let’s see our new query after applying it to the Scenario above.
SELECT TOP(1) [u].[Id], [u].[Name]
FROM [Users] AS [u]
WHERE [u].[Id] = 2
ORDER BY [u].[Id]
SELECT [p].[Id], [p].[UserId], [t].[Id]
FROM (
SELECT TOP(1) [u].[Id]
FROM [Users] AS [u]
WHERE [u].[Id] = 2
) AS [t]
INNER JOIN [Posts] AS [p] ON [t].[Id] = [p].[UserId]
ORDER BY [t].[Id]
SELECT [c].[Id], [c].[PostId], [c].[UserId], [t].[Id]
FROM (
SELECT TOP(1) [u].[Id]
FROM [Users] AS [u]
WHERE [u].[Id] = 2
) AS [t]
INNER JOIN [Comments] AS [c] ON [t].[Id] = [c].[UserId]
ORDER BY [t].[Id]This is what our query looks like, now let's again imagine where we apply this query to our hypothetical scenario above. Mary has 500 posts and 500 Comments. We first get Mary by her ID, Then we get Mary’s posts in our second query and finally, we get Mary’s comments. We end up running 3 separate queries but this time we only end up with 1001 rows instead of 250,000. A big win in this case.
The reason I wrote “In this case” above where I mentioned the AsSplitQuery is that it may not always be necessary and may even be detrimental to performance in some instances. This is because we are making more than one query when we use that, so we would have to determine whether or not the context of the situation is worth the tradeoff. That is why it is important to always test our implementations and compare different strategies to pick the best out of them.
I hope this article helped make you understand what a Cartesian Explosion is and its potential impact on the performance so that you too can avoid them in your code!
