Владимир Ситников — B-tree индексы в базах данных на примере .NET Entity Framework и PostgreSQL

Друзья, я рад приветствовать вас здесь, на втором дне нашей конференции .NEXT.

В этом зале сегодня будут очень интересные доклады про базы данных, про производительность, все, с чем вы сталкиваетесь, скорее всего, каждый день и выполняете задачи на своем рабочем месте.

Для того, чтобы представить следующего нашего первого спикера сегодня, я вам расскажу про один маленький нюанс.

Я очень часто провожу собеседование, и один из вопросов, касающихся баз данных, у меня звучит так.

Представим, что у тебя есть две таблицы, вернее одна таблица, и в ней очень много данных.

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

И что ты сначала сделаешь?

Ты сначала скопируешь данные, а потом повесишь индексы?

Или сначала повесишь индексы в новую таблицу и начнешь копировать данные?

И мне кажется, что сегодня вы точно услышите правильный ответ в нашем первом выступлении.

Владимир, тебе слово.

Спасибо огромное.

Привет, друзья.

Я не думал, что настолько классная подводка будет.

Я заранее всех приглашаю в дискуссионную зону, потому что на этот вопрос есть как минимум два правильных ответа.

То есть можно два варианта сказать, когда один вариант будет хорош, второй плох.

И, разумеется, если вы предложите оба варианта, работа вам обеспечена.

Поэтому давайте обсудим в дискуссионной зоне.

Но, тем не менее, битреиндексы, собеседование.

И при чем вообще все это?

При чем здесь подгрез?

Наверное, невозможно избежать базу данных.

Она есть у всех в том или ином виде.

И давайте разберемся, что будет на докладе.

На докладе мы рассмотрим, как работает B3 индекс.

Это самый популярный, самый типичный, это дефолт индекс, который вы создаете, если вы в принципе создаете индекс.

Мы рассмотрим, как индексы нужно применять для запросов и как создавать или использовать многоколоночные индексы.

Не самая простая тема, но вот как мы вообще обычно код пишем, мы берем C-sharp код, объявляем класс, создали поля, вдруг увидели, у нас есть, наверное, поиск по имени пользователя, и мы такие бах, добавили аннотацию, и появился у нас индекс.

Давайте проведем небольшой опрос такой, у кого, в принципе, на проекте есть база данных или сталкивался.

Держим, держим, держим руки.

Половина зала, больше, наверное, даже почти все.

Так, теперь опускаем индекс, держим руки, кто хотя бы раз сам создавал индекс.

Держим, держим руки.

О, все создавали.

А теперь еще держим руки те, кто создавал и понимает, зачем и какой индекс они создавали.

Так, все создавали осознанно.

Это очень классно.

Тогда мы доклад проведем в режиме

Вспомним то, что мы и так знали.

Давайте так настроимся.

И первый же вопрос.

А для чего вообще нужны индексы?

Это, кстати, третий ответ на вопрос.

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

Может, не надо?

Просто таблица есть, и все, индекс не нужен.

Итак, индекс обычно нужен для быстрой выборки.

Вот это обычное его использование, на самом деле есть другие.

Какая вообще может быть быстрая выборка?

Например, поиск по ID, по какому-то там ключевому полю, по значению, по строке почему-нибудь.

Это может быть поиск по двум колонкам, это может быть поиск по диапазону, то есть когда мы сказали значение больше чем, но и тут наши любимые прелести строки или числа, потому что они сортируются немножко по-разному, всегда 1, 10, 2, 3.

Индекс полезен для поиска по диапазону.

Мы сейчас говорим про самый простой B3 индекс, то есть география и прочее.

Вчера был прекрасный доклад обзорный, я туда давайте вас адресую.

Иногда полезно найти первые несколько или несколько

Последние несколько или в середине несколько значений, близких к нужному нам значению.

Тоже посмотрим, как это получается.

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

Итак.

Примерно все это, вот краткий пересказ доклада.

Можно посмотреть на такой страничке, я крайне рекомендую, она, казалось бы, вы наверняка ее видели, наверняка с ней сталкивались, но там есть много всего.

Возможно, вот даже с текущими знаниями вы откроете, увидите там раздел, который вы раньше не замечали просто.

И один из таких примеров, один из таких разделов, это вопрос на закрепление материала.

Там реально есть квиз.

Вы открываете пять вопросов, выбираете базу данных, и вам говорят, о, поздравляем, вы эксперт в Postgres.

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

Но вопросы хорошие, поэтому я рекомендую, я проверял.

Но прежде чем что-то оптимизировать и...

Создавать индексы нужно понять, зачем мы это делаем.

Ну, как бы, ну, зачем индексы?

Например, мы хотим оптимизировать скорость выборки.

Select оптимизируем.

Или мы, например, оптимизировать хотим модификацию данных.

Как правило, когда оптимизируем одно, другое страдает.

Бывает, наверное, какая-то универсальная оптимизация, когда какой-нибудь лишний код выпилили, и у нас все полегчало.

Но, как правило, что страдает?

Если нужно оптимизировать все вместе, и запросы, и модификацию, то беда, печаль, огорчение, ну, сложная работа, нужно разбираться конкретно.

Поэтому сейчас не очень рассматриваем, но вот давайте рассмотрим простой такой индекс, дефолт индекс, какой он должен быть.

И этим вопросом задался

Значит, ученый в 70-м году изобрел вот эту, собственно, механику B3 индекса.

Ее чуть потом улучшили, и буквально с 72-го года мало что менялось в концепции.

Но какие же у него были вопросы?

Зачем он делал?

Во-первых, индекс должен просто быть.

То есть это не должен быть какой-то тюнинг, еще что-то.

Вот просто мы его создали, и все.

Он должен всегда быть оптимальным.

То есть мы не должны пересоздавать его, мы не должны...

обновлять его, мы не должны его тюнить, он просто должен быть.

Это хороший индекс такой.

А что значит оптимальный?

Тоже такой понятный режим, но давайте чуть-чуть.

Например, индекс должен работать хорошо для больших данных.

Миллиард строк, индекс должен работать.

Триллион строк, индекс должен работать.

Но не надо забывать про маленькие данные.

Если...

данных мало, то он все равно должен хорошо работать.

Потому что бывают индексы, которые прекрасно работают только на больших данных, а на маленьких, ну, таких средненьких, не очень.

B3 себе этого не может позволить.

