122 Комп’ютерні науки

Permanent URI for this collection

https://ekmair.ukma.edu.ua/handle/123456789/35525
Освітньо-наукова програма: Комп’ютерні науки

Browse

Browsing 122 Комп’ютерні науки by Subject "computer system"

Now showing 1 - 1 of 1
  • Thumbnail Image
    Item
    Індексний доступ на основі суфіксних масивів для підрядкового пошуку в PostgreSQL : дисертація на здобуття наукового ступеня доктора філософії
    (2026) Зважій, Дмитро; Глибовець, Андрій
    Дисертація на здобуття наукового ступеня доктора філософії за спеціальністю 122 "Комп’ютерні науки" (12 — Інформаційні технології). — Національний університет "Києво-Могилянська академія", Київ, 2026. Дисертацію присвячено розробці методу індексного доступу для підрядкового пошуку, безпосередньо вбудованого в реляційну систему керування базами даних (СКБД). Підрядковий пошук, тобто знаходження усіх рядків бази даних, що містять заданий шаблон як префікс, як суфікс або як довільне входження, є фундаментальною операцією інформаційно-пошукових систем, проте у наявних реляційних СКБД він підтримується лише фрагментарно: вбудовані механізми PostgreSQL (Б-дерево з text_pattern_ops, GIN із pg_trgm, повнотекстовий пошук) охоплюють лише часткові випадки задачі, а зовнішні рішення на основі суфіксного індексу (зокрема SAES над Elasticsearch) не дають внутрішньої підтримки в самій реляційній СКБД. Це робить актуальною розробку методу індексного доступу, безпосередньо вбудованого в реляційну СКБД, який єдиною індексною структурою підтримує усі три операції підрядкового пошуку, визначений у термінах інваріантів цієї платформи та апробований у PostgreSQL. Об’єктом дослідження є процес виконання операцій підрядкового пошуку в реляційних системах керування базами даних. Предметом дослідження є моделі, методи та програмні засоби індексного доступу на основі суфіксних структур даних, що підтримують виконання операцій підрядкового пошуку у середовищі реляційної СКБД-платформи. Метою дослідження є побудова теоретичної моделі, розробка та експериментальне обґрунтування методу індексного доступу на основі суфіксного масиву для підтримки операцій підрядкового пошуку в PostgreSQL. Метод має гарантувати логарифмічну складність пошуку O(mlogN), однакову для трьох операцій (за префіксом, суфіксом та входженням), повну інтеграцію з менеджером буферів, журналюванням із записом наперед та програмним інтерфейсом методів доступу PostgreSQL і коректну взаємодію з моделлю багатоверсійного керування паралельністю на шляху читання. Для досягнення мети поставлено такі завдання дослідження: формально визначити операції підрядкового пошуку та їхню ієрархію складності; проаналізувати суфіксні структури даних як теоретичну основу методу; обґрунтувати вибір PostgreSQL як платформи апробації методу; виміряти продуктивність наявних механізмів PostgreSQL та оцінити розрив з теоретичними можливостями; побудувати теоретичну модель сторінкового суфіксного масиву у моделі блочного зовнішнього зберігання та довести межі I/O- і просторової складності методу інваріан- тно щодо конкретної СКБД-платформи; проаналізувати архітектуру PostgreSQL як систему обмежень для проєктування методу; обґрунтувати вибір суфіксного масиву порівняно з суфіксним деревом з урахуванням цих обмежень; розробити структуру сторінок, алгоритми побудови та пошуку методу; розробити програмну реалізацію SAindex безпосередньо в ядрі PostgreSQL; провести порівняльне експериментальне оцінювання на реальних та синтетичних даних. Для вирішення цих завдань застосовано теоретичні методи аналізу алгоритмів у моделі блочного зовнішнього зберігання з параметрами ⟨B, e, ek,N⟩ (побудова теоретичної моделі сторінкового суфіксного масиву та доведення меж I/O-складності методу); методи системної інтеграції через інтерфейс Access Method API PostgreSQL та системного програмування мовою C (розробка програмної реалізації SAindex); непараметричні методи статистичного аналізу, а саме критерій Манна–Вітні з контролем розміру ефекту через дельту Кліффа, якими виконано емпіричну верифікацію переваги на трьох наборах даних (GeoNames, synthetic_uniform, synthetic_zipf) на п’яти масштабах від 100 000 до 5 000 000 рядків, по 30 запусків на шаблон. Наукова новизна одержаних результатів полягає в такому. Уперше розроблено теоретичну модель сторінкового суфіксного масиву, сумісного з інваріантами реляційної СКБД-платформи, у системі параметрів ⟨B, e, ek,N⟩, яка зводить три операції підрядкового пошуку (префіксну, суфіксну та за входженням) до спільного діапазонного примітива з позиційною фільтрацією та обґрунтовує розподіл даних за схемою доступу через лему про розділення. Уперше доведено межі I/O-складності методу: верхню межу пошукової фази ≤ 2⌈log2 P⌉ + O(1) блочних доступів незалежно від типу операції та довжини шаблону, лінійні нижні межі фази збирання результатів для трьох стратегій та повноту покриття множин результатів, інваріантні щодо конкретної реляційної СКБД-платформи. Уперше встановлено просторову складність методу як N(e + 8,125) + B байтів, строго лінійну за обсягом колекції та незалежну від характеру даних, з кількісним обґрунтуванням коефіцієнта просторової надлишковості відносно вихідних даних. Уперше запропоновано метод індексного доступу на основі сторінкового су- фіксного масиву, повний цикл функціонування якого (зберігання, побудова, пошук, збирання результатів) специфіковано не в термінах PostgreSQL, а в термінах загальних інваріантів реляційної СКБД (буферний менеджер, журналювання із записом наперед, модель багатоверсійного керування паралельністю, інтерфейс методів доступу). Така платформо-незалежна специфікація уможливлює перенесення методу на будь-яку реляційну СКБД, що задовольняє ці інваріанти. Дістала подальшого розвитку інтеграція суфіксних структур у систему ти- пів та операторів реляційної СКБД через клас операторів text_sa_ops та два нові оператори: @> для пошуку за входженням (раніше доступний у PostgreSQL лише для контейнерних типів, але не для пари (text, text)) і ~@ для суфіксного пошуку, що є повністю новим оператором у системному каталозі; префіксний пошук інтегровано з вбудованим ^@. На відміну від евристичного розпізнавання планувальником шаблонів LIKE, запропоноване розширення дозволяє виразити тип підрядкового запиту прямо у системному каталозі. Практичне значення одержаних результатів та апробація методу. Запропонований метод апробовано шляхом розробки програмної реалізації SAindex обсягом 2782 рядки коду мовою C, інтегрованої безпосередньо в ядро PostgreSQL 18devel з відкритим вихідним кодом. Реалізація задовольняє вимоги стандартного протоколу побудови індексів та виконує повне WAL-журналювання операцій модифікації індексних сторінок; повноцінна підтримка інкрементальних модифікацій (aminsert, ambulkdelete, amvacuumcleanup) є напрямком подальшої роботи. На основі непараметричного критерію Манна–Вітні з контролем розміру ефекту через дельту Кліффа встановлено перевагу SAindex над триграмним методом GIN_TRGM з прискоренням 6,3× у медіані за шаблонами для запитів за входженням та 46,5× для префіксних запитів, перевагу над спеціалізованими Б-деревами у режимах низької селективності та рівнозначну продуктивність з BTREE_REV у режимі автоматичного вибору плану оптимізатором на масштабі 5M рядків. Достовірність експериментальних результатів підтверджено обов’язковою перевіркою коректності (160 з 160 тестових випадків відповідності множин рядків, повернутих SAindex, результатам послідовного сканування) та статистичною значущістю на основі 2188 тестів попарного порівняння методів. Дисертаційна робота складається з п’яти розділів. У першому розділі проведено аналітичний огляд методів пошуку підрядків та теоретичних основ суфіксних структур даних. Формалізовано три цільові операції підрядкового пошуку (префіксний, суфіксний пошук та пошук за входженням); розглянуто фундаментальні суфіксні структури (суфіксне дерево, суфіксний ма- сив, масив LCP, FM-індекс) та сучасні алгоритми їхньої побудови. Проаналізовано наявні механізми підрядкового пошуку в PostgreSQL та зовнішні рішення на основі суфіксного індексу; виявлено принциповий розрив між теоретичними можливостями суфіксних структур та їхньою реалізацією в реляційних СКБД, що обґрунтувало задачу дослідження. У другому розділі виконано експериментальну оцінку наявних механізмів підрядкового пошуку: міжсистемне порівняння PostgreSQL, Elasticsearch, MySQL та ClickHouse з еталонною реалізацією суфіксного дерева, деталізований бенчмарк механізмів PostgreSQL з виявленням характеру їхніх обмежень. Побудовано спрощену модель вартості пошуку у сторінковому суфіксному масиві в параметрах ⟨B, e,N, L,P⟩ та кількісно оцінено очікувану перевагу. У третьому розділі побудовано теоретичну модель індексного доступу на основі суфіксного масиву у зовнішній пам’яті в параметрах ⟨B, e, ek,N⟩, незалежну від конкретної СКБД-платформи. Доведено зведення трьох операцій підрядкового пошуку до єдиного діапазонного примітива з позиційною фільтрацією, межі I/O-складності пошукової та збиральної фаз, повноту покриття множин результатів і просторову складність N(e + 8,125) + B байтів. У четвертому розділі викладено метод індексного доступу на основі сторінкового суфіксного масиву для PostgreSQL. Архітектуру PostgreSQL подано як систему шести інваріантів C1–C6, що формують простір допустимих рішень; систематично оцінено шість вбудованих методів індексного доступу і обґрунтовано непридатність кожного як носія суфіксної структури. На цій основі запропоновано п’ятисекційну структуру зберігання на диску, формат індексного запису з матеріалізованим префіксом ключа, п’ятифазний конвеєр побудови через tuplesort, клас операторів text_sa_ops з трьома стратегіями пошуку та три стратегії збирання ідентифікаторів кортежів. Доведено коректність методу через систему з п’яти формальних тверджень. У п’ятому розділі наведено опис програмної реалізації SAindex та її експериментальної оцінки. Реалізацію виконано мовою C обсягом 2782 рядки коду й інтегровано в ядро PostgreSQL 18devel. Сформульовано методологію оцінки на трьох наборах даних (GeoNames, synthetic_uniform, synthetic_zipf) на п’яти масштабах від 100 000 до 5 000 000 рядків, по 30 запусків на шаблон. Наведено результати порівняння SAindex з GIN_TRGM, BTREE та BTREE_REV за чотирма парами, проаналізовано їхню статистичну значущість, поведінку за обмеженого I/O та валідність вибору планувальника; обговорено практичні обмеження методу та намічено напрями подальшої роботи.