I have a table that has 2.1G in data, 500.8M in index (3 indexes), and there are 10.2 million rows.

I'm joining with a much smaller table that's 9.7M in data, 17.9M in index (3 indexes), and 362,000 rows.

Here's the query:

SELECT table_A.id, username, folder, status, postdate, sender, subject, message, table_B.image
 FROM table_A
 LEFT JOIN table_B
  ON table_B.id = table_A.id
 WHERE username='example' AND folder='inbox'
 # this is actually all of the possible values for status, so I tested with and without this line
 AND (status = "New" OR status = "" OR status IS NULL) 

 AND COALESCE(table_B.sorter,0) = 0
ORDER BY POSTDATE DESC
LIMIT 21 

# offset is there because I paginate
OFFSET 0

# I also tried this, but it was no different:
SELECT table_A.id, username, folder, status, postdate, sender, subject, message, table_B.image
 FROM table_A
 LEFT JOIN table_B
  ON table_B.id = table_A.id
  AND COALESCE(table_B.sorter,0) = 0
 WHERE username='example' AND folder='inbox'
 AND (status = "New" OR status = "" OR status IS NULL) 
ORDER BY POSTDATE DESC
LIMIT 21 
OFFSET 0

The problem I'm having is when there are a lot of rows that match the WHERE, the query time is much slower! For example, I have one where there are 14,645 matches, and the query takes 4.960s to complete. Another has 3,269 matches, and the query took 3.0691s.

When I use Explain:

table: table_A
type: range
possible_keys: New Messages

# this index is on username, folder, and status
key: New Messages

key_len: 106
key_ref: NULL
rows: 8944
Extra: Using index condition; Using where; Using filesort

table: table_B
type: ref
possible_keys: id_2,ID,View

# this index is on id, sorter, and image; id_2 is on id and sorter, but I used "USE INDEX (id_2)" and it had no impact
key: View

key_len: 4
ref: goncco_forum.private_messages.id
rows: 1
Extra: Using where; Using index

But when I do the same query without joining with table_B, it finishes in 0.0655s. So the delay is definitely coming from the JOIN, but I can't see why?