Предисловие

В этой серии статей речь пойдет об индексах в PostgreSQL.

Любой вопрос можно рассматривать с разных точек зрения. Мы будем говорить о том, что должно интересовать прикладного разработчика, использующего СУБД: какие индексы существуют, почему в PostgreSQL их так много разных, и как их использовать для ускорения запросов. Пожалуй, тему можно было бы раскрыть и меньшим числом слов, но мы втайне надеемся на любознательного разработчика, которому также интересны и подробности внутреннего устройства, тем более, что понимание таких подробностей позволяет не только прислушиваться к чужому мнению, но и делать собственные выводы.

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

В этой части мы поговорим про разделение сфер ответственности между общим механизмом индексирования, относящимся к ядру СУБД, и отдельными методами индексного доступа, которые в PostgreSQL можно добавлять как расширения. В следующей части мы рассмотрим интерфейс метода доступа и такие важные понятия, как классы и семейства операторов. После такого длинного, но необходимого введения мы подробно рассмотрим устройство и применение различных типов индексов: Hash, B-tree, GiST, SP-GiST, GIN и RUM, BRIN и Bloom.

Интерфейс

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

Свойства

Все свойства методов доступа представлены в таблице pg_am (am — access method). Из этой таблицы можно получить и сам список доступных методов:

postgres=# select amname from pg_am;
 amname
--------
 btree
 hash
 gist
 gin
 spgist
 brin
(6 rows)

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

В версиях PostgreSQL 9.5 и более старых каждое свойство было представлено отдельным полем таблицы pg_am. Начиная с версии 9.6 свойства опрашиваются специальными функциями и разделены на несколько уровней:

• свойства метода доступа — pg_indexam_has_property,
• свойства конкретного индекса — pg_index_has_property,
• свойства отдельных столбцов индекса — pg_index_column_has_property.

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

В первой статье мы рассмотрели механизм индексирования PostgreSQL, во второй — интерфейс методов доступа, и теперь готовы к разговору о конкретных типах индексов. Начнем с хеш-индекса.

Hash

Устройство

Общая теория

Многие современные языки программирования включают хеш-таблицы в качестве базового типа данных. Внешне это выглядит, как обычный массив, но в качестве индекса используется не целое число, а любой тип данных (например, строка). Хеш-индекс в PostgreSQL устроен похожим образом. Как это работает?

Как правило, типы данных имеют очень большие диапазоны допустимых значений: сколько различных строк можно теоретически представить в столбце типа text? В то же время, сколько разных значений реально хранится в текстовом столбце какой-нибудь таблицы? Обычно не так много.

Идея хеширования состоит в том, чтобы значению любого типа данных сопоставить некоторое небольшое число (от 0 до N−1, всего N значений). Такое сопоставление называют хеш-функцией. Полученное число можно использовать как индекс обычного массива, куда и складывать ссылки на строки таблицы (TID). Элементы такого массива называют корзинами хеш-таблицы — в одной корзине могут лежать несколько TID-ов, если одно и то же проиндексированное значение встречается в разных строках.

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

Мы уже рассмотрели механизм индексирования PostgreSQL и интерфейс методов доступа, а также один из методов доступа — хеш-индекс. Сейчас поговорим о самом традиционном и используемом индексе — B-дереве. Глава получилась большой, запасайтесь терпением.

Btree

Устройство

Индекс btree, он же B-дерево, пригоден для данных, которые можно отсортировать. Иными словами, для типа данных должны быть определены операторы «больше», «больше или равно», «меньше», «меньше или равно» и «равно». Заметьте, что одни и те же данные иногда можно сортировать разными способами, что возвращает нас к концепции семейства операторов.

В прошлые разы мы рассмотрели механизм индексирования PostgreSQL, интерфейс методов доступа, и два метода: хеш-индекс и B-дерево. В этой части займемся индексами GiST.

GiST

