dmitgu (dmitgu) wrote,
dmitgu
dmitgu

Categories:

Базы данных - многомерные индексы, мгновенные суммы по отрезкам, кубам и т.п.

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

Итак, в бухгалтерии (да и в электронных таблицах, логистике, науке и везде) часто надо вычислить суммы (прихода, расхода и т.п.) по некоторым объектам учета от момента А до момента Б. Запускаем прогу и она бухтит и считает итог. Фактически она это делает перебором - получив нужную выборку данных и перебирая их запись за записью прибавляет очередное число к вычисляемому итогу.

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

Об индексах.

Тут надо сказать об индексах. Как вообще "внутренняя кухня" индекса обеспечивает мгновенную организацию нужного порядка? Обычно индекс имеет структуру немного модернизированного "2-3 дерева".  Расскажу об этом подробней - это нам потребуется для алгоритма мгновенного вычисления сумм. Если кто знает как там организованы узлы и их изменения - можно пропустить до следующего раздела.

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

Чтоб избежать переписывания всего списка, мы разбиваем список на "куски" по 100-200 номеров записей, например (изначально "куски" были по 2-3 записи, отсюда и название - "2-3 дерево") и ведем другой список, в котором упорядочены номера "кусков". Как только количество записей в "куске" переходит через 200 - делим его на 2 "куска" длиной в 100 и 101 номеров записей, например и заносим уже их номера (номер старого списка из 100 номеров записей и номер добавленного списка из 101 номера записей) в "суперсписок". Ясно, что и "суперсписок" может стать слишком большим, поэтому и к нему применяем стратегию 100-200 и уже физические номера "суперсписков" храним в "супер-супер-списке". И т.д. Я еще поясню ниже на практическом примере с картотекой.

О суммах в индексах

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

Вот мы ведем приход денег по кассе в картотеке, например. Она у нас разбита на дни, месяцы, годы, десятилетия и т.д. Допустим, мы обнаружили что 10 лет назад 15 апреля был неучтенный приход. Отлично - мы идем в комнату нулевых годов, залазим на стеллаж 2003 года, достаем коробку апреля, находим там 15 число и вставляем туда нашу новую карточку. Тут я описал операции со списками и суперсписками на "физическом" примере - у нас есть номера комнат, в них - номера стеллажей и т.д. и всё известно где лежит. Если нам станет мало "комнат" для десятилетий мы заведем "этажи" для веков, "здания" для тысячелетий, "поселки" для десятков тысячелетий и т.д.

Теперь вернемся к суммам. Как нам посчитать весь приход в кассу с 2 сентября 1999 г. по 12 июня 2011 года? А очень просто - нам надо изначально в картотеке записывать итог по всем периодам,  в которые попадает наша новая карточка. Тогда нам не придется пересчитывать все карточки за все время.  И тогда подсчет получается моментальным - мы сначала суммируем сумму с двери "целых" комнат (десятилетий) - тут попадает только одна комната нулевых годов. Затем мы суммируем числа с бумажки  на "стеллажах"на  целые годы, не образующие десятилетия - это 1999 г. и 2010 г. Затем суммируем надписи на "коробках" отдельных месяцев - это октябрь, ноябрь,  декабрь 1999 г. и январь, февраль, март, апрель, май 2011 г., затем добавляем наконец числа из картотеки для отдельных дней - это числа с 2 по 30 сентября 1999 г (а можно и разницу с коробки сентября 1999 г. минус 1 сентября 1999 г., кстати) и числа с 1 по 12 июня 2011г.

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

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

Лирическое отступление:

Ндя, может мелкомягким написать?  У них всякие OLAP для консолидации данных есть - но это не оперативная обработка. Внес изменение задним числом - и снова надо пересчитывать весь куб. И там надо ручками задавать агрегатирование - никакого простого включения в индексы. Вот по книге "Microsoft SQL Server 2012" Душана Петковича (ISBN 978-5-9775-0854-4) написано (Глава 21. "Введение в бизнес-аналитику", Раздел "Хранилища данных и киоски данных"):

"Разработка хранилища данных занимает в среднем 2 года и стоит 5 млн. долларов. С другой стороны, стоимость разработки киоска данных в среднем составляет 200 тыс. долларов, а разработка занимает от 3 до 5 месяцев."

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

У нас-то в России кто-нить занимается чем-то подобным? Вот Сколково всякие - они кроме как Пономареву "за лекции" башлять что еще делают? А то мы в России как опустились с передовых рубежей цивилизации (из-за "совка" с его несамостоятельностью людей и их неизбежной деградацией до скота) - так ни хрена не в тренде - копаем что-то палками-копалками, а как новые технологии создаются, какие идеи и книги выходят и что в науке  - фиг знает. Утрирую, ессно :)

