Database Optimisation Help Please

N

Nicko

Expert Member
Joined
Feb 16, 2010
Messages
1,048
Reaction score
1
Location
Cape Town
I'm working on a opensource game, aim to connect it to an online database. I have basically finished the thing, just working on the optimisation side of it and have one issue. One of my biggest computation functions is working out players rankings. This is my structure and function at present. The main table with all the players map times is the records table.

Records
-------
MapID
PlayerID
Time

Each map is associated with a difficulty for the map and gives a certain amount of points for completing it, which is represented by the DifficultyToPoints table (The Maps table has a difficulty column):

DifficultyToPoints
---------------
Difficulty
Points

This is where I have a problem. Right now I am only giving people points (and then ranking them) according to which maps they have completed and the difficulty of these maps. But now I want to also give people points for their ranking within each individual map. E.G if you ranked first in map X then you get Y points for being first and Z for finishing it. I have a slight idea how I would go about it, but I feel that there is surely a far more efficient method out there.

Here are my current functions WITHOUT the additional points for map rank (MySQL):
FUNCTION GetPlayerPoints (Player INT) RETURNS INT (11)

DECLARE TempPoints INT;
TempPoints = 0;
Select SUM(DifficultyToPoints.Points) AS Points INTO TempPoints From DifficultyToPoints, Records, Maps WHERE Records.Map_ID = Maps.MapID AND CAST(Maps.Difficulty AS SIGNED INT) = DifficultyToPoints.Level AND Records.Player_ID = Player GROUP BY Records.Map_ID;
//Gets and sums up the points associated with the map's difficulty for every record a player has... I just added GROUP BY Records.Map_ID now because I realized that people would be getting multiple points for completing the same map. It could be wrong.

RETURN TempPoints ;

FUNCTION `GetRank`(Player INT) RETURNS INT (11)
DECLARE `TempRank` INT;
CREATE TEMPORARY TABLE TempPoints (
Points INT ,
Player_ID INT
);
//Creates a temp table for all the points of the players to be inserted into

INSERT INTO TempPoints
SELECT GetPlayerPoints (AccID),
AccID
FROM Players;

SET @rownum := 0;
SELECT rank INTO `TempRank` FROM (
SELECT @rownum := @rownum + 1 AS rank, Points, Player_ID
FROM TempPoints ORDER BY Points DESC
) as result WHERE Player_ID=Player;
//Ranks it
RETURN `TempRank` ;
Click to expand...

I APOLOGISE for the wall of text, but a lot of it is quite straight forward code. To summarise my two issues is one the efficiency of the function (any suggestions to improve it?), and the second is adding points for map ranking.

This is my first time working on websites so all of this is quite new to me so I would appreciate any help. Thanks :)
 
Last edited:
First off, why do you feel you need to calculate the points each time?

I know there's a "rule", "Don't save what you can calculate", but that's usually to do with VAT in my experience (why would I want to save R14.50 as the VAT value if I can just calculate amount * 0.14)

This will really impact on performance JUST on ranking when players start looking up stuff.

I'm also not 100% sure of your database structure, so by guessing and thumb sucking and your explanation, I'd assume something like this:

Maps
-----
MapID
MapName
Difficulty

Player
------
PlayerID
PlayerName

Records(for saving if a player completed a map)
-------
MapID
PlayerID
TimeCompleted

This is where I'm not 100% sure of things, RecordsToPoints you have Difficulty and points. Now I *assume* there must be another table somewhere:

Difficulty
---------
DifficultyID
DifficultyName (Easy/Medium/Hard)
Difficulty

But if there were, you would have mentioned it :)

So your RecordsToPoints would look like this:

DifficultyID
Points

But that's a bit redundant IMO since we have the Difficulty table now, which can contain the record Points.... right?

But wait, you might not want to assign the same points for the same difficulty on the same map, because a Medium difficulty map might differ in points based on the map itself, so you'd have an intersection table

MapDifficultyPoints
----------------
MapID
DifficultyID
Points


Right, that sorts out some of my concerns re: what you already have there (because it makes it easier to query what the player scored:

(pseudo code, not tested) select sum(points) as TotalPoints,PlayerName,MapName from playertable inner join Records on Records.playerID = playertable.playerID inner join MapDifficultyPoints on MapDifficultyPoints.MapID = Records.MapID group by MapName,PlayerName
order by sum(points)

see, no temp table!)

I assume also a player can't go back and re-complete a completed map. Working under that assumption, it's safe to use the above pseudo query to save a history of the player's progression into a separate table for only that one record (instead of selecting all the maps he completed all the time)

PlayerHistoryTable
------------------
PlayerID
MapID
DifficultyID
PointsEarned (this is a separate column that's not associated with Points in the other table, because if you choose to change the points earned, you don't want to necessarily update the history table as well)

Then from there it's a simple (pseudo) query: select sum(PointsEarned) as Points, PlayerName from PlayerHistoryTable inner join playertable on playertable.PlayerID = PlayerHistoryTable.PlayerID order by sum(PointsEarned)

