Добро пожаловать в форум, Guest  >>   Войти | Регистрация | Поиск | Правила | В избранное | Подписаться
Все форумы / Сравнение СУБД Новый топик    Ответить
Топик располагается на нескольких страницах: Ctrl  назад   1 2 3 [4] 5   вперед  Ctrl      все
 Re: EAV с возможностью быстрой выборки по сложным условиям  [new]
web_fox
Member

Откуда: Киев
Сообщений: 444
Васисуалий Пупкинсон,

создадим для теста таблицу:

CREATE TABLE "public"."table1" (
  "id" INTEGER NOT NULL, 
  "property_arr" INTEGER[], 
  CONSTRAINT "table1_pkey" PRIMARY KEY("id")
) WITHOUT OIDS;

ALTER TABLE "public"."table1"
  ALTER COLUMN "id" SET STATISTICS 0;

CREATE INDEX "table1_idx" ON "public"."table1"
  USING gin ("property_arr" "public"."gin__int_ops");


Заполним 1 млн пользователей по 100 атрибутов со ссылками на 1000 значений:

TRUNCATE public.table1;

INSERT INTO public.table1
select s.i,
       array
       (
        select (random() * 1000)::integer + s.i - s.i
        from generate_series(1, 100) as s2(i)
       )
from generate_series(1, 1000000) as s(i);


analyze public.table1;


Поищем что-нибудь (тайминги домашнего компа):

select count(1) from public.table1 t1 where t1.property_arr @@ '1'
-----------
94802
1 rows fetched (172 ms)


select t1.id from public.table1 t1 where t1.property_arr @@ '(1|2|3|4|5|6|7|8|9|100|101|102|103|104|105|106|107|108|109|501|502|503|504|505|506|507|508|509)'
------------
941783
1 rows fetched (2,465 sec)


select t1.id from public.table1 t1 where t1.property_arr @@ '1&2&3&(4|5|6|7)'
-----------
273
1 rows fetched (328 ms)


select count(1) from public.table1 t1 where t1.property_arr @@ '1&!99&(9|10)'
15408
1 rows fetched (218 ms)

11 янв 11, 22:38    [10056745]     Ответить | Цитировать Сообщить модератору
 Re: EAV с возможностью быстрой выборки по сложным условиям  [new]
Васисуалий Пупкинсон
Member

Откуда: Москва
Сообщений: 23
web_fox
Васисуалий Пупкинсон,
создадим для теста таблицу
........

Спасибо! Завтра помедитирую над этим.
11 янв 11, 22:49    [10056788]     Ответить | Цитировать Сообщить модератору
 Re: EAV с возможностью быстрой выборки по сложным условиям  [new]
MasterZiv
Member

Откуда: Питер
Сообщений: 34709

On 11.01.2011 3:07, Васисуалий Пупкинсон wrote:

> не лезет ни в какие ворота (более 10 секунд). А если будет не очень селективный
> запрос с бОльшим числом параметров, то у пользователя определенно все зависнет.

Ты запрос-то покажи, и структуру.

Как бы проблема неселективных атрибутов -- она есть и от неё никуда не дется.
Только sort-merge join более менее может её решить, наверное. И то с большим
треском, с напрягом.

У тебя например есть два критерия -- мужчина и блондин. Две половины
таблицы про-JOIN-ить надо между собой и получить при этом, скажем, 1/8
таблицы в результате. Операция сложная, долгая, и особенно ничем не
ускоряемая.

Я даже пытался
> сделать сам такой велосипед посредством скрипта в Postgres. Но ничего путного из
> этого не вышло.

В PG вроде бы есть поддержка пространственных индексов. И вроде бы они то, что
надо. Не пробовал ?

Posted via ActualForum NNTP Server 1.4

12 янв 11, 00:53    [10057057]     Ответить | Цитировать Сообщить модератору
 Re: EAV с возможностью быстрой выборки по сложным условиям  [new]
SergSuper
Member

Откуда: SPb
Сообщений: 5488
Васисуалий Пупкинсон
SergSuper
вобще странно, мне кажется что для 100 тыч записей полное сканирование должно занимать доли секунды
может имеет смысл наиболее селективные атрибуты записывать в одну таблицу, делать простейший запрос, а потом проверять дополнительные атрибуты?


