Archive for June, 2007
Reduced query time from 90 to 0.3 seconds
Kevin Day, June 20th, 2007Recently, I had a PHP script that used a MySQL query that joined three tables and then ordered the result by the index of the first table. It ran fine for a few weeks, but then one day the query started taking 90 seconds to run. Using MySQL’s EXPLAIN statement, I found it was reading from disk instead of memory, and that was probably causing the big slow-down.
Oddly, when I tried running the query in phpMyAdmin, the query ran in under a second, so it was hard to debug. But later when I ran the query from the MySQL console, it took 90 seconds just like the PHP script. I tried a few different versions of the query to make it run faster, and luckily all I had to do was drop the ORDER BY clause and the query time dropped to 0.3 seconds. The table was already sorted in the right order, so that clause wasn’t even necessary. I had just thrown it in there because I felt better explicitly specifying how it should be sorted. Guess I’ll know better next time.
I was surprised that the ORDER BY clause could make such a big difference. My guess is that the result (about 700 rows) got stored in a temporary table on the disk before it was sorted. However, I was even more surprised that phpMyAdmin gave a different query time than the console. Not sure why there would be a difference there.
Linux user at Best Buy
Kevin Day, June 10th, 2007I didn’t know that the xkcd guy followed me around…
Ordered sets are speedy
Kevin Day, June 2nd, 2007Right now I’m reading Structure and Interpretation of Computer Programs, and I just finished the section on representing sets of data. Before reading this book I wouldn’t have thought much about this problem, but it turns out that your code can run a lot faster if you order your sets before manipulating them.
For example, if you want to find the union of two sets without repeating any elements, an unordered representation of sets will require a O(n2) process, wheras an ordered representation of sets can use a O(n) process. I’m guessing that most comp sci majors know this stuff well, but it was a neat surprise to me.
For anyone else reading SICP, here’s my answers to problems 2.59 and 2.62:
2.59. Implement the union-set operation for the unordered-list representation of sets:
(define (union-set set1 set2)
(define (element-of-set? x set)
(cond ((null? set) false)
((equal? x (car set)) true)
(else (element-of-set? x (cdr set)))))
(cond ((null? set1) set2)
((element-of-set? (car set1) set2)
(union-set (cdr set1) set2))
(else (cons (car set1) (union-set (cdr set1) set2)))))
2.62. Give a O(n) implementation of union-set for sets represented as ordered lists.
(define (union-set set1 set2) (cond ((null? set1) set2) ((null? set2) set1) (else (let ((x1 (car set1)) (x2 (car set2))) (cond ((= x1 x2) (cons x1 (union-set (cdr set1) (cdr set2)))) ((< x1 x2) (cons x1 (union-set (cdr set1) set2))) ((< x2 x1) (cons x2 (union-set set1 (cdr set2)))))))))
