Обсуждение: GIST для hstore/tsearch2
Насколько я понял, ключевой момент в GIST – хранение близких значений близко.
Т.е INSERT при помощи penalty выбирает самое “близкое” значение и вставляет туда.
Каким образом реализуется penalty/union в hstore/tsearch2 ?
В исходниках используется функция hemdist.. Возможно, в деле замешана дистанция Хэмминга..
Но почему она вычисляется побитно ?..
Т.е что там происходит-то толком, и почему оно работает ?!? ;)
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/