Improve Speed of RPI Calculation

Question

It currently takes about 10 minutes to process ~16k teams and ~81k games. I could soon have ~17k teams with ~160k, and multiple sports. I run this as a cron job overnight and store the results in a serialized gzipped array which is processed upon each pageload to sort teams by states for displaying and actually calculate the RPI (add WP, OWP and OOWP together) which works well for speed for displaying purposes. I'm only concerned with trying to speed up this calculation:

If you need more information about what the RPI (Ratings Percentage Index) is, this is a good primer. Please note, I have modified from this formula to include a weighting factor (function reduction_factor() ) so it is slightly different that that page states.

Here is my base function:

// *********************************************************************************************************************************
// function to calculate RPI given a sportid and year, optional cutoff date
// *********************************************************************************************************************************
function rpi($sportid, $year, $date = FALSE, $my_db, $sport_array){
    //figure out if this is a year-spanning sport
    $year_display = $year;
    $date_start = $year.$sport_array[$sportid]['start_date'];
    $date_end = $year.$sport_array[$sportid]['end_date'];

    if ($sport_array[$sportid]['end_year_plus']){
        $year_display = $year.'-'.($year+1);
        $date_end = ($year+1).$sport_array[$sportid]['end_date'];
    }

    if ($date) $date_end = $date;
    elseif ($date_end > date("Y-m-d")) $date_end = date("Y-m-d");


    $rpiteamarray = array();

    $results = $my_db->query("SELECT `teamid` FROM `team` WHERE `jv` = '0' AND `teamid` > 0;");

    while ($row = $results->fetchRow(MDB2_FETCHMODE_ASSOC)){
        $teamid = $row['teamid'];

        if (!array_key_exists($teamid, $rpiteamarray)) $rpiteamarray[$teamid] = new rpiteam($teamid, $sportid, $year, $my_db, $date_start, $date_end);
        if ($rpiteamarray[$teamid]->total_games() == 0) continue;
        $rpi[$teamid]['numgames'] = $rpiteamarray[$teamid]->total_games();
    }
    unset($results, $row);

    foreach ($rpi as $teamid => $value){
        $rpi[$teamid]['wp'] = $rpiteamarray[$teamid]->wp();
        $rpi[$teamid]['owp'] = $rpiteamarray[$teamid]->owp($rpiteamarray);
        $rpi[$teamid]['oowp'] = $rpiteamarray[$teamid]->oowp($rpiteamarray);
    }

    return $rpi;
}

Here is my rpiteam class:

<?php
class rpiteam {
    protected $sportid, $levelid, $levelid_state, $year, $wins, $loss, $tie, $total, $wp, $db, $opponentsarray, $date_start, $date_end;

    function __construct($teamid, $sportid, $year, $db, $date_start, $date_end) {
        if ($teamid == '') return null;
        if ($year == '') return null;
        if ($sportid == '') return null;

        $this->db = $db;
        $this->sportid = $sportid;
        $this->teamid = $teamid;
        $this->year = $year;
        $this->date_start = $date_start;
        $this->date_end = $date_end;

        $row = $this->db->query("SELECT `levelid`,`levelid_state` FROM `team_class` WHERE `teamid` = $teamid AND `sportid` = $sportid AND `year` = $year;")->fetchRow(MDB2_FETCHMODE_ASSOC);
        $this->levelid = $row['levelid'];
        $this->levelid_state = $row['levelid_state'];
        $this->opponentsarray = array();
    }

    public function wins(){
        if ($this->wins) return $this->wins;
        $this->wins = $this->db->query("SELECT COUNT(`winner`) FROM `game` WHERE `sportid` = $this->sportid AND `winner` = $this->teamid AND `date` BETWEEN '$this->date_start' AND '$this->date_end';")->fetchOne();
        return $this->wins;
    }

    public function loss(){
        if ($this->loss) return $this->loss;
        $this->loss = ($this->total_games())-($this->wins());
        return $this->loss;
    }

    public function total_games(){
        if ($this->total) return $this->total;
        //echo "SELECT COUNT(`winner`) FROM `game` WHERE `sportid` = $this->sportid AND `winner` IS NOT NULL AND (`hometeam` = $this->teamid OR `awayteam` = $this->teamid) AND `date` BETWEEN '$this->date_start' AND '$this->date_end';";
        $this->total = $this->db->query("SELECT COUNT(`winner`) FROM `game` WHERE `sportid` = $this->sportid AND `winner` IS NOT NULL AND (`hometeam` = $this->teamid OR `awayteam` = $this->teamid) AND `date` BETWEEN '$this->date_start' AND '$this->date_end';")->fetchOne();
        return $this->total;
    }