GiST — сокращение от «generalized search tree». Это сбалансированное дерево поиска, точно так же, как и рассмотренный ранее b-tree.

В чем же разница? Индекс b-tree жестко привязан к семантике сравнения: поддержка операторов «больше», «меньше», «равно» — это все, на что он способен (зато способен очень хорошо!). Но в современных базах хранятся и такие типы данных, для которых эти операторы просто не имеют смысла: геоданные, текстовые документы, картинки…

Тут на помощь и приходит индексный метод GiST. Он позволяет задать принцип распределения данных произвольного типа по сбалансированному дереву, и метод использования этого представления для доступа по некоторому оператору. Например, в GiST-индекс можно «уложить» R-дерево для пространственных данных с поддержкой операторов взаимного расположения (находится слева, справа; содержит и т. п.), или RD-дерево для множеств с поддержкой операторов пересечения или вхождения.

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

Мы уже рассмотрели механизм индексирования PostgreSQL, интерфейс методов доступа и три метода: хеш-индекс, B-дерево и GiST. В этой части речь пойдет о SP-GiST.

SP-GiST

Вначале немного о названии. Слово «GiST» намекает на определенную схожесть с одноименным методом. Схожесть действительно есть: и тот, и другой — generalized search trees, обобщенные деревья поиска, предоставляющие каркас для построения разных методов доступа.

«SP» расшифровывается как space partitioning, разбиение пространства. В роли пространства часто выступает именно то, что мы и привыкли называть пространством — например, двумерная плоскость. Но, как мы увидим, имеется в виду любое пространство поиска, по сути произвольная область значений.

SP-GiST подходит для структур, в которых пространство рекурсивно разбивается на непересекающиеся области. В этот класс входят деревья квадрантов (quadtree), k-мерные деревья (k-D tree), префиксные деревья (trie).

Мы уже познакомились с механизмом индексирования PostgreSQL и с интерфейсом методов доступа, и рассмотрели хеш-индексы, B-деревья, индексы GiST и SP-GiST. А в этой части займемся индексом GIN.

GIN

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

Лазарь Лагин, «Старик Хоттабыч».

Gin stands for Generalized Inverted Index and should be considered as a genie, not a drink.

README

Общая идея

GIN расшифровывается как Generalized Inverted Index — это так называемый обратный индекс. Он работает с типами данных, значения которых не являются атомарными, а состоят из элементов. При этом индексируются не сами значения, а отдельные элементы; каждый элемент ссылается на те значения, в которых он встречается.

Хорошая аналогия для этого метода — алфавитный указатель в конце книги, где для каждого термина приведен список страниц, где этот термин упоминается. Как и указатель в книге, индексный метод должен обеспечивать быстрый поиск проиндексированных элементов. Для этого они хранятся в виде уже знакомого нам B-дерева (для него используется другая, более простая, реализация, но в данном случае это несущественно). К каждому элементу привязан упорядоченный набор ссылок на строки таблицы, содержащие значения с этим элементом. Упорядоченность не принципиальна для выборки данных (порядок сортировки TID-ов не несет в себе особого смысла), но важна с точки зрения внутреннего устройства индекса.

Мы уже рассмотрели механизм индексирования PostgreSQL, интерфейс методов доступа и все основные методы доступа, как то: хеш-индексы, B-деревья, GiST, SP-GiST и GIN. А в этой части посмотрим на превращение джина в ром.

RUM

Хоть авторы и утверждают, что джин — могущественный дух, но тема напитков все-таки победила: GIN следующего поколения назвали RUM.

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

• Взять пакет yum или apt из репозитория PGDG. Например, если вы ставили PostgreSQL из пакета postgresql-10, то поставьте еще postgresql-10-rum.
• Самостоятельно собрать и установить из исходных кодов на github (инструкция там же).
• Пользоваться в составе Postgres Pro Enterprise (или хотя бы читать оттуда документацию).

Ограничения GIN

Какие ограничения индекса GIN позволяет преодолеть RUM?

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

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

