Thursday, March 3. 2011
Why go with O(n) if you can have O(n²)?
Found this while waiting for the CSV export of a search result from (*undisclosed project*) ...
The export took almost half an hour even though it was just extracting the snail mail addresses of about 40K contacts, so what caused it to only spit out about 20 rows per second? Looking at the PROCESSLIST output a pattern was easy to detect. What greeted me was a single running query which had only been running for a few seconds even though i was already waiting for export results for about 20 minutes:
SELECT ... LIMIT 32900, 100;
And then a few seconds later:
SELECT ... LIMIT 33000, 100;
So instead of retrieving the search results for export by firing a single query and processing the results in one go the same pagination logic seemed to be used as for displaying search results. About 400 queries instead of a single one, and each iteration taking more query time, with finally the last one taking about the same time as the only query in the all-at-once alone.
Somewhere, somehow, something terribly went wrong it seems ....
Could this bennefit from using the HANDLER statement?
mysql> SELECT * FROM test001;
+----+---------+
| id | name |
+----+---------+
| 1 | test 01 |
| 2 | test 02 |
| 3 | test 03 |
| 4 | test 04 |
| 5 | test 04 |
| 6 | test 05 |
| 7 | test 06 |
+----+---------+
7 rows in set (0.00 sec)
mysql> HANDLER test001 OPEN;
Query OK, 0 rows affected (0.00 sec)
mysql> HANDLER test001 READ `id` NEXT LIMIT 2;
+----+---------+
| id | name |
+----+---------+
| 1 | test 01 |
| 2 | test 02 |
+----+---------+
2 rows in set (0.00 sec)
mysql> HANDLER test001 READ `id` NEXT LIMIT 2;
+----+---------+
| id | name |
+----+---------+
| 3 | test 03 |
| 4 | test 04 |
+----+---------+
2 rows in set (0.00 sec)
mysql> HANDLER test001 CLOSE;
Query OK, 0 rows affected (0.00 sec)
mysql> SELECT * FROM test001;
+----+---------+
| id | name |
+----+---------+
| 1 | test 01 |
| 2 | test 02 |
| 3 | test 03 |
| 4 | test 04 |
| 5 | test 04 |
| 6 | test 05 |
| 7 | test 06 |
+----+---------+
7 rows in set (0.00 sec)
mysql> HANDLER test001 OPEN;
Query OK, 0 rows affected (0.00 sec)
mysql> HANDLER test001 READ `id` NEXT LIMIT 2;
+----+---------+
| id | name |
+----+---------+
| 1 | test 01 |
| 2 | test 02 |
+----+---------+
2 rows in set (0.00 sec)
mysql> HANDLER test001 READ `id` NEXT LIMIT 2;
+----+---------+
| id | name |
+----+---------+
| 3 | test 03 |
| 4 | test 04 |
+----+---------+
2 rows in set (0.00 sec)
mysql> HANDLER test001 CLOSE;
Query OK, 0 rows affected (0.00 sec)
Status after HANDLER use:
mysql> SHOW STATUS LIKE 'Handler%';
+----------------------------+-------+
| Variable_name | Value |
+----------------------------+-------+
| Handler_commit | 2 |
| Handler_delete | 0 |
| Handler_discover | 0 |
| Handler_prepare | 0 |
| Handler_read_first | 1 |
| Handler_read_key | 2 |
| Handler_read_last | 0 |
| Handler_read_next | 3 |
| Handler_read_prev | 0 |
| Handler_read_rnd | 0 |
| Handler_read_rnd_next | 0 |
| Handler_rollback | 0 |
| Handler_savepoint | 0 |
| Handler_savepoint_rollback | 0 |
| Handler_update | 0 |
| Handler_write | 0 |
+----------------------------+-------+
16 rows in set (0.00 sec)
Status after select with limit (same rows read):
mysql> SHOW STATUS LIKE 'Handler%';
+----------------------------+-------+
| Variable_name | Value |
+----------------------------+-------+
| Handler_commit | 2 |
| Handler_delete | 0 |
| Handler_discover | 0 |
| Handler_prepare | 0 |
| Handler_read_first | 2 |
| Handler_read_key | 4 |
| Handler_read_last | 0 |
| Handler_read_next | 0 |
| Handler_read_prev | 0 |
| Handler_read_rnd | 0 |
| Handler_read_rnd_next | 6 |
| Handler_rollback | 0 |
| Handler_savepoint | 0 |
| Handler_savepoint_rollback | 0 |
| Handler_update | 0 |
| Handler_write | 0 |
+----------------------------+-------+
16 rows in set (0.00 sec)
No, as the query is spanning several tables (person, address, country, ...)
Thought I'd share a bit since I've done this sort of thing myself. I don't believe you're giving the tradeoffs the proper attention in this case.
One being that if you are dealing with a large amount of rows and columns, memory consumption is a major barrier you start running into right away. Mix in how easy it is to introduce memory leaks with php's object model, and you have a recipe for disaster. I've found that people are much more tolerant if they have to wait a bit longer for something than not getting it at all (because you're script died from out of memory). If you use the paginate model, you have more fine-grained control over the entire process and can free up memory every pagination run.
The other trade off in this case is that if the server is multi-tasking, you are stealing a lot of i/o (mysql) in one fell swoop, then following up with a huge amount of cpu/memory. If you paginate, you switch from modest i/o (mysql) to modest cpu, then modest i/o, modest cpu (and so on), so you don't have to flat out deny other pending work.
I'm not ranting against pagination in a user frontend, that usually makes perfect sense as the typical user would only check out the first hand full of pages anyway.
What i'm talking about is an export script that creates the CSV export file in one go, just with multiple queries instead of a single one.
So any potential PHP side memory leak issues would hit you anyway while the script chews its way through the ~40K result rows; the only exception being the MySQL result set buffer which would indeed be smaller when using good old ext/mysql or mysqli_store_result() with the newer ext/mysqli (while mysqli_use_result() would only internally store one result row at a time anyway).
And regarding your multitasking/resource usage argument: any advantage of that in this "we need to show all data anyway" context would quickly be eaten away due to the O(n^2) nature of the approach, so that twice the amount of data would increase the database load four times while with a single query things would grow on a linear basis (assuming that the query itself scales linearly).
In this special case you'd also additionally have to count in that it does a GROUP BY and has "Using temporary; Using filesort" in it's EXPLAIN plan, so the LIMIT would save next to nothing in database resources while the pseudo-pagination causes the query to be run 400 times instead of just once ... and if we ever double the number of contacts in our database to 80K it would be run 1600 times then ... epic fail ...
I concur with Dan. Not really being interested in php memory leaks (that should be fixed by the developer), you still have to take into account the memory used for fetching the data from the db. If the developer hand-codes his queries, he can send a single select and fetch little by little. Unfortunately if there is an orm involved, it is most likely that this piecewise fetching is not supported, but sending many paginated queries is...
Any 'Solution' that scales by n^2 while an equivalent solution scales linearly with growing n is a bad idea. Period.
If you're using an ORM that can not deal with large result sets then the ORM is conceptually broken and adding LIMITs is just a workaround, not a solution.
And if you really have to use such a workaround then please use a sensible chunk size. Something in the range of 10K maybe ... but *definitely* not just 100 ...
Calendar
|
February '12 | |||||
| Mon | Tue | Wed | Thu | Fri | Sat | Sun |
| 1 | 2 | 3 | 4 | 5 | ||
| 6 | 7 | 8 | 9 | 10 | 11 | 12 |
| 13 | 14 | 15 | 16 | 17 | 18 | 19 |
| 20 | 21 | 22 | 23 | 24 | 25 | 26 |
| 27 | 28 | 29 | ||||
Quicksearch
Categories
Syndicate This Blog
Blog Administration
Powered by
