Provide item list with pager

It is now taking approx. 58 seconds to put up the initial list of nodes. I thought the db query might be slow so I checked into this thinking maybe I could add an index somewhere. Fishing throught the module, I think this is the first query caled:

SELECT DISTINCT(n.nid), n.type, n.title, n.created, n.changed, n.sticky, u.name, tn.tid FROM node n INNER JOIN users u ON u.uid = n.uid LEFT JOIN term_node tn ON n.nid = tn.nid WHERE ISNULL(tn.tid) ORDER BY n.sticky DESC, n.created DESC

I ran this in Mysql command line and it returned 749 rows in 0.12 seconds - not terrible. Then I ran

EXPLAIN SELECT DISTINCT(n.nid), n.type, n.title, n.created, n.changed, n.sticky, u.name, tn.tid FROM node n INNER JOIN users u ON u.uid = n.uid LEFT JOIN term_node tn ON n.nid = tn.nid WHERE ISNULL(tn.tid) ORDER BY n.sticky DESC, n.created DESC

to see if there were indexes and got this:

+----+-------------+-------+------+---------------+------+---------+---------------+------+---------------------------------+
| id | select_type | table | type | possible_keys | key  | key_len | ref           | rows | Extra                           |
+----+-------------+-------+------+---------------+------+---------+---------------+------+---------------------------------+
|  1 | SIMPLE      | u     | ALL  | PRIMARY       | NULL |    NULL | NULL          |   15 | Using temporary; Using filesort |
|  1 | SIMPLE      | n     | ref  | uid           | uid  |       4 | db03.u.uid |   44 | Using where                     |
|  1 | SIMPLE      | tn    | ref  | nid           | nid  |       4 | db03.n.nid |   16 | Using where; Not exists         |
+----+-------------+-------+------+---------------+------+---------+---------------+------+---------------------------------+

Really doesn't look bad - I don't think this is the problem.

Next I looked a firebug: profiling the javascript it look like there are over 64,000 calls and the longest ones each take multiple seconds most going to the jquery e (eval) function. I'm not much of a ajax guy so I'm not sure what to do next. Maybe I'll turn off all node types except pages (I have a few cck node types)

It seemed to worked fine when I had fewer nodes but now that I have over 1100, it has become very slow .

Any thoughts on improving performance are appreciated