Free EBooks On Redgate.Com

RedGate offers several free eBooks on SqlServer and other topics (some of them only announced and yet to become downloadable) on their bookstore. I had a look at "SQL Server Execution Plans" by Grant Fritchey, which seems to be pretty good. So now we can probably forgive RedGate for turning Reflector into a commercial product, after promising the opposite two years before, right?

When DataTable.Select() Is Slow, Use DataView.FindRows()

ADO.NET's DataTable.Select() comes with a runtime complexity of O(N). This turns into a problem when the DataTable contains a lot of rows, and DataTable.Select() is invoked many times. It's pretty obvious why - just like in LinqToObjects-queries - there is no indexed lookup. DataTable.Select() needs to scan through all rows, and compare all values.

What I usually ended up doing in those cases, was to loop over the DataTable once, and fill a Dictionary using the Select's lookup-criteria as the entry's key, and the DataRow as its value, and use the Dictionary for lookups from this point on. This works fine, but it clutters the code with all those Dictionaries, which - in addition - must be synchronized manually each time changes occur in the underlying DataTable.

The DataView class offers an alternative. By defining DataView's Sort-property in accordance to the search criteria, DataView.FindRows() then allows indexed lookup with the usual binary search tree lookup runtime complexity of O(log(n)) (yes I know, Hashtable lookup might even execute at O(1), but O(log(n)) will do here). For example:

// do this just one time
DataView view = new DataView(table);
view.Sort = "name, city";

// do this N times
DataRowView[] res = view.FindRows(
    new object[] { "Earp", "Tombstone" });

I should probably mention that DataTables and DataRows actually do offer indexed searching in two special cases:

(1) When there is a primary key defined on a DataTable, DataTable.Rows.Find() (resp. DataTable.FindBy[KeyColName]() on typed DataSets) allows for indexed primary key loookup.
(2) When there is a child relation defined on a DataTable, DataRow.GetChildRows() (resp. DataRow.Get[ChildRelName]() on typed DataSets) will return the parent row's children by indexed lookup as well.

When SQL IS Broken

I think it was Mr. Benedict in "Last Action Hero", who said:

"Eliminate all logical solutions to a problem - and the illogical becomes invariably true."

I received a distress call the other day, concerning a legacy application locking a SqlServer 2000 database, together with some profiler tracefiles.

Looking at the traces I indeed saw how certain statements were blocked for minutes, until other connections committed their transactions. Nothing extradordinary one might think, of course uncommitted data updates lead to data locks, which will block ensuing statements, that are trying to read or write the same data. Maybe those transactions were just taking too long. But here comes the catch: They did not contain any Inserts/Updates/Deletes, just Selects (the only reason for the existence of the transaction being, that a programmer some fifteen years ago had decided to activate implicit transactions). And with Isolation Level "Read Committed", and those queries lasting only a few milliseconds, there should not be any long-living locks.

