Digg: 40x Performance Increase by Sorting in PHP Rather than MySQL
highscalability.com
highscalability.com
The problem was that even though I denormalized my "posts" (from RSS feeds) table into a "post contents" and a "post metadata" table, MySQL wants to create a "temporary table" to do sorting and pulls every relevant row into it (I found this was even true with indexed columns at the time - I hope they improved it). This can lead to heavy disk access if the number of rows needing to be sorted is too high (consider 100,000 rows of 150 bytes each.. 15 megabytes, not good for a server under heavy load that needs to return a query in < 0.2 seconds).
My solution was to pull out ONLY the post IDs and date (or whatever column I wanted to sort by) from MySQL, do the sort in memory, then pull out the posts from the database by already ordered IDs (e.g. SELECT * FROM x WHERE id IN(9,4,22,38,4,..)). MySQL is crazy fast at giving you back rows X, Y, Z, and so on, if you specify them directly.
I ended up with many more fast queries rather than fewer deathly slow queries, and that was a great tradeoff in the end. I believe the system still runs that way under its new owner.
Update: I just realized I have the code in an archive here so I loaded it up. I can't believe this wasn't obvious to me! Since we already had the ordered IDs in memory (to build the SELECT query!) we loaded the posts with a SELECT .. IN into a hash (with the id as the key) then just went through the ordered ID list and pulled out the posts from the hash in the right order! :-)
Just get your data directly with a search, then array sort the hash using the hash key.
If I have a table with 10m rows (it was about that) and I want 10 posts from feeds X, Y and Z in reverse date order, to get them in just one query with local sorting I'd have to retrieve every row for feed X, Y and Z down the wire before doing the local date sort.
If I did the sorting with ORDER BY to avoid that issue, the complete JOIN (meta<->full) is used in the temporary sort table so, a bigass temporary table would result for MySQL to do its sorting.. bringing us back to square one :-)
Hopefully I'm not misunderstanding your point though.. it's been known to happen.
BTW, you were doing this to avoid using too much memory at the database, but by doing this (assuming it's PHP; you didn't say) you are loading the result set twice into webserver memory.
Obviously it worked for you, maybe the webserver had more free memory.
But I use FIELD() http://dev.mysql.com/doc/refman/5.0/en/string-functions.html...
SELECT FROM x WHERE id IN(9,4,22,38,4,..) ORDER BY FIELD(`id`, 9,4,22,38,4,..)
That said, I dont know if sql or php is quicker.
For example if your index is (username, date_posted) then you can do something like
SELECT * FROM table WHERE username='user' ORDER BY date_posted
SELECT * FROM table WHERE username IN ('user','user2') ORDER BY date_postedYou could change your index to (date_posted, username) to make it work, but then it will be slow when querying a small percent of the users.
2) Moving stuff from your database server to your webserver is actually changing the hardware environment it runs on. Especially relevant if your database server isn't keeping up or is RAM constrained or whatever else is different.
"The relational database tool chain is not evolving. It has failed for large scale, real-time environments."
I've been a big user of Postgres for going on five years now and it has made giant leaps in both features and performance. You can't blindly say relational tools are done evolving. I know the other players have made a lot of progress lately too (Oracle, MySQL, etc).
Same for MySQL, modulo (possibly) the Drizzle project.
Oracle has a lot of different irons in the fire, but "cheap scaling" isn't one of them. (If you've got the money to burn... TimesTen?)
That's not a knock on any of the above, it's just a different use case.
Neither are useful for the Digg usecase. Edit: That is to say, they're optimized for large datasets, low concurrency, medium latency, medium-to-high consistency and medium-to-low availability.
You can mirror the DB and configure it to do off-line analysis, or use something more suitable, but if it doesn't need to be transactional (and really, the top 10 comments your friends just made don't need to be transactional) then use a more suitable tool with less strict behavior.
I was running a internal webapp with a 25M rows in a MySQL table. The query for search was something like (pseudosql ahead):
select * from table where match title_field against search_term order by id desc limit 20
select * from table where match title_field against search_term
I'd suggest using "EXPLAIN EXTENDED" before your "SELECT" to see what it's doing and to consider specifying the columns, though in general I'd do what you did.
What it probably did was sort by id (in memory), and then run the search (i.e. check each row if it matched, and stopping after 20 rows), not realizing that it should do the search first, and only then sort.
EXPLAIN .... is your friend here.
Without the order by, the only possible index was the search, so it used that.
And digg probably had a similar error, since it makes no sense for php to be any faster in sorting than mysql.
Perhaps MySQL has improved lately but working on my working knowledge of about 3 years ago, it can make sense to do sorting externally... if you can work with fewer data to do the sorting externally ;-)
MySQL does/used to pull entire rows into the temporary table created for sorting. So if you have a 10,000 row, 100MB table and you're doing a SELECT that grabs, say, 10% (1000) of the rows and sorts them.. MySQL's temporary sort table will be 10MB (I found this to be true regardless of indexes - which only sped up the creation of the temporary table, but did not reduce its size - but as I was doing complex multi column sorts, it didn't matter anyway).
If you do it in PHP/wherever, you can pull out ONLY the "id" and the column you want to sort by (say, a date), and use only about 1000 * 10 bytesish == 10KB of data to do the id sort. Then you pull the full rows out by id (which MySQL is quick at).
Disclaimer: I last did all this about 3 years ago on an early version MySQL 5 deployment doing about 200 queries a second. So I ain't no RDBMS expert and what I say should probably be taken with a pinch of salt.
As long as your sort table stays in memory you are fine even if it's a lot of data, but if you hit the disk then you could be right. (But even if mysql says it hits the disk, doesn't mean it really does since the OS could cache it.)
But there are better ways of handling this. Number one being an index on that column.
You could also split the table in two, one part for sort data, the other for the large data. But I would only recommend that in very special cases, and only after careful benchmarking.
Most of the time just increase the maximum size of in-memory temporary tables.
Not with a SELECT .. WHERE id IN (x,x,x,...) type query. But, yeah, sort of. I actually did trial with separate SELECTs for every ID at first and it performed surprisingly well.
As long as your sort table stays in memory you are fine even if it's a lot of data
Trueish. At the time, though, it was a 10-12GB database on a 4GB machine and in 2006 I didn't have the cashflow to get anything better. So the most popular parts of the DB were cached OK, but there was little left for temporary tables. I say "trueish", though, because you're still using more memory bandwidth with temporary tables in this situation and that's an issue sometimes.
Number one being an index on that column.
The problem was that there were about 8 metadata columns and sorts were done with varying combinations of these (though usually one). Indexes became a big problem at a certain point because of how difficult they made it to clear stale data from the database (at one point we were doing 6 hour maintenance periods each month - with caches picking up the slack - to delete old records).
If I were doing it again, I'd do a lot differently (and not use MySQL), of course.. so your suggestions are certainly useful to anyone tackling a similar problem with 2010 eyes.
The statement here isn't that a sort in php is 4000% faster than a sort in mysql, all things equal.
What is left out of the discussion is the fact that all things are likely not equal, their database servers are way more resource constrained / under heavier load than the web servers. Thus, a CPU-bound operation like sorting will perform better if you can move the operation to a server that has more of the resource in question available.
"Digg is doomed unless they fire their tech staff." - http://plentyoffish.wordpress.com/2006/10/08/digg-is-doomed-...
When will people learn that the 'relation' in relational database comes from the correspondence between database tables and the mathematical notion of relations, not the ability to describe relationships between tables? Unless scaling practices make a relational database stop using tables, the database still being used as a relational database.
I sure hope that's not always the way it goes. Because then "then" would soon mean "than" and "than" would mean "then".
"right tool for the job", etc.
You can't have consistency. You can't query and view your data the way you want to. Only prearranged queries are allowed.
It's all very well to do that, but it's not a better solution to the original problem. It's acknowledging that the original problem is unsolvable or put differently, it's giving up.
Scalability, for me, is making the things scale that I want to do, not doing something that scales.
Sometimes it seems to me that we're heading straight back to the mainframe era where everything that wasn't prearranged, didn't fit the nightly batch window or was otherwise unexpected simply couldn't be done.
The answer to static precomputed reports and highly specialised, highly inflexible data structures were relational database systems and Excel.
So, were relational databases and spreadsheets really the answer, or just an alternative?
Hard coded access paths and data structures combined with explicit and selective consistency management is always faster and more scalable provided the number of different use cases is small and requirements don't change much. Doing a small number of things on a huge scale justifies the approach that people like twitter are taking.
Unfortunately what scales physically doesn't scale in terms of logical complexity. As soon as a greater variety of tasks, views and analyses have to be supported, productivity plummets and things come to a screeching halt. That's exactly what happened to corporate IT departments back then. Everything took ages to implement because you couldn't just join over or group by some unexpected set of attributes.
As a reaction to that, two things happened. For one, people tried to free their data from the iron grip of centralised IT departments and put it on PCs and into spread sheets that used very generic data structures to support a very large variety of views and analyses. Nothing had to be predetermined. Of course that also led to utter chaos in terms of consistency and it didn't scale to large amounts of data.
The other idea to cope with hard coded information was to separate the logical representation of information from pysical representations and access paths. Relational normalisation doesn't just guarantee consistency, much more importantly it guarantees the productivity of creating a wide variety of views on data. A separate and independent layer contains all the special casing and optimisations for frequent use cases.
I think the idea of modelling information according to a general, formally well defined logic and separating that model from implementation constraints is a timeless one. It's not just "an alternative". It's a fundamental principle of dealing with information and it's not specific to the relational model. I've been doing this for long enough to know that this kind of purity is hard to achieve and has to be comprimised now and then.
Throwing out good design principles is sometimes necessary. I can see why it is necessary for Google, Amazon or Facebook. But it is going to make these behemoths slower and less flexible. It's a price they pay for their size. It makes no sense for small companies to pay that price whilst not benefiting from the same economies of scale.
What the article doesn't mention is, was that the highest measured performance increment, or was it the mean or median or most common? Also, what was the margin of error in that reading?
Any database system goes far beyond giving you a set of interfaces to manage collections, lists, etc. This typically includes support for ACID (atomic, consistent, isolated and durable) transactions, multi-user access, a high level data definition language, one or more programming interfaces (including industry-standard SQL), triggers/event notifications, and more.
I also was playing with Redis and redis-py, but Python is too slow for me. So now at this very moment I'm playing with Memcached and its C API.
Redis and MongoDB look very promising but not reliable yet.
No critical bug found in 1.0 and 1.2 since their release apart for a replication bug happening in corner case conditions.
Please share with us how Redis is not reliable and I'll try to fix this ASAP.