Diary

2010-10-03

Опыт участия в разработке открытой СУБД PostgreSQL

Олег Бартунов (ГАИШ МГУ), Федор Сигаев (ГАИШ МГУ)

В докладе представлен опыт участия российских разработчиков в крупном проекте с открытым кодом, СУБД PostgreSQL. Авторы входят в число ведущих разработчиков, ими реализованы многие важные подсистемы СУБД PostgreSQL. Они принимают активное участие во всех крупнейших конференциях разработчиков и пользователей, как международных, так и российских.

Российское участие в проекте началось в конце 90-х годов, когда проект из академической разработки стал проектом сообщества и возникла потребность в использовании его в российском проекте. Реализация поддержки локализации (Олег Бартунов) позволила полноценно использовать СУБД PostgreSQL в non-ASCII странах, что способствовало распространению проекта. Дальнейшее российское участие связано с необходимостью использования СУБД PostgreSQL в крупнейшем проекте Rambler, в связи с чем Олег Бартунов и Федор Сигаев получили поддержку их работы над системой расширяемости PostgreSQL, так называемой GiST (Generalized Search Tree), которая позволяла стороннему программисту (не-разработчику движка бд) реализовывать новые полноценные типы данных поддержкой, т.е., типы данных могли иметь новые запросов и ускоряться индексами. Существующая академическая реализация не была рассчитана на какое-либо серьезное использование в крупном проекте, например, не было поддержки конкурентности и восстанавливания после сбоев. Успешная реализация GiST ускорила работу над созданием новых типов данных, что привело к появлению таких расширений, как полнотекстовый поиск, поддержку работы с массивами, поиску с ошибками, возможность работы со слабо-структурированными данными и многих других, реализованных другими разработчиками. Дальнейшая работа над полнотекстовым поиском привела к созданию нового типа индекса, GIN (Generalized Inverted Index) - обобщенного обратного индекса, своеобразному аналогу GiST. Использование PostgreSQL в GIS (расширение PostGIS является самым известным открытым проектом в области геоинформационных систем) привело к необходимости масштабирования PostgreSQL в сторону очень больших баз данных, в частности, к очень быстрому поиску ближайших соседей (k-nn search), что привело к дальнейшему улучшению подсистемы расширяемости GiST и реализации k-nn поиска с индексной поддержкой в ядре PostgreSQL и в настоящее время проходит период рецензирования для следующего релиза.

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

СУБД PostgreSQL активно используется астрономическим сообществом для работы с очень большими каталогами (миллиарды записей) небесных объектов. Для эффективной работы с таким каталогами требуется поддержка сферических координат, которая до недавнего времени была реализована только для коммерческой СУБД MS SQL (HTM - разбиение сферы на иерархические треугольники) командой под руководством Jim Gray. Лучшей альтернативой сейчас является расширение Q3C, написанное для PostgreSQL в ГАИШ МГУ Сергеем Копосовым при участии Олега Бартунова и которое широко используется не только в астрономии, но и в науках о Земле.

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

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

=

Российские спонсоры

  • Рамблер
  • РФФИ
  • 1C

Зарубежные спонсоры

  • Много (>10)
=

Российские участники:

  • Вадим Михеев (1995 – 10-Aug-2003) - реализация MVCC, WAL, SUBSELECT
  • Олег Бартунов (1996 – ) - поддержка локализации, GiST, GIN, полнотекстовый поиск
  • Федов Сигаев (2000 – ) - GiST, GIN, полнотекстовый поиск,…
  • Сергей Карпов (2007 – ) - поддержка полнотекстового поиска
  • Николай Самохвалов ( 2007 ) - поддержка XML
  • Алексей Борзов - веб-сайт PostgreSQL

0 Comments on this page

2010-01-12

What keywords are in text

The problem: Find what keywords are in text. We have papers and kw (keywords). kw.ts is a plainto_tsquery(kw.name).

          Table "public.papers"
      Column       |   Type   | Modifiers
-------------------+----------+-----------
 id                | integer  |
 oai_id            | text     |
 datestamp         | date     |
 title             | text     |
 authors           | text     |
 description       | text     |
 comment           | text     |
 creation_date     | date     |
 modification_date | date     |
 fts               | tsvector |
