Rate/trunk selection? Cost sorting + comments/questions

delineate · **Joined:** Fri Sep 05, 2008 1:11 am **Posts:** 4

This is a continuation of ticket 545, which it turns out is a contentious issue.

I understand this patch is unlikely to be included, but thought I'd at least demonstrate my attempt at a solution.
It can select and sort records the "traditional" way, or select the most specific rate per ratecard and then sort on rates, with 'defaultprefix' rates pushed to the bottom.
The latter may be desirable if you have 2 providers, with 1 ratecard (per range of destinations) and one provider has a cheaper rate but matching on a shorter prefix.
It also does all the work SQL, except the filtering of rates based on distinct trunks.

I believe this is a drop in solution, except for 2 points about which I have questions at the end.
The patch refactors a how the SQL code is generated quite a bit, so I'll show the original and results as stripped down SQL.

The original SQL rate selection looks essentially like this (more full version at end)

Code:

  SELECT tariffgroupname, lcrtype, tariffname, cc_ratecard.id, dialprefix, destination, buyrate /* etc */
  FROM cc_tariffgroup
  RIGHT JOIN cc_tariffgroup_plan ON cc_tariffgroup_plan.idtariffgroup=cc_tariffgroup.id
  INNER JOIN cc_tariffplan ON (cc_tariffplan.id=cc_tariffgroup_plan.idtariffplan )
  LEFT JOIN cc_ratecard ON cc_ratecard.idtariffplan=cc_tariffplan.id

  WHERE /* Call Plan Constraint */  AND /* Prefix Constraints */
   AND /* Ratecard Contraints */  AND /* Rate contraints */
   AND /* DNID Ratecard constraint */  AND /* CallerID Ratecard constraint */
ORDER BY LENGTH(dialprefix) DESC

My traditional reimplementation looks like this:

Code:

: SELECT tariffgroupname, lcrtype, tariffname, cc_ratecard.id, dialprefix, destination, buyrate, /* etc */
:          CASE WHEN cc_ratecard.dialprefix = 'defaultprefix' THEN 0 ELSE length(cc_ratecard.dialprefix) END as prefix_length
: FROM cc_tariffgroup
: RIGHT JOIN cc_tariffgroup_plan ON cc_tariffgroup_plan.idtariffgroup=cc_tariffgroup.id
: INNER JOIN cc_tariffplan ON (cc_tariffplan.id=cc_tariffgroup_plan.idtariffplan )
: LEFT JOIN cc_ratecard ON cc_ratecard.idtariffplan=cc_tariffplan.id
:
: WHERE /* Call Plan Constraint */  AND /* Prefix Constraints */
:   AND /* Ratecard Contraints */  AND /* Rate contraints */
   AND /* DNID Ratecard constraint */  AND /* CallerID Ratecard constraint */
ORDER BY prefix_length DESC,
         CASE WHEN (SELECT st2.lcrtype FROM cc_tariffgroup AS st2 WHERE cc_tariffgroup.id = 1 LIMIT 1) = 0 THEN cc_ratecard.buyrate ELSE cc_ratecard.rateinitial END

The first 2 changes (lines 2,11) sort by prefix length with 'defaultprefix' the shortest (and last)
The last change (line 12) sorts on buyrate or rateinitial depending on the LCR type.
Additional tertiary sorts could be appended.

The new rate based sorting method looks like this:

Code:

: SELECT tariffgroupname, lcrtype, tariffname, cc_ratecard.id, dialprefix, destination, buyrate, /* etc */
:          cc_ratecard.dialprefix = 'defaultprefix' AS is_default
: FROM cc_tariffgroup
: RIGHT JOIN cc_tariffgroup_plan ON cc_tariffgroup_plan.idtariffgroup=cc_tariffgroup.id
: INNER JOIN cc_tariffplan ON (cc_tariffplan.id=cc_tariffgroup_plan.idtariffplan )
: LEFT JOIN ( SELECT st1.idtariffplan, MAX(length(st1.dialprefix)) AS max_len FROM cc_ratecard AS st1
:                  WHERE /* Rate contraints */ AND /* Prefix Constraints */
:                  GROUP BY st1.idtariffplan
:                ) AS most_specific ON most_specific.idtariffplan = cc_tariffplan.id
LEFT JOIN cc_ratecard ON cc_ratecard.idtariffplan = cc_tariffplan.id AND CASE WHEN most_specific.max_len IS NOT NULL
                                     THEN length(cc_ratecard.dialprefix) = most_specific.max_len 
                                     ELSE cc_ratecard.dialprefix = 'defaultprefix' END

WHERE /* Call Plan Constraint */  AND /* Prefix Constraints */
   AND /* Ratecard Contraints */  AND /* Rate contraints */
   AND /* DNID Ratecard constraint */  AND /* CallerID Ratecard constraint */
ORDER BY is_default ASC,
         CASE WHEN (SELECT st2.lcrtype FROM cc_tariffgroup AS st2 WHERE cc_tariffgroup.id = 1 LIMIT 1) = 0 THEN cc_ratecard.buyrate ELSE cc_ratecard.rateinitial END ASC,

Lines 2 and 17 push the 'defaultprefix' rates to the bottom.
Lines 6-9 figures out the length of the longest prefix for each ratecard (cc_tariffplan)
Lines 10-12 makes sure we only join the most specific rate to each ratecard (cc_ratecard to cc_tariffplan)
Note: Not shown, but in the subquery /* Prefix Constraints */, we remove the 'OR dialprefix='defaultprefix' constraint.
If no normal rates are found, any available defaultprefix rates are attached on line 12.

So what are the results?
Consider the following termination Rates and the destination 011336xxxx

Code:

Provider    Ratecard     prefix             rate
A             A-NA          defaultprefix    0.02
A             A-AZ          01133            0.05
B             B-NA          defaultprefix    0.03
B             B-AZ          01133             0.04
B             B-AZ          011336            0.30

The original system (including the php routines)

Code:

B             B-AZ          011336            0.30  <=
B             B-AZ          01133             0.04
A             A-AZ          01133             0.05  <=
A             A-NA          defaultprefix    0.02
B             B-NA          defaultprefix     0.03

The arrows indicate the rates chosen via the distinct trunk selection.
This may be fine depending how you've organized your ratecards.
My implementation in traditional mode ($callplan_priority=0)
should result in the above list straight from the database (without the php default and prefix sorting)

Set $callplan_priority = 1 and you get the following database output:

Code:

Provider    Ratecard     prefix             rate
A             A-AZ          01133             0.05 <=
B             B-AZ          011336            0.30 <=
A             A-NA          defaultprefix    0.02
B             B-NA          defaultprefix     0.03

If A-AZ didn't exist, we would have

Code:

Provider    Ratecard     prefix             rate
B             B-AZ          011336            0.30 <=
A             A-NA          defaultprefix    0.02  <=
B             B-NA          defaultprefix     0.03

In all situations, it is good that defaults are pushed to the bottom and used last, because they are really for NA (N.America) and shouldn't be used to call International (France).
That's my best guess why defaults are pushed to the bottom anyways.
That begs the question though, in what situations would we want to actually use/include a default rate?

Performance
One thing I've noticed is that /* Asterisk pattern matching */ slows the query significantly (like 5X), so I've also made that a configurable option.
This is by no means a rigorous performance test, but here is my quick results on ~15k ratecards (ms, postgres maxcost ) on one destination.

Code:

                       | Original     | Original*  | Traditional | Traditional* | Ratecard cost sort | Ratecard cost sort*
Asterisk patterns     | 250, 1124  | 90, 1636  |  250,1139 |  86,1704     | 320, 2625            | 138, 3238
No Asterisk patterns | 35, 120     | 35, 138   |  30, 122    | 40, 153      | 35, 232                | 30,   271

