Решение задачи второго конкурса CUBRID it!

Привет, Хабраюзер! Предлагаю твоему вниманию решение задачи, победившее на втором конкурсе CUBRID it! Суть конкурса заключается в поиске наиболее оптимального решения SQL задачи, используя Java или PHP. Решение чисто алгоритмическое, поэтому даже если ты не связан с CUBRID и конкурсом CUBRID it!, то все равно загляни под кат – это может быть просто интересно и даже полезно. Поехали!

Задача конкурса

Имеется база данных, разумеется, CUBRID. Задача конкурса найти значение, которое чаще всего встречается в базе данных. В таблицах базы используются типы данных из ограниченного списка. Значение нужно приводить к типу string, используя стандартные функции базы данных и значение не должно состоять только из цифр. Подробное условие задачи можно найти здесь.

Решение

Во-первых, нам необходимо получить список столбцов и их типов во всех таблицах нашей базы данных. Для этого мы можем воспользоваться функциями PDO или «родными» драйверами CUBRID.

Получение списка таблиц:

cubrid_schema( $this->conn , CUBRID_SCH_CLASS );

Выбрав нужные таблицы, сделаем к каждой из них запрос:

$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)
Интересное решение призера конкурса Ekstazi
Задача конкурса (Англ)
Анонс конкурса на Хабре (Рус)
Победители конкурса (Англ, Рус)
Документация CUBRID