Добро пожаловать в форум, Guest  >>   Войти | Регистрация | Поиск | Правила | В избранное | Подписаться
Все форумы / Сравнение СУБД Новый топик    Ответить
Топик располагается на нескольких страницах: [1] 2 3 4 5 6   вперед  Ctrl      все
 Способы реализации индексов  [new]
Индекс Способович
Guest
При поиске/сканировании по индексу в MS SQL данные всегда берутся из индексов, в Firebird индекс содержит ссылку на запись и данные берутся из таблицы.
Какие плюсы и минусы у различных способов индексирования и как это реализовано в других СУБД?
Вопрос чисто теоретический, надеюсь того кто знает не затруднит просветить в этом плане.
29 мар 11, 03:25    [10436503]     Ответить | Цитировать Сообщить модератору
 Re: Способы реализации индексов  [new]
miksoft
Member

Откуда:
Сообщений: 38919
Индекс Способович
При поиске/сканировании по индексу в MS SQL данные всегда берутся из индексов
Я хоть MS SQL и не знаю, но готов поспорить, что это неверно.
29 мар 11, 09:54    [10436923]     Ответить | Цитировать Сообщить модератору
 Re: Способы реализации индексов  [new]
kDnZP
Member [заблокирован]

Откуда: ★[msg=16399436]★[msg=20850760]
Сообщений: 11289
miksoft
Индекс Способович
При поиске/сканировании по индексу в MS SQL данные всегда берутся из индексов
Я хоть MS SQL и не знаю, но готов поспорить, что это неверно.

Всегда - не верное утверждение, с чего ТС так решил не ясно. Для некластерных индексов обычно вернее даже обратное (если не брать include).
29 мар 11, 10:09    [10437016]     Ответить | Цитировать Сообщить модератору
 Re: Способы реализации индексов  [new]
Dimitry Sibiryakov
Member

Откуда:
Сообщений: 54783

Индекс Способович
Какие плюсы и минусы у различных способов индексирования и как это реализовано в других СУБД?

Плюс и минус тут тупо один: скорость работы. Разные индексы работают лучше остальных в
разных ситуациях. Поэтому в "других СУБД" есть туева хуча типов индексов и огромные тома
документации в которых подробно расписывается в каких случаях какие типы лучше использовать.

Posted via ActualForum NNTP Server 1.4

29 мар 11, 12:01    [10437979]     Ответить | Цитировать Сообщить модератору
 Re: Способы реализации индексов  [new]
Индекс Способович
Guest
kDnZP
miksoft
пропущено...
Я хоть MS SQL и не знаю, но готов поспорить, что это неверно.

Всегда - не верное утверждение, с чего ТС так решил не ясно. Для некластерных индексов обычно вернее даже обратное (если не брать include).

Да уточню, не всегда, при Index Seek через Key Lookup будет брать из кластерного/таблицы.
При Index Scan всегда, либо вообще не будет использовать индекс.

Dimitry Sibiryakov
Индекс Способович
Какие плюсы и минусы у различных способов индексирования и как это реализовано в других СУБД?

Плюс и минус тут тупо один: скорость работы. Разные индексы работают лучше остальных в
разных ситуациях. Поэтому в "других СУБД" есть туева хуча типов индексов и огромные тома
документации в которых подробно расписывается в каких случаях какие типы лучше использовать.

Это понятно, интересует чуть больше деталей.
Интересует обычный B-tree индекс и именно варианты его реализации в различных СУБД.
Расскажите хотя бы в первом приближении. Или киньте ссылкой на материал именно по этой теме.
29 мар 11, 18:08    [10441382]     Ответить | Цитировать Сообщить модератору
 Re: Способы реализации индексов  [new]
Dimitry Sibiryakov
Member

Откуда:
Сообщений: 54783

Индекс Способович
Интересует обычный B-tree индекс и именно варианты его реализации в различных СУБД.

Варианты не в реализации, а в том, что именно в индексе хранится. У IB/FB в индексе
хранится фактически хэш данных и именно поэтому она всегда лезет за реальными данными в
таблицу. Зато поиск по индексу сводится к быстрому сравнению бинарных данных. Это
оптимально когда выбирается малое число записей из многих.

Posted via ActualForum NNTP Server 1.4

29 мар 11, 18:24    [10441480]     Ответить | Цитировать Сообщить модератору
 Re: Способы реализации индексов  [new]