*uses the non-subselect DNID and CallerID constraints (See implementation notes)
Preliminary performance conclusions:
1) DNID, CID constraints can be costly, especially in conjunction w/ Asterisk matching.
2) Asterisk pattern matching is very costly
3) patch is more costly, however proper comparison should include php overhead in originals.

Implementation Notes:
Only tested in Postgres!
Should work in MySQL5 as it's more accepting.

Configuration
All config variables are set in patch to emulate the original implementation.
Currently the rate select mode and the asterisk regex mode are controlled internally by the variables $callplan_priority and $enable_asterisk_matching.
The could be set by the agi-conf system, or even as callplan variables.
I could see having a callplan choice of

absolute prefix length sorting

cost sort on longest prefix length per ratecard

cost sort on longest prefix length per trunk (not implemented in patch)
And the additional choice of if 'defaultprefix' rates should be appended

Always

when no other rates on ratecard

when no other rates on trunk

Never
'defaultprefix'
Interestingly, 'defaultprefix' is functionally equivalent to an empty string, and if stored that way, would eliminate the need for the special case.

Join types
The type of joins used in the original really doesn't make sense to me.
I even double checked my understanding of JOIN types
From the original code:

Code:

FROM cc_tariffgroup
RIGHT JOIN cc_tariffgroup_plan ON cc_tariffgroup_plan.idtariffgroup=cc_tariffgroup.id
INNER JOIN cc_tariffplan ON (cc_tariffplan.id=cc_tariffgroup_plan.idtariffplan )
LEFT JOIN cc_ratecard ON cc_ratecard.idtariffplan=cc_tariffplan.id

I don't understand why these Join types would be used? I would have thought this would make more sense:

Code:

FROM cc_tariffgroup
[INNER] JOIN cc_tariffgroup_plan ON cc_tariffgroup_plan.idtariffgroup=cc_tariffgroup.id
[INNER] JOIN cc_tariffplan ON (cc_tariffplan.id=cc_tariffgroup_plan.idtariffplan )
[INNER] JOIN cc_ratecard ON cc_ratecard.idtariffplan=cc_tariffplan.id

The inner is implied - with Postgres anyway.

Sure, the original works when everything is good.
If there are no orphans in cc_tariffgroup_plan, cc_tariffplan, or cc_ratecard, there's not really a semantic difference AFAIK.
However, the PHP code is expecting either only valid rates, or no rates for a rate lookup failure.
If we should have 'orphans' in cc_tariffgroup_plan, cc_tariffplans (ratecards) without an associated cc_tariffgroup (callplan) would be returned due to the right join.
Similarily, a cc_tariffplan w/o a rate would still return a row with null cc_ratecard fields.
Shouldn't the failsafe behaviour be to not return irrelevant or empty rate records?
So, my patch implements with inner joins.

DNID and CallerID Sub-queries
This part of the query looks like this (same fomat for CallerID) and has essentially been this way since revision 1.
But I don't understand why the subselect is needed.

Code:

