Допустим есть таблица без PK и по одному из её полей построен индекс. Как происходит операция Index Seek на самом нижнем уровне?
Проходим по узлам дерева до листьев, а там лежит служебное rowid и номер страницы в которой искомая запись, и по этому номеру страницы вычисляем смещение с которого нужно прочитать данные из файла БД?

Ну и интересует как это реализовано в различных СУБД и есть ли принципиальные отличия?

pkarklin, спасибо!

MasterZiv
Ок. А какие основные отличия?

MasterZivOn 08/19/2011 09:08 PM, tanglir wrote:

> Если убрать слово "кластерный", то это Мускль+ИнноДБ.

Зачем убирать ? В InnoDB вообще-то других индексов, кроме кластерных,
вообще не существует. Там всё в одном здоровом индексном дереве.

Это как в InnoDB, делаем на таблицу три индекса и получаем три копии таблицы отсортированные в порядке своих индексов?

Кластерный индекс это когда строится дерево по индексу, а в его листьях расположены остальные столбцы, как например PK в MS SQL. Тут ещё важно что они в базе лежат в порядке индекса для последовательного чтения с диска.
Но кластерный может быть только один индекс на таблицу, остальные обычные с указателями RID в листьях.

softwarerНу, "уникальный кластерный индекс" - вещь сама по себе весьма небесспорная, но просто интересно - где на практике применяется описанный угробищный подход?
А в чем угробищность подхода например?

SergSuperIndex SeekКластерный индекс это когда строится дерево по индексу, а в его листьях расположены остальные столбцы, как например PK в MS SQL .PK то здесь причем?..
Это "как например".
PK в MS SQL - всегда есть кластерный индекс.

alexeyvgSergSuperпропущено...
PK то здесь причем?.. Новички часто путают ПК и кластерный индекс (про разницу кластерного индекса и уникального кластерного индекса я вообще молчу - это для лысых профессоров :-) )
Надеюсь я ничего не напутал?

alexeyvgНо чаще всего это очень эффективно. Потому как не нужно перестраивать индексы при расщеплении страниц, не нужно удваивать размер индекса и делать по 2 чтения, как в оракле, и к тому же часто бывает, что обращение к страницам вообще не нужно, достаточно обращения к индексу.
А где там в Оракле удваивается размер индекса?

Кстати в Оракле можно делать кластерные IOT, по аналогии с кластерными таблицами (не путать с кластерным индексом)?

softwarerIndex SeekА в чем угробищность подхода например?
В том, что для индекса, например, глубины 5, нужно аж 10 чтений, чтобы добраться до искомых данных.
А можно чуть подробней? Или вы имеете ввиду при доступе к данным IOT/(таблицы с кластерным индексом) не по кластерному индексу, а по обычному? Я думаю там в листьях тоже есть информация о номере страницы с данными, навряд ли стали бы они так криво делать.

А если имеете ввиду именно кластерный индекс, то в обычном индексе в листьях находится RID по которому нужно ещё прочитать данные из таблицы, а в кластерном/IOT в листьях сами данные.
Мало того при IOS мы последовательно читаем, а не рандомно.

Например IOS нету в PostgreSQL и Firebird, там SELECT name FROM table ORDER BY id выгоднее делать сортировку чем использовать индекс по ID, как раз по описанной выше причине. По крайне мере в Firebird по этому поводу целая статья была.

SergSuperIndex Seekпропущено...

Это "как например".
PK в MS SQL - всегда есть кластерный индекс.

вобще-то не обязательно
Но PK - это логическое понятие, а тут разговор о физическом хранении
А можно пример как создать PK в MS SQL чтобы он не был кластерным индексом?

softwarerIndex SeekИли вы имеете ввиду ... Я думаю
Я имею в виду реализацию, описанную Master Ziv-ом на прошлой странице.

Index Seekтам SELECT name FROM table ORDER BY id выгоднее делать сортировку чем использовать индекс по ID
Запросы с order by id - вещь редкая, не то чтобы нужная, но из общих соображений я бы отметил, что в них сортировка будет выгоднее индекса всегда, когда нет гарантии в том, что записи вставлялись строго по возрастанию.
А ну что Master Ziv сказал я вообще не понял, надеюсь разъяснит.

"Запросы с order by id" это как пример. В реальности это круто скажется при SMJ, с допустим подсчетом агрегатов. В Firebird он начнет дергать таблицу в независимости от того что индекс покрывающий.
IOS по IOT позволит избежать random read, в отличие от index key lookup.
А IOT по сравнению с обычным покрывающим индексом позволит исключить затраты на сортировку по ненужным столбцам, допустим по которым идет подсчет агрегатов.
Собственно для этого например в MS SQL есть включенные столбцы и кластерный индекс, а в Oracle - IOT.