А на форумах программистов друг другу мозги вышибают, оскорбляют и считают - это полезно. Если это полезно, то тем, кто начинает оскорблять других за "глупые" ошибки надо просто мозги выбивать. Вот тогда отберутся истинные джедаи, которым вместо херни на форумах давно бы уже заткнули за пояс микрософты, ораклы и т.п. Только по факту - эти дебилы только другим людям могут мозги выбивать, превращая их в таких же дебилов, как сами "вышибалы".

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

Конец лирического отступления.

Не только суммы

У мгновенной суммы записей по любому отрезку в проиндексированном порядке есть частный случай. Этот частный случай - номер записи. Притом точный и мгновенно изменяющийся при вставке новых записей перед ним. В самом деле - каждая запись может рассматриваться как единица. И сумма таких единиц от начала порядка до данной записи дает ее номер в порядке. А как мгновенно считать и изменять подобные суммы - мы знаем.

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

Многомерные индексы

Но помимо всего вышесказанного можно организовывать и многомерные индексы и мгновенно рассчитывать итоги по многомерным "кубам" и параллелепипедам.  Для простоты разберем пример обстрела квадрата 100 км на 100 км за день. Нам нужно так построить базу, чтоб сразу вычислять, сколько каких воронок в любых прямоугольниках (X1, Y1, X2, Y2) имеется. Пусть шагом будет один метр.

Основой являются квадраты метр * метр. Теперь берем полосы шириной 1 м по оси X и длиной по оси Y в 1 м, 10 м, 100 м, 1 км, 10 км, 100 км - и записываем для каждой такой полосы число воронок. Потом то же самое делаем для полос шириной 10 м по оси X, затем для полос шириной 100 м по оси X и т.д. И у нас получится такой "базовый набор" прямоугольников, что любой другой прямоугольник можно представить как сумму от одного до 18*18 "больших" одинаковых прямоугольников из "базового набора" лежащих вплотную внутри нашего прямоугольника + оставшаяся "рамка".  Притом внутри рамки вдоль оси Х и вдоль оси Y мы можем найти такие же по своим Y и X-размерам соответственно прямоугольники, прилежащие стенка-к-стенке к этим большим прямоугольникам. Притом они будут в 10 раз меньше по оси Y и X чем "большие".  Лишь по углам нашего прямоугольника остались не разобранные прямоугольники - но и эти прямоугольники попадают в "базовую сетку" и содержат не больше "базовых прямоугольников", чем найденные на предыдущем шаге. Поэтому для подсчета числа воронок в нашем 2-мерном случае нам придется просуммировать порядка (Ln N)^2 чисел. Где N - число учитываемых объектов по одному "измерению" (хотя из-за логарифма нет принципиальной разницы - по одному измерению или по 2м, ибо даже N^2 даст лишь коэффициент 2 после применения логарифма).

И при появлении новой воронки придется вносить примерно столько же изменений - порядка (Ln N)^2. Действительно - полос шириной в 1 м по оси Х надо изменить 6 штук (1 + lg 100тыс. м), а кроме полос в 1 м шириной по X есть еще и шириной 10 м и т.д. - еще 5 шт. Вот и получается 6*6 для одного изменения. Хотя это завышенная оценка - среди этих прямоугольников около половины повторяется.

Это все означает, кстати, что можно делать и быстрые многомерные индексы для быстрой выборки из многомерных кубов (параллелепипедов, точнее). Хотя при этом придется и данных записывать на диск больше чем без индекса - примерно в (ln N)^M, где M - число измерений. Степень - это круто, ессно, но поскольку это степень от логарифма, то для больших чисел N это меньше, чем N^P где P - любое число, большее 1.

Лирическое отступление:

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

Конец лирического отступления.

Продолжение следует...

Надеюсь.

Версия 1.00 (последняя на сегодня). Исходные тексты подверсий версии 1 хранятся в каментах к:
http://dmitgu.livejournal.com/2024.html?thread=134632#t134632
Tags: ЖЖвЖЖ бухучет, ЖЖвЖЖ программирование, ИТ (информ. технологии), Мои алгоритмы
Subscribe

  • Post a new comment

    Error

    default userpic

    Your reply will be screened

    Your IP address will be recorded 

    When you submit the form an invisible reCAPTCHA check will be performed.
    You must follow the Privacy Policy and Google Terms of use.
  • 2 comments