Coding Obsession

Today’s tip is a relatively simple (but limited) way to programmatically extract the output columns of a SQL Server stored procedure or query along with the tables they come from.

This is something that came up at work. I didn’t want to do it by hand because there were many stored procedures to check, but it was difficult to automate because they could be (and were indeed) quite complex, with many selects and joins, computed columns, aliases and so on, and to make things worse the SQL code had no standard indentation or structure, so string searching and regular expressions were not reliable options. Parsing the Transact-SQL code would have been way harder than anything else, so it was out of discussion too. Unfortunately, the limitations of this solution (that I’ll mention later) stopped us from using and we had to do the job by hand.

Lazy as I am, I wanted to make SQL Server itself give me the information I needed. After meditating about it for a while an idea came to my mind: I could try to extract the information from the execution plan.

You probably know it, but the query execution plan that you can see in Microsoft SQL Server Management Studio (SSMS from now on) comes from the SQL Server engine in XML format -SSMS just displays it in a graphical form. This XML is a real gem that provides lots of information about the query (even things that aren’t displayed in the execution plan tab), and you can see it by setting the “SET STATISTICS XML” option to ON before you run your query. For example, let’s run the following query (just a plain SQL query so you can see what it’s going on, but remember that it’s the same for stored procedures) that joins the Product and ProductSubcategory tables of the AdventureWorks sample database:

Notice that I got two result sets. The first is the query’s result, and the second is the execution plan in XML format (if you don’t see it, make sure the “Include Actual Execution Plan” option isn’t turned on). If you click on the link SSMS will open the XML in a new window:

Look at the OutputList node in there. It contains all the columns that appear in the result, each one within a ColumnReference element:

As you can see the information is quite detailed: for each column you have the database, the table and the schema it belongs to. A non-intuitive thing to keep in mind is that the Alias attribute is not the column’s alias, but the table’s.

Armed with this knowledge we can now create a tool to extract the information automatically: it’s just a matter of executing the stored procedure and retrieving the execution plan to process it. But let’s do one last thing before jumping to the code. I don’t know about you, but I really hate to work with XML -I’d rather work against an object model. It turns out that we can do just that: the ShowPlan’s schema is publicly available for download, and with it and the XML Schema Definition Tool (xsd.exe, located at C:\Program Files\Microsoft SDKs\Windows\v6.0A\bin\xsd.exe on my machine) we can create the classes needed to take the execution plan’s XML and deserialize into an object graph. Run this command to generate the classes (I renamed the showplanxml.xml.xsd file I downloaded to showplanxml.xsd):

xsd C:\showplanxml.xsd /classes /o:C:\

This will create a file in C: called showplan.cs with several classes within it (the root being ShowPlanXML) that we can now include in a new project in Visual Studio (you may want to add a namespace to the generated classes). The code required to get a ShowPlanXML instance from the execution plan is really simple:

In the code snippet above I’m loading the XML from a local file just for demo purposes. In the real application I read it from a SqlDataReader after executing the stored procedure. I’m printing the version just to make sure the deserialization worked. But let’s do something more interesting:

Here I go through all the batches and statements until I reach the column references. The BaseStmtInfoType class has 4 derived classes: StmtCursorType, StmtReceiveType, StmtSimpleType, and StmtUseDbType (all these types are generated by xsd.exe too). You can tell more or less what case each one stands for based on the names. Since I’m looking for statements I only handle the case when the item is a StmtSimpleType instance. When I compile and run the code I get the following output:

Voilà! This is just what I wanted. Now some things to consider about the structure of the execution plan:

• For each step in the execution plan you’ll see a RelOp node (with its corresponding OutputList node). These nodes are nested according to the order they were executed. In our case:
  
  We’ll have 3 RelOp nodes: the outermost one will be a Hash Match, containing two others, an Index Scan and a Clustered Index Scan (this is probably easier to understand if you see the graphical execution plan and the XML document side by side).
  The good news is that for our purposes we only need to worry about the first RelOp node, since it corresponds to the last operation (the Hash Match).
• If you have more than one SQL statement in your stored procedure you’ll get execution plans for each of them. If you just care about the last result set you only need to process the last execution plan:
  
