04
Mar
10

Part 2, Chapter 5 – Gaps and islands

“It’s more the querying and teaching that I love.” – Itzik Ben-Gan

I’d been living under a rock for years as far as SQL notables were concerned, and even I knew the name Itzik Ben-Gan. You know, SQL Magazine , a Solid Quality Mentor, wrote a book or seven?  Then last year at SQLPASS, I got to meet and interview Itzik for my website, which was wonderful, except I’m still mildly embarrassed that you can see the stars twinkling in my eyes on film.

Chapter 5 is all about the gaps and islands problem (or, as it amuses me to write, the GandI problem).  For a GandI problem, you have a sequence – it could be numeric, or temporal – with missing values in it. Gaps clearly refers to the ranges of missing values; islands refers to the ranges of available values.

 “Ultimately, a querying problem is like a logical puzzle, that’s probably why I like it so much.” – IBG

 I like that Itzik devoted a full chapter – the only one of his in Deep Dives – to a single logical problem. In outline, he presents the problem, the data and parameters to solve, four solutions (with explanation, evaluation, and performance summary) to Gaps, and four solutions to Islands. The grand finale is a variation on the islands problem, followed by the Islands performance summary.

 In each solution we have a clear explanation of how it works, its performance, and how to apply the solution to a temporal sequence, or one with duplicate values.  Itzik is, as always, clear and concise, and he makes sure to point out special considerations. For example in Gaps solution 2, he notes how the query properly handles the NULL case that comes at the end of the rowset. “It is important to always think about the three-valued logic and ensure that you get the desired behavior…”.

 “If you take the 100 common types of querying problems, and you break them into pieces – into their fundamental components – you would find that there are certain techniques that, when you break them down like Legos, that you can then go and mix them and create another solution to handle another querying problem…” – IBG

 I’m always pleased and amazed at the number of valid solutions to a given problem.  Each solution represents a different line of thinking, and though one usually emerges as the clear winner, each solution has something to teach us. For example:

  • Islands solution one uses CTEs to define a set of all starting points and another set of ending points, each with assigned row numbers; the island pairs (begin, end) are found by matching up the assigned row numbers. How simple and elegant, to simply visualize an independent set of starting and ending points, and match them based on their order of occurrence.
  • Islands solution two conceptualizes the data differently: each island is treated as a group, and assigned a group number. The beginning and end points of that island are returned with a MIN and MAX for that group number. Very different, but just as valid.

I won’t ruin the chapter for you by going into greater detail (or telling which of these had the better performance). You’ll just have to read it yourself!

P.S. I encourage you, as Itzik does, to try your own solution on the problem before reading the given solutions. Happy days!

Jen is a SQL Server developer and DBA of over 10 years. She has worked for FedEx, Brinks, and Microsoft, and is currently having a lovely stint at BeautiControl in Carrollton. Jen the co-designer and administrator of MidnightDBA.com, where she make training videos, articles, and blogs. She lives in Dallas, Texas with her SQL MVP husband and 3 gorgeous kids.

Advertisements

0 Responses to “Part 2, Chapter 5 – Gaps and islands”



  1. Leave a Comment

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s


Chapters

Enter your email address to subscribe to this blog and receive notifications of new posts by email.

Join 13 other followers