LINUX.ORG.RU

PostgreSQL. Группировка по временному интервалу

 , ,


1

2

Сап, Лор! Есть поток данных с таймштампом:

        time         
---------------------
 2015-02-08 08:57:21 
 2015-03-23 05:22:42 
 2015-03-23 05:24:52 
 2015-03-23 05:25:14 
 2015-03-23 05:25:46 
 2015-04-03 13:00:28 
 2015-04-03 13:00:33 
 2015-04-03 13:00:38 
 2015-04-03 13:00:43 
 2015-04-03 13:00:48 

Нужно этот поток сгруппировать, таким образом, что бы в каждой группы образовались рекорды с разницей во времени не более X. Т.е. на выходе получить что то типа такого:

        time         | group_field 
---------------------+----------
 2015-02-08 08:57:21 |        1
 2015-03-23 05:22:42 |        2
 2015-03-23 05:24:52 |        2
 2015-03-23 05:25:14 |        2
 2015-03-23 05:25:46 |        2
 2015-04-03 13:00:28 |        3
 2015-04-03 13:00:33 |        3
 2015-04-03 13:00:38 |        3
 2015-04-03 13:00:43 |        3
 2015-04-03 13:00:48 |        3

Время хранится в UTC. Есть идеи как такое реализовать? Сейчас это реализовано через отдельную сущность (group_field - id сущности), что ОЧЕНЬ усложняет CRUD, т.к. объем данных велик. Поэтому было принято решение отказаться от сущности в пользу такой группы-фантома.

★★★★

а сейчас как вычисляется group_field?

maxcom ★★★★★ ()
Ответ на: комментарий от maxcom

ID реальной сущности. Т.е, при сохранении идет проверка: если временной интервал между полученным и последним рекордом (от одного источника) не превышает допустимое значение - задаем ID из предыдущего рекорда, в противном случае - создаем новый инстанс сущности, добавляем в зависимость полученный рекорд и каскадно сохраняем.
Все происходит на бекенде, никаких триггеров и функций.

comp00 ★★★★ ()

Можно считать что всё уже пришло и хранится в базе? Если нет, то поток приходит всегда отсортированный по таймстампу?

urquan ()
Последнее исправление: urquan (всего исправлений: 1)

А нельзя ли id-ом группы просто взять время с начала эпохи по модулю X? Например, если X - это минута, то X - это число минут с начала эпохи?

В противном случае задача не имеет однозначного решения. Например, у тебя три точки с интервалом в 40 секунд. Их можно двумя способами (а то и тремя) разбить на группы.

den73 ★★★★★ ()
Последнее исправление: den73 (всего исправлений: 1)

немного анально конечно ), ябы лучше триггером заполнял это

with one(t) as (
values
	('2015-02-08 08:57:21'), 
	('2015-03-23 05:22:42'),
	('2015-03-23 05:24:52'), 
	('2015-03-23 05:25:14'),
	('2015-03-23 05:25:46'), 
	('2015-04-03 13:00:28'), 
	('2015-04-03 13:00:33'), 
	('2015-04-03 13:00:38'), 
	('2015-04-03 13:00:43'), 
	('2015-04-03 13:00:48')
),
two as (
	select row_number() over() as id, t,
		extract(epoch from t::timestamp without time zone at time zone 'utc')::bigint as tt
	from one
),
three as (
	select two.*, 
		two.tt - lag(two.tt) over (order by id) > 100000
		or lag(two.tt) over (order by id) is null as start_of_group
		from two
) 
select three.t, sum(three.start_of_group::int) over(order by id) as group_field
from three

drsm ()
Ответ на: комментарий от urquan

Не можно, а нужно. В том то и дело, что поток не шотсортирован. Т. е. в общем случае, каждая запись содержит время, более позднее чем предыдущая, но существует несколько частных случаев когда эта закономерность нарушается. Причем эти частные случаи (как оказалось) весьма часты, к сожалению. В любом случае, группировать необходимо данные из таблицы.

comp00 ★★★★ ()
Ответ на: комментарий от den73

А нельзя ли id-ом группы просто взять время с начала эпохи по модулю X? Например, если X - это минута, то X - это число минут с начала эпохи?

А как разрешать коллизии? Очевидно же что набор ID-шек будет цикличным. Или я не так понял?

