Optimize IP Range Join

tmarket · #1 (**permalink**) 06-23-08, 12:51

I have 2 tables: an IP Address table, and an IP Ranges table. I want to retrieve a list of ranges in the ranges table for which one or more of the IP addresses in the IP address table fall within that range. The IP addresses are represented as integers, and the IP ranges are non-overlapping.

What I'm trying to use is this:

Code:

SELECT title FROM ranges JOIN ips ON ip BETWEEN start AND stop

but it takes too long. Is there a better way?

Here is the structure:

Code:

mysql> describe ranges;
+------------+------------------+------+-----+---------+----------------+
| Field      | Type             | Null | Key | Default | Extra          |
+------------+------------------+------+-----+---------+----------------+
| range_id   | int(20) unsigned | NO   | PRI | NULL    | auto_increment |
| start      | int(10) unsigned | NO   | UNI | NULL    |                |
| stop       | int(10) unsigned | NO   | UNI | NULL    |                |
| title      | varchar(200)     | NO   |     | NULL    |                |
+------------+------------------+------+-----+---------+----------------+

mysql> describe ips;
+------------+------------------+------+-----+---------+----------------+
| Field      | Type             | Null | Key | Default | Extra          |
+------------+------------------+------+-----+---------+----------------+
| ip_id      | int(20) unsigned | NO   | PRI | NULL    | auto_increment |
| ip         | int(10) unsigned | NO   | MUL | NULL    |                |
+------------+------------------+------+-----+---------+----------------+

This is similar but different from this: http://forums.mysql.com/read.php?115...747#msg-106747

I've tried several different combinations of indexes, but no success.

Code:

CREATE TABLE `ranges` (
  `range_id` int(20) unsigned NOT NULL auto_increment,
  `start` int(10) unsigned NOT NULL,
  `stop` int(10) unsigned NOT NULL,
  `title` varchar(200) NOT NULL,
  PRIMARY KEY  (`range_id`),
  UNIQUE KEY (`start`),
  UNIQUE KEY (`stop`),
  KEY `title` (`title`)
) ENGINE=MyISAM;

Code:

CREATE TABLE `ips` (
  `ip_id` int(20) unsigned NOT NULL auto_increment,
  `ip` int(10) unsigned NOT NULL,
  PRIMARY KEY  (`ip_id`),
  KEY `ip` (`ip`)
) ENGINE=MyISAM;

r937 · #2 (**permalink**) 06-23-08, 13:59

start by removing the auto_increment columns from both tables

figure out what makes each row unique without the auto_increment, then make that the PK

if you get the PK right for the ranges tables, your query will optimize by itself as if by magic

topcat2 · #3 (**permalink**) 06-25-08, 02:36

Index is not going to help you here. Removing primary keys will help, but only marginally. There are a couple of things to do:

1. Change the data type for ip, start, and stop to bigint. If you are using IP numbers, the integer data type won't be able to handle IP's that start with a high number, like 198.%.%.%.

2. Decrease the number of rows in the ips table. You may have to do some kind of horizontal partition. Better yet, you can partition both the ips table and the ranges table. This decreases the number of rows that need to be processed during the join, and hence speeds up the query.

Internet Services

Web Development

Digital Marketing

Consumer Tech