Я тестил для 100 тыс. пользователей, у которых в среднем есть по 50 атрибутов. Поэтому получилось 5 миллионов записей. А на 100 тыс. записей думаю да, проблем не было бы.
ну дык денормализуйте немного
у вас же основные критерии - это логика - так и храните их прямо в той же таблице битиками поля, на 50 аттрибутов хватит двух интежеров
в итоге таблица будет из записей по 20 байт ( 4 - ссылка на основные аттрибуты, 8 - 50 битовых атрибутов, 4 - возраст, 4 - город)
сканирование должно проходить мгновенно даже если и 5 млн записей
12 янв 11, 10:48    [10057891]     Ответить | Цитировать Сообщить модератору
 Re: EAV с возможностью быстрой выборки по сложным условиям  [new]
-2-
Member

Откуда:
Сообщений: 15330
SergSuper
ну дык денормализуйте немного
Нет смысла что-то изобретать
я@линух:~> find / -ls > big.table 2> /dev/null
я@линух:~> wc big.table
  535847  5917094 72173665 big.table
я@линух:~> head big.table
     2    4 drwxr-xr-x  27 root     root         4096 Oct 15 01:29 /
303105    4 drwxr-xr-x   4 root     root         4096 May  5  2010 /srv
303106    4 drwxr-xr-x   2 root     root         4096 May  5  2010 /srv/ftp
303107    4 drwxr-xr-x   4 root     root         4096 May  5  2010 /srv/www
303108    4 drwxr-xr-x   2 root     root         4096 May  5  2010 /srv/www/cgi-bin
303109    4 drwxr-xr-x   2 root     root         4096 May  5  2010 /srv/www/htdocs
163841   12 drwxr-xr-x   3 root     root        12288 Oct 14 15:30 /sbin
163898   60 -rwxr-xr-x   4 root     root        56488 May  8  2010 /sbin/mke2fs
163890  308 -rwxr-xr-x   2 root     root       307208 Feb 23  2009 /sbin/reiserfsck
163900    0 lrwxrwxrwx   1 root     root            3 Oct 11 12:39 /sbin/lvcreate -> lvm
я@линух:~> time awk '($5=="root"||size>1073741824)&&$8!="May"{s++}END{printf "Count=%d", s}' big.table
Count=157496
real    0m0.355s
user    0m0.344s
sys     0m0.008s
парс 500К строк 70МБ неструктурированного плоского файла - 0,35 сек
12 янв 11, 14:06    [10059542]     Ответить | Цитировать Сообщить модератору
 Re: EAV с возможностью быстрой выборки по сложным условиям  [new]
Васисуалий Пупкинсон
Member

Откуда: Москва
Сообщений: 23
web_fox
CREATE INDEX "table1_idx" ON "public"."table1"
USING gin ("property_arr" "public"."gin__int_ops");[/src]


Вот, наконец, дошли руки продолжить эту задачу. Попробовал испытать этот способ, но получаю ошибку:
"ERROR: operator class "public.gin__int_ops" does not exist for access method "gin""

Если я правильно понимаю, это значит что модуль intarray не установлен. Посмотрел в доках, там написано, что нужно запускать gmake для этого, если модуль не установлен, а если установлен, то скрипт из папки contrib. Но у меня в этой папке скрипта для intarray нет (т.е. похоже, что этот модуль нужно скачивать отдельно, но что-то нигде не видно, откуда его можно скачать), да и вообще, postgres (9-й) у меня сейчас установлен на Windows, да и без исходников.
Вобщем, что-то я с этим застрял. Если не трудно, подскажите, пожалуйста, что тут надо сделать, чтобы на gin__int_ops не ругалось, я просто с postgres до этого дела не имел вообще...
13 янв 11, 10:24    [10063742]     Ответить | Цитировать Сообщить модератору
 Re: EAV с возможностью быстрой выборки по сложным условиям  [new]
Ggg_old
Member

Откуда: Одесса
Сообщений: 1342
я думаю, что лучше вашу проблему с модулем gin озвучить в разделе по POstgre, ответ будет быстрее.
13 янв 11, 10:45    [10063918]     Ответить | Цитировать Сообщить модератору
 Re: EAV с возможностью быстрой выборки по сложным условиям  [new]
web_fox
Member

Откуда: Киев
Сообщений: 444
Васисуалий Пупкинсон,

у меня тоже на виндовс. Для виндовс достаточно просто запустить файл C:\Program Files\PostgreSQL\xxxxxx\share\contrib\_int.sql. И всё.

Качал я PG в виде инсталятора, а не бинарника.

Если у вас этого файла там почему-то нет и вы ставили через инсталятор, то пишите в профильный форум "Все форумы/PostgreSQL" - там ответят.
13 янв 11, 12:20    [10064805]     Ответить | Цитировать Сообщить модератору
 Re: EAV с возможностью быстрой выборки по сложным условиям  [new]
web_fox
Member

Откуда: Киев
Сообщений: 444
Васисуалий Пупкинсон,

кстати, на bitmap-поиске скорость на PG аналогичная, тока придётся создавать кучу индексов на кажд столбец и кучу колонок под каждый атрибут, ну вы знаете...
13 янв 11, 12:42    [10065050]     Ответить | Цитировать Сообщить модератору
 Re: EAV с возможностью быстрой выборки по сложным условиям  [new]
Васисуалий Пупкинсон
Member

Откуда: Москва
Сообщений: 23
web_fox
Васисуалий Пупкинсон,
у меня тоже на виндовс. Для виндовс достаточно просто запустить файл C:\Program Files\PostgreSQL\xxxxxx\share\contrib\_int.sql.

О, спасибо, сработало. Файл этот у меня есть, я просто думал, что он должен называться intarray.sql.
Жаль, что такой штуки нет для типа smallint, заметная экономия места была бы, да и ускорение опять-же.
13 янв 11, 13:42    [10065602]     Ответить | Цитировать Сообщить модератору
 Re: EAV с возможностью быстрой выборки по сложным условиям  [new]
web_fox
Member

Откуда: Киев
Сообщений: 444
-2-
MasterZiv
И тебе придётся таки трахаться с OR
create table test_bm 
...
-----------------------------------------------------------------------------------------------
| Id  | Operation                    | Name           | Rows  | Bytes | Cost (%CPU)| Time     |
-----------------------------------------------------------------------------------------------
|   0 | SELECT STATEMENT             |                | 16978 |   646K|    29   (0)| 00:00:01 |
|   1 |  TABLE ACCESS BY INDEX ROWID | TEST_BM        | 16978 |   646K|    29   (0)| 00:00:01 |
|   2 |   BITMAP CONVERSION TO ROWIDS|                |       |       |            |          |
|   3 |    BITMAP OR                 |                |       |       |            |          |
|   4 |     BITMAP MERGE             |                |       |       |            |          |
|*  5 |      BITMAP INDEX RANGE SCAN | TEST_BM#HEIGHT |       |       |            |          |
|   6 |     BITMAP MERGE             |                |       |       |            |          |
|*  7 |      BITMAP INDEX RANGE SCAN | TEST_BM#AGE    |       |       |            |          |


Попкорн съеден, ответа не дождались :)
13 янв 11, 15:35    [10066745]     Ответить | Цитировать Сообщить модератору
 Re: EAV с возможностью быстрой выборки по сложным условиям  [new]
MasterZiv
Member

Откуда: Питер
Сообщений: 34709

On 13.01.2011 15:35, web_fox wrote:

> -----------------------------------------------------------------------------------------------
> | Id | Operation | Name |Rows | Bytes | Cost (%CPU)| Time |
> -----------------------------------------------------------------------------------------------
> |*0* |SELECT STATEMENT | |*16978* | 646K|*29* (*0*)|*00*:*00*:*01* |
> |*1* |TABLE ACCESS BY INDEX ROWID | TEST_BM |*16978* | 646K|*29* (*0*)|*00*:*00*:*01* |
> |*2* | BITMAP CONVERSIONTO ROWIDS| | | | | |
> |*3* | BITMAPOR | | | | | |
> |*4* | BITMAP MERGE | | | | | |
> |**5* | BITMAPINDEX RANGE SCAN |TEST_BM#HEIGHT | | | | |
> |*6* | BITMAP MERGE | | | | | |
> |**7* | BITMAPINDEX RANGE SCAN |TEST_BM#AGE | | | | |
>
>
>
> Попкорн съеден, ответа не дождались :)

Ну круто, PG умеет это делать. Или это не PG ? Оракл ?
Ну рад за любого из них.

Posted via ActualForum NNTP Server 1.4

14 янв 11, 14:00    [10072600]     Ответить | Цитировать Сообщить модератору
 Re: EAV с возможностью быстрой выборки по сложным условиям  [new]
Apex
Member

Откуда: Made in USSR
Сообщений: 3910
MasterZiv
Ну круто, PG умеет это делать. Или это не PG ? Оракл ?
Ну рад за любого из них.

А что, кто-то не умеет?? Ну, не считая всякого бесплатного шлака, конечно.
15 янв 11, 17:04    [10077484]     Ответить | Цитировать Сообщить модератору
 Re: EAV с возможностью быстрой выборки по сложным условиям  [new]
