Группировка серийных постов, близких по времени

Добрый день, Хабр!

В проекте столкнулся со следующей задачей: есть новостная лента фотографий, постить в которую пользователи могут только по одной фотографии, а отображать их нужно вместе в виде галереи. Иными словами, все строки выборки нужно логически объединить в несколько «временных окон» по каждому автору и использовать это при отображении.

Напрашивается группировать следующие один за одним посты, однако это не подходит: если два пользователя параллельно и неспешно аплоадят сотню фотографий — в ленту они добавляются поочерёдно, и при просмотре посты будут неприятно чередоваться.

За решением на MySQL

Постановка задачи

Сразу оговорюсь что группировать посты при выборке — неправильно: очень желательно чтобы группы изображений оставались статичными и ничто ниоткуда не отваливалось. Таким образом, каждый пост должен явно относиться к какой-то «группе», визуально представляемой галереей.

Решение — не панацея, но есть круг задач где именно этот подход может пригодиться.

Сначала оформим таблицу для экспериментов:

CREATE TABLE `feed`(
 `id` INT UNSIGNED NOT NULL AUTO_INCREMENT,
 `tm` INT UNSIGNED NOT NULL COMMENT 'timestamp',
 `user_id` INT UNSIGNED NOT NULL COMMENT 'author id',
 `image` VARCHAR(255) NOT NULL COMMENT 'posted image filename',
 `group` INT UNSIGNED NULL DEFAULT NULL COMMENT 'post group',
 PRIMARY KEY(`id`),
 INDEX(`user_id`),
 INDEX(`tm`,`group`)
 );

Таблица `feed` — это список постов. У каждого поста есть время добавления tm, ссылка на автора user_id, собственно картинка, а также мы добавляем специальный столбец group который и позволяет группировать изображения в галерею. При добавлении новой записи group=NULL.

Вариант неправильный

Сначала кажется: выбираем самый свежий пост, дальше выбираем посты того же юзера в радиусе одного часа, и присваиваем им всем group= id-первого-поста. Только в этом случае каждый пост, окажется, будет принадлежать только своей группе. Нет, не подходит :)

Группировка

Сперва нужно определить критерий временнОй близости постов:

SET @granularity:=60*60;

Так, все посты в пределах одного часа группируются в одну галерею.

Далее совершаем следующий логический ход: даём каждому посту стать «основой» для группы:

SELECT `g`.`id` AS `group`
FROM `feed` `g`;

И такая группа будет содержать строки в часовом радиусе от «основы» (разница времени — в пределах одного часа):

SELECT `g`.`id` AS `group`, `f`.*
FROM `feed` `g`
    CROSS JOIN `feed` `f`
    ON (`f`.`user_id` = `g`.`user_id` 
        AND `f`.`tm` BETWEEN `g`.`tm`-@granularity AND `g`.`tm`
    )

Так, теперь у каждой строки есть ряд кандидатов в основы. Критерий выбора: выбираем в качестве «основы» пост, содержащий наибольшее число постов в своём часовом радиусе.
Чтобы не напрягать MySQL лишними вычислениями — вместо радиуса используем критерий `f`.`tm` BETWEEN `g`.`tm`-@granularity AND `g`.`tm`: тогда основа с самым широким составом будем иметь наибольший `id`:

SELECT MAX(`g`.`id`) AS `group`, `f`.*
FROM `feed` `g`
    CROSS JOIN `feed` `f`
    ON (`f`.`user_id` = `g`.`user_id` 
        AND `f`.`tm` BETWEEN `g`.`tm`-@granularity AND `g`.`tm`
    )
GROUP BY `f`.`id`

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

Отмечу, что здесь есть нюанс. При отображении такой ленты мы теперь будем сортировать по `group` DESC. Тогда если в приведённом выше коде используется функция MAX() то в сортировке ленты самая свежая «группа» (получившая последнее обновление) будет прыгать в самый верх.
Это поведение можно легко изменить: тогда мы получаем постоянные группы, такие, что элементы не могут перемещаться из одной в другую: для этого достаточно использовать функцию MIN(): основой тогда всегда становится самый старый пост, и группа может лишь дополняться новыми поступающими фотографиями:

SELECT MIN(`g`.`id`) AS `group`, `f`.*
FROM `feed` `g`
    CROSS JOIN `feed` `f`
    ON (`f`.`user_id` = `g`.`user_id` 
        AND `f`.`tm` BETWEEN `g`.`tm` AND `g`.`tm`+@granularity
    )
GROUP BY `f`.`id`

Теперь нам нужно обновить таблицу по результатам этого запроса: задать значение столбца `group`. MySQL не позволяет обновлять таблицу из которой производится чтение в одном UPDATE запросе, поэтому приходится сначала перенести нашу выборку во временную таблицу:

CREATE TEMPORARY TABLE `_feedg`
SELECT MAX(`g`.`id`) AS `group`, `f`.`id`
FROM `feed` `g`
    CROSS JOIN `feed` `f`
    ON (`f`.`user_id` = `g`.`user_id` 
        AND `f`.`tm` BETWEEN `g`.`tm`-@granularity AND `g`.`tm`
    )
WHERE `f`.`group` IS NULL 
    OR `f`.`tm` >= (UNIX_TIMESTAMP()-2*@granularity)
GROUP BY `f`.`id`;

Обратите внимание на появившееся условие WHERE: оно используется для оптимизации чтобы перегруппировка осуществлялась только над самой верхушкой таблицы, среди свежайших записей.

Теперь, используя временную таблицу, можно обновить исходную:

UPDATE `feed` `f` CROSS JOIN `_feedg` `g` USING(`id`)
SET `f`.`group` = `g`.`group`;

Запрос желательно выполнять после каждой вставки, но для оптимизации можно это делать по крону, оставив часть работы на алгоритм вывода.

UPD: как подсказал Melkij — действительно, обновлять можно если запрос чтения сделать подзапросом вместо JOIN'а. Тогда убираем полностью CREATE TEMPORARY TABLE, а запрос UPDATE будет выглядеть так:

UPDATE `feed` `f` CROSS JOIN (
    SELECT 
        MAX(`g`.`id`) AS `group`, 
        `f`.`id`
    FROM `feed` `g`
        	CROSS JOIN `feed` `f`
        	ON (`f`.`user_id` = `g`.`user_id` AND `f`.`tm` BETWEEN `g`.`tm`-@granularity AND `g`.`tm`)
    WHERE `f`.`group` IS NULL OR `f`.`tm` >= (UNIX_TIMESTAMP()-2*@granularity)
    GROUP BY `f`.`id`
    ) `g` USING(`id`)
SET `f`.`group` = `g`.`group`;

Выборки

Теперь, как грамотно осуществить выборку из такой таблицы?

Если `group` проставлен для всех строк — тогда

SELECT * 
FROM `feed`
ORDER BY `group` DESC, `tm` DESC;

Однако в случае если приведённый выше запрос запускается по крону и, следовательно, у нас есть часть строк для которых group=NULL, часть логики вывода должна возлагаться на скрипт-рендерер, а выборку следует делать так:

SELECT * 
FROM `feed`
ORDER BY `group` IS NULL, `group` DESC, `tm` DESC;

Ссылки

Мой вопрос на stackoverflow: Stackoverflow: Grouping serial posts in a user feed. Здесь можно полюбоваться как это делается в Oracle с использованием «временных окон».

SQLfiddle, поиграться: SQLfiddle

Надеюсь, я был полезен.