Решение задачи второго конкурса 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
    Поделиться публикацией

    Комментарии 10

      0
      В целом все красиво, но, есть одно select * from table limit 0 работает дольше чем ручной обход схемы на больших таблицах. А вообще подход к решению шикарнейший. Меня остановил подобный путь чрезмерным расходом памяти. Хм, может перелинкуем наши решения?
        0
        Это можно, но учитывая, что я так долго писал статью, то с силами для объединения решений я соберусь еще не скоро =)
          0
          Ты же про линк на решение, что то я после 10 часов в автобусе невнимательный =) да конечно. я только за.
          0
          Глупый такой вопрос. Почему просто не сделать выборку SELECT… FROM A UNION B UNION C UNION D UNION ETC?
            0
            Особенно если учесть, что запрос select + group + count(*) + order by count(*) всё равно потребует full scan'а индекса (да какой нафиг индекса, если to_char еще накладывается), так что пользы от оптимизационного геморроя я что-то не вижу.
              0
              Промахнулся, ответил Вам ниже.
              0
              Вопрос не глупый. Такой вариант конечно рассматривался, однако поверьте мне на слово мой вариант работает быстрее. UNION — очень тяжеловесная операция, так как необходимо делать ORDER BY уже после объединения данных. Т.е. в моем варианте ORDER BY происходит для каждого столбца в отдельности за приемлимое время (однако не маленькое), а в случае с UNION эта сортировка происходит для всех данных вместе. Сравните: отсортировать 100 столбцов по миллиону записей в отдельности и отсортировать все эти данные после объединения. Выигрыш серьезный получается.
              по крайней мере в CUBRID.
              Я попробовал различные способы. Этот получился наиболее быстрым.
                0
                Много памяти жрет.
                  0
                  Знаю. Критерием была скорость. Если с учетом памяти, то другие решения лучше.
                    0
                    Нет, я про вариант с union :) А так — гораздо эффективней решение чем union. Нечто среднее — память/скорость. У меня скорость ниже, но памяти меньше расходуется.

                Только полноправные пользователи могут оставлять комментарии. Войдите, пожалуйста.