pg91

Эффективный поиск ближайших соседей и другие новые средства в PostgreSQL

Что планировалось

Совещание ведущих разработчиков PostgreSQL в мае 2010 года в Оттаве, Канада, выработало список приоритетных задач для PostgreSQL 9.1.

Ведущие разработчики PostgreSQL (Я снимаю).

Group picture of PostgreSQL developers, Ottawa 2010

Josh Berkus ведет список приоритетных работ для PostgreSQL 9.1.

The Prority List for PostgreSQL 9.1  is almost done

Что удалось реализовать

Список новых и наиболее важных разработок, вошедших в PostgreSQL 9.1 (Полный список изменений).

Функциональность

  • Synchronous Replication - Синхронная репликация гарантирует сохранность данных при сбоях мастера. В 9.0 появилась потоковая (асинхронная) репликация (streaming replication), которая означала, что как только произошла запись в WAL, они рассылались ко всем слейвам. В асинхронной репликации всегда есть промежуток времени, когда после фиксации транзакции на мастере, на слейвах она еще не зафиксировалась, что может вызвать потерю данных при проблеме с мастером. В синхронной репликации текущая транзакция ожидает подтверждение от всех слейвов, что WAL был послан на все слейвы и они его получили.
  • Per-column collation - задание правила сравнения строк для каждого атрибута
  • Unlogged tables - возможность отказа журналирования транзакций (WAL) для таблицы. Это ускоряет запись в такие таблицы за счет потери возможности восстановления после сбоев и их репликации.

Новинки

  • SSI (Serializable Snapshot Isolation) - поддержка истинной сериализуемости конкурентных транзакций. До версии 9.1 поддерживались следующие уровни изоляции образов: READ UNCOMMITTED=READ COMMITTED, REPEATABLE READ=SERIALIZABLE. При этом SERIALIZABLE означал, что в текущей транзакции видны все записи зафиксированные до первого запроса или до выполнения команды, изменяющей данные, в рамках этой транзакции. Однако, настоящей изоляции транзакции для уровня изоляции SERIALIZABLE не поддерживалось и приходилось использовать явные блокировки. В версии 9.1 уровень изоляции REPEATABLE READ и SERIALIZABLE разошлись в том смысле, что уровень изоляции SERIALIZABLE стал действительно гарантировать последовательное выполнение транзакций - как будто транзакции выполняются последовательно друг за другом. Это достигается отслеживанием условий, которые могут вызвать нарушение сериализации (predicate locking). При детектировании таких условий выдается ошибка сериализации. Пример:
mytab:
 class | value 
-------+-------
     1 |    10
     1 |    20
     2 |   100
     2 |   200

Transaction A: Подсчитывает сумму для class=1 (30) и вставляет новую запись с class=2. Transaction B: Подсчитывает сумму для class=2 (300) и вставляет новую запись с class=1. Так как нет варианта, когда бы последовательное выполнение транзакций привело бы к непротиворечивому результату, то в SERIALIZABLE режиме выполнится только одна транзакция, а вторая откатится с ошибкой. (Если A раньше B, то B получит значение 330, а не 300. Аналогично для случая, если B исполняется раньше A). Предикативная блокировка позволит распознать такую ситуацию, при этом, она не блокирует записей, поэтому не может вызвать взаимоблокировку (deadlocks). Отмечу, что это первая продакшн-реализация SSI (статья вышла в 2008, Michael J. Cahill, Uwe Röhm, Alan D. Fekete. Serializable Isolation for Snapshot Databases. In the Proceedings of the 2008 ACM SIGMOD international conference on management of data, pages 729-738.).

  • KNN-GiST - возможность эффективного поиска (логарифмическая зависимость от размера таблицы) ближайших соседей, используя GiST индекс. Поддерживаются все встроенные типы данных. Это стало возможным заменой прежней стратегии обхода поискового дерева вглубь (Depth-First Search) с использованием стека для хранения узлов, на стратегию поиска наилучшего узла (Best-First Search) использованием очереди с приоритетом (priority queue). При этом, наилучший узел выбирается из условия минимального расстояния от заданной точки. Прежняя стратегия делала использование индекса для поиска ближайших соседей неэффективным, так как требовалось обойти весь индекс и прочитать всю таблицу в случайном порядке, что гораздо медленнее последовательного чтения всей таблицы. Очередь с приоритетом реализована в виде красно-черного дерева (RB-Tree), что позволило использовать одну стратегию обхода поискового дерева и для обычных поисков (все расстояния одинаковы и очередь вырождается в стек).

Например, для поиск 10 ближайших точке, к заданной, из 1 миллиона точек:

postgres=# explain analyze select *, position <-> point(500,500) from test order by position <-> point(500,500) limit 10;
                                                         QUERY PLAN                                                          
-----------------------------------------------------------------------------------------------------------------------------
 Limit  (cost=39519.39..39519.42 rows=10 width=16) (actual time=480.326..480.330 rows=10 loops=1)
   ->  Sort  (cost=39519.39..42019.67 rows=1000110 width=16) (actual time=480.324..480.326 rows=10 loops=1)
         Sort Key: (("position" <-> '(500,500)'::point))
         Sort Method: top-N heapsort  Memory: 25kB
         ->  Seq Scan on test  (cost=0.00..17907.38 rows=1000110 width=16) (actual time=0.013..271.170 rows=1000000 loops=1)
 Total runtime: **480.353 ms**
(6 rows)

