Slow SELECTs on node table w/ORDER & my hacky solution

http://drupal.org –

So i have about 12500 rows in my node table currently. This doesn't seem like a ridiculous amount... I have been on projects with far more and I expect the table to grow on this project. The problem I have is when I have to run SELECT queries on the node table, specifically ones that are general "get the newest content of type x" where I have to order a large result set, the queries are real slow...

For example:

A)

SELECT * FROM `drupal_node` n
JOIN drupal_content_type_news c ON n.nid = c.nid and n.vid = c.vid
WHERE n.type = 'news' AND c.field_news_title_value <> ''
ORDER BY n.nid DESC

*** Showing rows 0 - 29 (3,548 total, Query took 0.9636 sec)

Or if I want to join for the path alias (it is sometimes faster with the extra join which doesn't make sense, exp since it seems like having to do that join using CONCAT would be slow...)

B)

SELECT * FROM `drupal_node` n
JOIN drupal_content_type_news c ON n.nid = c.nid and n.vid = c.vid
JOIN drupal_url_alias url ON url.src = CONCAT('node/', n.nid)
WHERE n.type = 'news' AND c.field_news_title_value <> ''
ORDER BY n.nid DESC

*** Showing rows 0 - 29 (3,548 total, Query took 0.8300 sec)

So anyways, all my indexes seem to be working at whatnot... things are just slow because of the number of rows that are being scanned to do the ordering.