Adam Machanic : challenge, concatenation

Grouped String Concatenation: ... The Winner Is ...

Adam Machanic — Sun, 31 May 2009 20:07:00 GMT

After weeks of putting it off, I finally found the time and spent the last day and a half judging the Grouped String Concatenation Challenge. I would like to congratulate the winner, Peter Larsson, who submitted a great query and walks away with a shiny new MSDN Premium subscription.

For those who are interested, following is a breakdown of the judging process, along with some commentary:

Submission Process

To begin with, e-mails. As I mentioned in the first post, I ignored all e-mails that didn't follow the directions. Luckily this was only a few submissions. I felt it rather odd that people would spend a not insignificant amount of time working up a solution only to not bother to read the guidelines thoroughly. But that's human nature, I suppose.

Round 1

Once I collected all of the queries that followed the e-mail rules (all of which are included in the attached ZIP file), I began testing against an expanded version of AdventureWorks (the script for that is also included). I decided to eliminate any queries that did not produce the correct output data based on my sample set, or which took longer than 30 seconds to complete. The majority of queries did complete in a reasonable amount of time, and many were eliminated because the output simply wasn't correct. The biggest issue was ordering of the elements in the comma-delimited sets. I also deducted points from one person's entry because of invalid column names, but I decided to let the entry ride to the next round.

An important side note is that I created this competition with the sole intention of discovering new and different ways to do grouped string concatenation, and my hope was that someone would come up with a clever, fast solution. Unfortunately, that didn't happen, and every submission that used any technique except FOR XML PATH was eliminated in the first round of testing. I received some extremely creative solutions from a couple of people and I would like to mention them here:

Alejandro Mesa's submissions made use of various XQuery techniques, and are very interesting to look at, although fairly slow
Dean Cochrane's submission used an interesting idea of doing a MAX(CASE ...) pivot for the lists. Alas, the product names lists were not correct, so the submission didn't make it to the stress testing phase
Scott Coleman tried a similar technique, actually using the PIVOT keyword. Unfortunately, this ran for over 200 seconds, so it was eliminated

Also interesting to note is that a few people tried recursive CTE solutions. These were all cancelled at the 300 second mark. Recursive CTEs, as mentioned before on here on SQLblog, simply do not scale in their current implementation.

Round 2

After tabulating the Round 1 results I was left with 18 queries, and some obvious contenders. I ran each query through a SQLQueryStress session with 10 threads running 5 iterations each. In this phase the queries were separated into fairly distinct groups: Those that ran for around 5 minutes, those that ran for around 7-8 minutes, and those that ran longer. These groups were based, not surprisingly, on how much attention was paid by the query writers to the little details. For example, Peter Larsson's winning query cut down on logical reads dramatically by doing some of the grouping in a derived table, rather than in the outermost query as some of the other submissions did.

Lesson learned: When doing aggregations, especially when joining a lot of tables, think about what you're really aggregating, and do the aggregation as early as possible. For example, if you need to aggregate sales per customer and get customer names, do the aggregation of the sales numbers first, then join out to get the customer names. Otherwise the query processor is forced to do more work than it has to do, and your query won't be as fast. Peter and a few other contestants understood this distinction and wrote queries that were much faster as a result.

Round 3

Round 2 eliminated 4 queries, leaving me with 14 to judge based on query style. In order to judge consistently, I came up with 10 factors. A query was allotted 500 points to start, and failure to meet each factor resulted in a 50 point penalty. These factors were:

Consistent Indentation

Does the query use the same rules for indentation in all parts? This is huge for readability and helps people understand where each section of the query starts and ends.

Consistent Capitalization

Does the query use the same rules for capitalization throughout? For example, keywords should be either all capitalized, or all lowercase.

Capitalize Keywords

I like to see keywords capitalized.

Use AS for Alias Names

AS is optional, and I've left it out in many queries I've written. But the more of other peoples' code I read, the more I realize that it really does help on the readability front. Use it. Always.

Follow Capitalization of Base Tables/Columns

If the base table is called OrderHeader, I want to see it used as OrderHeader when referenced in your query, rather than orderheader. A trainer I know found this out the hard way, when he reinstalled SQL Server on his laptop shortly before a training session, and used a case-sensitive collation rather than his previously-installed case-insensitive collation. He had been careless in adhering to capitalization for his training materials, and discovered the issue in front of the class. Oops.

Long Horizontal Lists

I don't like horizontal scrolling, and I find long lists difficult to read.

Consistent Vertical Lists

Put either a comma after each element or before each element, not both. Indent your lists the same way throughout. If you indent some items below the SELECT, don't put other items on the same line as the SELECT (or GROUP BY, or ORDER BY, etc)

Alignment of Delimiters

