Algorithms and computational complexity is the key thing to understanding why your program or DB query has so poor performance - meaning, why it so slow. Unfortunately, many computer science students hate algorithm analysis courses where the principles of computational complexity is taught. They seem to miss the point that algorithm analysis is a stairway to better programming, and is a necessary skill for DB query optimization, Data Science and Big Data analysis.
Latest workshop focused on MySQL and ArangoDB as an example engines. Participants had to learn some queries on premade SQL database, then export all data to ArangoDB, and build similar queries. This gave everybody an opportunity to compare SQL and NoSQL query styles, their performance and principles of computational complexities with query optimization.
During the workshop there was some really interesting progress on queries, which shows nicely what computational complexity is, actually.
Familiar country - SQL
After familiarizing themselves with current database the participants had several tasks where they had to write queries to collect certain types of data sets. One simple task was to find out top scoring players with player name included. Player data was in its own table, and scores were recorded in their own table including game type and other game information.One early version of necessary query was made like this by a participant
Query A.
SELECT u.playername, h.gamescoreFROM (SELECT playerid, MAX(gamescore) as highscore
FROM scoretable
WHERE gametype = 'CTF'
GROUP BY playerid) x
JOIN
scoretable h ON x.playerid = h.playerid AND x.highscore = h.gamescore
JOIN
player u ON h.playerid = u.playerid
ORDER BY h.score DESC LIMIT 10
Participants were quite satisfied with it, since its running time seemed quite fast. It was 76 ms, to be exact. But I had to point out, that it is possible to make it faster. You can easily see, that Query A is doing unnecessary work since the query joins maximum scores for each and every player with player data, and after that sorts them in descending order picking out 10 of the best.
This means that query first groups gamescores and picks maximum value for each scoring player (N), then joins this with playerdata (M) and sorts the joined table. But we are only interested in 10 best scoring players so it is better to sort those score immediately and after that join only those best 10 players with player data table, like this
Query B.
SELECT u.playername, x.highscoreFROM (SELECT playerid, MAX(score) as highscore
FROM scoretable
WHERE gametype = 'CTF'
GROUP BY playerid
ORDER BY highscore DESC
LIMIT 10) x
JOIN
player u ON x.playerid = u.playerid
and also get rid of that unnecessary join in original query. Running time is actually halved to 35 ms. Joins cost in performance, and now we are joining only the 10 best players, not all scoring players.
Hostile territory - NoSQL
When SQL tasks were completed, whole database was exported into ArangoDB. This was very simple task, since you can export MySQL database in JSON format which is really easy to import into ArangoDB.
After the import participants had to recreate the same queries as before, but now with ArangoDB query language AQL. Participants had only few problems with AQL. It has some similarity with SQL which makes it easier to "jump into" for anyone familiar with SQL - compared to Javascript style queries. But there were enough differences also which lead to many mistakes.
Biggest difference seemed to be the process order, but when participants finally understood that AQL is like mix of procedural SQL and basic SQL, they started to grasp the skill of building AQL queries. Their first try on '10 best players' query was far from efficient, however.
Query C.
FOR d IN playersLET hscores = (
FOR s IN scoretable
FILTER s.playerid == d.idplayer
FILTER s.gametype == 'CTF'
LET numscore = TO_NUMBER(s.score)
COLLECT pid = s.playerid INTO scores
RETURN {'hscore': MAX(scores[*].numscore)}
)
SORT hscores[0].hscore DESC
LIMIT 0,10
RETURN {'player': d.playername, 'score': hscores[0].hscore}
This query works and gives correct result, but it has a disastrous performance of 26 seconds (26000 ms), which is unacceptable. After I guided players to analyse its computational complexity, they soon understood why it was so. You are going through every player in database, then every time go through score data to calculate his maximum score (even if he has no scores at all), then sort them and pick the 10 highest scoring players.
The real problem is the sort operation, however. Sort is done in such phase, that query optimizer cannot optimize it. Actually, SORT is a bit of a bottleneck in ArangoDB. But in this case there is also a lot of unnecessary calculations. Problem was that participants tried to join player data and player scores and collect the result simultaneously, like they did in SQL.
In AQL you can operate procedurally step-by-step. I guided participants to collect first just 10 best scoring player ids, and then join that with player names, leading to this query
Query D.
LET leader = (FOR s IN scoretableFILTER s.gametype == 'CTF'
LET numscore = TO_NUMBER(s.score)
COLLECT pid = TO_NUMBER(s.playerid) INTO scoresbypid
LET hscore = MAX(scoresbypid[*].numscore)
SORT hscore DESC
LIMIT 0,10
RETURN {'pid': pid, 'score':hscore}
)
FOR l IN leader
FOR d IN devices
FILTER d.idplayer == l.pid
RETURN {'pid': d.playername, 'score': l.score}
Participants were astonished, when running time dropped to 132 ms. This performance is good but not the best. Only difference was that first we operated only on scoredata, grouped them by player id, calculated the maximum and then sorted it picking the 10 best. After that, this data with only 10 objects was joined with player names.
Even in this case the sort operation is a bottleneck, but less so than in previous case. To conclude the session, I presented final modification to Query D in order to optimize it even more.
Query E.
LET leader = (FOR s IN scoretableFILTER s.gametype == 'CTF'
SORT s.score DESC
LIMIT 400
LET numscore = TO_NUMBER(s.score)
COLLECT pid = TO_NUMBER(s.playerid) INTO scoresbypid
LET hscore = MAX(scoresbypid[*].numscore)
SORT hscore DESC
LIMIT 0,10
RETURN {'pid': pid, 'score':hscore}
)
FOR l IN leader
FOR d IN devices
FILTER d.idplayer == l.pid
RETURN {'pid': d.playername, 'score': l.score}
Only difference is the sort operation before grouping. This may sound like a stupid idea, because we already know that sort is a bottleneck. However, it performs quite fast on original data. Since we are looking for 10 best scoring players, we are not interested in low scores at all. In this case, no player had more than 200 scores recorded. So, I just sorted quickly all scores and took only 400 best scores to subsequent calculations. Running time of this query dropped to 33 ms, which was even better than best MySQL query on fully optimized database.
Aftermath
Participants found it interesting how fast a SQL database is when it is properly indexed and uses foreign keys, so it can optimize queries. So you should not think that RDBMs and SQL are obsolete old technology. They are still very competent at what they do, if you know how to tune them.
It was also interesting how easy it is to do sloppy queries in NoSQL, and how you actually have to plan queries. On the other hand, in this case ArangoDB's AQL gives you lots of option to filter out the data you need.
