4
$\begingroup$

Many of us are familiar with N+1 problem when working with database queries. The problem was known before ORMs (Object-relational mapping frameworks) came around, but it seems that ORMs exacerbated it.

The problem goes like this. If your database has a table of cars and each car has a list of wheels (stored in another table), if you first query for all cars (1) and then for each car you query for its wheels (N) you get orders of magnitude less efficient query because you in fact have N+1 queries, whereas you could just have one.

I'll show you one scenario in which it is difficult for a less experienced developer to spot that they have an N+1 problem while using ORM.

Let's assume we have the following tables definition in Microsoft Sql Server:

CREATE TABLE [dbo].[Article](
  [Id] [int] IDENTITY(1,1) NOT NULL,
  [Title] [nvarchar](max) NULL,
CONSTRAINT [PK_dbo.Article] PRIMARY KEY CLUSTERED ([Id] ASC)
)
GO

CREATE TABLE [dbo].[ArticleScore](
  [Id] [int] IDENTITY(1,1) NOT NULL,
  [ArticleId] [int] NOT NULL,
  [ActualCity] [nvarchar](10) NULL,
  [Score] [int] NOT NULL,
 CONSTRAINT [PK_dbo.ArticleScore] PRIMARY KEY CLUSTERED ([Id] ASC)
)

GO

ALTER TABLE [dbo].[ArticleScore]  WITH CHECK ADD  CONSTRAINT [FK_dbo.ArticleScore_dbo.Article_ArticleId] FOREIGN KEY([ArticleId])
REFERENCES [dbo].[Article] ([Id])
GO

There is nothing fancy here, the main thing is that we have two tables that have a foreign key relationship.

Now let's assume that we use EntityFramework, and somewhere in the code we have a line like this:

var scores = context.ArticleScores.Where(x => x.Score < 100).ToList();

Now the scores list gets passed around a few methods, and somewhere else it's used like this:

var filtered = scores.Where(x => x.Article.Title != "trash").ToList();

This last line will cause a separate query to be executed for each Article object. When the number of objects are large, the overhead as we all know serious.

Full example that can be run and examined in SQL Profiler can be found here, which is adapted from here but I hope that the idea is clear.

The problem with this particular case can be solved with eager loading, and Entity Framework offers Include method that would load Article objects along with ArticleScore objects in the first query, thus eliminating the need to query the database at all for the second query.

Now to my question.

I would (apparently incorrectly) imagine, that there should be enough information for ORM to execute the second query in a single sql query, thus reducing N+1 problem to 1+1 problem which, in most cases won't be a problem.

ORM knows about relationship between Article table and ArticleScore table. It knows that conceptually a list of ArticleScore objects represent a slice of ArticleScore table. Thus it should be able to figure out how to get the corresponding slice of the Article table in one query, it does not look like a rocket science.

So could you please tell me, is there some fundamental problem, when writing ORMs, that would prevent elimination of most of the N+1 problems?

I understand that you cannot prevent someone from shooting oneself in the foot by writing specifically incorrect code, but in the examples like the one given above many people can easily miss the problem altogether, which is apparent to me after a few code reviews I conducted. To many people this code looks like it should have worked without exhibiting N+1.

$\endgroup$
  • $\begingroup$ I'm not really qualified to write an answer, but I'm pretty sure that what you want is possible, just complicated enough that nobody has tried it. Just the eager fetching approach creates enough problems for most ORM writers! It also might confuse people's expectations of data consistency (since it occupies a middle ground between eager and lazy). But still, I could imagine doing it within a Perl ORM that I'm familiar with, and I don't see any obvious reason why it wouldn't work. $\endgroup$ – hobbs May 5 '16 at 19:14
3
$\begingroup$

Challenge #1: Imperative code

You've shown code that is in a nicely functional form. But in many languages, in many cases, the code won't be in that nice form. Imagine if instead of

var filtered = scores.Where(x => x.Article.Title != "trash").ToList();

the code is instead

var filtered = new List();
for (x in scores)
    if (x.Article.Title != "trash")
        filtered.append(x);

Now you're hosed: you're stuck with n+1 queries, and there's no hope for the ORM to avoid that. In many (imperative) programming languages, you'd be lucky for the code to show up in the former form; it'll more typically be in the latter form.

Challenge #2: Static analysis of code

Let's go back to your original example:

var filtered = scores.Where(x => x.Article.Title != "trash").ToList();

How can the ORM transform this into a single SQL query? To do that, it would have to do non-trivial static analysis of the source code. This can't be handled just through a simple library.

