1

Тема: який індекс працює швидше і чому

маю postgresql,
таблицю з двома стовбцями - id (циферки по-порядку) та хешем (строки з md5 - 32символи буковки-циферки),

створюю btree індекс

запитання - індекс по якому стовпчику буде швидшим і чому?

дякую:)

2

Re: який індекс працює швидше і чому

PostgreSQL вже настільки просунутий, що там можна робити

CREATE TABLE t(
  id циферки по-порядку,
  хеш строки з md5 - 32символи буковки-циферки
);

чи все ж ті типи якісь інші?

Подякували: 221VOLT, leofun01, ADR3

3

Re: який індекс працює швидше і чому

:D
id - int, (serial)
hash - varchar (тут я просто уточнив які значення є)

4

Re: який індекс працює швидше і чому

bytea, мені здається, більше підходить для md5, та й навіть char (розмір же фіксований), ну то ваші проблеми.
Що ж до швидкості пошуку - то:
- треба тестувати;
- швидкість буде відрізнятися на час обчислення хешу, а вона вочевидь менше в коротшого значення, тобто в id.

Подякували: 221VOLT1

5 Востаннє редагувалося iovchynnikov (28.05.2016 09:23:06)

Re: який індекс працює швидше і чому

221VOLT написав:

запитання - індекс по якому стовпчику буде швидшим і чому?

А які запити ви найбільше будете робити?

Якщо ви будете робити тільки SELECT hash FROM table WHERE id=** то хеш буде швидшим (O(1) проти O(log)). В усіх інших випадках (особливо будь-які порівняльні операції >, <, between), дерево буде швидшим, де дерево виконує операції за O(log) а пошук по хеш таблиці перетворюється/майже перетворюється на full table scan. Саме тому дерево є індексом за замовчуванням, а у багатьох db - єдиний варіянт.

Поза тим, постгрес у зв'язку з реалізацією може перебудовувати hash індекс. Так, наприклад, postgress перебудує повністю hash індекси після крешу бази, або проблемах з записом даних (https://www.postgresql.org/docs/9.1/sta … types.html).

Для md5 найкращій тип це char[32].

Подякували: 221VOLT, FakiNyan, leofun013

6

Re: який індекс працює швидше і чому

iovchynnikov написав:
221VOLT написав:

запитання - індекс по якому стовпчику буде швидшим і чому?

А які запити ви найбільше будете робити?

Якщо ви будете робити тільки SELECT hash FROM table WHERE id=** то хеш буде швидшим (O(1) проти O(log)). В усіх інших випадках (особливо будь-які порівняльні операції >, <, between), дерево буде швидшим, де дерево виконує операції за O(log) а пошук по хеш таблиці перетворюється/майже перетворюється на full table scan. Саме тому дерево є індексом за замовчуванням, а у багатьох db - єдиний варіянт.

Поза тим, постгрес у зв'язку з реалізацією може перебудовувати hash індекс. Так, наприклад, postgress перебудує повністю hash індекси після крешу бази, або проблемах з записом даних (https://www.postgresql.org/docs/9.1/sta … types.html).

Для md5 найкращій тип це char[32].

так, запит саме такий (WHERE id=** , перепрошую, затупив я - відразу не написав сам запит)

чесно - я не зрозумів, чому хеш буде швидшим,
хоча трошки і читав про btree (якби розумів - запитання не виникло би))


буду вдячний за будь-який маленький приклад - на прикладі швидше доходить
(хочеться нарешті зрозуміти цю відмінність, закрити для себе це запитання)

7 Востаннє редагувалося iovchynnikov (28.05.2016 14:39:33)

Re: який індекс працює швидше і чому

221VOLT написав:
iovchynnikov написав:
221VOLT написав:

запитання - індекс по якому стовпчику буде швидшим і чому?

А які запити ви найбільше будете робити?

Якщо ви будете робити тільки SELECT hash FROM table WHERE id=** то хеш буде швидшим (O(1) проти O(log)). В усіх інших випадках (особливо будь-які порівняльні операції >, <, between), дерево буде швидшим, де дерево виконує операції за O(log) а пошук по хеш таблиці перетворюється/майже перетворюється на full table scan. Саме тому дерево є індексом за замовчуванням, а у багатьох db - єдиний варіянт.

Поза тим, постгрес у зв'язку з реалізацією може перебудовувати hash індекс. Так, наприклад, postgress перебудує повністю hash індекси після крешу бази, або проблемах з записом даних (https://www.postgresql.org/docs/9.1/sta … types.html).