MasterZiv
Member

Откуда: Питер
Сообщений: 34709

On 29.03.2011 10:54, miksoft wrote:

> При поиске/сканировании по индексу в MS SQL данные *всегда* берутся из индексов
>
> Я хоть MS SQL и не знаю, но готов поспорить, что это неверно.

Таки неверно.

Posted via ActualForum NNTP Server 1.4

29 мар 11, 21:33    [10442196]     Ответить | Цитировать Сообщить модератору
 Re: Способы реализации индексов  [new]
MasterZiv
Member

Откуда: Питер
Сообщений: 34709

On 29.03.2011 4:25, Индекс Способович wrote:

> При поиске/сканировании по индексу в MS SQL данные всегда берутся из индексов, в
> Firebird индекс содержит ссылку на запись и данные берутся из таблицы.

Это утверждение неверно.

> Какие плюсы и минусы у различных способов индексирования и как это реализовано в
> других СУБД?

Основной способ индексирования во всех субд -- B+tree.
Все остальные виды индексов в общем-то достаточно экзотичны и малоприменимы в
общей практике, и призваны лечить какие-то экзотические тупые запросы.

Posted via ActualForum NNTP Server 1.4

29 мар 11, 21:36    [10442212]     Ответить | Цитировать Сообщить модератору
 Re: Способы реализации индексов  [new]
Индекс Способович
Guest
MasterZiv
On 29.03.2011 4:25, Индекс Способович wrote:

> При поиске/сканировании по индексу в MS SQL данные всегда берутся из индексов, в
> Firebird индекс содержит ссылку на запись и данные берутся из таблицы.

Это утверждение неверно.

> Какие плюсы и минусы у различных способов индексирования и как это реализовано в
> других СУБД?

Основной способ индексирования во всех субд -- B+tree.
Все остальные виды индексов в общем-то достаточно экзотичны и малоприменимы в
общей практике, и призваны лечить какие-то экзотические тупые запросы.

Прочитайте пожалуйста внимательно мое второе сообщение в теме.
29 мар 11, 22:34    [10442492]     Ответить | Цитировать Сообщить модератору
 Re: Способы реализации индексов  [new]
Индекс Способович
Guest
Dimitry Sibiryakov
Индекс Способович
Интересует обычный B-tree индекс и именно варианты его реализации в различных СУБД.

Варианты не в реализации, а в том, что именно в индексе хранится. У IB/FB в индексе
хранится фактически хэш данных и именно поэтому она всегда лезет за реальными данными в
таблицу. Зато поиск по индексу сводится к быстрому сравнению бинарных данных. Это
оптимально когда выбирается малое число записей из многих.

Имеется ввиду, что индекс представляет собой b-дерево с неполными данными?
Потому как хэш-данных храниться в хэш-индексах, которые не имеют информации о порядке и отсутствуют в IB/FB.
29 мар 11, 23:08    [10442624]     Ответить | Цитировать Сообщить модератору
 Re: Способы реализации индексов  [new]
Dimitry Sibiryakov
Member

Откуда:
Сообщений: 54783

Индекс Способович
Имеется ввиду, что индекс представляет собой b-дерево с неполными данными?
Потому как хэш-данных храниться в хэш-индексах, которые не имеют информации о порядке и
отсутствуют в IB/FB.

А что такое неполные данные? И почему это хэш-индексы не имеют информации о порядке?

Posted via ActualForum NNTP Server 1.4

29 мар 11, 23:21    [10442669]     Ответить | Цитировать Сообщить модератору
 Re: Способы реализации индексов  [new]
Индекс Способович
Guest
Dimitry Sibiryakov
Индекс Способович
Имеется ввиду, что индекс представляет собой b-дерево с неполными данными?
Потому как хэш-данных храниться в хэш-индексах, которые не имеют информации о порядке и
отсутствуют в IB/FB.

А что такое неполные данные? И почему это хэш-индексы не имеют информации о порядке?

1. Меньше чем исходные данные.
2. По определению.
29 мар 11, 23:26    [10442690]     Ответить | Цитировать Сообщить модератору
 Re: Способы реализации индексов  [new]
Dimitry Sibiryakov
Member

Откуда:
Сообщений: 54783

Индекс Способович
1. Меньше чем исходные данные.
2. По определению.

