SQL Overlap Test

Many times I come across SQL where the developer is trying to check for overlap between two ranges (usually date ranges, but sometimes numbers). For example, to meet the requirement "select all employees whose hired from and to dates overlap with the project start and end dates".

The developer sketches out all the possible overlap scenarios and finds four:

1) End of range A overlaps start of range B:
A----
    B---------

2) Start of range A overlaps end of range B:
    A--------
B----

3) Range A falls entirely within range B:
    A---
B--------------

4) Range B falls entirely within range A:
A--------------
    B---

This leads to SQL like this (assuming all values are not null):

where (a.start < b.start 
       and a.end between b.start and b.end)
or    (a.start between b.start
       and b.end and a.end > b.end)
or    (a.start between b.start and b.end
       and a.end between b.start and b.end)
or    (b.start between a.start and a.end
       and b.end between a.start and a.end)

If, as is often the case, the end dates are allowed to be null, meaning "forever", then the SQL becomes yet more complex. In some cases I have seen attempts at this where the developer has got it wrong and missed out one of the cases altogether.

In fact it is much easier to look at the cases where A and B do not overlap, because there are only two such cases:

1) Range A ends before range B starts:
A---
       B-----

2) Range A starts after range B ends:
       A-----
B---

This leads to the much simpler SQL:

where not (a.end < b.start or a.start > b.end)

which can be rearranged to the even simpler (though perhaps less intuitive):

where a.end >= b.start 
and   a.start <= b.end

Even if we have to allow for null end dates this is now very simple:

where nvl(a.end,b.start) >= b.start 
and   a.start <= nvl(b.end,a.start)

I don't claim that any of the above is original, I am sure this algorithm appears in many SQL and other books. But I see variants of the long-winded version (sometimes bug-ridden ones) so often I thought it worth documenting here so I can point to it in future.

Chris Date Seminar

Chris Date is giving a 2 day seminar called SQL and Relational Theory - How to Write Accurate SQL Code in Edinburgh, 13th-14th May 2010. I really wish I could go to it myself. I attended one of his seminars back in about 1997 and it was both riveting and highly educational.

What does GROUP BY CUBE do?

This is one of those "new" features that has actually been around for a long time, but I had never used it. Then recently I was asked to tune a long-running report, and it occured to me that it might just be what I needed.

The report consisted of 4 summary queries, each of which presented the same data but summarised by a different "dimension". Imagine it was based on the EMP table, then the report would show:

Employee Summary by Job
-----------------------

Job                                          # Emps  Total Sal
---------------------------------------- ---------- ----------
CLERK                                             4       4150
ANALYST                                           2       6000
MANAGER                                           3       8275
SALESMAN                                          4       5600
PRESIDENT                                         1       5000
                                         ---------- ----------
                                                 14      29025
                                                 

Employee Summary by Manager
---------------------------

Mgr                                          # Emps  Total Sal
---------------------------------------- ---------- ----------
7566                                              2       6000
7698                                              5       6550
7782                                              1       1300
7788                                              1       1100
7839                                              3       8275
7902                                              1        800
                                         ---------- ----------
                                                 14      29025

Employee Summary by Department
------------------------------

Dept                                         # Emps  Total Sal
---------------------------------------- ---------- ----------
10                                                3       8750
20                                                5      10875
30                                                6       9400
                                         ---------- ----------
                                                 14      29025

That is only 3 queries, but you get the idea.

Each query took 10 minutes to run (reasonable given the complexity of the query and the amount of data), so the whole report took 40 minutes.

My goal was to reduce the time to more like 10 minutes - perhaps by pre-computing the results grouped by all 4 dimensions into a temporary table and then reporting on that. However, it occured to me that GROUP BY CUBE might be what I needed, so I tried it out. Here is a simple query:

SQL> select job, mgr, deptno, count(*) numemps, sum(sal) tots
  2  from emp
  3  group by cube(job, mgr, deptno);

JOB              MGR     DEPTNO    NUMEMPS     TOTSAL
--------- ---------- ---------- ---------- ----------
                                         1       5000
                                        14      29025
                             10          1       5000
                             10          3       8750
                             20          5      10875
                             30          6       9400
                7566                     2       6000
                7566         20          2       6000
                7698                     5       6550
                7698         30          5       6550
                7782                     1       1300
                7782         10          1       1300
                7788                     1       1100
                7788         20          1       1100
                7839                     3       8275
                7839         10          1       2450
                7839         20          1       2975
                7839         30          1       2850
                7902                     1        800
                7902         20          1        800
