1. Get rid of all advertisements and get unlimited access to documents by upgrading to Premium Membership. Upgrade to Premium Now and also get a Premium Badge!

Finding islands – 4 methods in Oracle

Discussion in 'SQL PL/SQL' started by sushant, Mar 20, 2014.

  1. sushant

    sushant Guest

    Finding islands – 4 methods in Oracle

    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:

    Code (SQL):
    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:

    Code (SQL):
    CREATE TABLE tab1
    (
    col1 INTEGER
    );
    Then, insert a few rows:

    Code (SQL):
    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:

    Code (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:

    Code (SQL):
    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.

    Code (SQL):
    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).

    Code (SQL):
    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)

    Code (SQL):
    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;