Метод доступа RUM в первом приближении можно рассматривать как GIN, в который добавлена позиционная информация, и который поддерживает выдачу результата в нужном порядке (аналогично тому, как GiST умеет выдавать ближайших соседей). Пойдем по порядку.

В прошлых статьях мы рассмотрели механизм индексирования PostgreSQL, интерфейс методов доступа и следующие методы: хеш-индексы, B-деревья, GiST, SP-GiST, GIN и RUM. Тема этой статьи — BRIN-индексы.

BRIN

Общая идея

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

Упрощенно говоря, BRIN хорошо работает для тех столбцов, значения в которых коррелируют с их физическим расположением в таблице. Иными словами, если запрос без предложения ORDER BY выдает значения столбца практически в порядке возрастания или убывания (и при этом по столбцу нет индексов).

Метод доступа создавался в рамках европейского проекта по сверхбольшим аналитическим базам данных Axle с прицелом на таблицы размером в единицы и десятки терабайт. Важное свойство BRIN, позволяющее создавать индексы на таких таблицах — небольшой размер и минимальные накладные расходы на поддержание.

Работает это следующим образом. Таблица разбивается на зоны (range) размером в несколько страниц (или блоков, что то же самое) — отсюда и название: Block Range Index, BRIN. Для каждой зоны в индексе сохраняется сводная информация о данных в этой зоне. Как правило, это минимальное и максимальное значения, но бывает и иначе, как мы увидим дальше. Если при выполнении запроса, содержащего условие на столбец, искомые значения не попадают в диапазон, то всю зону можно смело пропускать; если же попадают — все строки во всех блоках зоны придется просмотреть и выбрать среди них подходящие.

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

В прошлых статьях мы рассмотрели механизм индексирования PostgreSQL и интерфейс методов доступа, а также хеш-индексы, B-деревья, GiST, SP-GiST, GIN, RUM и BRIN. Нам осталось посмотреть на индексы Блума.

Bloom

Общая идея

Классический фильтр Блума — структура данных, позволяющая быстро проверить принадлежность элемента множеству. Фильтр очень компактен, но допускает ложные срабатывания: он имеет право ошибиться и счесть элемент принадлежащим множеству (false positive), но не имеет права сказать, что элемента нет в множестве, если на самом деле он там присутствует (false negative).

Фильтр представляет собой битовый массив (называемый также сигнатурой) длиной m бит, изначально заполненный нулями. Выбираются k различных хеш-функций, которые отображают любой элемент множества в k битов сигнатуры. Чтобы добавить элемент в множество, нужно установить в сигнатуре каждый из этих битов в единицу. Следовательно, если все соответствующие элементу биты установлены в единицу — элемент может присутствовать в множестве; если хотя бы один бит равен нулю — элемент точно отсутствует.

В случае индекса СУБД мы фактически имеем N отдельных фильтров, построенных для каждой индексной строки. Как правило, в индекс включаются несколько полей; значения этих полей и составляют множество элементов для каждой из строк.

Благодаря выбору размера сигнатуры m, можно находить компромисс между объемом индекса и вероятностью ложного срабатывания. Область применения Блум-индекса — большие, достаточно «широкие» таблицы, запросы к которым могут использовать фильтрацию по любым из полей. Этот метод доступа, как и BRIN, можно рассматривать как ускоритель последовательного сканирования: все найденные индексом совпадения необходимо перепроверять по таблице, но есть шанс вовсе не рассматривать значительную часть строк.

Часть первая — Affinity Propagation
Часть вторая — DBSCAN
Часть третья — кластеризация временных рядов
Часть четвёртая — Self-Organizing Maps (SOM)
Часть пятая — Growing Neural Gas (GNG)

Если вы спросите начинающего аналитика данных, какие он знает методы классификации, вам наверняка перечислят довольно приличный список: статистика, деревья, SVM, нейронные сети… Но если спросить про методы кластеризации, в ответ вы скорее всего получите уверенное «k-means же!» Именно этот золотой молоток рассматривают на всех курсах машинного обучения. Часто дело даже не доходит до его модификаций (k-medians) или связно-графовых методов.

