find IP among 1.5mill records

[anysero]

Hi,

I have recently purchased the ip2location database. This databse containts 1.5million rows with IP ranges (ipFROM,ipTO) and some other data like countryname, cityname etc. I need to write a query that is extremely much faster than my current ones.

The IP numbers are stored in long format (int(10) unsigned). The SELECT statement provided by ip2location is extremely slow, and looks like this:

SELECT countryname FROM tbl WHERE (ipFROM <= IP) AND (ipTO >= IP)

I currently do the following:

1. SELECT max(ipFROM) FROM tbl WHERE (ipFROM <= IP)
2. SELECT countryname FROM tbl WHERE (ipFROM = RESULT FROM 1)

This speeds up the query with about 50%, but a query for a high ip-number - ie. 212.78.161.106 still takes about 4 seconds to process (7,5 seconds with original SELECT).

A friend (knowing a lot about mathematics, but little about databases, suggested the following;

Consider IP to be the address we are searching for. The database consists of N elements. N0=1

1. Compare IP with record N/2
2. if IP < N/2 -> N = N/2
if IP > N/2 -> N0 = N/2
if none of these, adress matches.
3. next iteration compare IP with NO/2+NO/2
4. continue this process until none match, and you have the adress..

MY QUESTION: How can I do this? I use php and mysql.

I would also appriciate any other suggestions to speed up the query.

Sero

 

[Bastien]

Are there indeces on the table?

You may want to refine the query somewhat since any query that will return more than 30% of the rows in the table will result in a full table scan as the optimizer decides that a full table scan will be faster than using the index.



Bastien

Cat, the other other white meat

 

[ingresman]

Show us the defintion of the table (including the indexs). Bastein is cirrect it is alkmost certainly doing a table scan which in 1.5 million rows is not good !!.

 

[lgarner]

Your friend is suggesting that you write your own binary search, which is what pretty much every database does on its own, I think.

I'd probably try "select ipFrom from table where ipTo >= address limit 1". I don't know if there's overhead in the max() function, but I would think so. Also, make sure there's an index on ipTo.

 

[Karl Blessing]

The binary search ( which is automatic on most databases like lgarner said), simply a matter of deviding the search results in half, if result is not in between the min/max of the second half then must be in the first half, so goes to the first half, breaks that in half, then does the same routine over and over again until it narrows it down to one record. This would be quicker than searching every single, one, because yer narrowing it down half each time until the min/max becomes a single number. Course this only works if the results are sorted.

But as said above I Think some form of searching method is already done by the database. Though I would think would be nice if you were able to pre-process the table, to generate a second table with the short names, search the short name table, to find the ID number needed to pull the exact row from the large table.

Karl Blessing
PHP/MySQL Developer

http://www.karlblessing.com

 

[anysero]

The complete table definition:

create table IPCITYLATLONG(
ipFROM int(10) unsigned zerofill NOT NULL DEFAULT 0000000000 ,
ipTO int(10) unsigned zerofill NOT NULL DEFAULT 0000000000 ,
countrySHORT char(2) NOT NULL ,
countryLONG varchar(64) NOT NULL ,
ipREGION varchar(128) NOT NULL ,
ipCITY varchar(128) NOT NULL ,
ipLATITUDE double ,
ipLONGITUDE double ,
PRIMARY KEY (ipFROM,ipTO)
)

SEro

 

[Bastien]

try creating a separate index on each of the ip columns (ipFrom, ipTo)

Bastien

Cat, the other other white meat

 

[anysero]

I've never created indexes before, are you able to explain to me how I do this?

Regards,

Sero