    public function get_opponentsarray(){
        if ($this->opponentsarray) return $this->opponentsarray;

        $opponentsarray = array();

        $result = $this->db->query("SELECT `hometeam`,`awayteam`,`winner` FROM `game` WHERE `sportid` = $this->sportid AND `winner` IS NOT NULL AND (`hometeam` = $this->teamid OR `awayteam` = $this->teamid) AND `date` BETWEEN '$this->date_start' AND '$this->date_end' ORDER BY `date` ASC;");
        while ($row = $result->fetchRow(MDB2_FETCHMODE_ASSOC)){
            if ($row['hometeam'] == $this->teamid){
                if ($row['winner'] == $this->teamid) $opponentsarray[$row['awayteam']] = 'W';
                elseif ($row['winner'] == 0) $opponentsarray[$row['hometeam']] = 'T';
                else $opponentsarray[$row['awayteam']] = 'L';
            }
            elseif ($row['awayteam'] == $this->teamid){
                if ($row['winner'] == $this->teamid) $opponentsarray[$row['hometeam']] = 'W';
                elseif ($row['winner'] == 0) $opponentsarray[$row['hometeam']] = 'T';
                else $opponentsarray[$row['hometeam']] = 'L';
            }
        }
        $this->opponentsarray = $opponentsarray;
        return $this->opponentsarray;
    }

    public static function reduction_factor($levelid){
        switch ($levelid){
            case 66: return 1.00;
            case 55: return 1.00;
            case 44: return 0.90;
            case 33: return 0.75;
            case 22: return 0.60;
            case 11: return 0.45;
            case 9:  return 0.40;
            case 8:  return 0.35;
            case 7:  return 0.30;
            case 6:  return 0.15;
            default: return 1.00;
        }
    }

    // *********************************************************************************************************************************
    // Calculate WP (winning percentage)
    // *********************************************************************************************************************************
    public function wp(){
        if ($this->wp) return $this->wp;

        if ($this->total_games() == 0) {
            $this->wp = 0;
            return $this->wp;
        }

        $reduce = $this->reduction_factor($this->levelid_state);

        $this->wp = round($this->wins()/$this->total_games() * $reduce, 4);
        return $this->wp;
    }

    // *********************************************************************************************************************************
    // Calculate WP (winning percentage) with exclusion
    // *********************************************************************************************************************************
    public function wp_exclude($team_excluding, $rpiteamarray){
        $opponentsarray = $this->get_opponentsarray();

        $wins = 0;
        $total = 0;

        foreach ($opponentsarray as $key => $value){
            if ($key == $team_excluding) continue;
            ++$total;
            if ($value == 'W') ++$wins;
            elseif ($value == 'T') $wins = $wins + 0.5;
        }

        if ($total == 0) return 0;
        return round($wins/$total * $this->reduction_factor($this->levelid_state), 4);
    }

    // *********************************************************************************************************************************
    // Calculate OWP (opponents winning percentage)
    // *********************************************************************************************************************************
    public function owp($rpiteamarray){
        $opponentsarray = $this->get_opponentsarray();

        $owp = 0;
        $total = 0;

        foreach ($opponentsarray as $key => $value){
            ++$total;
            $owp += $rpiteamarray[$key]->wp_exclude($this->teamid, $rpiteamarray);
        }
        if ($total == 0) return 0;
        return round($owp/$total, 4);
    }

    // *********************************************************************************************************************************
    // Calculate OWP (opponents winning percentage)
    // *********************************************************************************************************************************
    public function oowp($rpiteamarray){
        $opponentsarray = $this->get_opponentsarray();

        $oowp = 0;
        $total = 0;

        foreach ($opponentsarray as $key => $value){
            $owp_opponentsarray = $rpiteamarray[$key]->get_opponentsarray();

            foreach ($owp_opponentsarray as $owp_key => $owp_value){
                ++$total;
                $oowp += $rpiteamarray[$owp_key]->wp();
            }

        }
        if ($total == 0) return 0;
        return round($oowp/$total, 4);
    }
}

I use PHP with PEAR MDB2.

Is there a good way to prepare the queries used in the class? That is, can I prepare the queries once somehow, so when they are called ~16k times each it helps?

I haven't run the numbers, but I think it's querying the database 4x(num teams) or ~64k times.

