Thread: Re: [pgsql-ru-general] Дистанция cube, как выбрать ближайшие чтобы из индекса?

Всем привет.

Обновил патч на текущую базу кода. Взять можно на ветке в джитхабе
https://github.com/kelvich/postgresql/compare/distances?expand=1или из того письма по ссылке Олега. 

С ним в той же ситуации план такой:

CREATE TABLE t (id integer, c cube);
INSERT INTO "t"
     SELECT
        generate_series(1, 1000000) AS "id",
        cube(ARRAY[random(), random(), random(), random()]) AS "c";
CREATE INDEX on t using gist(c);
EXPLAIN ANALYZE
        SELECT
            "id", "c" <-> cube(ARRAY[0.3,0.3,0.3,0.3])  AS "dist"
        FROM
            "t"
        ORDER BY
            "c" <-> cube(ARRAY[0.3,0.3,0.3,0.3])
        LIMIT 10;
                                                          QUERY PLAN
       

-------------------------------------------------------------------------------------------------------------------------------
 Limit  (cost=0.41..1.49 rows=10 width=44) (actual time=9.869..11.160 rows=10 loops=1)
   ->  Index Scan using t_c_idx on t  (cost=0.41..107568.41 rows=1000000 width=44) (actual time=9.867..11.155 rows=10
loops=1)
         Order By: (c <-> '(0.3, 0.3, 0.3, 0.3)'::cube)
 Planning time: 0.129 ms
 Execution time: 11.859 ms

Патч сейчас пошлю на commitfest и постараюсь довести его до момента включения в основную ветку.

Стас Кельвич.


On Oct 5, 2014, at 3:04 PM, Oleg Bartunov <obartunov@gmail.com> wrote:

> Вам нужно попробовать патч Стаса для куба, поищите в -hackers за прошлый год. Стас, проясни ситуацию с патчем, плиз.
>
> http://www.postgresql.org/message-id/9E07E159-E405-41E2-9889-A04F534FC257@gmail.com
>
> Олег
>
> 2014-10-05 11:33 GMT+04:00 Dmitry E. Oboukhov <unera@debian.org>:
>                          Таблица "public.t"
>  Колонка |   Тип   |                  Модификаторы
> ---------+---------+------------------------------------------------
>  id      | integer | NOT NULL DEFAULT nextval('t_id_seq'::regclass)
>  p       | point   |
> Индексы:
>     "t_p_gist_idx" gist (p)
>
> INSERT INTO "t"
>      SELECT
>         generate_series(1, 1000000) AS "id",
>         point(random(), random()) AS "p";
>
> EXPLAIN ANALYZE
>     SELECT
>         "id", point(0.3, 0.3) <-> p
>     FROM
>         "t"
>     ORDER BY
>         point(0.3, 0.3) <-> p
>     LIMIT 10;
>
>  Limit  (cost=0.29..1.10 rows=10 width=20) (actual time=0.248..0.276 rows=10 loops=1)
>    ->  Index Scan using t_p_gist_idx on t  (cost=0.29..81860.29 rows=1000000 width=20) (actual time=0.246..0.269
rows=10loops=1) 
>          Order By: (p <-> '(0.3,0.3)'::point)
>  Total runtime: 0.320 ms
> (4 строки)
>
> Для точек - прям то что надо, работает чистый index scan и лимит.
>
> Продолжаем эксперимент:
>
> ALTER TABLE "t"
>     ADD COLUMN "c" cube NOT NULL
>         DEFAULT cube(ARRAY[random(), random(), random(), random()]);
>
> CREATE INDEX "t_c_gist_idx" ON "t" USING GIST ("c");
>
> Далее выбираем ближайшие кубы по аналогии с точками
>
> EXPLAIN ANALYZE
>     SELECT
>         "id", cube_distance("c", cube(ARRAY[0.3,0.3,0.3,0.3])) AS "dist"
>     FROM
>         "t"
>     ORDER BY
>         cube_distance("c", cube(ARRAY[0.3,0.3,0.3,0.3]))
>     LIMIT 10;
>
>
>  Limit  (cost=49494.64..49494.67 rows=10 width=36) (actual time=791.093..791.098 rows=10 loops=1)
>    ->  Sort  (cost=49494.64..51994.64 rows=1000000 width=36) (actual time=791.090..791.092 rows=10 loops=1)
>          Sort Key: (cube_distance(c, '(0.3, 0.3, 0.3, 0.3)'::cube))
>          Sort Method: top-N heapsort  Memory: 25kB
>          ->  Seq Scan on t  (cost=0.00..27885.00 rows=1000000 width=36) (actual time=0.041..507.259 rows=1000000
loops=1)
>  Total runtime: 791.137 ms
> (6 строк)
>
>
> То есть видно что в случае с точками выборка ближайших соседей -
> выборка нескольких элементов из индекса.
>
> в случае с кубом - это еще и сортировка всей таблицы из миллиона
> элементов.
>
> соответственно для точек получается 0.3мс, для кубов 791 мс.
>
>
> я так полагаю что cube не определяет дистанцию для индекса, либо я
> как-то не включил ее использование.
>
> Вопрос: как привести EXPLAIN по cube к такому же виду как по point?
>
> --
>
> . ''`.                               Dmitry E. Oboukhov
> : :’  :   email: unera@debian.org jabber://UNera@uvw.ru
> `. `~’              GPGKey: 1024D / F8E26537 2006-11-21
>   `- 1B23 D4F8 8EC0 D902 0555  E438 AB8C 00CF F8E2 6537
>
> -----BEGIN PGP SIGNATURE-----
> Version: GnuPG v1.4.10 (GNU/Linux)
>
> iEYEAREDAAYFAlQw9E0ACgkQq4wAz/jiZTdhwACfRr9PIppB1cJ0egIExvXzH9cp
> pIAAoKHEpNeFRZPxE+VV52oUCmZ4ecST
> =XLdI
> -----END PGP SIGNATURE-----
>
>

