Все сильно зависит от содержания (организации данных) ваших таблиц и от запросов, которые вы к ним делаете. Обычно строятся индексы по тем полям, которые участвуют в основных запросах. Тут самое главное не переборщить и не насоздавать индексов слишком много, иначе будет тормозить вставка.
Индексы сразу создаются по первичным/вторичным ключам.
Для анализа базы делайте explain ваших запросов -
https://habrahabr.ru/post/203320/
Ну и если запросов типа LIKE много, то имеет смысл проиндексировать ваши данные в поисковиках типа elasticsearch.