Unfortunately, SqlServer 2000 tracing does not support "Blocked process report" events. This tracing event was only introduced in SqlServer 2005, and delivers in detail which SQL statements block which other statements (you can find it in the "Errors and Warnings" event category. Hint: don't forget to activate 'show advanced options', and set an appropriate 'blocked process threshold' via sp_configure()). Of course one can always have a look at the Management Studio Acitivity Monitor, but the statement information there is not so fine-grained (all it displayes is the last statement within a batch, not necessarily the one causing blocking). And I hadn't received any activity monitor data for my analysis.

So when I took a closer at the tracefile, all I could do was to scan through all of those Lock Acquired / Lock Released events. This is a really tedious task, not only because there might be hundreds of locks being acquired and released on any scope from row to table, but most of all because you only see which locks get acquired, and not which locks actually fail to get acquired (and hence lead to blocking).

The statement being blocked turned out to be a single row update. I saw a key lock and a page lock being acquired, and then things stood still. So what I did was to look for an identical statement within the trace, but one which would not be blocked. Luckily, I found one, and by closer examination, I noticed that the next lock acquisition would have been a page level lock mode upgrade from "Intent Update (IU)" to "Intent Exclusive (IE)". That's also not surprising, just standard procedure when a row is about to be updated.

The only thing that collides with such a lock upgrade would have been an existing "Shared (S)" lock on the same page (or a row within that page). But how could there be a shared lock, when no other query accessing the same data was currently running (taking in consideration Isolation Level "Read Committed")? OK, some minutes before, a query accessing the same table had been executed, and its transaction was still open (due to implicit transactions), but the statement's shared locks should be gone by now. OK, it didn't make a lot of sense to use a transaction for a read-only operation (again: Isolation Level "Read Committed", not "Repeatable Read"), and applying a clientside cursor was also kind of weird. But the cursor had been closed at this point, so it's locks should be gone. Legacy applications sometimes act weird, and we should still expect proper database locking.

I built a repro testcase, and sure enough, could reproduce it on SqlServer 2000. There were several shared locks on the query's connection, even once the query's cursor had been closed. In comparison, running the same testcase on SqlServer 2005 resulted to no dagling IS locks, hence no blocking. Well, it's anyway about time to upgrade ten year old database systems. You see, "SQL(Server 2000) WAS broken" in this case.

SqlServer: When querying previously inserted rows within the same transaction is slow...

... this might have to do with table statistics not having been updated yet!

I was banging my head on this problem today: One and the same query took minutes when run within a transaction, and only seconds when run right after transaction commit. What's special about that case is, that the query reads from a table, that undergoes massive inserting just the statement before (insert-by-select).

As I was testing in an isolated environment without any other connections, it was pretty clear from that start, that this was not a locking issue. I suspected a query optimizer problem from the beginning, and tried "option(recompile)", rephrasing the query (it was pretty complex, three levels of subqueries and the like) and even indexed views, but to no avail.

I was about to dig into a huge profiled transaction batch execution plan (the same query's post-transaction execution plan had looked fine), when I found this posting, and scales fell from my eyes. My immediate guess: this was not an index issue (as the original poster had presumed), this was an "outdated statistics" issue! See, every index has statistics attached, and rebuilding an index automatically updates its statistics as well.

But instead of calling some heavyweight "dbcc dbreindex" as explained in the posting (index rebuild should go to a maintenance plan, but not be placed in an application runtime SQL batch!), I simply invoked "update statistics" on the table in question, right between the insert statement and the query. Voila! Query optimizer is back on track, and now executes the same query about a hundred times faster. I should note though, that "update statistics" also comes with a certain overhead (two to three seconds in our case).

I was aware that SqlServer decides on its own when to update statistics. Seems as if 50,000 new rows and a complex follow-up query isn't necessarily considered sufficient reason for a statistics update, at least not when being part of the same transaction.

Is "Select Distinct" a Code Smell?

From my experience, "Select distinct" indeed is a code smell (and I am not alone). Why would I fetch something, just to get rid of it again in the next step? There are situations when "distinct" makes sense, but they are rare...

In 9 out of 10 cases when I encountered a "Select distinct", the programmer tried to remove duplicate rows caused by joins along multiple too-many associations (AKA cartesian product). This not only is bad programming style, it might also kill performance.

There is always a way to rephrase such a query in order to avoid join duplicates, e.g. by replacing joins with exist-clauses, using subselects within the select-clause, derived tables in the from-clause, etc.

Hibernate Performance Tuning Tips

Top 10 Hibernate Performance Tuning Recommendations:

(1) Avoid join duplicates (AKA cartesian products) due to joins along two or more parallel to-many associations; use Exists-subqueries, multiple queries or fetch="subselect" (see (2)) instead - whatever is most appropriate in the specific situation. Join duplicates are already pretty bad in plain SQL, but things get even worse when they occur within Hibernate, because of unnecessary mapping workload and child collections containing duplicates.

(2) Define lazy loading as the preferred association loading strategy, and consider applying fetch="batch-size" or "subselect" rather than "select". Configure eager loading only for special associations, but join-fetch selectively on a per-query basis.

(3) In case of read-only services with huge query resultsets, use projections and fetch into flat DTOs (e.g. via AliasToBean-ResultTransformer), instead of loading thousands of mapped objects into the Session.

(4) Take advantage of StatelessSessions, HQL Bulk Update and Delete statements, as well as Insert-By-Select (supported by HQL as well).

(5) Set FlushMode to "Never" on Queries and Criteria, when flushing is not necessary at this point.

(6) Set ReadOnly to "true" on Queries and Criteria, when objects returned will never be modified.

(7) Consider clearing the whole Session after flushing, or evict on a per-object basis, once objects are not longer needed.

(8) Define a suitable value for jdbc.batch_size (resp. adonet.batch_size under NHibernate).

(9) Use Hibernate Query-Cache and Second Level Caching where appropriate (but go sure you are aware of the consequences).

(10) Set hibernate.show_sql to "false" and ensure that Hibernate logging is running at the lowest possible loglevel (also check log4j/log4net root logger configuration).

Special Addendum:

NHibernate's 2.x ProjectionList implementation added considerable runtime-overhead, namely by invoking some reflection API calls for every resultset row. This might slow down queries with large resultsets.

As those reflection API calls were invariant in regard to the resultset rows being iterated over (as a matter of fact, what these calls actually did was to gather resultset column schema information), and I needed an immediate fix and did not have time to wait for any NHibernate patch, I forked my own ProjectionList from NHibernate's code, did all those reflection calls once, and re-used the result from that point on. Now I doubt this is still an issue under NHibernate 3.x (and I think Hibernate under Java was never affected), but if you are using NHibernate 2.x and your profiling tool shows lots of CPU cycles being burnt in ProjectionList, you might want to give this approach a try.

All those advices are Hibernate-specific. For additional database tuning tips, you may want to have a look at:

Database Performance Tuning from Arno Huetter

• Missing Indices
• The Importance Of Choosing The Right Clustered Index
• More Performance Tuning
• SqlServer: Favor Inline UDFs Over Table Variables
• SqlServer Standard Edition DOES Support Indexed Views
• Is "Select Distinct" a Code Smell?
• Tips For Lightning-Fast Insert Performance On SQL Server

More Hibernate postings:

• Hibernate Reverse Engineering And SqlServer Identity Columns
• Implementing Equals And HashCode In Hibernate POCOs/POJOs
• NHibernate Criteria-Query: Child Collection Not Populated Despite FetchMode.Join When Criteria Exists For Child Table
• Hibernate: Joins Without Associations
• Fetching Strategies In Hibernate

Fetching Strategies In Hibernate

One thing always to remember is that the fetching strategies - as defined within Hibernate mapping configuration - only affect data retrieval via Session.get(), Session.load() and association navigation, plus Criteria queries, as long as they do not override fetch behavior via Criteria.setFetchMode(). HQL in contrast works in a kind of WYSIWYG-manner - whatever fetching is defined by the query will be done, not more, and not less, with mapping configuration being ignored as far as fetching is concerned.

More Hibernate postings:

• Hibernate Reverse Engineering And SqlServer Identity Columns
• Implementing Equals And HashCode In Hibernate POCOs/POJOs
• NHibernate Criteria-Query: Child Collection Not Populated Despite FetchMode.Join When Criteria Exists For Child Table
• Hibernate: Joins Without Associations
• Hibernate Performance Tuning Tips

Will The Real Programmers Please Stand Up?

Arousing posting on the RethinkDB blog.

In the interest of openness, we’ll post the smoke test that makes us turn away 19 out of 20 candidates within half an hour of a phone conversation (and that’s after screening the resumes). We don’t ask people to code a solution to a complex algorithms problem. We don’t ask to solve tricky puzzle questions. We don’t ask to do complex pointer arithmetic or manipulation. Here is the question that the vast majority of candidates are unable to successfully solve, even in half an hour, even with a lot of nudging in the right direction:

Write a C function that reverses a singly-linked list.

That’s it. We’ve turned away people with incredibly impressive resumes (including kernel developers, compiler designers, and many a Ph.D. candidate) because they were unable to code a solution to this problem in any reasonable amount of time.

Using Database Snapshots For Fast Testautomation DB Restore

The textbooks basically suggest the following alternatives for restoring databases to their original state after individual automated test runs:

(1) Let each test insert its own testdata on initialization, and when done, revert those changes, as well as everything the test did update.
(2) Embed the whole test run in a transaction, and rollback the transaction at the end.
(3) Restore the database from its original state before each test.

Unfortunately, none of those options worked for us. (1) is not practicable on complex database operations. (2) is not possible if there is no access to the database connection / transaction applied by the tested component. Plus we us a different data access layer for verifying test results (as the same data access layer could camouflage errors), so there is no way to work within the same transaction scope. Option (3) - when taken conventionally (applying traditional backup/restore) - was just too slow; because of several reasons, that very test database is about 150MB of size, and we have over 2000 automated tests to run.

What helped me out was SqlServer's wonderful Database Snapshot feature (available in Developer and Enterprise Editions). Snapshots are readonly-views of the database at a certain point in time. Their copy-on-write approach allows for much faster database restore, as the database now keeps track of which data pages have really changed.

So what I basically did was to create a snapshot at the beginning, then run the test on the original database, and then restore that database from the snapshot. Lightning fast!

Hibernate: Joins Without Associations

I think I have seen this topic come up dozens of times on the Hibernate discussion forums:

How can I join a table in Hibernate when there is no association in the object model?

And the usual answer is:

Use Theta-style Joins in HQL, and it can't be done in Criteria API.

While this is basically true, I would like to elaborate a little bit more on that.

First of all, we should distinguish between joining and join fetching in Hibernate. Are we using the join in order to fetch a child collection or a single entity within the same query, or not? Because if we are not, there is the chance we don't need a Join at all, and a simple Exists-subquery will do as well, because the joined entity only appears in the From-/Where-clauses, not in the Select-clause. And in a correlated subquery, we can connect pretty much everything to the main query. This has other advantages too, e.g. avoiding unwanted join duplicates and achieving better performance.

Thinking about join-fetching, this might also give us an idea (at least by my interpretation) on why Theta-Joins are required in HQL. They basically look like this:

select foo, bar
from   FooEntity as foo, BarEntity as bar
where  foo.someothercol = 'foo' and 
       foo.somecol = bar.somecol

So we will end up with a resultset that contains a list, with each list element being an object-array of size 2, with obj[0] representing a FooEntity and obj[1] representing a BarEntity .

If we had by contrast an association between FooEntity and BarEntity, we could right something like:

select foo
from   FooEntity foo
       inner join fetch foo.Bars
where  foo.someothercol = 'foo'

Looking at the query alone makes it pretty clear, that there must be a distinct definition on how the association between FooEntity and BarEntity looks like. This definition, usually representing a foreign key relation, will be applied on join fetches, lazy loading and - maybe most importantly - when updating associations. That is what Hibernate associations are all about. FooEntity.Bars will always contain child-rows following that association definition (either all child-rows, or a subset). This is why we can not choose any other arbitrary join criteria in order to fetch other BarEntities into FooEntity.Bars. It just does not make sense.

"But I want to use Criteria API", I can hear you say. OK, I'll come to that in a moment.

First I should mention at that point, that Hibernate also offers nice support for legacy databases in this context. Associations can be defined even when referencing non-primary keys. Unfortunately the NHibernate-guys have not ported that feature yet.

And I want to note that the restriction on associated rows can be narrowed down even more by providing an additional "With"-expression in de Join-Clause or within the Where-clause in HQL.

But I digress. So we have a solution for HQL, and we know why associations are needed for join fetching, and when there is no join fetching but only joining, we might be better off using an Exists subquery anyway. So what about Criteria API?

Fact is: Joining requires an association under Criteria API. Fact is also: There are join criterias that can not be expressed by an association. So the solution I came up with was: Use a database view as a kind of mediator. This view, let's call it FooBar, contains the join criteria expression in it's From/Where-clause, and selects the primary keys of the two associated tables Foo and Bar:

create view FooBar as
select Foo.Id as FooId,
       Bar.Id as BarId
from   Foo
       inner join Bar on foo.somecol = bar.somecol

The view can as well contain further columns, and even a primary key (constructed on-the-fly), or might be materialized for performance reasons.

It is mapped into the Hibernate object model just as any table would be in case of a 1:1 or 1:N relation (and we can then define associations both to Foo and to Bar), or as a N:M mapping table. Hibernate won't even know (nor care), that it's a view. In our object model, we make those associations read-only (as we rather won't try to update the view), simply by providing public access only to an enumerator/iterator, resp. a getter but no setter for a single associated entity.

We can now join-fetch formerly non-associated entities under Criteria API as well, or project some of their columns into a flat resultset (AKA DTO-fetching). And we are able to provide further criteria in our queries' Where-clauses. Works like charm!

From a design viewpoint, we should not pollute our domain model with too many of those view-associations. What we can do is to provide an additional table mapping for those cases, e.g. by subclassing our main entities.

With all those options at hand, there is very little we can NOT do with Joins in Hibernate. And in that case, there is always native SQL support in Hibernate as well.

More Hibernate postings:

• Hibernate Reverse Engineering And SqlServer Identity Columns
• Implementing Equals And HashCode In Hibernate POCOs/POJOs
• NHibernate Criteria-Query: Child Collection Not Populated Despite FetchMode.Join When Criteria Exists For Child Table
• Fetching Strategies In Hibernate
• Hibernate Performance Tuning Tips

For database tuning tips, you may want to have a look at:

Database Performance Tuning from Arno Huetter

HashMap Vs. TreeMap

This is one of my favorite programming interview questions: "What's the difference between Hash Tables and Binary Search Trees?" (or: "HashMap vs. TreeMap"). Let's see...

	Hash Tables (HashMap)	Binary Search Trees (TreeMap)
Algorithm	Keys are mapped to values by using hash functions. Hash functions transform the key to a numeric index (usually by calculating an integer value from the key first, and then applying a "modulo arraysize" operation). This index identifies an array element ("bucket"), where all corresponding values reside (values which all stem from keys with equal hash value). The key must still be looked up within the bucket, but as hashing algorithms are supposed to ensure a good hash value distribution, hence small bucket size, this lookup is very fast. The bucket array may have to be resized dynamically when a certain load factor is reached.	Node-based tree data structure, where every node contains one record (key-only, or key and value), and has a left subtree (with smaller keys) and a right subtree (with larger keys); hence keys must be comparable. Self-balancing trees, like red-black-trees, keep their height as small as possible for fast searching and inserting.
Java Implementations	Hashtable HashMap HashSet	TreeMap
.NET Implementations	Hashtable Dictionary HashSet	SortedDictionary SortedList
C++ STL Implementations	std::unordered_map std::unordered_set	std::map
Sorted	No	Yes
Range Search	No	Yes
Runtime Complexity	Inserting: O(1) (normal case), O(N) (worst case, only with bad hash algorithm) Searching: O(1) (normal case), O(N) (worst case, only with bad hash algorithm) More details	Inserting: O(log(n)) (when balanced) Searching: O(log(n)) (when balanced) More details
Implementation Notes	Equal objects must produce the same hash code, however unequal objects need not produce distinct hash codes. Equals() implementations must be reflexive, symmetric, transitive, consistent. More details. .NET's ValueType.Equals() and GetHashCode() methods are based on reflection, hence slow; you should provide your own implementation in structs.	CompareTo() implementations must be reflexive, symmetric, transitive, consistent. More details.

The Story Behind Balsamiq Mockups

Peldi Guilizzoni writes on the creation of Balsamiq Mockups. They have indeed built a wonderful tool, elegant in its design, simple in its usage, yet extremely powerful in what can be achieved by applying it. Our UI folks have been using Balsamiq Mockups since summer 2008, but I just happened to read the history of its creation today. What a truly inspiring story - sometimes one has to take risks to fulfill his dream.

The Best Programmers...

The best programmers are not marginally better than merely good ones. They are an order-of-magnitude better, measured by whatever standard: conceptual creativity, speed, ingenuity of design, or problem-solving ability.

(Randall E. Stross)

SqlServer: Favor Inline UDFs Over Table Variables

T-SQL's Table Variables surely do have their benefits, but several drawbacks as well. We used to apply them in the past within larger T-SQL batches, in order to save and reuse some smaller query results, and to avoid code duplication:

declare @MyTable table (...)

insert into @MyTable(...)
select ...

select *
from   @MyTable MyTable
       inner join ...
where  ...

But some databases grew in size far beyond original expectations, and those table variables that used to hold 100 rows, now hold 10.000 rows or more, and spill over into TempDB, hence perform badly.

So I replaced them with Inline User Defined Functions (these are table-valued UDFs, which only consist of a single Select statement):

create function dbo.MyUdf(...)
returns table
as
return (
    select ...
)
go

They can then be inlined like this:

select *
from   (dbo.MyUdf(someparam)) MyVirtualTable
       inner join ...
where  ...

This means high performance (due to the UDF query being inlined, query optimizer can do quite some magic) AND avoiding code duplication. Nice!

SqlServer Standard Edition DOES Support Indexed Views

Why on earth do nine out of ten articles on SqlServer Indexed Views state, that they are only available in Enterprise and Developer Edition? This is blatantly wrong, and prevents developers from using a great performance tuning feature.

Standard Edition DOES support Indexed Views (and from what I have heard, but not tried: even so does Express Edition). The only difference is, that one has to provide a "with (noexpand)" query hint in order for the Indexed View to be applied in Standard Edition (I checked execution plans to go sure). Plus Enterprise Edition can choose to use an Indexed View for optimization, even if it does not appear in the original query.

I think this whole confusion might be caused by Microsoft's SqlServer feature matrices, which are pretty unclear on that topic, too.