I follow a .NET-inspired style where I put delimiters on their own lines, and line them up vertically. This gives my code what I feel is an airy, easy-to-read feel. When reading others' code I look for some kind of alignment. Failure to align delimiters makes it very difficult to understand, again, where one section begins and another ends. By the way, common delimiters for this challenge included both parens and CASE...END.

Comments

Does the query have comments? Are the comments useful in understanding the logic?

Aesthetics

This is perhaps the most subjective. My general feeling on how I enjoyed reading the code.

All in all, the queries were pretty good. I would like to call out Rick Halliday, who had the highest score in this round with some very well formatted and highly readable code.

Round 4

After judging Round 3 I tallied all of the scores and was left with a tie for top 3:

Rick Halliday
Leonid Koyfman
Peter Larsson's query #4

All three of these queries were well thought out, but only one could win, so I took another pass through each. Rick's query, though extremely well written and readable, was eliminetad first due to the fact that it performed worse than the other two. This left Leonid and Peter. It was a tough choice, but I had to give the prize to Peter for taking the time to really think through the problem and figure out exactly how best to do the aggregations. Leonid was a very, very close second, and I really wish I had a consolation prize for him.

The End

And that's that. Thank you to everyone who participated in the challenge. I hope it was as much a learning experience for you as it was for me. Congratulations again to Peter. All of the materials are attached in the ZIP file; please let me know if you have any questions, comments, etc.

The Grouped String Concatenation Challenge is Closed

Adam Machanic — Mon, 16 Mar 2009 00:22:00 GMT

Just over two weeks ago I posted the Grouped String Concatenation Challenge. A more difficult challenge than the last one I posted, partially in hopes that not as many people would submit solutions and it would be easier for me to judge. But alas, my readers are obviously really into this stuff, and I received submissions from 39 people, some of whom sent me up to four different solutions. I didn't expect such an amazing response, and now it's up to me to sort through all of these e-mails and declare a winner--no easy task.

The submissions I've looked at so far have been of very high quality, and most of them use FOR XML PATH('') in some way. A few people experimented with other techniques--which is exactly what I was hoping for--and I'll be especially interested in seeing how their solutions stack up. I also spent a lot of time this last two weeks working on alternative solutions, and most of my attempts didn't scale well. I'm hoping that some reader managed to come up with a trick I haven't thought of yet.

The judging will be done as follows:

I'll run each submission and test it for correctness against my own benchmark query (the results of which were attached to the original post). If any of the rows don't match exactly, that submission will be disqualified.
Next I will run each query twice, and will eliminate any query that doesn't run in less than four seconds on my notebook (the fastest ones I've already seen run in two).
The remaining queries will be run through SQLQueryStress sessions on a version of AdventureWorks modified to have twice as many customers and eight times as many orders. Queries in this stage will be scored on a bell curve where the top 15% will receive a score of 10, the upper-middle 35% a score of 6, the lower-middle 35% a score of 2, and the rest a score of 0. The 0s will be eliminated.
The remaining queries will then be evaluated for readability. This is purely subjective and since I'm the judge my idea of what constitutes readability wins. So I hope you've been reading my blog for a while and have absorbed some of my best practices in this area! Queries will be scored based on the same curve as before.
At this stage the queries with the highest combined scores will be weighted based on innovation and the ability to apply their techniques to a general pattern, in order to find the number one query.

Thanks again to everyone who submitted! I'm looking forward to judging the submissions. Watch this space for a comprehensive breakdown of the results, to be posted sometime in the next couple of weeks.

T-SQL Challenge: Grouped String Concatenation

Adam Machanic — Fri, 27 Feb 2009 18:22:00 GMT

It's been quite a while since the LIKE vs ? Puzzle, and I feel like it's time for another one. Response was overwhelming last time, and I'm back with a much tougher puzzle and a much bigger prize. So get ready, because I'm going to really make you stretch your brain and your T-SQL skills for this one.

But first, a bit of background. String concatenation is something I've talked about on this blog before, and it is an incredibly popular topic; my post on the subject has gotten more hits than any other single post I've ever done. TechNet blogger Ward Pond also understands the popularity of the topic, having discussed concatenation at least five times on his blog. And as illustrated in this excellent article by Anith Sen, there are a number of methods available to the intrepid SQL Server explorer; the techniques Ward and I show are just the tip of the iceberg.

And while all of that is great, there is a deep and troublesome hidden problem: Nowhere in my post, nor Anith's article, nor Ward's series, will you find a technique that completely solves the concatenation problem. The FOR XML PATH('') method--by far the most popular SQL Server 2005 "trick" I see repeated over and over in these articles and on forums--is a bit limiting. It doesn't help when we need to "group" our string concatenation, i.e. concatenate strings for a number of key values and return multiple rows in the result. And FOR XML PATH('') also leaves us a bit flat if we need to return aggregated data with the concatenated strings or--even more interesting--concatenate multiple different columns in the same output.

