Для каждого запроса, который использует мультитенантную природу вашего дизайна, вы захотите иметь индекс, который включает tenantId. Вопрос в том, где в структуре индекса должен присутствовать tenantId? Ответ, конечно, зависит. Попробуйте построить индекс так, чтобы поле с наибольшей избирательностью было первым.
Например, предполагая таблицу с равномерным распределением по штатам (50) и с 10 арендаторами, я построил бы индекс как State, затем TenantId; для той же таблицы с 1000 арендаторов я бы построил индекс TenantId, затем State.
На практике оба индекса пригодятся (пусть оптимизатор разберется).