Developing Linq to LLBLGen Pro, part 14
Update: I made a mistake in the first Linq to Sql query. It's not that slow as I previously posted. I didn't filter on country, which made it pull the rows of all 91 customers into memory instead of the 11. Fetching 91 customer rows, 818 order rows and 2015 order details rows took Linq to Sql over 900ms, fetching 11 customers took 165ms, not over 900. The text has been corrected for that.
(This is part of an on-going series of articles,
started here)
We're getting closer to the goal: a full-featured
Linq provider for
LLBLGen Pro. Hopefully next week the Linq CTP for LLBLGen Pro is ready
for release to customers, fingers crossed!
Last time
I talked about the function mapping support for database
functions and in-memory function/method/property access
extravangansa, today I'll discuss one of the cornerstones of
using an O/R mapper in the first place: fetching trees of
objects using hierarchical fetches.
Eager-loading of related data using prefetch paths
One of the two ways of fetching hierarchical data is by
fetching a tree of entity instances. For example: fetch all
customers from Germany and their Order entities and for
every Order entity the related Order Detail entities as
well. Using an O/R mapper should make this simple, and
efficient, i.e.: the right entities should be fetched
and all entities should be merged into a tree so their
relation to each other is shown. This means that all the
Order entity instances are stored in
Orders collections inside the Customer entity which
owns the Order instances. All Order Detail instances should
be placed inside OrderDetails collections, namely the
ones of the owning Order entity.
To do this efficiently, it would take at most 3 queries to
do this: one for the Customers, one for the Orders of these
Customers and one for the OrderDetails of these Orders.
LLBLGen Pro has a build-in mechanism which is called
Prefetch Paths, which lets you specify the paths
along a tree, and every node which should be fetched
together with the main entity / entities to fetch. In this
particular case, we're fetching Customers from Germany, and
our path therefore is pretty simple: Customer - Order -
OrderDetails. If you want, you can specify a filter per
node, a sort expression per node and a limitation (so only
the last 5 orders for example). It also allows you to
specify multiple branches in the graph. This means that the
path doesn't have to be linear, you specify a tree with
multiple branches, e.g. Customer - Employee (m:n via
Orders), Customer - Order - OrderDetails and Order -
Employee.
Prefetch paths are also polymorphic. So you can specify a
branch in the tree which is only available in certain
subtypes. For example if you take the dreaded inheritance
hierarchy Employee - Manager - BoardMember and BoardMember
has a relation with CompanyCar (as they are the only ones
allowed to have a company car, the lucky ********!), you can
define a path for fetching Employees and BoardMember -
CompanyCar: for every Employee which is a BoardMember, the
related CompanyCar is fetched. Yes, it's pretty neat
.
It's key that these eager-loading specifications, fetch
plans, prefetch paths or whatever you want to call them, are
specified at the query level and are executed
with the query. So when you're fetching the customers
together with the prefetch path, you are fetching the
complete tree defined by the specified path. Now,
it's pretty clear that the complete path has to be fetched
at once, but why is it important that the path is specified
with the query? After all, doesn't Linq to Sql use a model
where the tree to fetch is specified via LoadOptions on the
DataContext? The main issue with defining it elsewhere is
that if you execute multiple queries on the DataContext,
you'll have to make sure the LoadOptions for that particular
query are set to the correct values. The Entity Framework
uses a different approach if I'm not mistaken, they indeed
use an extension method to specify the related entities, yet
it uses strings which I find particular weird considering
the fact that the sole purpose of Linq being better than
embedded SQL strings was that it's compile-time checked.
Linq to LLBLGen Pro will have a Queryable extension method
called WithPath, which allows you to specify a
complete tree inside the query, together with filters per
node, sorting per node, exclusion of fields per node etc.,
i.o.w. the usual Prefetch Path stuff. Everything is
specifyable using compile-time checked constucts, so no
string mess. Let's get back to our little example of
Customers from Germany and their Orders and OrderDetails
entities. This is how the query looks like:
// Query A
var q = (from c in metaData.Customer
where c.Country=="Germany"
select c).WithPath(
new PathEdge<OrderEntity>(CustomerEntity.PrefetchPathOrders,
new PathEdge<OrderDetailsEntity>(OrderEntity.PrefetchPathOrderDetails)));
You simply define the path edges of the path to the related entities to fetch together with the main entities and you're done. As edges can be defined inside other edges, it's possible to specify multi-branched trees inside the query, and every PathEdge object can contain a lambda-based filter, a sort expression, a limiter and a list of fields to exclude. As Linq does allow you to specify lambda expressions wherever you want, the filter is specifyable using lambdas, and as the type to define the lambda on is specified with the PathEdge, you'll get full intellisense. The sort expression is a different matter: sorting is specified in Linq using 'orderby', but that's only accepted at a specific place, namely inside a query, but not at every spot. So we've to fall back onto normal LLBLGen Pro sort expressions for that, but that's ok, they're easy to specify. For example if we want to sort the orders on the OrderDate, descending, we would do instead:
// Query B
var q = (from c in metaData.Customer
where c.Country=="Germany"
select c).WithPath(
new PathEdge<OrderEntity>(CustomerEntity.PrefetchPathOrders, null,
new SortExpression((OrderFields.OrderDate | SortOperator.Descending), 0,
new PathEdge<OrderDetailsEntity>(OrderEntity.PrefetchPathOrderDetails)));
The code is still compile time checked. Our prefetch path
code has been in the framework since 2004 and it has gone
through some revisions where it received more and more
tweaks. One of the main tweaks, which is developer
controllable, is the setting when LLBLGen Pro should switch
from a subquery based filter to an IN (values...) based
filter for fetching related entities. LLBLGen Pro uses 1
query per path node and merges sets through hash-value
comparisons. It doesn't use joins between parent/child in a
tree, as that leads to problems: with 1:n relations it leads
to a lot of duplicates and with multi-branched trees it
leads to complicated scenarios to fetch the data out the
resultset and to very wide resultsets. So using 1 query per
path node is much more efficient, and as a bonus: the fetch
code for the node itself is the same as you'd normally use
so easier to implement as well. The Entity Framework uses
joins for related entities, which I don't think is a wise
thing to do.
Say in the above path, the engine has fetched the Customers
from Germany is now going to fetch their Orders. This could
be done in SQL with:
SELECT o.OrderID, o.CustomerID, ...
FROM Orders o
WHERE o.CustomerID IN
(
SELECT CustomerID
FROM Customers
WHERE Country=@country
)
A clever Irish developer, Marcus Mac Innes, the owner of pix.ie, said to me: "Isn't that optimizable with an IN (customerID, customerID...) query in certain conditions? and he wrote a proof of concept. In Northwind, there are 11 customers from Germany. As these are fetched before the Orders, and therefore you know the CustomerIDs to filter the Orders on, you can instead do:
SELECT o.OrderID, o.CustomerID, ... FROM Orders o WHERE o.CustomerID IN (@customerID1, @customerID2, ...., @customerID11)
This is faster, as the RDBMS just has to read one table. There's a catch: as the # of parameters increases with the increased number of parent objects already fetched, the question arises: is this always faster? Marcus did some extensive testing and the sweetspot for average sized tables was near a 100 parameters. Above that number, and the subquery as shown in the first SQL snippet was faster. This is excellent tweaking material, so LLBLGen Pro sports a threshold which allows you per query to optimize this setting, as it can be that your tables require a lower number, or perhaps in some cases a higher number. We set the threshold initially to 50 to be on the safe side for all queries.
Performance of prefetch paths and Expression tree
parsing
So, how does this all perform? We first have to measure how
fast our Linq provider parses Expression trees. As our
provider doesn't have a compiled query equivalent like Linq
to Sql, it's key to know if using Linq instead of our normal
API is of any value. Our tests show that a medium complex
query in Linq is fully handled by our provider in under 1
millisecond on a core2quad system with XP. So the overhead
is pretty minimal. This also shows that the necessity of a
compiled query feature isn't necessary: the overhead isn't
really noticable when you take into account network latency
/ db roundtrips, object materialization etc. etc.
Let's run the first query, Query A a 100 times on this
system and let's see how fast it is. After that it's
compared to the same query using Linq to Sql instead. Now, I
want to stress that benchmarks in general have to be taken
with a grain of salt: it's a snapshot of a moment in time
under the conditions of that moment, not a fact of life. So
it's an indication of what the performance will be.
With all tests I've done, I've first warmed up the CLR a bit
with fetching a query or two, so all assemblies are loaded,
database connections are live etc. Tracing/logging was
switched off, the networked database server was idle
(SqlServer 2000).
As we'll see later on in the article, the performance of
LLBLGen Pro in hierarchical fetches is pretty good and Linq
to Sql, well... let's say it doesn't do that well. The fact
that Linq to Sql has a hard time with hierarchical fetches
isn't new: several people have blogged about this in the
past:
Patrik Löwendahl,
Roger Jennings
and
David Hayden.
Here's my simple LLBLGen Pro test code. I use an empty
foreach instead of calling ToList() on the query, because
ToList() in every provider copies the results into a new
List object, which takes performance without adding anything
to the story, so I left that out. Our queries are typed with
an interface which allows you to obtain the results directly
in a list, so you can avoid this performance penalty. With
Linq to Sql, you either have to call ToList() or traverse
the set.
Stopwatch sw = new Stopwatch();
sw.Start();
int amount = 100;
for(int i = 0; i < amount; i++)
{
FetchNestedSetTest();
}
sw.Stop();
Console.WriteLine("Fetching the nested set {2} times took: {0}ms. On average this took per fetch: {1}ms",
sw.ElapsedMilliseconds, sw.ElapsedMilliseconds / amount, amount);
//...
// the routine FetchNestedSetTest:
public static void FetchNestedSetTest()
{
using(DataAccessAdapter adapter = new DataAccessAdapter())
{
LinqMetaData metaData = new LinqMetaData(adapter);
var q = (from c in metaData.Customer
where c.Country=="Germany"
select c).WithPath(
new PathEdge<OrderEntity>(CustomerEntity.PrefetchPathOrders,
new PathEdge<OrderDetailsEntity>(OrderEntity.PrefetchPathOrderDetails)));
foreach(var v in q)
{
}
}
}
The output: Fetching the nested set 100 times took: 1906ms.
On average this took per fetch: 19ms
That's 3 queries per call, 19ms total for setup the query,
adapter, db connection query parsing etc. This is a debug
build for the complete stack (Linq provider, O/R runtime,
SQL engine) and connects to a SqlServer 2000 database over
the network.
Ok, now let's see what Linq to Sql does in this case (same
machine, same target database, ran after LLBLGen Pro's
version).
Stopwatch sw = new Stopwatch();
sw.Start();
int amount = 100;
for(int i = 0; i < amount; i++)
{
FetchNestedSetTest();
}
sw.Stop();
Console.WriteLine("Fetching the nested set {2} times took: {0}ms. On average this took per fetch: {1}ms",
sw.ElapsedMilliseconds, sw.ElapsedMilliseconds / amount, amount);
//...
// the routine FetchNestedSetTest:
public static void FetchNestedSetTest()
{
NorthwindDataContext nw = new NorthwindDataContext();
DataLoadOptions loadOptions = new DataLoadOptions();
loadOptions.LoadWith<Customer>(c => c.Orders);
loadOptions.LoadWith<Order>(o => o.Order_Details);
nw.LoadOptions = loadOptions;
var q = from c in nw.Customers
where c.Country=="Germany"
select c;
foreach(var v in q)
{
}
}
Ready? This is the output: Fetching the nested set 100 times
took: 16558ms. On average this took per fetch: 165ms
Yes, I've checked it a couple of times, and before you ask
if my code indeed fetches data, it does. 19ms vs. 165ms.
That's a big difference. How is this possible? The
main reason is that MS' code isn't clever in this case. It
doesn't do any fancy optimization of the graph fetch, while
it has all the information at hand to do so. Instead it
executes a lot of queries: 1 for the Customers, one
to fetch for every Customer's Orders and per Order, one to
fetch the Order's OrderDetail entities. That's a lot of
queries, which take a lot of time. Not only that, it will
burn your server to the ground if you have many people
accessing your database and executing these queries. So if
you're considering Linq to Sql, be sure you know this
serious performance bottleneck. See also the 3 articles by
Patrik, Roger and Dave I've linked to above, which explain
the issue more in detail. In a bit, we'll see that this
approach could also lead to wrong results in some
cases. More on that below.
Microsoft has put a lot of effort in optimizing the Linq to
Sql runtime via IL code generation at runtime (see
Rico Mariani's posts about this subject) to get fast set fetches. This code indeed does its work
well, simple sets are fetched very quickly, a couple of
milliseconds per query faster than our code. But, I'm sorry
to say it Rico and friends, isn't this work all in vain when
the optimization in the end turns out to be a
micro-optimization (which is considered a bad thing)?
Shouldn't this work have been applied to the bigger picture
which clearly shows that the Linq to Sql framework isn't
equipped with solid, tweakable, clever logic to perform
all queries very fast, especially the queries for
hierarchical fetches, one of the core reasons to use an O/R
mapper in the first place? Optimizing frameworks is a
delegate manner, and optimizing O/R mappers is something you
have to work hard for: the classic 'it depends' is
applicable to a lot of situations and to get the best
performance in all cases, it's key that the framework
notices which situation it is in and adapts to that
situation. Code to quickly do hierarchical fetches with
tweakable features is somewhat complex to write, especially
the merging of the sets, but Linq to Sql doesn't even
support m:n relations, so the hardest part of hierarchical
fetches was already off the table!
Let's look at the other way of doing hierarchical fetches
with Linq.
Fetching hierarchical sets of non-entity projections
Linq allows you to specify a projection inside the
projection of your query, or more than one. I'll show you
two examples. The first one I'll show you is a complex, 5
entity touching hierarchical fetch with multiple paths. The
other one is a simpler one which fails to return the proper
set in Linq to Sql which is caused by their way of handling
nested sets in the projection.
Linq to LLBLGen Pro treats nested queries inside the
projection the same way as prefetch paths: nested queries
are fetched with a separate query per set, the sets are
merged using hashvalue matching and the queries for the
nested sets are optimized using the same bag of tricks used
for prefetch paths (yes, we're using more tricks than just
Marcus' trick
). The nested queries in a Linq query have an additional
problem though: if the end result is a set of anonymous
types you can only materialize the objects if you have all
the data: anonymous types don't have setter properties, only
getters. This requires a 2-phase projection: first the data
is fetched from the db using a simple projection, and stored
into a temporary storage in-memory. Then all nested queries
are fetched, and the results of each query are placed in the
slot per row of the set to materialize. Then that rowset is
projected again, but this time in-memory with the
actual projectors so in-memory method calls are ran and
anonymous type instantiation works OK.
Ok, let's look at our phat nested query first:
var q = from c in metaData.Customer
where c.Country == "Germany"
select new
{
c.CompanyName,
c.City,
Orders = from o in c.Orders
select new
{
OrderDetails = from od in o.OrderDetails
select new
{
od.Product,
od.Quantity,
od.UnitPrice
},
o.Employee,
o.OrderDate
}
};
This query combines fetches of anonymous types with data
projected from entity sets with fetches of entities:
od.Product and o.Employee are fetches of related entities,
while the rest are projections to anonymous types. This
query fetches data from Customer, Order, OrderDetails,
Product and Employee, and should use at most 5 queries.
Let's put this baby on the testbench to see how fast our
provider is. We use the same setup as above, only this time
FetchNestedSetTest() simply executes the query above instead
of the prefetch path query. The foreach assures proper
enumeration. The query is also in a unittest with
data-checks, so it indeed does fetch all data, so the
timings are correct.
The output is: Fetching the nested set 100 times took:
4363ms. On average this took per fetch: 43ms
This number isn't that much of a surprise, considering the
fact that the overall set of data is pretty small: just 11
customers, their orders, order details, the products used in
those order details (70 in total) and the employees who
filed the orders. With the approach of one query per node,
and with tricks like switching to an IN (value, value..)
query instead of a subquery, it makes the individual sets
pretty small, and the merger routine which has to merge the
different rows based on hashvalues doesn't have a hard time.
A debug build was used.
Now, let's see how Linq to Sql handles this query. It comes as no surprise that a nested query inside a projection is handled the same way as with the loadoptions: the query is executed per parent, except when it is a scalar, then it is folded into the parent's select for obvious reasons (we do that too, btw). To avoid controversy, here's the Linq to Sql variant of this query:
var q = from c in nw.Customers
where c.Country == "Germany"
select new
{
c.CompanyName,
c.City,
Orders = from o in c.Orders
select new
{
OrderDetails = from od in o.Order_Details
select new
{
od.Product,
od.Quantity,
od.UnitPrice
},
o.Employee,
o.OrderDate
}
};
The output: Fetching the nested set 100 times took: 30714ms.
On average this took per fetch: 307ms
So 43ms vs. 307ms. Analyzing what Linq to Sql does, you see
the same thing: a lot of queries are executed.
Clearly there's no clever code in place which makes this
more optimal.
It might be that you now think these are edge cases., but I
beg to differ. Just because you can group sets so easily
together in projections in Linq, it's mandatory that these
fetches are done optimally. Futhermore, and I already
stressed that point above: the ability to fetch trees of
objects is a big advantage of an O/R mapper over simpler
code which fills classes with results from a query: merging
sets efficiently without any effort from the developer is a
very nice feature as the data is grouped in trees, objects
in collections inside other objects, exactly as the class
model dictates. Isn't that one of the reasons people want to
work with entities, objects and the like and not with flat
tabular data?
There's another reason why the approach Linq to Sql uses
isn't that good: it can lead to wrong results. The following
Linq to Sql query results in 818 rows, one for every Order
entity in the database. However, that's wrong, as 'Distinct'
is used in the query: Customers have often more than 1 order
and often multiple orders are filed by the same Employee.
The right answer has to be 472 (on our northwind test
database) instead of 818 rows. But because Linq to Sql
doesn't use 2-phase projections, it can't take into account
the Distinct at all, leading to the wrong results:
var q = (from o in nw.Orders
select new
{
o.EmployeeID,
CustomerData = (from c in nw.Customers where c.CustomerID == o.CustomerID select new { c.CompanyName, c.City, c.Country }).Single()
}).Distinct();
The query is perhaps not what you'd see in your daily work, but it proves the point: an O/R mapper has to produce the right results according to the query.
I'll conclude with an example of Linq to LLBLGen Pro using a nested query which result is passed to a method which is executed in-memory, thus executed during projection. The method is very simple but illustrates the mechanism.
// helper class which contains the in-memory method to call
public class InMemoryMethodCallsForTests
{
public static bool IsUsefulEntity(CustomerEntity customerEntity)
{
return customerEntity.Country == "Germany";
}
}
// unit test which illustrates the point of calling this method with a nested query result.
[Test]
public void InMemoryMethodCallWithNestedSetResultAsParameter()
{
using(DataAccessAdapter adapter = new DataAccessAdapter())
{
LinqMetaData metaData = new LinqMetaData(adapter);
var ordersFromGermany = from o in metaData.Order
where o.Customer.Country=="Germany"
select o.OrderId;
List<int> orderIds = ordersFromGermany.ToList();
Assert.AreEqual(121, orderIds.Count);
var q = from o in metaData.Order
select new {
o.OrderId,
Value = InMemoryMethodCallsForTests.IsUsefulEntity(o.Customer)
};
foreach(var v in q)
{
if(v.Value)
{
Assert.IsTrue(orderIds.Contains(v.OrderId));
}
else
{
Assert.IsFalse(orderIds.Contains(v.OrderId));
}
}
}
}
This test calls for every anonymous type fetched the IsUsefulEntity routine by passing the result of the nested query on the Customer to it. The result is placed in the slot for 'Value' and is used to materialize the anonymous type instances returned by the query.
So, done yet?
Not entirely but almost. We want to add support for Full
text search to our Linq provider (our API supports it, so
it's a small thing), a way to specify fields to exclude in
entity fetches (so fetch all fields from Employee except the
Photo field) which is something already implemented in
LLBLGen Pro so it shouldn't be a lot of work to add it and
some very minor details to wrap up and then it's done!
If everything goes according to plan, we'll release
next week a Linq CTP of LLBLGen Pro v2.6 to our
customers. This CTP includes new runtime (v2.6), templates,
the Linq provider and the sourcecode of all unittests for
Linq so you get a lot of queries to look at to get started.
After that, we'll spend a month or so to make the changes
we've planned for v2.6 which will then be released in beta.
I think that gives us enough time to hammer out the
bugs/glitches/things we forgot from the Linq provider before
release.
Final words
This was the last article in this series. It spans 14
episodes and I think it's a great read how my journey
through Linq land went: from being in the pitch-black with
just a flashlight with dead batteries, to the bright sunny
dailylight of today with the fully working, high performance
provider it has become. Compiled in release build, the Linq
provider alone is 170KB, and the provider alone spans
roughly 925KB of C# sourcecode (and there's still some small
things left!). The first branch in SVN was created in
September 2007, so roughly 5-6 months worth of work. I was
on the edge of giving up on this Linq provider a couple of
times, mainly due to having no real information when what
appears where in the tree, however I'm glad I made it: the
Linq provider offers a nice way of querying all databases
supported by LLBLGen Pro and makes a nice addition to the
featureset we already provide.
I'd like to thank all people who have supported me during
this journey! I hope you all enjoyed reading these articles.
The wait is almost over, though I can assure you, it was
worth it.
