ansaurus

Question

improving query times a sql ip lookup database

Answer 1

A:

May be review possibility to change architecture? (Using MSSQL hints me that you can use .Net) Since you use readonly database review some: in memory database. Or try OracleCoherence for .Net (http://coherence.oracle.com/)

Dewfy 2010-07-05 11:27:57

Thanks, I'll have a look into this.

tt83 2010-07-05 11:40:09

Answer 2

A:

What are your indexes? Would it help if you had one covering index? So ipfrom, ipto on one index? Could then even "include" id, countrycode, countryname, region, and city fields in that index so system does not have to go to data pages to get that data.

-Krip

Krip 2010-07-05 11:29:28

tt83 2010-07-05 12:35:00

also worth knowing if you have a clustered index and what fields that covers.

Krip 2010-07-05 18:11:16

Answer 3

A:

I see two ways to reduce execution time

1.Simple one would be to Cache whole 3m of records and use .NET native Datasets to retrieve wanted item in IP range. This will obviously eat your server CPU but you won't make 10 calls to DB every second.

2.Harder one would be to split IPs to different tables like IPRanges1 .... IPRanges9. So once you get user IP and want to query other details, you just pass to query another param with first digit of IP. This will reduce looping through 3M to 3m/9 (or something like that). Reduce in execution time will be obvious. If you combine it with Caching method you will end up with something proper.

eugeneK 2010-07-05 12:04:49

Answer 4

+1 A:

How does this perform? I'm hoping that it should use an index seek on ipto to quickly resolve the top part, an index seek on ipfrom to resolve the bottom part and 2 (or possibly one) bookmark lookups to get the rest of the columns to return.

SELECT id, ipfrom, ipto, countrycode, countryname,region,city FROM
(
SELECT TOP 1 id, ipfrom, ipto, countrycode, countryname,region,city
FROM tbl_ip 
WHERE @ip <= ipto
ORDER BY ipto
INTERSECT
SELECT TOP 1 id, ipfrom, ipto, countrycode, countryname,region,city
FROM tbl_ip 
WHERE ipfrom <= @ip
ORDER BY ipfrom DESC
) ip

Martin Smith 2010-07-05 12:14:07

ok, i've reposted the execution plan. the plan i posted earlier wasn't using the indexes because I had actually taken them off. the new plan is using the indexes.

tt83 2010-07-05 12:33:26

@tt83 - Can you confirm whether my assumption about correlation between the columns is correct or not?

Martin Smith 2010-07-05 12:36:20

just checked out your assumption that ipto in one row is previous to ipfrom in the next row and you are correct!

tt83 2010-07-05 12:37:33

i've tried that query and it executes in about double the time the original query took unfortunately..

tt83 2010-07-05 13:10:12

@tt83 can you post the execution plan for that one please?

Martin Smith 2010-07-05 13:10:53

the new execution plan has been posted to the question...

tt83 2010-07-05 13:16:51

@tt83 I'd first see Neil Poulton's answer and see if that helps. If not half of that plan you posted looks alright. It just needs an index on 'ipto' and then should perform fine (the composite index on from and to can be used for the bottom part of the query but not the top part). Infact if no other queries are relying on the composite index 2 separate indexes. One on 'ipfrom'and the other on 'ipto' would be the best combination for the query above.

Martin Smith 2010-07-05 13:53:13

@tt83, Martin is right - the culprit for slow execution of the above query is ORDER BY ipto, assuming only one composite index (ipfrom, ipto). (so you can expect gain if you separate indexes, if the above query run only twice as slow while building the index for sorting). Furthermore I got the same query in my answer - but only using ipfrom since I assumed the ip ranges not overlapping but covering a some bigger range (in another words ipto equals ipfrom of the next row). In that case you don't need two indexes (you don't even need two columns strictly speaking).

Unreason 2010-07-05 14:16:22

thanks guys, following Martin's advice to add one index on (ipfrom, ipto) and another just on ipto, my original query now takes just 1 ms!! thanks for all the answers!

tt83 2010-07-05 14:26:41

by the way, where did you guys learn so much about the inner workings of indexes from? i haven't been able to find much useful info on the web...

tt83 2010-07-05 14:30:17

@tt83, Martin: I am being picky today; I updated my answer - I claim that you don't need two indexes nor interesection. @tt83, Re indexes, a combination of wikipedia, C.J.Date (Introduction to Database Systems) and examining execution plans across RDBMSes did a trick for me.

Unreason 2010-07-05 14:42:58

@Unreason - Absolutely correct. Precisely because of the correlation only one index is needed.

Martin Smith 2010-07-05 14:46:13

