Best approach to detect subnet overlap in a postgresql db

Question

I've got a postgres db with nearly 200'000 network address types. I'd like to detect if some subnets are overlapping themselves, for ex, detect 123.0.0.0/16, 123.2.0.0/24 and 123.3.4.128/30 and report them.

I'm already using a lot of python scripts and netaddr library.

Considering the number of entries, what would be the best approach/algorithm to detect overlaps?

I'm pretty sure there's a better way than comparing each entry to the whole database.

Answer 1

I think the following should be a fairly efficient approach:

import netaddr
import bisect

def subnets_overlap(subnets):
    # ranges will be a sorted list of alternating start and end addresses
    ranges = []
    for subnet in subnets:
        # find indices to insert start and end addresses
        first = bisect.bisect_left(ranges, subnet.first)
        last = bisect.bisect_right(ranges, subnet.last)
        # check the overlap conditions and return if one is met
        if first != last or first % 2 == 1:
            return True
        ranges[first:first] = [subnet.first, subnet.last]
    return False

Examples:

>>> subnets_overlap([netaddr.IPNetwork('1.0.0.0/24'), netaddr.IPNetwork('1.0.0.252/30')])
True
>>> subnets_overlap([netaddr.IPNetwork('1.0.0.0/24'), netaddr.IPNetwork('1.0.1.0/24')])
False

Answer 2

import sys
import ipaddr
from pprint import pprint

from netaddr import IPNetwork, IPAddress
matching_subent=[]
def cidrsOverlap(cidr0):
    subnets_list = [IPNetwork('123.0.0.0/16'),
                    IPNetwork('123.2.0.0/24'), 
                    IPNetwork('123.132.0.0/20'),
                    IPNetwork('123.142.0.0/20')]
    flag = False
    for subnet in subnets_list:
        if (subnet.first <= cidr0.last and subnet.last >= cidr0.last): 
            matching_subent.append(subnet)


    print "Matching subnets for given %s are %s" %(cidr0, matching_subent)
    pprint(subnets_list) 

cidrsOverlap(IPNetwork(sys.argv[1]))