How to generate a list of first N binary numbers in Oracle SQL?

In my recent post I showed how to convert a decimal number (i.e. an integer) into a binary string. We can build upon that technique to answer the question:

WITH x AS (
SELECT LEVEL n
FROM dual
CONNECT BY LEVEL<=50
)
SELECT x.N, y.bin
FROM x, LATERAL (SELECT LISTAGG(SIGN(BITAND(x.N, POWER(2,LEVEL-1))),'') 
                        WITHIN GROUP(ORDER BY LEVEL DESC) bin
                 FROM dual
                 CONNECT BY POWER(2, LEVEL-1)<=x.N) y

Note the LATERAL keyword (Oracle 12c new feature) that enables us to reference “x” in the inline view “y”. In pre-12c world, we would have to use TABLE/CAST/MULTISET function composition to achieve the same result:

WITH x AS (
SELECT LEVEL n
FROM dual
CONNECT BY LEVEL<=50
)
SELECT x.N, y.column_value bin
FROM x, TABLE(CAST(MULTISET(
          SELECT LISTAGG(SIGN(BITAND(x.N, POWER(2,LEVEL-1))),'') 
                 WITHIN GROUP(ORDER BY LEVEL DESC) bin
          FROM dual
          CONNECT BY POWER(2, LEVEL-1)<=x.N) AS sys.odcivarchar2list)) y

The idea used in the following query is based on a totally different approach. It builds a string of “0”s and “1”s in a loop until its length reaches a desired value:

WITH x(v, n) AS (
SELECT column_value, 1
FROM TABLE(sys.odcivarchar2list('0','1'))
UNION ALL
SELECT x.v || t.column_value, x.n+1
FROM TABLE(sys.odcivarchar2list('0','1')) t JOIN x on LENGTH(x.v)=n
WHERE n<=CEIL(LOG(2,50))
), y AS (
SELECT NVL(LTRIM(x.v,'0'),'0') bin, ROWNUM-1 dec
FROM x
WHERE n=(SELECT MAX(n) FROM x)
)
SELECT *
FROM y
WHERE dec<=50

To better understand the above query, try the following one:

SELECT *                            
FROM TABLE(sys.odcivarchar2list('0','1')), 
     TABLE(sys.odcivarchar2list('0','1')),
     TABLE(sys.odcivarchar2list('0','1')),
     TABLE(sys.odcivarchar2list('0','1'))

If we put enough tables in the Cartesian product and concatenate all column_value columns in a single character string expression, we will achieve our goal. The challenge with this approach is to dynamically change the number of the tables in the FROM clause. This can be simulated in the recursive WITH clause by repeatedly adding more and more collections of bits (0 and 1).

My Oracle Group on Facebook:

If you like this post, you may want to join my new Oracle group on Facebook: https://www.facebook.com/groups/sqlpatterns/

Would you like to read about many more tricks and puzzles?

For more tricks and cool techniques check my book “Oracle SQL Tricks and Workarounds”.

 

Three Solutions to Puzzle of the Week #18

Puzzle of the Week #18:

There are gaps in values of empno column in emp table. The challenge is to find all the gaps within the range of employee numbers already in use. All numbers should be grouped in ranges (see expected result section below). A single SELECT statement against emp table is expected.

Expected Result:

Avail. Emp Numbers
------------------
7370 - 7498
7500 - 7520
7522 - 7565
7567 - 7653
7655 - 7697
7699 - 7781
7783 - 7787
7789 - 7838
7840 - 7843
7845 - 7875
7877 - 7899
7901 - 7901
7903 - 7933

Solutions

#1: Using GROUP BY Over ROWNUM expression

WITH x AS (
SELECT MIN(empno) min_no, MAX(empno) max_no
FROM emp
), y AS (
SELECT min_no+LEVEL-1 empno
FROM x
CONNECT BY min_no+LEVEL-1<=max_no
MINUS
SELECT empno
FROM emp
)
SELECT MIN(empno) || ' - ' || MAX(empno) "Avail. Emp Numbers"
FROM y
GROUP BY empno-ROWNUM
ORDER BY empno-ROWNUM;

