Анализ одного алгоритма операции Join

Аннотация

Реляционный подход к организации баз данных за время своего существования пе-режил достаточно коллизий и неоднократно подвергался серьезной, и часто, необоснованной критике. Одним из положений критики было возражение против операции Join, которая считалась крайне неэффективной. Однако эта операция существовала в самых ранних системах обработки данных. В ранних публикациях она относится к классу слияния нестрого упорядоченных информационных массивов. В дальнейшем она была названа операцией слияния нестрого упорядоченных файлов. В последних работах в области машинного обучения стало активно развиваться направление, связанное с реляционными базами данных. Современные аналитические системы в производственной, финансовой, банковской, медицинской и многих других сферах базируются на больших объемах, структурированных данных, которые хранятся в, как правило, реляционных базах данных. Важное направление ускорения реализации запросов в таких базах данных заключается в использовании методов параллельной обработки данных. А так как операция Join – самая сложная из всех остальных операций, составляющих запросы, вопросам выбора для ее реализации наиболее эффективных алгоритмов, которые, в свою очередь, могут быть просто и эффективно. В статье предложен алгебраический метод формализации операции Join. На основе этого метода предложен алгоритм ее реализации с использованием специфической структуры очереди, которая называется "черпак". Приведены результаты экспериментального анализа алгоритма, подтвердившие его преимущество перед алгоритмом, который реализован в использованной системе управления базами данных Microsoft SQL Server. Приведены методы параллельной реализации предложенного алгоритма. Для этой цели использован традиционный поточный подход и подход, основанный на на архитектуре вычислительной системы с ассоциативным распределением ресурсов.