Просторовий індекс для PostgreSQL на основі Z-order (vs R-tree), продовження


минулий раз ми прийшли до висновку, що для ефективної роботи просторового індексу на основі Z-order необхідно зробити 2 речі:
  • ефективний алгоритм отримання подинтервалов
  • низькорівневу роботу з B-деревом
Ось саме цим ми і займемося під катом.

Почнемо з більш цікавого, алгоритму.

Розбиття на підпорядкований
Будемо розглядати 2-мірний алгоритм (індексація точок) в силу його відносної простоти. Втім, на великі розмірності алгоритм легко узагальнюється.

Зараз ми (для простоти) будемо використовувати невід'ємні цілочисельні координати. Координати обмежені 32 бітами, тому значення ключа індексу можна зберігати в uint64

Нам знадобляться наступні прості властивості z-нумерації:
  1. Нехай на площині відзначений деякий прямокутник. Тоді серед всіх точок прямокутника найменший z-номер має лівий нижній кут прямокутника (будемо називати його «z»), а найбільший – правий верхній кут (назвемо його «Z»). Дана властивість очевидним чином випливає із способу побудови z-кімнати.
  2. Кожен прямокутник можна розділити єдиним чином на два прямокутника (вертикальним або горизонтальним розрізом) так, що всі z-номери першого прямокутника менше всіх z-номерів другого. Це випливає з самоподібності Z-кривий. Елементарна комірка з чотирьох клітин ділиться навпіл, потім ще навпіл двома розрізами, те ж саме відбувається на всіх рівнях ієрархії.
Як саме необхідно розрізати экстент, щоб зберегти властивість безперервності подинтервалов?

З самоподібності кривий випливає, що розрізати можна тільки по решітці з кроком в ступінь двійки і з вузлом в початку координат.

Але яку конкретно грати з доступних 64 вибрати? Це досить просто. Розрізається экстент повинен займати в шуканої решітці більше однієї клітини, інакше просто нічого розрізати. З іншого боку, по кожній з координат розмір не може перевищувати 2 клітини, а принаймні по одній повинен бути строго 2 клітини. Якщо по обидва розмірностями розрізається экстент займає 2 клітини, різати будемо по тій координаті, чий розряд в побудові Z-значення старший.

Як же знайти таку решітку? Це теж нескладно. Досить порівняти Z-значення кутів z та Z Почнемо порівнювати зі старших розрядів і знайдемо розряд, де їх значення розійшлися. Ось і шукана решітка.

Як здійснити розріз? Тут необхідно згадати метод побудови Z-значення, а саме те, що x&y координати чергуються через розряд. Отже:
  • нехай відмінність між z і Z почалося в розряді m
  • розрізати будемо по одній координаті, на яку довелося m, незалежно від того, x чи y, нехай в даному випадку це x, втім, для y все працює точно так само
  • з экстента (x0,y0,x1,y1) ми повинні отримати два: (x0,y0,x2-1,y1),(x2,y0,x1,y1)
  • а для того, щоб отримати x2 досить обнулити всі розряди x координати молодше m, тобто через один
  • x2-1 виходить обнуленням біта m і присвоєнням 1 всім молодшим x розрядів
Отже, як виглядає алгоритм генерації підпорядкованого? Досить невибагливо:
  1. Заводимо чергу підзапитів, спочатку в цій черзі один єдиний елемент — шуканий экстент
  2. Поки черга не порожня:
    1. дістаємо елемент з вершини черзі
    2. якщо для цього запиту не спрацьовує критерій зупинки
      1. отримуємо z і Z — значення для його кутів
      2. порівнюємо z і Z — знаходимо розряд m, за яким будемо різати

      3. вищеописаним способом отримуємо два подзапроса
      4. поміщаємо їх у чергу, спочатку той, що з великими Z-значеннями, потім другий
Такий спосіб гарантує нам генерацію підзапитів, при якому Z-значення фінальних (тобто ті, на яких спрацював критерій зупинки) підпорядкованого лише зростають, пробросов тому не виникає.

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

Варто відзначити, що при виробленні такого критерію ми не можемо покладатися лише на параметри запиту, площі, геометричні властивості… У реальних даних розподіл точок може бути досить нерівномірні, наприклад, міста і порожні простору. Населеність площ нам заздалегідь невідома.

Значить необхідна інтеграція з пошуком в дереві індексу, який, як ми пам'ятаємо, B-дерево.

Як виглядає підзапит з точки зору індексу? Це сукупність даних, розташованих на деякому числі сторінок. Якщо підзапит порожній, то і інтервал даних порожній, але тим не менш кудись дивиться, т. к. щоб зрозуміти що даних немає, треба спробувати їх прочитати і спуститися з вершини дерева до листової сторінки. Може так статися, що порожній запит дивиться і за межі дерева.