CLERK                                    4       4150
CLERK                        10          1       1300
CLERK                        20          2       1900
CLERK                        30          1        950
CLERK           7698                     1        950
CLERK           7698         30          1        950
CLERK           7782                     1       1300
CLERK           7782         10          1       1300
CLERK           7788                     1       1100
CLERK           7788         20          1       1100
CLERK           7902                     1        800
CLERK           7902         20          1        800
ANALYST                                  2       6000
ANALYST                      20          2       6000
ANALYST         7566                     2       6000
ANALYST         7566         20          2       6000
MANAGER                                  3       8275
MANAGER                      10          1       2450
MANAGER                      20          1       2975
MANAGER                      30          1       2850
MANAGER         7839                     3       8275
MANAGER         7839         10          1       2450
MANAGER         7839         20          1       2975
MANAGER         7839         30          1       2850
SALESMAN                                 4       5600
SALESMAN                     30          4       5600
SALESMAN        7698                     4       5600
SALESMAN        7698         30          4       5600
PRESIDENT                                1       5000
PRESIDENT                    10          1       5000
PRESIDENT                    10          1       5000

52 rows selected.

Buried in amongst all those rows is all the data I need. There is a GROUPING function that can be used to see which group a row belongs to:

SQL> select job, mgr, deptno, count(*) numemps, sum(sal) totsal
  2  ,      grouping(job) gj, grouping(mgr) gm, grouping(deptno) gd
  3  from emp
  4  group by cube(job, mgr, deptno);

JOB              MGR     DEPTNO    NUMEMPS     TOTSAL         GJ         GM         GD
--------- ---------- ---------- ---------- ---------- ---------- ---------- ----------
                                         1       5000          1          0          1
                                        14      29025          1          1          1
                             10          1       5000          1          0          0
                             10          3       8750          1          1          0
                             20          5      10875          1          1          0
                             30          6       9400          1          1          0
                7566                     2       6000          1          0          1
                7566         20          2       6000          1          0          0
                7698                     5       6550          1          0          1
                7698         30          5       6550          1          0          0
                7782                     1       1300          1          0          1
                7782         10          1       1300          1          0          0
                7788                     1       1100          1          0          1
                7788         20          1       1100          1          0          0
                7839                     3       8275          1          0          1
                7839         10          1       2450          1          0          0
                7839         20          1       2975          1          0          0
                7839         30          1       2850          1          0          0
                7902                     1        800          1          0          1
                7902         20          1        800          1          0          0
CLERK                                    4       4150          0          1          1
CLERK                        10          1       1300          0          1          0
CLERK                        20          2       1900          0          1          0
CLERK                        30          1        950          0          1          0
CLERK           7698                     1        950          0          0          1
CLERK           7698         30          1        950          0          0          0
CLERK           7782                     1       1300          0          0          1
CLERK           7782         10          1       1300          0          0          0
CLERK           7788                     1       1100          0          0          1
CLERK           7788         20          1       1100          0          0          0
CLERK           7902                     1        800          0          0          1
CLERK           7902         20          1        800          0          0          0
ANALYST                                  2       6000          0          1          1
ANALYST                      20          2       6000          0          1          0
ANALYST         7566                     2       6000          0          0          1
ANALYST         7566         20          2       6000          0          0          0
MANAGER                                  3       8275          0          1          1
MANAGER                      10          1       2450          0          1          0
MANAGER                      20          1       2975          0          1          0
MANAGER                      30          1       2850          0          1          0
MANAGER         7839                     3       8275          0          0          1
MANAGER         7839         10          1       2450          0          0          0
MANAGER         7839         20          1       2975          0          0          0
MANAGER         7839         30          1       2850          0          0          0
SALESMAN                                 4       5600          0          1          1
SALESMAN                     30          4       5600          0          1          0
SALESMAN        7698                     4       5600          0          0          1
SALESMAN        7698         30          4       5600          0          0          0
PRESIDENT                                1       5000          0          0          1
PRESIDENT                                1       5000          0          1          1
PRESIDENT                    10          1       5000          0          0          0
PRESIDENT                    10          1       5000          0          1          0

Based on that, I can filter out the rows I'm not interested in and format the results like this:

SQL> select case when gj=0 and gm=1 and gd=1 then 'Job'
  2              when gj=1 and gm=0 and gd=1 then 'Manager'
  3              when gj=1 and gm=1 and gd=0 then 'Dept'
  4              end as keytype
  5  ,      case when gj=0 and gm=1 and gd=1 then job
  6              when gj=1 and gm=0 and gd=1 then to_char(mgr)
  7              when gj=1 and gm=1 and gd=0 then to_char(deptno)
  8              end as keyval
  9  ,      numemps, totsal
 10  from
 11  (
 12  select job, mgr, deptno, count(*) numemps, sum(sal) totsal
 13  ,      grouping(job) gj, grouping(mgr) gm, grouping(deptno) gd
 14  from emp
 15  group by cube(job, mgr, deptno)
 16  )
 17  where (gj=0 and gm=1 and gd=1)
 18  or    (gj=1 and gm=0 and gd=1)
 19  or    (gj=1 and gm=1 and gd=0);

KEYTYPE KEYVAL                                      NUMEMPS     TOTSAL
------- ---------------------------------------- ---------- ----------
Manager 7566                                              2       6000
        7698                                              5       6550
        7782                                              1       1300
        7788                                              1       1100
        7839                                              3       8275
        7902                                              1        800
                                                          1       5000
*******                                          ---------- ----------
sum                                                      14      29025
Job     ANALYST                                           2       6000
        CLERK                                             4       4150
        MANAGER                                           3       8275
        PRESIDENT                                         1       5000
        SALESMAN                                          4       5600
*******                                          ---------- ----------
sum                                                      14      29025
Dept    10                                                3       8750
        20                                                5      10875
        30                                                6       9400
*******                                          ---------- ----------
sum                                                      14      29025

... which gives me the breakdown I want in a single query, and provides the performance boost I was hoping for!

"Pivot" Queries

One of the frequently asked questions on SQL forums is how to present data “horizontally” rather than “vertically”, known as a “pivot query”. For example, instead of this:

DEPTNO      JOB         HEADCOUNT
----------  ---------  ----------
10          CLERK               1
10          MANAGER             1
20          ANALYST             2
20          CLERK               2
20          MANAGER             1
30          CLERK               1
30          MANAGER             1
30          SALESMAN            4

… people would like to know how to produce this:

DEPTNO         ANALYST       CLERK     MANAGER    SALESMAN
----------  ----------  ----------  ----------  ----------
10                               1           1
20                   2           2           1
30                               1           1           4

In Oracle, the normal way is to write a query using DECODE like this:

select deptno
, count(DECODE(job,'ANALYST', 1)) as "ANALYST"
, count(DECODE(job,'CLERK', 1)) as "CLERK"
, count(DECODE(job,'MANAGER', 1)) as "MANAGER"
, count(DECODE(job,'SALESMAN', 1)) as "SALESMAN"
from emp
group by deptno
order by deptno;

The DECODE ensures that the jobs go in the right columns.
Now this type of query is quite easy to write (when you know how), but is also quite laborious; also, if the list of jobs changes then the query needs to be changed too.
To make producing such queries a “piece of cake” I have built a package called pivot that can be used to generate the SQL like this:
begin
pivot.print_pivot_query
( 'deptno'
, 'job'
, 'emp'
, '1'
, agg_types => 'count'
);
end;
/
select deptno
, count(DECODE(job,'ANALYST', 1)) as "ANALYST"
, count(DECODE(job,'CLERK', 1)) as "CLERK"
, count(DECODE(job,'MANAGER', 1)) as "MANAGER"
, count(DECODE(job,'SALESMAN', 1)) as "SALESMAN"
from emp
group by deptno
order by deptno
PL/SQL procedure successfully completed.


The package code follows. Note that it requires the “parse” package that I posted earlier.

