Mastering Recursive CTEs: The Missing Number Problem

Hey fellow developers and data enthusiasts!

Have you ever been in a technical interview and been hit with a classic SQL puzzle? Or maybe you've faced a real-world data-cleaning task where you needed to identify gaps in your dataset. A common version of this problem is: "Given a list of numbers, find all the missing numbers within a specific range."

Today, we're going to tackle this exact problem. It's a fantastic way to sharpen your SQL skills, particularly with a powerful feature called Recursive Common Table Expressions (CTEs).

The Problem

Let's imagine you have a table called Numbers with a single column, number. This table is supposed to contain an unbroken sequence of integers from 1 to 100, but some numbers have gone missing.

Example Numbers table:

Our goal is to write a single SQL query that returns all the missing numbers. For the example above, the result should look like this:

Desired Result:

The Strategy: Generate, Compare, and Filter

Our approach is simple and elegant. We'll solve this in two main steps:

1. First, we'll programmatically generate a complete and perfect list of numbers from 1 to 100.

2. Then, we'll compare our perfect list with the numbers actually present in the Numbers table and filter out the ones that are missing.

Let's dive into the code.

Step 1: Generating the Full Sequence with a Recursive CTE

To create our "perfect" list of numbers from 1 to 100, we'll use a recursive CTE. If you haven't used one before, don't worry! Think of it as a temporary table that can build upon itself.

Here’s the code to generate the sequence:

with recursive cte as (
  -- This is the starting point (Anchor)
  select 1 as number
  union all
  -- This is the repeating part (Recursive Step)
  select number + 1 from cte
  where number < 100
)

Let's break this down:

• with recursive cte as (...): This line declares our temporary, recursive table and names it cte.

• select 1 as number: This is the anchor member. It's the starting seed for our sequence. Our cte begins its life with just a single row containing the number 1.

• union all: This operator stacks the results from each step.

• select number + 1 from cte where number < 100: This is the recursive member, and it's where the magic happens.

  • It looks at the last row added to cte, takes its number value, and adds 1 to it.

  • The where number < 100 is our crucial exit condition. It tells the query to stop recursing once it generates the number 100. Without this, it would run forever!

After this part runs, we have a temporary table cte in memory that contains every integer from 1 to 100. Our perfect list is ready.

Step 2: Filtering to Find the Missing Numbers

Now that we have our complete list, the final step is surprisingly simple. We just need to select the numbers from our cte that are not present in our original Numbers table.

We can do this with a WHERE NOT IN clause.

select number from cte
where number not in (select number from numbers)

• select number from cte: We start by selecting from our perfect list (1, 2, 3, ..., 100).

• (select number from numbers): This subquery grabs the list of numbers that are actually in your table.

• where number not in (...): This is the filter. It goes through our perfect list and asks for each number, "Is this number in the Numbers table?" If the answer is no, it keeps it for the final result.

Putting It All Together

Here is the complete query in all its glory:

with recursive cte as (
  select 1 as number
  union all
  select number + 1 from cte
  where number < 100
)
select number from cte
where number not in (select number from numbers);

This single query first builds the complete sequence and then efficiently subtracts the existing numbers, leaving you with only the gaps.

It's a clean, readable, and powerful solution to a common problem. Recursive CTEs can be used for much more, like navigating organizational charts or mapping routes, but this example is a perfect introduction to their power.

Happy coding!