September 11, 2009

Implementing LINQ in ORM, part 1. No SQL DOM = no LINQ.

When we launched ORMBattle.NET, I got few complains like this one. And it's true - for now we almost never explained all the details of our LINQ translation layer. There are two reasons of this:
  • Until the end if June we've been writing the code. It was clear we have no time to waste on blogging about this. In fact, we wanted to get fully functional LINQ provider ASAP. And only after this we could talk about it.
  • What we were doing was actually much more complex than what we've seen so far. IQToolkit, series of Frans Bouma posts and everything else we could find is actually much simpler than what we developed. So it was clear that a description of this will be really large.
But now I have some time to describe our LINQ implementation. The description won't be complete - I will try to cover only major aspects. Moreover, frequently I won't describe the solution completely, but instead I will try to describe the problem it is related to. It's much easier do develop a solution if you know the problem. So let's start. My today's post is devoted to SQL DOM. I'm going to cover the following questions:
  • What is SQL DOM?
  • Is it a "must have" part of any ORM that is going to support LINQ?
  • What are alternatives to SQL DOM?
  • Why we developed it? When we started, is was completely unclear if we will support LINQ or not.
  • What about NHibernate or Subsonic? They have LINQ providers, but don't have SQL DOM.
What is SQL DOM?

SQL DOM is object oriented model of SQL language, as well as a set of providers allowing to compile these models to actual SQL commands (nearly, text + parameters). If you're interested how it looks like, visit Xtensive.Sql.Dml namespace. Our implementation of SQL DOM is responsible for schema extraction and DDL support as well. So actually it is almost complete DOM of SQL language based on SQL:1999 standard.

Here is an example code relying on SQL DOM (if it isn't colorized, visit original post - I use SyntaxHighlighter, that doesn't work via RSS):

public void TableAutoAliasTest()
  SqlTableRef tr1 = SqlDml.TableRef(Catalog.Schemas["Person"].Tables["Contact"], "a");
  SqlTableRef tr2 = SqlDml.TableRef(Catalog.Schemas["Person"].Tables["Contact"], "a");

  SqlSelect select = SqlDml.Select(tr1.CrossJoin(tr2));
  select.Limit = 10;
  select.Columns.AddRange(tr1[0], tr1[0], tr2[0]);
  select.Where = tr1[0]>1 && tr2[0]>1;

  sqlCommand.CommandText = sqlDriver.Compile(select).GetCommandText();

Is it a "must have" part of any ORM that is going to support LINQ?

I think, yes. First of all, few evidences:

But how SQL DOM helps here? Actually, it allows LINQ translator to be independent of underlying database. LINQ translation architecture with SQL DOM looks nearly the following:
  • LINQ translator produces "unified" SQL DOM model for each LINQ query.
  • Unified SQL DOM model is processed by a set of provider dependent visitors, that rewrite unsupported SQL constructions there to supported ones, as well as simplify (beautify) resulting SQL DOM model.
  • Finally, this model is converted to SQL command.
Can something similar be done without SQL DOM? Yes, but in fact it will lead to usage of solution similar to SQL DOM. Let me demonstrate a single method from our LINQ translation layer:

protected static bool ShouldUseQueryReference(
  CompilableProvider origin, 
  SqlProvider compiledSource)
  var sourceSelect = compiledSource.Request.SelectStatement;
  var calculatedColumnIndexes = sourceSelect.Columns
    .Select((c, i) => IsCalculatedColumn(c) ? i : -1)
    .Where(i => i >= 0)
  var containsCalculatedColumns = 
    calculatedColumnIndexes.Count > 0;
  var pagingIsUsed = sourceSelect.Limit != 0 || 
    sourceSelect.Offset != 0;
  var groupByIsUsed = sourceSelect.GroupBy.Count > 0;
  var distinctIsUsed = sourceSelect.Distinct;
  var filterIsUsed = !sourceSelect.Where.IsNullReference();
  var columnCountIsNotSame = sourceSelect.From.Columns.Count !=
  if (origin.Type == ProviderType.Filter) {
    var filterProvider = (FilterProvider)origin;
    var usedColumnIndexes = new TupleAccessGatherer()
    return pagingIsUsed || 

  if (origin.Type == ProviderType.Select) {
    var selectProvider = (SelectProvider)origin;
    return containsCalculatedColumns && 
        ci => selectProvider.ColumnIndexes.Contains(ci));


    || distinctIsUsed 
    || pagingIsUsed 
    || groupByIsUsed;

As you see, we're studying the content of previously produced SQL DOM expression to make some decision, that will actually affect on production of subsequent expression. Actually, this code helps to decide if we must create a new query with nested select statement, or simply decorate the statement we already have. And to make this decision, we must know how existing statement looks like.

Note that such a solution isn't 100% necessary. E.g. you can decide to rely on just the first case (create subquery) . But this doesn't always work. For example, it's quite desirable to reduce the statement nesting level in Oracle (see the tail of this post for details).

Finally, the SQL DOM tree transform I just described isn't the only one. There are many others, e.g. you must implement APPLY rewriter. Btw, in our case it is implemented on RSE level (i.e. we transform query plan rather then SQL DOM model), but if you don't have such an intermediate layer, likely, it will appear either as rewriter in LINQ translator layer, or as SQL DOM rewriter.

What are alternatives to SQL DOM?

As I just mentioned, the simplest alternative coming to mind is custom (internal) LINQ extensions allowing to precisely describe SQL language constructions, e.g. as it's described here. So such a translation pipeline would look like:
  • LINQ translator produces translates original LINQ expression to SQL-like expressions
  • This expression is processed by a set of provider dependent visitors, that rewrite unsupported SQL constructions there to supported ones, as well as simplify (beautify) resulting expression.
  • Finally, this expression is converted to SQL command.
But as you may find, this is nearly the same as in case with SQL DOM. Let's list pros and cons: Pros:
  • No necessity to develop large set of classes. 
  • Likely, it will allow to develop a complete solution faster.
  • Expressions in .NET are of predefined types. You can't associate custom information with them. But in this case you need the information related to SQL, not to C# expressions. E.g. to decide if this SELECT statement has WHERE clause, you must check if method call expression (e.g. calling .Select) has a parameter named "where". So "studying" such expressions must be a hell: you must be aware what can be used there, how to check if a particular construction is used and so on. Remember that you can't use your custom types in such models (if you will, in fact, you will develop SQL DOM ;) ).
  • You will anyway need schema model.
  • So likely, this will slow down the development of anything related to it. Rewriters, visitors (compilers) and so on.
  • Moreover, this will slow down the translation. Expressions are immutable, and their construction is quite slow (at least now).
Why we developed it? When we started, is was completely unclear if we will support LINQ or not.

This decision was based on our previous experience. DataObjects.Net v1.X ... 3.X never had this part, and finally we came to a conclusion we anyway need it. As you may find, it isn't related to LINQ much. It is an abstraction allowing to deal with SQL in object oriented fashion, rather with SQL as text. And this ability brings tons of benefits - in particular, it makes SQL generation in ORM quite unified.

SQL DOM was actually the first part we developed for DataObjects.Net 4. Btw, we even sold few copies of it :) (obviously, we knew it will be almost impossible: such a monster is necessary mainly for ORM developers). Here is a testimonial we recently got for it (translated from Russian):

"In one of our project we faced necessity to build complex SQL queries independently from specific DBMS. It was in 2007. It was clear that we need some object model of SQL the language. Searching the market then led us to Xtensive SQL DOM. It was not a product - it was a library that existed in this company and was used for their own needs. However, they wrote about it on their support forum. It should be mentioned the openness of the company was surprisingly high, which is always nice. We acquired this library and are successfully using it for two years now. Despite the fact that we have implemented some modifications there, I can highlight high quality of its design and code . Its architecture allowed us to implement a new SQL DOM provider for Oracle for it solely by our own forces. Now SQL DOM is included into DataObjects.Net 4. Definitely, any product of this company deserves the closest attention.

Sincerely, Sergey Dorogin.
Lead developer,
Department of Information Technology, JSC "CROC Incorporated"

CROC is the leading Russian company in IT infrastructure creation (IDC "Russia IT Services Forecast and Analysis" reports, 2002 - 2008). CROC helps customers improve business efficiency and meet their strategic goals through the advanced use of information technology.

The Oracle provider for DataObjects.Net 4 we develop now is based on SQL DOM Oracle provider code we received from Sergey.

What about NHibernate or Subsonic? They have LINQ providers, but don't have SQL DOM.

This means they either perform very limited set of transformations with SQL or don't perform them at all. And until this is done, LINQ implementation they provide will be quite limited.

Speaking about NHibernate, As far as I can judge, the team (or person) working on its LINQ translator  is going to translate LINQ to AST trees of HQL. Thus the very first thing they started to work on is implementation of HQL parser based on standard grammar parser (ANTLR). But for me this is a secondary problem. It is absolutely unclear how this will help to resolve the main issues:
  • LINQ is much more complex and rich than HQL. So to fully support LINQ, HQL must be extended to support all of its features. Obviously, this isn't easy even from the point of syntax.
  • Moreover, compilation of such HQL won't be as simple as now. Now NHibernate providers build SQL by contactenating strings, but they'll need nearly the same infrastructure as I just described.
So actually, I don't see how NHibernate team is going to deliver LINQ in some reasonable time at this point. They make some steps around the same point, but don't move further.

Ok, that's just what I see. I could make a mistake: my opinion is based only on blog posts, but not on the source code. So don't consider this as 100% fact. I'll be glad to hear anything showing that actual situation is different.