Для md5 найкращій тип це char[32].

так, запит саме такий (WHERE id=** , перепрошую, затупив я - відразу не написав сам запит)

чесно - я не зрозумів, чому хеш буде швидшим,
хоча трошки і читав про btree (якби розумів - запитання не виникло би))


буду вдячний за будь-який маленький приклад - на прикладі швидше доходить
(хочеться нарешті зрозуміти цю відмінність, закрити для себе це запитання)

Особливого розуміння тут не треба, це - особливості самих структур даних: hashtable i b-tree.
Най маємо 2 індекси: hashIndex(id, md5), btreeIndex(id, md5)

hashIndex зберігає дані у постаті таблиці:
------------------------------------------
| hash(id) | List<md5> ("бакет")  |
------------------------------------------

Наприклад, якщо таку таблицю
------------------------------
| 1 | 1312dasdas131sad |
| 2 | vcxvxvxcvxcvxcsaad |
| 3 | asasasasasasasasa  |
| 4 | 111zzzxxxccc55555 |
| 5 | pppppppppppaaaaa |
------------------------------

проіндексовані стовпчики можуть виглядати у масиві так:
----------------------------------------------------------
| 123sc | [1, 1312dasdas131sad], [2, vcxvxvxcvxcvxcsaad]
| 5serc  | [3, asasasasasasasasa]
| 632x  | [4, 111zzzxxxccc55555]
| 112x  | [5, pppppppppppaaaaa]
-------------------------------------------------------------
array[123sc] = list([1, 1312dasdas131sad], [2, vcxvxvxcvxcvxcsaad])
array[5serc] = list([3, asasasasasasasasa])

Алгоритм створення хеш таблиці такий:
1) Беремо якийсь_алгоритм_хешування і застосовуємо його до ключа (1 стовпчик). Отримане значення - ключ у хеш таблиці.
2) Дописуємо у відповідний бакет відповідне до ключа значення (2 стовпчик).

Чому у бакеті може бути кілька значень? Тому що якийсь_алгоритм_хешування не дає 100% унікальний id бакета, тож 2 різних значення у 1 стовпчику можуть дати 1 й той самий індекс. Ось тому у нашій таблиці 1312dasdas131sad,vcxvxvxcvxcvxcsaad відповідають різні індексі, а у хештаблиці вони знаходяться у одному бакеті під 1 індексом.

Ну і тепер чому це where id = ** працює швидше.
Уявіть таблицю у базі у вигляді зв'язаного списку. Пошук по такій базі - ітерація від елементу до елементу і перевірка чи індекси співпадають. ~ O(n)
Якщо ми створюємо хеш індекс, пошук вже буде відбуватися у хештаблиці, яка зберігається у вигляді масиву, доступ до елементів якого за індексом є дуже швидкою операцію (тому що кожній комірці масиву відповідає однозначний адрес у пам'яті). Залишилося лише:

..where id = 1
1) якийсь_алгоритм_хешування(1) = 123sc
2) hastableArray[123sc] = list([1, 1312dasdas131sad], [2, vcxvxvxcvxcvxcsaad])
3) findValueInBucketByKey(1, list([1, 1312dasdas131sad], [2, vcxvxvxcvxcvxcsaad])) = 1312dasdas131sad

Тобто у порівнянні до пошуку за усією таблицею, використовуючи індекс можна "зрізати" одразу пошук до 1-5 значень.

Натомість дерево будує...збалансоване дерево, яке треба обходити:
https://upload.wikimedia.org/wikipedia/commons/thumb/a/a9/Unbalanced_binary_tree.svg/2000px-Unbalanced_binary_tree.svg.png
Звичайно, тупо він не обходить, а звіряється зі значенням ключів, де праве значення, більше лівого (чи навпаки) і вирішує у яку сторону піти, доки не знайде потрібне. І ця операція може буде у більшості випадках повільніша.

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

Сподіваюся хоч щось зрозуміло з цього))

Подякували: 221VOLT, leofun01, Анатолій, Regen4

8

Re: який індекс працює швидше і чому

дякую, те що потрібно :)

9

Re: який індекс працює швидше і чому

Одна проблема: у вас тут хеш не обчислюється, тільки дерево. Обидва індекси - btree, тільки у випадку з полем serial він заданий неявно.

Подякували: 221VOLT1