First International NoCoug SQL Challenge – And the Winner is…Posted: July 31, 2009
Iggy Fernandz invented an impossible challenge.
NoCoug and Apress sponsored an international competition.
9 SQL experts from all over the world submitted clever solutions.
SQL Guru Dan Tow reviewed the solutions and picked his favorite.
Alberto Dell’Era wins the challenge for his wonderful solution using Discrete Fourier Transforms; the runner-up is André Araujo from Australia, who used binary arithmetic and common table expressions in his solution.
The Order of the Wooden Pretzel will be bestowed on Alberto but the real prize is six books of his choice from the Apress catalog. André will receive a prize of six e-books of his choice.
Congratulations to the winners! Iggy will contact you soon to arrange for the delivery of your bounty. Thanks to everyone who participated. We’ll see you again in April for the second SQL challenge. BTW. If you have good SQL riddles – something fun and difficult, send them my way. Who knows, maybe you’ll be featured as the next challenging wizard.
Which reminds me: Last April, when Iggy presented his challenge, he told me that he wrote his own highly efficient solution to the problem. Now that the challenge is over and the winners have been announced – it is high time he will present his own solution to the world. Please go to his blog and bug him a bit about this. I’m sure a little peer pressure will make him see the light. Thanks :)
NoCoug will publish Iggy’s review of the winning result in the NoCoug Journal. If it’ll be posted online I’ll link to it. Iggy’s article includes an explanation of the decision by Dan Tow and also an explanation of the mathematics behind Alberto’s solution that I actually almost kind-of understood after reading both Alberto’s and Iggy’s explanations for around 4 hours one afternoon. My university would take my degree back if they knew, I’m sure.
One thing that bugs me is that Alberto’s winning solution is not very interesting from a SQL perspective. Note that the winning solution is the DFT solution which uses cartesian joins and subquery factoring, not the FFT solution which uses SQL Model. Dan Tow said that Model is iterative and therefore violates the spirit of SQL – which is about sets and relations. I can understand his sentiment, except that Model is part of the SQL standard.
So the winning solution is just plain SQL. It is algorithmically brilliant and I completely admire Alberto for coming up with it, but still just plain (very long) SQL. And I was wondering – this is a SQL challenge and not a math challenge. Shouldn’t the winning solution demonstrate more SQL brilliance and less math brilliance?
On the other hand, the winning solution demonstrates one of the most important principles of programming – Using a clever algorithm (such as FFT) will give you performance and scalability that no amount of query and database tuning will ever achieve. So in away its light use of SQL features does make it a good win for a SQL challenge.
My personal favorite solution is Fabien (Walder) Contaminard‘s. He still uses more math than SQL. He uses the multinomial distribution (which unlike’s Alberto’s math I actually understood). I thought it was a simple, straight forward, readable and very clever solution. Of course, it was slower than the winning entry, but he did find some interesting differences between SQL Server and Oracle while trying to optimize it.
Here’s a summary of all submitted solutions:
- Laurent Schneider’s solution using CONNECT BY and XMLQUERY (Switzerland).
- Rob van Wijk’s solution using the MODEL clause (Netherlands).
- Vadim Tropashko’s solution using 11gR2 recursive joins This entry should win the shortest solution award. (USA).
- Craig Martin’s solution using CONNECT BY and logarithms (USA).
- Alberto Dell’Era’s two solutions using Fourier transforms (Italy).
- Fabien (Waldar) Contaminard’s solution using the multinomial distribution (France).
- Almost anonymous Postgres solution using pipeline functions (Romania).
- André Araujo’s solution using binary arithmetics and subquery factoring (Australia)
Thanks for playing. See you all next Year. Don’t forget to send me your SQL riddles so I can pick the best for the next challenge (and spend long weekends trying to solve them all!)