Fun with SQL: integer runs

Aristotle on 2007-03-28T14:37:34

Someone posted an SQL question in a forum I occasionally frequent. The setup:

CREATE TABLE tbl (num INTEGER);
INSERT INTO tbl VALUES (  1);
INSERT INTO tbl VALUES (  2);
INSERT INTO tbl VALUES (  3);
INSERT INTO tbl VALUES (  4);
INSERT INTO tbl VALUES (  9);
INSERT INTO tbl VALUES ( 10);
INSERT INTO tbl VALUES ( 11);
INSERT INTO tbl VALUES ( 20);
INSERT INTO tbl VALUES ( 21);
INSERT INTO tbl VALUES ( 22);
INSERT INTO tbl VALUES ( 23);
INSERT INTO tbl VALUES (100);
INSERT INTO tbl VALUES (101);
INSERT INTO tbl VALUES (102);
INSERT INTO tbl VALUES (103);

His question: is there a way to produce the following output?

start       end       
----------  ----------
1           4         
9           11        
20          23        
100         103       

I didn’t think it was possible at first, but after some thinking and tinkering, I managed to come up with a solution:

SELECT s.num AS start, MIN( e.num ) AS end
FROM (
	SELECT num
	FROM tbl t1
	WHERE NOT EXISTS ( SELECT NULL FROM tbl t2 WHERE t2.num = t1.num - 1 )
	ORDER BY num
) s
CROSS JOIN (
	SELECT num
	FROM tbl t1
	WHERE NOT EXISTS ( SELECT NULL FROM tbl t2 WHERE t2.num = t1.num + 1 )
	ORDER BY num
) e
WHERE s.num <= e.num
GROUP BY s.num;

---

Cross JOIN

cosimo on 2007-03-28T20:32:53

Cool!

I think I must review what the "CROSS JOIN" does in my SQL manual... :-)
Thanks for sharing.

Re:Cross JOIN

Aristotle on 2007-03-29T06:39:59

CROSS JOIN is simply an explicit way to request the standard cartesian product.

sqlite> CREATE TABLE tbl (num INTEGER);
sqlite> INSERT INTO tbl VALUES (  1);
sqlite> INSERT INTO tbl VALUES (  2);
sqlite> INSERT INTO tbl VALUES (  3);
sqlite> SELECT t1.num A, t2.num B FROM tbl t1 CROSS JOIN tbl t2;
A           B
----------  ----------
1           1
1           2
1           3
2           1
2           2
2           3
3           1
3           2
3           3

You can write the exact same query like this:

SELECT t1.num A, t2.num B FROM tbl t1, tbl t2

I just prefer the newer syntax because there are few cases where you’d deliberately ask for a cartesian product, and with the old syntax it’s not clear whether you did so or merely forgot the join condition. The new explicit syntax documents your intent.