@tt83 You might find this question useful http://stackoverflow.com/questions/3022424/recommended-book-for-sql-server-query-optimisation

Martin Smith 2010-07-05 14:52:57

Answer 5

A:

You probably need to separate out the data into two tables: IPData (ipfrom, ipto, locationid) and LocationData (locationid, countryname, city, etc)

I would change the where clause to:

WHERE @ip BETWEEN ipfrom AND ipto

Ryan Leyesa 2010-07-05 12:43:50

Answer 6

A:

If ip ranges start at powers of 2 (and they should), you could exploit the fact that ip = ipfrom or ip = ipfrom & 11...10 or ip = ipfrom & 11...00, etc...

32 index lookups should be faster than a index range scan.

Just a thought.

Samuel 2010-07-05 13:01:41

this looks interesting but it's a little bit beyond my knowledge to be honest. would you be able to do a sample query based on the your post?

tt83 2010-07-05 13:11:41

Answer 7

+1 A:

Try adding this to the WHERE clause AND ipfrom <= ipto

Neil Poulton 2010-07-05 13:25:37

+1 I think that might well resolve it.

Martin Smith 2010-07-05 13:31:10

Or not. On original index (ipfrom, ipto) the above condition would not help (especially since each ipfrom leaf on the index would have maximum one entry for ipto; which means that the index will have to be scanned).

Unreason 2010-07-05 14:20:45

Answer 8

+1 A:

Is your clustered index on id? If so, you could maybe change it to ipfrom, ipto.

Yellowfog 2010-07-05 13:50:46

+1 clustered is good in this case (data rarely changes)

Unreason 2010-07-05 13:53:20

Not really the issue though. It's only returning one row.

Martin Smith 2010-07-05 13:56:34

And it's not going to be able to traverse the clustered index faster?

Yellowfog 2010-07-05 13:59:28

Whilst this will help slightly the main problem with the query is that the query optimiser doesn't realise that there is a correlation between the 'ipfrom' and 'ipto' columns so scans a lot of rows unnecessarily.

Martin Smith 2010-07-05 14:02:45

Yes, now I look at the execution plan I see what you mean

Yellowfog 2010-07-05 14:07:48

Answer 9

+2 A:

I think the main reason why the query is slow even with index ipfrom, ipto is that the engine can not use the index properly.

It takes the first condition ipfrom <= @ip and is able to use index for that, however this inequality has a low selection and if your ip ranges cover all ips and are not overlapping then for the index has only one ipto entry for each ipfrom index leaf.

That is not so useful and it ends up doing full index scan (assumption1).

So, to speed it up there are several tricks

1) If select @ip_max_delta = max(ipto-ipfrom) is not to big (~1000 records) you can add WHERE ipfrom > (@ip - @ip_max_delta) (this is directly usable only if ip's are stored as int). This will work well with any index starting with ipfrom

2)

SELECT TOP 1 id, ipfrom, ipto, countrycode, countryname,region,city
FROM tbl_ip 
WHERE ipfrom <= @ip
ORDER BY ipfrom DESC

This should return really quickly (especially if you cluster on ipfrom and you should as your data rarely changes).

If the above does not return quickly can you test the execution time (and plan) on the following query, just for reference

SELECT id, ipfrom, ipto, countrycode, countryname,region,city
FROM tbl_ip 
WHERE ipfrom = @ip

(choose existing @ip that exists in ipfrom column)

EDIT2: Re Martin's solution

I don't see reason to a) use intersection/subquery and b) to maintain two indexes

SELECT TOP 1 id, ipfrom, ipto, countrycode, countryname,region,city
FROM tbl_ip 
WHERE ipfrom <= @ip
ORDER BY ipfrom DESC

Should return the same as Martin's query if there is correlation between ipfrom and ipto in consecutive rows. If not then additional condition can be applied directly

SELECT TOP 1 id, ipfrom, ipto, countrycode, countryname,region,city
FROM tbl_ip 
WHERE ipfrom <= @ip AND @ip <= ipto
ORDER BY ipfrom DESC

This query is quite similar to the starting one, but the ORDER BY should allow parser to choose better plan (unverfied). If it does not then

SELECT id, ipfrom, ipto, countrycode, countryname,region,city
FROM
(SELECT TOP 1 id, ipfrom, ipto, countrycode, countryname,region,city
FROM tbl_ip 
WHERE ipfrom <= @ip
ORDER BY ipfrom DESC) s
WHERE @ip <= ipto

Should do the trick and would require only index on ipfrom.

Unreason 2010-07-05 14:07:32

ansaurus

tags:

views:

answers:

improving query times a sql ip lookup database

related questions