{"id":1674,"date":"2013-07-25T00:00:00","date_gmt":"2013-07-25T00:00:00","guid":{"rendered":"https:\/\/test.simple-talk.com\/uncategorized\/the-sql-of-gaps-and-islands-in-sequences\/"},"modified":"2026-04-30T09:24:10","modified_gmt":"2026-04-30T09:24:10","slug":"gaps-islands-sql-server-data","status":"publish","type":"post","link":"https:\/\/www.red-gate.com\/simple-talk\/databases\/sql-server\/t-sql-programming-sql-server\/gaps-islands-sql-server-data\/","title":{"rendered":"Gaps and Islands in SQL Server: Fast Set-Based Solutions Compared"},"content":{"rendered":"\n
\n

The gaps and islands problem is the task of detecting unbroken runs of sequential values (islands) and the missing values between them (gaps) in a column – typically an IDENTITY column, a date column, or a sequence number. <\/strong><\/p>\n

This article presents an alternative set-based solution to both gaps and islands, compares it against the four solutions documented in Itzik Ben-Gan’s chapter of SQL Server MVP Deep Dives, and includes a scalable test harness that benchmarks all approaches from 200,000 to 2,000,000 rows. <\/strong><\/p>\n

The alternative solution uses a self-join with row numbering and turns out to be competitive with, and in some cases faster than, the established approaches. All solutions are set-based T-SQL – no cursors or loops.<\/strong><\/p>\n

What are Gaps and Islands in SQL Server?<\/h2>\n

The word ‘Gaps’ in the title refers to gaps in sequences of values. Islands are unbroken sequences delimited by gaps. The ‘Gaps and Islands’ problem is that of using SQL to rapidly detect the unbroken sequences, and the extent of the gaps between them in a column.<\/p>\n

Islands and gaps appear in all sorts of sequences, be they IDENTITY columns where some rows have been removed or dates that occur in sequence (but some are missing).\u00a0 In all cases, the sequences do not contain duplicates. The ‘Gaps and Islands’ problem isn’t entirely an academic game, since a number of business processes demand some way of detecting gaps and islands in sequences.<\/p>\n

A typical example might occur in the express distribution business where a consignment has many packages numbered sequentially.\u00a0 Typically you scan all packages when a consignment reaches the depot.\u00a0 If packages are missing those represent the gaps.\u00a0 So if you want to represent the event “consignment arrived at the depot” and list the package numbers that did arrive, you’d want to group them like 1-10, 15-18, etc. where those are the islands.<\/p>\n

It is complex and interesting task to come up with a solution that performs and scales well. \u00a0Chapter 5 of SQL Server MVP Deep Dives<\/a>, Gaps and Islands by Itzik Ben-Gan, is probably the best and most thorough explanation of the main solutions.\u00a0 My interest was piqued by that article and I played about with the examples to try to gain a little better insight.\u00a0<\/p>\n

While doing so, I happened upon a rather different solution to the problem, and was sufficiently intrigued to develop a test harness to evaluate the way that the various algorithms performed and scaled. Let’s dip our toe in the pond by looking at some sample data.<\/p>\n

The sample data<\/h2>\n
CREATE TABLE GapsIslands (ID INT NOT NULL, SeqNo INT NOT NULL);\n\u00a0\nALTER TABLE dbo.GapsIslands ADD CONSTRAINT pk_GapsIslands PRIMARY KEY (ID, SeqNo);\n\u00a0\nINSERT INTO dbo.GapsIslands\nSELECT 1, 1 UNION ALL SELECT 1, 2 UNION ALL SELECT 1, 5 UNION ALL SELECT 1, 6 \nUNION ALL SELECT 1, 8 UNION ALL SELECT 1, 9 UNION ALL SELECT 1, 10 UNION ALL SELECT 1, 12 \nUNION ALL SELECT 1, 20 UNION ALL SELECT 1, 21 UNION ALL SELECT 1, 25 UNION ALL SELECT 1, 26;\u00a0 \n\u00a0\nSELECT * FROM dbo.GapsIslands;\n<\/pre>\n
We’ve thrown in an ID column because you may need to retrieve islands and\/or gaps across more than one record grouping.\u00a0 However, this value is not used in the basic examples, but will be used in the later performance test harnesses. This produces a table of sample data (on the left) and I’ve added the results we should expect for islands (in the middle) and gaps (on the right):<\/p>\n
\n\n\n\n\n
\n
Results<\/b><\/p>\n<\/td>\n
\n
Islands<\/b><\/p>\n<\/td>\n
\n
Gaps<\/b><\/p>\n<\/td>\n<\/tr>\n
\n
ID SeqNo<\/p>\n
1\u00a0 1<\/p>\n
1\u00a0 2<\/p>\n
1\u00a0 5<\/p>\n
1\u00a0 6<\/p>\n
1\u00a0 8<\/p>\n
1\u00a0 9<\/p>\n
1\u00a0 10<\/p>\n
1\u00a0 12<\/p>\n
1\u00a0 20<\/p>\n
1\u00a0 21<\/p>\n
1\u00a0 25<\/p>\n
1\u00a0 26<\/p>\n<\/td>\n
\n
ID StartSeqNo EndSeqNo<\/p>\n
1\u00a0 1\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0 2<\/p>\n
1\u00a0 5\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0 6<\/p>\n
1\u00a0 8\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0 10<\/p>\n
1\u00a0 12\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0 12<\/p>\n
1\u00a0 20\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0 21<\/p>\n
1\u00a0 25\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0 26<\/p>\n<\/td>\n
\n
ID StartSeqNo EndSeqNo<\/p>\n
1\u00a0 3\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0 4<\/p>\n
1\u00a0 7\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0 7<\/p>\n
1\u00a0 11\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0 11<\/p>\n
1\u00a0 13\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0 19<\/p>\n
1\u00a0 22\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0 24<\/p>\n<\/td>\n<\/tr>\n<\/tbody>\n<\/table>\n<\/div>\n
In our example, islands are contiguous groups of integers.\u00a0 In a way, gaps are the inverse of islands, as they are the endpoints between the islands.\u00a0<\/p>\n
It is interesting to note that there will always be one less row of gaps than islands.<\/p>\n
Some Islands Solutions<\/h2>\n
In the SQL MVP Deep Dives book, the author provides four solutions to the islands problem.\u00a0 From his timing results, it seems that two of these seem to be much better than the others, based on the measure of elapsed time only.\u00a0 Let’s take a look at these two.<\/p>\n
INSERT INTO dbo.GapsIslands\nSELECT 1, 1 UNION ALL SELECT 1, 2 UNION ALL SELECT 1, 5 UNION ALL SELECT 1, 6 \nUNION ALL SELECT 1, 8 UNION ALL SELECT 1, 9 UNION ALL SELECT 1, 10 UNION ALL SELECT 1, 12 \nUNION ALL SELECT 1, 20 UNION ALL SELECT 1, 21 UNION ALL SELECT 1, 25 UNION ALL SELECT 1, 26\u00a0 \n\u00a0\nPRINT 'Islands Solution #1 from SQL MVP Deep Dives';\nWITH StartingPoints AS\n(\n\u00a0\u00a0\u00a0 SELECT ID, SeqNo, ROW_NUMBER() OVER(ORDER BY SeqNo) AS rownum\n\u00a0\u00a0\u00a0 FROM dbo.GapsIslands AS A\n\u00a0\u00a0\u00a0 WHERE NOT EXISTS (\n\u00a0\u00a0\u00a0 \u00a0\u00a0\u00a0\u00a0SELECT *\n\u00a0\u00a0\u00a0 \u00a0\u00a0\u00a0\u00a0FROM dbo.GapsIslands AS B\n\u00a0\u00a0\u00a0 \u00a0\u00a0\u00a0\u00a0WHERE B.ID = A.ID AND B.SeqNo = A.SeqNo - 1)\n),\nEndingPoints AS\n(\n\u00a0\u00a0\u00a0 SELECT ID, SeqNo, ROW_NUMBER() OVER(ORDER BY SeqNo) AS rownum\n\u00a0\u00a0\u00a0 FROM dbo.GapsIslands AS A\n\u00a0\u00a0\u00a0 WHERE NOT EXISTS (\n\u00a0\u00a0\u00a0 \u00a0\u00a0\u00a0\u00a0SELECT *\n\u00a0\u00a0\u00a0 \u00a0\u00a0\u00a0\u00a0FROM dbo.GapsIslands AS B\n\u00a0\u00a0\u00a0 \u00a0\u00a0\u00a0\u00a0WHERE B.ID = A.ID AND B.SeqNo = A.SeqNo + 1)\n)\nSELECT S.ID, S.SeqNo AS start_range, E.SeqNo AS end_range\nFROM StartingPoints AS S\nJOIN EndingPoints AS E ON E.ID = S.ID AND E.rownum = S.rownum;\n\u00a0\nPRINT 'Islands Solution #3 from SQL MVP Deep Dives';\nSELECT ID, StartSeqNo=MIN(SeqNo), EndSeqNo=MAX(SeqNo)\nFROM (\n\u00a0\u00a0\u00a0 SELECT ID, SeqNo\n\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0 ,rn=SeqNo-ROW_NUMBER() OVER (PARTITION BY ID ORDER BY SeqNo)\n\u00a0\u00a0\u00a0 FROM dbo.GapsIslands) a\nGROUP BY ID, rn;\n<\/pre>\n
We have modified the code provided to support the ID column, which may reflect different user IDs, machine IDs, or whatever for your particular case.\u00a0 When you run this code, you’ll find that the results precisely match the expected results for islands shown in the table above.\u00a0 It is important to note that in at least the second case, the sequence numbers must be unique within an ID in order for the solution to work.<\/p>\n
The following performance was achieved by these two solutions across 1,000,000 rows, with the index being essential to achieving these results.\u00a0 This basically confirms the findings in the book: solution #3 is faster.<\/p>\n
\n\n\n\n\n\n\n
\n
Islands<\/b><\/p>\n<\/td>\n
\n
Test Harness – 1,000,000 Rows<\/b><\/p>\n<\/td>\n<\/tr>\n
\n
Solution<\/b><\/p>\n<\/td>\n
\n
CPU (ms)<\/b><\/p>\n<\/td>\n
\n
Elapsed Time (ms)<\/b><\/p>\n<\/td>\n
\n
Logical IOs<\/b><\/p>\n<\/td>\n<\/tr>\n
\n
Islands #1<\/p>\n<\/td>\n
\n
1545<\/p>\n<\/td>\n
\n
1611<\/p>\n<\/td>\n
\n
10568<\/p>\n<\/td>\n<\/tr>\n
\n
Islands #3<\/p>\n<\/td>\n
\n
733<\/p>\n<\/td>\n
\n
807<\/p>\n<\/td>\n
\n
2642<\/p>\n<\/td>\n<\/tr>\n<\/tbody>\n<\/table>\n<\/div>\n
In the resources file, you may run the script: Islands Test Harness #1.sql<\/i><\/b> to confirm these results for yourself and see how they may vary based on your machine’s configuration.<\/p>\n
The Traditional Gaps Solutions<\/h2>\n
The gaps problem, in my mind at least, is intrinsically a bit more challenging than islands because, in effect you need to “make up” the data points that are the endpoints of each gap; meaning that by definition for the gaps, the endpoints of the gap do not already exist in the data.<\/p>\n
As I thumb through my extensively dog-eared copy of the SQL MVP Deep Dives book, I find there are four solutions proposed for gaps.\u00a0 Of these, there are 3 which seem to perform to relatively the same order of magnitude when it comes to elapsed time.<\/p>\n
PRINT 'Gaps Solution #1 from SQL MVP Deep Dives';\nSELECT ID, StartSeqNo=SeqNo + 1, EndSeqNo=(\n\u00a0\u00a0\u00a0 SELECT MIN(B.SeqNo)\n\u00a0\u00a0\u00a0 FROM dbo.GapsIslands AS B\n\u00a0\u00a0\u00a0 WHERE B.ID = A.ID AND B.SeqNo > A.SeqNo) - 1\nFROM dbo.GapsIslands AS A\nWHERE NOT EXISTS (\n\u00a0\u00a0\u00a0 SELECT *\n\u00a0\u00a0\u00a0 FROM dbo.GapsIslands AS B\n\u00a0\u00a0\u00a0 WHERE B.ID = A.ID AND B.SeqNo = A.SeqNo + 1) AND\n\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0 SeqNo < (SELECT MAX(SeqNo) \n\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0 FROM dbo.GapsIslands B \n\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0 WHERE B.ID = A.ID);\n\u00a0\nPRINT 'Gaps Solution #2 from SQL MVP Deep Dives';\nSELECT ID, StartSeqNo=cur + 1, EndSeqNo=nxt - 1\nFROM (\n\u00a0\u00a0\u00a0 SELECT ID, cur=SeqNo, nxt=(\n\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0 SELECT MIN(B.SeqNo)\n\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0 FROM dbo.GapsIslands AS B\n\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0 WHERE B.ID = A.ID AND B.SeqNo > A.SeqNo)\n\u00a0\u00a0\u00a0 FROM dbo.GapsIslands AS A) AS D\nWHERE nxt - cur > 1;\n\u00a0\nPRINT 'Gaps Solution #3 from SQL MVP Deep Dives';\nWITH C AS\n(\n\u00a0\u00a0\u00a0 SELECT ID, SeqNo, ROW_NUMBER() OVER(PARTITION BY ID ORDER BY SeqNo) AS rownum\n\u00a0\u00a0\u00a0 FROM dbo.GapsIslands\n)\nSELECT Cur.ID, StartSeqNo=Cur.SeqNo + 1, EndSeqNo=Nxt.SeqNo - 1\nFROM C AS Cur\nJOIN C AS Nxt ON Cur.ID = Nxt.ID AND Nxt.rownum = Cur.rownum + 1\nWHERE Nxt.SeqNo - Cur.SeqNo > 1;\n<\/pre>\n
Once again a check of the results confirms that they are identical to those shown in the preceding table for gaps.\u00a0 Test harness Gaps Test Harness #1.sql<\/i><\/b> confirms that solution #1 from SQL MVP Deep Dives is the fastest.<\/p>\n
\n\n\n\n\n\n\n\n
\n
Gaps<\/b><\/p>\n<\/td>\n
\n
Test Harness – 1,000,000 Rows<\/b><\/p>\n<\/td>\n<\/tr>\n
\n
Solution<\/b><\/p>\n<\/td>\n
\n
CPU (ms)<\/b><\/p>\n<\/td>\n
\n
Elapsed Time (ms)<\/b><\/p>\n<\/td>\n
\n
Logical IOs<\/b><\/p>\n<\/td>\n<\/tr>\n
\n
Gaps #1<\/p>\n<\/td>\n
\n
903<\/p>\n<\/td>\n
\n
810<\/p>\n<\/td>\n
\n
23012<\/p>\n<\/td>\n<\/tr>\n
\n
Gaps #2<\/p>\n<\/td>\n
\n
5056<\/p>\n<\/td>\n
\n
1522<\/p>\n<\/td>\n
\n
3192926<\/p>\n<\/td>\n<\/tr>\n
\n
Gaps #3<\/p>\n<\/td>\n
\n
1591<\/p>\n<\/td>\n
\n
1593<\/p>\n<\/td>\n
\n
5278<\/p>\n<\/td>\n<\/tr>\n<\/tbody>\n<\/table>\n<\/div>\n
An Alternative Gaps Solution<\/h2>\n
Since we have relatively a fast method of determining islands, perhaps it’s possible to convert that solution into one that will identify our gaps.\u00a0 Let’s take a look at the islands results to see how it might be converted into gaps.<\/p>\n
\"gaps<\/figure>\n
\u00a0<\/p>\n
If we first insert two columns and fill the first with one less than the StartSeqNo<\/strong> and the second with one greater than the EndSeqNo<\/strong>, we can circle the numbers that represent the gaps.\u00a0 Each pair of colored, circled numbers in the rightmost table perfectly represents our gaps.<\/p>\n
This suggests to us that UNPIVOTing the islands might give us something to work with to arrive at the gaps.\u00a0 There are at least three methods to un-pivot two columns: 1) using the SQL UNPIVOT keyword, 2) doing a UNION ALL<\/strong> between each of the columns and 3) using the CROSS APPLY VALUES (CAV) approach to UNPIVOT.\u00a0 We’ll choose the latter because as this article: An Alternative (Better?) Method to UNPIVOT<\/a> seems to demonstrate, that approach may be the swiftest.\u00a0 We’ll also move the fastest islands bit of code magic into a Common Table Expression (CTE) so we can focus on our gaps solution.<\/p>\n
WITH Islands AS \n(\n\u00a0\u00a0\u00a0 SELECT ID, StartSeqNo=MIN(SeqNo) - 1, EndSeqNo=MAX(SeqNo) + 1\n\u00a0\u00a0\u00a0 FROM (\n\u00a0\u00a0\u00a0 \u00a0\u00a0\u00a0\u00a0SELECT ID, SeqNo\n\u00a0\u00a0\u00a0 \u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0,rn=SeqNo-ROW_NUMBER() OVER (PARTITION BY ID ORDER BY SeqNo)\n\u00a0\u00a0\u00a0 \u00a0\u00a0\u00a0\u00a0FROM dbo.GapsIslands) a\n\u00a0\u00a0\u00a0 GROUP BY ID, rn\n)\nSELECT ID, SeqNo\n\u00a0\u00a0\u00a0 ,n=ROW_NUMBER() OVER (PARTITION BY ID ORDER BY SeqNo)\n\u00a0\u00a0\u00a0 ,m=ROW_NUMBER() OVER (PARTITION BY ID ORDER BY SeqNo)\/2\nFROM Islands\nCROSS APPLY (VALUES (StartSeqNo),(EndSeqNo)) a(SeqNo)\nORDER BY ID, StartSeqNo;\n<\/pre>\n
We’ve thrown in a couple of row numbers to see if they might help us with the grouping we need.\u00a0 These results are:<\/p>\n
ID\u00a0 SeqNo\u00a0 n\u00a0\u00a0 m\n1\u00a0\u00a0 0\u00a0\u00a0\u00a0\u00a0\u00a0 1\u00a0\u00a0 0\n1\u00a0\u00a0 3\u00a0\u00a0\u00a0\u00a0\u00a0 2\u00a0\u00a0 1\n1\u00a0\u00a0 4\u00a0\u00a0\u00a0\u00a0\u00a0 3\u00a0\u00a0 1\n1\u00a0\u00a0 7\u00a0\u00a0\u00a0\u00a0\u00a0 4\u00a0\u00a0 2\n1\u00a0\u00a0 7\u00a0\u00a0\u00a0\u00a0\u00a0 5\u00a0\u00a0 2\n1\u00a0\u00a0 11\u00a0\u00a0\u00a0\u00a0 6\u00a0\u00a0 3\n1\u00a0\u00a0 11\u00a0\u00a0\u00a0\u00a0 7\u00a0\u00a0 3\n1\u00a0\u00a0 13\u00a0\u00a0\u00a0\u00a0 8\u00a0\u00a0 4\n1\u00a0\u00a0 19\u00a0\u00a0\u00a0\u00a0 9\u00a0\u00a0 4\n1\u00a0\u00a0 22\u00a0\u00a0\u00a0\u00a0 10\u00a0 5\n1\u00a0\u00a0 24\u00a0\u00a0\u00a0\u00a0 11\u00a0 5\n1\u00a0\u00a0 27\u00a0\u00a0\u00a0\u00a0 12\u00a0 6\n<\/pre>\n
We certainly have the numbers in SeqNo that represent the endpoints of our gap and we even have a grouping column (m) that will allow us to group our gap start\/end points, which we arrived at by the totally simplistic method of dividing by two.\u00a0 Now all we have to do is figure out a way to remove the first and last row from the result set!<\/p>\n
Since all the gap endpoints of interest are in groups of two, this brings to mind the HAVING clause.\u00a0 Let’s give that a try.<\/p>\n
WITH Islands AS \n(\n\u00a0\u00a0\u00a0 SELECT ID, StartSeqNo=MIN(SeqNo) - 1, EndSeqNo=MAX(SeqNo) + 1\n\u00a0\u00a0\u00a0 FROM (\n\u00a0\u00a0\u00a0 \u00a0\u00a0\u00a0\u00a0SELECT ID, SeqNo\n\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0 \u00a0\u00a0\u00a0\u00a0\u00a0,rn=SeqNo-ROW_NUMBER() OVER (PARTITION BY ID ORDER BY SeqNo)\n\u00a0\u00a0\u00a0 \u00a0\u00a0\u00a0\u00a0FROM dbo.GapsIslands) a\n\u00a0\u00a0\u00a0 \u00a0GROUP BY ID, rn\n)\nSELECT ID, StartSeqNo=MIN(SeqNo), EndSeqNo=MAX(SeqNo)\nFROM (\n\u00a0\u00a0\u00a0 SELECT ID, SeqNo\n\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0 ,m=ROW_NUMBER() OVER (PARTITION BY ID ORDER BY SeqNo)\/2\n\u00a0\u00a0\u00a0 FROM Islands\n\u00a0\u00a0\u00a0 CROSS APPLY (VALUES (StartSeqNo),(EndSeqNo)) a(SeqNo)) a\nGROUP BY ID, m\nHAVING COUNT(*) = 2\nORDER BY ID, StartSeqNo;\n<\/pre>\n
Inspection of the results set clearly shows we’ve achieved our expected results – the gaps!<\/p>\n
Performance Comparison of Gaps Solutions<\/h2>\n
Performance always counts so let’s see how well this solution performs in a sufficiently large test harness versus the solutions proposed in the MVP Deep Dives book.\u00a0<\/p>\n
In the two test harness scripts we mentioned previously, the code to generate a large test data set looks like this:<\/p>\n
SET NOCOUNT ON\nSET STATISTICS TIME, IO OFF\nCREATE TABLE GapsIslands (ID INT NOT NULL, SeqNo BIGINT NOT NULL);\n\u00a0\nALTER TABLE GapsIslands\n\u00a0ADD CONSTRAINT pk_GapsIslands PRIMARY KEY (ID, SeqNo);\n\u00a0\nDECLARE @Records INT = 1000000;\n\u00a0\n-- Generate a sequence numbers table with 10 unique IDs for a total\n-- of @Records rows, with small gaps around every 500 or so.\nWITH Tally (n) AS \n(\n\u00a0\u00a0\u00a0 SELECT TOP (1+CAST(FLOOR((@Records\/10)\/500.+@Records\/10) AS INT))\n\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0 ROW_NUMBER() OVER (ORDER BY (SELECT NULL))\n\u00a0\u00a0\u00a0 FROM sys.all_columns a CROSS JOIN sys.all_columns b\n)\nINSERT INTO dbo.GapsIslands\nSELECT m, n\nFROM (SELECT TOP 10 n FROM Tally) a(m)\nCROSS APPLY Tally b\nWHERE n % 500 <> m;\nPRINT 'Rows in test harness: ' + CAST(@@ROWCOUNT AS VARCHAR(12));\n\u00a0\n-- Make the gaps wider towards the end\nDECLARE @Gaps INT = 1\nWHILE @Gaps <= 3\nBEGIN\n\u00a0\u00a0\u00a0 WITH Gaps AS (SELECT TOP (@Gaps * 1000) ID, SeqNo FROM GapsIslands ORDER BY SeqNo DESC)\n\u00a0\u00a0\u00a0 UPDATE Gaps\n\u00a0\u00a0\u00a0 SET SeqNo = SeqNo * POWER(10, @Gaps) * (ID + 1);\n\u00a0\u00a0\u00a0 \n\u00a0\u00a0\u00a0 SELECT @Gaps = @Gaps + 1; \nEND\n<\/pre>\n
While reviewing this article, Peter Larsson (alias PESO) suggested an alternative using CROSS APPLY VALUES that may improve the speed.\u00a0 So let’s take a look at that method also.<\/p>\n
WITH cteSource(ID, Seq, Num)\nAS (\n\u00a0\u00a0 SELECT d.ID, f.Seq, f.Num\n\u00a0\u00a0 FROM (\n\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0 SELECT ID,\n\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0 ROW_NUMBER() OVER (PARTITION BY ID ORDER BY MIN(SeqNo)) AS Grp,\n\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0 MIN(SeqNo) AS StartSeqNo,\n\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0 MAX(SeqNo) AS EndSeqNo\n\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0 FROM (\n\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0 SELECT ID, SeqNo,\n\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0 SeqNo - ROW_NUMBER() OVER (PARTITION BY ID ORDER BY SeqNo) AS rn\n\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0 FROM dbo.GapsIslands\n\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0 ) AS a\n\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0 GROUP BY ID,rn\n\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0 ) d\n\u00a0\u00a0 CROSS APPLY (\n\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0 VALUES (d.Grp, d.EndSeqNo + 1),(d.Grp - 1, d.StartSeqNo - 1)\n\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0 ) AS f(Seq, Num)\n)\nSELECT ID, MIN(Num) AS StartSeqNo, MAX(Num) AS EndSeqNo\nFROM cteSource\nGROUP BY ID, Seq\nHAVING COUNT(*) = 2;\u00a0 \n<\/pre>\n
Using the gaps solutions identified previously, a quick check of the results at 1,000,000 rows delivers these results (run Gaps Test Harness #2.sql<\/i><\/b>).<\/p>\n
\n\n\n\n\n\n\n\n\n\n
\n
Gaps<\/b><\/p>\n<\/td>\n
\n
Test Harness – 1,000,000 Rows<\/b><\/p>\n<\/td>\n<\/tr>\n
\n
Solution<\/b><\/p>\n<\/td>\n
\n
CPU (ms)<\/b><\/p>\n<\/td>\n
\n
Elapsed Time (ms)<\/b><\/p>\n<\/td>\n
\n
Logical IOs<\/b><\/p>\n<\/td>\n<\/tr>\n
\n
SQL MVP Deep Dives Gaps #1<\/p>\n<\/td>\n
\n
967<\/p>\n<\/td>\n
\n
827<\/p>\n<\/td>\n
\n
22997<\/p>\n<\/td>\n<\/tr>\n
\n
SQL MVP Deep Dives Gaps #2<\/p>\n<\/td>\n
\n
5258<\/p>\n<\/td>\n
\n
1653<\/p>\n<\/td>\n
\n
3192923<\/p>\n<\/td>\n<\/tr>\n
\n
SQL MVP Deep Dives Gaps #3<\/p>\n<\/td>\n
\n
1840<\/p>\n<\/td>\n
\n
1834<\/p>\n<\/td>\n
\n
5278<\/p>\n<\/td>\n<\/tr>\n
\n
CROSS APPLY VALUES – Islands to Gaps<\/p>\n<\/td>\n
\n
718<\/p>\n<\/td>\n
\n
933<\/p>\n<\/td>\n
\n
2639<\/p>\n<\/td>\n<\/tr>\n
\n
CAV – Islands to Gaps (by PESO)<\/p>\n<\/td>\n
\n
640<\/p>\n<\/td>\n
\n
711<\/p>\n<\/td>\n
\n
2639<\/p>\n<\/td>\n<\/tr>\n<\/tbody>\n<\/table>\n<\/div>\n
Elapsed times for the new CAV (Cross Apply Values) methods appear quite competitive, and both logical IOs and CPU time appear improved.\u00a0 In a moment we’ll see if these results can be reproduced and how they scale.<\/p>\n
An Alternative Islands Solution<\/h2>\n
If it is possible to convert Islands to Gaps, perhaps it is also possible to convert Gaps to Islands.\u00a0 Let’s consider a data transformation as follows:<\/p>\n
\"1842-clip_image004.jpg\"<\/figure>\n
\u00a0<\/p>\n
For this solution, we’ll take the end point and add one, while we subtract one from the start point.\u00a0 We need to add a row, and that row will be the first and last sequence number in our series. \u00a0Finally, we’ll un-pivot and add a row number that groups each resulting sequence number in pairs (note that you could either add 1 to or subtract 1 from the row number before dividing by 2).<\/p>\n
So now, skipping the intermediate explanatory step as it is quite similar to what we did before, we can arrive at the following code to calculate islands from gaps:<\/p>\n
WITH Gaps AS \n(\n\u00a0\u00a0\u00a0 SELECT ID, StartSeqNo=SeqNo + 1, EndSeqNo=(\n\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0 SELECT MIN(B.SeqNo)\n\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0 FROM dbo.GapsIslands AS B\n\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0 WHERE B.ID = A.ID AND B.SeqNo > A.SeqNo) - 1\n\u00a0\u00a0\u00a0 FROM dbo.GapsIslands AS A\n\u00a0\u00a0\u00a0 WHERE NOT EXISTS (\n\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0 SELECT *\n\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0 FROM dbo.GapsIslands AS B\n\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0 WHERE B.ID = A.ID AND B.SeqNo = A.SeqNo + 1) AND\n\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0 SeqNo < (SELECT MAX(SeqNo) \n\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0 FROM dbo.GapsIslands B \n\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0 WHERE B.ID = A.ID)\n)\n\u00a0\u00a0\u00a0 ,MinMax AS \n(\n\u00a0\u00a0\u00a0 SELECT ID, MinSeqNo=MIN(SeqNo), MaxSeqNo=MAX(SeqNo)\n\u00a0\u00a0\u00a0 FROM dbo.GapsIslands\n\u00a0\u00a0\u00a0 GROUP BY ID\n)\nSELECT ID, MinSeqNo=MIN(SeqNo), MaxSeqNo=MAX(SeqNo)\nFROM (\n\u00a0\u00a0\u00a0 SELECT ID, SeqNo, m=(ROW_NUMBER() OVER (PARTITION BY ID ORDER BY SeqNo)-1)\/2\n\u00a0\u00a0\u00a0 FROM (\n\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0 SELECT ID, MinSeqNo=EndSeqNo+1, MaxSeqNo=StartSeqNo-1 \n\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0 FROM Gaps\n\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0 UNION ALL \n\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0 SELECT ID, MinSeqNo, MaxSeqNo\n\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0 FROM MinMax) a\n\u00a0\u00a0\u00a0 CROSS APPLY (VALUES (MinSeqNo),(MaxSeqNo)) b (SeqNo)) b\nGROUP BY ID, m;\n<\/pre>\n
The Gaps CTE above is the SQL MVP Deep Dives fastest (elapsed time) approach to gaps and the MinMax CTE is used to compute the additional row we’ll need to go from gaps to islands.<\/p>\n
So how do these results compare to our fastest islands solutions at 1,000,000 rows?<\/p>\n
\n\n\n\n\n\n\n\n
\n
Islands<\/b><\/p>\n<\/td>\n
\n
Test Harness – 1,000,000 Rows<\/b><\/p>\n<\/td>\n<\/tr>\n
\n
Solution<\/b><\/p>\n<\/td>\n
\n
CPU (ms)<\/b><\/p>\n<\/td>\n
\n
Elapsed Time (ms)<\/b><\/p>\n<\/td>\n
\n
Logical IOs<\/b><\/p>\n<\/td>\n<\/tr>\n
\n
SQL MVP Deep Dives Islands #1<\/p>\n<\/td>\n
\n
1217<\/p>\n<\/td>\n
\n
1256<\/p>\n<\/td>\n
\n
10568<\/p>\n<\/td>\n<\/tr>\n
\n
SQL MVP Deep Dives Islands #3<\/p>\n<\/td>\n
\n
593<\/p>\n<\/td>\n
\n
727<\/p>\n<\/td>\n
\n
2641<\/p>\n<\/td>\n<\/tr>\n
\n
CROSS APPLY VALUES – Gaps to Islands<\/p>\n<\/td>\n
\n
1358<\/p>\n<\/td>\n
\n
890<\/p>\n<\/td>\n
\n
25690<\/p>\n<\/td>\n<\/tr>\n<\/tbody>\n<\/table>\n<\/div>\n
The SQL MVP Deep Dives Islands solution #3 still wins the elapsed time race but our approach is a respectable showing, being solidly in second place in terms of elapsed time.\u00a0 It appears that parallelism accounts for this positioning, as CPU for the CAV – Gaps to Islands solution exceeds the elapsed time.\u00a0 These results may be reproduced by running Islands Test Harness #2.sql<\/i><\/b>.<\/p>\n
Scalability<\/h2>\n
Using each #2 test harness, we’ll generate test data from 200,000 to 2,000,000 rows and chart the results for comparison.\u00a0 You’ll see that the final results appear to be a bit mixed.<\/p>\n
\"1842-img4B.jpg\"<\/figure>\n
\u00a0<\/p>\n
\"1842-img4C1.jpg\"<\/figure>\n
\u00a0<\/p>\n
\"1842-img4D.jpg\"<\/figure>\n
\u00a0<\/p>\n
For the CAV (Cross Apply Values) solutions for islands to gaps, their ranking appears as #1 for CPU across the board, although it is a slim lead and the convergence at 2M rows suggests that it may start lagging behind above that.\u00a0 For elapsed time, the CAV solutions appear to be basically tied with MVP DD S#1 up to about 1.2M rows, but then they fall to second place ranking above that row count.\u00a0 In logical IOs they are the clear winner across the board (the SQL MVP Deep Dive solution #2 was omitted due to scaling of the chart).\u00a0 MVP DD S#3 does get good marks for logical IOs.<\/p>\n
\"1842-img48.jpg\"<\/figure>\n
\u00a0<\/p>\n
\"1842-img49.jpg\"<\/figure>\n
\u00a0<\/p>\n
\"1842-img4A.jpg\"<\/figure>\n
\u00a0<\/p>\n
For the CAV (Cross Apply Values) solution of gaps to islands, it manages to achieve a #2 ranking for CPU above 1M rows but lagged slightly behind prior to that.\u00a0 For elapsed time, above 1.8M rows it seems to have achieved the #1 ranking of the 3 solutions (below 1.8M it is #2), but our scaling tests don’t go above 2M rows so we’re not sure how long it would maintain that lead.\u00a0 However on logical IOs, it is a clear #3 (and would probably remain so) regardless of the number of rows in the test harness.<\/p>\n
It also appears that for the CAV gaps to islands solution, we lost the parallelism that resulted in the highly favorable elapsed time result, possibly because SQL had cached a non-parallelized execution plan at the lower row counts.<\/p>\n
Ultimately the CAV (Cross Apply Values) approaches may offer benefits under some conditions but your choice should be made based on a careful analysis of which solution works best for your constraints of data rows, parallelism and the specific resource that you most wish to conserve (CPU, elapsed time or logical IOs).<\/p>\n
Gaps and Islands<\/h2>\n
A Google search for anything similar to an approach like this for calculating islands and gaps came up empty, but we’d love to hear if anyone has published anything on it before or has other improvements to suggest.\u00a0 And we’d most certainly be thrilled to hear from our valued readers if this solution has been of benefit to them. Perhaps in SQL 2012 someone can come up with something faster utilizing a window frame.\u00a0 We look forward to hearing about that too.<\/p>\n
\u00a0Timing tests run for this article were done in SQL Server 2008 R2 on a Dell Inspiron Core i5 2.4 GHz with 8GB of memory.\u00a0<\/p>\n
\u00a0Until next time<\/p>\n
The Excel file with the results of the test, and the graphs, is attached, as are the four SQL source files for the tests. Links to them can be found at the head of this article<\/p>\n<\/div>\n\n\n\n
If you liked this article, you might also like<\/em> Introduction to Gaps and Islands Analysis<\/a><\/p>\n\n\n\n
 <\/div>\n\n\n\n
\u00a0<\/div>\n\n\n\n
\n    
FAQs<\/h2>\n\n                        
1. What is the gaps and islands problem in SQL?<\/h3>\n            
\n                
The gaps and islands problem is the task of identifying unbroken runs of sequential values in a column (islands) and the missing values between those runs (gaps). It appears in any situation where you have a sequence that may have breaks – an IDENTITY column where rows have been deleted, a date column where some dates are missing, or a package-scan sequence where some packages were not scanned. A typical result lists each island as a start-end range (e.g., 1-10, 15-18) and each gap similarly (e.g., 11-14, 19-19). The number of gaps is always one less than the number of islands in a given sequence.<\/p>\n            <\/div>\n                    
2. How do you solve the gaps and islands problem in SQL Server?<\/h3>\n            
\n                
The two most efficient set-based approaches are: (1) the row-number difference method, where you subtract a ROW_NUMBER() value from the sequence value – consecutive values in the same island produce the same difference, so you can GROUP BY that difference to find island boundaries; and (2) a self-join approach that finds rows whose neighbours are non-consecutive, marking those as island boundaries. This article demonstrates both, plus an alternative that converts the islands problem to a gaps problem and back. All approaches are pure T-SQL with no cursors, and benchmark test data shows each scales differently depending on the shape of the input data.<\/p>\n            <\/div>\n                    
3. What is the fastest way to find gaps in a SQL sequence?<\/h3>\n            
\n                
The fastest approach depends on the shape of the data – specifically the ratio of gap rows to island rows. For data with few gaps, a self-join that compares each row to the previous row (using LEAD() or LAG() in SQL Server 2012+) is very fast because most comparisons succeed quickly. For data with many gaps, the row-number difference approach is often faster because it processes each row exactly once. The article’s performance test harness benchmarks both approaches at 200,000 to 2,000,000 rows so you can see the crossover point for your own data shape.<\/p>\n            <\/div>\n                    
4. What is the difference between gaps and islands in SQL?<\/h3>\n            
\n                
Islands are unbroken runs of consecutive values in a sequence – groups where each value is exactly one more than the previous value. Gaps are the missing values between islands – ranges where no rows exist. In a sample set like (1, 2, 5, 6, 8, 9, 10), the islands are (1-2), (5-6), and (8-10); the gaps are (3-4) and (7-7). The two problems are complementary: solving one typically gets you the data you need to compute the other. The number of gaps is always one less than the number of islands when both are bounded by the same dataset.<\/p>\n            <\/div>\n            <\/section>\n","protected":false},"excerpt":{"rendered":"
Efficient SQL Server solutions to the gaps and islands problem – detecting unbroken sequences and the gaps between them. Covers the author’s alternative approach and a performance test harness comparing it with Itzik Ben-Gan’s four solutions from SQL Server MVP Deep Dives.…<\/p>\n","protected":false},"author":221942,"featured_media":0,"comment_status":"open","ping_status":"closed","sticky":false,"template":"","format":"standard","meta":{"_acf_changed":false,"footnotes":""},"categories":[143531],"tags":[4150,5134,4252],"coauthors":[6800],"class_list":["post-1674","post","type-post","status-publish","format-standard","hentry","category-t-sql-programming-sql-server","tag-sql","tag-sql-prompt","tag-t-sql-programming"],"acf":[],"_links":{"self":[{"href":"https:\/\/www.red-gate.com\/simple-talk\/wp-json\/wp\/v2\/posts\/1674","targetHints":{"allow":["GET"]}}],"collection":[{"href":"https:\/\/www.red-gate.com\/simple-talk\/wp-json\/wp\/v2\/posts"}],"about":[{"href":"https:\/\/www.red-gate.com\/simple-talk\/wp-json\/wp\/v2\/types\/post"}],"author":[{"embeddable":true,"href":"https:\/\/www.red-gate.com\/simple-talk\/wp-json\/wp\/v2\/users\/221942"}],"replies":[{"embeddable":true,"href":"https:\/\/www.red-gate.com\/simple-talk\/wp-json\/wp\/v2\/comments?post=1674"}],"version-history":[{"count":8,"href":"https:\/\/www.red-gate.com\/simple-talk\/wp-json\/wp\/v2\/posts\/1674\/revisions"}],"predecessor-version":[{"id":110218,"href":"https:\/\/www.red-gate.com\/simple-talk\/wp-json\/wp\/v2\/posts\/1674\/revisions\/110218"}],"wp:attachment":[{"href":"https:\/\/www.red-gate.com\/simple-talk\/wp-json\/wp\/v2\/media?parent=1674"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"https:\/\/www.red-gate.com\/simple-talk\/wp-json\/wp\/v2\/categories?post=1674"},{"taxonomy":"post_tag","embeddable":true,"href":"https:\/\/www.red-gate.com\/simple-talk\/wp-json\/wp\/v2\/tags?post=1674"},{"taxonomy":"author","embeddable":true,"href":"https:\/\/www.red-gate.com\/simple-talk\/wp-json\/wp\/v2\/coauthors?post=1674"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}