Finding longest matching prefix

Question

I have two tables:

Sources:

(SName)  (SId)
Apple1   100
Apple2   200
Banks    300
BanksB   400
Bankerly 500

Prefixes:

(PName) (PId)
App     1
Bank    2
Banker  3

My goal: To find the longest prefix that matches each of sources. The results would look like this:

(SName)  (SId) (PName) (PId)
Apple1   100   App     1
Apple2   200   App     1
Banks    300   Bank    2
BanksB   400   Bank    2
Bankerly 500   Banker  3

Constraints: I am using SQL Server 2000 and cannot upgrade. I know how to solve this problem using analytic functions, but they are not available in SQL Server 2000, as far as I know.

Answer 1

One way (SQL Fiddle)

SELECT SName,
       SId,
       LEFT(SName, MAX(LEN(PName)))                                          AS PName,
       CAST(SUBSTRING(MAX(STR(LEN(PName), 10) + LTRIM(PId)), 11, 10) AS INT) AS PId
FROM   Sources S
       JOIN Prefixes P
         ON S.SName LIKE P.PName + '%'
GROUP  BY SId,
          SName 
ORDER BY SId   

I am assuming that none of the prefixes are allowed to contain characters such as % that would mess up a LIKE search.

It uses a variant of the method in listing 5 in this article on TOP N Per Group Queries to bundle the PId along with the MAX(length). Once the MAX(length) is known it can be used to re-calculate what the prefix must have been so there is no need to add PName in to the concatenation.

Answer 2

An alternative, because it's been too long since I wrote a SQL Server 2000 query (no APPLY syntax!). This way uses a table of numbers, which you probably already have:

-- Table of numbers
DECLARE @Numbers TABLE (n int PRIMARY KEY);
INSERT @Numbers (n)
SELECT number FROM master.dbo.spt_values WHERE type = N'P';

Sample data:

DECLARE @Sources TABLE (SName varchar(100), SId int);
DECLARE @Prefixes TABLE (PName varchar(100) UNIQUE, PId int PRIMARY KEY);

INSERT INTO @Sources
SELECT 'Apple1',   100 UNION ALL
SELECT 'Apple2',   200 UNION ALL
SELECT 'Banks',    300 UNION ALL
SELECT 'BanksB',   400 UNION ALL
SELECT 'Bankerly', 500;

INSERT INTO @Prefixes
SELECT 'App',     1 UNION ALL
SELECT 'Bank',    2 UNION ALL
SELECT 'Banker',  3;

Solution:

SELECT
    t.SName, 
    t.Sid,
    Pid = CONVERT(int, LEFT(t.Result, 11)),
    PName = SUBSTRING(t.Result, 12, 8000)
FROM
(
    SELECT s.SName, sId,
    (
        SELECT TOP 1
            CONVERT(char(11), p.PId) + p.PName
        FROM @Prefixes AS p
        JOIN @Numbers AS n ON
            n.n <= LEN(s.SName)
        WHERE
            p.PName = LEFT(s.SName, N.n)
        ORDER BY
            N.n DESC
    ) AS Result
    FROM @Sources AS s
) AS t;

Query plan:

And here is the SQLFiddle.