Использование бинарного поиска для оптимизации запроса на выборку данных

[@konsoletyper]

выполняющий 3 INNER JOIN'а на таблицы, размеры которых впечатляли. Каждая таблица в среднем содержала 40 000 000 миллионов записей. Получается, что временная таблица состояла бы из 4*4*4*10^21 = 64*10^21 записей

O_O А точно никак не обойтись без этих INNER JOIN'ов? Тем более, кто сказал, что JOIN'ы выполняются путём создания декартова произведения и полного просмотра получившейся таблицы? Всё сильно зависит от наличия индексов и типа отношений.

Итак, предположим, что нам необходимо сделать INNER JOIN на 3 таблицы, а затем задать условие «столбец х в диапазоне между 10 и 20». Причём столбец х не имеет индекса.

Ну так а добавить индекс? Или там так часто делаются вставки/обновления? Тогда непонятно, почему по такой нагруженной таблице строятся отчёты.

Берем таблицу с этим самым столбцом и применяем на ней бинарный поиск, для поиска диапазона первичных ключей, удовлетворяющих условию 10<=x<=20

Т.е. правильно ли я понимаю, что значения в столбце x монотонно возрастают, т.е. для любых строк a и b верно: a.id > b.id => a.x > b.x? Но в любом случае, бинарный поиск — это поиск по индексированному списку, а не по таблице. Индексированный список, в отличие от таблицы, не содержит «дырок», так что в нём не стоит проблемы «а что делать, если при очередном разделении пополам мы не нашли элемент с индексом k».

[@kazmiruk]

Можно обойтись и без джойнов, но тогда мы бы не смогли получить результат одним запросом и пришлось бы выполнить кучу кода на php с огромным объемом данных. Да, много подготовительной работы, но зато всего один запрос для получения ответа.
Проект достался мне уже таким. Делать еще один индекс для такой таблицы это довольно проблематично. Займет кучу времени и не факт, что его польза потом проявится где-то еще кроме этой задачи. И да, в таблицы делается довольно много вставок.
Задачу ставлю не я. Обычно проектируется и разрабатывается система, а потом начальство проявляет желание получить кучу красивых графиков по таблицам, которые не были спроектированы для такой задачи.
Про монотонное возрастание верно. Но х и id не обязательно должны возрастать. Один столбец может возрастать, а второй убывать. Суть от этого не поменяется, диапазон мы тоже сможем найти.
Дырки в таблице безусловно есть. Это решалось тем, что если выбирался id, который попадает на дырку, то выбирался ближайший элемент и его значение.

[@Busla]

Как же получается «для подобной выборки использовать только индексы», если столбец по которому выбираете не индексирован?!

[@kazmiruk]

В самом запросе будут участвовать: при определении диапазонов используются только первичные ключи, в джойнах вместо диапазона вида «WHERE x > 10 AND x <20» мы уже напишем «WHERE id>1000 AND id<2000», где id=1000 — элемент со значением 10 и максимальным id, а id=2000 — элемент со значением 20 и минимальным id (для случая монотонного возрастания id и x). Вся суть в том, чтобы вместо столбцов без индексов использовать первичные ключи. Но этот способ подходит только если данные монотонно возрастают\убывают, как уже заметил konsoletyper.