Нужен алгоритм, который прям хорошо работает.

И у нас система должна

позволяет многопоточный доступ.

То есть мы должны менять, изменять, удалять, добавлять строки, которые между собой не пересекаются.

Разумеется, пересекающиеся строки — это отдельная проблема, тем не менее.

Итак, у нас есть три такие критерия оптимизации.

Давайте индекс создадим, и на какую же мы проблему наткнемся?

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

Как оптимизировать память?

Ну, кому интересно, можете соседний доклад посмотреть в соседнем зале, прямо сейчас идет.

Но давайте посмотрим, что же делать, когда у нас нет памяти, не хватает.

И базы данных все разбивают индексы по каким-то блокам, страницам.

В Postgres это называется страница.

Страница имеет размер 8 килобайт, и вот на ней размещаются данные.

она может иметь другой размер, если вы соберете свою сборку.

Но, разумеется, никому это никогда не надо, поэтому достаточно 7-8 килобайт.

Давайте просто так считать, что это такой сверху данный размер.

мы можем в наши 8 килобайт поместить сколько-то записей, сколько поместится.

И когда мы попробуем вставить записи в индекс, ну, например, пятерочку мы взяли и добавили, и следующую четверочку взяли, добавили, девяточку взяли, добавили.

Все хорошо пока идет, да, все нормально.

Мы, кстати, можем сразу добавлять записи в отсортированном виде.

Это нам позволит быстрее искать бинарный поиск, наше все.

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

То есть никто сами сырые данные не пытается каждый раз пересортировать.

Отдельно хранятся данные, отдельно хранятся индексы в отсортированном порядке.

Но, если интересно, можно обсудить в дискуссии.

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

Куда?

Куда делать?

Ну, понятное дело, нам надо новую страницу, и вот мы такие взяли и разделили нашу исходную на две.

Ну, потому что мы добавили новую, и туда взяли, добавили немножко старого.

Как именно переносим данные?

Вопрос тоже интересный.

Каждая база данных по-разному это решает.

Наверное, надо сделать какой-то баланс, ну, типа 50 на 50.

Логично, да?

То есть plane туда, plane туда.

Будет

Одинаково плохо в худшем случае.

Поэтому берем, разделяем.

И помним, кстати, что строки могут быть разной длины, если это имя какое было длинное.

Может оказаться одна запись на полстраницы.

Вы можете подумать, что будет, если одна запись больше страницы, там запись больше 8 килобайт.

А мы как бы пытались ставить.

Ну, давайте пока опустим этот вопросик.

Но, может быть, придет в голову еще.

Мы, значит, взяли нашу единичку, добавили на первую страницу, и у нас все хорошо.

Смотрите, 1, 4, 5, 9, все стартеровно.

Мы такие взяли, между собой их связали, и у нас уже появился связанный список.

Здесь кто-то может заметить, что, блин, это долго будет, если мы будем ходить постоянно так по цепочке, особенно три строки, а если миллион, то у нас бесконечный цикл получится.

Поэтому мы создаем еще одну страницу над текущими.

Ну, то есть мы наш 2 связали под один корень, и там добавили какое-то граничное значение, которое нам будет показывать, куда нужно ходить.

Ну, вот мы эту страницу добавили, и у нас, смотрите, получился индекс.

Вот это прям B3 индекс.

Не совсем это B плюс 3.

Если вы вдруг заинтересуетесь, посмотрите статьи, какие бывают индексы, ну, оптимизации десятки разных,

И первая самая версия называлась B3, потому что так захотел автор.

Но в чем был фундаментальный недостаток?

В том, что в первой версии, и вот это, кстати, очень большая засада, если вы, допустим, готовитесь к собеседованию, или вы пытаетесь просто понять, ну как оно там, да, в Википедию открываете, там B3,

Нелегко понять, чем отличаться от B+.

А реально ни в одной базе B простого не используется.

Везде плюсы.

К сожалению, этот самый B-sharp дерево не изобрели пока.

В чем разница?

Разница в том, что в B-дереве значения хранятся только в самой нижней части нашего дерева.

То есть хранятся значения только в самом низу.

А все промежуточные узлы нужны только для того, чтобы найти путь к нашему листовому блоку, нашей листовой странице.

Вот такая оптимизация.

Она позволяет гораздо проще модифицировать данные.

Итак, давайте попробуем найти в нашем дереве, как вообще оно работает.

Значит, если у нас значение не превышает пятерку, то мы идем влево.

Если оно вдруг равно пятерке или больше, то мы идем вправо.

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

Но такая механика довольно нехитрая.

К сожалению, к счастью, исходники Postgres доступны.

К сожалению, там очень часто встречается ситуация, что одна и та же переменная используется в разных смыслах, в разных местах.

Потому что экономят место на диске и не хотят выделять дополнительные поинтеры.

И вот там действительно иногда запутано, куда что указывает.

Но механика примерно такая.

Давайте возьмем таблицу.

Понятно, я надеюсь, тут диски сад, надо бы вообще быстрее рассказывать.

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

миллион или сколько-то там записей.

Соберем статистику по этой таблице и запустим самый, значит, сложный запрос.

Это поиск первичного ключа.

ID равно 1.

Выбираем несчастные наши две колонки.

Один им, других нет.

И что мы видим?

Мы видим результат базы.

База говорит, один, и все нормально.

Вопрос, как база этого достигла?

Как она вообще искала?

Полностью перебирала таблицу или не полностью?

Мы можем узнать, если прогоним explain-analyze.

Берем explain-analyze,

Нам вот что-то такое показывают, и тут мы видим, написано индекс, все хорошо, индекс, даже название индекса, первичный ключ.

Видим условия, по которым мы искали, какие-то значения, но можно так присмотреться, увидеть, что, например, там фактическая длительность работы запроса была, даже сколько базе пришлось времени потратить на подготовку этого запроса.

И здесь я попробовал немножко усыпить вашу бдительность, но я надеюсь, что кто-то все-таки задался вопросом.

Слушайте, мы как бы в индексе хранили первичный ключ.

Первичный ключ состоит из ID.

Да, вот там только ID.

В результате запроса у нас вернулось ID и имя.

Вот кто-то тут нас обманывает.

Откуда это взялось имя, его не было в индексе?

Вот.

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

Значит, как она работает в Postgres?

Вот все точно так же, как было, я пока вас не обманываю.