dnidprefix= SUBSTRING('xxxxxxxxxxxx',1,length(dnidprefix))
OR (dnidprefix='all' 
      AND 0 = (SELECT count(dnidprefix)
                   FROM cc_tariffplan
                   RIGHT JOIN cc_tariffgroup_plan ON cc_tariffgroup_plan.idtariffgroup=1
                   WHERE dnidprefix=SUBSTRING('xxxxxxxxxxxx',1,length(dnidprefix)))      

I read it as:

Code:

Select a ratecard where 
-the ratecard dnidprefix "mask" matches ours
OR
-the rate card matches 'all', but only where no other dnidprefix matching cards exist.

I suppose that would make more sense to me if by 'all', we mean 'default'
I've added variables dnid_all_means_default and $cid_all_means_default that uses the faster
form when set to 0.

Code:

dnidprefix='all' OR SUBSTRING('xxxxxxxxxxxx',1,length(dnidprefix)) = dnidprefix

Also, if dnid or callerid are empty, we drop all the substring parts of the query as there's no point.
And I use [INNER] JOIN for the same reason - No point counting 'NULL' ratecards.

That's all :shock:

Well, that's the result of my personal code review, sorry it's so long...
I've attached a patch that should work 1.4RC1+ as well as a seperate file containing the full modified function.
Please feel free to take whatever you like from it.
Any problems, feedback or insight into my questions is appreciated.
(Or performance results!)

If you don't like it or it breaks your system, please detail your usage configuration or there's no point discussing really.

Cheers!

Simplified Original SQL

Code:

SELECT tariffgroupname, lcrtype, tariffname, cc_ratecard.id, dialprefix, destination, buyrate /* etc */
FROM cc_tariffgroup
RIGHT JOIN cc_tariffgroup_plan ON cc_tariffgroup_plan.idtariffgroup=cc_tariffgroup.id
INNER JOIN cc_tariffplan ON (cc_tariffplan.id=cc_tariffgroup_plan.idtariffplan )
LEFT JOIN cc_ratecard ON cc_ratecard.idtariffplan=cc_tariffplan.id
/* Skipping the trunk joins */

WHERE cc_tariffgroup.id=1 /* Call Plan Constraint */
  /* Prefix Constraints */
  AND ((dialprefix='12345678900' OR dialprefix='12345678900' OR dialprefix='12345678900' OR dialprefix='12345678900' OR dialprefix='12345678900'
       OR dialprefix='190590' OR dialprefix='19059' OR dialprefix='1905' OR dialprefix='190' OR dialprefix='19' OR dialprefix='1' 
       OR dialprefix='defaultprefix' /* Prefix Matching */
      ) OR ( /* Asterisk pattern matching */
       dialprefix LIKE '&_%' ESCAPE '&'
       AND '12345678900' ~* REGEXP_REPLACE(REGEXP_REPLACE(REGEXP_REPLACE(REGEXP_REPLACE(REGEXP_REPLACE(('^' ||  dialprefix ||  '$'),
           'X', '[0-9]', 'g'), 'Z', '[1-9]', 'g'), 'N', '[2-9]', 'g'), E'\\.', E'\\.+', 'g'), '_', '', 'g')))
  /* Ratecard Contraints */
  AND startingdate <= CURRENT_TIMESTAMP
  AND (expirationdate > CURRENT_TIMESTAMP OR expirationdate IS NULL)
  /* Rate contraints */
  AND startdate <= CURRENT_TIMESTAMP
  AND (stopdate > CURRENT_TIMESTAMP OR stopdate IS NULL)
  AND (starttime <= 1429 AND endtime >=1429)
  AND idtariffgroup='1' /* Redundant SQL */
  /* DNID Ratecard constraint */
  AND ( dnidprefix= SUBSTRING('xxxxxxxxxxxx',1,length(dnidprefix))
       OR (dnidprefix='all' 
           AND 0 = (SELECT count(dnidprefix)
                    FROM cc_tariffplan
                    RIGHT JOIN cc_tariffgroup_plan ON cc_tariffgroup_plan.idtariffgroup=1
                    WHERE dnidprefix=SUBSTRING('xxxxxxxxxxxx',1,length(dnidprefix))) 
          )
      )
  /* CallerID Ratecard constraint */
  AND ( calleridprefix = SUBSTRING('yyyyyyyyyyyy',1,length(calleridprefix))
        OR (calleridprefix = 'all' 
            AND 0 = (SELECT count(calleridprefix)
                     FROM cc_tariffplan
                     RIGHT JOIN cc_tariffgroup_plan ON cc_tariffgroup_plan.idtariffgroup=1
                     WHERE calleridprefix=SUBSTRING('yyyyyyyyyyyy',1,length(calleridprefix)) )
            )
       )
ORDER BY LENGTH(dialprefix) DESC

provided by Star2Billing S.L.

Rate/trunk selection? Cost sorting + comments/questions

Who is online