phone number prefix lookup

Question

I have to implement java based call routing engine which route calls based on the phone number prefix to the appropriate gateway.

Here my table (postgres) containing the prefixes:

CREATE TABLE call_routing (
  prefix character varying(20) PRIMARY KEY NOT NULL,
  carrier character varying(50) NOT NULL,
  dialstring character varying(50) NOT NULL
)

Some sample data:

INSERT INTO call_routing values ('02','1','/sofia/gateway/gw1');
INSERT INTO call_routing values ('0221','1','/sofia/gateway/gw2');
INSERT INTO call_routing values ('0228','1','/sofia/gateway/gw3');

For example phone number 0221123456789 should be routed to gateway "/sofia/gateway/gw2", phone number 0211123456789 should be routed to "/sofia/gateway/gw1", etc.

Questions:

1. What will be the fastest approach with java / jdbc to query the best matching prefix.
2. Is it a better approach to read the table on application startup into java objects and do everything in java without db access on each call?

Answer 1

Get a better indexing

By ordering directly on prefix, not length(prefix):

SELECT dialstring FROM call_routing
WHERE number like prefix || '%'
ORDER BY prefix DESC
LIMIT 1

Why?

Because the selected rows for a number abcdef will be prefixes. So will be numbers like:

a ab abc abcd

So if you order them alphabetically it's enough to get a list from longest to shortest, and that's what you want.

Also you can get a stronger filter using:

prefix between 'a' and 'abcde'. All your prefixes will be alphabetically >= the shortest prefix and alphabetically <= the longest one.

So it could be expressed as:

SELECT dialstring FROM call_routing WHERE
prefix between substr(number, 1, 1) and number -- range filter (use index)
AND number like prefix || '%' -- only relevant data (normal filter)
ORDER BY prefix DESC -- index will work
LIMIT 1

And of course the index will be on column prefix.

Cache all?

Yes, please. :)

How many items do you have? If it's not a huge list, load it in memory.

Then you can have a TreeMap (if you want order by prefix) or a HashMap (if you prefer to find the longest prefix first and keep trying with one char less each time). Which one will be better? Depends on the number of prefixes that are in the range a >> abcde and don't match the like condition (abbde by example).

If there are no a lot of entries

You could use an array, sorted by prefix desc:

be
b
abcde
abbbc
abd
ab

For finding the good prefix do an Arrays.binarySearch(T[], T key, Comparator<T>) to find if your phone is in there (abcde). If it is... ok. If it's not you move forward until:

- you find a prefix (OK, this is the winner)
- it doesn't start with the same char (there are no prefix)

This way you are traversing the range abcde >> a and finding the first prefix (it is, the longest possible).

The good one

Is making a T-R-E-E (I'm not sure about the name). Make a tree where each node holds only a letter (number in your case).

0 // represents 0
 ->
   2  // represents 02
     -> 1 // represents 021
     -> 3 // represents 023
 ->
   4 // represents 04

So when you look for you longest prefix you try to get as deep as possible in your tree:

Node n = root;
for (char c: number) {
    if ((child = n.hasChild(c)) != null)
    {
       prefix += c;
       n = child;
    }
    else
       break;
}

You just need a to create a

class Node
{
   int digit;
   Map<Integer, Node> childs = new HashMap<Integer, Node>(); // or a 10 bucket array :)
   YourInfo info;
}

And for creating the structure:

findOrCreateNode(prefix).setInfo(info);

where findOrCreateNode is the same as before but when it doesn't found the node... creates it (n.put(c, new Node(c))).