Практические вопросы, которые возникают при работе с базами данных, часто требуют решений нестандартного характера, заставляя отвлечься на миг от запальцеванного монитора и, взяв карандаш, поимпровизировать на бумаге, концентрируясь в первую очередь на алгоритме решения... и только после -- на реализации. Имея (я надеюсь неплохую) привычку браузить форумы, посвященные СУБД, наталкиваюсь на разнообразные вопросы посвященные не только проблемам установки компонент, синтаксиса SQL, доступа к БД... но и задачи алгоритмического характера, представляющие практический интерес. Одному из таких вопросов и посвящена настоящяя статья.
Итак, формулировка, в которой я встречал эту задачу в последний раз перед написанием статьи была приблизительно таковой (оригинал, говоря откровенно, был весьма расплывчатым, поэтому попробую в некоей мере перефразировать, опуская излишние детали): имеется таблица Images (ImageID INT, CategoryID INT, [Relevance] FLOAT), содержащая номера рисунков (ImageID), каждому рисунку сопоставляется некоторая категория (CategoryID), к которой он принадлежит, и релевантность ([Relevance]). Дело в том, что в задачу разработчика входила реализация некоего "поискового движка", который по определенным критериям возвращал бы соответствующее множество рисунков. Вобщим, как было ясно из поста, движок он построил согласно всем требованиям заказчика... кроме одного. Результат запроса, возвращаемого движком, нужно было упорядочить таким образом, чтобы получились "кортежи" (просьба не путать с понятием "кортеж" в теории реляционных баз данных) следующего вида. В первый кортеж должны входить наиболее релевантные рисунки по одному из каждой категории (упорядоченные по CategoryID), во второй -- следующие ниже по релевантности (то-есть, не более релевантные, чем первые, но наиболее релевантные из оставшихся) также по одному из каждой категории и т. д. Иными словами, результат запроса к движку должен быть отчет, состоящий из колонок, в каждой из которых находятся рисунки, принадлежащие фиксированной категории, и упорядоченные внутри колонки согласно релеванитности.
Хочу отметить, что в оригинале релевантность не содержалась в таблице, а определенным образом вычислялась на основе значений некоторых величин, извлекаемых из других таблиц. Но это не ограничивает ни в коей мере общности рассуждений... мы просто скрываем лишние детали. Кроме того, категорий рисунков имеется около дюжины (иными словами, небольшое число, но не фиксированное), в свою очередь разработчик приводил примерное число рисунков -- около 200 000. Рисунки приблизительно равномерно распределены по категориям, но "приблизительно" значит, что последние кортежи будут неполными, то-есть в общем случае в них будут присутствовать рисунки не из всех категорий. Ну и, естественно, читатель уже подметил, что для формулировки задачи абсолютно неважно, какие объекты мы рассматриваем (будь-то рисунки, как в нашем случае, или имена подружек... упорядоченные по релевантности). Главное -- это наличие двух признаков: групирующего (CategoryID) и упорядывающего ([Relevance]).
Ну что ж. Переходим к решению. Так как разаработчик использовал MS SQL Server 2000, то и мы будем использовать этот же SQL-сервер. Именно нам и понадобится Transact-SQL. Но сначала -- алгоритм. Итак, создаем временную таблицу, которая кроме столбцов таблицы Images будет содержать еще два: Ind и Ind2 целого типа. В эту таблицу (назовем ее @Tab) поместим все записи из Images, упорядоченные по CategoryID (по возростанию) в качестве первичного признака и по [Relevance] (по убыванию) в качестве вторичного, проставив им соответсвующие значения поля Ind от 1 до числа, равного количеству записей в Images. А теперь -- самый важный шаг. Точнее, последовательность шагов. Подсчитываем, сколько рисунков (записей) во всех категориях, кроме последней (согласно упорядочению по возрастанию). Пускай это число @x. Тогда в каждой записи последней категории полю Ind2 присваиваем значение Ind - @x. На следующем шаге подсчитываем, сколько записей во всех категориях, кроме двух последних и помещаем значение в @x. В каждой записи в предпоследней категории полю Ind2 присваиваем значение Ind - @x и т. д., пока не заполним значения Ind2 во всех записях. Таким образом мы добиваемся того, что Ind2 в рамках каждой категории будет изменяться от еденицы до числа, равного количеству рисунков в категории (естественно, в рамках категории упорядочение, задаваемое Ind2, будет совпадать с упорядочением по релевантности). И, наконец, упорядочиваем теперь @Tab по Ind2 (по возрастанию) в качестве первичного признака и по релевантности (по убыванию) в качестве вторичного. Следующий код иллюстрирует сказанное.
DECLARE @Tab TABLE (ImageID INT, CategoryID INT, [Relevance] FLOAT, Ind INT IDENTITY(1, 1), Ind2 INT) INSERT INTO @Tab (ImageID, CategoryID, [Relevance]) SELECT * FROM Images ORDER BY CategoryID ASC, [Relevance] DESC DECLARE @Cat TABLE (CategoryID INT) INSERT INTO @Cat SELECT DISTINCT CategoryID FROM Images DECLARE @Curr_Cat_Quant INT SELECT @Curr_Cat_Quant = COUNT(*) FROM @Cat DECLARE @Var1 INT DECLARE @Var2 INT WHILE @Curr_Cat_Quant > 0 BEGIN SELECT @Var1 = MAX(CategoryID) FROM @Cat SELECT @Var2 = COUNT(*) FROM @Tab A INNER JOIN @Cat B ON A.CategoryID = B.CategoryID WHERE A.CategoryID != @Var1 UPDATE @Tab SET Ind2 = Ind - @Var2 WHERE CategoryID = @Var1 DELETE FROM @Cat WHERE CategoryID = @Var1 SELECT @Curr_Cat_Quant = COUNT(*) FROM @Cat END
У читателя уже возник, наверное, вопрос: почему именно так, почему не создать для запроса из @Tab курсор и не пробежаться по записям, присваивая Ind2 сразу необходимое значение... и вобще, зачем нужны два поля Ind и Ind2. Но тут как раз все дело в производительности. Такой код ощутимо тормозил бы работу системы, так как рисунков в каждой группе у нас много, а FETCH -- "дорогостоящая" операция. Вместо этого мы предлагаем SQL-серверу самому заполнить Ind (посредством автоинкремента) и потом за несколько шагов (так как категорий у нас немного) обработать Ind2 с помощью более быстрой конструкции INSERT... SELECT.
Остается произвести заключительный запрос, который и дает нам необходимый результат:
SELECT * FROM @Tab ORDER BY Ind2 ASC, [Relevance] DESC
Я буду весьма признателен за комментарии по поводу моей статьи.
