GIST для hstore/tsearch2

Поиск
Список
Период
Сортировка
Искать

GIST для hstore/tsearch2

От:
"Ilia Kantor" <ilia@obnovlenie.ru>
Дата:

Насколько я понял, ключевой момент в GIST – хранение близких значений близко.

Т.е INSERT при помощи penalty выбирает самое “близкое” значение и вставляет туда.

 

Каким образом реализуется penalty/union в hstore/tsearch2 ?

 

В исходниках используется функция hemdist.. Возможно, в деле замешана дистанция Хэмминга..

Но почему она вычисляется побитно ?..

 

Т.е что там происходит-то толком, и почему оно работает ?!? ;)

Re: GIST для hstore/tsearc

От:
Teodor Sigaev <teodor@sigaev.ru>
Дата:


Ilia Kantor wrote:
> Насколько я понял, ключевой момент в GIST – хранение близких значений 
> близко.
Угу

> 
> Т.е INSERT при помощи penalty выбирает самое “близкое” значение и 
> вставляет туда.
Угу-2

> Каким образом реализуется penalty/union в hstore/tsearch2 ?
> 

Union - побитовое OR

penalty - в общем случае показывает насколько измениться некая мера при union 
старого ключа с новым. Для R-tree - изменение площади bounding box.  Для 
tsearch2/hstore - просто расстояние Хемминга между новым ключом и старым. Это 
мера была выбрана из нескольких по рез-татам экспериментов.


> В исходниках используется функция hemdist.. Возможно, в деле замешана 
> дистанция Хэмминга..
> 
> Но почему она вычисляется побитно ?..

Именно именно, разновидность дистанции Хэмминга. Грубо говоря, XOR'им два ключа 
и считаем кол-во единичек в результате. Т.е. в этих модулях нулевое расстояние 
имеют одинаковые ключи.

> Т.е что там происходит-то толком, и почему оно работает ?!? ;)

И tsearch2 и hstore используют Signature tree - дерево бинарных сигнатур. 
Указатель на страницу имеет побитовый OR всех ключей на странице.


-- 
Teodor Sigaev                                   E-mail: teodor@sigaev.ru
                                                    WWW: http://www.sigaev.ru/
FAQ