![[Home]](/~megera/oddmuse/zen3.gif)
Олег Бартунов (ГАИШ МГУ), Федор Сигаев (ГАИШ МГУ)
В докладе представлен опыт участия российских разработчиков в крупном проекте с открытым кодом, СУБД 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 в ГАИШ МГУ Сергеем Копосовым при участии Олега Бартунова и которое широко используется не только в астрономии, но и в науках о Земле.
Отметим постоянную поддержку РФФИ, которая наряду с поддержкой заинтересованных компаний, позволила авторам реализовывать свои идеи и занять ведущее положение среди разработчиков проекта.
В докладе, также, будут затронуты вопросы продвижения разработчиков в крупных проектах и причины слабого присутствия российских разработчиков в них.
Российские спонсоры
Зарубежные спонсоры
Российские участники:
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);
Just upgraded my Nikon D90 to D700. http://www.flickr.com/photos/obartunov/4155280161/sizes/o/
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.
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:
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.
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.
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.
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
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.
=# 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'
=# 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
=# select '1 ? 1'::tsquery; tsquery ----------- '1' ? '1'
=# 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)
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 !