Например, у тебя три точки с интервалом в 40 секунд. Их можно двумя способами (а то и тремя) разбить на группы.

Не важно какой интервал между первой и последней точки, важен интервал между парами. Пока интервал не превышает заданное значение - точки принадлежат одной группе.

comp00 ★★★★ ()
Ответ на: комментарий от comp00

Ааа, т.е. группа заканчивается, когда наступает перерыв длиннее чем X?

Ну тогда мне кажется, это не стоит делать средствами SQL. Это нужно делать путём создания курсора, идущего по записям по порядку, и сравнивать следующее с предыдущим. Я не знаю postgres, но там есть возможность писать на языках программирования хранимые процедуры. Вот её и придётся использовать. В Firebird или MS SQL я бы именно хранимками бы воспользовался, если это нужно в оффлайне.

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

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

den73 ★★★★★ ()
Ответ на: комментарий от drsm

К сожалению, я сейчас не могу проверить, но суть понял. Догадывался, что надо копать в сторону row_number.
По поводу триггера (пусть это фактически и не триггер вовсе будет, а просто логика при сохранении сущности в бд) - сейчас по сути так и реализовано. Тут возникает проблема когда приходят данные между 2мя группами, и эти группы надо переформировать в одну. И таких частных случаев хватает. Сейчас реализован целый механизм по сохранению этих сущностей, разделению их на группы. И он работает (даже с фичами), но адски медленно. Перенести его в БД на триггеры - это дать прирост в 10-15% но навсегда потерять понимание как этот монстр работает.
Нет, эти группы должны формироваться динамически, и должны отображать актуальность лишь на момент запроса. Иначе смысла заморачиваться с новым решением просто нет

comp00 ★★★★ ()
Ответ на: комментарий от den73

Клиентов много, плюс данные, в принципе, хронологически не отсортированы.
Нужно в реалтайме.
Одна таблица, данные с сотни устройств, на каждое устройство сейчас по несколько сотен групп. Сам понимаешь, если планировщиком все это дело проходить и хранимкой апдейтить - база ляжет уже на 1кк записей...

comp00 ★★★★ ()
Ответ на: комментарий от comp00

Ну это сложная задачка. Тогда в любом случае id-ом группы я бы сделал тамстамп первого сообщения в группе. В остальном надо подумать. Надо ли, чтобы база в рилтайме принимала данные от клиентов или они могут повисеть некоторое время, пока база наведёт порядок с группами? Кстати, насчёт по модулю я неправильно сказал, не по модулю, а целое(число секунд с начала эпохи/X).

den73 ★★★★★ ()
Последнее исправление: den73 (всего исправлений: 1)
Ответ на: комментарий от den73

Ну индекс-то по таймстампу хотя бы ты можешь создать?

den73 ★★★★★ ()
Ответ на: комментарий от den73

Тогда в любом случае id-ом группы я бы сделал тамстамп первого сообщения в группе.

Первое «сообщение» понятие слишком относительное, что бы делать его ключем. Пришло сообщение с более ранним таймом - и что, у всех n записей группы обновлять этот ключ? А еще может быть такой случай: запись попадает в интервал между группами, и группы необходимо смержить. Эти все нюансы и вошли в формулировку «ОЧЕНЬ усложняет CRUD».
Преимущества подхода через статичные данные, хранимые в таблице, только в том, что легко по по этой статике получить выборку «сообщений» из группы, на этом все плюсы заканчиваются. Ибо логика там мама не горюй, к сожалению.

Ну индекс-то по таймстампу хотя бы ты можешь создать?

Не суть важно что будет в поле, по которому надо группировать. Главное по этому что-то сгруппировать, и получить массив рекордов. А дальше кеширование в какую нибудь noSQL и работа с хешем.

comp00 ★★★★ ()
Последнее исправление: comp00 (всего исправлений: 1)
Ответ на: комментарий от comp00

это знакомая блин ситуация, в моем случае, правда «более старые» данные прийти не могут, просто GPS time vs internal RTC. и когда последние убегают вперед, получается дельтаТЭ отрицательной при синке времени девайсом...

Догадывался, что надо копать в сторону row_number.

не ровнумбер, скорее window functions нужен lag чтобы считать дельту и sum для start_of_group, это «паттерн» такой: отмечаешь начала групп, потом сум по ним для сквозной нумерации.

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