Взагалі, процес вичитування даних подзапроса складається з двох фаз —
  • зондування дерева. Починаючи з кореневої сторінки ми шукаємо ключ менше або дорівнює Z-значення лівого нижнього кута подзапроса (z) і так спускаємося до листової сторінки. На виході отримуємо стек сторінок і листову сторінку «в повітрі». На цій сторінці шукаємо елемент більше або дорівнює шуканому.
  • читання вперед до кінця подзапроса. В PostgreSQL листові сторінки B-дерева пов'язані списком, якщо б цього не було, для того, щоб отримати наступну сторінку довелося б піднятися вгору по стеку сторінок, щоб потім спуститися на неї.
Отже, після зондувального запиту у нас в руках листова сторінка, на якій імовірно починаються наші дані. Можливі різні ситуації:
  1. Знайдений елемент сторінки більше правого верхнього кута подзапроса (Z). Тобто даних немає.
  2. Знайдений елемент сторінки менше Z, останній елемент сторінки менше Z. тобто підзапит починається на цій сторінці, закінчується десь далі.
  3. Знайдений елемент сторінки менше Z, останній елемент сторінки більше Z. тобто весь підзапит розташований на цій сторінці.
  4. Знайдений елемент сторінки менше Z, останній елемент сторінки дорівнює Z. тобто підзапит починається на цій сторінці, але можливо закінчується наступного (кілька елементів з одними координатами). А може і сильно далі, якщо дублікатів багато.
Варіант N1 не вимагає ніяких дій. Для N2 природним представляється наступний критерій зупинки (розщеплення підпорядкованого) — будемо розрізати їх до тих пір, поки не отримаємо варіанти 3 або 4. З варіантом N3 все очевидно, у разі N4 сторінок з даними може бути кілька, але розрізати підзапит безглуздо т. к. на наступній сторінці(цах) можуть бути тільки дані з ключем рівним Z, після розрізу ми опинимося в тій же самій ситуації. Щоб справитися з цим, достатньо просто вважати з наступною(ють) сторінок всі дані з ключем рівним Z. Їх може і не бути, взагалі, N4 — це досить екзотичний випадок.

Робота з B-деревом
Низькорівнева колективна робота з B-деревом не представляє особливих труднощів.
Але доведеться створити розширення.
Загальна логіка така — зареєструємо SRF функцію
CREATE TYPE __ret_2d_lookup AS (c_tid TID, x integer, y: integer);
CREATE FUNCTION zcurve_2d_lookup(text, integer, integer, integer, integer)
RETURNS SETOF __ret_2d_lookup
AS 'MODULE_PATHNAME'
LANGUAGE C IMMUTABLE STRICT;

яка на вхід отримує ім'я індексу і экстент. А повертає набір елементів, в кожному з яких покажчик на рядок таблиці і координати.

Доступ до власне дереву відбувається так:
const char *relname; /* зовнішній параметр */
...
List *relname_list;
RangeVar *relvar;
Relation rel;
...
relname_list = stringToQualifiedNameList(relname);
relvar = makeRangeVarFromNameList(relname_list);
rel = indexOpen(rel);
...
indexClose(rel);

Отримання кореневої сторінки:
int access = BT_READ;
Буфер buf;
...
buf = _bt_getroot(rel, access);

В цілому, пошук в індексі зроблений подібно звичайному пошуку B дереві (см postgresql/src/backend/access/nbtree/nbtsearch.c). Зміни пов'язані зі специфікою ключа, можливо, можна було обійтися і без неї, хай це було б і трохи повільніше.

Пошук всередині сторінки виглядає так:
Page page;
BTPageOpaque opaque;
OffsetNumber low, high;
int32 result, cmpval;
Datum datum;
bool isNull;
...
page = BufferGetPage(buf);
opaque = (BTPageOpaque) PageGetSpecialPointer(page);
low = P_FIRSTDATAKEY(opaque);
high = PageGetMaxOffsetNumber(page);
...
тут йде бінарний пошук
...
/* для листової сторінки повертаємо знайдене значення */
if (P_ISLEAF(opaque))
return low;
/* для проміжної - попередній елемент */
return OffsetNumberPrev(low);

Отримання елемента сторінки:
OffsetNumber offnum; 
Page page;
Relation rel;
TupleDesc itupdesc = RelationGetDescr(rel);
IndexTuple itup;
Datum datum;
bool isNull;
uint64 val;
...
itup = (IndexTuple) PageGetItem(page, PageGetItemId(page, offnum));
datum = index_getattr(itup, 1, itupdesc, &isNull);
val = DatumGetInt64(datum);