Indexes:
    "fts_idx" gin (fts)
    "fts_types_idx" gin (document_token_types(comment))
    "id_idx" btree (id)
Table "public.kw"
  Column   |         Type          | Modifiers
-----------+-----------------------+-----------
 key_id    | integer               |
 name      | character varying(64) |
 status_id | integer               |
 ts        | tsquery               |

arxiv=# select papers.title, array_agg(kw.name) from papers 
join kw on papers.fts @@ kw.ts and papers.id=2 
group by papers.title;

                  title                   |            array_agg
------------------------------------------+---------------------------------
 Sparsity-certifying Graph Decompositions | {color,Williams,trees,colorful}
(1 row)

In principle, it's possible to use this approach to find plagiarism.

Other way is to use ts_stat) function, which decomposes tsvector on words.

CREATE OR REPLACE FUNCTION ts_stat(tsvector, weights text, OUT word text, OUT ndoc
integer, OUT nentry integer)
RETURNS SETOF record AS
$$
    SELECT ts_stat('SELECT ' || quote_literal( $1::text ) || '::tsvector', quote_literal( $2::text) );
$$ LANGUAGE SQL RETURNS NULL ON NULL INPUT IMMUTABLE;

select ARRAY ( select (ts_stat(fts,'*')).word from papers where id=2);

0 Comments on this page

2009-11-26

Configure psql output

Use FETCH_COUNT internal psql variable to configure psql output

\set FETCH_COUNT 10

This will help to avoid memory problem, since psql waits until the complete result set has been produced, which can be very big.

0 Comments on this page

2009-11-25

K-nn search in PostgreSQL

Update: Download spots data (900,000 spots, 25 Mb compressed).

After our first announcement in -hackers mailing list of knngist we received positive feedback and recommendation to make GiST smarter. This night I tested new version of knn-search, which Teodor heroically made in 2 days, based on improved GiST, which now understand which algorithm of tree traverse to use (depth-first as for plain GiST, or distance based priority queue for KNNGiST). We also introduced amcanorderbyop flag to pg_am, which indicates if access method supports ordering operations.

We need index on coordinates.

=# create index pt_idx on spots using gist(coordinates); 

Now, compare traditional approach and knn (apply patches to CVS HEAD from commitfest).

1. Find 10 closest points to the given point.

SELECT coordinates, (coordinates <-> '5.0,5.0'::point) AS dist 
FROM spots ORDER BY dist ASC LIMIT 10;
             coordinates             |       dist       
-------------------------------------+------------------
 (3.57192993164062,6.51727240153665) | 2.08362656457647
 (3.49502563476562,6.49134782128243) | 2.11874164636854
 (3.4393,6.4473)                     | 2.12848814420001
 (3.31787109375,6.50089913799597)    | 2.25438592075067
 (2.6323,6.4779)                     | 2.79109148900569
 (2.66349792480469,6.53159856871478) | 2.79374947392946
 (1.84102535247803,6.27874198581057) |  3.4079762161672
 (1.2255,6.1228)                     | 3.93796014327215
 (1.22772216796875,6.15693947094637) | 3.94570513108469
 (9.6977,4.044503)                   | 4.79388775494473
(10 rows)

Total number of rows processed by traditional approach is 908846.

8.4.2                 464.501 ms
8.5dev+knngist-0.6    0.971 ms

We see more than 400x better performance for knngist.

2. More complex query with fts (total rows 5098 rows).

=# CREATE INDEX spots_idx ON spots USING gist (coordinates,to_tsvector('french',address));
=# SELECT id, address,
(coordinates <->'(2.29470491409302,48.858263472125)'::point) AS dist
FROM spots WHERE to_tsvector('french',address) @@ to_tsquery('french','mars')
ORDER BY coordinates <-> '(2.29470491409302,48.858263472125)'::point
LIMIT 10;

8.4.2               166.089 ms
5dev+knngist-0.6    2.758 ms

Performance benefit is also remarkable for complex queries.

3. Complex polygon (PARIS 1, see knngist ), number of rows is 238.

