Selecting best items

[Chris]

Code: [Select]

//...
while($row=mysql_fetch_array(...))
{
...
}
There is one table holding various items player possess. Each item has 3 fields: type (type of item), level (how good the item is), quantity (stacked items). There can be several copies of the same item type (like 10 swords of various levels).

Now I will need to do a lot of "select best sword" or "select best 5 hunting dogs and give the sum of their level". How to do it the most efficient way (performance)?

The quantity part is optional (I can live without it, but I would prefer to have it).

[CygnusX]

To select the sum of the best 5 hunting dogs based on quality...


$Result = $db->query("Select sum(qty) as MySum from Items where Type = 'HuntingDog' order by Quality Desc limit 0,5");


Like that?  Not 100% sure it works... but I think it does.

[Chris]

No, there already is a query done. Only one query for all items and all calculations The counting has to be done on PHP side.

[CygnusX]

oooh..

In that case:

I'd probably do.

$MyArray = array();

while($Row = ...)
{

  if(count($Myarray) < $NumValues)
  {
    $MyArray[$Row['Key']] = $Row['Value'];
  }
  elseif($Row['Value'] > min($MyArray) )
  {
     rsort($MyArray);
     array_pop($MyArray);
     $MyArray[$Row['Key']] = $Row['Value'];
  }

}

Am I doing it right?

[Chris]

Am I doing it right?

Not really Maybe I will post a simple solution for 1 best selection so it become more clear.

Code: [Select]

$bestsword=$bestshield=0;
while($row=mysql_fetch_array(...))
{
if($row['type']==SWORD && $row['level']>$bestsword) $bestsword=$row['level'];
if($row['type']==SHIELD && $row['level']>$bestshield) $bestshield=$row['level'];
}So, selecting "one best" is trivial (the fastest algorithm is obvious) but it becomes more complex for "select sum of 5 best" and when items are stacked.

[V3RTEXGaming]

Am I doing it right?

Not really Maybe I will post a simple solution for 1 best selection so it become more clear.

Code: [Select]

$bestsword=$bestshield=0;
while($row=mysql_fetch_array(...))
{
if($row['type']==SWORD && $row['level']>$bestsword) $bestsword=$row['level'];
if($row['type']==SHIELD && $row['level']>$bestshield) $bestshield=$row['level'];
}So, selecting "one best" is trivial (the fastest algorithm is obvious) but it becomes more complex for "select sum of 5 best" and when items are stacked.

Question, why would you handle the comparisons between their levels and such with PHP, versus the SQL query? You're retrieving an entire dataset, to only use a portion of it. Also, using mysql_fetch_array() is fine, but it creates 2 data sets, an associative array, and an indexed array, why not just use mysql_fetch_assoc() if you're going to use associative naming?

[Chris]

Question, why would you handle the comparisons between their levels and such with PHP, versus the SQL query?

Because PHP is incomparably faster than SQL. It is almost impossible to code something in PHP as unoptimized as to make it slower than additional SQL query.

Also, using mysql_fetch_array() is fine, but it creates 2 data sets, an associative array, and an indexed array, why not just use mysql_fetch_assoc() if you're going to use associative naming?

