10

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?

6
  • 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. May 11, 2012 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. May 11, 2012 at 19:15
  • @w0lf: are there overlapping ranges in ip2country (begin_num, end_num) ? May 11, 2012 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. May 11, 2012 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. May 11, 2012 at 21:48

3 Answers 3

3

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.

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

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!

1
  • 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 May 12, 2012 at 19:05
0

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
3
  • thanks, I have tried your approach, but it seems to be more expensive than the initial query May 12, 2012 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 :) May 12, 2012 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 :) May 13, 2012 at 6:28

Your Answer

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

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