The query plan said Index Seek. The query was doing ~8,000 logical reads per call against a 4-million-row table and burning ~330ms of CPU under load. Both things were true at once, and the gap between them is worth a post.

The query

We have a geoIP lookup table, roughly:

CREATE TABLE dbo.mapIPtoLocation (
    startIpNumber bigint NOT NULL,
    endIpNumber   bigint NOT NULL,
    locID         int    NOT NULL,
    -- clustered PK
    CONSTRAINT PK_mapIPtoLocation PRIMARY KEY CLUSTERED
        (startIpNumber, endIpNumber, locID)
);

Four million rows, mostly non-overlapping IP ranges. The lookup I believed was hot, called from every page that wants to geolocate a visitor:

SELECT TOP 1 locID
FROM   dbo.mapIPtoLocation
WHERE  startIpNumber <= @ip
  AND  endIpNumber   >= @ip;

This is a range-overlap query. The visitor IP has to fall inside one row’s [startIpNumber, endIpNumber] interval.

I got the “every page” part wrong, and I acted on it first. I took the 332ms figure from an incident capture during a slow-site episode and read it as proof that the request logging procedure ran this scan on every request. So I filed a ticket to read the location already stored on the visitor’s row and only fall back to the scan for new visitors. The next day I scripted the procedure out of production and read it. The scan only runs inside the branch for a new IP, and the code path for a known IP never reads the location at all. My ticket had nothing to short-circuit, so I rescoped it to a small reorder of the new-IP block. The index below is the fix for the query where it does run.

Why the seek lies

The clustered index is keyed on (startIpNumber, endIpNumber, locID). The optimizer looks at startIpNumber <= @ip and sees a sargable predicate on the leading key column. So it does a B-tree seek to the upper bound of startIpNumber and starts walking backward (or, equivalently, walks forward to the upper bound, depending on how it’s framed). Every row it touches in that walk gets its endIpNumber tested.

The plan shows Index Seek. Pretty green icon. Optimizer cost is low.

The problem is that “seek to the upper bound and walk” can match an enormous number of rows. For a visitor with an IP in the middle of the address space, the seek lands halfway through the table and the engine walks ~2 million rows before TOP 1 fires on the first row whose endIpNumber >= @ip. The “seek” is doing about half the work of a full scan.

This is the difference between an index seek (B-tree navigation to a specific point) and an index seek range (the actual set of rows that pass the leading-column predicate). When the leading predicate is one-sided (<= @ip with no lower bound), the seek range can be enormous, and the remaining predicates are applied as residuals during the scan of that range.

The fix is a second seek path

There’s no way to make startIpNumber <= @ip two-sided. The data is what it is. But the optimizer can be given a different index whose seek range is small for the same query:

CREATE NONCLUSTERED INDEX IX_mapIPtoLocation_endIp_startIp
    ON dbo.mapIPtoLocation (endIpNumber, startIpNumber)
    INCLUDE (locID)
    WITH (ONLINE = ON, DATA_COMPRESSION = PAGE);

Now the optimizer has two angles of attack:

  1. Seek by startIpNumber <= @ip, walk down through endIpNumber (the old half-table-scan path).
  2. Seek by endIpNumber >= @ip, walk up through startIpNumber (the new path).

Critically, for a well-formed geoIP dataset, almost no rows have an endIpNumber greater than @ip and a startIpNumber greater than @ip. Those rows are ranges that haven’t reached @ip yet. The first row where endIpNumber >= @ip is overwhelmingly likely to also satisfy startIpNumber <= @ip, because ranges don’t overlap and they’re sorted. The seek range on the new index is tiny. TOP 1 fires almost immediately.

The INCLUDE (locID) makes the index covering, so the lookup never touches the base table.

The empirical check that mattered

The whole argument above rests on one assumption: ranges don’t overlap. If they do, the same one-sided pathology can recur on the new index. So before deploying, one query against the live table:

WITH ordered AS (
    SELECT startIpNumber, endIpNumber,
           LAG(endIpNumber) OVER (ORDER BY startIpNumber) AS prev_end
    FROM   dbo.mapIPtoLocation
)
SELECT COUNT(*) AS overlapping_pairs
FROM   ordered
WHERE  prev_end IS NOT NULL
  AND  prev_end >= startIpNumber;

Result: zero. Across all four million rows. The assumption holds; the design is sound.

The lesson

Index Seek in a query plan does not mean “fast.” It means the engine used a B-tree to find an entry point. What happens after that entry point is the whole story. When the leading predicate is a one-sided range, the seek range can be unbounded on one side, and you’re doing a scan with extra steps.

The fix is usually not to rewrite the query, though ORDER BY startIpNumber DESC TOP 1 plus a post-filter is another lever that can also work. The real fix is to give the optimizer a different B-tree to enter from, oriented around the other side of the range. Two seek paths, one of which is always cheap.

Cost: ~40 MB of compressed index, ~30 seconds of online build, zero write amplification because the underlying data is static.

The 40 MB of compressed index now sits beside the four-million-row table doing exactly what the original clustered key couldn’t: giving every lookup a seek range that collapses to almost nothing. The zero from the overlap check is the reason it works and the reason it will keep working without maintenance, and the 332ms figure that started this whole investigation turned out to describe a code path that barely runs at all. What’s left is a query that still says Index Seek in the plan, only now the words are finally true.