softwarerIndex SeekIOS по IOT позволит избежать random read, в отличие от index key lookup.
Если IOS - это что-нибудь типа Index Order Scan, то фокус как раз в том, что оно далеко не всегда лучшее решение.

Когда расщепляется страница в середине индекса, у сервера есть фактически два варианта: либо передвигать пол-индекса, либо записать новую страницу куда-нибудь в конец, то есть нарушить порядок следования страниц в индексе. Когда после этого производится массовое чтение по [покрывающему] индексу, то "считать индекс от начала до конца и отсортировать" скорее всего будет быстрее, нежели постранично считывать его в нужном порядке.
SMJ - Sort Merge Join.

Бывает что и Fast Full Index Scan с сортировкой быстрее чем Full Index Scan по сильно фрагментированному индексу. Если это OLTP, то там и данных и запросов таких мало. Если DWH, то индексы обычно в хорошем состоянии.
Но в приведенном мною примере если и случиться FFIS, то не с сортировкой, а с HASH JOIN и HASH MATCH. А вот если зададим в предикатах WHERE диапазоны то приехали, сортировка. Ну а сортировка по фактам DWH вообще унылое зрелище, если только не секционирована по этому полю.
Собственно с диапазонами в предикатах WHERE в Exadata идет FFIS со спасительным Smart Scan. А дальше HJ/HM.

Не знаю насколько в Firebird отсутствие IOS связано с версионностью :)
Но там соответственно не возможно и Fast Full Index Scan.
И нету спасительных в этом случае HASH JOIN с HASH MATCH.
Ну представьте таблицу в 10 ТБ, либо всю сортировать во внешней памяти, либо всю в random read дергать :) Это сутки.

egorych , круто :)

Dimitry SibiryakovIndex SeekНу представьте таблицу в 10 ТБ, либо всю сортировать во внешней памяти, либо всю в random
read дергать :) Это сутки.

Боюсь, что разработчика, написавшего такой запрос, убьют независимо от используемой СУБД...

Если вы про который я написал, то соединение со справочником и агрегированием по фактам входит почти в любой запрос к DWH и на нормальных СУБД он выполнится за несколько десятков минут. С матвью за минуту.
Или вы про то что его можно выполнить в Firebird за то же время? Расскажите как.

Dimitry SibiryakovIndex Seekсоединение со справочником и агрегированием по фактам входит почти в любой запрос к DWH

И почти любой запрос к DWH молотит террабайты данных? Я думал для этого давно придумали
свёртку в OLAP кубы.

И Firebird, вообще-то, не претендует на использование в DWH. У неё другая ниша.

А в результате какого запроса получается свёртка в OLAP кубы? :)

MasterZivOn 20.08.2011 2:59, Index Seek wrote:

> Это как в InnoDB, делаем на таблицу три индекса и получаем три копии таблицы
> отсортированные в порядке своих индексов?

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

Два индекса содержащие в листьях значения индексных полей или включенных полей кластерного индекса?
(Индексные - это которые отсортированы в кластерном, включенные - нет)

" и два индекса (можно сказать -- кластерные таблицы)"
Имеется ввиду кластерные таблицы в определениях Oracle?

ScareCrowавторИмеется ввиду кластерные таблицы в определениях Oracle?
да это везде так, потому что по другому не сделаешь. хотя коллега софтварер говорит что в Оракле еще и указатель на страницу хранится.
p.s. чем больше узнаю про оракл тем больше удивляюсь - как он вообще умудряется работать?
В кластерных таблицах указатель на страницу хранится? Это скорей всего нигде так.
Кластерные таблицы - это физически сджойненные таблицы, а логически отдельные. Не совсем понятно как они относятся к индексам в InnoDB.

SergSuper , да, индекс так и выглядит. А вывод то какой?

MasterZivOn 23.08.2011 15:51, Index Seek wrote:

> Два индекса содержащие в листьях значения индексных полей или включенных полей
> кластерного индекса?
> (Индексные - это которые отсортированы в кластерном, включенные - нет)
>
> " и два индекса (можно сказать -- кластерные таблицы)"
> Имеется ввиду кластерные таблицы в определениях Oracle?

Это я так сказал, чтобы было понятнее. Но видно получилось наоборот.

Там будут три индекса, один кластерный, и два обычных,
два последних в листах будут содержать ссылки на записи в виде
значений полей кластерного индекса (PK) этой таблицы.

Ну это везде так, на сколько я помню. В MS SQL точно.
А вот приписывают ли ещё в листьях обычных индексов рядом с номером PK и номер страницы?

чукотский мальчикIndex SeekИмеется ввиду кластерные таблицы в определениях Oracle?В Oracle нет кластерных таблиц. Есть кластеризованные таблицы (clustered table)
Точно, спасибо. Залетало все в 2 раза быстрее.