=# SELECT id, address,  (coordinates <->
'(2.29470491409302,48.858263472125)'::point) AS dist
FROM spots WHERE
to_tsvector('french',address) @@ to_tsquery('french','place')
AND  coordinates <@ :PARIS1::polygon
ORDER BY  coordinates <-> '(2.29470491409302,48.858263472125)'::point
LIMIT 10;

8.4.2                18.125 ms
8.5dev+knngist-0.6   19.704 ms

Since benefit of knn comes from reduction number of rows to sort (traditional approach is a fetch,sort,limit scenario) it's clear, that we'll see improvement when:

  1. the total number of rows returned by a query (before limit) is big
  2. rows are long

Another benefit of knn-search is more simple logic, since one doesn't need to know "radius" of neighbourhood in advance. In the above queries I assume infinite radius to demonstrate the biggest benefit of knn-search.

0 Comments on this page

2009-11-05

Back to Moscow from Nepal

This october three astronomers (I and two my colleagues) trekked in Everest area - for 15 days we did Kathmandu->Lukla - Phakding - Namche Bazaar - Tengboche - Chukhung (Chukhung Ri)-Kongma La (pass) - Lobuche - Gorakshep (Kala Patar) - Dzhongla - Cho La (pass) - Dragnag - Gokyo (Gokyo Ri, fifth lake Cho Oyu) - Renjo La (pass) -Molerung - Namche Bazaar - Lukla → Kathmandu.

No problem, except one of my colleague fainted while climbing to Kala Patar, but descent to Gorakshep helped him so much, so he even ate omlet !

After trek we spent lovely 4 days in Kathmandu walking around, relaxing and shopping.

I started to publish my pictures to my flickr page.

0 Comments on this page

2009-10-12

Flying to Nepal

This time I plan to explore Everest region - Lukla-Chukung Ri-Kongma La-Everest Base Camp-Kala Patar-Cho La-Gokyo Ri-6th Lake-Renjo Pass-Lukla.

0 Comments on this page

2009-09-08

Finding overlapping ranges

The problem of finding overlaped ranges in table(id,low,upper) looks trivial. I tried to find elegant solution, so I decided to describe non-overlapping set and then invert logical expression.

                 ------
          -----          -----
NOT(t1.low >= t2.upper  or t1.upper <= t2.low)

Then I want to exclude equal ranges

