2

I'm asking something very similar to Find if number is between two numbers in different fields in a MySQL database on Stack Overflow.

In the two options provided there, one is:

SELECT * FROM your_table WHERE 1265631252 BETWEEN `IP FROM` AND `IP TO`;

...which another poster said is slower compared to his current (and my current) method:

select * from your_table where ip_from <= 1265631252 and ip_to >= 1265631252;"

My table is 700+K rows, and it takes a long time to search the thousands of IP addresses I have. It takes 1 to 2 hours to query the thousands of IP addresses I have, and I'm wondering if there's a faster way.

The table contains overlapping ranges (third row overlaps with second and fourth row), e.g.

 IP FROM      IP TO         REGISTRY  ASSIGNED      CTRY  CNTRY  COUNTRY
"1265631232", "1265893375", "arin",   "1152835200", "US", "USA", "United States"
"1265893376", "1265958911", "arin",   "1149120000", "US", "USA", "United States"
"1265948800", "1266089983", "arin",   "1149120000", "US", "USA", "United States"
"1266024448", "1266089983", "arin",   "1162425600", "US", "USA", "United States"   

The EXPLAIN results shows:

id  select_type    table      type    possible_keys    key       key_len    ref     rows      Extra
1   SIMPLE         mytable    range   PRIMARY          PRIMARY   8          NULL    197252    Using where

migrated from stackoverflow.com Jun 5 '15 at 13:56

This question came from our site for professional and enthusiast programmers.

1

Your current code is O(N), even with the index, where N=700K.

Solution. That blog explains how to restructure the table of IP addresses to have only one column (start, no end), and provides code for searching/inserting, etc., efficiently. This technique is O(logN)* which is a vast improvement compared to O(N).

It involves ORDER BY + LIMIT to get the efficiency. If you have gaps in IP ranges, then extra rows are needed to indicate "unowned". Routines take care of properly inserting/removing these rows when you insert new entries.

*: In real world scenarios, to compare performance, we can ignore non-leaf nodes because (in a production system) they are almost always fully cached. Then, assuming the leaf node is not cached, the query only needs to do 1 disk hit. The OP's code is comparison would (estimated) need hundreds of disk hits.

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy