Есть склад, на него приходит товары, с него уходят товары. Храним в базе: момент времени, товар, количество расхода/прихода.

Нужно быстро получать количество товара на любой момент времени. Чтобы посчитать количество нужно "сложить" все движения (нарастающим) до этого момента времени. Имеется запрос, который суммирует движения, но работает долго, т.к. приходится суммировать все записи о движении (записей очень-очень много).

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

Вроде, задача достаточно типовая. Например, в 1С решается с помощью "регистров накоплений" — структуры, созданной специально для этого.

Как обычно решаются такие задачи?
Существует ли поддержка со стороны БД?
Существуют ли библиотеки, которые реализуют такое "промежуточные" результаты? (любой язык)

Здравствуйте, Буравчик, Вы писали:


Б>Для ускорения можно (нужно?) хранить промежуточные результаты (например, на конец месяцы/недели/дня и т.п.). Но...
да, нужно иметь промежуточные предрассчитанные результаты, других вариантов нет.
остатки на произвольную дату считаются так — берется ближайший предрассчитанный итог и по документам от него до нужного момента считаются обороты и результаты агрегируются.
при грамотном подборе периода хранения предрасчитанных итогов, посчитать обороты в интервале обычно довольно быстро.


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


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


Б>Вроде, задача достаточно типовая. Например, в 1С решается с помощью "регистров накоплений" — структуры, созданной специально для этого.
по сути и это и есть предрассчитанные остатки/итоги.


Б>Как обычно решаются такие задачи?
Б>Существует ли поддержка со стороны БД?
в БД есть материализованные вью, возможно их можно использовать для поддержки актуальности промежуточных итогов.
конкретно их не использовал, у нас с уровня приложения производился пересчет при корректировках задним числом.

Здравствуйте, MadHuman, Вы писали:

MH>...

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

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

Можно еще помечать промежуточные итоги как недействительные, а когда они понадобятся, то досчитывать их. Или отдельный сервис, который периодически пересчитывает промежуточные итоги.

Но тогда усложняется логика получения итоговых значений — дополнительно придется учитывать недействительные итоги.

MH>в БД есть материализованные вью, возможно их можно использовать для поддержки актуальности промежуточных итогов.
MH>конкретно их не использовал, у нас с уровня приложения производился пересчет при корректировках задним числом.

А при движениях задним числом — сразу пересчитывали при добавлении движения, или отдельный сервис периодически?

Здравствуйте, Буравчик, Вы писали:

Б>Есть склад, на него приходит товары, с него уходят товары. Храним в базе: момент времени, товар, количество расхода/прихода.

Б>Нужно быстро получать количество товара на любой момент времени. Чтобы посчитать количество нужно "сложить" все движения (нарастающим) до этого момента времени. Имеется запрос, который суммирует движения, но работает долго, т.к. приходится суммировать все записи о движении (записей очень-очень много).

Б>Для ускорения можно (нужно?) хранить промежуточные результаты (например, на конец месяцы/недели/дня и т.п.). Но...
Б>Во-первых эти промежуточные результаты нужно обновлять при каждом приходе/расходе.
Б>Во-вторых, движение товаров может быть введено задним числом. Придется пересчитывать промежуточные итоги сразу за несколько периодов (тоже долго).

Б>Вроде, задача достаточно типовая. Например, в 1С решается с помощью "регистров накоплений" — структуры, созданной специально для этого.

Б>Как обычно решаются такие задачи?
Б>Существует ли поддержка со стороны БД?
Б>Существуют ли библиотеки, которые реализуют такое "промежуточные" результаты? (любой язык)

В sql server можно триггеры использовать для опережающего подсчета количества. А так правильно сказали, что какие данные вам нужны те и сразу рассчитывайте. Удобно это будет делать если бизнес-логика будет представлена domain model.

Здравствуйте, Буравчик, Вы писали:

Б>Для ускорения можно (нужно?) хранить промежуточные результаты (например, на конец месяцы/недели/дня и т.п.). Но...
Б>Во-первых эти промежуточные результаты нужно обновлять при каждом приходе/расходе.

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

Б>Во-вторых, движение товаров может быть введено задним числом. Придется пересчитывать промежуточные итоги сразу за несколько периодов (тоже долго).

Непонятно, почему долго. Стандартные параметры (сумма, количество) не должно быть долго. Если у тебя по годам и по дням, например, тебе при изменении надо пересчитать две записи. Причём даже не пересчитать, а сделать простую операцию (для суммы -oldValue+newValue). Ну и эти задние числа обычно исключение, а не правило.

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

Б>Во-первых эти промежуточные результаты нужно обновлять при каждом приходе/расходе.
Б>Во-вторых, движение товаров может быть введено задним числом. Придется пересчитывать промежуточные итоги сразу за несколько периодов (тоже долго).
Зачем весь период пересчитывать? Вроде надо только учесть ещё не учтённые факты?

Здравствуйте, Буравчик, Вы писали:

Б>Думал, где-то это уже обобщили
обобщили в специализированных платформах-фрэймворках типа 1С и подобных.


Б>А при движениях задним числом — сразу пересчитывали при добавлении движения, или отдельный сервис периодически?
сразу, так как иначе все предрасчитанные итоги после момента корректировки становятся недействительны.
с учетом того что перерасчет по ограниченному кол-ву позиций, то это работало довольно шустро.
А для жирных документов с большим кол-вом позиций (когда это реально даст проблемы с перфомансом), можно корректировку делать отложенно, то есть
шедулить на ночное время например проводку такого документа.

Здравствуйте, vsb, Вы писали:

Б>>Для ускорения можно (нужно?) хранить промежуточные результаты (например, на конец месяцы/недели/дня и т.п.). Но...
Б>>Во-первых эти промежуточные результаты нужно обновлять при каждом приходе/расходе.

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

Да, согласен (выше написал про это). Можно пересчитывать каждый день, а в течение дня считать в лоб, будет не очень долго.

Б>>Во-вторых, движение товаров может быть введено задним числом. Придется пересчитывать промежуточные итоги сразу за несколько периодов (тоже долго).

vsb>Непонятно, почему долго. Стандартные параметры (сумма, количество) не должно быть долго. Если у тебя по годам и по дням, например, тебе при изменении надо пересчитать две записи. Причём даже не пересчитать, а сделать простую операцию (для суммы -oldValue+newValue). Ну и эти задние числа обычно исключение, а не правило.

К сожалению, в моем случае так нельзя. В реальной задаче требуется не только обработать каждую записаь, но и обработать последовательность записей. Простой пример — найти максимальное время между двумя движениями в течение периода. Есть и более сложные показатели. Здесь обычным -oldValue+newValue не обойтись, проще пересчитать заново. Но при этом за год можно считать исходя из данных за месяцы, а за месяцы — исходя из недельных данных и т.д.

Здравствуйте, MadHuman, Вы писали:

MH>Здравствуйте, Буравчик, Вы писали:

Б>>Думал, где-то это уже обобщили
MH>обобщили в специализированных платформах-фрэймворках типа 1С и подобных.

