TSQL performance - JOIN on value BETWEEN min and max

Question

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?

Answer 1

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.

Answer 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!

Answer 3

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