> Всем привет.

> Обновил патч на текущую базу кода. Взять можно на ветке в джитхабе
https://github.com/kelvich/postgresql/compare/distances?expand=1или из того письма по ссылке Олега. 

спасибо огромное.

можно будет knn делать на этой штуковине.

Народ, а скажите вот такую штуку.

на докладе на митапе показывали как картинки индексируют итп.
похожие находят.

только я не очень понимаю как это к KNN привести.

вот допустим у меня есть некая функция, которая вычисляет dist между
двумя картинками

select dist(img1, img2)

допустим 0.52

select dist(img2, img3)

допустим 0.64

Далее хотим это дело в cube положить

но как?

я игрался на том что клал в cube так:
(предполагаем что картинкочная похожесть - один из критериев KNN)

insert into ... cube(ARRAY[a,b,c,dist(img0, img_i)])

такой подход работает, но очень большие трудности с выбором img0

для картинок или слов - непонятно что делать опорой

или есть еще какие-то варианты как в индекс складывать что-то между
чем вычисляются расстояния, но базы нет?



--

. ''`.                               Dmitry E. Oboukhov
: :’  :   email: unera@debian.org jabber://UNera@uvw.ru
`. `~’              GPGKey: 1024D / F8E26537 2006-11-21
  `- 1B23 D4F8 8EC0 D902 0555  E438 AB8C 00CF F8E2 6537

И для картинок и для семантики в базу сохраняются вектора. Картинку в вектор Саша переводил своей тулзой
https://github.com/akorotkov/imgsmlr(если просто, то сначала преобразование Фурье, потом усреднение по участкам и
получаетсяматрица 4х4) для слов можно брать https://code.google.com/p/word2vec/
 

On Oct 16, 2014, at 11:04 PM, Dmitry E. Oboukhov <unera@debian.org> wrote:

>> Всем привет.
> 
>> Обновил патч на текущую базу кода. Взять можно на ветке в джитхабе
https://github.com/kelvich/postgresql/compare/distances?expand=1или из того письма по ссылке Олега.
 
> 
> спасибо огромное.
> 
> можно будет knn делать на этой штуковине.
> 
> Народ, а скажите вот такую штуку.
> 
> на докладе на митапе показывали как картинки индексируют итп.
> похожие находят.
> 
> только я не очень понимаю как это к KNN привести.
> 
> вот допустим у меня есть некая функция, которая вычисляет dist между
> двумя картинками
> 
> select dist(img1, img2)
> 
> допустим 0.52
> 
> select dist(img2, img3)
> 
> допустим 0.64
> 
> Далее хотим это дело в cube положить
> 
> но как?
> 
> я игрался на том что клал в cube так:
> (предполагаем что картинкочная похожесть - один из критериев KNN)
> 
> insert into ... cube(ARRAY[a,b,c,dist(img0, img_i)])
> 
> такой подход работает, но очень большие трудности с выбором img0
> 
> для картинок или слов - непонятно что делать опорой
> 
> или есть еще какие-то варианты как в индекс складывать что-то между
> чем вычисляются расстояния, но базы нет?
> 
> 
> 
> -- 
> 
> . ''`.                               Dmitry E. Oboukhov
> : :’  :   email: unera@debian.org jabber://UNera@uvw.ru
> `. `~’              GPGKey: 1024D / F8E26537 2006-11-21
>  `- 1B23 D4F8 8EC0 D902 0555  E438 AB8C 00CF F8E2 6537

> И для картинок и для семантики в базу сохраняются вектора. Картинку в вектор Саша переводил своей тулзой
https://github.com/akorotkov/imgsmlr(если просто, то сначала преобразование Фурье, потом усреднение по участкам и
получаетсяматрица 4х4) для слов можно брать https://code.google.com/p/word2vec/ 

спасибо посмотрю

то есть я правильно понял что для картинок получаем 16 чиселок,
которые храним в cube?

--

. ''`.                               Dmitry E. Oboukhov
: :’  :   email: unera@debian.org jabber://UNera@uvw.ru
`. `~’              GPGKey: 1024D / F8E26537 2006-11-21
  `- 1B23 D4F8 8EC0 D902 0555  E438 AB8C 00CF F8E2 6537

Всё так, храним числа. А потом выбираем ближайшие по теореме Пифагора.

On Oct 17, 2014, at 10:27 AM, Dmitry E. Oboukhov <unera@debian.org> wrote:

>
> то есть я правильно понял что для картинок получаем 16 чиселок,
> которые храним в cube?
>
> --
>
> . ''`.                               Dmitry E. Oboukhov
> : :’  :   email: unera@debian.org jabber://UNera@uvw.ru
> `. `~’              GPGKey: 1024D / F8E26537 2006-11-21
>  `- 1B23 D4F8 8EC0 D902 0555  E438 AB8C 00CF F8E2 6537