У нас данные хранятся в таблице.

Таблица отдельно в таких же блоках, страницах данные лежат.

Разница в том, что в таблицу данные добавляются как попало.

Реально, как они пришли, так они и попали.

Поэтому они там совершенно не отсортированы.

Если вы их специально не отсортируете.

Есть, кстати, команда.

Или если вы, например, не отсортируете их при вставке.

Когда мы будем вставлять данные, мы можем вставлять их тоже в таблицу сортированно, чтобы побыстрее искались.

Это отдельный вопрос.

Но индекс указывает на таблицу.

То есть записи в индексе говорят, где в таблице лежит эта запись.

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

И выборка из индекса, и проход в таблицу.

Поэтому нужно понимать, что если вы видели индекс scan, то это плохо.

Но так просто давно это было сделано, и лет, наверное, только через 15 придумали оптимизацию, чтобы в некоторых случаях не ходить в таблицу, если, например, все данные в индексе есть.

Это называется индекс-онли-скан.

Поэтому если вы видите индекс-онли-скан, это лучше, чем индекс-скан.

Но, тем не менее.

А ключевой момент в том, что индекс сортирован.

То есть он позволяет вот прям искать.

Второй момент, что страницы в индексе ссылаются друг на друга.

То есть там есть справа налево, слева направо, сверху вниз ссылки.

Ну, сверху вниз это, наверное, очевидно, что они в дереве есть в каком-то.

Но справа налево это чуть менее очевидно.

Мы сейчас увидим, где это нам нужно.

И, значит, листья ссылаются на таблицу.

Таблица вот простая.

Давайте я вас спрошу, а сколько занимает чтение памяти?

Чтение, вот кто может сказать или так помнит примерно хотя бы?

Так.

В чем-нибудь, в миллисекундах.

В миллисекундах занимает чтение памяти.

Вот сколько?

Зачем я сказал, что я знаю?

Зачем он спросил?

Возможно, вы пришли с соседнего доклада, и там наверняка рассказывали.

Есть замечательная страница, справочник, много вариаций, чисел, которые должен знать каждый программист.

Особенно на C-sharp.

Но вообще каждый.

Что это такое за числа?

Это числа, которые характеризуют наше железо.

Железо, на котором мы живем.

Кстати, вчера был классный доклад по железу.

100% CPU — это проблема или нет?

Значит, какие у нас там числа есть?

Это...

Обращение к крышу, обращение к памяти, обращение к диску, блокировка, неблокировка.

Наверное, можно творчески использовать.

Если вы понимаете, что в вашей бизнес-операции два чтения памяти, три блокировки, вы такие раз и посчитали микросекунды.

Но в нашем случае, в случае индекса, важны две штуки.

Это обращение к памяти порядок 100 нс и обращение к диску.

Но зависит от того, какой диск у вас.

Это либо миллисекунды, либо SSD побыстрее.

Но главное, что память намного-намного быстрее.

И диск намного-намного медленнее.

И каждый раз, когда мы загружаем новую страницу нашего индекса, идем сверху вниз, то мы читаем с диска.

Скорее всего, если мы не обеспечили, что у нас весь индекс памяти лежит, это отдельный тикет.

Сделать грелку, которая будет прогревать индекс и грузить его в память.

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

Это надо узнать.

А как?

Как узнать, сколько дисковых операций у нас будет в нашем плане выполнения или в реальном выполнении запроса?

К сожалению, по умолчанию не выводится.

Поэтому пишем explain не просто analyze, но еще и buffers добавляем.

И вот это самое buffers нам

добавляет информацию про то, сколько будет прочитано данных.

Но, к сожалению, конечно, если они закэшированы в Postgres, или закэшированы в операционной системе, или закэшированы в кэше диска, мы отсюда не узнаем.

Но мы хотя бы будем знать, что, например, смотрите, такой запрос, сколько-то тысяч обращений к страницам делал.

И если мы вспомним предыдущую цифру, одна страница 10 миллисекунд, иначе говоря, 100 страниц в секунду,

Вот 100 — это универсальное число.

100 строк в секунду мы можем ожидать скорость работы нашего индекса, условно говоря.

И мы тут увидели 6300, и это примерно значит 63 секунды, потому что на 100 поделили.

Вот такой запрос, может, в худшем случае.

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

Но прекрасная такая вот механика.

Поэтому...

Мы, значит, взяли, индекс создали и посмотрели, что у нас получилось с нашими страницами и буферами.

Вот они как бы грузятся или нет.

И здесь увидели, что 3 прочитали, 4 страницы, грубо говоря, прочитали.

Все, индекс в данном случае хорошо сработал.

Поэтому...

Советую запускать explain не просто analyze, но из buffers и смотреть на то, сколько диска у нас читается, сколько дисковых операций у нас происходит.

Конечно, идеальный способ проверить это сбросить все кэши, перезагрузить операционку, перезагрузить storage, ну или сделать какие-то много сложных запросов, чтобы и во всех кэшах они тоже ушли эти данные.

Но даже когда данные прокэшировались, то вот такая цифра позволит оценить, ну а как будет в худшем случае.

Итак, давайте посмотрим, а сколько у нас будет в худшем случае, как наш индекс работать.

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

Внимание на экран.

Логарифм впервые в истории пригодился.

Но 5-6 уровней нашего индекса, не больше, даже при очень большом количестве строк.

И что, кстати, очень классно, это то, что эта глубина не зависит от данных.

Она зависит только от количества и объема данных.

То есть от того, что мы вставляли их в одном порядке, в другом.

То есть там нет вот этого дисбаланса.

которое бывает, если мы какое-нибудь красно-черное дерево возьмем, начнем его создавать.

Красно-черное тоже балансированное, кстати.

Если мы простое бинарное дерево попытаемся создавать, оно может оказаться небалансированным.

База хорошая.

Давайте поищем по диапазонам.

Мы взяли, запрос написали, и у нас написано ID больше 5 и меньше 8.

Посмотрим, как это в плане будет.

В плане это точно так же будет, на самом деле, ID больше 5 и меньше 8.

Здесь база иногда творчески переосмысливает, и надо так смотреть, ну, а типа вообще то ли мы написали или нет.

Но иногда можно прям увидеть.

И очень хорошо, когда вот эти предикаты, которые мы написали, в индекс прям так и попадают.