MasterZiv
Member

Откуда: Питер
Сообщений: 34709

On 15.01.2011 17:04, Apex wrote:

> А что, кто-то не умеет?? Ну, не считая всякого бесплатного шлака, конечно.

Умеют далеко не все.

Posted via ActualForum NNTP Server 1.4

17 янв 11, 11:00    [10082893]     Ответить | Цитировать Сообщить модератору
 Re: EAV с возможностью быстрой выборки по сложным условиям  [new]
ScareCrow
Member

Откуда: Белый город
Сообщений: 17472
я вот уже 4 страницы не понимаю этот цирк. расскажите для кокой хотя бы немного реальной задачи нужно джойнить между собой 30 раз по миллиону записей?
17 янв 11, 23:04    [10087590]     Ответить | Цитировать Сообщить модератору
 Re: EAV с возможностью быстрой выборки по сложным условиям  [new]
web_fox
Member

Откуда: Киев
Сообщений: 444
ScareCrow,

а, может, вы просто приведёте свой вариант решения сразу на SQL без лишнего разговора про джоины, материальные представления и партицирования?

а мы посмотрим. Возможно, даже человеку поможете ;)
17 янв 11, 23:24    [10087633]     Ответить | Цитировать Сообщить модератору
 Re: EAV с возможностью быстрой выборки по сложным условиям  [new]
Васисуалий Пупкинсон
Member

Откуда: Москва
Сообщений: 23
ScareCrow
я вот уже 4 страницы не понимаю этот цирк. расскажите для кокой хотя бы немного реальной задачи нужно джойнить между собой 30 раз по миллиону записей?


Дык вот, поиск пользователей... 30 раз и миллион записей - это конечно не так уж чтобы совсем реально, но всё-таки хотелось бы иметь определенный запас прочности, чтобы даже и при таких условиях приложение давало ответ за более-менее разумное время.

На данный момент ситуация такова - попробовал разные способы, предложенные уважаемыми коллегами в этом топике, подходящий вариант найти трудно, т.к. сильно осложняет дело то обстоятельство, что результаты нужно выдавать в отсортированном виде (по времени регистрации пользователя), страницами. Если бы всё сводилось к тому, чтобы выдать просто некоторое количество любых пользователей, подходящих под указанные критерии, то отлично работал бы способ с gin индексом по intarray, предложенный web_fox-ом. Но в случае если подходящих под условие строк оказывается очень много, то серверу приходится сначала выбрать их все, отсортировать, и лишь потом выдать определенную порцию. И это сразу всё тормозит. Что касается gist индекса, то он не показывает особенно впечатляющих результатов.
Пробовал MongoDB. Вопреки ожиданиям, скорость поиска тоже не ахти. Использовал подход с Multikeys. То есть две колонки - _id (int) и а (массив int-ов длиной 100 элементов). Индекс по a. На миллионе записей запрос на наличие в атрибутах 6-ти указанный чисел выполняется секунд 40. Запрос такой:
attribute_values.find(a : {$all : [37, 45, 50, 60, 67, 90]}}, {_id : 1}).limit(20)
Смотрел explain, индекс используется. Черт его знает что за фигня, вроде всё правильно сделал... По идее, эта БД как раз ведь для таких задач и заточена...

Пробовал вариант с индивидуальной колонкой (и индексом по ней) для каждого атрибута (тестил для 200 колонок и миллиона записей). В принципе, работает неплохо, но очень уж неказистый сам способ, да и поддержка...

От формата EAV отказался совсем. Надежных по скорости результатов для любых ситуаций достичь затруднительно, мягко говоря.

Памятуя о неоднократных советах, данных в этом топике, использовать сквозное сканирование, как последнее средство решил испытать и это. И что вы думаете? Успех!
Испробовал вариант с битовой строкой длиной 250 бит (это в PostgreSQL), в котором каждому атрибуту соответствует определенная позиция в строке (дело в том, что у меня подавляющее большинство атрибутов - флаги, или можно свести атрибут к набору флагов).
Строк - миллион. То есть два поля - user_id и битовая строка. Коэффициент заполнения страниц поставил 100%, чтобы поплотнее запихнуть. Работает меньше секунды даже если нужно просмотреть всю таблицу. Конечно, надо было гораздо раньше это испробовать, но как-то интуитивно казалось, что при такой ширине строки перебор будет занимать всё-же слишком много времени.
Сегодня потестирую это более основательно, и если всё ок, не вылезет никаких граблей, то наверно на этом и остановлюсь, ибо просто и надежно. Да и запас прочности хороший.
18 янв 11, 10:59    [10088910]     Ответить | Цитировать Сообщить модератору
 Re: EAV с возможностью быстрой выборки по сложным условиям  [new]
