Well, based on that output it seems MySQL is using as effective a strategy as possible; covering indexes are being used for all joined sets resulting in ~24676*3 index lookups. Given the fact that the first set only reduces the result to 24K records, and the three remaining joins are matched against this (relatively) large result set, I'm not sure if you can do any better. My only suggestion would be to try to get the index selectivity a little better, heading towards a unique index. What kind of data is stored in these fields? Is it possible that the BID predicate may be more selective than the currently used AID left predicate? Just a thought...
Also, I'm having trouble understanding how this kind of query is producing slowdowns on the server. What is the throughput you consistently get for reads against this table (in queries/sec)? Has the slow query log identified this particular situation as causing numerous locking or read contention?
Jay Pipes
Community Relations Manager, North America, MySQL Inc.
Got Cluster?
http://www.mysql.com/cluster
Personal:
http://jpipes.com