Автор Тема: СУБД и деревья  (Прочитано 68653 раз)

ilovb

  • Hero Member
  • *****
  • Сообщений: 2538
  • just another nazi test
    • Просмотр профиля
    • Oberon systems
СУБД и деревья
« : Апрель 11, 2012, 09:47:14 am »
У одынесников есть профессиональная забава под названием "разузлование".
На производственном предприятии рано или поздно возникает задача анализа затрат.
Т.е. нужен отчет, который показывает из чего сложилась себестоимость продукции в виде дерева.
Затраты обычно накапливаются в одной, или нескольких таблицах вида:
| Дата | Номенклатура | Затрата | Сумма |
Тут номенклатура выступает в качестве родителя.

В 1С конечно все несколько сложнее. Там эти данные хранятся в регистре РАУЗ.
Но специфика 1С тут мало интересна и я не буду ее освещать.

Суть задачи в следующем:
Нужно максимально эффективно по времени выполнить разузлование.
Ограничения:
Ваш код на клиенте.
СУБД находится на сервере в локальной сети 100мбит.
К СУБД можно обращаться только SQL оператором SELECT.
Рекурсивные запросы СУБД не поддерживает.
Пользователь может формировать отчет за любой период с наложением любых отборов на данные.
Отчет должен формироваться за приемлемое время на огромных объемах данных.
Можно рассмотреть вариант, когда исходные данные предварительно подготавливаются каким либо образом (время подготовки не ограничено, но это не должно в разы увеличить размер базы).

Как бы вы решали такую задачу?

p.s. Задавайте вопросы. Буду уточнять...

ilovb

  • Hero Member
  • *****
  • Сообщений: 2538
  • just another nazi test
    • Просмотр профиля
    • Oberon systems
Re: СУБД и деревья
« Ответ #1 : Апрель 11, 2012, 09:59:04 am »
Уточнение:
На сервере СУБД можно формировать временные таблицы и индексировать их.

valexey

  • Administrator
  • Hero Member
  • *****
  • Сообщений: 1990
    • Просмотр профиля
Re: СУБД и деревья
« Ответ #2 : Апрель 11, 2012, 10:25:34 am »
Из постановки задачи мне не понятно - где тут дерево?
"но сейчас, чтобы компенсировать растущую мощность компьютеров, программисты используют фреймворки"

ilovb

  • Hero Member
  • *****
  • Сообщений: 2538
  • just another nazi test
    • Просмотр профиля
    • Oberon systems
Re: СУБД и деревья
« Ответ #3 : Апрель 11, 2012, 11:02:24 am »
Вечером сделаю пример с исходными данными и деревом которое нужно получить.

Губанов Сергей Юрьевич

  • Hero Member
  • *****
  • Сообщений: 590
    • Просмотр профиля
    • Домашняя страница
Re: СУБД и деревья
« Ответ #4 : Апрель 11, 2012, 11:33:00 am »
Еще хотелось бы узнать что значит "огромные объёмы".

Допустим мы (Дата | Номенклатура | Затрата | Сумма) занумеровали целыми числами (UInt64 | UInt64 | UInt64 | UInt64).

Это 32 байта на строчку.

В одном гигабайте уберётся 33.5 миллионов таких записей.
В восьми гигабайтах -- 268 миллионов записей. Это много или мало?

ilovb

  • Hero Member
  • *****
  • Сообщений: 2538
  • just another nazi test
    • Просмотр профиля
    • Oberon systems
Re: СУБД и деревья
« Ответ #5 : Апрель 11, 2012, 12:09:35 pm »
Ну в 1С в этой таблице примерно 100 байт на строчку.
В таблице за год накапливается примерно 10 гигов (+/- 1).

p.s. Еще может разнообразная дополнительная информация тащиться из других таблиц. В результате на строчку максимум 200 байт наверно.

p.p.s Тут не очень важны конкретные циферы. Важно лишь понимать, что на клиента это все закачивать нет возможности, т.к. элементарно не хватит памяти. Т.е. выгребсти всю таблицу одним запросом и обойти ее рекурсией не прокатит... Получать запросом подчиненные записи на каждый элемент дерева очень дорого. Плюс если в таблице зацикливание, нам его нужно как-то обойти.

ilovb

  • Hero Member
  • *****
  • Сообщений: 2538
  • just another nazi test
    • Просмотр профиля
    • Oberon systems
Re: СУБД и деревья
« Ответ #6 : Апрель 11, 2012, 12:21:37 pm »
Интересны также общие соображения. Например клиент формирует отчет по всей продукции за год, но такой отчет в оперативе не поместится.... Как быть? Покрутить пальцем у виска или предложить альтернативу?

Клиенту по сути нужна комфортная работа. Чтобы, изменив период или отбор какой, не приходилось ждать по 6 часов. :)

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

Тут коренные проблемы две:
1. Нам неизвестна глубина формируемого дерева
2. В дереве могут быть циклы

ilovb

  • Hero Member
  • *****
  • Сообщений: 2538
  • just another nazi test
    • Просмотр профиля
    • Oberon systems
Re: СУБД и деревья
« Ответ #7 : Апрель 11, 2012, 12:31:58 pm »
Ну в 1С в этой таблице примерно 100 байт на строчку.

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

Губанов Сергей Юрьевич

  • Hero Member
  • *****
  • Сообщений: 590
    • Просмотр профиля
    • Домашняя страница
Re: СУБД и деревья
« Ответ #8 : Апрель 11, 2012, 01:32:27 pm »
Так записей-то в таблице сколько?

ilovb

  • Hero Member
  • *****
  • Сообщений: 2538
  • just another nazi test
    • Просмотр профиля
    • Oberon systems
Re: СУБД и деревья
« Ответ #9 : Апрель 11, 2012, 01:42:49 pm »
Примерно 10 000 000 за год

ilovb

  • Hero Member
  • *****
  • Сообщений: 2538
  • just another nazi test
    • Просмотр профиля
    • Oberon systems
Re: СУБД и деревья
« Ответ #10 : Апрель 11, 2012, 01:46:41 pm »
Вот свежие реальные данные: Формируем по 15 позициям продукции за месяц. Элементов самого нижнего уровня в дереве примерно 1 миллион

alexus

  • Гость
Re: СУБД и деревья
« Ответ #11 : Апрель 11, 2012, 01:56:12 pm »
Интересны также общие соображения. Например клиент формирует отчет по всей продукции за год, но такой отчет в оперативе не поместится.... Как быть? Покрутить пальцем у виска или предложить альтернативу?
Крутить у виска - не доблесть, значит нужна альтернатива...
(если по-хорошему, то начать следовало бы, наверное, с проектирования БД под предметную область)

Цитата: ilovb
Клиенту по сути нужна комфортная работа. Чтобы, изменив период или отбор какой, не приходилось ждать по 6 часов. :)
... и клиент прав...

Цитата: ilovb
Сразу все мы не можем закачать на клиента, значит нужно динамически подтягивать по мере необходимости.... но делать это эффективно.
Можно подкачивать, можно сформировать [временную] таблицу и потом читать из неё.

Цитата: ilovb
Тут коренные проблемы две:
1. Нам неизвестна глубина формируемого дерева
2. В дереве могут быть циклы
1. Глубина не слишком важна, если данные для отчёта формируются во временной таблице, да, и при подкачке данных на клиента... тоже не слишком проблематично. Хотя не очень понятен тезис о произвольной глубине иерархии. Неужели структура себестоимости продукции/затрат произвольна?.. Может быть поговорить с экономистами?..
2. Циклов в "дереве" быть не может, иначе это не "дерево", а циклический граф. Возможно, имелось ввиду, что на одну вложенную ветку ссылаются две других ветки-владельцы?.. Тогда это не "дерево", а сеть, орграф.

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

Какая СУБД используется?

ilovb

  • Hero Member
  • *****
  • Сообщений: 2538
  • just another nazi test
    • Просмотр профиля
    • Oberon systems
Re: СУБД и деревья
« Ответ #12 : Апрель 11, 2012, 02:09:57 pm »
...Неужели структура себестоимости продукции/затрат произвольна?.. Может быть поговорить с экономистами?...
Затраты только примерно планировать можно.
Вот сломался станок например. Мастер чинит этот станок.
Работа мастера в данном случае затрата, которая имеет свою стоимость. Эта стоимость должна войти в себестоимость полуфабриката, обрабатываемого на этом станке.
Т.е. затраты это не спецификация. Нету предопределенного состава затрат. Их можно только анализировать, и влиять на их состав управленческими рычагами. Таким образом регулируют себестоимость продукции и соответственно маржинальный доход.
Для того отчет и нужен.  :)

На остальное по порядку вечером отвечу.

Губанов Сергей Юрьевич

  • Hero Member
  • *****
  • Сообщений: 590
    • Просмотр профиля
    • Домашняя страница
Re: СУБД и деревья
« Ответ #13 : Апрель 11, 2012, 02:14:34 pm »
Примерно 10 000 000 за год
Тогда это ерунда. Перенумеруйте все используемые объекты в целые числа. В 64 разрядных целых числах таблица по 4 числа в строке из 10М записей займёт всего 300 Мб. Закачай эти 300 Мб в оперативную память клиента и со скоростью света сделай над ней любые расчёты. При выводе отчёта на лету преобразовывай обратно из целых чисел в исходные объекты.

ilovb

  • Hero Member
  • *****
  • Сообщений: 2538
  • just another nazi test
    • Просмотр профиля
    • Oberon systems
Re: СУБД и деревья
« Ответ #14 : Апрель 11, 2012, 02:33:34 pm »
Во первых: Как их нумеровать? Нам только SELECT доступен.
Во вторых: Как их обратно в объекты преобразовать? Объекты то в СУБД хранятся... Сделать к базе 10м запросов? На это месяц уйдет.