И мы видим, что у нас по-прежнему 4 страницы, кстати, смотрите, 4 страницы, но айдишников там сейчас тоже неизвестно сколько, но как это происходит в нашей структуре деревянной, да, вот если у нас есть индекс, мы спустились по дереву, нашли пятерочку, пятерочку нашли, и что же мы будем делать дальше?

Типичное недопонимание, которое, ну или вот неправильно, или даже объяснение я слышал, это, ну смотрите, мы нашли пятерочку, потом мы еще раз спускаемся и ищем шестерочку, еще раз спускаемся и ищем восьмерочку и так далее.

На самом деле у нас страницы хранят сортированные данные, поэтому мы нашли пятерку, идем вправо, ну они вправо, можно идти.

И вот тут мы как бы все, дальше не можем.

Но есть ссылочки между собой, поэтому можем ходить просто вправо, взяли ссылочку, прошли, открыли новую страницу.

Вот это и есть тот самый физик ларит на диске, который 10 миллисекунд в крутящемся диске или какие-нибудь там микросекунды, ну сотни микросекунд в SSD случае.

И дальше продолжаем читать.

Мы такие прочитали семерку, восьмерку, и получается, что мы довольно с небольшими накладными расходами можем читать по диапазону.

Здесь можно заметить, мы читали слева направо, а можно точно так же читать справа налево.

Не обязательно ограничиться восьмеркой в нашей правой границе, то есть можно сказать «дай мне пять записей, которые больше пяти».

При этом запрос будет работать, даже если пятерки как таковой не было.

То есть мы такие даем 5 записей, которые больше 5,5.

Индекс точно так же будет работать.

Мы спустимся до места, где должна была лежать 5,5 наша ячейка и пойдем вправо.

Поэтому помним, что сканировать можно и по возрастанию, и по убыванию.

Заходим сверху вниз в индекс в один раз, потом идем слева направо.

В клиническом случае, к сожалению, можно слева направо идти весь индекс.

Прямо с самой левой границы до самой правой границы.

И вы не узнаете на самом деле про это, потому что это будет называться индекс-скан.

В Postgres.

В других базах иногда это чуть более понятно.

В Oracle это прямо Index Full Scan называется.

В Postgres Index Scan.

Надо следить за диапазонами, ну или за физико-ридами, которые у вас происходят.

И данные, если их не было в индексе, по-прежнему тянем из таблицы.

То есть мы ходим, и это что значит?

Это значит, что если у нас запрос возвращает, например, 10 тысяч строк, то это потенциально 10 тысяч заходов в таблицу, и это потенциально 10 тысяч обращений к случайным страницам.

И это значит 100 секунд.

Ну, типа 10 тысяч строк, и уже 100 секунд.

База тормозит, да.

Ну, .NET не тормозит, а база, к сожалению, может.

Если вот такой запрос писать.

Если данные заранее отсортировать, то, конечно, они могут не в совершенно разные страницы попасть, а в одну.

Я пытался как-то формулу вводить, нашел ничего лучше, кроме как задачку.

Значит, купи 10 чебуреков, собери кошку.

То есть сколько случайных блоков мы прочитаем, когда прочитаем 10 тысяч строк из таблицы?

Неизвестно.

Давайте посмотрим, как же у нас база, значит, все-таки... Как можно увидеть, что мы читаем что-то не то?

И очень полезно, я рекомендую присматриваться к тому, какие дополнительные данные появляются в плане выполнения.

Смотрите, если мы читали только ID...

вот просто ID, имя не выбирали, то база пишет, что у нас индекс only scan.

Ну, казалось бы, все нормально.

То есть мы такие прочитали ID, получили ID, что могло пойти не так.

К сожалению, мы могли запустить другое время.

День прошел, мы запустили еще раз, и у нас получилась вот такая штука.

Тоже индекс only scan.

Но еще появилось что-то написанное hip-hotches.

Можно вообще не заметить, а можно заметить.

Можно прочитать, что такое hip в Postgres и узнать, что это таблица.

Почему-то таблицу называют хипом, и почему-то оказывается, что нам нужно иногда ходить в таблицу.

И это иногда случается тогда, когда в таблице кто-то меняет данные.

К сожалению, в Postgres индекс сам по себе не хранит информацию про удаленные строки.

И если строку кто-то удалил или изменил, то индекс все равно по-прежнему указывает на старую строку.

Посмотрим еще.

И оказывается, что написано это index-only, но по факту работает примерно так же, как обычный index-can.

То есть мы ее в индексе нашли, а потом сходили в таблицу.

Отсюда вывод какой?

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

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

Запретный вопрос или нет?

Я вам предлагаю такой ответ.

Я вам сейчас расскажу, как крутится би-дерево.

Оно, не би-дерево, а би-дерево.

Очень классно.

Это прям...

Я очень люблю рассказывать.

Почему?

Потому что тривиальный алгоритм, который классно работает.

Смотрите, вот мы берем и в такое дерево добавляем семерочку.

Как мы это делаем?

Ну, возьмем семерочку, добавим наверх, а потом подумаем, направо она пойдет или налево.

Вот на самом деле нет.

И вот так, так не работает.

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

Ну, в смысле, семерочку добавил наверх.

Гениальность бидерева заключается в том, что данные растут снизу.

они добавляются вниз.

Иными словами, для того, чтобы добавить семерку, мы сначала находим, а куда бы эта семерка должна была попасть, если бы она уже была в дереве.

То есть мы такие идем, ну, она больше пятерки, значит, где-то справа, значит, там.

Значит, туда нужно добавлять семерку.

И добавляем именно уже самый-самый низ.

И вот помните, я говорил, b плюс дерево, оно значение хранит в листах.

И вот как раз позволяет нам сначала найти самый-самый последний узел, и мы туда добавим.

Давайте добавим.

Как добавим?

Они лезут.

Мы делим нашу страницу.

Так оказалось, что слева 3, справа 2.

Перекинули немножко значение направо-налево, добавили семерку, привязали между собой узлы и новодобавленную страницу тоже привязали наверх.

У нас получилось вот такое дерево.

Мы взяли, добавили, и смотрите, у нас повезло, что девятка поместилась наверх, могла бы не поместиться собака.

И что бы тогда мы делали?

Если бы девятка не поместилась, то мы бы тогда верхнюю страницу разбили пополам и образовали еще одну корневую.

Поэтому интересный момент, что дерево не от корня растет до корень наверху, а растет оно снизу.