ну по идее норм, попробовал на реальных данных

select count(*), max(gid) from (
select *, sum(sog::int) over(order by id) as gid 
from (
	select id, datetime, coalesce(datetime - lag(datetime) over(order by id) > '00:10:00', true) sog
	from track where device_id = ? order by id
) _
) _

1037326;107
меньше двух секунд у меня если индексы в кеше, думал будет тормозней

drsm ()
Ответ на: комментарий от comp00

Первое «сообщение» понятие слишком относительное, что бы делать его ключем. Пришло сообщение с более ранним таймом - и что, у всех n записей группы обновлять этот ключ? А еще может быть такой случай: запись попадает в интервал между группами, и группы необходимо смержить. Эти все нюансы и вошли в формулировку «ОЧЕНЬ усложняет CRUD».

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

Не суть важно что будет в поле, по которому надо группировать.

Это я просто думаю про план запроса. Если у тебя индекс по таймстампу, ты можешь получить группы за один проход по всем записям по возрастанию, причём это будет один проход по возрастанию индекса, для этого нужен курсор, как я уже писал выше, и тебе не понадобится строить дополнительную выборку в памяти сервера для выполнения запроса. На выходе будет поток из идентификаторов записей и кодов группы, который ты хочешь. Соответственно, это вопрос к производительности БД - можешь ли ты себе позволить такой индекс. Не знаю, как в Postgres, а вообще построение индекса может замедлить работу БД, и его надо периодически перестраивать для балансировки.

den73 ★★★★★ ()
Ответ на: комментарий от drsm

Впервые вижу over, но почему у тебя тут order by id в группировке, если данные могут прийти не в порядке возрастания времени? Я так понял, автору темы нужен порядок по времени?

den73 ★★★★★ ()
Ответ на: комментарий от drsm

Похоже, у нас похожие задачи, у меня тоже device_id, track_id, и координаты GPS...
Собственно, вся эта тема - это ничто иное, как попытка перехода к динамическому представлению треков...
Можно поинтересоваться, как ты делишь на треки (достаточно словесного описания процесса)? Может я принципиально в чем-то заблуждаюсь.

За рабочий запрос спасибо.

comp00 ★★★★ ()
Ответ на: комментарий от den73

слияние двух групп в начале истории приведёт к перенумерации всех групп.

Ну нет, при слиянии групп, по сути, берется одна из групп (с наибольшим числом рекордов), в нее добавляются рекорды из меньшей группы, меньшая группа дропается.

Это я просто думаю про план запроса.

В данный момент на таблице 2 индекса: time и уникальный time + field1 + field2.

Postgres, а вообще построение индекса может замедлить работу БД, и его надо периодически перестраивать для балансировки.

Ну я выполняю VACUUM ANALYZE периодически xD.

Я так понял, автору темы нужен порядок по времени?

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

comp00 ★★★★ ()

Если тебя устроит решение с группировкой по каким-то временным единицам (по секундам, по минутам, по часам, дням, неделям, месяцам или годам), тогда можешь использовать функцию date_trunc.

gnunixon ★★★ ()
Ответ на: комментарий от comp00

Ну нет, при слиянии групп, по сути, берется одна из групп (с наибольшим числом рекордов), в нее добавляются рекорды из меньшей группы, меньшая группа дропается.

То, что я предлагаю - это почти то же самое, только у тебя сохраняется более ранняя (а не большая по размеру) из сливаемых групп. Какая разница? Всё равно ты не можешь полагаться на сохранность кода никакой группы - ты же заранее не можешь знать, что «эта группа уже достаточно большая и никогда не будет съедена».

Но дело твоё. Думаю, я больше ничем не могу быть здесь полезен.

den73 ★★★★★ ()
Ответ на: комментарий от comp00

please define «делишь на треки» не совсем понятно.

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

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

читаю из базы я либо данные за последние ххх секунд для множества устройств. либо по устройству за интервал времени [s, f), по 1+ устройств.

потом полученный жирный датасет в Java пакуется в нужное представление, и отдается уже далее json или в отчеты. тут главное не выжрать всю память.

постпроцессинг инфы для треков не делал, тк все итак работает на текущих объемах довольно долго.

drsm ()
Вы не можете добавлять комментарии в эту тему. Тема перемещена в архив.