postgres=# create index q on test using gist ( position );
postgres=# explain analyze select *, position <-> point(500,500) from test order by position <-> point(500,500) limit 10;
                                                        QUERY PLAN                                                        
--------------------------------------------------------------------------------------------------------------------------
 Limit  (cost=0.00..0.77 rows=10 width=16) (actual time=1.041..1.200 rows=10 loops=1)
   ->  Index Scan using q on test  (cost=0.00..77208.61 rows=1000000 width=16) (actual time=1.040..1.198 rows=10 loops=1)
         Order By: ("position" <-> '(500,500)'::point)                          
 Total runtime: **1.226 ms**

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

  • SE/Postgres - поддержка мандатной политики доступа, совместимой с SE Linux (Security Enhanced Linux). Поддержка реализована в виде загружаемого модуля (расширения), которые вводит дополнительный слой проверки безопасности на основе использования меток безопасности (security labels). При этом, каждая проверка безопасности включает проверку двух меток - метка объекта и метка субъекта. Этим достигается централизованная политика доступа к различным объектам системы, независимо от того, где они хранятся (файловая система, база данных).
SECURITY LABEL [ FOR provider ] ON
{
  TABLE object_name |
  COLUMN table_name.column_name |
  AGGREGATE agg_name (agg_type [, ...] ) |
  DOMAIN object_name |
  FOREIGN TABLE object_name
  FUNCTION function_name ( [ [ argmode ] [ argname ] argtype [, ...] ] ) |
  LARGE OBJECT large_object_oid |
  [ PROCEDURAL ] LANGUAGE object_name |
  SCHEMA object_name |
  SEQUENCE object_name |
  TYPE object_name |
  VIEW object_name
} IS 'label'

SECURITY LABEL FOR selinux ON TABLE mytable IS 'system_u:object_r:sepgsql_table_t:s0';
  • wCTE (writable Common Table Expressions) - использование команд, которые изменяют данные (INSERT,UPDATE,DELETE), с оператором WITH. Это позволяет исполнять несколько разных операций в одном запросе, например: Получить сводку удаленных постов по пользователю и обновить статистику пользователей.
WITH deleted_posts AS (
DELETE FROM posts
WHERE created < now() - '6 months'::INTERVAL
RETURNING *
), deleted_per_user as (
SELECT user_id, count(*)
FROM deleted_posts
GROUP BY 1
)
UPDATE counts
SET posts_count = posts_count - d.count
FROM deleted_per_user d
WHERE d.user_id = counts.user_id;

Расширяемость

  • Extensions - разработана инфраструктура управления расширениями. Команды CREATE/DROP/ALTER EXTENSION позволяют манипулировать расширениями (устанавливать, обновлять, изменять ) как единым целым. Прежний путь заливки различных SQL-скриптов в базу данных приводил к слабо-управляемому множеству разных объектов, входящих в расширение, что вызывало проблему с их обновлением и использованием.
postgres=# \dx
                        List of installed extensions
   Name   | Version |   Schema   |                Description                
----------+---------+------------+-------------------------------------------
 file_fdw | 1.0     | public     | foreign-data wrapper for flat file access
 plpgsql  | 1.0     | pg_catalog | PL/pgSQL procedural language
(2 rows)
postgres=# \dx+ file_fdw
     Objects in extension "file_fdw"
           Object Description            
-----------------------------------------
 foreign-data wrapper file_fdw
 function file_fdw_handler()
 function file_fdw_validator(text[],oid)
(3 rows)
  • SQL/MED - поддержка SQL стандарта в части управления внешними (вне базы данных) данными (Management of External Data). Команды CREATE/DROP/ALTER FOREIGN TABLE, CREATE/DROP/ALTER SERVER, CREATE/DROP/ALTER USER MAPPING FOR, CREATE/DROP/ALTER FOREIGN DATA WRAPPER обеспечивают прозрачную интеграцию со внешними данными. Примеры синтаксиса:
CREATE SERVER server_name [ TYPE 'server_type' ] [ VERSION 'server_version' ]
    FOREIGN DATA WRAPPER fdw_name
    [ OPTIONS ( option 'value' [, ... ] ) ]

CREATE FOREIGN TABLE schemaname.tablename (
    column_name type_name [ OPTIONS ( ... ) ] [ constraints | DEFAULT default value [...] ],
    ...
  )
  INHERITS ( parent )
  SERVER remote_postgresql_server
  OPTIONS ( ... );

В качестве примера доступа к файлам реализовано расширение file_fdw.

postgres=# CREATE SERVER file_server FOREIGN DATA WRAPPER file_fdw;
postgres=# CREATE FOREIGN TABLE passwd (
username text,
pass text,
uid int4,
gid int4,
gecos text,
home text,
shell text
) SERVER file_server
OPTIONS (format 'text', filename '/etc/passwd', delimiter ':', null '');
postgres=# select * from passwd order by uid asc limit 3;
 username | pass | uid | gid | gecos  |   home    |   shell   
----------+------+-----+-----+--------+-----------+-----------
 root     | x    |   0 |   0 | root   | /root     | /bin/bash
 daemon   | x    |   1 |   1 | daemon | /usr/sbin | /bin/sh
 bin      | x    |   2 |   2 | bin    | /bin      | /bin/sh
(3 rows)
postgres=# \d
             List of relations
 Schema |  Name  |     Type      |  Owner   
--------+--------+---------------+----------
 public | passwd | foreign table | postgres
 public | test   | table         | postgres
(2 rows)