И в такой конфигурации у нас путь от верха до самой нижней вершины занимает всегда одинаковое количество шагов.

Одинаковое количество шагов гарантирует нам то, что поиск будет одинаково быстрый.

Поэтому крутить дерево не надо, надо просто иногда составать родительские или корневые узлы.

На практике при стандартных размерах, если у вас значение очень длинное, то надо уже подумать, может быть, его надо как-то отсекать.

У нас были случаи, когда значение превышало 4000 символов.

Ну, разумеется, никто по такому не ищет, а ищет только по маленьким.

И мы поэтому индексировали под строку substr от первых 50 букв.

Приходится, правда, потом и в запросах это писать.

Но зато индекс получается компактнее.

Миллион строк, три уровня.

И вот это все хорошо с числами, но давайте попробуем другие типы данных туда положить.

Допустим, UUID.

И если мы создадим таблицу с числами, с ID, то у нас будет некая разница.

Ну какая разница?

Разница простая.

Bigin занимает 8 байт, а UUID занимает 16 байт.

И, казалось бы, бегантов в два раза больше поместится, там высота индекса будет.

Ну, не в два раза, конечно, там логарифм, но не суть.

Вопрос.

Как вы думаете, что будет работать быстрее?

Давайте попробуем.

Кто за UID?

Вот кто использует UID для первичного ключа?

Вот так.

UID, там первичный ключ в базе, да?

Хорошо.

Беганты.

Кто за беганты?

Беганты наше все, UID нет.

Так, значит, 30% и там, и там, непересекающиеся.

Еще 30% сидят и смотрят, что из этого будет.

Да, что делать, что делать?

Ну, давайте посмотрим.

Вообще, первая такая мысль, что беганты будут работать вроде как побыстрее, а не компактнее.

Ну, давайте посмотрим, как у нас система будет переживать нашу массовую ставку.

Значит, товарищ собеседующий сказал, мы вставляем.

Ну, давайте вставим.

И мы такие берем и вставляем.

Ну а как еще?

Ну вот у нас бегенты.

Мы берем последовательность и из нее выбираем данные.

Мы берем юиды.

Откуда юиды брать?

Кстати, если кто-то знает, вы такие, я молодец, я знаю, откуда брать.

Но откуда?

Мы берем генрандом юид и, значит, тоже его вставляем.

У нас получается примерно такой индекс.

Числа заполнены куда-то.

И в чем получается интересная особенность?

Когда мы вставляем числа из последовательности, индекс всегда отсортирован, поэтому всегда примерно такое выглядит, но числа будут попадать в правую границу, в самую правую границу.

И смотрите, если мы вставляем из последовательности, то левую часть нашего индекса мы вообще даже не будем трогать.

Она не нужна, память на нее не расходуется, из кэше она уйдет.

И актуально,

Для модификации будет только правая часть.

Я тут так схитрил, да, я там select не рассматриваю, потому что если кто-то select, допустим, единичку, то эта единичка доблестно в кэш тоже попадет.

Но, тем не менее, именно операция вставки, она будет так растить наш индекс вправо-вправо-вправо, и довольно немного надо памяти для того, чтобы это все переварить.

Если же мы говорим про UUID,

то про них, к сожалению, так не скажешь.

Особенно про рандомные.

Если вы взяли простой, ну типа простой рандомный UID, он, к сожалению, рандомный.

Это будет означать, что он будет попадать в разные места нашего индекса.

Ну то есть они как бы не монотонно растут.

Они случайные, казалось бы.

И это значит, что они будут попадать в случайные места нашего индекса.

А мы же помним, что для того, чтобы вставить строку, у нас сначала найти строку, а у нас строки нет.

То есть мы должны сначала найти вот эту страницу, где нам нужно добавить запись, и, типа, привет, получите, распишитесь по physical read или 2 на каждую вставку.

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

Это будет много чтений.

Это будет тяжело для записи, потому что вы, ну, типа, добавили одну строку, а пишете блок, ну, страницу 8-килобайтную.

А в Postgres есть еще и full-page writes.

Первая модификация страницы пойдет в wowlog целиком.

То есть вы добавили 100 байт, у вас записалась страница индекса, и она еще бахнулась в wowlog.

И про это все можно посчитать вот здесь.

Значит, чем там заканчивается история?

Их история заканчивается очень просто.

Померили юиды и получили, что скорость вставки в 6 раз ниже.

Объем записываемых данных больше.

Ну, то есть вы в каком-нибудь облаке купили диск, и у вас там идет и опсов гораздо больше, ну, из-за того, что юиды неправильные.

Вот какие-то не такие юиды.

Вопрос, что же с ними делать?

Что делать с юидами?

Теперь вспоминаем, кто знает, кто не очень вспомнил.

Есть правильные юиды, седьмые.

Суть седьмых UID в том, что они time-based, то есть они более-менее монотонно растут.

Там есть кусочек в начале UID, который содержит время, и у нас проблема как бы сводится к предыдущей.

Поэтому если у вас где-то есть UID, которые вам не важны какие, можете попробовать поменять генератор, и система станет работать быстрее.

Это весьма такой бесплатный хак.

Есть еще вариант запасаться SSD.

Но это не всегда работает.

Значит, одна из самых сложных вещей, и вообще обычно у нас все хорошо работает, но вот один кейс как-то не очень.

И вот я советую вспоминать, а как в вашей системе обрабатывается удаление данных.

Потому что insert, update сделать гораздо проще, чем delete.

Разные API даже иногда делают.

И давайте посмотрим, как же удаляются данные из B3 индекса.

Вот у нас был такой индекс.

И мы удаляем строку.

Например, давайте удалим девяточку.

Я уже проговорился, что в Postgres индекс не хранит информацию про видимость.

Но это что означает?

Означает, что в таблице такой флажок.

Эта строка удалена.

И все.

И другая строка удалена.

И третья строка удалена.

И вот они так лежат мертвым грузом.

Вот прям мертвым грузом.

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

И вот теперь мы на старое место уже можем какие-то новые данные вставлять.

И вторую почистили, вот это как-то асинхронно проходит.

И третью мы, значит, строку почистили.

А в индексе, заметьте, все по-прежнему находится на старом месте.

Это означает, что если в такой конфигурации, это прям разумная конфигурация нашей базы.

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

Но это прям реальная операция.

Это печально.

