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

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

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

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

    За решением на 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

    Надеюсь, я был полезен.
    • +17
    • 1.5k
    • 2
    Share post

    Comments 2

      +2
      > MySQL не позволяет обновлять таблицу из которой производится чтение в одном UPDATE запросе
      Подзапросом можно.

      UPDATE `feed` `f` CROSS JOIN (подзапрос, заполняющий временную таблицу) `g` USING(`id`) SET `f`.`group` = `g`.`group`;

      При том, если не ошибаюсь, ещё пару спичек выиграем за счёт отсутствия копирования из временной таблицы, созданной для группировки результата, в сеансовую temporary table
        0
        О да, спасибо! И как я это проглядел :)
        Добавил в статью

      Only users with full accounts can post comments. Log in, please.