Take the 2-minute tour ×
Database Administrators Stack Exchange is a question and answer site for database professionals who wish to improve their database skills and learn from others in the community. It's 100% free, no registration required.

I have two tables in which I store:

  • an IP range - country lookup table
  • a list of requests coming from different IPs

The IPs were stored as bigints to improve lookup performance.

This is the table structure:

create table [dbo].[ip2country](
    [begin_ip] [varchar](15) NOT NULL,
    [end_ip] [varchar](15) NOT NULL,
    [begin_num] [bigint] NOT NULL,
    [end_num] [bigint] NOT NULL,
    [IDCountry] [int] NULL,
    constraint [PK_ip2country] PRIMARY KEY CLUSTERED 
    (
        [begin_num] ASC,
        [end_num] ASC
    )
)

create table Request(
    Id int identity primary key, 
    [Date] datetime, 
    IP bigint, 
    CategoryId int
)

I want to get the request breakdown per country, so I perform the following query:

select 
    ic.IDCountry,
    count(r.Id) as CountryCount
from Request r
left join ip2country ic 
  on r.IP between ic.begin_num and ic.end_num
where r.CategoryId = 1
group by ic.IDCountry

I have a lot of records in the tables: about 200,000 in IP2Country and a few millions in Request, so the query takes a while.

Looking at the execution plan, the most expensive part is a Clustered Index Seek on index PK_IP2Country, which is executed many times (the number of rows in Request).

Also, something that I feel a little strange about is the left join ip2country ic on r.IP between ic.begin_num and ic.end_num part (don't know if there's a better way to perform the lookup).

The table structure, some sample data and query are available in SQLFiddle: http://www.sqlfiddle.com/#!3/a463e/3 (unfortunately I don't think I can insert many records to reproduce the problem, but this hopefully gives an idea).

I'm (obviously) not an expert in SQL performance/optimizations, so my question is: Are there any obvious ways in which this structure/query can be improved performance-wise that I am missing?

share|improve this question
2  
Can an IP address map to multiple countries? If not, you can narrow your PK to just begin_num. I also have to join on A BETWEEN B AND C fairly often, and I'm curious to know if there's a way to achieve this without tedious RBAR joins. –  Jon of All Trades May 11 '12 at 19:13
1  
It's a little off-topic to your question, but I'd consider making begin_ip and end_ip persisted calculated columns, to prevent the possibility of the text and numbers getting out of synch somehow. –  Jon of All Trades May 11 '12 at 19:15
    
@w0lf: are there overlapping ranges in ip2country (begin_num, end_num) ? –  ypercube May 11 '12 at 21:22
    
@JonofAllTrades normally one IP should belong to a single country, so I think your idea of a query like give me the first record that has a begin_num < ip in asc order of begin_num (correct me if I'm wrong) could be be valid and improve performance. –  w0lf May 11 '12 at 21:35
1  
@w0lf: My impressions is that that's basically what the server is doing in a case like this, because it first scans by begin_num, then scans by end_num within that set and only finds one record. –  Jon of All Trades May 11 '12 at 21:48

3 Answers 3

up vote 3 down vote accepted

You need an additional index. In your Fiddle example I added:

CREATE UNIQUE INDEX ix_IP ON Request(CategoryID, IP)

Which covers you for the request table and gets an index seek instead of a clustered index scan.

See how that improves it and let me know. I'm guessing it'll help quite a bit since the scan on that index is I'm sure not cheap.

share|improve this answer
    
I don't know why, but the results seem to be different (in SQLFiddle) –  w0lf May 11 '12 at 21:27
    
@w0lf: they are different (probbaly) because you are both inserting random data into the tables. –  ypercube May 11 '12 at 21:45
    
@ypercube surely that's the cause. I've done so many things lately that I forgot that data was random. Sorry. –  w0lf May 12 '12 at 6:56

There's always the brute-force approach: you could explode your IP map. Join a numbers table against your existing map to create one record per IP address. That's only 267K records based on your Fiddle data, no problem at all.

CREATE TABLE IPLookup
  (
  IP  BIGINT PRIMARY KEY,
  CountryID  INT
  )
INSERT INTO IPLookup (IP, CountryID)
  SELECT
    N.Number, Existing.IDCountry
  FROM
    ip2country AS Existing
    INNER JOIN Numbers AS N ON N.Number BETWEEN Existing.begin_num AND Existing.end_num

This would make the seeks simpler, and hopefully faster. This only makes sense if you make relatively few updates on ip2country, of course.

I hope someone else has a better a solution!

share|improve this answer
    
The whole data set would produce more than 5 billion records, so I don't think I'll do it. But this is a nice idea nevertheless; I'm sure it's feasible in many similar cases. +1 –  w0lf May 12 '12 at 19:05

Try this:

SELECT ic.IDCountry,
        COUNT(r.Id) AS CountryCount
FROM Request r
INNER JOIN (SELECT begin_num+NUMS.N [IP], IDCountry 
            FROM ip2country
            CROSS JOIN (SELECT TOP(SELECT ABS(MAX(end_num-begin_num)) FROM ip2country) ROW_NUMBER() OVER(ORDER BY sc.name)-1 [N]
                        FROM sys.columns sc) NUMS
            WHERE begin_num+NUMS.N <= end_num) ic
ON r.IP = ic.IP
WHERE r.CategoryId = 1
GROUP BY ic.IDCountry
share|improve this answer
    
thanks, I have tried your approach, but it seems to be more expensive than the initial query –  w0lf May 12 '12 at 19:19
    
How many rows do you have in each table? I would like to reproduce the scale of your problem on my DB and try to solve without adding an index :) –  Vince Pergolizzi May 12 '12 at 21:49
    
about 200,000 in IP2Country and a few millions (possibly tens of millions in the near future) in Request. I think if you solve it without indexes you deserve a "DBA of the year" title :) –  w0lf May 13 '12 at 6:28

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.