Avail. Emp Numbers
--------------------
7370 - 7498
7500 - 7520
7522 - 7565
7567 - 7653
7655 - 7697
7699 - 7781
7783 - 7787
7789 - 7838
7840 - 7843
7845 - 7875
7877 - 7899
7901 - 7901
7903 - 7933

#2: Using MATCH_RECOGNIZE (Oracle 12c and up;  credit to Zohar Elkayam)

WITH x AS (
SELECT MIN(empno) min_no, MAX(empno) max_no
FROM emp
), y AS (
SELECT min_no+LEVEL-1 empno
FROM x
CONNECT BY min_no+LEVEL-1<=max_no
MINUS
SELECT empno
FROM emp
)
SELECT firstemp || ' - ' || lastemp "Avail. Emp Numbers"
FROM y
MATCH_RECOGNIZE (
  ORDER BY empno
  MEASURES
   A.empno firstemp,
   LAST(empno) lastemp
  ONE ROW PER MATCH
  AFTER MATCH SKIP PAST LAST ROW
  PATTERN (A B*)
  DEFINE B AS empno = PREV(empno)+1
);

#3: Using LEAD Analytic function (credit to Krishna Jamal)

WITH x AS
(
SELECT empno, LEAD(empno,1) OVER(ORDER BY empno) lead_empno
FROM emp
)
SELECT (empno+1) || ' - ' || (lead_empno-1) "Avail. Emp Numbers"
FROM x
WHERE empno+1!=lead_empno;

Also, see a very similar Puzzle of the Week #15 for more workarounds.

My Oracle Group on Facebook:

If you like this post, you may want to join my new Oracle group on Facebook: https://www.facebook.com/groups/sqlpatterns/

Would you like to read about many more tricks and puzzles?

For more tricks and cool techniques check my book “Oracle SQL Tricks and Workarounds” for instructions.

3 Solutions to Puzzle of the Week #10: Fibonacci

Puzzle of the Week #10: Fibonacci

With a single SELECT statement calculate first 20 Fibonacci numbers without using Binet’s formula.

Expected Result:

   N     Fib(n)
---- ----------
   1          1
   2          1
   3          2
   4          3
   5          5
   6          8
   7         13
   8         21
   9         34
  10         55
  11         89
  12        144
  13        233
  14        377
  15        610
  16        987
  17       1597
  18       2584
  19       4181
  20       6765

Solutions:

#1. Oracle 10g solution (using MODEL clause):

SELECT n, f AS "Fib(n)"
FROM dual
MODEL
  DIMENSION BY (0 d)
  MEASURES (0 n, 0 f)
  RULES ITERATE(20) (
     f[iteration_number]=DECODE(iteration_number, 0,1, 1,1,
                                f[iteration_number-2]+f[iteration_number-1]),
     n[iteration_number]=iteration_number+1
  );

  N     Fib(n)
--- ----------
  1          1
  2          1
  3          2
  4          3
  5          5
  6          8
  7         13
  8         21
  9         34
 10         55
 11         89
 12        144
 13        233
 14        377
 15        610
 16        987
 17       1597
 18       2584
 19       4181
 20       6765

#2. Oracle 11.2g solution (using Recursive WITH clause):

WITH x(n, f1, f2) AS (
SELECT 1, 1, 1
FROM dual
UNION ALL
SELECT n+1, f2, f1+f2
FROM x
WHERE n<20
)
SELECT n, f1 AS “Fib(n)”
FROM x

#3. Oracle 12c solution (using WITH for PL/SQL function):

WITH
  FUNCTION fib(n INTEGER) RETURN NUMBER DETERMINISTIC
  AS
  BEGIN
     RETURN CASE WHEN n IN (1,2) THEN 1
                 ELSE fib(n-2)+fib(n-1)
            END;
  END;
SELECT LEVEL n, fib(LEVEL) AS "Fib(n)"
FROM dual
CONNECT BY LEVEL<=20

Suggested further reading:

For more tricks and cool techniques check my book “Oracle SQL Tricks and Workarounds” for instructions. The book is also available on Amazon and in all major book stores.

My Oracle Group on Facebook:

If you like this post, you may want to join my new Oracle group on Facebook: https://www.facebook.com/groups/sqlpatterns/