In an application that I developed recently, I needed to be able to choose an unused IP address from a set of available address ranges. I didn’t really want to have to write some stored procedure to iterate over the entire space to until it found a gap. After a while I came up with (roughly) this:

SELECT MIN(addresses.available) FROM (
  SELECT i1.ip_addr + 1 AS available
    FROM interfaces i1
      INNER JOIN assignable_ip_ranges r
        ON i1.ip_addr >= r.start AND
           i1.ip_addr < r.end
      LEFT OUTER JOIN interfaces i2
        ON i1.ip_addr + 1 = i2.ip_addr
    WHERE i2.id IS NULL
  UNION
  SELECT r.start AS available
    FROM assignable_ip_ranges r
      LEFT OUTER JOIN interfaces i
        ON r.start = i.ip_addr
    WHERE i.id IS NULL
) addresses;

A quick explanation of what’s happening here:

If you do a left outer join of a table with itself with the criteria that some field on the left side, plus one, is equal to that same field on the right, the rows in the result that are NULL on the right side will have the maximum values of sequences on the left. For example, say you have table xyzzy containing four records with field foo containing the values 1, 2, 3, and 5. This query:

SELECT * 
  FROM xyzzy a
  LEFT OUTER JOIN xyzzy b
    ON a.foo + 1 = b.foo;

will yield:

That explains the LEFT OUTER JOIN and WHERE clause in the first sub-SELECT. The INNER JOIN just restricts the addresses to being chosen from the ranges in assignable_ip_ranges. (Note that the “end” comparison is a strict less-than, though. An address that has a gap following it at the end of an assignable range doesn’t do us any good!)

This technique has one big problem: it has no way of filling in the gap between the beginning of an available range and the first used address! That’s where the second sub-SELECT comes in. It uses roughly the same LEFT OUTER JOIN technique, but instead of doing a self-join, uses the start of the available IP ranges and the used IPs for joining. In essence, we’re pretending that there’s an assigned IP just before the beginning of every range.

At this point, we’ve got a list of the beginnings of all gaps, and we just take the minimum for the next address. Shazam!