Re: many to many performance

Hi Craig,

Thank you for your answer.

Here are my test table and indecies definitions:

-- document id to category id
create table doc_to_cat (
doc_id integer not null,
cat_id integer not null
) with (oids=false);

-- Total 1m rows. 500k unique document ids. 20k unique category ids. Each doc_id refers to exactly two cat_id.
insert into doc_to_cat
select i/50*25 + i%50 as doc_id, i/50 as cat_id from generate_series(0, 1000000) i

create index doc_to_cat__doc_id on doc_to_cat using btree (doc_id);
create index doc_to_cat__cat_id on doc_to_cat using btree (cat_id);

-- document id to array of category ids
create table doc_to_cat_arr (
doc_id integer not null,
cat_arr integer[] not null
) with (oids=false);

insert into doc_to_cat_arr
select doc_id, int_array_aggregate(cat_id) as cat_arr
from doc_to_cat
group by doc_id

create index doc_to_cat_arr__doc_id on doc_to_cat_arr using btree (doc_id);

-- category id to array of document ids
create table cat_to_doc_arr (
cat_id integer not null,
doc_arr integer[] not null
) with (oids=false);

insert into cat_to_doc_arr
select cat_id, int_array_aggregate(doc_id) as doc_arr
from doc_to_cat
group by cat_id

create index cat_to_doc_arr__doc_arr__gin on cat_to_doc_arr using gin (doc_arr gin__int_ops);

-- Query Ids
create table query_ids (
doc_id integer not null
) with (oids=false);

-- 200k test ids for query with
insert into query_ids
select generate_series(100000, 300000);

create index query_ids__doc_id on query_ids using btree (doc_id);

Now queries plans. We are looking for cat_id having relations with 200k doc ids:

explain analyze
select distinct cat_id from doc_to_cat join query_ids using (doc_id)

"Unique (cost=19303.84..19602.03 rows=20544 width=4) (actual time=1006.745..1190.472 rows=8002 loops=1)"
" -> Sort (cost=19303.84..19452.93 rows=372735 width=4) (actual time=1006.743..1094.908 rows=400002 loops=1)"
" Sort Key: doc_to_cat.cat_id"
" Sort Method: quicksort Memory: 31039kB"
" -> Merge Join (cost=2972.22..13785.04 rows=372735 width=4) (actual time=167.591..750.177 rows=400002 loops=1)"
" Merge Cond: (query_ids.doc_id = doc_to_cat.doc_id)"
" -> Index Scan using query_ids_doc_id on query_ids (cost=0.00..2912.05 rows=200001 width=4) (actual time=0.021..81.291 rows=200001 loops=1)"
" -> Index Scan using doc_to_cat_doc_id on doc_to_cat (cost=0.00..14543.09 rows=1000001 width=8) (actual time=0.017..281.769 rows=599978 loops=1)"
"Total runtime: 1195.397 ms"

explain analyze
select distinct int_array_enum(cat_arr) from doc_to_cat_arr join query_ids using (doc_id)
"Unique (cost=13676.57..13836.57 rows=19732 width=29) (actual time=1061.490..1246.595 rows=8002 loops=1)"
" -> Sort (cost=13676.57..13756.57 rows=200001 width=29) (actual time=1061.488..1150.451 rows=400002 loops=1)"
" Sort Key: (int_array_enum(doc_to_cat_arr.cat_arr))"
" Sort Method: quicksort Memory: 31039kB"
" -> Merge Join (cost=2318.98..10859.01 rows=200001 width=29) (actual time=163.840..816.697 rows=400002 loops=1)"
" Merge Cond: (doc_to_cat_arr.doc_id = query_ids.doc_id)"
" -> Index Scan using doc_to_cat_arr_doc_id on doc_to_cat_arr (cost=0.00..11311.10 rows=500025 width=33) (actual time=0.022..359.673 rows=300002 loops=1)"
" -> Index Scan using query_ids_doc_id on query_ids (cost=0.00..2912.05 rows=200001 width=4) (actual time=0.016..81.370 rows=200001 loops=1)"
"Total runtime: 1251.613 ms"

explain analyze
select cat_id from cat_to_doc_arr
where doc_arr && (select int_array_aggregate(q.doc_id) from (select doc_id from query_ids limit 20000) as q)
This query should never be run - too slow even with limit 20k of input ids.

So .. final best result is more than 1 second (on fast machine) for test dataset 5 times less than needed. So I am far away from achieving good results.
I have to ask again if anyone faced similar situation, and is there any way to achive closer to optimal performance using postgresql functionality and extensibility?

Chavdar Kopoev

-----Original Message-----
From: Craig Ringer [mailto:craig(at)postnewspapers(dot)com(dot)au]
Sent: 2008-11-26, 19:40:47
To: Chavdar Kopoev [mailto:chavdar(at)kopoev(dot)com]
Subject: Re: [PERFORM] many to many performance

Chavdar Kopoev wrote:

> I want to use as a data storage postgresql. Tried several data structures, testing btree, gin, gist indecies over them, but best achieved performance for a 10 times smaller dataset (10k cat ids, 100k doc ids, 1m relations) is slower more than 5 times.

Can you post your queries and table definitions so people trying to help
you know what you did / tried to do? A downloadable self contained
example might also be useful.

Please also post the output of `EXPLAIN' on your queries, eg:

EXPLAIN SELECT blah, ... FROM blah;

> I read about postgresql bitmap indecies and "data lookup" when scanning indecies to get a value for current transaction. Downloaded latest v8.4 snapshot, compiled it, but as I see there is no bitmap index in it. Maybe if I download HEAD revision I will find them there, dont know.

Bitmap index scans are an internal function that's used to combine two
indexes on the fly during a query (or at least use both of them in one
table scan). You don't make a bitmap index, you just make two ordinary
btree indexes and let Pg take care of this for you.

If you query on the columns of interest a lot, you might want to use a
multi-column index instead.

--
Craig Ringer