Finding islands – 4 methods in Oracle

Submitted by learn-with-vide... on Sat, 2014-01-18 15:12
articles: 
SQL & PL/SQL

Finding islands are classic problems in PL/SQL. The basic concept is that you have some sort of numbers, like these: 1, 2, 3, 5, 6, 8, 9, 10, 15, 20, 21, 22, 23, 25, 26. The islands problem involves identifying ranges of existing values. For these numbers, the solution will be as follows:
first_island_element last_island_element
1 3
5 6
8 10
15 15
20 23
25 26

First, run the following code, to create tab1 table:

CREATE TABLE tab1
(
col1 INTEGER
);

Then, insert a few rows:

INSERT INTO tab1 VALUES (1);
INSERT INTO tab1 VALUES (2);
INSERT INTO tab1 VALUES (3);
INSERT INTO tab1 VALUES (5);
INSERT INTO tab1 VALUES (6);
INSERT INTO tab1 VALUES (8);
INSERT INTO tab1 VALUES (9);
INSERT INTO tab1 VALUES (10);
INSERT INTO tab1 VALUES (15);
INSERT INTO tab1 VALUES (20);
INSERT INTO tab1 VALUES (21);
INSERT INTO tab1 VALUES (22);
INSERT INTO tab1 VALUES (23);
INSERT INTO tab1 VALUES (25);
INSERT INTO tab1 VALUES (26);

COMMIT;

With data, you can take care of solving the islands problem…

    Finding Island With Classic PL/SQL Query

Here’s the query required to implement this problem in classic PL/SQL:

SELECT MIN (aa.col1) AS first_island_elemnt, MAX (aa.col1) AS last_island_element
FROM (SELECT t.col1,
(SELECT MIN (tt.col1)
FROM tab1 tt
WHERE tt.col1 >= t.col1
AND NOT EXISTS (SELECT *
FROM tab1 ttt
WHERE ttt.col1 = tt.col1 + 1)) AS col2
FROM tab1 t) aa
GROUP BY aa.col2
ORDER BY first_island_elemnt;

This PL/SQL code generates the following output:

first_island_element last_island_element
1 3
5 6
8 10
15 15
20 23
25 26

This solution has two drawbacks: is very slowly and very complicated.

    Finding Islands With Classic PL/SQL And CTE

The second solution is a modification of the first. Use CTE (Common Table Expressions) to simplify the query.

WITH aa AS
(SELECT t.col1,
(SELECT MIN (tt.col1)
FROM tab1 tt
WHERE tt.col1 >= t.col1
AND NOT EXISTS (SELECT *
FROM tab1 ttt
WHERE ttt.col1 = tt.col1 + 1)) AS col2
FROM tab1 t)
SELECT MIN (aa.col1) AS first_island_elemnt,
MAX (aa.col1) AS last_island_element
FROM aa
GROUP BY aa.col2
ORDER BY first_island_elemnt;

Query logic has been simplified, but the explain plan has not changed.

    Finding Islands With Analytic Functions

The third solution is also one that calculates a group identifier, but using analytic functions (also known as window functions).

SELECT MIN (col1) AS first_island_elemnt, MAX (col1) AS last_island_element
FROM (SELECT col1, col1 - ROW_NUMBER () OVER (ORDER BY col1) AS col2
FROM tab1) tt
GROUP BY col2
ORDER BY first_island_elemnt;

This solution is concise and simple. The query is also highly efficient.

    Finding Islands With DENSE_RANK

One of the most efficient solutions to the islands problem involves using ranking function: DENSE_RANK. You use the this function to create a sequence of integers in col1 ordering. Then calculate the difference between col1 and the dense rank (col2)

WITH tt AS
(SELECT col1, col1 - DENSE_RANK () OVER (ORDER BY col1) AS col2
FROM tab1)
SELECT MIN (col1) AS first_island_elemnt, MAX (col1) AS last_island_element
FROM tt
GROUP BY col2
ORDER BY first_island_elemnt;

»