Потом, значит, наш автовакуум будет полностью просматривать индекс и чистить из него, значит, битые ссылки, которые уже точно никуда не ведут.

Мы почистили единичку, пятерку, девятку, и после этого у нас вот такая система образовалась.

Записано три или одно число по факту, просто четверочка записана, но мы используем кучу пустых блоков.

Это не всегда плохо.

От этого можно избавиться, если сделать rebuild индекса, конечно.

Но эти страницы могут переиспользоваться, если вы добавляете записи.

Например, добавляете число больше 5, это число пойдет в правую страницу индекса.

Меньше 5 в левую.

Поэтому что стоит учитывать?

Учитывайте, что у вас мусор копится.

И сам по себе индекс не хранит информацию по видимости, поэтому индекс scan или индекс only scan не всегда хорошо работает.

Если мы удаляем какую-то запись из таблицы, то это не значит, что мы ходим по всем индексам и там обновляем значения.

Удаление довольно быстро работает.

Но в индексах копится мусор.

К счастью, если вы не очень надеетесь на автовакуум, то обновляйтесь на 14+.

В Postgres 14 Plus сделали оптимизацию, которая выполняется в момент разделения блоков.

И вообще Postgres пытается всячески избежать именно разделения блоков,

Потому что делить блок — это надо добавлять куда-то его, привязывать к дереву.

Если можно почистить мусор, не деля блок, то это очень классно.

И оптимизация, которая называется bottom-up deletion, она что делает?

Она в индексе, если видит строку, которая указывает на мертвую строку в таблице, то эту строку зачищает сразу, и на освободившееся место мы можем уже вставлять строки.

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

Возможно, у вас прям так и работает.

Значит, давайте дальше двигаться.

Внешние ключи, они бывают.

Мы такие нашу таблицу вспомнили с пользователями.

Возможно, у нас есть таблица с проектами, и, возможно, у нас даже пользователь указывает на проект.

Это значит, что пользователь в рамках какого-то проекта работает или создан.

Мы можем создать внешний ключ, что означает, что не будет мусора в таблице «Users».

Но, к сожалению, PostgreSQL не создает индекс автоматически по внешним ключам.

И это значит, что надо не забывать их индексировать.

Но для чего?

Иногда можно не индексировать.

Вот, кстати, тоже хороший вопрос.

Ну, всегда ли нужно индексировать?

И дальше поехали еще час обсуждать.

Но в таком простом случае можно не думать и всегда создавать индекс.

Почему?

Потому что, во-первых, по умолчанию нет.

Во-вторых, если мы будем удалять проект, нужно удалить всех пользователей этого проекта, а мы не хотим блокировать таблицу целиком.

И хотя бы этого уже достаточно.

Мы вставляли, удаляли, а давайте обновим.

Как обновляется индексированная колонка?

Мы добавили запись в индекс про эту самую колонку.

А, да.

Добавили запись в индекс про эту колонку, а старая осталась мертвым грузом.

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

А старая строка осталась, пока ее вакуум не соберет.

И это плохо, потому что новые строки добавляются во всех индексах.

То есть, если у вас на таблице 15 индексов, вы обновили колонку, которая была индексирована хоть каким-то одним,

то вы создали во всех 15 индексах новые записи.

Ну, то есть один апдейт — обновляется индекс.

Это плохо.

Поэтому обновлять индексированные колонки — это больно.

Ну, я не знаю, кроме как не обновлять их, но иногда приходится.

Значит, если вы обновляете неиндексированную колонку, то там чуть проще.

Потому что если эта строка новая, измененная, помещается в ту же самую страницу на месте, то база ее там оставляет рядом, и старые индексы не обновляются.

То есть если вы обновляете неиндексированную колонку, это прямо хорошо работает и не требует обновления всех индексов.

Если строка при этом, конечно, не поместится, то, ну, в связи с задачей предыдущей, во всех индексах добавили все новые записи, и старая строка остается мертвым бурзом, ждет своего автовакуума.

Какой здесь вывод?

Ну, вывод простой.

Не надо создавать индексы на каждую колонку, потому что наверняка захотите ее обновить, а тогда придется индексы менять.

Давайте дальше двигаться.

Если у нас данные чуть-чуть растут-растут, может потребоваться многоколоночный индекс.

Но давайте рассмотрим, как.

Вот у нас есть таблица с пользователями, и мы добавили туда колонку со статусом.

Какой может быть статус?

Давайте, например, возьмем такой.

Есть активные, есть неактивные и чуть-чуть таких неопределившихся.

И таблица без запроса – это время на ветер.

Надо запрос знать, потому что индекс без запроса создать невозможно точно.

Индекс без запроса вам не создать.

Вот такой запрос.

Мы ищем неопределившихся пользователей по имени.

Два условия.

И статус, и имя.

Барабанная дробь.

Уже кто-то прикидывает, какие индексы.

Но вот я давайте угадаю пару вариантов.

Значит, имя, статус или статус, имя.

Вот.

Так, ну такие варианты.

Так, давайте проголосуем.

Вот первый вариант.

Имя, статус.

Кто за такой вариант?

Имен много, они уникальны.

Уникально, у кого-то надо ставить начало индекса.

Ну а как еще?

Так, хорошо, спасибо.

Ну там пять человек я вижу.

Наверное, слегка не вижу.

Статус, имя.

Сначала они уникальны.

О, кстати, больше.

Человек 15, наверное, 20.

Короче, все за статус 7.

Очень классно.

Так, хорошо.

Свой вариант.

Вот если у кого есть свой вариант еще.

Так, еще свой вариант.

Так, больше одного своего варианта.

Держим руки.

Больше двух вариантов.

Больше трех.

Четырех, пяти.

Так, ура.

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

Но давайте действительно свой вариант сначала рассмотрим, потому что вот это сложно, это реально сложно.

Давайте простой вариант рассмотрим.

Смотрите, если нам, допустим, не нужны активные, которых в таблице много, и мы их не хотим просто в индексе хранить, мы можем так раз написать «where» статус «не наш».

И это очень классно, потому что любое условие практически SQL задали, и индекс сократили.

Разумеется, все эти накладные расходы, вот помните, неиндексированная колонка появилась, то есть она не требует обновления индекса, но записи не требует в индексе.

В общем, одни плюсы.

Это такой вариант.

Еще есть вариант include колонку делать.

