No newer entries | Menu | Useful docker commands

The 1+N problem

The 1+N problem is the problem where you read data from a DB using an ORM and then have to fire off more queries for each retrieved row in order to load additional data

For example, look at these three models in C# (this example excludes the properties we don't need)

public class Author
{
  public int Id {get;set;}
  //TODO: More artist info like name, birthdate, picture, isAlive flag, etc.
  public virtual ICollection<Book> Books {get;set;}
}

public class Book
{
  public int Id {get;set;}
  //TODO: More book info like title, description, ISBN, etc.
  public int AuthorId {get;set;}
  public Author Author {get;set;}
  public virtual ICollection<Owner> Owners {get;set;}
}

public class Owner
{
  public int Id {get;set;}
  //TODO: More owner properties
  public virtual ICollection<Book> Books {get;set;}
}

If a user wants to see a table of all books in their collection, you would naively do ctx.Books.Where(b => b.Owners.Any(o => o.Id == CurrentUserId)), iterate over it, and then do ctx.Authors.First(m => m.Id == book.AuthorId) for every book. This is really bad, especially when the user has multiple books from the same author. You might optimize this to only query for authors you haven't yet queried.

This is the 1+N problem. In this case, "N" is just 1 because we only reference the author from the book, but the book might have multiple referenced items such as the revision, publisher, printer, languages, etc.

The exact formula for the query total is 1+(n*c), where "n" is the number of referenced properties you query, and "c" is the number of items returned by the main query.

This is stupidly slow and inefficient, and one of the main points people criticize when they talk about ORMs.

Note: if you use SQLite you will likely not notice a significant slowdown due to the lack of a network layer

The 1+N solution

The solution is to ditch your ORM and use one that has not stopped evolving decades ago. For this purpose, we look at the one Microsoft provides for .NET: "Entity Framework" (usually just written as "EF").

Missing intermediates

You might have spotted in the models above that I created an n:n mapping for books and users, but I did not create an intermediate table. This is on purpose. Good ORMs model them automatically. In .NET, you only have to model the intermediate table if the name does not matches the autogenerated one (there's ways around this), or if you want to add additional columns to that table apart from the two referential id columns. Example columns for the intermediate table would be the purchase date and how far they've read the book.

Note that this has no impact on the 1+N problem, I just wanted to clarify why the intermediate model is absent.

Including references

The "Book" model references the "Author" model twice, once as "Author" for the model itself and once as "AuthorId" for just the key. This is on purpose and gives you more flexibility. EF doesn't forces you to include the "AuthorId" property, but it makes queries like selecting all books from an author easier. It also simplifies assigning authors to books because you just need to set the "AuthorId" but not the "Author" for existing authors.

EF is smart enough to not load referential data for key comparisons. This means the two book counting queries below are equivalent:

ctx.Books.Where(b => b.AuthorId = 13).Count();
ctx.Books.Where(b => b.Author.Id = 13).Count();

If we actually need a referenced property, we can include the "Author" reference by using .Include():

I will start indenting queries from now on

ctx.Books
  .Include(b => b.Author)
  .Where(b => b.Owners.Any(o => o.Id == CurrentUserId))

Now the "Author" property of each book will be populated. You can chain as many ".Include" together as you want.

You can also include properties from referenced properties using .ThenInclude(). Let's say the "Author" model references a binary from a "Blob" table for their portrait. You would include those properties directly after including the Author:

ctx.Books
  .Include(b => b.Author)
  .ThenInclude(a => a.Portrait)
  .Where(b => b.Owners.Any(o => o.Id == CurrentUserId))

And yes you can filter by referenced properties. If you only want books from authors that are dead you can do this:

ctx.Books
  .Include(b => b.Author)
  .ThenInclude(a => a.Portrait)
  .Where(b => b.Owners.Any(o => o.Id == CurrentUserId) && !b.Author.IsDead);

You do not actually need to include the author if it's for filtering only.

Cartesian explosion

SQL delivers the data in tabular format. This means that data gets duplicated quickly when you include multiple properties. If we add revisions and languages to books and include them too, the SQL server has to duplicate all other referenced data for each row of referenced data in order to retain the table-like format.

If a book has 10 revisions and 3 languages you will end up with the book entry repeated 30 times, every language 10 times, and every revision 3 times.

This is known as cartesian explosion, and it can get out of hand fast. The total row count will be the product of all the individual referenced data count. 100 books with 3 languages and 10 revisions each would yield 3000 rows.

In EF, this is trivial to solve:

ctx.Books
  .Include(b => b.Author)
  .ThenInclude(a => a.Portrait)
  .Include(b => b.Language)
  .Include(b => b.Revision)
  .Where(b => b.Owners.Any(o => o.Id == CurrentUserId))
  .AsSplitQuery() //The magic

This causes EF to create individual SELECT queries for each used table. You can also enable this globally, and then use .AsSingleQuery() for the few locations where you don't want it.

There's potentially a few problems with this:

  1. Most SQL implementations only allow you to read from one query at a time, this means your function call will not start streaming results until all but the last subquery are processed. If this is a problem, try to build your query from the direction so the most data heavy query comes last.
  2. This is not transaction safe. You have to put a transaction around it if this is important to you.

Caching

Sometimes it can be worth it to cache some data. For example, you might cache all languages in memory because they don't need a lot of space and rarely change. This means you don't have to include the "Language" property. You still know which language it is because the "LanguageId" property will still be populated.

Conclusion

ORMs aren't shit, your ORM is.