You mention you have indexes on the id of each table but do you have indexes on the foreign keys (a_id, b_id) in your example? And do you have and index for the column you use in the query if it is a common search?