ROFL, because I never thought about it Everyone was using mysql_fetch_array so I was using it too (it's really funny no one on this forum pointed this out over these years). You are absolutely correct, using mysql_fetch_array() is stupid in more than 99% of cases.

REP +1

[CygnusX]

Thats hillarious.  I read a book once that recommended using mysql_fetch_array()... and for years I have wondered what the difference was between that and mysql_fetch_assoc().  I never realized the former also created an array of index=>values.  I guess I'll have to update my database abstraction layer now : )

[Harkins]

I wrote wrapper functions to do this back in my PHP days - so all the code to access Items would be in one class, and I could pass snippets of SQL to a function that would do the select and pass me back an array. I had no idea I was inventing my own ORM, I just got tired of seeing so much duplicated and low-level code cluttering up my app code.

[Nox]

Because PHP is incomparably faster than SQL. It is almost impossible to code something in PHP as unoptimized as to make it slower than additional SQL query.

That's quite hard to believe since SQL databases are designed specificly for such tasks...

[CygnusX]

I think he's saying that is is better to do one query and manipulate the results to your liking as oppose to doing 2 queries. 

[V3RTEXGaming]

Question, why would you handle the comparisons between their levels and such with PHP, versus the SQL query?

Because PHP is incomparably faster than SQL. It is almost impossible to code something in PHP as unoptimized as to make it slower than additional SQL query.

I wouldn't be so quick to say PHP is incomparably faster than SQL. I can run some benchmarks, but not yet. From what I've read in this thread, I don't think you'll need an extra query to do what you're trying to do.

Example:

Based on:

Code: [Select]

$bestsword=$bestshield=0;
while($row=mysql_fetch_array(...))
{
if($row['type']==SWORD && $row['level']>$bestsword) $bestsword=$row['level'];
if($row['type']==SHIELD && $row['level']>$bestshield) $bestshield=$row['level'];
}
You could manage this as such:

Code: [Select]

SELECT players.id, items.id, items.name, items.type FROM players
INNER JOIN items
ON players.id = items.owner_id
WHERE players.id = 12576 AND items.type = 'SWORD' AND items.equipped = 0 AND items.level > (SELECT items.level FROM players INNER JOIN items ON players.id = items.owner_id WHERE items.equipped = 1 AND items.type = 'SWORD')
The above probably won't work, and is simply to be used as an example, that you don't need 2 queries to figure it out, using a single query can get the job done, without the overhead of php trying to figure everything out for you, and save you the trouble of pulling loads of unneeded data from the DB.

Also, using mysql_fetch_array() is fine, but it creates 2 data sets, an associative array, and an indexed array, why not just use mysql_fetch_assoc() if you're going to use associative naming?

ROFL, because I never thought about it Everyone was using mysql_fetch_array so I was using it too (it's really funny no one on this forum pointed this out over these years). You are absolutely correct, using mysql_fetch_array() is stupid in more than 99% of cases.

REP +1

 

[Chris]

Question, why would you handle the comparisons between their levels and such with PHP, versus the SQL query?

Because PHP is incomparably faster than SQL. It is almost impossible to code something in PHP as unoptimized as to make it slower than additional SQL query.

I wouldn't be so quick to say PHP is incomparably faster than SQL. I can run some benchmarks, but not yet. From what I've read in this thread, I don't think you'll need an extra query to do what you're trying to do.

There was a topic about this on the forum. Various game owners were comparing their history of performance problems and the unquestionable conclusion was that all problems were always caused by MySQL (only codestryke managed to lag his server by PHP once, but he really went overboard and was young and unsmart back then so it can't really count ).

Code: [Select]

SELECT players.id, items.id, items.name, items.type FROM players
INNER JOIN items
ON players.id = items.owner_id
WHERE players.id = 12576 AND items.type = 'SWORD' AND items.equipped = 0 AND items.level > (SELECT items.level FROM players INNER JOIN items ON players.id = items.owner_id WHERE items.equipped = 1 AND items.type = 'SWORD')
The above probably won't work, and is simply to be used as an example, that you don't need 2 queries to figure it out, using a single query can get the job done, without the overhead of php trying to figure everything out for you, and save you the trouble of pulling loads of unneeded data from the DB.

Subquery and join counts as almost another query Also there are no items equipped. The whole function is to autoequip best items.

No, definitely a PHP side solution should be used for this

[codestryke]

There was a topic about this on the forum. Various game owners were comparing their history of performance problems and the unquestionable conclusion was that all problems were always caused by MySQL (only codestryke managed to lag his server by PHP once, but he really went overboard and was young and unsmart back then so it can't really count ).

I did this by having to many loops, which is basically what you are considering. I also showed in a previous how a query is indeed faster then PHP allocating memory for the array and then processing the array.

Joins are NOT like adding another query, if the join is indexed then the added time is trivial.

Anyways...

SELECT MAX(level) FROM items WHERE playerid = ? GROUP BY type
You have the best level for every type of group and that would be faster then PHP if indexed correctly

[Zeggy]

The kind of info you are trying to get just requires sorted data...

So you could either sort it in the query or sort it with php. Either way, once the data is sorted, you should be able to use $swords[0] for best sword, or sum $swords[0..4] for the total sum of the best 5 swords, etc..

[Chris]

There was a topic about this on the forum. Various game owners were comparing their history of performance problems and the unquestionable conclusion was that all problems were always caused by MySQL (only codestryke managed to lag his server by PHP once, but he really went overboard and was young and unsmart back then so it can't really count ).

I did this by having to many loops, which is basically what you are considering. I also showed in a previous how a query is indeed faster then PHP allocating memory for the array and then processing the array.

And I thought it was one of these rare times when we agreed on something

Joins are NOT like adding another query, if the join is indexed then the added time is trivial.

Well, maybe joins have some optimization, but even if perfectly indexed there are still 4 physical files to read (index of table 1, data of table 1, index of table 2, data of table 2). I simply don't believe it could be even comparable to simple sort in PHP (under eAccelerator and ZendOptimizer, so the algorithm is already cached and tokenized in memory).

One thing, this is for maximium 200 items returned from the query (in a pessimistic scenario, usually it would be like 30-50). So it is a small dataset.

SELECT MAX(level) FROM items WHERE playerid = ? GROUP BY type
You have the best level for every type of group and that would be faster then PHP if indexed correctly

GROUP BY!? Maybe I'm doing something wrong but it always results in filesort for me... I almost never use it.

So you could either sort it in the query or sort it with php.

Yes, I want the fastest PHP sort possible. That's my question

[Zeggy]

Wouldn't you just use the built-in php sorting methods? http://php.net/manual/en/array.sorting.php

[Chris]

Sorry, no sort, actually it is more about how to fill the initial sort array (and if to make one array for several kinds of items or separate for each kind of item). Also how to take into account the quantity variable (chop it and insert as separate entries to the sort array?)

Code: [Select]

$bestsword=$bestshield=0;
$dogs=array(); $falcons=array();
while($row=mysql_fetch_array(...))
{
if($row['type']==SWORD && $row['level']>$bestsword) $bestsword=$row['level'];
if($row['type']==SHIELD && $row['level']>$bestshield) $bestshield=$row['level'];
if($row['type']==DOG) // add it to $dogs array here ($row['level'] and $row['quantity'])
if($row['type']==FALCON) // add it to $falcons array here ($row['level'] and $row['quantity'])
}

$sumof5bestdogs=_SOME_SORT_FUNCTION($dogs)_
$sumof5bestfalcons=_SOME_SORT_FUNCTION($falcons)_

[CygnusX]

On thinking of this some more, I'd probably add the following to your query:

Order by Type Desc, Level Desc

This way, as you loop through the data you pulled, you could easily get the first 5 of each type.  

ie:

$MyArray = array();

while($Row = ...)
{

if(!empty($MyArray[$Row['type']]) && count($MyArray[$Row['type'])) < 5)
{
   $MyArray[$Row['type]] = $Row['info];
}

}

the !empty should keep the check from throwing an error

[codestryke]

I made a quick and dirty test to see how things would shake out. As I suspected the array method Chris is leaning towards is faster when you have a limited number of items per player (say 10 or less). As the number of items each player has grows (to 20 per player) then using a database group by gets faster. This makes sense as the array method has to loop though all the players inventory items, more items more looping and thus more time.

Code: [Select]

<?
$dblink = mysql_connect('127.0.0.1', 'root', '');
if( !$dblink )
   die('Could not connect: ' . mysql_error());

$db = mysql_select_db('test', $dblink);
if( !$db )
   die ('Can\'t use foo : ' . mysql_error());

//make();
//exit;
$num_tests = 1000;

$i = 0;
$time_start = microtime(true);
while( $i < $num_tests ) {
test_db();
++$i;
}
echo '<p>DB Execution time: ', (microtime(true) - $time_start), '</p>';


$i = 0;
$time_start = microtime(true);
while( $i < $num_tests ) {
test_array();
++$i;
}
echo '<p>Array Execution time: ', (microtime(true) - $time_start), '</p>';


function test_array() {
global $db;

$best = array();
$rs = mysql_query('SELECT level, typeid FROM inventory WHERE playerid = ' . mt_rand(1, 200));
while( $row = mysql_fetch_assoc($rs) ) {
if( $row['typeid'] == 1 && $row['level'] > $best['sword']) $best['sword'] = $row['level'];
if( $row['typeid'] == 2 && $row['level'] > $best['armor']) $best['armor'] = $row['level'];
if( $row['typeid'] == 3 && $row['level'] > $best['ring']) $best['ring'] = $row['level'];
if( $row['typeid'] == 4 && $row['level'] > $best['dog']) $best['dog'] = $row['level'];
if( $row['typeid'] == 5 && $row['level'] > $best['shoes']) $best['shoes'] = $row['level'];
}
}


function test_db() {
global $db;

$best = array();
$rs = mysql_query('SELECT MAX(level) FROM inventory WHERE playerid = '.mt_rand(1, 200).' GROUP BY typeid');
while( $row = mysql_fetch_assoc($rs) ) {
if( $row['typeid'] == 1 ) $best['sword'] = $row['level'];
if( $row['typeid'] == 2 ) $best['armor'] = $row['level'];
if( $row['typeid'] == 3 ) $best['ring'] = $row['level'];
if( $row['typeid'] == 4 ) $best['dog'] = $row['level'];
if( $row['typeid'] == 5 ) $best['shoes'] = $row['level'];
}


}


function make() {
global $db;

mysql_query('DELETE FROM inventory');

$num_players = 5000;
$num_levels = 20;
$items = array(1 => 'sword', 'armor', 'ring', 'dog', 'shoes');

for($i = 1; $i < $num_players+1; $i++ ) {
for($j = 1; $j < count($items)+1; $j++ ) {
for($k = 1; $k < $num_levels+1; $k++ ) {
mysql_query('INSERT INTO inventory (playerid, typeid, name, level) VALUES ('.$i.', '.$j.', "'.$items[$j].' '.$k.'", '.$k.')');
}
}
}
}

?>

If you decide to play with the code remember to turn off query caching to get accurate test results.

Edit, here is the table structure...

Code: [Select]

CREATE TABLE IF NOT EXISTS `inventory` (
  `playerid` int(10) unsigned NOT NULL,
  `typeid` int(10) unsigned NOT NULL,
  `name` char(10) NOT NULL,
  `level` tinyint(3) unsigned NOT NULL,
  KEY `playerid` (`playerid`)
) ENGINE=MyISAM;


[Chris]

Interesting use of GROUP BY. Not only it reduces the loop inside PHP but also data transfer volume from MySQL daemon...

One thing that bothers me about this benchmark. It calculates CPU, while in real environment the bootleneck might be IO (which might also explain why we all have all server issues triggered always by MySQL never by PHP). So, the big question, will GROUP BY trigger the dreadful filesort or not?