Підсумковий алгоритм
  1. Заводимо чергу підзапитів, спочатку в цій черзі один єдиний елемент — шуканий экстент
  2. Поки черга не порожня:
    1. дістаємо елемент з вершини черзі
    2. виконуємо зондуючий запит в індексі для z (лівого нижнього кута). В цілях економії можна робити зондування не кожен раз, а тільки якщо останнє знайдене значення (яке спочатку 0) більше або дорівнює z

    3. у разі, якщо знайдене перевищує мінімальне значення Z (правий верхній кут), закінчуємо обробку цього подзапроса, переходимо на П. 2
    4. перевіряємо останній елемент листової сторінки B-дерева, на якій зупинився зондуючий запит
    5. якщо він більше або дорівнює Z, вибираємо елементи сторінки, фільтруємо їх на предмет приналежності пошуковому экстенту і запам'ятовуємо кінцеві точки.
    6. якщо він дорівнює Z, читаємо індекс вперед до повного вичерпання ключів зі значенням рівним Z і теж запам'ятовуємо їх
    7. в іншому випадку — останнє значення сторінки менше Z
      1. порівнюємо z і Z — знаходимо розряд m, за яким будемо різати
      2. вищеописаним способом отримуємо два подзапроса

      3. поміщаємо їх у чергу, спочатку той, що з великими Z-значеннями, потім другий


Попередні результати
У заголовній ілюстрації статті представлено розділення реального запиту на підзапит і кінцеві точки. Показано порівняння знайдених R-деревом результатів з отриманими вищеописаним алгоритмом. Картинка часів налагодження і видно, що однієї точки не вистачає.

Але картинки — картинками, а хочеться побачити порівняння продуктивності.
З нашого боку буде та ж таблиця
create table test_points (x integer,y: integer);
COPY test_points from '/home/.../data.csv';
create index zcurve_test_points on test_points(zcurve_val_from_xy(x, y));

і запити типу
select count(1) from zcurve_2d_lookup('zcurve_test_points', 500000,500000,501000,501000);

Порівнювати будемо з R-деревом як зі стандартом de facto. Причому, на відміну від минулого статті, нам потрібен «index only scan» за R-дерева т. к. наш Z-індекс більше не звертається до таблиці.
create table test_pt as (select point(x,y) from test_points);
create index test_pt_idx on test_pt using gist (point);
vacuum test_pt;

На таких даних запит
explain (analyze, buffers) select * from where test_pt 
point <@ box(
point(500000, 500000), 
point(510000, 510000));

видає
QUERY PLAN
---------------------------------------------------------------------------------------------
Index Only Scan using test_pt_idx on test_pt (cost=0.42..539.42 rows=10000 width=16) 
(actual time=0.075..0.531 rows=968 loops=1)
Index Cond: (point <@ '(510000,510000),(500000,500000)'::box)
Heap Fetches: 0
Buffers: shared hit=20
Planning time: 0.088 ms
Execution time: 0.648 ms
(6 rows)

що і потрібно було.

Власне порівняння:
Тип запиту Тип індексу Час мсек. Shared reads Shared hits
100Х100
~1 точка
R-tree
Z-curve
0.4*
0.34*
1.8
1.2
3.8
3.8
1000Х1000
~100 точок
R-tree
Z-curve
0.5...7**
0.41*
6.2
2.8
4.9
37
10000Х10000
~10000 точок
R-tree
Z-curve
4...150***
6.6****
150
43.7
27
2900
* — дані отримані при усередненні серії довжини 100 000
** — дані отримані при усередненні серії різної довжини, 10 000 vs 100 000
*** — дані отримані при усередненні серії різної довжини, 1 000 vs 10 000
**** — дані отримані при усередненні серії довжини 10 000

Виміри проводилися на скромній віртуальній машині з двома ядрами і 4 Гб ОЗП, тому часи не мають абсолютної цінності, а ось чисел прочитаних сторінок можна довіряти.
Часи показано на друге прогонах, на розігрітому сервері і віртуальній машині. Кількості прочитаних буферів — на свіжо-піднятому сервері.

Висновки
  • у всякому разі на маленьких запитах Z-індекс працює швидше R-дерева
  • і читає при цьому помітно менше сторінок
  • R-дерево набагато раніше починає масово промахуватися повз кешу
  • при цьому і сам Z-індекс вчетверо компактніше, так що для нього кеш працює більш ефективно
  • причому, не виключено, що промахи йдуть повз дискового кешу хост-машини, інакше важко пояснити таку різницю


далі
Розглянутий двовимірний точковий індекс призначений лише для перевірки концепції, в житті він мало-корисний.

Навіть для тривимірного індексу 64-розрядного ключа вже не вистачає (або впритул) для корисної роздільної здатності.

Так що попереду буде:
  • перехід на інший ключ, numeric
  • 3D варіант, в тому числі точки на сфері
  • перевірка можливості роботи з кривою Гільберта
  • повноцінні виміри
  • 4D варіант — прямокутники
  • 6D варіант — прямокутники на сфері
  • ...


PS: Исходники викладені тут з ліцензією BSD, описане в цій статті відповідає гілці raw-2D"

PPS: Алгоритм як такий був розроблений у стародавні часи (2004-2005 рр.) в співавторстві з Олександром Артюшиным.

PPPS: Величезне спасибі хлопцям з PostgresPro за те, що спонукали мене на впровадження даного алгоритму в PostgreSQL.
Джерело: Хабрахабр

0 коментарів

Тільки зареєстровані та авторизовані користувачі можуть залишати коментарі.