А тебе никогда не приходило в голову, что в качестве хэш-функции можно выбрать, например,
toupper() и тем самым получить case-insensitive индекс? При этом оба твоих пункта плачут и
идут лесом. Хэши, знаешь ли, не ограничиваются криптографическими...

Posted via ActualForum NNTP Server 1.4

29 мар 11, 23:29    [10442703]     Ответить | Цитировать Сообщить модератору
 Re: Способы реализации индексов  [new]
Индекс Способович
Guest
Dimitry Sibiryakov
Индекс Способович
1. Меньше чем исходные данные.
2. По определению.

А тебе никогда не приходило в голову, что в качестве хэш-функции можно выбрать, например,
toupper() и тем самым получить case-insensitive индекс? При этом оба твоих пункта плачут и
идут лесом. Хэши, знаешь ли, не ограничиваются криптографическими...

Если бы определением хэш-функции было - любая функция, вы были бы правы.
Но у хэш-функции есть определение и то что вы приводите никак туда не подходит.
Собственно как и case-insensitive индекс не подходит под определение хэш-индекса.
Но если вы настаиваете, ладно вы правы.

Лучше давайте вернемся к теме. К чему вы сказали про хэш данных в индексе?
Dimitry Sibiryakov
Варианты не в реализации, а в том, что именно в индексе хранится. У IB/FB в индексе
хранится фактически хэш данных и именно поэтому она всегда лезет за реальными данными в
таблицу.

Я так понимаю из индекса данные не берутся исключительно из-за отсутствия в них информации об актуальности данных (информации о версиях)?
29 мар 11, 23:45    [10442765]     Ответить | Цитировать Сообщить модератору
 Re: Способы реализации индексов  [new]
Dimitry Sibiryakov
Member

Откуда:
Сообщений: 54783

Я сказал это потому, что я не ограничиваю пространство хэш-функций узкими рамками функций,
пригодных для криптографических целей. И так да, согласно этому определению любая функция
может являться хэш-функцией пока удовлетворяет условию однозначности преобразования x в
f(x). Поэтому f(x)=upper(x) или f(x)=x ничем не хуже чем f(x)=md5(x). Даже лучше,
поскольку при условии x<y<z выполнение условия f(x)<f(y)<f(z) позволяет получить тот самый
индекс, сохраняющий информацию о порядке.

И данные из индекса не берутся не только из-за отсутствия информации об их актуальности,
но и потому, что данных там, собственно, нет. Применяемая для получения индексного ключа
функция в общем случае необратима, что как раз свойственно хэш-функциям.

Posted via ActualForum NNTP Server 1.4

30 мар 11, 00:07    [10442803]     Ответить | Цитировать Сообщить модератору
 Re: Способы реализации индексов  [new]
Индекс Способович
Guest
Dimitry Sibiryakov
Я сказал это потому, что я не ограничиваю пространство хэш-функций узкими рамками функций,
пригодных для криптографических целей. И так да, согласно этому определению любая функция
может являться хэш-функцией пока удовлетворяет условию однозначности преобразования x в
f(x). Поэтому f(x)=upper(x) или f(x)=x ничем не хуже чем f(x)=md5(x). Даже лучше,
поскольку при условии x<y<z выполнение условия f(x)<f(y)<f(z) позволяет получить тот самый
индекс, сохраняющий информацию о порядке.

И данные из индекса не берутся не только из-за отсутствия информации об их актуальности,
но и потому, что данных там, собственно, нет. Применяемая для получения индексного ключа
функция в общем случае необратима, что как раз свойственно хэш-функциям.

ZXY<Zxy<abc и ZXY<ZXY<ABC )
Это называется коллизии, они так же не позволяют сохранять порядок.
Если не ограничивать пространство арбузов узкими рамками тыквины, а ещё и яблоки арбузами называть. Я не настаиваю, но я бы предпочел называть функции подходящие под определение хэш-функции.
Но не верьте мне, я просто беру частные случаи, на самом деле вы правы.

Кстати, а как в Oracle с этим дело обстоит, там данные берутся из индекса?
30 мар 11, 00:45    [10442873]     Ответить | Цитировать Сообщить модератору
 Re: Способы реализации индексов  [new]
kdv
Member

Откуда: iBase.ru
Сообщений: 30253
Индекс Способович
Кстати, а как в Oracle с этим дело обстоит, там данные берутся из индекса?

