Программирование

Серия статей по разным поводам на обще-программерские темы.

Индексирование в MUMPS

Серия статей из книги "MUMPS СУБД" о индексах в MUMPS системах, их возможностях, алгоритмах и структурах индексов.

MUMPS: Многоиндексная выборка (zig-zag)

Многоиндексной выборкой, иначе называемой шаговой или зиг-загом, называется выборки идентификаторов записей по нескольким индексным структурам одновременно. Также часто встречается название zig-zag ordered scan. Принципиальным моментом является слово ordered, или упорядочение искомых идентификаторов. Применяется для выборки из двух или более индексов.

MUMPS: Индексация уникального атрибута

Одной из интереснейших и спорных тем в индексации является тема индексации уникального атрибута. Индексы в данном случае используются по меньшей мере в двух различных задачах:

• Для поиска нужной записи по заданному значению атрибута.
• Для поддержания условия уникальности значения атрибута среди всех имеющихся записей.

MUMPS: Операции с древовидными индексами

К операциям с древовидными индексами относятся операции, использующие деревья с индексами и реализующие над ними теоретико - множественные операции. К таким операциям относят логические операции над множествами: OR (ИЛИ), AND (И), и другие. При этом деревья используются для хранения множеств - операндов и результата операции.

MUMPS: Сортировка по индексу

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

MUMPS: Простой индекс

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

MUMPS: Выборки по индексу

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

MUMPS: Индекс поиска по фрагменту

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

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

MUMPS: Совмещение древовидных и битовых индексов

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

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

MUMPS: Массовое перестроение индексов

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

MUMPS: Индексация длинных атрибутов

В реализации любых М систем в целях повышения эффективности реализаций вводятся ограничения на длину индекса. Ограничения такого же характера присутствуют и в других, не-М реализациях СУБД. В распространенных реализациях М длина индексов включая имя переменной ограничена 255 байт.

MUMPS: Индексация для шаблона (like)

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

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

MUMPS: Индексация данных

Термин индекс здесь и далее используется строго в целях обозначения дополнительных поисковых или оптимизирующих структур. Основным языком примеров выбрано стандартное подмножество языка МUMPS. Но, хотя по возможности применяется страндартный синтаксис, в некоторых исключительных случаях для большей читаемости применяются Cache Object Script и MiniM Database Server - расширения. Их применение ограничено и допускает альтернативную замену на эквивалентные выражения в иных диалектах МUMPS. Применение битмап индексов ограничено теми MUMPS системами, которые поддерживают расширенные $BIT функции.

MUMPS: Дифференциальное индексирование

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

MUMPS: Межтабличный индекс

Межтабличным индексом называется индексная структура, объединяющая в себе данные не для одного, а для двух или более логических наборов данных. Записи в межтабличном индексе перестраиваются при добавлении, изменении и удалении записей в наборах записей, данные из которых входят в этот индекс. Основным назначением межтабличного индекса является сокращение операций соединения таблиц.

Cache: Смотрим план SQL запроса

В Cache5 появилась утилита показа плана выполнения запроса ShowPlan^%apiSQL.

MUMPS: Покрывающий индекс

Покрывающим индексом (cover index) называется индекс, который может быть использован для нескольких задач выборки данных, в том числе для тех, для которых он изначально не планировался. Название отражает не вид структуры, а различные возможности ее применения.

MUMPS: Индекс с условием на вставку

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

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

MUMPS: Составной индекс

Если простой индекс отображает значение одного атрибута на идентификатор или набор идентификаторов строк, то составной индекс отображает совокупность значений двух или более атрибутов на идентификатор или набор идентификаторов строк.

MUMPS: Нормирование значений в индексах

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

Ключевой операцией для использования индекса является обращение к искомому значению в глобал или локаль, и поиск выполняет непосредственно СУБД, поскольку значения индексов в MUMPS хранятся сортированно.

MUMPS: Индекс на вычисляемый атрибут

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

MUMPS: Битслайс индекс (bitslice)

Резаный битовый индекс представляет собой совокупность структур, отображающих фрагменты значений атрибутов на набор идентификаторов строк данных. Структурно аналогичен битовому индексу (bitmap), но представляет собой N битовых индексов, работающих для всех значений атрибутов. Индексации подвергаются только числовые атрибуты либо те, которые могут быть приведены к числовому виду. Значение N зависит от типа выбранного атрибута.

В карту входят отдельные карты по каждому биту значения атрибута. В примере рассмотрим тип натуральное число. Само число в нашем примере рассматривается как 32-битное без знака. Берутся отдельные биты числа и по этим битам строится 32 отдельных битовых индекса.

MUMPS: Операции с битовыми индексами

Здесь поведем речь о реализации теоретико-множественных операций над битовыми индексами.

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

MUMPS: Битмап индекс (bitmap)

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

Эклиптики звезд и галактик и темная сила

На это размышление натолкнул факт, что наши планеты вокруг нашей звезды летают по орбитам не просто так, а в так называемой плоскости эклиптики. В общем и целом к эклиптике относится движение в плоскости или очень близко к плоскости орбиты Земли. Относительно большими отклонениями плоскостей от этой условно общей плоскости обладают Меркурий и Плутон, у них наклоны плоскостей орбиты соответственно примерно 7 и примерно 20 градусов. И эти величины, относительно небольшие, выглядят заметными. Факт наблюдается в том, что, хотя по теории Ньютона наши планеты могут летать по совершенно любым плоскостям, ибо единственная значимая сила для них это сила гравитации от Солнца, тем не менее в действительности планеты летают в некоей плоскости или в некотором ограниченном коридоре.

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

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

Еще более интересно становится если увидеть как движется и само Солнце в Галактике.

И вот так выглядит условная анимация движения Солнца в Галактике:

MUMPS: Память и сборка мусора

Одним из важных практических вопросов применения MUMPS систем является отношение к памяти, принятое в системах такого класса и исторически сложившиеся традиции или поведение систем, наиболее ожидаемое разработчиками.

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

MUMPS: Функция $BIT

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

Битовый индекс представляет собой совокупность сегментов, каждый из которых это последовательность байт, и каждый бит в ней значим, может иметь значение либо "объект с идентификатором, равным номеру бита, существует" (1), либо "не существует" (0). Кроме того, применяется правило умолчания, что если бит находится за пределами реально физически существующих байт, либо строка байт вообще не существует, то логически для битовых операций это эквивалентно последовательности нулей.

В техническом отношении битовые операции могут быть добавлены к MUMPS системе внешними по отношению к ней функциями в динамической библиотеке. Автору довелось участвовать в проектах, где использовался именно такой вариант. Разработки блестяще работали в режиме OLAP и имели некоторые непреодолимые недочеты в режиме OLTP.

MUMPS: Интерпретатор

Как уже было описано в разделе косвенности, язык MUMPS содержит определения синтаксических конструкций, не позволяющих выполнить систему выполнения кода по схеме традиционных компиляторов с одним только неизменяемым исполняемым кодом. Этому препятствуют и операции косвенности, и команда XECUTE.

Все имеющиеся реализации MUMPS систем в той или иной мере являются интерпретаторами. Это либо интерпретаторы интерпретирующего типа или интерпретаторы компилирующего типа или комбинированные.

MUMPS: О модулях

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

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

Routine Editor for Intersystems Cache / Windows / Linux / MacOSX

MUMPS project MiniM Database Server have builtin MiniM Routine Editor. Some time ago this tool has been ported to working on with Intersystems Cache database.

MUMPS + JSON

How to get data in JSON format from the MUMPS?

Обратимость времени

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

Положим, что есть формула движения тела x=f(t).

По ней, подставляя различные значения t, можем определить соответствующие значения x. Необычность ситуации здесь состоит в том, что мы можем подставить в эту формулу значения времени t отстоящие в прошлом.

Почему векторное произведение - это площадь?

У формулы векторного произведения, построенного на двух 3-мерных векторах, есть две формулы его величины: 1) формула на словах определяющая направление результата и описывающая величину в виде произведения модулей векторов на синус угла между ними и 2) формула задающая значения каждой из компонент результата на основе компонент исходных векторов.

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