To get the score for the entire database and ranking them.... no temp table ;)

I know I know, I haven't even TOUCHED on the issue you want solved, and that's by giving them points on the ranking (but hopefully you'll see my logic in a few moments, or already have!)

Next thing (your concern) is to add points to people who are ranked as completing the map first/2nd/3rd whatever:

MapRankPoints
--------------
MapID
DifficultyID
RankID (I'm not including this table for you, it's just a description "Rank 1, Rank 2 etc")
Points

Right... see? So now we have the history table containing all of the player completed points, we can just use more or less the same query to show overall ranking, add mapid/difficultyid to it and group it by the other fields and inner join this table and have another calculated column go: (sum(PointsEarned)+RankPoints.Points) as TotalPoints

Okay, so I might not have gotten it 100% right, and I'm sure I'm missing several things here, but even vbulletin (this forum) keeps a physical table with search queries for speed. Temp tables are really REALLY bad for high volume stuff (depending on how you use it)

The next step you should take is look at indexing on your tables/columns for optimization etc

Okay, it's time for me to wake up now. GOOD LUCK
 
Okay here it goes.

The reason I had for the DifficultyToPoints (not suppose to be RecordsToPoints, was a typo) table was so that I could just change that one value if I wanted to award more/less points for completing easy/medium/hard etc maps. I would also prefer to award the same points for each difficulty. So for the first part, taking your suggestion into account, would this work.

Difficulty
---------
DifficultyID
DifficultyName (Easy/Medium/Hard)
Difficulty
Points

MapDifficultyPoints (Some maps don't have a difficulty associated with them, should I keep this or just make a difficulty column in the Maps table and assign it NULL if there is no difficulty for the map.)
----------------
MapID
DifficultyID

select sum(Difficulty.points) as TotalPoints,PlayerName,MapName from playertable inner join Records on Records.playerID = playertable.playerID inner join MapDifficultyPoints on MapDifficultyPoints.MapID = Records.MapID inner join Difficulty on Difficulty.DifficultyID = MapDifficultyPoints.DifficultyID group by MapName,PlayerName
order by sum(Difficulty.points)

Here is where I got a few questions. Wouldn't this give a person points for completing the same map multiple times?

I know you talk about it here, but I'm not entirely sure what you mean.
I assume also a player can't go back and re-complete a completed map. Working under that assumption, it's safe to use the above pseudo query to save a history of the player's progression into a separate table for only that one record (instead of selecting all the maps he completed all the time)

PlayerHistoryTable
------------------
PlayerID
MapID
DifficultyID
PointsEarned (this is a separate column that's not associated with Points in the other table, because if you choose to change the points earned, you don't want to necessarily update the history table as well) I see the advantage of this, but I would rather have everything updated
Click to expand...

Are you saying that when someone completes a map, I enter the record into the records table, but I also enter the record into the history table IF they haven't already gotten a record for that map. Basically making it a PlayerMapCompletion table. If this isn't what you mean, I don't really know how else it would work. But hey I am still discovering hidden functionalities of SQL every day :)

Once again if I assumed correctly then this PlayerMapCompletion table would be perfect as it would give me exactly what I am looking for in terms of totalling the players points. (But then I don't know what the purpose of the first statement, unless you were just showing me what I could do with it).

The ranking thing I just cant seem to understand. How does it work out peoples rank? Especially seeing as MapRankPoints doesn't have a PlayerID. I will spend some more time looking at it later, maybe then it will come to me, but I actually gotta pop out for a bit now :)

Thanks again for the help, I hope that I'm not querying things that should be obvious.
 
This answer won't be as long as my previous one. You assume right, it's sort of a history table, it's a player progression table in other words. You will only save points there when maps are completed. The MapID/DifficultyID thing is good, because then you only have 1 table storing difficulty which means it's easier to query down the line.

The SQL statement I gave won't give them multiple points for the same map because of the "Group By" on the mapname (if it's unique, if not, use MapID)

Play around with it. Temp tables are evil, especially if you consider scaling things up to thousands, if not millions, of players checking their scores and where they rank in the game compared to others.
 
Some good info the the replys, but I simply have to comment on the VAT storage vs calculation. I assume when you say you wouldn't store the vat value, just calculate using 14%, that you would indeed store 14% as the vat rate for that line item?

If not, you will be completely screwed when they decide to make vat 14.5% or support multi currency
 
Last edited:
I have not read everything as I am about to crash now (like early nights on Sun).
Excuse me if I am off base here.

Avoid functions, cursors and temp tables/table variables if you can.
I try to use common take expressions (CTE) first and only resort to the other types of no other choice. CTE's are very efficient and more readable. Plus they are updateable.
Just make sure to build indexes on your join fields (if any) and filters.

For monetary values, I always store the Value Ex plus the VAT rate with every transaction. If the currency rate is changed later it won't affect your history (and it shouldn't).

EDIT: just noticed you are using MySQL. Apologies as I was responding from a SQL Server context. Not sure if MySQL supports CTE's.
 
Last edited:
_kabal_ said:
Some good info the the replys, but I simply have to comment on the VAT storage vs calculation. I assume when you say you wouldn't store the vat value, just calculate using 14%, that you would indeed store 14% as the vat rate for that line item?

If not, you will be completely screwed when they decide to make vat 14.5% or support multi currency
Click to expand...

lol yea, I store the vat percentage because if vat changed you don't want history data to change as well
 
Sorry for the super delayed replay. Its just been a very very hectic week, havent had a moment to spare.

Mike Smit said:
I have not read everything as I am about to crash now (like early nights on Sun).
Excuse me if I am off base here.

Avoid functions, cursors and temp tables/table variables if you can.
*snip*
Click to expand...
Thanks for the pointers! Didn't realize I needed to avoid functions, and was actually doing the complete opposite. Will edit out all my functions later.

_kabal_ said:
oracle has a rank() function that you can use to achieve some of what you might need, ie top N ranked for map, your map rank, etc

you can achieve similar behaviour in mysql: http://stackoverflow.com/questions/3333665/mysql-rank-function
Click to expand...

I wish it was that easy =/. The actual ranking wasn't the problem. The issue was generating a table of points to be ranked. Especially as the ranking was a two fold problem, needed to get points from their map completions and their rankings within that map.

AcidRaZor said:
This answer won't be as long as my previous one. You assume right, it's sort of a history table, it's a player progression table in other words. You will only save points there when maps are completed. The MapID/DifficultyID thing is good, because then you only have 1 table storing difficulty which means it's easier to query down the line.

The SQL statement I gave won't give them multiple points for the same map because of the "Group By" on the mapname (if it's unique, if not, use MapID)