Немножко по-другому будет работать, и уже надо чуть больше запросов рассматривать, чем только один.

Но давайте вот эти варианты немножко сейчас запаркуем и посмотрим, как же у нас будет работать вот такой, например, индекс.

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

он не работает как вложенные индексы.

Он работает как один индекс.

Как один индекс, когда у нас данные отсортированы в том же самом порядке, в котором мы бы писали эти колонки в order by.

Иными словами, если у нас есть вот такой запрос, например, дайте нам данные с таблицы order by по статусу имени и, например, верните 5 строк, то для такого запроса хорошо подойдет индекс статус имя.

Я повторю, потому что я несколько раз объяснял уже, и обычно люди не сразу понимают, что количество записей и объем индекса не зависят от порядка колонок.

К сожалению, зависят, но будем считать, что не зависят.

Значит, в дискуссии можно обсудить.

Не зависят.

Грубо говоря, не зависят.

Зависеть будет только скорость работы.

Даже если в запросе всегда указаны и имя, и статус.

Даже когда и имя, и статус.

Значит, почему?

Потому что, смотрите, у нас запрос, вернее, вот такой индекс status name, это значит таблица отстроена по статусу и по нейму, а в обратном порядке, легко понятно, в обратном порядке.

Давайте посмотрим, как это выглядит.

У нас, допустим, есть, значит, статус.

Имя.

Ну, вот слева.

Смотрите, все активные легли рядом, все неопределившиеся легли рядом в одну страницу.

И справа.

Ну, там не совсем так получилось.

Там у нас как бы такой микс.

В одной странице и активные, и неактивные, и во второй странице активные, неактивные.

Если в запросе нам в первую очередь нужны были неопределившиеся, мы выполнили запрос, не знаю, допустим, тест 2 мы загрузили,

И это что получилось?

В одном случае мы загрузили страницу, пендинг с тест-2, левая и нижняя.

И у нас 8 килобайт памяти емко хранятся только те, которые не определились.

Они могут подойти для следующего запроса.

То есть один запрос в вакууме будет работать абсолютно одинаково.

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

Если же мы создали в данном случае name статус,

то в кэше будут лишние записи активные, которые не нужны.

Разумеется, мы могли их просто исключить aware условиям, которые мы с самого начала сказали.

Давайте так посмотрим.

Значит, тут кто-то может заметить.

Простите, коллега, но если у нас есть запрос по имени, статус не знаем, а вот есть просто имя.

Что же нам делать?

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

По первой букве.

То есть у нас имя должно стоять первой колонкой в индексе, чтобы вот такой запрос работал.

А мы пришли в систему, а там, ну, уже кто-то шибко умный создал вот такой индекс.

И говорит, таблица на терабайт, создавать индекс нельзя, вот как бы запрос пиши нормально, ну ты что, SQL программировать не умеешь.

И мы говорим, что делать?

Значит, ну мы не совсем обречены, потому что даже в таком индексе можно немножко схитрить, и добавить статусы, которые мы знаем, ну потенциально там могут сработать.

Если мы знаем, что их, допустим, два всего, ну или 3, 4, 5, мы такие упомянули, и в запрос их добавили.

Ну, конечно, статусов может меняться, да, и количество их может меняться.

Мы такие взяли и сделали select distinct.

И вот, пожалуйста, ну, то, чтобы не хардкодить все уникальные, мы написали select distinct.

К сожалению, вот такая конструкция будет тормозить.

Она реально возьмет всю таблицу, ну, или весь индекс, расканирует,

найдет уникальные, и запрос не выполнится за разумное время.

Поэтому нужно прибегать к хитростям.

Мы вспоминаем устройство индекса, и что мы знаем?

Мы знаем, что индекс отсортирован, это значит, что минимальное, например, значение можно найти довольно быстро.

Спустившись влево-влево-влево, самое первое значение нашли.

Ну, они там могли быть удаленные, и мы такие, ну, типа, прочитали 100 тысяч удаленных записей, если это мусор.

Но давайте просто минимальное значение мы можем быстро найти.

А где минимальное, там и следующее.

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

Мы не читаем все записи из индекса, а мы находим как бы следующую.

И это тоже быстро работает.

И мы так можем сделать третий раз.

На четвертый раз у нас Control-C устанет, и мы напишем рекурсивный подзапрос.

Значит, рекурсивный подзапрос, который делает то же самое.

Да, мы берем, выбираем минимальную запись, и потом мы дополнительно ищем следующую, пока она находится.

Вот такой запрос на обычном B3 индексе находит уникальные значения в колонке за такое приемлемое время.

Вот это приемлемое время, оно сравнимо с количеством данных, которые вернет запрос.

То есть это не объем таблицы, а это именно количество данных, которые вернет запрос.

Если их там уникальных не очень много...

то, значит, можно довольно быстро это получить.

Ну и как бы свести задачу к предыдущим, найти наш нейм-статус по даже тому странному индексу.

К сожалению, такую оптимизацию пока в сам Postgres не завезли.

То есть ждем еще сколько-то лет, либо заинтересованные пишем вручную, у кого она актуальна, значит, используем и читаем, собственно, на страничке.

Итак, я предлагаю дружить с вашими индексами.

Посмотрите, что же у вас есть.

Потому что в запросе может помочь.

Учитывайте цель оптимизации.

Потому что создать индекс — это значит ускорить выборку, но замедлить вставку.

Если важна скорость вставки, то, возможно, индекс не надо было создавать.

И иногда имеющихся индексов уже достаточно.

Иногда они лишние, и лишние можно просто взять и удалить.

На этом все.

С вами был Владимир Сидников.

Спасибо.

Владимир, большое тебе спасибо.

Кстати, по поводу отсутствия индексов.

Мы столкнулись один раз с такой проблемой.

Кто-то решил класть логи в таблицу.

И, соответственно, как все нормальные разработчики, просто взяли и поставили индексы на текстовые поля, чтобы искать же по логам можно было удобнее.

А никто, например, в Continuous Integration System их по логам не ищет.

Просто берут и выводят вот это все.

И в какой-то момент система начинает деградировать, деградировать, деградировать.

Все, конечно же, решилось тем, что мы просто убрали все индексы из таблицы.

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

Ребят, у нас, наверное, есть время на 2-3 вопроса здесь из зала.

А те, кто не успеют, пойдут в дискуссионную зону дальше тебя мучить.

Вот у нас, видимо, первый вопрос.

