MySQL - Island Analysis - Find Islands in Number Sequence
Understanding how to identify islands is useful in data analysis.
In this post, we will go over different techniques of using Self Join
and Window Functions Lead()
and Lag()
to identify islands in a number sequence.
Islands identified will be presented as a range.
Problem
The sample Test numbers table contains 4 islands. We need to create a SQL script to identify them.
number |
---|
1 |
2 |
5 |
6 |
7 |
8 |
9 |
10 |
12 |
13 |
14 |
15 |
20 |
Execution of the SQL script should output lower and upper bound of each island.
island_start | island_end |
---|---|
1 | 2 |
5 | 10 |
12 | 15 |
20 | 20 |
Example Data
create table Test (
number INT
);
-- Island 1
insert into Test (number) values (1);
insert into Test (number) values (2);
-- Island 2
insert into Test (number) values (5);
insert into Test (number) values (6);
insert into Test (number) values (7);
insert into Test (number) values (8);
insert into Test (number) values (9);
insert into Test (number) values (10);
-- Island 3
insert into Test (number) values (12);
insert into Test (number) values (13);
insert into Test (number) values (14);
insert into Test (number) values (15);
-- Island 4
insert into Test (number) values (20);
Use
DB-Fiddle to execute SQL scripts on sample data.
Solution - Find Islands Using Self Join
Find the Start Number of Each Island
We can left join
the table with itself on a join key offset by 1 to check if the current number is the start of an island.
This is true if we cannot find a previous number that's exactly 1 less than the current number. prev_num
column would be null
in this case.
SELECT l.number AS curr_num
,r.number AS prev_num
FROM Test l
-- Do we have a previous number in the sequence that's 1 less than the current number?
LEFT JOIN Test r ON l.number = r.number + 1
ORDER BY l.number
In the following illustration, we can see that curr_num
is the start number of an island if prev_num
is null.
Find the End Number of Each Island
We can left join
the table with itself on a join key offset by 1 to check if the current number is the end of an island.
This is true if we cannot find a next number that's exactly 1 greater than the current number. next_num
column would be null
in this case.
SELECT l.number AS curr_num
,r.number AS next_num
FROM Test l
-- Do we have a next number in the sequence that's 1 greater than the current number?
LEFT JOIN Test r ON l.number = r.number - 1
ORDER BY l.number
In the following illustration, we can see that curr_num
is the end number of an island if next_num
is null.
Present Islands as Range
The first CTE island_start_nums
stores start numbers of islands. Each number is sorted ascendingly and assigned an unique row_num
value.
The second CTE island_end_nums
stores end numbers of islands. Each number is sorted ascendingly and assigned an unique row_num
value.
Finally, we inner join the first and second CTE on row_num
key to present islands as range.
WITH island_start_nums
AS (
SELECT l.number AS island_start
,row_number() OVER (
ORDER BY l.number ASC
) AS row_num
FROM Test l
LEFT JOIN Test r ON l.number = r.number + 1
WHERE r.number IS NULL
)
,island_end_nums
AS (
SELECT l.number AS island_end
,row_number() OVER (
ORDER BY l.number ASC
) AS row_num
FROM Test l
LEFT JOIN Test r ON l.number = r.number - 1
WHERE r.number IS NULL
)
SELECT s.island_start
,e.island_end
FROM island_start_nums s
INNER JOIN island_end_nums e ON s.row_num = e.row_num;
The following screenshot illustrates that island_start_nums
CTE inner join island_end_nums
CTE on row_num
Key to present islands as range.
Here is the query output with the number range of each island.
island_start | island_end |
---|---|
1 | 2 |
5 | 10 |
12 | 15 |
20 | 20 |
Solution - Find Islands Using Row_Number
The first column number
contains a list of numbers that we need to find islands.
The second column row_num
contains the row number which makes use of the Row_Number
window function to generate a sequential numbers for our numbers.
The third column diff_group
contains the difference between column number
and column row_num
.
Each time the difference increases, we have identified a new island as the row number falls further behind our number.
SELECT number
,row_number() OVER (
ORDER BY number
) AS row_num
,number - row_number() OVER (
ORDER BY number
) AS diff_group
FROM Test t
The following screenshot illustrates the logics we described to identify islands in our number sequence.
We have successfully identified all the number islands. To present islands as range, we simply group by diff_group
and use Min
function to get the lower bound of each island and use Max
function to get the upper bound of each island.
WITH island_analysis
AS (
SELECT number
,row_number() OVER (
ORDER BY number
) AS row_num
,number - row_number() OVER (
ORDER BY number
) AS diff_group
FROM Test t
)
SELECT min(number) AS island_start
,max(number) AS island_end
FROM island_analysis i
GROUP BY diff_group;
Here is the same output with the number range of each island.
island_start | island_end |
---|---|
1 | 2 |
5 | 10 |
12 | 15 |
20 | 20 |
Solution - Find Islands Using Dense_Rank
The Row_Number
window function is useful in identifying islands within a number sequence that does NOT have duplicate numbers.
However, our results would be incorrect if we have duplicate numbers in our number sequence as you can see in the following illustration.
This is because Row_Number
always increments each row by 1 even for identical numbers.
This screenshot illustrates that our island results is now incorrect when a duplicate number 7 is introduced in the number sequence. Number 7 now belongs to two different islands!
How do we adjust our solution to manage duplicates in the number sequence?
We could remove duplicates first before performing island analysis.
Alternatively, we can utilize the Dense_Rank
window function that returns the rank of each row with no gaps in the ranking values.
The rank of a specific row is one plus the number of distinct rank values that come before that specific row.
SELECT number
,dense_rank() OVER (
ORDER BY number
) AS row_num
,number - dense_rank() OVER (
ORDER BY number
) AS diff_group
FROM Test t
The screenshot illustrates that by simply substituting Row_Number
window function with Dense_Rank
window function, our island results will no longer be impacted by duplicates!
With the help of Dense_Rank
window function, we have again successfully identified all the number islands even if duplicate numbers.
To present islands as range, we simply group by diff_group
and use Min
function to get the lower bound of each island and use Max
function as before to get the upper bound of each island.
WITH island_analysis
AS (
SELECT number
,dense_rank() OVER (
ORDER BY number
) AS row_num
,number - dense_rank() OVER (
ORDER BY number
) AS diff_group
FROM Test t
)
SELECT min(number) AS island_start
,max(number) AS island_end
FROM island_analysis i
GROUP BY diff_group;
Here is the same output again with the number range of each island and we will be able to manage duplicates in case there is any in the number sequence.
island_start | island_end |
---|---|
1 | 2 |
5 | 10 |
12 | 15 |
20 | 20 |