Могу предложить такой вариант. Делаем табличку cars_usage_profile
car_id, client_id, elapsed_usage_time,
где elapsed_usage_time - допустим суммарное время наката клиентом в секундах, если тариф вычисляться будет в коде, и я уверен, что это правильно. Мало ли как завтра захотят ещё обсчитывать, что тогда делать с имеющейся базой?
История заказов car_usage_history выглядеть тогда может так:
cars_usage_profile_id, date_start, date_finish,
откуда можно вычислить легко разницу во времени.
Далее, при каждом добавлении строчки в историю проката делаем обсчёт времени пользования. Тут есть быстрый вариант, когда можно взять предыдущее значение из cars_usage_profile и прибавить новое, а есть более медленный с пробеганием по всем строчкам истории с указанным cars_usage_profile_id, который если не будет устраивать - можно зафигачить в крон для полного пересчёта времени использования. Чисто так, для спокойствия души, что всё сходится.
Поиск будет работать очень быстро.