CREATE OR REPLACE PACKAGE pivot IS
  TYPE ref_cursor IS REF CURSOR;
  PROCEDURE print_pivot_query
  ( group_cols   IN VARCHAR2              -- Comma-separated list of column(s), including table alias if applicable,
                                          -- to be used to group the records
  , pivot_col    IN VARCHAR2              -- The name of the column to be pivoted, including table alias if applicable
  , tables       IN VARCHAR2              -- Comma-separated list of table(s), with table alias if applicable
  , value_cols   IN VARCHAR2              -- Comma-separated list of column(s), including table alias if applicable
                                          -- for which aggregates are to be shown at each intersection
  , pivot_values IN VARCHAR2 DEFAULT NULL -- Comma-separated list of values of pivot column to be used;
                                          -- if omitted, all values are used (determined dynamically)
  , agg_types    IN VARCHAR2 DEFAULT NULL -- Comma-separated list of aggregate types, corresponding to value_cols;
                                          -- if omitted, SUM is the default
  , where_clause IN VARCHAR2 DEFAULT NULL -- where clause of query
  , order_by     IN VARCHAR2 DEFAULT NULL -- order by clause; if omitted, output is ordered by group_cols
  );
  FUNCTION pivot_query
  ( group_cols IN VARCHAR2
  , pivot_col IN VARCHAR2
  , tables IN VARCHAR2
  , value_cols IN VARCHAR2
  , pivot_values IN VARCHAR2 DEFAULT NULL
  , agg_types IN VARCHAR2 DEFAULT NULL
  , where_clause IN VARCHAR2 DEFAULT NULL
  , order_by IN VARCHAR2 DEFAULT NULL
  ) RETURN VARCHAR2;
  FUNCTION pivot_cursor
  ( group_cols IN VARCHAR2
  , pivot_col IN VARCHAR2
  , tables IN VARCHAR2
  , value_cols IN VARCHAR2
  , pivot_values IN VARCHAR2 DEFAULT NULL
  , agg_types IN VARCHAR2 DEFAULT NULL
  , where_clause IN VARCHAR2 DEFAULT NULL
  , order_by IN VARCHAR2 DEFAULT NULL
  ) RETURN ref_cursor;