в B+Tree индексе данных нет. Есть только ссылки на данные, о чем и говорит DS.
MS SQL (как и любой другой блокировочный сервер, и если в MS SQL не включать версионность) может использовать только индекс (без данных) по столбцу field например для count(field), потому что число ключей всегда соответствует числу записей. То же самое - если и поиск и выборка идет только одного индексного столбца, тут в данные лазить без надобности.

У ФБ по причине версионности это не так. Например, у трех версий одной записи может быть 2 ключа. Т.е. количество ключей может быть больше чем количество записей, но не меньше чем количество версий. И, в ключах индексов ФБ не хранится информация о транзакции. Таким образом, без чтения версии и определения ее видимости нельзя посчитать count по столбцу.
Dmitry Sibiryakov косвенно намекает на общее сходство обычных индексов ФБ с индексами по выражению, которые уж точно самих данных не содержат, хотя выражение может быть A+0, т.е. даже не меняющее значения столбца.

При всем при этом индексы ФБ - достаточно обычные B+деревья, с некоторой спецификой, правда, куда входит как минимум префиксная компрессия и однонаправленность скана ключей.

Данные в индексах - это как раз кластерные индексы, или, грубо говоря, таблица, отсортированная по "индексному" столбцу. Коллеги вполне могут меня поправить, я глубоко устройством кластерных индексов не интересовался.
30 мар 11, 03:54    [10443003]     Ответить | Цитировать Сообщить модератору
 Re: Способы реализации индексов  [new]
Sk1N.
Member

Откуда: Курган
Сообщений: 75
kdv,
kdv
...
Например, у трех версий одной записи может быть 2 ключа. Т.е. количество ключей может быть больше чем количество записей, но не меньше чем количество версий.
...

Сначала ключей меньше чем версий, потом обратное: ключей не может быть меньше чем версий. Где описка? :)
30 мар 11, 07:44    [10443082]     Ответить | Цитировать Сообщить модератору
 Re: Способы реализации индексов  [new]
pkarklin
Member

Откуда: Москва (Муром)
Сообщений: 74930
kdv
У ФБ по причине версионности ... в B+Tree индексе данных нет.


Я правильно понимаю, что в ФБ хранение в индексе хэша, а не данных Вы объясняете версионностью?

Dimitry Sibiryakov
У IB/FB в индексе хранится фактически хэш данных и именно поэтому она всегда лезет за реальными данными в таблицу. Зато поиск по индексу сводится к быстрому сравнению бинарных данных. Это
оптимально когда выбирается малое число записей из многих.


Я правильно понимаю, что такие понятия как covered indexes и indexes with included columns (которые позволяют снизить издержки на IO и "экономить" буфферный кэш) в IB/FB отсутвуют как класс?
30 мар 11, 08:46    [10443179]     Ответить | Цитировать Сообщить модератору
 Re: Способы реализации индексов  [new]
kdv
Member

Откуда: iBase.ru
Сообщений: 30253
Sk1N.
Сначала ключей меньше чем версий, потом обратное: ключей не может быть меньше чем версий. Где описка? :)

ошибка во второй части.
количество записей <= количество ключей <= количество записей+версий

pkarklin
Я правильно понимаю, что в ФБ хранение в индексе хэша, а не данных Вы объясняете версионностью?

нет. И про "хэш в индексе" Сибиряков уже объяснил, что ОН имел в виду. Хранятся, конечно, данные, только из-за отсутствия в ключе информации о транзакции невозможно определить видимость ключа без определения видимости записи.

Целесообразность введения в ключ номера транзакции обсуждали, но насколько я помню, признали нецелесообразным - оверхед увеличения размера ключа больше чем польза от трюков "считал индекс, данные можно не читать".
Например, в индексе не хранится сотня одинаковых ключей А - хранится 1 ключ А и отсортированная цепочка номеров записей, имеющих такой ключ.
30 мар 11, 10:43    [10443681]     Ответить | Цитировать Сообщить модератору
 Re: Способы реализации индексов  [new]
MasterZiv
Member

Откуда: Питер
Сообщений: 34709

On 29.03.2011 19:08, Индекс Способович wrote:

> Это понятно, интересует чуть больше деталей.
> Интересует обычный B-tree индекс и именно варианты его реализации в различных СУБД.
> Расскажите хотя бы в первом приближении. Или киньте ссылкой на материал именно
> по этой теме.

