PostgreSQL：查找INET地址段中的首个空闲最低IP

Got it, let's tackle this problem—finding the smallest free IP in a large PostgreSQL table (4M+ records for a /10 subnet) efficiently. First, let's start with foundational fixes, then move to advanced optimizations tailored for big datasets.

1. Start with the Basics: Index Your IP Column #

The single most impactful fix is adding a btree index on your ip column. PostgreSQL's INET type natively supports btree indexing, which turns slow full-table scans into fast range queries:

CREATE INDEX idx_ips_ip ON ips USING btree (ip);

This is non-negotiable for all the following optimizations to work.

2. Efficient Query to Find the Smallest Free IP #

Instead of scanning every IP in the subnet, we'll target gaps between existing IPs and check the subnet's starting IP first (since we want the smallest free IP). Here's an optimized query:

WITH subnet AS (
    -- Define your target subnet (adjust start/end for your /10 range)
    SELECT '127.0.0.0'::INET AS start_ip, '128.0.0.0'::INET AS end_ip
),
existing_ips AS (
    -- Only pull IPs within the target subnet (uses the index!)
    SELECT ip 
    FROM ips 
    WHERE ip BETWEEN (SELECT start_ip FROM subnet) AND (SELECT end_ip FROM subnet)
    ORDER BY ip
),
gap_checks AS (
    -- Check gaps between consecutive existing IPs
    SELECT 
        lag(ip) OVER (ORDER BY ip) + 1::INET AS gap_start,
        ip AS gap_end
    FROM existing_ips
    UNION ALL
    -- Check if the subnet's starting IP is unoccupied
    SELECT start_ip, (SELECT min(ip) FROM existing_ips) - 1::INET
    FROM subnet
    WHERE (SELECT min(ip) FROM existing_ips) > (SELECT start_ip FROM subnet)
)
-- Pick the first valid gap's starting IP
SELECT gap_start AS first_free_ip
FROM gap_checks
WHERE gap_start <= gap_end
ORDER BY gap_start
LIMIT 1;

Why this works: #

• We filter down to only the IPs in your target subnet first, avoiding scanning the entire table.
• The lag() window function efficiently finds gaps between sorted IPs without expensive self-joins.
• We prioritize checking the subnet's starting IP first—if it's free, we return it immediately without processing more data.

3. Advanced Optimizations for 4M+ Records #

For /10 subnets (4,194,304 possible IPs), even indexed queries can benefit from these tweaks:

Partition Your Table #

Split the ips table into partitions based on IP ranges (e.g., by the first 10 bits for your /10 subnet). This way, queries only scan the partition containing your target subnet instead of the entire 4M+ record table:

-- Convert the main table to a partitioned table
CREATE TABLE ips (ip INET NOT NULL) PARTITION BY RANGE (ip);

-- Create a partition for your /10 subnet (adjust ranges as needed)
CREATE TABLE ips_subnet_127_0_0_0_10 PARTITION OF ips
FOR VALUES FROM ('127.0.0.0'::INET) TO ('128.0.0.0'::INET);

If you already have data, you'll need to migrate it to the appropriate partitions, but this pays off long-term for large datasets.

Precompute Free IPs (For High-Concurrency Scenarios) #

If your IP allocation pattern allows for slight delays (or you can maintain consistency with triggers), precompute and cache free IPs in a separate table:

CREATE TABLE free_ips (ip INET PRIMARY KEY);

-- Populate initial free IPs (run once)
INSERT INTO free_ips (ip)
SELECT ip
FROM generate_series('127.0.0.0'::INET, '128.0.0.0'::INET, '1'::INET) AS ip
WHERE NOT EXISTS (SELECT 1 FROM ips WHERE ips.ip = ip);

-- When allocating an IP, just grab the smallest one
DELETE FROM free_ips
WHERE ip = (SELECT min(ip) FROM free_ips)
RETURNING ip;

-- When releasing an IP, add it back
INSERT INTO free_ips VALUES ('127.0.0.2');

This turns lookup time into O(1) since you're just pulling the minimum value from a pre-populated table. Use triggers on the ips table to automatically sync free_ips if you need strict real-time consistency.

Early-Termination Query #

If you only care about the smallest free IP, you can avoid checking all gaps by stopping at the first valid candidate:

WITH subnet AS (
    SELECT '127.0.0.0'::INET AS start_ip
),
min_existing AS (
    SELECT min(ip) AS min_ip FROM ips WHERE ip >= (SELECT start_ip FROM subnet)
)
SELECT 
    CASE 
        -- If subnet start is unoccupied, return it immediately
        WHEN min_ip > start_ip THEN start_ip
        -- Otherwise, find the first IP whose next IP is missing
        ELSE (
            SELECT ip + 1::INET 
            FROM ips 
            WHERE ip >= (SELECT start_ip FROM subnet)
            AND NOT EXISTS (SELECT 1 FROM ips WHERE ips.ip = ip + 1::INET)
            ORDER BY ip
            LIMIT 1
        )
    END AS first_free_ip
FROM min_existing, subnet;

This is faster than the gap-check query because it avoids processing all gaps—it stops as soon as it finds the first valid free IP.

Key Takeaways #

• Always index the ip column first—this is the foundation of all speed gains.
• Narrow your query to the target subnet to avoid unnecessary data scanning.
• For massive datasets, partitioning reduces the amount of data PostgreSQL needs to process.
• Precomputing free IPs is ideal for high-concurrency systems where lookup speed is critical.

内容的提问来源于stack exchange，提问作者Alfred Balle