Давай послушаем.

Добрый день.

Гаранин Александр, НРД.

Спасибо большое за доклад.

Мне хотелось бы узнать, вы сказали, что индекс не знает об удаленных записях, из-за этого возникают дополнительные расходы.

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

Поэтому по любому обращению в таблицу идет.

Вот в чем тогда отличается вот этот only scan индекс от обычного индекса, если в любом случае мы должны посмотреть, удалена запись или нет.

Спасибо за вопрос.

Я давайте переформулирую.

Зачем нам нужно знать, что индекс не хранит удаленные записи, если нам все равно ходить в таблицу и перепроверять?

Я правильно понял?

Да, да, да.

Значит, в чем проблема?

Проблема такая.

Вот у нас есть данные, допустим, и кто-то спрашивает, а есть ли у нас запись для пятерочки?

И вот в такой конфигурации, когда у нас в таблице пятерка уже отмечена как удаленная, мы зайдем в индекс, увидим пятерочку.

Мы уже сделали операцию.

Пошли в таблицу, сделали операцию и увидели, что там она удалена.

Это значит, мы ничего не вернули, а сделали работу.

Мы тормозим.

Если бы, глядя в индекс, мы видели, что эта запись уже удалена,

Вот прям сразу.

Мы бы тогда в таблицу не ходили, мы бы сэкономили один прыжок в нашу таблицу и страницу табличную не грузили бы.

Это раз.

Ну, казалось бы, одна, какой вопрос, какая проблема, да?

Вообще не проблема.

Проблема в том, что вот этот мусор возникает не просто при удалениях, он возникает при апдейтах.

То есть если вы обновляете строку, индексированную какую-нибудь колоночку, то у вас для одной пятерочки может возникнуть много записей.

То есть там будет написано 5, 5, 5, 5, 5, 5, 5.

Они будут ссылаться на разные страницы таблиц, и вы поиском по первичному ключу можете пройти тысячу строк в таблице.

Из них одна будет реальная, а 999 будут удаленных.

Это больно, когда вы поиском по первичному ключу обращаетесь к 1000 блоков диска.

Это 10 секунд.

Хорошо, спасибо.

Так, друзья.

Слушай, видимо, первый доклад.

Утро второго дня пока тяжело, особенно индексы.

Давайте, ребята, следующий вопрос.

Да, здравствуйте.

Спасибо за доклад.

Очень интересно повторить все это.

Если у нас проблема такая есть, что у нас индекс непокрывающий, мы ходим в таблицу, почему в Postgre отказались от кластерного индекса, да?

То есть чтобы сразу в кластерный индекс создать туда какие-то поля, которые нам нужны, там их держать в памяти и быстро, соответственно, запрашивать, как это в Microsoft SQL сделано.

Почему в Postgre решили от этого отказаться?

Спасибо.

Да, спасибо за вопрос.

Вопрос, почему в PostgreSQL решили отказаться от кластерных индексов, что бы это ни значило.

К сожалению, не отказывались, а не выбирали.

То есть PostgreSQL развивался довольно давно.

То есть это 80-е годы примерно.

Ну там Ingress, PostgreSQL и так далее истории.

Просто не завезли.

То есть исходная реализация была такая.

В таблице, которая внизу, данные хранятся в несортированном виде.

Вот это такая база PostgreSQL.

Индексы хранятся поверх.

И формат таблицы мы не меняем.

Поэтому для того, чтобы сделать хранение данных в таблице тоже в сортированном виде, рядом с индексом или только в индексе, это прям фундаментально.

Таблица это то, что есть база-база в Postgres.

Это довольно сложная работа.

И лучшее, что у нас сейчас сделано, есть команда cluster table в Postgres, что она означает по факту?

Она означает, что мы можем попросить базу отсортировать саму таблицу, записи в таблице в порядке нашего индекса.

Потому что вот что сейчас творится?

Сейчас индекс указывает хаотично.

Одна и та же страница, 1,4 указывает в таблицу и налево, и направо.

То есть мы буквально, если хотим парочку соседних значений, мы уже random read в таблице делаем.

Значит, есть базы, ну, например, MySQL по первичному ключу всегда сортирует, ну, как бы по-другому не умеет, это отдельная проблема.

В Oracle есть индекс органайз таблицы, в MySQL, в MSSQL есть кластер индекс, да, это что значит?

Что таблица как бы всегда поддерживается в сортированном порядке по индексу.

В Postgres не реализовали.

Приходите с патчами, но счастливой отладки.

Команда, этот самый кластер, она один раз в момент вызова сортирует таблицу.

То есть если вы залили таблицу большой миграцией, можете так, кластер, и у вас таблица будет сортирована.

Слушай, мне кажется, самая частая фраза от спикеров, которые говорят про Postgres, начиная от Олега Бартунова, приходите с патчами.

Нет, а на самом деле приходить с патчами.

Я вот как бы не так просто.

Я поддерживаю gdbc-драйвер в Java.

То есть это коннектор, один из, типа, дефолт-коннекторов Java в Postgres.

Я пришел с патчами, и мне через какое-то время говорят, хочешь, давай.

Хорошо.

Владимир, спасибо большое за доклад.

Очень интересно было.

Но я вот хотел бы, наверное, продолжить вопрос человека, который первый его задал.

А действительно, если у нас есть индекс онлескан, почему он не всегда делает heap fetch?

Ну, то есть, типа, он все-таки знает, что...

Ну, то есть у него там, не знаю, есть... Замечательный вопрос.

Каким образом появляется индекс онлайн-скат с хип-фетчами?

То есть почему мы не всегда, а иногда?

Значит, оптимизация какая добавлена?

На уровне страницы индекса есть битовый флажок такой, один битик, который говорит, мамы, клянусь, вот эта индексная страница нормальная.

То есть при какой-то модификации флажок сразу сбрасывается, и все.

И у нас на этой странице начинаются хипфетчи.

Иными словами, если мы добавляем к нашей четверочке рядом какое-нибудь значение, то вся страница объявляется подозрительная, и выборка единички с четверочкой замедляется.

Спасибо большое.

Друзья, у нас, к сожалению, подошло время к концу на вопросы из зала, поэтому я предлагаю далеко не убегать.

Владимир сейчас подойдет в дискуссионную зону, и дальше можно отвечать на вопросы про Postgres.

Спасибо тебе большое.

Спасибо.