Runcible, ваш запрос может быть переписан. Вы всегда должны указывать свои условия JOIN в предложении ON, а не в WHERE.
Ваш запрос станет:
SELECT TableB.bar
FROM TableB
JOIN TableA
ON TableB.shared_id = TableA.shared_id
AND TableA.foo = 1000;
Мало того, что вы хотите сделать это:
ALTER TABLE TableB ADD INDEX (shared_id,bar);
Вы хотите добавить индекс к A следующим образом:
ALTER TABLE TableA ADD INDEX (foo, shared_id);
Сделайте это и предоставьте EXPLAIN вывод, пожалуйста.
Также обратите внимание, что добавляя индекс в (shared_id, bar), вы просто сделали свой индекс (shared_id) избыточным. Брось.