Не то чтобы k-means так уж плох, но его результат почти всегда дёшев и сердит. Есть более совершенные способы кластеризации, но не все знают, какой когда следует применять, и очень немногие понимают, как они работают. Я бы хотел приоткрыть завесу тайны над некоторыми алгоритмами. Начнём с Affinity propagation.

Часть первая — Affinity Propagation
Часть вторая — DBSCAN
Часть третья — кластеризация временных рядов
Часть четвёртая — Self-Organizing Maps (SOM)
Часть пятая — Growing Neural Gas (GNG)

Углубимся ещё немного в малохоженные дебри Data Science. Сегодня в очереди на препарацию алгоритм кластеризации DBSCAN. Прошу под кат людей, которые сталкивались или собираются столкнуться с кластеризацией данных, в которых встречаются сгустки произвольной формы — сегодня ваш арсенал пополнится отличным инструментом.

Часть первая — Affinity Propagation
Часть вторая — DBSCAN
Часть третья — кластеризация временных рядов
Часть четвёртая — Self-Organizing Maps (SOM)
Часть пятая — Growing Neural Gas (GNG)

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

Кластеризация временных рядов — неблагодарное дело. Даже при группировке статических данных часто получаются сомнительные результаты, что уж говорить про информацию, рассеянную во времени. Однако нельзя игнорировать задачу, только потому что она сложна. Попробуем разобраться, как выжать из рядов без меток немного смысла. В этой статье рассматриваются подтипы кластеризации временных рядов, общие приёмы и популярные меры расстояния между рядами. Статья рассчитана на читателя, уже имевшего дело с последовательностями в data science: о базовых вещах (тренд, ARMA/ARIMA, спектральный анализ) рассказываться не будет.

Часть первая — Affinity Propagation
Часть вторая — DBSCAN
Часть третья — кластеризация временных рядов
Часть четвёртая — Self-Organizing Maps (SOM)
Часть пятая — Growing Neural Gas (GNG)

Self-organizing maps (SOM, самоорганизующиеся карты Кохонена) — знакомая многим классическая конструкция. Их часто поминают на курсах машинного обучения под соусом «а ещё нейронные сети умеют вот так». SOM успели пережить взлёт в 1990-2000 годах: тогда им пророчили большое будущее и создавали новые и новые модификации. Однако, в XXI веке SOM понемногу уходят на задний план. Хоть новые разработки в сфере самоорганизующихся карт всё ещё ведутся (большей частью в Финляндии, родине Кохонена), даже на родном поле визуализации и кластеризации данных карты Кохонена всё чаще уступает t-SNE.

Давайте попробуем разобраться в тонкостях SOM'ов, и выяснить, заслуженно ли они были забыты.

Часть первая — Affinity Propagation
Часть вторая — DBSCAN
Часть третья — кластеризация временных рядов
Часть четвёртая — Self-Organizing Maps (SOM)
Часть пятая — Growing Neural Gas (GNG)

Доброго времени суток, Хабр! Сегодня я бы хотел рассказать об одном интересном, но крайне малоизвестном алгоритме для выделения кластеров нетипичной формы — расширяющемся нейронном газе (Growing Neural Gas, GNG). Особенно мало информации об этом инструменте анализа данных в рунете: статья в википедии, рассказ на Хабре о сильно изменённой версии GNG и пара статей с одним лишь перечислением шагов алгоритма — вот, пожалуй, и всё. Весьма странно, ведь мало какие анализаторы способны работать с меняющимися во времени распределениями и нормально воспринимают кластеры экзотической формы — а это как раз сильные стороны GNG. Под катом я попробую объяснить этот алгоритм сначала человеческим языком на простом примере, а затем более строго, в подробностях. Прошу под кат, если заинтриговал.

