Главная страница статей --> Хитрости при программировании php, заметки по базам данных

Категориальное упорядочение результатов запроса

Источник: realcoding.net

Практические вопросы, которые возникают при работе с базами данных, часто требуют решений нестандартного характера, заставляя отвлечься на миг от запальцеванного монитора и, взяв карандаш, поимпровизировать на бумаге, концентрируясь в первую очередь на алгоритме решения... и только после -- на реализации. Имея (я надеюсь неплохую) привычку браузить форумы, посвященные СУБД, наталкиваюсь на разнообразные вопросы посвященные не только проблемам установки компонент, синтаксиса 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

Я буду весьма признателен за комментарии по поводу моей статьи.



Похожие статьи:
- Введение в технологию AJAX
- Сложные графики и диаграммы в ASP.NET. Часть пятая – интерактивность.
- Сила параметров XmlElement в Web-методах ASP.NET
- Путеводитель по обмену ссылками
- Частичная проверка правильности ввода данных.
- Postback и Query String - совместить несовместимое
- Секреты правильной раскрутки сайтов
- Средства безопасности ASP.NET. Аутентификация
- Новое в ASP.NET 2. Профили пользователей
- Ожидание выполнения длительного процесса в ASP.NET
- Сайты доноры - источники траффика
- Роль контента в раскрутке сайта
- Лекция 6. Работа с базами данных.


Оглавление | Обсудить на форуме | Главная страница сайта | Карта сайта |

Контакты
Редакция:
[0.001]