• SET STATISTICS XML ON will execute the query. The benefit of this is that you can extract the columns aliases from the SqlDataReader and match them by position with columns in the XML execution plan, provided you don’t have computed columns (see “Limitations” later). If you don’t need the aliases you can use the SET SHOWPLAN_XML option instead, which will generate the execution plan but will not actually execute the query, and therefore should be faster.

Limitations

This technique has 3 big limitations:

• If you have computed columns the resulting XML will be much more complex. For example, let’s add a new column computed with a CASE statement to our query:
  
  Now the execution plan will look like this:
  
  As you can see the column is referred to as “Expr1004″. To actually find the expression you will have to navigate (possibly deep) into the document:
  
  The entire CASE expression is in the XML, and you can get to the actual column used (MakeFlag) but it can be tedious (and this is intended to be a simple trick).
• You can’t determine the column aliases. The XML document doesn’t contain the aliases. At first I thought I could match the column references in the OuputList node to the column names from the query result by position, but unfortunately the columns in the XML are not necessarily in the same order. I was quite disappointed when I saw this because it makes this technique far less powerful (I’ve only checked in SQL Server 2005, perhaps things are better in SQL Server 2005 SP2 or SP3, or SQL Server 2008, but I don’t have any of them handy to check).
• If you have conditional logic the parameters that you pass to the stored procedure matter. This what you would expect since we are working with an execution plan anyway.

Well that’s all. I’m planning to upload a sample application for all this, but I’m too tired to do it tonight, so wait for the next post if you are interested. Hope this helps, happy coding!

Julián Hidalgo SQL Server, Tips & Tricks SQL Server, Tips & Tricks

There is a great MSDN Magazine article about multithreading applications called “What Every Dev Must Know About Multithreaded Apps“, written by Vance Morrison, an architect on the .NET Runtime Team.

I read the article a long time ago, but I decided to re-read it and to post a short summary here, just to make sure I remember the important points of it. The summary has links to the corresponding sections in Vance’s article. 

Introduction

• The fundamental requirement for writing correct programs is the same whether the program is sequential or multithreaded: all code in the program must protect any invariants that other parts of the program need, but preserving program invariants is much more difficult in the multithreaded case.

Threads and Memory

• The tricky part of multithreaded programming is how threads communicate with one another.
• The most commonly deployed multithreaded communication model is called the shared memory model:
  • In this model all threads have access to the same pool of shared memory.
  • Its advantage and also its biggest problem is that multithreaded programs are programmed in much the same way as sequential programs.
  • The model does not distinguish between memory that is being used strictly for thread local use (like most locally declared variables), and memory that is being used to communicate with other threads (like some global variables and heap memory).

Races

• There are four conditions needed for a race to be possible:
  • There are memory locations (typically global/static variables or heap memory reachable from global/static variables) that are accessible from more than one thread.
  • There is a property associated with these shared memory locations that is needed for the program to function correctly. Typically, the property needs to hold true before an update occurs for the update to be correct.
  • The property does not hold during some part of the actual update.
  • Another thread accesses the memory when the invariant is broken, thereby causing incorrect behavior.

Locks

• The most common way of preventing races is to use locks to prevent other threads from accessing memory associated with an invariant while it is broken. This removes the fourth condition required for a race, thus making it impossible to happen.
• In the Microsoft .NET Framework locks are implemented by the System.Threading.Monitor class.
• The lock statement in C# is a shortcut for the following:

          System.Threading.Monitor.Enter(someObject);

          try

          {

              // body

          }

          finally

          {

              System.Threading.Monitor.Exit(someObject);

          }

• Exceptions in a lock block must be properly handled. The lock is there to ensure an invariant, so it’s important to make sure that the invariant wasn’t broken as a result of the exception.
• A simple lock statement is appropriate if there is no useful cleanup to do or if everything in its body is read-only.

Using locks properly

• Locks provide mutual exclusion for regions of code, but generally programmers want to protect regions of memory.
• For a lock to provide mutual exclusion for a region of memory, no writes to that memory can occur without entering the same lock. In a properly designed program, associated with every lock is a region of memory for which it provides mutual exclusion. There is no obvious artifact of the code that makes this association clear, and yet this information is absolutely critical for anyone reasoning about the multithreaded behavior of the program.
• Every lock should have a specification associated with it that documents the precise region of memory (set of data structures) for which it provides mutual exclusion.
• While having memory regions protected by different locks that overlap is not strictly incorrect, it should be avoided because it is not useful.