(На картинке: нейронный газ осторожно трогает кактус)

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

Под катом много картинок, в том числе анимированных gif.

Наборами данных в миллионы экземпляров в задачах машинного обучения уже давным давно никого не удивишь. Однако мало кто задаётся вопросом, как качественно визуализировать эти титанические пласты информации. Когда размер датасета превышает миллион, становится довольно грустно использовать стандартный t-SNE; остаётся играться с даунсэмплированием или вовсе ограничиваться грубыми статистическими инструментами. Но на каждую задачу найдётся свой инструмент. В своей статье я бы хотел рассмотреть два алгоритма, которые преодолевают барьер квадратичной сложности: уже хорошо известный Barnes-Hut t-SNE и новый претендент на звание «золотого молотка infovis'a» LargeVis.


(Это не картина художника-абстракциониста, а визуализация LiveJournal-датасета с высоты птичьего полёта)

Нейронные сети учатся совсем не так как люди. Оптимизация нейронной сети — на самом деле градиентный спуск по некоторой функции потерь $$, где переменными являются веса слоёв $$. Это очень мощный подход к подстройке системы, который применяется также в физике, экономике и многих других областях. На данный момент предложено немало конкретных методов градиентного спуска, но все они предполагают, что градиент $$ хорошо себя ведёт: нет обрывов, где он скачкообразно возрастает, или плато, где он обращается в ноль. С первой проблемой можно разобраться при помощи gradient clipping, но вторая заставляет тщательно подумать. Кусочно-линейную или дискретную функцию нетривиально ограничить более приятной функцией

• во многих областях reinforcement learning (далее RL)
• в VAE с дискретными латентными переменными
• в GAN с дискретными генераторами

Как поступать в таких ситуациях?

Под катом много формул и гифок.

TL;DR

1. В глубоких нейронных сетях основным препятствием для обучения являются седловые точки, а не локальные минимумы, как считалось ранее.
2. Большинство локальных минимумов целевой функции сконцентрированы в сравнительно небольшом подпространстве весов. Соответствующие этим минимумам сети дают примерно одинаковый loss на тестовом датасете.
3. Сложность ландшафта увеличивается по приближении к глобальным минимумам. Почти во всём объёме пространства весов подавляющая часть седловых точек имеет большое количество направлений, по которым из них можно сбежать. Чем ближе к центру кластера минимумов, тем меньше «направлений побега» у встреченных на пути седловых точек.
4. Всё ещё неясно, как найти в подпространстве минимумов глобальный экстремум (любой из них). Похоже, что это очень сложно; и не факт, что типичный глобальный минимум намного лучше типичного локального, как в плане loss'a, так и в плане обобщающей способности.
5. В сгустках минимумов существуют особые кривые, соединяющие локальные минимумы. Функция потерь на этих кривых принимает лишь чуть большие значения, чем в самих экстремумах.
6. Некоторые исследователи считают, что широкие минимумы (с большим радиусом «ямы» вокруг) лучше узких. Но есть и немало учёных, которые полагают, что связь ширины минимума с обобщающей способностью сети очень слаба.
7. Skip connections делают ландшафт более дружелюбным для градиентного спуска. Похоже, что вообще нет причин не использовать residual learning.
8. Чем шире слои в сети и чем их меньше (до определённого предела), тем глаже ландшафт целевой функции. Увы, чем более избыточна параметризация сети, тем больше нейросеть подвержена переобучению. Если использовать сверхширокие слои, то несложно найти глобальный минимум на тренировочном наборе данных, но обобщать такая сеть не будет.

Всё, листайте дальше. Я даже КДПВ ставить не буду.

Привет, Хабр. Сегодня я бы хотел развить тему вариационной оптимизации и рассказать, как применить её к задаче обрезки малоинформативных каналов в нейронных сетях (pruning). При помощи неё можно сравнительно просто увеличить «скорострельность» нейронной сети, не перелопачивая её архитектуру.