Any other improvements possible?

Sorry if this is a stupid question, I haven't read over your question fully yet, but why are you checking all this data every time? Does it change? If, once its stored, its static, then you can check it once then cache the results, then each subsequent check can use the cached results instead. I'm currently looking over your code, but I may not be able to upload my answer until tomorrow. — mseancole, Jan 9, 2013 at 22:04
Can you explain a bit about why you first iterate over the recordset, store an array and then iterate again over the array? — Rob Apodaca, Jan 9, 2013 at 23:56
@mseancole The data can change with the addition of new results, and rarely the change of past results (errors, corrections). I do currently store as a file and run this calculation daily, but I'd like to increase the speed so it could be updated several times a day without hampering the rest of the website. — MECU, Jan 10, 2013 at 20:09
@RobApodaca The rpi() function flow is as follows: Get a list of all teams. Create the objects from the list of teams. If the team hasn't played any games, their values (WP, OWP and OOWP) will all be 0.0000 so I've chosen to just not display them at all so I remove them from the $rpi array. Then I run through the array to actually calculate the RPI values. — MECU, Jan 10, 2013 at 20:13
@jsanc623 @RobApodaca As it turns out, the query(s) that had (hometeam` = $this->teamid OR awayteam = $this->teamid)` were the biggest hit to performance. Each of these queries took 0.5 to 1.1 seconds. Changing this query dba.stackexchange.com/questions/45219/… makes it now take <0.002 seconds, so total execution went from 900 minutes to 2 minutes. — MECU, Jun 27, 2013 at 14:28

jsanc623 · Accepted Answer · 2013-01-08 18:42:02Z

Not quite a lot that can be done performance-wise...you have a lot of data to pour over (16,000 * 81,000 = 1,296,000,000 records and with the new data 17,000 * 160,000 = 2,720,000,000 records). You could possibly think of moving over to a faster database (Redis? Cassandra?).

Anyways, I made a few minor changes to your code - added empty() checks rather than empty string checks, shortened a few if statements, etc.

<?php

/**
 * Function to calculate RPI given a sportid and year, optional cutoff date
 */

function rpi($sportid, $year, $date = FALSE, $my_db, $sport_array){
    # figure out if this is a year-spanning sport
    $year_display = $year;
    $date_start = $year . $sport_array[$sportid]['start_date'];
    $date_end = $year . $sport_array[$sportid]['end_date'];
    $today = date("Y-m-d");
    $rpiteamarray = array();

    if($sport_array[$sportid]['end_year_plus']){
        $year_display = $year . '-' . ( $year + 1 );
        $date_end = ( $year + 1 ) . $sport_array[$sportid]['end_date'];
    }

    if($date){
        $date_end = $date;
    } else if ($date_end > $today){
        $date_end = $today;
    }

    $results = $my_db->query("SELECT `teamid` FROM `team` WHERE `jv` = '0' AND `teamid` > 0;");

    while ($row = $results->fetchRow(MDB2_FETCHMODE_ASSOC)){
        $teamid = $row['teamid'];

        if(!array_key_exists($teamid, $rpiteamarray)){
            $rpiteamarray[$teamid] = new rpiteam($teamid, $sportid, $year, $my_db, $date_start, $date_end);
        }
        if($rpiteamarray[$teamid]->total_games() == 0){
            continue; 
        }
        $rpi[$teamid]['numgames'] = $rpiteamarray[$teamid]->total_games();
    }
    unset($results, $row);

    foreach($rpi as $teamid => $value){
        $rpi[$teamid]['wp'] = $rpiteamarray[$teamid]->wp();
        $rpi[$teamid]['owp'] = $rpiteamarray[$teamid]->owp($rpiteamarray);
        $rpi[$teamid]['oowp'] = $rpiteamarray[$teamid]->oowp($rpiteamarray);
    }

    return $rpi;
}
?>

and the class:

<?php

class rpiteam {
    protected $sportid, $levelid, $levelid_state, $year,
              $wins, $loss, $tie, $total, $wp, $db,
              $opponentsarray, $date_start, $date_end;

    function __construct($teamid, $sportid, $year, $db, $date_start, $date_end){
        # You had three If statements here...just replace it with one
        if (empty($teamid) || empty($year) || empty($sportid)){
            return null;
        }

        $this->db = $db;
        $this->sportid = $sportid;
        $this->teamid = $teamid;
        $this->year = $year;
        $this->date_start = $date_start;
        $this->date_end = $date_end;

        $row = $this->db->query("SELECT `levelid`,`levelid_state` FROM `team_class` WHERE `teamid` = $teamid AND `sportid` = $sportid AND `year` = $year;")->fetchRow(MDB2_FETCHMODE_ASSOC);
        $this->levelid = $row['levelid'];
        $this->levelid_state = $row['levelid_state'];
        $this->opponentsarray = array();
    }

    public function wins(){
        if (!empty($this->wins)){
            return $this->wins;
        }

        $this->wins = $this->db->query("SELECT COUNT(`winner`) FROM `game` WHERE `sportid` = $this->sportid AND `winner` = $this->teamid AND `date` BETWEEN '$this->date_start' AND '$this->date_end';")->fetchOne();
        return $this->wins;
    }

    public function loss(){
        if (!empty($this->loss)){
            return $this->loss;
        }
        $this->loss = ($this->total_games())-($this->wins());
        return $this->loss;
    }

    public function total_games(){
        if (!empty($this->total)){
            return $this->total;
        }
        $this->total = $this->db->query("SELECT COUNT(`winner`) FROM `game` WHERE `sportid` = $this->sportid AND `winner` IS NOT NULL AND (`hometeam` = $this->teamid OR `awayteam` = $this->teamid) AND `date` BETWEEN '$this->date_start' AND '$this->date_end';")->fetchOne();
        return $this->total;
    }

    public function get_opponentsarray(){
        if (!empty($this->opponentsarray)){
            return $this->opponentsarray;
        }

        $result = $this->db->query("SELECT `hometeam`,`awayteam`,`winner` FROM `game` WHERE `sportid` = $this->sportid AND `winner` IS NOT NULL AND (`hometeam` = $this->teamid OR `awayteam` = $this->teamid) AND `date` BETWEEN '$this->date_start' AND '$this->date_end' ORDER BY `date` ASC;");
        while ($row = $result->fetchRow(MDB2_FETCHMODE_ASSOC)){
            if ($row['hometeam'] == $this->teamid){
                if ($row['winner'] == $this->teamid) $this->opponentsarray[$row['awayteam']] = 'W';
                elseif ($row['winner'] == 0) $this->opponentsarray[$row['hometeam']] = 'T';
                else $this->opponentsarray[$row['awayteam']] = 'L';
            } elseif ($row['awayteam'] == $this->teamid){
                if ($row['winner'] == $this->teamid) $this->opponentsarray[$row['hometeam']] = 'W';
                elseif ($row['winner'] == 0) $this->opponentsarray[$row['hometeam']] = 'T';
                else $this->opponentsarray[$row['hometeam']] = 'L';
            }
        }
        return $this->opponentsarray;
    }

    public static function reduction_factor($levelid){
        switch ($levelid){
            case 66: return 1.00;
            case 55: return 1.00;
            case 44: return 0.90;
            case 33: return 0.75;
            case 22: return 0.60;
            case 11: return 0.45;
            case 9:  return 0.40;
            case 8:  return 0.35;
            case 7:  return 0.30;
            case 6:  return 0.15;
            default: return 1.00;
        }
    }

    /*
     * Calculate WP (winning percentage)
     */
    public function wp(){
        if (!empty($this->wp)){
            return $this->wp;
        }

        if ($this->total_games() == 0) {
            $this->wp = 0;
            return $this->wp;
        }

        $reduce = $this->reduction_factor($this->levelid_state);

        $this->wp = round($this->wins() / $this->total_games() * $reduce, 4);
        return $this->wp;
    }

    /*
     * Calculate WP (winning percentage) with exclusion
     */
    public function wp_exclude($team_excluding, $rpiteamarray){
        $opponentsarray = $this->get_opponentsarray();

        $wins = 0;
        $total = 0;

        foreach ($opponentsarray as $key => $value){
            if ($key == $team_excluding) continue;
            ++$total;
            if ($value == 'W') ++$wins;
            elseif ($value == 'T') $wins = $wins + 0.5;
        }

        if ($total == 0) return 0;
        return round($wins / $total * $this->reduction_factor($this->levelid_state), 4);
    }

    /*
     * Calculate OWP (opponents winning percentage)
     */
    public function owp($rpiteamarray){
        $opponentsarray = $this->get_opponentsarray();

        $owp = 0;
        $total = 0;

        foreach ($opponentsarray as $key => $value){
            ++$total;
            $owp += $rpiteamarray[$key]->wp_exclude($this->teamid, $rpiteamarray);
        }
        if ($total == 0) return 0;
        return round($owp / $total, 4);
    }

    /*
     * Calculate OWP (opponents winning percentage)
     */
    public function oowp($rpiteamarray){
        $opponentsarray = $this->get_opponentsarray();

        $oowp = 0;
        $total = 0;

        foreach ($opponentsarray as $key => $value){
            $owp_opponentsarray = $rpiteamarray[$key]->get_opponentsarray();

            foreach ($owp_opponentsarray as $owp_key => $owp_value){
                ++$total;
                $oowp += $rpiteamarray[$owp_key]->wp();
            }

        }
        if ($total == 0) return 0;
        return round($oowp/$total, 4);
    }
}
?>

Like I said - very little to do with code from my POV - perhaps someone can skim through it and add their ideas on how to optimize it further.

The games don't multiply by the teams; that is, each team doesn't play 81k games. So, 81k of records/rows in the table, each game has 2 teams as a part of it. Thanks for the tip on empty(). — MECU, Jan 8, 2013 at 18:46

Rob Apodaca · Accepted Answer · 2013-01-18 00:28:03Z

I think there are two main areas you can focus on:

n+1 queries You have 1 query to select all of the teamid's and n additional queries, where n is the total number of games per team. Actually, the problem is more severe than that because you call get_opponentsarray() from owp(), oowp(), and wp_exclude(). And, wp_exclude() is also called from owp(). All of these queries and redundant queries are probably chewing up the most time. Work on creating one query (or fewer) with joins to the games table as necessary. Make sure that columns are indexed appropriately.

Serialize, gzip You mention that you are taking all of the results and storing in a serialized, gzipped array. Not sure where you are persisting that (file system?) but, I think you would be better off storing the results in a denormalized table. If fact, if you take my advice and use just one query, you could select into your results from that one query into the denormalized table.

Personally, I'd reconsider the whole approach here. Surely you are not displaying ~17k teams in a single web page. If you are, don't. If you only display ~20 teams per page, you could easily run some aggregate queries against the games table and run your rpi calculation for each. Not only would this cut out the cron/batch process, your users would always have up-to-date data displayed.

Edit: To display only a few teams per page, pass the limit and offset in the url. For example, to display teams 10 through 30, use a url like:

/teams?offset=10&limit=20

The result set should contain all data needed for the page (including the rpi calculation).

I might not understand how it works, but I think I'm "caching" the get_opponentsarray() query by storing the array as an property of the object. So the query runs the first time it needs it, then after that, it already has the array so it just returns that array. Is it not "caching" the array and operating like I think it does? — MECU, Jan 14, 2013 at 14:07
The file storing part was not part of the code shown above, but yes, stored in a file. I am not displaying ~17k teams on one page, but I do show an entire state's teams, which for some states, is in the thousands. I then use jQuery datatables to help display smartly, but, if someone isn't using javascript, they would get a single table of perhaps thousands of teams. But that is an interesting thought: Only display ~25 teams at a time which would certainly cut down on the calculation time. The trouble is: How do you know which top 25 to display, without calculating at least an entire state? — MECU, Jan 14, 2013 at 14:09
@MECU ok, yeah I guess I missed the results storage in the array. — Rob Apodaca, Jan 18, 2013 at 0:20

Community · Accepted Answer · 2017-04-13 12:43:04Z

3

Changing the query that contains

(`hometeam` = $this->teamid OR `awayteam` = $this->teamid)

To one without the OR makes that query go from 0.5-1.1 seconds to <0.002 seconds each. *20,000 occurances (or more) is a huge time delta.

See https://dba.stackexchange.com/questions/45219/how-can-i-speed-up-this-slow-simple-query

edited Apr 13, 2017 at 12:43

CommunityBot

1

answered Jun 27, 2013 at 14:30

MECU

3532 silver badges16 bronze badges

Add a comment |

Stack Exchange Network

Improve Speed of RPI Calculation

3 Answers 3

Your Answer

Not the answer you're looking for? Browse other questions tagged
php
mysqli
or ask your own question.

Hot Network Questions

Improve Speed of RPI Calculation

3 Answers 3

Your Answer

Sign up or log in

Post as a guest

Not the answer you're looking for? Browse other questions tagged phpmysqli or ask your own question.

Related

Hot Network Questions

Not the answer you're looking for? Browse other questions tagged
php
mysqli
or ask your own question.