• Индексы в PostgreSQL — 8


      Мы уже рассмотрели механизм индексирования 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 умеет выдавать ближайших соседей). Пойдем по порядку.
      Читать дальше →
    • Разбор задач викторины Postgres Pro на Highload++ 2017

        На Higload++ 2017 года в Сколково наша компания Postgres Professional снова провела викторину с традиционной раздачей ништяков, в качестве которых выступили билеты на февральский PgConf.Russia 2018.

        В этой статье разбираются вопросы викторины.


        Читать дальше →
        • +23
        • 4,2k
        • 9
      • Индексы в PostgreSQL — 7


          Мы уже познакомились с механизмом индексирования 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-ов не несет в себе особого смысла), но важна с точки зрения внутреннего устройства индекса.

          Читать дальше →
        • Различия Postgres Pro Enterprise и PostgreSQL

            1. Кластер multimaster


            Расширение multimaster и его поддержка в ядре, которые есть только в версии Postgres Pro Enterprise, дают возможность строить кластеры серверов высокой доступности (High Availability). После каждой транзакции гарантируется глобальная целостность (целостность данных в масштабах кластера), т.е. на каждом его узле данные будут идентичны. При этом легко можно добиться, чтобы производительность по чтению масштабировалась линейно с ростом количества узлов.
            Читать дальше →
          • Индексы в PostgreSQL — 6


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

              SP-GiST


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

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

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

              Читать дальше →
            • Что умеет планировщик заданий в Postgres Pro

                Планировщик заданий (scheduler) не во все времена считался обязательным инструментом в мире баз данных. Все зависело от назначения и происхождения СУБД. Классические коммерческие СУБД (Oracle, DB2, MS SQL) представить себе без планировщика решительно невозможно. С другой стороны, трудно вообразить потенциального пользователя MongoDB, который откажется от выбора этой модной NoSQL-СУБД из-за отсутствия планировщика. (Кстати, термин «планировщик заданий» в русском контексте СУБД употребляют, чтобы отличить его от планировщика запросов — query planner, мы же для краткости будем звать его здесь планировщиком).

                PostgreSQL, будучи Open Source и впитав традиции сообщества с образом жизни DIY («сделай сам»), в наше время регулярно претендует на место как минимум заместителя коммерческой СУБД. Из этого автоматически следует, что PostgreSQL просто обязана иметь планировщик, и что этот планировщик должен быть удобен для администратора базы и для пользователя.
                Читать дальше →
              • Разбор задач викторины Postgres Pro на PGDay'17

                  Хорошей традицией на постгресовых конференциях стало устраивать викторины с розыгрышем билетов на следующие конференции. Наша компания Postgres Professional на недавнем PgDay’17 разыгрывала билеты на PgConf.Russia 2018, которая пройдет в феврале 2018 года в Москве. В этой статье представлен обещанный разбор вопросов викторины.
                  Читать дальше →
                • Индексы в PostgreSQL — 5


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

                    GiST


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

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

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

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


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

                      Btree


                      Устройство


                      Индекс btree, он же B-дерево, пригоден для данных, которые можно отсортировать. Иными словами, для типа данных должны быть определены операторы «больше», «больше или равно», «меньше», «меньше или равно» и «равно». Заметьте, что одни и те же данные иногда можно сортировать разными способами, что возвращает нас к концепции семейства операторов.
                      Читать дальше →
                      • +32
                      • 10,8k
                      • 8
                    • Индексы в PostgreSQL — 3


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

                        Hash


                        Устройство


                        Общая теория


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

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

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

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