Вам нужен нижний диапазон? Есть ли записи ранее 1901 года?
Как создается столбец time_id? Если time_id всегда больше с каждой новой записью, добавляемой в БД, вы можете рассмотреть поиск идентификатора с ближайшей записью к 2009-01-16, а затем выбрать по идентификатору
select my_field_A, my_field_B
FROM
mytable
WHERE
id <= ?
Если это не так, попробуйте проверить разделение, доступное в MySQL 5.1, и разбейте таблицу по годам, что должно значительно увеличить скорость.