END;
/
CREATE OR REPLACE PACKAGE BODY pivot IS
  g_mode varchar2(10);
  g_sql varchar2(32767);
  PROCEDURE pr
  ( p_text in varchar2
  )
  IS
    v_text VARCHAR2(32767) := p_text;
  BEGIN
    if g_mode = 'PRINT' then
      WHILE LENGTH(v_text) > 255 LOOP
        DBMS_OUTPUT.PUT_LINE( SUBSTR(v_text,1,255) );
        v_text := SUBSTR(v_text,256);
      END LOOP;
      DBMS_OUTPUT.PUT_LINE( v_text );
    else
      g_sql := g_sql || ' ' || p_text;
    end if;
  END pr;
  /*
  || Generates the SQL statement for a pivot query based on parameters
  || Example:
  || create_pivot_query
  || ( group_cols => 'd.dname'
  || , pivot_col => 'e.job'
  || , tables => 'emp e, dept d'
  || , value_cols => 'e.sal,e.age'
  || , agg_types => 'min,max'
  || , where_clause => 'e.deptno = d.deptno'
  || );
  || Generates a query like:
  || select d.dname
  || , min(DECODE(e.job,'ANALYST', e.sal, 0 )) as "min_ANALYST_esal"
  || , max(DECODE(e.job,'ANALYST', e.age, 0 )) as "max_ANALYST_eage"
  || , min(DECODE(e.job,'CLERK', e.sal, 0 )) as "min_CLERK_esal"
  || , max(DECODE(e.job,'CLERK', e.age, 0 )) as "max_CLERK_eage"
  || , min(DECODE(e.job,'MANAGER', e.sal, 0 )) as "min_MANAGER_esal"
  || , max(DECODE(e.job,'MANAGER', e.age, 0 )) as "max_MANAGER_eage"
  || , min(DECODE(e.job,'PRESIDENT', e.sal, 0 )) as "min_PRESIDENT_esal"
  || , max(DECODE(e.job,'PRESIDENT', e.age, 0 )) as "max_PRESIDENT_eage"
  || , min(DECODE(e.job,'SALESMAN', e.sal, 0 )) as "min_SALESMAN_esal"
  || , max(DECODE(e.job,'SALESMAN', e.age, 0 )) as "max_SALESMAN_eage"
  || from emp e, dept d
  || where e.deptno = d.deptno
  || group by d.dname
  || order by d.dname
  ||
  || i.e. the parameters are used like this:
  || select
  || , (DECODE(,, , 0 ))
  || from
  || where
  || group by
  || order by
  ||
  */
  PROCEDURE define_pivot_query
  ( group_cols IN VARCHAR2
  , pivot_col IN VARCHAR2
  , tables IN VARCHAR2
  , value_cols IN VARCHAR2
  , pivot_values IN VARCHAR2 DEFAULT NULL
  , agg_types IN VARCHAR2 DEFAULT NULL
  , where_clause IN VARCHAR2 DEFAULT NULL
  , order_by IN VARCHAR2 DEFAULT NULL
  )
  IS
    type ref_cursor is ref cursor;
    rc ref_cursor;
    pv_tab parse.varchar2_table;
    val_tab parse.varchar2_table;
    agg_tab parse.varchar2_table;
    num_pvs integer := 0;
    num_vals integer := 0;
    num_aggs integer := 0;
    alias varchar2(100);
  BEGIN
    g_sql := NULL;
    -- Determine pivot values: use list if given, otherwise construct query to find them
    if pivot_values is not null then
      parse.delimstring_to_table( pivot_values, pv_tab, num_pvs );
    else
      open rc for 'select distinct ' || pivot_col || ' from ' || tables || ' where ' || nvl(where_clause,'1=1');
      loop
        num_pvs := num_pvs+1;
        fetch rc into pv_tab(num_pvs);
        exit when rc%notfound;
      end loop;
      close rc;
      num_pvs := num_pvs-1;
    end if;
    parse.delimstring_to_table( value_cols, val_tab, num_vals );
    -- Determine aggregate functions (default is SUM)
    if agg_types is not null then
      parse.delimstring_to_table( agg_types, agg_tab, num_aggs );
    end if;
    if num_aggs <> num_vals then
      for i in num_aggs+1..num_vals loop
        agg_tab(i) := 'sum';
      end loop;
    end if;
    pr('select '||group_cols);
    for pv in 1..num_pvs loop
      pv_tab(pv) := trim(pv_tab(pv));
      for val in 1..num_vals loop
        val_tab(val) := trim(val_tab(val));
        if num_vals = 1 then
          alias := substr(pv_tab(pv),1,30);
        else
          alias := substr(agg_tab(val) || '_' || TRANSLATE(pv_tab(pv),'x. -()<>','x') || '_' || TRANSLATE(val_tab(val),'x. -()<>','x'),1,30);
        end if;
        pr( ', '||agg_tab(val)||'(DECODE(' || pivot_col || ',''' || pv_tab(pv) || ''', ' || val_tab(val) || '))'
            || ' as "' || alias || '"' );
      end loop;
    end loop;
    pr('from ' || tables );
    if where_clause is not null then
      pr('where ' || where_clause);
    end if;
    pr('group by ' || group_cols);
    pr('order by ' || NVL(order_by,group_cols));
  END define_pivot_query;
  PROCEDURE print_pivot_query
  ( group_cols IN VARCHAR2
  , pivot_col IN VARCHAR2
  , tables IN VARCHAR2
  , value_cols IN VARCHAR2
  , pivot_values IN VARCHAR2 DEFAULT NULL
  , agg_types IN VARCHAR2 DEFAULT NULL
  , where_clause IN VARCHAR2 DEFAULT NULL
  , order_by IN VARCHAR2 DEFAULT NULL
  )
  IS
  BEGIN
    g_mode := 'PRINT';
    define_pivot_query
    ( group_cols
    , pivot_col
    , tables
    , value_cols
    , pivot_values
    , agg_types
    , where_clause
    , order_by
    );
  END;
  FUNCTION pivot_query
  ( group_cols IN VARCHAR2
  , pivot_col IN VARCHAR2
  , tables IN VARCHAR2
  , value_cols IN VARCHAR2
  , pivot_values IN VARCHAR2 DEFAULT NULL
  , agg_types IN VARCHAR2 DEFAULT NULL
  , where_clause IN VARCHAR2 DEFAULT NULL
  , order_by IN VARCHAR2 DEFAULT NULL
  ) RETURN VARCHAR2
  IS
  BEGIN
    g_mode := 'TEXT';
    define_pivot_query
    ( group_cols
    , pivot_col
    , tables
    , value_cols
    , pivot_values
    , agg_types
    , where_clause
    , order_by
    );
    RETURN g_sql;
  END;
  FUNCTION pivot_cursor
  ( group_cols IN VARCHAR2
  , pivot_col IN VARCHAR2
  , tables IN VARCHAR2
  , value_cols IN VARCHAR2
  , pivot_values IN VARCHAR2 DEFAULT NULL
  , agg_types IN VARCHAR2 DEFAULT NULL
  , where_clause IN VARCHAR2 DEFAULT NULL
  , order_by IN VARCHAR2 DEFAULT NULL
  ) RETURN ref_cursor
  IS
    rc ref_cursor;
  BEGIN
    g_mode := 'CURSOR';
    define_pivot_query
    ( group_cols
    , pivot_col
    , tables
    , value_cols
    , pivot_values
    , agg_types
    , where_clause
    , order_by
    );
    OPEN rc FOR g_sql;
    RETURN rc;
  END;
END;
/