How many locks?

• The main disadvantage of having more than one lock is the complexity involved. The program has more parts associated with it so there is more opportunity for programmer error.
• It is best to have few locks that protect large regions of memory and only split them when lock contention is shown to be a bottleneck on performance.

Taking Locks on Reads

• A lock should always be entered before writing a memory location. When memory is read the case is a little more complicated because it depends on the programmer’s expectations.
• In general, when code needs a program invariant, all locks associated with any memory involved with the invariant must be taken.
• For multithreaded applications the programmer’s mindset should change from believing that nothing changes unless it is explicitly changed to believing that everything changes unless locks are used to prevent it.

What Memory Needs Lock Protection?

• An easy and correct answer would be that all memory needs to be protected by a lock, but this would be overkill for most apps.
• Memory can be made safe for multithreaded use in one of several ways:
  • Memory that is only accessed by a single thread is safe because other threads are unaffected by it. This includes most local variables and all heap-allocated memory before it is published (made reachable to other threads). Once memory is published, however, it falls out of this category and some other technique must be used.
  • Memory that is read-only after publication does not need a lock because any invariants associated with it must hold for the rest of the program (since the value does not change).
  • Memory that is actively updated from multiple threads generally uses locks to ensure that only one thread has access while a program invariant is broken.
  • In certain specialized cases where the program invariant is relatively weak, it is possible to perform updates that can be done without locks. Typically, specialized compare-and-exchange instructions are used. These techniques are best thought of as special, lightweight implementations of locks. 
• A general rule should be that all program memory should fall into one of three buckets: thread exclusive, read-only, or lock protected.

Methodical Locking

