Привет, Читатель! Предлагаю твоему вниманию решение задачи, победившее на втором конкурсе CUBRID it! Суть конкурса заключается в поиске наиболее оптимального решения SQL задачи, используя Java или PHP. Решение чисто алгоритмическое, поэтому даже если ты не связан с CUBRID и конкурсом CUBRID it!, то все равно загляни под кат – это может быть просто интересно и даже полезно. Поехали!
Задача конкурса
Имеется база данных, разумеется, CUBRID. Задача конкурса найти значение, которое чаще всего встречается в базе данных. В таблицах базы используются типы данных из ограниченного списка. Значение нужно приводить к типу string, используя стандартные функции базы данных и значение не должно состоять только из цифр. Подробное условие задачи можно найти здесь.
Решение
Во-первых, нам необходимо получить список столбцов и их типов во всех таблицах нашей базы данных. Для этого мы можем воспользоваться функциями PDO или «родными» драйверами CUBRID.
Получение списка таблиц:
cubrid_schema( $this->conn , CUBRID_SCH_CLASS ); |
Выбрав нужные таблицы, сделаем к каждой из них запрос:
1 2 3 | $result = cubrid_execute( $this->conn , "SELECT * FROM {$table['NAME']} LIMIT 0;"); $column_names = cubrid_column_names($result); $column_types = cubrid_column_types($result); |
$column_names
и $column_types
содержат соответственно массивы с названиями полей таблицы и типом данных каждом из них.
Далее нам необходимо сделать выборку по каждому столбцу. В общем виде запрос будет выглядеть так:
SELECT TO_CHAR(`fieldname`), COUNT(*) FROM `tablename` GROUP BY `fieldname` ORDER BY 2 DESC; |
Такой запрос мы должны сделать для каждого столбца в базе данных. Запрос может незначительно изменяться, в зависимости от типа данных столбца. В результате мы получаем таблицу вида «Значение»-«Количество значений в столбце», отсортированную по убыванию количества значений. Пример результата запроса:
Значение | Количество |
---|---|
CUBRID | 159 |
HOLA! | 80 |
14,3 | 50 |
… | … |
Это значит, что значение «CUBRID» встречается в поле таблицы 159 раз, а «14,3» только 50.
Запрос, который мы используем, довольно простой и очень быстрый, практически без всяких проверок, за исключением отдельных случаев. Таких запросов много – по одному на каждый столбец в базе данных, но не пугайтесь, мы не будем загружать все эти значения в память PHP, мы будем работать с указателем на результат запроса. Для удобства работы сохраним указатели на результаты запросов в виде массива.
Теперь мы должны подсчитать, какое же значение наиболее часто встречается в таблицах нашей базы данных. Для этого в цикле будем брать из нашего массива указателей один результат запроса и из него извлекать текущую строку.
Для примера возьмем три столбца Field1, Field2, Field3, из которых в результате запроса получились следующие данные:
Результат запроса для поля Field1:
Значение | Количество |
---|---|
CUBRID | 159 |
HOLA! | 80 |
14,3 | 50 |
… | … |
Результат запроса для поля Field2:
Значение | Количество |
---|---|
14,3 | 160 |
CUBRID | 100 |
xyz | 90 |
… | … |
Результат запроса для поля Field3:
Значение | Количество |
---|---|
HOLA! | 100 |
14,3 | 10 |
xyz | 5 |
… | … |
Таблицы могут быть любого размера, и соответственно результат, который получается после запроса, может представлять собой очень большую таблицу.
На каждом шаге цикла мы будем считывать по одной строке этих таблиц и заносить их в специальный массив, таким образом, после первого обхода таблиц результат будет выглядеть так:
Array('CUBRID' => 159, '14,3' => 160, 'HOLA!' => 100) |
На этом этапе проверяется, чтобы строка не состояла только из цифр, согласно условию задачи.
Полученные данные мы заносим в массив. Для наглядности текущий результат буду показывать в виде сводной таблицы, которая после первого обхода выглядит так:
Значение | Field1 | Field2 | Field3 | Сумма | Потенциальное количество |
---|---|---|---|---|---|
14,3 | — | 160 | — | 160 | 259 |
CUBRID | 159 | — | — | 159 | 260 |
HOLA! | — | — | 100 | 100 | 319 |
В массив вносятся данные при каждой новой итерации цикла. Дефис означает, что это значение еще не встречалось в этом столбце, а соответственно оно еще может встретиться. Но если оно встретиться, то его количество будет не больше, чем количество предыдущего найденного в том же столбце, так как эти наши таблицы результатов отсортированы по убыванию количества значений. Это означает, что даже если значение «CUBRID» будет следующим в столбце «Field2», его количество будет не больше, чем 160. «Потенциальное количество» — это то, сколько максимально может набрать данное значение, т.е. по сути «сумма дефисов». Потенциальное количество для «CUBRID» определяется исходя из предположения, что это значение встретится в следующей итерации в полях «Field2» и «Field3» с максимально возможным количеством (160 и 100) соответственно.
Что нам дают эти данные? Они нам говорят о том, сколько может набрать в сумме то или иное значение. Сумма + Потенциальное количество – это и есть то количество, которое теоретически может быть в итоге для текущего значения. Исходя из этого числа, мы можем сделать предположение, сможет ли оно быть первым в этом списке, или его уже можно вычеркнуть и не учитывать в дальнейшем. Дальше мы увидим, как это работает.
После следующего шага («HOLA!» — 80, «CUBRID» — 100, «14,3» — 10) таблица выглядит следующим образом:
Значение | Field1 | Field2 | Field3 | Сумма | Потенциальное количество |
---|---|---|---|---|---|
CUBRID | 159 | 100 | — | 259 | 10 |
HOLA! | 80 | — | 100 | 180 | 100 |
14,3 | — | 160 | 10 | 170 | 80 |
Обратите внимание на значение «14,3»: его сумма 170 и потенциально он может набрать только 80. Т.е. при самом удачном раскладе его количество будет 250, что уже меньше, чем у текущего лидера (CUBRID — 259). Значит это значение уже никогда не займет первое место в нашем списке. Так ему и надо. Мы можем смело удалять значение «14,3» из списка и больше его не учитывать. Так мы будем поступать со всеми значениями, которые не смогут стать лидерами. Таким образом, мы формируем «Топ» из тех значений, у которых есть шанс занять первое место.
При следующем шаге («14,3» — 50, «xyz» — 90, «xyz» — 5) мы увидим, что теперь, любое значение которого нет «Топе» не сможет набрать больше 145 (50+90+5), а значит и занять первое место. На этом можем остановить наш поиск и не смотреть оставшиеся значения в таблицах, так как эти значения просто не попадут в «Топ».
Теперь, когда у нас есть точный список претендентов на лидерство, нам достаточно найти их количество в тех столбцах, в которых у нас стоит дефис, т.е. в тех в которых у нас еще могут оставаться значения. Это делается несложными запросами вида:
SELECT `Field3`, COUNT(*) FROM `tablename` WHERE `Field3` = `CUBRID` GROUP BY `Field3`; |
Просуммировав количество в разных столбцах для каждого значения, мы узнаем наиболее часто встречающееся значение в базе данных. Что собственно нам и нужно из условия задачи.
Спасибо за внимание, несколько интересных ссылок:
Исходный код решения (лицензия GPL v2)
Интересное решение призера конкурса
Задача конкурса (Англ)
Анонс конкурса на Хабре (Рус)
Победители конкурса (Англ, Рус)
Документация CUBRID