Optimize IP Range Join

[tmarket]

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:

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:

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,106747,106747#msg-106747

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

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;

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;

[tesuji]

hi

You may try this syntax, what is quite usual in other databases:
SELECT title FROM ranges JOIN ips ON
(
ip BETWEEN start AND stop
)

Question about this create table statement:

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;

Does this table really contains duplicate ip numbers (it wouldn't make any sense)? If not, you should delete ip_id and make ip to be the primary key! (It is really badly bad habit always generating artificial primary keys if tables already have enough columns to form their own natural primary keys from.)

krs,
tesu

[tmarket]

Hi tesuji, thanks for the reply.

Yes, the ips table contains duplicate IP addresses, so I can't make it a primary key.

[tesuji]

Hi tmarket

Did you already tried this sort of inner join:

select r.title from ranges r, ips s
where r.start <= s.ip and sr.ip <= r.stop

Additionally, you should put indexes on s.ip and (r.start, r.stop), e.g.
CREATE INDEX uniqueIndexName on ranges(start, stop), both indexes in ascending order.

krs,
tesu

p.s. As you may know, your sort of inner join is a so called theta-join, and this sort of joins is well known to be the slowest join one can create. (And you are using two of them)