We have a MySQL table with about 3.5 million IP entries.

The structure:

CREATE TABLE IF NOT EXISTS `geoip_blocks` (
  `uid` int(11) NOT NULL auto_increment,
  `pid` int(11) NOT NULL,
  `startipnum` int(12) unsigned NOT NULL,
  `endipnum` int(12) unsigned NOT NULL,
  `locid` int(11) NOT NULL,
  PRIMARY KEY  (`uid`),
  KEY `startipnum` (`startipnum`),
  KEY `endipnum` (`endipnum`)
) TYPE=MyISAM  AUTO_INCREMENT=3538967 ;

The problem: A query takes more than 3 seconds.

SELECT uid FROM `geoip_blocks` WHERE 1406658569 BETWEEN geoip_blocks.startipnum AND geoip_blocks.endipnum LIMIT 1

- about 3 seconds

SELECT uid FROM `geoip_blocks` WHERE startipnum < 1406658569 and endipnum > 1406658569 limit 1

- no gain, about 3 seconds

How can this be improved?