Siemargl
Member

Откуда: 010100
Сообщений: 6641
Результат аховый =)

Я думаю, что с Монго что то не так. Потому что хранение там весьма компактное. Может убрать индекс, и там тоже будет фуллскан?
Причем в Монго чтение базы сделано через memory mapping.
18 янв 11, 11:36    [10089263]     Ответить | Цитировать Сообщить модератору
 Re: EAV с возможностью быстрой выборки по сложным условиям  [new]
web_fox
Member

Откуда: Киев
Сообщений: 444
Васисуалий Пупкинсон
Успех!

Ну, раз мы вам помогали, значит, ждём от вас публикации результатов :)

Покажите, пожалуйста, лучший по времени EXPLAIN ANALYZE каждого из трёх вариантов запроса (только на одинаковых данных c одинаковым поиском) с сортировкой, которую хотели, и т.п.:
1. Через отдельные колонки (там, где bitmap-скан будет).
2. Через intarray.
3. Через bit string.
18 янв 11, 13:05    [10090106]     Ответить | Цитировать Сообщить модератору
 Re: EAV с возможностью быстрой выборки по сложным условиям  [new]
ScareCrow
Member

Откуда: Белый город
Сообщений: 17472
web_fox
ScareCrow,

а, может, вы просто приведёте свой вариант решения сразу на SQL без лишнего разговора про джоины, материальные представления и партицирования?

а мы посмотрим. Возможно, даже человеку поможете ;)

все нормальные люди СНАЧАЛА выбирают 10/20/100 записей для показа, а ПОТОМ их джойнят со всем остальным.
18 янв 11, 13:31    [10090415]     Ответить | Цитировать Сообщить модератору
 Re: EAV с возможностью быстрой выборки по сложным условиям  [new]
-2-
Member

Откуда:
Сообщений: 15330
ScareCrow
все нормальные люди СНАЧАЛА выбирают 10/20/100 записей для показа, а ПОТОМ их джойнят со всем остальным.
Если я хочу 10 блондинок с ростом 180, возрастом 22-25 и весом 60-65кг, то сначала надо отобрать 10 человек, а потом приджоинить парики на лысину и отрезать все лишнее.
18 янв 11, 16:33    [10092030]     Ответить | Цитировать Сообщить модератору
 Re: EAV с возможностью быстрой выборки по сложным условиям  [new]
ScareCrow
Member

Откуда: Белый город
Сообщений: 17472
сортированы они по какому полю?
18 янв 11, 16:42    [10092121]     Ответить | Цитировать Сообщить модератору
 Re: EAV с возможностью быстрой выборки по сложным условиям  [new]
Alexander Ryndin
Member

Откуда:
Сообщений: 4919
Блог
ScareCrow
сортированы они по какому полю?
По первичному ключу.
18 янв 11, 16:50    [10092178]     Ответить | Цитировать Сообщить модератору
 Re: EAV с возможностью быстрой выборки по сложным условиям  [new]
iscrafm
Member [заблокирован]

Откуда:
Сообщений: 35345
ScareCrow
web_fox
ScareCrow,

а, может, вы просто приведёте свой вариант решения сразу на SQL без лишнего разговора про джоины, материальные представления и партицирования?

а мы посмотрим. Возможно, даже человеку поможете ;)

все нормальные люди СНАЧАЛА выбирают 10/20/100 записей для показа, а ПОТОМ их джойнят со всем остальным.

жесть
18 янв 11, 17:20    [10092388]     Ответить | Цитировать Сообщить модератору
 Re: EAV с возможностью быстрой выборки по сложным условиям  [new]
softwarer
Member

Откуда: 127.0.0.1
Сообщений: 67463
Блог
iscrafm
ScareCrow
все нормальные люди СНАЧАЛА выбирают 10/20/100 записей для показа, а ПОТОМ их джойнят со всем остальным.

жесть

Ну, в некотором смысле девушка права. Она только забыла упомянуть, что говорит о традиционном алгоритме знакомства на улице, а не о сайте знакомств
18 янв 11, 17:24    [10092404]     Ответить | Цитировать Сообщить модератору
Топик располагается на нескольких страницах: Ctrl  назад   1 2 3 [4] 5   вперед  Ctrl      все
Все форумы / Сравнение СУБД Ответить