NOT(t1.low >= t2.upper  or t1.upper <= t2.low or (t1.low = t2.low and t1.upper = t2.upper  )

We don't want to do extra matches, so

NOT(t1.low >= t2.upper  or t1.upper <= t2.low or (t1.low = t2.low and t1.upper = t2.upper  ) and t1.id > t2.id

0 Comments on this page

2009-08-12

Algebra for full-text queries

We introduce phrase operator ?[n], or phrase conjuction operator, which is similar logical conjuction operator ( AND, &), but preserve order of operands (non-commutative) and constraint distance between them (<=n)

Logical conjuction operator (AND, &) is associative, commmutative, distributive, idempotent. In set theory intersection operator is an example of logical conjunction operator.

  • The ? operator is non-commutative, so 'A ? B' ≠ 'B ? A'
  • The ? operator is non-associative (left-associative) and evaluates from left to right.
=# select '1 ? 2 ? 3'::tsquery = '(1 ? 2) ? 3'::tsquery;
 ?column?
----------
 t

but

=# select '1 ? 2 ? 3'::tsquery = '1 ?  (2 ? 3)'::tsquery;
 ?column?
----------
 f

Function *phraseto_tsquery()* can be used for easy construction of phrase queries:

=# select phraseto_tsquery('1 2 3');
  phraseto_tsquery
---------------------
 ( '1' ? '2' ) ? '3'
  • The ? operator distributes across OR and AND:
=# select '1 ? ( 2 | 3)'::tsquery = '( 1 ? 2 ) | ( 1 ? 3 )'::tsquery;
 ?column?
----------
 t
=# select '1 ? ( 2 & 3)'::tsquery = '( 1 ? 2 ) & ( 1 ? 3 )'::tsquery;
 ?column?
----------
 t

'1 ? ( 2 & 3)'::tsquery looks like a problem, but consider situation when dictionary returns two lexems, so in tsvector they will have the same coodinates.

=# select '1:1 2:2 3:2'::tsvector  @@ '1 ? ( 2 & 3)'::tsquery;
 ?column?
----------
 t
  • The ? operator is non-idempotent, i.e. 'A ? A' ≠ 'A' ( not as AND: A & A ≡ A )
=# select '1 ? 1'::tsquery;
  tsquery
-----------
 '1' ? '1'

Compound word

=# CREATE TEXT SEARCH DICTIONARY nb_no_ispell ( TEMPLATE = ispell,
DictFile = nb_no, AffFile = nb_no );
=# select ts_lexize('nb_no_ispell', 'telefonsvarer');
          ts_lexize
------------------------------
 {telefonsvarer,telefon,svar}
=# CREATE TEXT SEARCH CONFIGURATION public.no ( COPY=pg_catalog.norwegian);
=# ALTER TEXT SEARCH CONFIGURATION  no ALTER MAPPING FOR asciiword, asciihword, hword_asciipart,word,
hword, hword_part WITH nb_no_ispell, norwegian_stem;

=# select to_tsquery('no','telefonsvarer & device');
                     to_tsquery
----------------------------------------------------
 ( 'telefonsvarer' | 'telefon' & 'svar' ) & 'devic'
=# select to_tsvector('no','telefonsvarer  device');
                   to_tsvector
--------------------------------------------------
 'devic':2 'svar':1 'telefon':1 'telefonsvarer':1

Now, see how phraseto_tsquery works:

=# select phraseto_tsquery('no','telefonsvarer device');
                              phraseto_tsquery
----------------------------------------------------------------------------
 'telefonsvarer' ? 'devic' | ( 'telefon' ? 'devic' ) & ( 'svar' ? 'devic' )

Casting produce the same result:

=# select '(telefonsvarer | telefon & svar ) ? devic'::tsquery;
                                  tsquery
----------------------------------------------------------------------------
 'telefonsvarer' ? 'devic' | ( 'telefon' ? 'devic' ) & ( 'svar' ? 'devic' )

More complex phrase:

=# select phraseto_tsquery('no','telefonsvarer device ok');
                                              phraseto_tsquery
-------------------------------------------------------------------------------------------------------------
 ( 'telefonsvarer' ? 'devic' ) ? 'ok' | ( ( 'telefon' ? 'devic' ) ? 'ok' ) & ( ( 'svar' ? 'devic' ) ? 'ok' )

=# select '(telefonsvarer |  telefon & svar ) ? devic ? ok'::tsquery;
                                                   tsquery
-------------------------------------------------------------------------------------------------------------
 ( 'telefonsvarer' ? 'devic' ) ? 'ok' | ( ( 'telefon' ? 'devic' ) ? 'ok' ) & ( ( 'svar' ? 'devic' ) ? 'ok' )

(1 row)

0 Comments on this page

2009-07-27

Rb-tree and GIN again !

Yesterday I again was beaten by GIN problem (PostgreSQL 8.4) with sorted data, see my post about rbtree. I tried to index following table, which represents interlinks between wikipedia articles.

wplinks=# \d links2
     Table "public.links2"
 Column |   Type    | Modifiers
--------+-----------+-----------
 id     | integer   |
 idout  | integer[] |
 idin   | integer[] |

To my surprise timings for indexes creation were very different - ~ 6x !

wplinks=# vacuum analyze links2;
VACUUM
Time: 65080.606 ms
wplinks=# create index idout_idx on links2 using gin(idout);
CREATE INDEX
Time: 6033572.537 ms
wplinks=# create index idin_idx on links2 using  gin(idin);
vacuum analyze;
CREATE INDEX
Time: 35946958.226 ms

Today, I tried rbtree version of GIN and got very nice result - 18x better creation time for idin and almost 4x better than old idout.

wplinks=# create index idout_rbtree_idx on links2 using  gin(idout);
CREATE INDEX
Time: 1560819.955 ms
wplinks=# create index idin_rbtree_idx on links2 using  gin(idin);
CREATE INDEX
Time: 1994567.418 ms

Notice, that 8.4 already have Tom's hack to protect GIN against skewed data. Certainly, we need rbtree in PostgreSQL !

0 Comments on this page

More...