From the ORM's perspective, it is passed a function that determines which articles should be kept; it knows nothing about what the function does -- it can just call the function. That's not enough to do the transformation you want. To do the transformation you want, one would have to inspect the code of that function and figure out what it is doing and then somehow turn that into a SQL query. That is decidedly non-trivial (and might require both compiler support and non-trivial static analysis algorithm).

Put another way, from the ORM's perspective, the above code is equivalent to

var filtered = scores.Where(f).ToList();

where the ORM knows nothing about what f does; all the ORM can do is invoke f on values of its choice. When you don't know what f does, there's no way to transform that into a single SQL query.

Fixing this would require a way to take code written in the underlying language and compile it to SQL. That basically means building a second compiler for the underlying programming language, and it's not easy.

In some languages, the ORM library actually obtains more than just a black-box function f: by using support for domain-specific languages or reflection, the ORM library might be able to obtain a parse tree for f. In this case, the ORM library has more to work with, and in principle the ORM library could use static analysis of the parse tree of f to try to compile it to a single SQL query. It will be language-dependent whether an ORM library can do this, purely as a library, without compiler support. So in some languages achieving what you want will be easier than in others.

$\endgroup$
  • $\begingroup$ Thank you. The second part is not very convincing, because ORM has no problem translating var filtered = context.ArticleScores.Where(x => x.Score < 100).Where(x => x.Article.Title != "trash").ToList(); to a single SQL query. Could you please contrast these two usage and explain why former poses a problem while the later does not? All you have written looks applicable to this latter example too, but despite that, it manages. $\endgroup$ – Andrew Savinykh May 4 '16 at 19:48
  • $\begingroup$ @AndrewSavinykh, thanks for your comment. I don't have enough knowledge to speak authoritatively, but are you sure it's the ORM library that is doing that translation? If there is such a translation happening, my first suspicion is that it must be in the C# compiler. I don't know the details of how the C# compiler compiles such statements to SQL, and it might be hard to answer your question without that information. Anyway, at this point those aspects start to sound like it might be C#-specific, and I don't know enough to answer, because I simply don't know how C#'s support for this works. $\endgroup$ – D.W. May 4 '16 at 20:39
  • $\begingroup$ @D.W. it's language assisted — C# provides LINQ which is a powerful way of building up queries, and one of the things it can do is turn a lambda expression into a query object that can then be turned into SQL (or something else entirely, when querying a different data source). But the same idea is possible in other languages, just expressed differently, you only need to assume the existence of some sort of composable representation of a query. What it's not doing is actually running that function against each data item. $\endgroup$ – hobbs May 5 '16 at 19:07
  • $\begingroup$ Why is challenge #1 a challenge? I don't get it. A clever enough compiler would figure out that the imperative version equivalent to the functional version. It might be difficult to infer this equivalence, but this isn't about imperative vs functional way of doing this operation, it's about effectful primivites, concurrency, sharing, etc. And that's just an example of #2. $\endgroup$ – Gilles 'SO- stop being evil' May 5 '16 at 23:10
  • $\begingroup$ @Gilles, it's more challenging to reconstruct the functional version starting from the imperative version, then if you start from the functional version -- that takes non-trivial static analysis, in imperative languages. That's why it's a challenge -- though as you say not an insurmountable challenge, at least in principle. ("Effectful primitives" is the difference between imperative vs functional programming I'm talking about; I'm not sure why this isn't a difference between imperative code vs functional code.) $\endgroup$ – D.W. May 5 '16 at 23:21
0
$\begingroup$

As there are drop-in replacements for LINQ to SQL (PDF) that guarantee a number of queries proportional to the number of occurrences of IQueryable in the type, no, this is not a fundamental problem. Or at least, LINQ to SQL doesn't present it.

$\endgroup$
  • $\begingroup$ The PDF link does not seem to function and without the contents of it this answer seems like a "link-only" answer, that it I cannot even check if it's relevant. The first link is behind a pay wall. $\endgroup$ – Andrew Savinykh Jan 2 at 20:17
  • $\begingroup$ I just tried the PDF link now and it worked for me. You can Google the paper to find some other preprint or read other related papers, e.g. Avalanche-Safe LINQ Compilation. That said, the details of how it works don't really matter. The point, as stated in my answer, is that there is a way to avoid the N+1 problem (aka query avalanches) for any LINQ to SQL expression. If you believe that statement, you don't need to read the paper. The paper is just evidence for that statement. $\endgroup$ – Derek Elkins Jan 2 at 22:05

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.