A "Longest-Prefix" Solution for SQL

A River of Words

Thursday, February 26. 2009

A "Longest-Prefix" Solution for SQL

Something came up in IRC today, I thought I found a pretty nice solution to it, thought I’d share it here. A guy has a table in his database that contains ‘prefixes’. It looks like this:

id number
1 1
2 1800
3 18
4 180
5 1801

Given the phone number “18005551234”, he’d like to find the longest valid prefix. He had suggested to me that he was considering a stored procedure which loops, character-by-character, through the input looking for the longest match. Instead, I recommended he use ‘replace’ to trim the ‘prefixes’ off of the input, and let an ‘order by’ tell him which of those actually resulted in the shortest remaining string (and thus, was the longest match).

The query I ended up with goes something like this:
select id from prefixes order by length(replace('18005558355', number, '')) asc limit 1;
Given a better understanding of mysql’s ‘replace()’, we ended up using this instead – note the identities are renamed to reflect his actual sytem:
SELECT id, prefix from routes where locate(prefix, '18005558355') = 1 order by length(prefix) desc limit 1;

Is there a better way? Below the fold is a quick (postgresql) “dump” of the database in question so you can come up with your own proposals.

CREATE TABLE prefixes ( id integer NOT NULL, number character varying(20));

CREATE SEQUENCE prefixes_id_seq INCREMENT BY 1 NO MAXVALUE NO MINVALUE CACHE 1;
ALTER SEQUENCE prefixes_id_seq OWNED BY prefixes.id;

ALTER TABLE prefixes ALTER COLUMN id SET DEFAULT nextval('prefixes_id_seq'::regclass);
ALTER TABLE ONLY prefixes ADD CONSTRAINT prefixes_pkey PRIMARY KEY (id);
-- We don't want to ever allow duplicate entries for the same prefix
CREATE UNIQUE INDEX idxu_prefixes_number ON prefixes USING btree (number);

INSERT INTO prefixes (id, number) VALUES (1, '1');
INSERT INTO prefixes (id, number) VALUES (2, '1801');
INSERT INTO prefixes (id, number) VALUES (3, '18');
INSERT INTO prefixes (id, number) VALUES (4, '18005');
INSERT INTO prefixes (id, number) VALUES (5, '1800');
INSERT INTO prefixes (id, number) VALUES (6, '180');

Posted by TML in Programming at 14:32 | Comments (3) | Trackbacks (0)

Trackbacks
Trackback specific URI for this entry

No Trackbacks

Comments
Display comments as (Linear | Threaded)

The more I think about it, the more I prefer the second option anyway – it’s more clear that it’s driving at the intended problem, that of "finding the longest prefix which matches" – use the where clause on locate() to say "where it matches", and the order by+locate to find the "longest".

#1 TML on 2009-02-26 16:33 (Reply)

Here’s a similar expression that seems to work with SQL Server

SELECT id, prefix from routes where charindex(prefix, ‘18005558355’) = 1 order by len(prefix) desc

#1.1 Johnny Elbows on 2009-02-26 16:38 (Reply)

This should be the equivalent PgSQL:

select id, number from prefixes where position(number in ‘18885558355’) = 1 order by length(number) desc limit 1;

#2 TML on 2009-02-26 16:38 (Reply)

Add Comment

You can use [highlight lang=langName][/highlight] tags to embed source code snippets
Textile-formatting allowed
Standard emoticons like :-) and ;-) are converted to images.
E-Mail addresses will not be displayed and will only be used for E-Mail notifications.

To prevent automated Bots from commentspamming, please enter the string you see in the image below in the appropriate input box. Your comment will only be submitted if the strings match. Please ensure that your browser supports and accepts cookies, or your comment cannot be verified correctly.
CAPTCHA

E-Mail addresses will not be displayed and will only be used for E-Mail notifications.

To prevent automated Bots from commentspamming, please enter the string you see in the image below in the appropriate input box. Your comment will only be submitted if the strings match. Please ensure that your browser supports and accepts cookies, or your comment cannot be verified correctly.
CAPTCHA
 
Submitted comments will be subject to moderation before being displayed.
 
profile for TML on Stack Exchange, a network of free, community-driven Q&A sites

Calendar

Back February '12
Mon Tue Wed Thu Fri Sat Sun
    1 2 3 4 5
6 7 8 9 10 11 12
13 14 15 16 17 18 19
20 21 22 23 24 25 26
27 28 29        

Quicksearch

Archives

Categories



All categories

Syndicate This Blog

Blog Administration

Open login screen

Powered by

Serendipity PHP Weblog

Template dropdown

Statistics

Last entry: 2011-09-01 12:27
101 entries written
51 comments have been made

Statistics

Last entry: 2011-09-01 12:27
101 entries written
51 comments have been made

Statistics

Last entry: 2011-09-01 12:27
101 entries written
51 comments have been made