Finding Missing Numbers in Sequences: 2 Elegant SQL Approaches

SQL Quickies #26

Problem: Finding What’s Missing From A Sequence

Imagine you’re working with a database table called “Numbers” that contains a single column “number” with various integer values. You need to identify which numbers are missing from a sequence between 1 and 100.

This is a common challenge in data analysis and database management: identifying gaps in sequential data. Whether you’re looking for missing invoice numbers, skipped ID sequences, or discontinuities in time series data, the techniques we’ll explore are broadly applicable.

Let’s dive into couple of different approaches for solving this problem — both work with MySQL and BigQuery.

Approach 1: Using Recursive CTEs

Recursive CTEs are supremely clever and is incredibly useful in these type of scenarios.

WITH RECURSIVE sequence AS (
    SELECT 1 AS number  -- starting point
    UNION ALL
    SELECT number + 1   -- updation, this is where the magic happens 
    FROM sequence
    WHERE number < 100  -- looping condition
)
SELECT sequence.number AS missing_number
FROM sequence
LEFT JOIN Numbers ON sequence.number = Numbers.number
WHERE Numbers.number IS NULL
ORDER BY sequence.number;

1. The WITH RECURSIVE clause creates a recursive CTE that starts with the number 1. Think loops from programming (start, update, condition).
2. The recursive part adds the next number in the sequence until reaching 100.
3. We then LEFT JOIN this sequence with the Numbers table and filter for the missing values (by checking for NULL).

Approach 2: The Self-Join Technique

For databases that don’t support recursive CTEs, we can use a self-join technique to generate sequences:

WITH sequence AS (
    SELECT ones.n + 10*tens.n + 1 AS number
    FROM 
        (SELECT 0 AS n UNION SELECT 1 UNION SELECT 2 UNION SELECT 3 UNION SELECT 4 
         UNION SELECT 5 UNION SELECT 6 UNION SELECT 7 UNION SELECT 8 UNION SELECT 9) ones,
        (SELECT 0 AS n UNION SELECT 1 UNION SELECT 2 UNION SELECT 3 UNION SELECT 4 
         UNION SELECT 5 UNION SELECT 6 UNION SELECT 7 UNION SELECT 8 UNION SELECT 9) tens
    WHERE ones.n + 10*tens.n + 1 <= 100
)
SELECT sequence.number AS missing_number
FROM sequence
LEFT JOIN Numbers ON sequence.number = Numbers.number
WHERE Numbers.number IS NULL
ORDER BY sequence.number;

1. We create temporary tables representing ones, tens, and hundreds positions.
2. The Cartesian product of these tables gives us all possible combinations of digits.
3. By calculating ones.n + 10*tens.n + 100*hundreds.n + 1, we generate a sequence of numbers upto 100.
4. Finally, we perform the same LEFT JOIN and filtering as in the previous case.

This technique may look complex, but it’s extremely portable. It is worth spending time to try and understand this.

Performance Considerations

When choosing between these approaches, consider:

• Database compatibility: Use approach #1 for PostgreSQL, #2 for most modern databases, and #3 for universal compatibility.
• Dataset size: For large ranges (millions of numbers), the self-join approach may cause performance issues due to the Cartesian product.
• Readability and maintenance: The generate_series() approach is most readable, followed by the recursive CTE.

Beyond Missing Numbers: Real-World Applications

These techniques extend beyond finding missing numbers in a sequence. You can adapt them to:

• Identify gaps in date ranges
• Find missing transactions in a sequence
• Generate date or time series for reporting
• Create consistent bins for histograms

Conclusion

Finding missing values in sequential data is a fundamental SQL skill with applications across numerous domains. While the specific syntax might vary between database systems, the core pattern remains the same: generate a complete sequence, join it with your actual data, and filter for the gaps.

Whether you choose the elegance of generate_series(), the portability of recursive CTEs, or the universal compatibility of the self-join technique depends on your specific database environment and requirements.

What SQL challenges are you facing in your data work? Let me know in the comments below!