Зважій Д. В. Індексний доступ на основі суфіксних масивів для підрядкового пошуку в PostgreSQL. — Кваліфікаційна наукова праця на правах рукопису.
Дисертація на здобуття наукового ступеня доктора філософії за спеціальністю 122 «Комп'ютерні науки» (12 — Інформаційні технології). — Національний університет «Києво-Могилянська академія», Київ, 2026.
Дисертацію присвячено розробці методу індексного доступу для підрядкового пошуку, безпосередньо вбудованого в реляційну систему керування базами даних (СКБД). Підрядковий пошук, тобто знаходження усіх рядків бази даних, що містять заданий шаблон як префікс, як суфікс або як довільне входження, є фундаментальною операцією інформаційно-пошукових систем, проте у наявних реляційних СКБД він підтримується лише фрагментарно: вбудовані механізми PostgreSQL (Б-дерево з text_pattern_ops, GIN із pg_trgm, повнотекстовий пошук) охоплюють лише часткові випадки задачі, а зовнішні рішення на основі суфіксного індексу (зокрема SAES над Elasticsearch) не дають внутрішньої підтримки в самій реляційній СКБД. Це робить актуальною розробку методу індексного доступу, безпосередньо вбудованого в реляційну СКБД, який єдиною індексною структурою підтримує усі три операції підрядкового пошуку, визначений у термінах інваріантів цієї платформи та апробований у PostgreSQL.
Об'єктом дослідження є процес виконання операцій підрядкового пошуку в реляційних системах керування базами даних. Предметом дослідження є моделі, методи та програмні засоби індексного доступу на основі суфіксних структур даних, що підтримують виконання операцій підрядкового пошуку у середовищі реляційної СКБД-платформи. Метою дослідження є побудова теоретичної моделі, розробка та експериментальне обґрунтування методу індексного доступу на основі суфіксного масиву для підтримки операцій підрядкового пошуку в PostgreSQL. Метод має гарантувати логарифмічну складність пошуку O(m log N), однакову для трьох операцій (за префіксом, суфіксом та входженням), повну інтеграцію з менеджером буферів, журналюванням із записом наперед та програмним інтерфейсом методів доступу PostgreSQL і коректну взаємодію з моделлю багатоверсійного керування паралельністю на шляху читання.
Для досягнення мети виконано аналіз наявних суфіксних структур даних і механізмів PostgreSQL, побудовано теоретичну модель сторінкового суфіксного масиву в моделі блочного зовнішнього зберігання, розроблено метод індексного доступу SAindex та його програмну реалізацію в ядрі PostgreSQL, проведено порівняльне експериментальне оцінювання на реальних і синтетичних даних. Застосовано методи аналізу алгоритмів у цій моделі, системної інтеграції через Access Method API PostgreSQL і системного програмування мовою C, а також непараметричний критерій Манна–Вітні з контролем розміру ефекту через дельту Кліффа.
Наукова новизна одержаних результатів полягає в такому. Уперше розроблено теоретичну модель сторінкового суфіксного масиву в системі параметрів ⟨B, e, e_k, N⟩, яка зводить три операції підрядкового пошуку до спільного діапазонного примітива з позиційною фільтрацією. Уперше доведено межі I/O-складності методу: верхню межу пошукової фази ≤ 2⌈log₂?⌉ + O(1) блочних доступів незалежно від типу операції, лінійні нижні межі фази збирання результатів і повноту покриття множин результатів. Уперше встановлено просторову складність методу як N(e+8,125)+B байтів. Уперше запропоновано метод індексного доступу, повний цикл функціонування якого специфіковано в термінах загальних інваріантів реляційної СКБД, що уможливлює його перенесення на будь-яку СКБД, яка задовольняє ці інваріанти. Дістала подальшого розвитку інтеграція суфіксних структур у систему типів і операторів реляційної СКБД через клас операторів text_sa_ops і два нові оператори підрядкового пошуку.
Практичне значення та апробація методу. Метод апробовано програмною реалізацією SAindex (2782 рядки коду мовою C), інтегрованою в ядро PostgreSQL 18devel. На основі критерію Манна–Вітні з контролем розміру ефекту через дельту Кліффа встановлено перевагу SAindex над триграмним методом GIN_TRGM із прискоренням 6,3× у медіані для запитів за входженням і 46,5× для префіксних запитів, перевагу над спеціалізованими Б-деревами в режимах низької селективності та коректність результатів у 160 з 160 тестових випадків.
Дисертація складається з п'яти розділів: аналітичний огляд методів пошуку підрядків; експериментальна оцінка наявних механізмів підрядкового пошуку в PostgreSQL; теоретична модель індексного доступу на основі суфіксного масиву в зовнішній пам'яті; проєктування методу SAindex для PostgreSQL; опис реалізації SAindex та її експериментальної оцінки.
Ключові слова: суфіксний масив, дерева, Б-дерево, підрядковий пошук, обробка природної мови, метод індексного доступу, модель зовнішньої пам'яті, PostgreSQL, попарні порівняння, булева алгебра, прийняття рішень, оцінювання, архітектура системи, комп'ютерна система, інформаційна технологія.