Ищу названия конкретных библиотек (java/c#/python/ruby/php).
С надеждой, что в них реализована абстрактная логика работы с промежуточными значениями. Чтобы не делать велосипед.

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

Да, так и буду делать.

Здравствуйте, Osaka, Вы писали:

O>Зачем весь период пересчитывать? Вроде надо только учесть ещё не учтённые факты?

Потому что агрегация на самом деле сложнее, чем просто сложение. Выше написал.

Здравствуйте, Буравчик, Вы писали:

Б>Ищу названия конкретных библиотек (java/c#/python/ruby/php).
Б>С надеждой, что в них реализована абстрактная логика работы с промежуточными значениями. Чтобы не делать велосипед.

Также ищу статьи на эту тему и/или ключевые слова для поиска

Здравствуйте, Буравчик, Вы писали:

Б>Как обычно решаются такие задачи?

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

Здравствуйте, Буравчик, Вы писали:

Б>Есть склад, на него приходит товары, с него уходят товары. Храним в базе: момент времени, товар, количество расхода/прихода.

Б>Как обычно решаются такие задачи?
Б>Существует ли поддержка со стороны БД?
Б>Существуют ли библиотеки, которые реализуют такое "промежуточные" результаты? (любой язык)

Периодически агрегировать. Может быть раз в день, может быть раз в час, да хоть раз в минуту. может быть по запросу, или же ленивая агрегация в некоторых случаях. Хранить агрегированные значения в отдельной таблице по времени агрегирования. Текущее значение подсчитывать как самое новое агрегированное + сумма или что у вас там накопилось с этого момента. Если база спроектирована нормально, и агрегирование делается относительно часто, то такая сумма должна быстро считаться. Если нужен пересчет задним числом, то как тут уже предложили выше, пойдет древовидная структура.
Агрегация дельт за каждый день, отдельная агрегация их же за месяц, за год и т.п. Тогда при пересчете придется пересчитывать только одну небольшую подветку этого дерева.

Здравствуйте, Буравчик, Вы писали:
Б>Как обычно решаются такие задачи?
Б>Существует ли поддержка со стороны БД?
Б>Существуют ли библиотеки, которые реализуют такое "промежуточные" результаты? (любой язык)
Вообще, для быстрого получения агрегированных данных применяют OLAP решения. Типичный OLAP-индекс — это как раз и есть предрассчитанные агрегаты по типичным осям агрегирования.
Если есть возможность выбора технологий, то я бы рекомендовал гуглить по ключевому слову OLAP + особенности, характерные именно для вашей задачи.
Если у вас уже есть какая-то технология, то можно навелосипедить нужное решение и на ней. Это может оказаться дешевле, чем привинчивать OLAP к вашему OLTP решению, и заморачиваться с синхронизацией, двойным подключением клиента к СУБД, и прочими сложностями.

Но для начала нужно убедиться, что штатной скорости реально не хватает.
Ну, например, пусть у вас движения пишутся вот в таком виде:

create table Movements(
  moveDate datetime primary key not null, -- обеспечиваем монотонный ключ
  partId int not null foreign key references Parts(Id),
  quantity numeric(18,4)
)

Если я ничего не путаю, то решением исходной задачи является вот такой view (SQL Server 2012+):

create view RollingMovements as 
  select moveDate, partId, quantity, 
    SUM(quantity) OVER (PARTITION BY partId order by moveDate rows between unbounded preceding and current row) as runningQuantity 
  from Movements

Убеждаемся, что у нас есть индекс по (partId, moveDate), и проверяем на боевых данных план и общий тайминг запроса типа такого:

select top 1 * from RollingMovements 
  where partID = @partId and moveDate <= @date

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

Здравствуйте, Sinclair, Вы писали:

S>Вообще, для быстрого получения агрегированных данных применяют OLAP решения. Типичный OLAP-индекс — это как раз и есть предрассчитанные агрегаты по типичным осям агрегирования.
S>Если есть возможность выбора технологий, то я бы рекомендовал гуглить по ключевому слову OLAP + особенности, характерные именно для вашей задачи.
S>Если у вас уже есть какая-то технология, то можно навелосипедить нужное решение и на ней. Это может оказаться дешевле, чем привинчивать OLAP к вашему OLTP решению, и заморачиваться с синхронизацией, двойным подключением клиента к СУБД, и прочими сложностями.

По ощущениям, OLAP заточены под огромные массивы данных, не работают в realtime (на лету), и почти нет решений open source.
Внимательное, конечно, посмотрю, спасибо, но скорее всего сделаю велосипедик (одна табличка там всего, на которую можно завязать кучу запросов).

S>Но для начала нужно убедиться, что штатной скорости реально не хватает.

Сейчас скорости хватает, но тенденция такова, что хватать не будет.

S>Ну, например, пусть у вас движения пишутся вот в таком виде:

Предложенные решения с тюнингом БД, как уже писал ранее, не подходят. Так как кроме запроса БД требуется хитрая обработка, которую запросами SQL не выразишь.
И эта обработка занимает времени даже больше, чем непосредственно выборка из БД.

Здравствуйте, Буравчик, Вы писали:

Б>Здравствуйте, Sinclair, Вы писали:

S>>Вообще, для быстрого получения агрегированных данных применяют OLAP решения. Типичный OLAP-индекс — это как раз и есть предрассчитанные агрегаты по типичным осям агрегирования.
S>>Если есть возможность выбора технологий, то я бы рекомендовал гуглить по ключевому слову OLAP + особенности, характерные именно для вашей задачи.
S>>Если у вас уже есть какая-то технология, то можно навелосипедить нужное решение и на ней. Это может оказаться дешевле, чем привинчивать OLAP к вашему OLTP решению, и заморачиваться с синхронизацией, двойным подключением клиента к СУБД, и прочими сложностями.

Б>По ощущениям, OLAP заточены под огромные массивы данных, не работают в realtime (на лету), и почти нет решений open source.
Б>Внимательное, конечно, посмотрю, спасибо, но скорее всего сделаю велосипедик (одна табличка там всего, на которую можно завязать кучу запросов).

Ну...Есть разные NoSQL базы которые не называют себя OLAP но по факту делают что-то очень похожее. Различные column-oriented как HBase например.
Они как раз по большей части open source, в принципе неплохой вариант для чистого агрегирования. Только могут возникнуть проблемы с распределенными транзакциями, нужны дополнительные телодвижения чтобы синхронизировать две базы. И это все конечно же не realtime (realtime агрегация и не требуется, а после агрегирования данные становятся read-only фактически, за исключением случая когда нужно что-то пересчитывать за прошлые периоды, но тут без знания подробностей задачи что-то конкретное сложно посоветовать).

Здравствуйте, Буравчик, Вы писали:

Б>По ощущениям, OLAP заточены под огромные массивы данных, не работают в realtime (на лету), и почти нет решений open source.

как и говорилось, периодически делается агрегация данных
из свободного есть Pentaho

Здравствуйте, Буравчик, Вы писали:

Б>Предложенные решения с тюнингом БД, как уже писал ранее, не подходят. Так как кроме запроса БД требуется хитрая обработка, которую запросами SQL не выразишь.
Б>И эта обработка занимает времени даже больше, чем непосредственно выборка из БД.
А в чём хитрость обработки? Максимальное время между двумя движениями тривиально выражается через self-join, а потом у нас опять тривиальная агрегация с функцией MAX, которая коммутативна.

Здравствуйте, Sinclair, Вы писали:

S>А в чём хитрость обработки? Максимальное время между двумя движениями тривиально выражается через self-join, а потом у нас опять тривиальная агрегация с функцией MAX, которая коммутативна.

В реальной задаче — это не движения товара, а сообщения от датчиков. Задачу про движения товара задавал, так как считал, что при работе со складами эти задачи решены, чтобы перенять опыт оттуда (плюс знал готовый пример — реестры накопления в 1С).

Про сложность обработки: Перед тем, как посчитать агрегированные значения, нужно привести в порядок последовательность сообщений (какие-то сообщения проигнорировать, какие-то "передвинуть"). На обработанной последовательности сообщений считаются агрегаты — суммы, максимумы, среднее и т.п. Плюс сообщения бывают разного типа (берутся из несколько табличек). Плюс имеются правила определения статуса устройства, который зависит от информации из сообщений и значений агрегатов. Плюс этих статусов несколько.

Здравствуйте, Буравчик, Вы писали:
Б>В реальной задаче — это не движения товара, а сообщения от датчиков. Задачу про движения товара задавал, так как считал, что при работе со складами эти задачи решены, чтобы перенять опыт оттуда (плюс знал готовый пример — реестры накопления в 1С).
Именно так. При работе со складами эти задачи решены через OLAP.

Б>Про сложность обработки: Перед тем, как посчитать агрегированные значения, нужно привести в порядок последовательность сообщений (какие-то сообщения проигнорировать, какие-то "передвинуть").
Это делается однократно, до агрегации.
Б>На обработанной последовательности сообщений считаются агрегаты — суммы, максимумы, среднее и т.п.
Пока ничего военного. Любая методика пре-агрегации работает на ура — среднее только надо заменить на sum и count.
Б>Плюс сообщения бывают разного типа (берутся из несколько табличек).
Эмм, select union all?
Б>Плюс имеются правила определения статуса устройства, который зависит от информации из сообщений и значений агрегатов. Плюс этих статусов несколько.
Ну, вот это может быть и интересно.
В целом, я бы копал в сторону определения набора view, а затем материализации некоторых из них. Там есть свои ограничения, но, опять же, ничего военного.
Есть нюансы с внесением записей "задним числом", но непонятно, есть ли оно вообще — или всё делается в более-менее реальном времени, на этапе "передвижки" и "игнорирования" сообщений.