• In a well-designed class, clients only access its internal state by calling its instance methods. If a lock is taken on entry to any instance method, and released on exit, there is a systematic way of ensuring that all accesses to internal data (instance fields) only occur when the lock is held. Classes that follow this protocol are called monitors (NOTE: So in essence monitors are classes that thread-safe because they synchronize access to their internal data. See this Wikipedia article about monitors for a better explanation of the concept).
• The concept of a monitor is one of the simplest and most useful techniques for methodical locking.
• The name of a lock in the .NET Framework is System.Threading.Monitor, a type specifically tailored to support the monitor concept.
• .NET locks operate on System.Object to make the creation of monitors easier.
• Every object has a built-in lock that can be used to protect its instance data. By embedding the body of every instance method in a lock(this) statement, a monitor can be formed (NOTE: Jeffrey Richter, in his “CLR via C#, Second edition“ book, explains why using lock(this) or lock(typeof(ClassName)) isn’t a good idea. See [1] in the footnotes).
• There is a special attribute, [MethodImpl(MethodImplAttributes.Synchronized)], that can be placed on instance methods to automatically insert the lock(this) statement (NOTE: Since this attribute will surround the method’s code with a lock(this) is it’s an instance methof or a lock(typeof(typename)) if it’s a static method, you should never use this attribute either. Again, see [1] in the footnotes).
• .NET locks are reentrant, meaning that the thread that has entered the lock can enter the lock again without blocking. This allows methods to call other methods on the same class without causing the deadlock that would normally occur.
• Indiscriminate use of monitors can result in either too little or too much locking.
• An important weakness with the monitor concept is that it provides no protection if the class gives out updatable pointers to its data.
• Monitors don’t address the more complicated situation when multiple locks need to be taken.
• Generally speaking, most reusable code (like container classes) should not have locks built into it because it can only protect itself, and it is likely that whatever code uses it will need a stronger lock anyway. The exception to this rule is when it is important that the code works even with high-level program errors. The global memory heap and security-sensitive code are examples of exceptional cases.
• It is less error prone and more efficient to have just a few locks that protect large amounts of memory. A single lock that protects many data structures is a good design if it allows the desired amount of concurrency. If the work each of the threads will do doesn’t require many updates to shared memory, consider taking this principle to the extreme and having one lock that protects all shared memory. It works well for applications whose worker threads don’t interact much.
• In cases where threads read shared structures frequently, but write to them infrequently, reader-writer locks such as System.Threading.ReaderWriterLock can be used to keep the number of locks in the system low (NOTE: Jeffrey Richter also says in his “CLR via C#, Second edition” book that he doesn’t recommend that anyone ever use this class, see [2] in the footnotes). This type of lock has one method for entering for reading and one for entering for writing. The lock will allow multiple readers to enter concurrently, but writers get exclusive access. Since readers now don’t block one another, the system can be made simpler (containing fewer locks) and still achieve the necessary concurrency.
• Lock usage can often be at odds with normal object-oriented program abstraction because locking is really another independent dimension of the program that has its own design criteria (other such dimensions include lifecycle management, transactional behavior, real-time constraints, and exception-handling behavior).
• If some method does not take locks itself, but expects its caller to provide that mutual exclusion, then that requirement is a precondition of calling that method and should be in its interface contract.
• If a data abstraction might take a lock or call client (virtual) methods while holding a lock, that also needs to be part of the interface contract. 
• There is little that class library designers can do to make the library friendlier to multithreading, because locking just one data structure is rarely useful. It is only when the threading structure of program is designed that locks can be usefully added.

Deadlock

• Once a program has more than one lock deadlock becomes a possibility, which is another reason to avoid having many locks in the system.
• Deadlocks can only occur if there is a circular chain of threads such that each thread in the chain is waiting on a lock already acquired by the next in line. For example, if one thread tries to enter Lock A and then Lock B, while simultaneously another thread tries to enter Lock B and then Lock A, it is possible for them to deadlock if each enters the lock that the other owns before attempting to enter the second lock.
• Deadlocks are generally prevented in one of two ways:
  • The best way to prevent deadlock is to have few enough locks in the system that it is never necessary to take more than one lock at a time.
  • If the former is impossible, deadlock can also be prevented by having a convention on the order in which locks are taken. Each lock in the system is assigned a “level”, and the program is designed so that threads always take locks only in strictly descending order by level. This protocol makes cycles involving locks, and therefore deadlock, impossible. If this strategy does not work (can’t find a set of levels), it is likely that the lock-taking behavior of the program is so input-dependent that it is impossible to guarantee that deadlock cannot happen in every case. Typically, this type of code falls back on timeouts or some kind of deadlock detection scheme.
• An analysis must be made to determine why more than one lock has to be taken simultaneously.
• Taking multiple locks is only necessary when code needs to get exclusive access to memory protected by different locks. This analysis typically either yields a trivial lock ordering that will avoid deadlock or shows that complete deadlock avoidance is impossible.

The Cost of Locks

• Another reason to avoid having many locks in a system is the cost of entering and leaving a lock.
• The lightest locks use a special compare/exchange instruction to check whether the lock is taken, and if it isn’t, they enter the lock in a single atomic action. This special instruction is relatively expensive (typically ten to hundreds of times longer than an ordinary instruction).
• There are two main reasons for this expense, and they both have to do with issues arising on a true multiprocessor system:
  • The compare/exchange instruction must ensure that no other processor is also trying to do the same thing. Fundamentally, this requires one processor to coordinate with all other processors in the system. This is a slow operation and accounts for the lower bound of the cost of a lock (dozens of cycles).
  • The other reason for the expense is the effect inter-process communication has on the memory system. After a lock has been taken, the program is very likely to access memory that may have been recently modified by another thread. If this thread ran on another processor, it is necessary to ensure that all pending writes on all other processors have been flushed so that the current thread sees the updates. The cost of doing this largely depends on how the memory system works and how many writes need to be flushed. This cost can be pretty high in the worst case (possibly hundreds of cycles or more).
• The cost of a lock is can be significant. If a frequently called method needs to take a lock and only executes a hundred or so instructions, lock overhead is likely to be an issue. The program generally needs to be redesigned so that the lock can be held for a larger unit of work.
• As the number of processors in the system grows locks become the main impediment in using all the processors efficiently:
  • If there are too few locks in the program, it is impossible to keep all the processors busy since they are waiting on memory that is locked by another processor.
  • If there are many locks in the program, it is easy to have a “hot” lock that is being entered and exited frequently by many processors. This causes the memory-flushing overhead to be very high, and throughput again does not scale linearly with the number of processors. The only design that scales well is one in which worker threads can do significant work without interacting with shared data.

A Quick Word on Synchronization

• Locks don’t really provide a mechanism for threads to synchronize.
• The principles for synchronizing threads without introducing races are not much different from the principles for proper locking.
• In the .NET Framework synchronization functionality is implemented in the ManualResetEvent and AutoResetEvent classes. These classes provide Set, Reset, and WaitOne methods: the WaitOne method causes a thread to block as long as the event is in the reset state. When another thread calls the Set method, AutoResetEvents will allow one thread that called WaitOne to unblock, while ManualResetEvents will unblock all waiting threads.
• Generally, events are used to signal that a more complicated program property holds.
• In general, it’s a bad idea to hold locks while waiting on events.

Conclusion

• The difference between sequential and multithreaded programs is that protecting program invariants is more complicated in the multithreaded case. 
• It requires a significantly higher degree of discipline to build a correct multithreaded program:
  • Ensuring through tools like monitors that all thread-shared, read-write data is protected by locks.
  • Carefully design which memory is protected by which lock.
  • Controlling the extra complexity that locks inevitably add to the program.
• Good designs are typically the simplest, and for multithreaded programs this means having the fewest number of locks that achieve the needed concurrency.

[1] Simply stated, when you lock on the this pointer or the object’s type, you open the possibility for malicious code to deadlock threads that use that type. For a complete explanation see pages 636-639 of “CLR via C#, Second Edition“.

[2] The ReaderWriterLock class has three flaws: its performance is awful, even when there is not contention on the lock, it has a policy of favoring readers over writers, “writers get starved for time and do not complete their work in a timely fashion”, and finally it supports recursion, meaning that the thread that enters the lock must be the thread that exits it (Richter consider this a bug because it’s becoming commonplace to have a thread enter a lock and start an operation to access some data and have another thread to complete the operation and exit the lock, specially likely in a asynchronous programming model). See pages 642-643 of “CLR via C#, Second Edition“.

So that’s it. If you are new to multithreading programming I strongly suggest you to read the original article. Happy coding!

Julián Hidalgo .NET, C#, Threading .NET, C#, Threading

This is the easiest way to query the schema of a database I know of:

• First go to SQL Server Management Studio, expand the databases node and go to the list of tables. In this example I’m using the AdventureWorks database:

• Launch the SQL Profiler and start a new trace.
• Right-click the tables node and select “Refresh”:

• Now you can see the the query that the SSMS used in the SQL Profiler:

And that’s it, you just have to customize it to fit your needs. You can apply this to query other type of objects of course, like indexes, keys and so on (basically anything you see in SSMS). For example, the following query will list all the columns and the table they belong to:

SELECT
tbl.name as TableName,
clmns .name AS [Name],
CAST (ISNULL(cik.index_column_id, 0) AS bit) AS [InPrimaryKey],
CAST (ISNULL((select TOP 1 1 from sys.foreign_key_columns AS colfk where colfk.parent_column_id = clmns.column_id and colfk.parent_object_id = clmns.object_id), 0) AS bit) AS [IsForeignKey],
usrt.name AS [DataType],
CAST (clmns.precision AS int) AS [NumericPrecision],
CAST (clmns.scale AS int) AS [NumericScale],
clmns.is_nullable AS [Nullable],
clmns.is_computed AS [Computed]
FROM
sys.tables AS tbl
INNER JOIN sys.all_columns AS clmns ON clmns.object_id=tbl.object_id
LEFT OUTER JOIN sys.indexes AS ik ON ik.object_id = clmns.object_id and 1=ik.is_primary_key
LEFT OUTER JOIN sys.index_columns AS cik ON cik.index_id = ik.index_id and cik.column_id = clmns.column_id and cik.object_id = clmns.object_id and 0 = cik.is_included_column
LEFT OUTER JOIN sys.types AS usrt ON usrt.user_type_id = clmns.user_type_id
ORDER BY tbl.name, clmns.name

To obtain it I refreshed the list of columns in a table, and from the resulting query I removed a couple of joins and the where clause, and added a different ORDER BY clause.

An extra bonus of this trick is that by examining the queries SSMS uses you’ll learn more about SQL Server itself.

Hope it helps :)

Julián Hidalgo SQL Server, Tips & Tricks SQL Server, Tips & Tricks