Hello to all who read this.  My goal is to create a highly efficient commercial grade routing
system for VOIP carriers who handle hundreds of thousands of calls daily, if not millions.  For
each of these calls a telephony engine must query the database for 2 pieces of information,
where the call goes, and wether or not the system will carry the audio stream of the call or request
the source and destination communicate directly.  Here is an example result expected...


               route             | rtp_forward
---------------------------------+-------------
 sip/sip:12345678901@12.34.56.78 | yes


I have achieved this with the following query and tables however the performance is not enough and I
feel either optimization or a new approach is in order.  Any suggestions would be greatly appreciated.


SELECT
  LOWER(protocol) || '/' || (CASE WHEN LOWER(protocol) = 'sip' THEN 'sip:' ELSE '' END) || prefix ||
    SUBSTR('${called}', (CASE WHEN strip1 AND SUBSTR('${called}', 7, 1) = '1' THEN 8 ELSE 7 END)) ||
    '@' || host::varchar AS route,
  (SELECT rtp_forward FROM clients WHERE SUBSTR('${called}', 1, 6) = prefix) AS rtp_forward
FROM providers
WHERE
  destid = (SELECT destid FROM routes WHERE SUBSTR('${called}', 1, 6) IN (SELECT prefix FROM
    clients WHERE (CASE WHEN type = 'prepaid' AND balance <= 0 THEN false ELSE true END) AND active) AND
  class = (SELECT class FROM clients WHERE prefix = SUBSTR('${called}', 1, 6) AND active) AND
  SUBSTR('${called}', (CASE WHEN strip1 AND SUBSTR('${called}', 7, 1) = '1' THEN 8 ELSE 7
    END)) LIKE route || '%%' AND active ORDER BY route DESC, rate ASC LIMIT 1) AND
  active

${called} is replaced by the telephony engine before each query is executed with the following...

55555512345678901

...where the first 6 digits are always used as client identification and the remaining are the DID,
or destination ID, the number dialed.  So in this instance client 555555 would be calling 12345678901.

Desired actions needed by query.  The client must match an active entry in the clients table, the
dialed number must match an applicable active route in the routes table. There must be an active
entry in the providers table matching the 'destid' of the route designated.  And the result must be
formated as shown above, with a valid voip uri string and the rtp_forward boolean value.

The routes table should be expected to consist of hundreds of thousands of different 'route'
combinations.  ie, at any given time it could contain an easy 500,000 rows.  The job of the query
is to return the longest matching route. In the case of duplicates the least expensive is chosen.

Here's the tables with example data...


           Table "public.clients"
   Column    |       Type        | Modifiers
-------------+-------------------+-----------
 name        | character varying |
 prefix      | character varying |
 class       | integer           |
 rtp_forward | character varying |
 type        | character varying |
 balance     | double precision  |
 active      | boolean           |


  name   | prefix | class | rtp_forward |     type     | balance | active
---------+--------+-------+-------------+--------------+---------+--------
 Client1 | 123456 |     1 | yes         | postpaid     | 1012.64 | t
 Client2 | 555555 |     1 | yes         | postpaid     |    23.1 | t
 Client3 | 420420 |     2 | no          | unrestricted |       0 | t


         Table "public.providers"
  Column  |       Type        | Modifiers
----------+-------------------+-----------
 destid   | integer           |
 name     | character varying |
 alias    | character varying |
 prefix   | character varying |
 protocol | character varying |
 host     | character varying |
 port     | integer           |
 strip1   | boolean           |
 active   | boolean           |


 destid |   name    | alias | prefix | protocol |      host     | port | strip1 | active
--------+-----------+-------+--------+----------+---------------+------+--------+--------
      1 | Provider1 | p1    | 828282 | h323     | 12.23.34.45   | 1720 | f      | t
      2 | Provider2 | p2    |        | sip      | 1.2.3.4       | 5060 | f      | t
      3 | Provider3 | p3    | 494949 | sip      | 123.234.56.78 | 5060 | t      | t


            Table "public.routes"
   Column    |       Type        | Modifiers
-------------+-------------------+-----------
 route       | character varying | not null
 lata        | character varying |
 ocn         | character varying |
 rate        | double precision  |
 cost        | double precision  |
 init        | integer           |
 inc         | integer           |
 description | character varying |
 class       | integer           |
 destid      | integer           |
 active      | boolean           |
Indexes:
    "routes_pkey" PRIMARY KEY, btree (route)


  route  | rate | cost | init | inc | description | class | destid | active
---------+------+------+------+-----+-------------+-------+--------+--------
 1       |  3.1 |  1.5 |    6 |   6 | Primary 1+  |     1 |      1 | t
 1234    |  2.5 | 1.12 |    6 |   6 | p2 offnet   |     1 |      2 | t
 1234567 | 1.25 | 0.75 |    6 |   6 | p3 onnet    |     1 |      3 | t


I am testing this on a Pentium D 3.0 dual core w/ 1 gig ddr and a 10k sata w/ Linux 2.6.13 and
PostgreSQL 8.1beta3 (yes I should grab the latest release, just haven't done it yet).  I've optimized
postgresql.conf by modifying shared_buffers & effective cache size to the best of my knowledge after
reading various PostgreSQL optimizing guides.  The query under no load (ie, telephony engine is not
requesting info) complete in aprox 50-70ms.  Like I said earlier, this is not enough.  I'd like to
see it under the 10 ms mark if at all possible.

Looking forward to any insight,

James Saunders