Там мало что можно придумать.
Обычно делают префиксное сжатие ключа (как правило все ключи на странице
начинаются с какого-то одного префикса, его не хранят, хранят только
различающиеся суффиксы), иногда делают сжатие ключей (но это идиотизм воообще),
и 2 самых дежурных темы --

-- как и когда заполнять и расщеплять страницы
-- в виде чего хранить ссылки на записи в таблице.

Это уже собственно к индексам мало относится, больше к архитектуре СУБД.

Posted via ActualForum NNTP Server 1.4

30 мар 11, 11:23    [10444016]     Ответить | Цитировать Сообщить модератору
 Re: Способы реализации индексов  [new]
Dimitry Sibiryakov
Member

Откуда:
Сообщений: 54783

kdv
Dmitry Sibiryakov косвенно намекает на общее сходство обычных индексов ФБ с
индексами по выражению, которые уж точно самих данных не содержат, хотя выражение может
быть A+0, т.е. даже не меняющее значения столбца.

Да я, собственно, не намекаю, а прямо об этом говорю. Данные на пути в индекс всегда
проходят преобразование в ключ. И функция этого преобразования - чёрный ящик. Даже если
она обратима, никто об этом не знает, поэтому весь движок построен на предположении, что
это преобразование необратимо.

pkarklin
Я правильно понимаю, что такие понятия как covered indexes и indexes with included columns
(которые позволяют снизить издержки на IO и "экономить" буфферный кэш) в IB/FB отсутвуют
как класс?

Именно так. За счёт этого нет проблем с регистро- и акценто-нечувствительностью при
индексном доступе.

Posted via ActualForum NNTP Server 1.4

30 мар 11, 11:40    [10444180]     Ответить | Цитировать Сообщить модератору
 Re: Способы реализации индексов  [new]
pkarklin
Member

Откуда: Москва (Муром)
Сообщений: 74930
Dimitry Sibiryakov
Именно так. За счёт этого нет проблем с регистро- и акценто-нечувствительностью при
индексном доступе.


О каких проблемах идет речь? Например, регистро- и акценто-нечувствительность\нечуствительность в MS SQL может быть задана вплоть до уровня отдельного поля в таблице.
30 мар 11, 12:33    [10444631]     Ответить | Цитировать Сообщить модератору
 Re: Способы реализации индексов  [new]
Gluk (Kazan)
Member

Откуда:
Сообщений: 9365
Индекс Способович
Dimitry Sibiryakov
Я сказал это потому, что я не ограничиваю пространство хэш-функций узкими рамками функций,
пригодных для криптографических целей. И так да, согласно этому определению любая функция
может являться хэш-функцией пока удовлетворяет условию однозначности преобразования x в
f(x). Поэтому f(x)=upper(x) или f(x)=x ничем не хуже чем f(x)=md5(x). Даже лучше,
поскольку при условии x<y<z выполнение условия f(x)<f(y)<f(z) позволяет получить тот самый
индекс, сохраняющий информацию о порядке.

И данные из индекса не берутся не только из-за отсутствия информации об их актуальности,
но и потому, что данных там, собственно, нет. Применяемая для получения индексного ключа
функция в общем случае необратима, что как раз свойственно хэш-функциям.

ZXY<Zxy<abc и ZXY<ZXY<ABC )
Это называется коллизии, они так же не позволяют сохранять порядок.
Если не ограничивать пространство арбузов узкими рамками тыквины, а ещё и яблоки арбузами называть. Я не настаиваю, но я бы предпочел называть функции подходящие под определение хэш-функции.
Но не верьте мне, я просто беру частные случаи, на самом деле вы правы.

Кстати, а как в Oracle с этим дело обстоит, там данные берутся из индекса?


определение хэш функции соблаговолите представить :)
а то получается почти как про 7 красных линий
30 мар 11, 12:44    [10444703]     Ответить | Цитировать Сообщить модератору
 Re: Способы реализации индексов  [new]
Ivan Durak
Member

Откуда: Minsk!!!
Сообщений: 3789
А в оракле тоже непокрывающие чтоли? аки в фб?
30 мар 11, 12:49    [10444748]     Ответить | Цитировать Сообщить модератору
Топик располагается на нескольких страницах: [1] 2 3 4 5 6   вперед  Ctrl      все
Все форумы / Сравнение СУБД Ответить