Play around with it. Temp tables are evil, especially if you consider scaling things up to thousands, if not millions, of players checking their scores and where they rank in the game compared to others.
Click to expand...

Haha I don't think it will be in the millions of players, but I can always hope :D I have taken your suggestions into account and made some changes. I know this probably isn't exactly what you had in mind, but I think it will work.

The Tables:
Maps
----
MapID
MapName
DifficultyID

Difficulty
---------
DifficultyID
DifficultyName
DifficultyNum
Points_Awarded

Players
-----
PlayerID
PlayerName

Records
-------
PlayerID
MapID
Time

PlayerBestTime
-------------
PlayerID
MapID
BestTime
Points
Click to expand...

So what will happen is that when someone completes a map, it gets inserted into records
but only if it beast their time will it be then inserted into MapCompletion only if it beats their best time with the corresponding points for the map.

Insert Query:
INSERT INTO PlayerBestTime (PlayerID, MapID, BestTime, Points) VALUES (PlayerID, Map_ID, Time, GetPointsFromDifficulty (MapID)) ON DUPLICATE UPDATE MapCompletion SET BestTime=Time WHERE PlayerID = Player_ID AND MapID = Map_ID AND BestTime > Time
Click to expand...

Now to get the points from the maps completed, will be as simple as this.

Select PlayerID, sum(Points) as TotalPoints FROM PlayerBestTime GROUP BY PlayerName ORDER BY TotalPoints
Click to expand...

Now to expand on that and include the points from the map rankings:
SELECT PlayerID, SUM (Points) AS Total_Points
FROM(
SELECT PlayerID, GetPointsFromRank (rank) AS Points
FROM Maps AS parent,
(SELECT PlayerID, @curRank := @curRank + 1 AS rank
FROM PlayerBestTime temp, (SELECT @curRank := 0) r
WHERE parent.MapID = temp.MapID
ORDER BY BestTime
LIMIT 0,10) AS RankTable
UNION ALL
SELECT PlayerID, sum(Points) as Points FROM PlayerBestTime GROUP BY PlayerID
) TotalPointsTable
GROUP BY PlayerID
Click to expand...

So that would be a table for the total points, in order to get the global rankings for the players would just be another ranking select.

SELECT PlayerID, @curRank := @curRank + 1 AS rank
FROM (
SELECT PlayerID, SUM (Points) AS Total_Points
FROM(
SELECT PlayerID, GetPointsFromRank (rank) AS Points
FROM Maps AS parent,
(SELECT PlayerID, @curRank := @curRank + 1 AS rank
FROM PlayerBestTime temp, (SELECT @curRank := 0) r
WHERE parent.MapID = temp.MapID
ORDER BY BestTime
LIMIT 0,10) AS RankTable
UNION ALL
SELECT PlayerID, sum(Points) as Points FROM PlayerBestTime GROUP BY PlayerID
) TotalPointsTable
GROUP BY PlayerID) AS PointsTable, , (SELECT @curRank := 0) r
ORDER BY Total_Points
Click to expand...

EDIT: Just realized that my core query in the total points query is broken. I meant to iterate through the maps to get their top players, but I forgot about doing that. Will fix it tomorrow.

EDIT: Fixed the problem. I'm 80% sure this new version will work, unless someone can find fault in my logic. I will be able to confirm, if it works, a bit later.
 
Last edited:
You must log in or register to reply here.
Back
Top
Sign up to the MyBroadband newsletter
X