Sure, there are ways to solve this problem, but they usually require temp tables, user-defined functions (CLR or otherwise), tables of numbers, cursors, or other adjunct objects. And while some of these solutions are certainly workable they lack the beauty of a single, self-contained solution. In the interest of solving this problem I recently created a challenge for myself: Figure out how to do "grouped" concatenation using nothing more than a single T-SQL statement. No temp tables. No UDFs. No procedural logic.

But rather than do the work all alone and simply post my solution, I've decided to invite you to join me in the quest. Are you up for it?

Here are the rules of the game:

You are to create a single T-SQL statement that concatenates values from the AdventureWorks (note: not AdventureWorks2008) Sales.SalesOrderHeader, Sales.SalesOrderDetail, Production.Product, and Person.Contact tables.
The output should have the following columns, in the following order, and no other columns:

CustomerID: The customer's CustomerID (this is the unique key in the output)
FirstName: The customer's first name
LastName: The customer's last name
OrderCount: Number of orders placed by the customer
TotalDollarAmount: Total dollar amount of all orders placed by the customer (based on the SalesOrderHeader.SubTotal column)
TotalProductQuantity: Total number of items purchased by the customer in all orders (based on SalesOrderDetail.OrderQty)
OrderNumbers: Comma-delimited list containing the order numbers (SalesOrderHeader.SalesOrderNumber) for each of the orders placed by the customer

The numbers within the list should be alphabetized. The list should have neither leading nor trailing commas, and each element in the list should be separated by a single comma with no spaces or other white space beforeor after the comma

ProductNames: Comma-delimited list containing the unique names of all products ordered by the customer in all orders

The names within the list should be alphabetized. The list should have neither leading nor trailing commas, and each element in the list should be separated by a single comma with no spaces or other white space beforeor after the comma

No tables--permanent, temporary, or variable--are to be created. No dynamic SQL is to be used. No user-defined functions, views, or stored procedures are allowed. No variables may be declared. To put it simply, no permanent or temporary objects of any kind, at any scope, are to be explicitly created. No procedural statements of any kind--cursors or control-of-flow--are allowed. This must be a standalone statement in the AdventureWorks database; nothing more and nothing less.
Aside from the previous stipulation, any SQL Server 2005 or 2008 feature is fair game. Documented or not, if it ships with the product and can be used in a standalone T-SQL statement, you can use it. If you do use a version-specific feature, please let me know (especially if it's a SQL Server 2005 feature that's gone in 2008). Bonus points may be given for solutions that work on either version, but I'll make that decision after reviewing the submissions.
Entries will be judged first and foremost on correctness, then on a combination of performance, readability, and ability to apply your technique as a general pattern.

Just to be absolutely clear: If your submission violates the rules, outputs the wrong data, or does not precisely follow the output guidelines listed above, it will be ignored. Last time I spent a lot of energy going back and forth with people helping them get there, and I just don't have the bandwidth to do that again. So double-check your submission before you send it to me.
Make your submission readable or you will lose credit even if performance is amazing. I don't appreciate looking at a mess, and it's good for your career to learn how to write code that others can maintain. Hint: Learn to indent your code properly; lack of indentation is the biggest mistake I see people make with regard to readability.
Take your time. You have two weeks to work on this. I've already come up with three different solutions that have vastly different performance characteristics. Perhaps your first shot isn't the best choice?

The entry deadline is March 16, 2009, midnight GMT. No exceptions.
Submissions should be e-mailed to me, using a .SQL file attachment.

Do not paste your solution into the body of your e-mail
The subject of your e-mail should be "Grouped String Challenge Submission".
E-mail your submissions to [my first name] [at] [this site].
Again, be careful and don't violate these guidelines or your submission will be ignored.

... What's that? You want a prize? Fine, fine ...

The prize, for the best submission, is a full MSDN subscription, valued at around $10,000. How's that for inspiration?

... and that's that! One final note: Please do not post your solution in the comments here or on another blog, before the deadline has been reached! Last time several people did that and it was incredibly annoying both for me and those contestants trying to think through the problem. You won't be doing yourself any favors by trying to mess up the competition.

Once the deadline is reached I will test all of the submissions, tabulate the results, and post back here in early April. I promise, I won't let the thing stagnate for months like I did last time.

Have fun with it, be creative, and feel free to post comments here with any questions you might have. I found this to be a fairly difficult but very interesting exercise and I hope you agree. Enjoy, and I'm looking forward to seeing what you can do!