вторник, 15 сентября 2009 г.

Тестирование PostgreSQL 8.1 на больших таблицах: денормализация

Как один из вариантов оптимизации скорости выборки может быть использована денормализация таблиц. Продолжим работать с тем же тестовым распределением, но теперь в таблице фактов заменим числовые ключи на строковые значения, соответствующие значениям из справочников. Для генерации тестового распределения использована приведенная ниже функция, создающая строки из символа "0", повторенного случайное число раз от нуля до заданного аргументом значения.

Для вычисления времени выполнения запроса на этот раз использую команду explain analyze, хотя имхо она дает заниженное значение времени. Количество возвращаемых строк также можно увидеть в выводе названной команды, но из соображений удобства привожу и результат запроса на получение числа строк.

Параметры сервера:

Intel(R) Core(TM)2 Quad CPU Q6700 @ 2.66GHz
MemTotal: 8310900 kB


Параметры сервера PostgreSQL:

work_mem = 100000 # min 64, size in KB
maintenance_work_mem = 2000000 # min 1024, size in KB
shared_buffers = 200000 # min 16 or max_connections*2, 8KB each


PostgreSQL version

select version();
version
----------------------------------------------------------------------------------------------------------------
PostgreSQL 8.1.15 on i486-pc-linux-gnu, compiled by GCC cc (GCC) 4.1.2 20061115 (prerelease) (Debian 4.1.1-21)
(1 row)


Вспомогательные функции:

CREATE OR REPLACE FUNCTION public.populate_varstring(length int)
RETURNS text AS
$BODY$

return [string repeat 0 [expr {round($1*rand())}]]

$BODY$
LANGUAGE 'pltcl' VOLATILE;


CREATE OR REPLACE FUNCTION public.populate_string(length int)
RETURNS text AS
$BODY$

return [string repeat 0 $1]

$BODY$
LANGUAGE 'pltcl' VOLATILE;


Нормализованная таблица без справочников (10M записей)

create table tmp_facts7(a1 int,a2 int,a3 int,a4 int);
insert into tmp_facts7(a1,a2,a3,a4) select (18*random())::int,(18*random())::int,
(18*random())::int,(18*random())::int from generate_series(1,10000000);

create index tmp_facts7_a1_idx on tmp_facts7(a1);
create index tmp_facts7_a2_idx on tmp_facts7(a2);
create index tmp_facts7_a3_idx on tmp_facts7(a3);
create index tmp_facts7_a4_idx on tmp_facts7(a4);

select count(*) from tmp_facts7 where a1=2 and a2=2 and a3=2 and a4=2;
count
-------
102
(1 row)

explain analyze select * from tmp_facts7 where a1=2 and a2=2 and a3=2 and a4=2;
QUERY PLAN
---------------------------------------------------------------------------------------------------------------------------------------------
Bitmap Heap Scan on tmp_facts7 (cost=858.50..862.52 rows=1 width=16) (actual time=312.659..315.412 rows=102 loops=1)
Recheck Cond: ((a4 = 2) AND (a3 = 2) AND (a2 = 2))
Filter: (a1 = 2)
-> BitmapAnd (cost=858.50..858.50 rows=1 width=0) (actual time=311.972..311.972 rows=0 loops=1)
-> Bitmap Index Scan on tmp_facts7_a4_idx (cost=0.00..286.00 rows=50000 width=0) (actual time=94.804..94.804 rows=555224 loops=1)
Index Cond: (a4 = 2)
-> Bitmap Index Scan on tmp_facts7_a3_idx (cost=0.00..286.00 rows=50000 width=0) (actual time=97.709..97.709 rows=555616 loops=1)
Index Cond: (a3 = 2)
-> Bitmap Index Scan on tmp_facts7_a2_idx (cost=0.00..286.00 rows=50000 width=0) (actual time=94.862..94.862 rows=555418 loops=1)
Index Cond: (a2 = 2)
Total runtime: 315.702 ms

SELECT relname, relpages, reltuples FROM pg_class
WHERE NOT relname LIKE 'pg_%' ORDER BY relpages DESC;

relname | relpages | reltuples
----------------------------------------+----------+-------------
tmp_facts7 | 58824 | 1e+07
tmp_facts7_a1_idx | 21899 | 1e+07
tmp_facts7_a2_idx | 21899 | 1e+07
tmp_facts7_a3_idx | 21899 | 1e+07
tmp_facts7_a4_idx | 21899 | 1e+07


Нормализованная таблица со справочниками (10M записей + 10,100,1k,10k записей в справочниках)

drop table tmp_facts7_a1;
create table tmp_facts7_a1(id int, name text);
insert into tmp_facts7_a1
select generate_series,populate_string(generate_series) from generate_series(1,10);
create index tmp_facts7_a1_name_idx on tmp_facts7_a1(name);


drop table tmp_facts7_a2;
create table tmp_facts7_a2(id int, name text);
insert into tmp_facts7_a2
select generate_series,populate_string(generate_series) from generate_series(1,100);
create index tmp_facts7_a2_name_idx on tmp_facts7_a2(name);


drop table tmp_facts7_a3;
create table tmp_facts7_a3(id int, name text);
insert into tmp_facts7_a3
select generate_series,populate_string(generate_series) from generate_series(1,1000);
create index tmp_facts7_a3_name_idx on tmp_facts7_a3(name);


drop table tmp_facts7_a4;
create table tmp_facts7_a4(id int, name text);
insert into tmp_facts7_a4
select generate_series,populate_string(generate_series) from generate_series(1,10000);
create index tmp_facts7_a4_name_idx on tmp_facts7_a4(name);

select count(*)
from tmp_facts7
join tmp_facts7_a1 on tmp_facts7.a1=tmp_facts7_a1.id
join tmp_facts7_a2 on tmp_facts7.a2=tmp_facts7_a2.id
join tmp_facts7_a3 on tmp_facts7.a3=tmp_facts7_a3.id
join tmp_facts7_a4 on tmp_facts7.a4=tmp_facts7_a4.id
where tmp_facts7_a1.name='00' and tmp_facts7_a2.name='00' and tmp_facts7_a3.name='00' and tmp_facts7_a4.name='00';
90

explain analyze
select count(*)
from tmp_facts7
join tmp_facts7_a1 on tmp_facts7.a1=tmp_facts7_a1.id
join tmp_facts7_a2 on tmp_facts7.a2=tmp_facts7_a2.id
join tmp_facts7_a3 on tmp_facts7.a3=tmp_facts7_a3.id
join tmp_facts7_a4 on tmp_facts7.a4=tmp_facts7_a4.id
where tmp_facts7_a1.name='00' and tmp_facts7_a2.name='00' and tmp_facts7_a3.name='00' and tmp_facts7_a4.name='00';
QUERY PLAN
-------------------------------------------------------------------------------------------------------------------------------------------------------------
Aggregate (cost=210529.30..210529.31 rows=1 width=0) (actual time=12160.879..12160.880 rows=1 loops=1)
-> Hash Join (cost=164.09..210529.22 rows=33 width=0) (actual time=53.455..12160.696 rows=90 loops=1)
Hash Cond: ("outer".a4 = "inner".id)
-> Hash Join (cost=21.98..210384.80 rows=132 width=4) (actual time=2.790..12159.510 rows=1747 loops=1)
Hash Cond: ("outer".a1 = "inner".id)
-> Hash Join (cost=20.85..210369.85 rows=2500 width=8) (actual time=1.326..12144.334 rows=30961 loops=1)
Hash Cond: ("outer".a3 = "inner".id)
-> Hash Join (cost=3.25..209827.25 rows=100000 width=12) (actual time=0.083..11806.323 rows=556026 loops=1)
Hash Cond: ("outer".a2 = "inner".id)
-> Seq Scan on tmp_facts7 (cost=0.00..158824.00 rows=10000000 width=16) (actual time=0.002..6252.510 rows=10000000 loops=1)
-> Hash (cost=3.25..3.25 rows=1 width=4) (actual time=0.037..0.037 rows=1 loops=1)
-> Seq Scan on tmp_facts7_a2 (cost=0.00..3.25 rows=1 width=4) (actual time=0.002..0.034 rows=1 loops=1)
Filter: (name = '00'::text)
-> Hash (cost=17.59..17.59 rows=5 width=4) (actual time=0.024..0.024 rows=1 loops=1)
-> Bitmap Heap Scan on tmp_facts7_a3 (cost=2.02..17.59 rows=5 width=4) (actual time=0.022..0.022 rows=1 loops=1)
Recheck Cond: (name = '00'::text)
-> Bitmap Index Scan on tmp_facts7_a3_name_idx (cost=0.00..2.02 rows=5 width=0) (actual time=0.019..0.019 rows=1 loops=1)
Index Cond: (name = '00'::text)
-> Hash (cost=1.12..1.12 rows=1 width=4) (actual time=0.013..0.013 rows=1 loops=1)
-> Seq Scan on tmp_facts7_a1 (cost=0.00..1.12 rows=1 width=4) (actual time=0.007..0.010 rows=1 loops=1)
Filter: (name = '00'::text)
-> Hash (cost=141.98..141.98 rows=50 width=4) (actual time=0.044..0.044 rows=1 loops=1)
-> Bitmap Heap Scan on tmp_facts7_a4 (cost=2.17..141.98 rows=50 width=4) (actual time=0.042..0.042 rows=1 loops=1)
Recheck Cond: (name = '00'::text)
-> Bitmap Index Scan on tmp_facts7_a4_name_idx (cost=0.00..2.17 rows=50 width=0) (actual time=0.038..0.038 rows=1 loops=1)
Index Cond: (name = '00'::text)
Total runtime: 12160.956 ms

select count(*)
from tmp_facts7
where
tmp_facts7.a1 IN (select id from tmp_facts7_a1 where name='00') and
tmp_facts7.a2 IN (select id from tmp_facts7_a2 where name='00') and
tmp_facts7.a3 IN (select id from tmp_facts7_a3 where name='00') and
tmp_facts7.a4 IN (select id from tmp_facts7_a4 where name='00');
90

QUERY PLAN
--------------------------------------------------------------------------------------------------------------------------------------------------------------------------
Aggregate (cost=208849.46..208849.47 rows=1 width=0) (actual time=11530.444..11530.444 rows=1 loops=1)
-> Hash IN Join (cost=10.41..208849.45 rows=1 width=0) (actual time=54.422..11530.272 rows=90 loops=1)
Hash Cond: ("outer".a1 = "inner".id)
-> Hash IN Join (cost=9.28..208848.31 rows=1 width=4) (actual time=4.918..11529.142 rows=1711 loops=1)
Hash Cond: ("outer".a2 = "inner".id)
-> Hash IN Join (cost=6.03..208845.04 rows=1 width=8) (actual time=0.388..11513.718 rows=30963 loops=1)
Hash Cond: ("outer".a3 = "inner".id)
-> Hash IN Join (cost=3.02..208837.02 rows=1000 width=12) (actual time=0.083..11252.212 rows=556092 loops=1)
Hash Cond: ("outer".a4 = "inner".id)
-> Seq Scan on tmp_facts7 (cost=0.00..158824.00 rows=10000000 width=16) (actual time=0.009..6100.572 rows=10000000 loops=1)
-> Hash (cost=3.01..3.01 rows=1 width=4) (actual time=0.067..0.067 rows=1 loops=1)
-> Index Scan using tmp_facts7_a4_name_idx on tmp_facts7_a4 (cost=0.00..3.01 rows=1 width=4) (actual time=0.065..0.066 rows=1 loops=1)
Index Cond: (name = '00'::text)
-> Hash (cost=3.01..3.01 rows=1 width=4) (actual time=0.051..0.051 rows=1 loops=1)
-> Index Scan using tmp_facts7_a3_name_idx on tmp_facts7_a3 (cost=0.00..3.01 rows=1 width=4) (actual time=0.048..0.049 rows=1 loops=1)
Index Cond: (name = '00'::text)
-> Hash (cost=3.25..3.25 rows=1 width=4) (actual time=0.036..0.036 rows=1 loops=1)
-> Seq Scan on tmp_facts7_a2 (cost=0.00..3.25 rows=1 width=4) (actual time=0.003..0.034 rows=1 loops=1)
Filter: (name = '00'::text)
-> Hash (cost=1.12..1.12 rows=1 width=4) (actual time=0.013..0.013 rows=1 loops=1)
-> Seq Scan on tmp_facts7_a1 (cost=0.00..1.12 rows=1 width=4) (actual time=0.007..0.011 rows=1 loops=1)
Filter: (name = '00'::text)
Total runtime: 11530.519 ms


select count(*)
from tmp_facts7,tmp_facts7_a1,tmp_facts7_a2,tmp_facts7_a3,tmp_facts7_a4
where tmp_facts7.a1=tmp_facts7_a1.id and tmp_facts7.a2=tmp_facts7_a2.id and tmp_facts7.a3=tmp_facts7_a3.id and tmp_facts7.a4=tmp_facts7_a4.id
and tmp_facts7_a1.name='00' and tmp_facts7_a2.name='00' and tmp_facts7_a3.name='00' and tmp_facts7_a4.name='00';
90


explain analyze
select count(*)
from tmp_facts7,tmp_facts7_a1,tmp_facts7_a2,tmp_facts7_a3,tmp_facts7_a4
where tmp_facts7.a1=tmp_facts7_a1.id and tmp_facts7.a2=tmp_facts7_a2.id and tmp_facts7.a3=tmp_facts7_a3.id and tmp_facts7.a4=tmp_facts7_a4.id
and tmp_facts7_a1.name='00' and tmp_facts7_a2.name='00' and tmp_facts7_a3.name='00' and tmp_facts7_a4.name='00';
QUERY PLAN
--------------------------------------------------------------------------------------------------------------------------------------------------------------------------
Aggregate (cost=208849.46..208849.47 rows=1 width=0) (actual time=11471.422..11471.423 rows=1 loops=1)
-> Hash Join (cost=10.41..208849.45 rows=1 width=0) (actual time=55.361..11471.247 rows=90 loops=1)
Hash Cond: ("outer".a1 = "inner".id)
-> Hash Join (cost=9.28..208848.31 rows=1 width=4) (actual time=5.006..11470.182 rows=1711 loops=1)
Hash Cond: ("outer".a2 = "inner".id)
-> Hash Join (cost=6.03..208845.04 rows=1 width=8) (actual time=0.419..11454.973 rows=30963 loops=1)
Hash Cond: ("outer".a3 = "inner".id)
-> Hash Join (cost=3.02..208837.02 rows=1000 width=12) (actual time=0.100..11194.330 rows=556092 loops=1)
Hash Cond: ("outer".a4 = "inner".id)
-> Seq Scan on tmp_facts7 (cost=0.00..158824.00 rows=10000000 width=16) (actual time=0.011..6054.843 rows=10000000 loops=1)
-> Hash (cost=3.01..3.01 rows=1 width=4) (actual time=0.083..0.083 rows=1 loops=1)
-> Index Scan using tmp_facts7_a4_name_idx on tmp_facts7_a4 (cost=0.00..3.01 rows=1 width=4) (actual time=0.080..0.081 rows=1 loops=1)
Index Cond: (name = '00'::text)
-> Hash (cost=3.01..3.01 rows=1 width=4) (actual time=0.059..0.059 rows=1 loops=1)
-> Index Scan using tmp_facts7_a3_name_idx on tmp_facts7_a3 (cost=0.00..3.01 rows=1 width=4) (actual time=0.056..0.057 rows=1 loops=1)
Index Cond: (name = '00'::text)
-> Hash (cost=3.25..3.25 rows=1 width=4) (actual time=0.049..0.049 rows=1 loops=1)
-> Seq Scan on tmp_facts7_a2 (cost=0.00..3.25 rows=1 width=4) (actual time=0.010..0.048 rows=1 loops=1)
Filter: (name = '00'::text)
-> Hash (cost=1.12..1.12 rows=1 width=4) (actual time=0.025..0.025 rows=1 loops=1)
-> Seq Scan on tmp_facts7_a1 (cost=0.00..1.12 rows=1 width=4) (actual time=0.019..0.022 rows=1 loops=1)
Filter: (name = '00'::text)
Total runtime: 11471.499 ms


Денормализованная таблица (10M записей)

create table tmp_facts7(a1 text,a2 text,a3 text,a4 text);
insert into tmp_facts7(a1,a2,a3,a4)
select populate_varstring(18),populate_varstring(18),populate_varstring(18),populate_varstring(18) from generate_series(1,10000000);

create index tmp_facts7_a1_idx on tmp_facts7(a1);
create index tmp_facts7_a2_idx on tmp_facts7(a2);
create index tmp_facts7_a3_idx on tmp_facts7(a3);
create index tmp_facts7_a4_idx on tmp_facts7(a4);

select count(*) from tmp_facts7 where a1='0000000000' and a2='0000000000' and a3='0000000000' and a4='0000000000';
count
-------
94
(1 row)

explain analyze select count(*) from tmp_facts7 where a1='0000000000' and a2='0000000000' and a3='0000000000' and a4='0000000000';
QUERY PLAN
-------------------------------------------------------------------------------------------------------------------------------------------------------
Aggregate (cost=16271.06..16271.07 rows=1 width=0) (actual time=567.677..567.678 rows=1 loops=1)
-> Bitmap Heap Scan on tmp_facts7 (cost=15897.42..16270.82 rows=95 width=0) (actual time=567.458..567.643 rows=94 loops=1)
Recheck Cond: ((a1 = '0000000000'::text) AND (a3 = '0000000000'::text) AND (a2 = '0000000000'::text) AND (a4 = '0000000000'::text))
-> BitmapAnd (cost=15897.42..15897.42 rows=95 width=0) (actual time=567.270..567.270 rows=0 loops=1)
-> Bitmap Index Scan on tmp_facts7_a1_idx (cost=0.00..3933.47 rows=550133 width=0) (actual time=128.749..128.749 rows=555230 loops=1)
Index Cond: (a1 = '0000000000'::text)
-> Bitmap Index Scan on tmp_facts7_a3_idx (cost=0.00..3943.60 rows=551600 width=0) (actual time=130.825..130.825 rows=556203 loops=1)
Index Cond: (a3 = '0000000000'::text)
-> Bitmap Index Scan on tmp_facts7_a2_idx (cost=0.00..3974.53 rows=555867 width=0) (actual time=126.721..126.721 rows=555106 loops=1)
Index Cond: (a2 = '0000000000'::text)
-> Bitmap Index Scan on tmp_facts7_a4_idx (cost=0.00..4045.07 rows=565733 width=0) (actual time=132.243..132.243 rows=555891 loops=1)
Index Cond: (a4 = '0000000000'::text)
Total runtime: 568.144 ms

SELECT relname, relpages, reltuples FROM pg_class
WHERE NOT relname LIKE 'pg_%' ORDER BY relpages DESC;
relname | relpages | reltuples
------------------------------------+----------+-----------
tmp_facts7 | 111003 | 1e+07
tmp_facts7_a1_idx | 36469 | 1e+07
tmp_facts7_a2_idx | 36468 | 1e+07
tmp_facts7_a3_idx | 36467 | 1e+07
tmp_facts7_a4_idx | 36467 | 1e+07


Выводы

При денормализации таблицы размер самой таблицы и индексов примерно удвоился, и во столько же раз упала скорость выборки. Заметим, что при тесте все данные помещались в буфере СУБД, при работе с диском можно ожидать худших результатов.

Что касается выборки из нормализованной таблицы со справочниками, то результаты просто отвратительные. Если присмотреться, то из каждого справочника выборается единственное значение (равное числу 2), и запрос должен выполняться с той же скоростью, что и при выборке из таблицы фактов с указанными значениями идентификаторов справочников.

суббота, 12 сентября 2009 г.

Тестирование SQLite 3.6.17-mobigroup.2 на больших таблицах

Цель данного тестирования - проверить работу в SQLite тестов, написанных при тестировании PostgreSQL и убедиться, какая из СУБД более подходит для работы с большими БД.

Параметры сервера/Server parameters:

Intel(R) Core(TM)2 Quad CPU Q6700 @ 2.66GHz
MemTotal: 8310900 kB


Параметры БД SQLite/SQLite parameters:

sqlite> pragma page_size;
4096
sqlite> pragma cache_size;
400000

Размер кэша выбран равный использованному при тестировании PostgreSQL (в рассматриваемых СУБД используются разные размеры страниц, поэтому кэш в обоих случаях 1,6 Gb, хотя абсолютные значения параметров отличаются). Функция intrange2table, используемая для создания тестового распределения, предоставляется одним из расширений, доступных в deb-пакете, а также в исходных текстах.

The SQLite cache size is equal to PostgreSQL cache size. The PostgreSQL databases are using 8 kB page size by default. SQlite cache size is measured in pages (4kB in my configuration) but not on kilobytes. The intrange2table() function for SQLite may be downloaded by links above.

Размеры тестовых БД/Test DB sizes

ls -lah ~|grep test|grep db
-rw-r--r-- 1 veter veter 73M 2009-09-12 14:35 test6.db
-rw-r--r-- 1 veter veter 759M 2009-09-12 14:46 test7.db
-rw-r--r-- 1 veter veter 7.8G 2009-09-12 15:10 test8.db


Тест базы 1 М записей./1 M records

sqlite3 ~/test6.db

create temp table tmp_facts(rowid int);
select intrange2table (1,1000000,1,'tmp_facts');
create table facts(a1 int,a2 int,a3 int,a4 int);

insert into facts
select
cast(abs(random())/9223372036854775807.*10 as int),
cast(abs(random())/9223372036854775807.*10 as int),
cast(abs(random())/9223372036854775807.*10 as int),
cast(abs(random())/9223372036854775807.*10 as int)
from tmp_facts;

create index facts_a1_idx on facts(a1);
create index facts_a2_idx on facts(a2);
create index facts_a3_idx on facts(a3);
create index facts_a4_idx on facts(a4);

select count(*) from facts where a1=2 and a2=2 and a3=2 and a4=2;
92
CPU Time: user 0.152010 sys 0.000000

explain query plan select count(*) from facts where a1=2 and a2=2 and a3=2 and a4=2;
0|0|TABLE facts WITH INDEX facts_a4_idx

С композитным индексом/With composite index:

create index facts_complex_idx on facts(a1,a2,a3,a4);

select count(*) from facts where a1=2 and a2=2 and a3=2 and a4=2;
92
CPU Time: user 0.000000 sys 0.000000

explain query plan select count(*) from facts where a1=2 and a2=2 and a3=2 and a4=2;
0|0|TABLE facts WITH INDEX facts_complex_idx

select count(*)
from facts
join (select 2 as a1) as x1 on x1.a1=facts.a1
join (select 2 as a2) as x2 on x2.a2=facts.a2
join (select 2 as a3) as x3 on x3.a3=facts.a3
join (select 2 as a4) as x4 on x4.a4=facts.a4;
92
CPU Time: user 0.000000 sys 0.000000

explain query plan
select count(*)
from facts
join (select 2 as a1) as x1 on x1.a1=facts.a1
join (select 2 as a2) as x2 on x2.a2=facts.a2
join (select 2 as a3) as x3 on x3.a3=facts.a3
join (select 2 as a4) as x4 on x4.a4=facts.a4;
0|1|TABLE AS x1
1|2|TABLE AS x2
2|3|TABLE AS x3
3|4|TABLE AS x4
4|0|TABLE facts WITH INDEX facts_complex_idx


Тест базы 10 М записей./10 M records

sqlite3 ~/test7.db

create temp table tmp_facts(rowid int);
select intrange2table (1,10000000,1,'tmp_facts');
create table facts(a1 int,a2 int,a3 int,a4 int);

insert into facts
select
cast(abs(random())/9223372036854775807.*18 as int),
cast(abs(random())/9223372036854775807.*18 as int),
cast(abs(random())/9223372036854775807.*18 as int),
cast(abs(random())/9223372036854775807.*18 as int)
from tmp_facts;

create index facts_a1_idx on facts(a1);
create index facts_a2_idx on facts(a2);
create index facts_a3_idx on facts(a3);
create index facts_a4_idx on facts(a4);

select count(*) from facts where a1=2 and a2=2 and a3=2 and a4=2;
97
CPU Time: user 0.924057 sys 0.000000

explain query plan select count(*) from facts where a1=2 and a2=2 and a3=2 and a4=2;
0|0|TABLE facts WITH INDEX facts_a4_idx

С композитным индексом/With composite index:

create index facts_complex_idx on facts(a1,a2,a3,a4);

select count(*) from facts where a1=2 and a2=2 and a3=2 and a4=2;
97
CPU Time: user 0.000000 sys 0.000000

explain query plan select count(*) from facts where a1=2 and a2=2 and a3=2 and a4=2;
0|0|TABLE facts WITH INDEX facts_complex_idx

select count(*)
from facts
join (select 2 as a1) as x1 on x1.a1=facts.a1
join (select 2 as a2) as x2 on x2.a2=facts.a2
join (select 2 as a3) as x3 on x3.a3=facts.a3
join (select 2 as a4) as x4 on x4.a4=facts.a4;
97
CPU Time: user 0.000000 sys 0.000000

explain query plan
select count(*)
from facts
join (select 2 as a1) as x1 on x1.a1=facts.a1
join (select 2 as a2) as x2 on x2.a2=facts.a2
join (select 2 as a3) as x3 on x3.a3=facts.a3
join (select 2 as a4) as x4 on x4.a4=facts.a4;
0|1|TABLE AS x1
1|2|TABLE AS x2
2|3|TABLE AS x3
3|4|TABLE AS x4
4|0|TABLE facts WITH INDEX facts_complex_idx


Тест базы 100 М записей./100 M records

sqlite3 ~/test8.db

create temp table tmp_facts(rowid int);
select intrange2table (1,100000000,1,'tmp_facts');
create table facts(a1 int,a2 int,a3 int,a4 int);

insert into facts
select
cast(abs(random())/9223372036854775807.*33 as int),
cast(abs(random())/9223372036854775807.*33 as int),
cast(abs(random())/9223372036854775807.*33 as int),
cast(abs(random())/9223372036854775807.*33 as int)
from tmp_facts;

create index facts_a1_idx on facts(a1);
create index facts_a2_idx on facts(a2);
create index facts_a3_idx on facts(a3);
create index facts_a4_idx on facts(a4);

select count(*) from facts where a1=2 and a2=2 and a3=2 and a4=2;
95
CPU Time: user 6.244390 sys 0.004000

explain query plan select count(*) from facts where a1=2 and a2=2 and a3=2 and a4=2;
0|0|TABLE facts WITH INDEX facts_a4_idx

С композитным индексом/With composite index:

create index facts_complex_idx on facts(a1,a2,a3,a4);

select count(*) from facts where a1=2 and a2=2 and a3=2 and a4=2;
95
CPU Time: user 0.000000 sys 0.000000

explain query plan select count(*) from facts where a1=2 and a2=2 and a3=2 and a4=2;
0|0|TABLE facts WITH INDEX facts_complex_idx

select count(*)
from facts
join (select 2 as a1) as x1 on x1.a1=facts.a1
join (select 2 as a2) as x2 on x2.a2=facts.a2
join (select 2 as a3) as x3 on x3.a3=facts.a3
join (select 2 as a4) as x4 on x4.a4=facts.a4;
95
CPU Time: user 0.000000 sys 0.000000

explain query plan
select count(*)
from facts
join (select 2 as a1) as x1 on x1.a1=facts.a1
join (select 2 as a2) as x2 on x2.a2=facts.a2
join (select 2 as a3) as x3 on x3.a3=facts.a3
join (select 2 as a4) as x4 on x4.a4=facts.a4;
0|1|TABLE AS x1
1|2|TABLE AS x2
2|3|TABLE AS x3
3|4|TABLE AS x4
4|0|TABLE facts WITH INDEX facts_complex_idx


Обсуждение:
Используется только 1 индекс, это плохо. Но с этим одним индексом выборка из таблицы 1 M работает быстрее, чем в PostgreSQL с 3-мя индексами.

Композитный индекс позволяет сделать время выборки исчезающе малым, независимо от размера таблицы (когда-то гонял тесты на таблицах до 100 Гб, регрессии не заметил). Притом JOIN-ы используют композитный индекс, тогда как PostgreSQL этого не умеет.

Для практических целей достаточно композитного индекса не по всем столбцам. Например, использование в данном тесте индекса по 2-м столбцам позволит на порядок обогнать постгрес.

Для ускорения запросов можно использовать пересечение индексных выборок в тех случаях, когда требуется оптимизация при работе с раздельными индексами.

Размер идентичной БД SQLite ровно вдвое меньше, чем в PostgreSQL - база 1 М занимает 73 и 144 Мб соответственно. Кроме того, PostgreSQL хранит дополнительные логи и журналы транзакций, что также требует дополнительного места.

Выборки SQLite меньше зависят от размеров доступного пространства ОЗУ, большой кэш требуется только при модификации больших объемов данных. Таким образом, когда размер БД превышает размер ОЗУ, деградации производительности не происходит.

R-tree индекс не рассматриваем, т.к. сравнение выполнялось только для стандартного b-tree индекса в PostgreSQL и SQLite.

Резюме:

В SQLite не хватает аналога постгресного bitmap index scan, позволяющего слияние одинарных индексов при выборках и сортировках. Выборка по одному индексу (простому или композитному) работает лучше, чем в PostgreSQL.

bitmap index scan зачастую лучше заменять на композитный индекс даже в PostgreSQL, т.к. производительность первого намного уступает второму решению. Будет разумным полагать, что эта техника пригодна для некритичных к скорости выборки БД, когда можно пожертвовать преимуществами композитного индекса взамен простоты разработки и построения запросов - фактически, к этой категории можно отнести значительную часть всех применений БД. Для интересующих автора OLPT-систем с реалтайм отчетностью по актуальным данным и в PostgreSQl и в SQLite пригодны только композитные индексы.

В процессе тестирования от нашего взгляда ускользнула методика измерения времени запроса. Все запросы выполнялись при активном кэшировании файла БД операционной системой, об этом свидетельствуют сообщения вида "sys 0.000000". С учетом этого параметра можно многое узнать и при первом выполнении запроса на БД, не находящейся в кэше ОС, но это выходит за рамки нашего рассмотрения.

пятница, 11 сентября 2009 г.

Тестирование PostgreSQL 8.1 на больших таблицах

В очередной раз "ввязался" в дискуссию о разработке больших баз данных на СУБД PostgreSQL. В ходе обсуждения появилась необходимость провести численные измерения скорости выполнения запросов на базах разного масштаба. Так же обнаружилось, что в PostgreSQL 8.3 планировщик работает получше, но принципиальной разницы нет, т.к. того же самого поведения можно добиться и в 8.1.

Выполнено:
Проверил 1 М, 10 М и 100 М записей с тремя индексами (запрос по 4-м полям, но каждый раз использовалось только 3 индекса). Размер выборки во всех случаях был практически идентичный. Для того, чтобы заставить постгрес пользоваться индексами, были подобраны параметры тестового распределения. При 100 М записей постгрес не смог создать индекс после вставки всех записей, требуя больше памяти, потому индексы создавались до вставки. Время измерено в pgadmin, все запросы работали по "горячему кэшу", т.е. запускались несколько раз подряд до стабилизации времени выборки (для 100 М таблицы первые 3 запуска время выполнения было около 40-ка секунд, и только на 4-м запуске кэш "разогрелся").

Параметры сервера:

Intel(R) Core(TM)2 Quad CPU Q6700 @ 2.66GHz
MemTotal: 8310900 kB


Параметры сервера PostgrSQL:

work_mem = 100000 # min 64, size in KB
maintenance_work_mem = 2000000 # min 1024, size in KB
shared_buffers = 200000 # min 16 or max_connections*2, 8KB each


Версия сервера PostgrSQL:

select version();
version
----------------------------------------------------------------------------------------------------------------
PostgreSQL 8.1.15 on i486-pc-linux-gnu, compiled by GCC cc (GCC) 4.1.2 20061115 (prerelease) (Debian 4.1.1-21)
(1 row)


Размеры тестовых таблиц и индексов (кол-во 8к блоков):

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

SELECT relname, relpages, reltuples FROM pg_class
WHERE NOT relname LIKE 'pg_%' ORDER BY relpages DESC;
relname | relpages | reltuples
------------------------------------+----------+-------------
tmp_facts8 | 575323 | 9.00079e+07
tmp_facts8_a2_idx | 279976 | 9.00079e+07
tmp_facts8_a4_idx | 279811 | 9.00079e+07
tmp_facts8_a1_idx | 279740 | 9.00079e+07
tmp_facts8_a3_idx | 279652 | 9.00079e+07
tmp_facts7 | 58824 | 1e+07
tmp_facts7_a1_idx | 21899 | 1e+07
tmp_facts7_a2_idx | 21899 | 1e+07
tmp_facts7_a3_idx | 21899 | 1e+07
tmp_facts7_a4_idx | 21899 | 1e+07
tmp_facts6 | 5883 | 1e+06
tmp_facts6_a1_idx | 2193 | 1e+06
tmp_facts6_a2_idx | 2193 | 1e+06
tmp_facts6_a3_idx | 2193 | 1e+06
tmp_facts6_a4_idx | 2193 | 1e+06


С индексами по каждому из столбцов и с композитным индексом по всем столбцам:

SELECT relname, relpages, reltuples FROM pg_class
WHERE NOT relname LIKE 'pg_%' ORDER BY relpages DESC;
relname | relpages | reltuples
------------------------------------+----------+-----------
tmp_facts7 | 58824 | 1e+07
tmp_facts7_complex_idx | 38506 | 1e+07
tmp_facts7_a1_idx | 21899 | 1e+07
tmp_facts7_a2_idx | 21899 | 1e+07
tmp_facts7_a3_idx | 21899 | 1e+07
tmp_facts7_a4_idx | 21899 | 1e+07
tmp_facts6 | 5883 | 1e+06
tmp_facts6_complex_idx | 3853 | 1e+06
tmp_facts6_a1_idx | 2193 | 1e+06
tmp_facts6_a2_idx | 2193 | 1e+06
tmp_facts6_a3_idx | 2193 | 1e+06
tmp_facts6_a4_idx | 2193 | 1e+06

Для 100 М не удалось провести тест с композитным индексом, см. примечания ниже.

Тест базы 1 М записей.

create table tmp_facts6(a1 int,a2 int,a3 int,a4 int);
insert into tmp_facts6(a1,a2,a3,a4) select (10*random())::int,(10*random())::int,
(10*random())::int,(10*random())::int from generate_series(1,1000000);

create index tmp_facts6_a1_idx on tmp_facts6(a1);
create index tmp_facts6_a2_idx on tmp_facts6(a2);
create index tmp_facts6_a3_idx on tmp_facts6(a3);
create index tmp_facts6_a4_idx on tmp_facts6(a4);

select count(*) from tmp_facts6 where a1=2 and a2=2 and a3=2 and a4=2;
90
140 ms

explain select * from tmp_facts6 where a1=2 and a2=2 and a3=2 and a4=2;
QUERY PLAN
------------------------------------------------------------------------------------------
Bitmap Heap Scan on tmp_facts6 (cost=89.00..93.02 rows=1 width=16)
Recheck Cond: ((a4 = 2) AND (a3 = 2) AND (a2 = 2))
Filter: (a1 = 2)
-> BitmapAnd (cost=89.00..89.00 rows=1 width=0)
-> Bitmap Index Scan on tmp_facts6_a4_idx (cost=0.00..29.50 rows=5000 width=0)
Index Cond: (a4 = 2)
-> Bitmap Index Scan on tmp_facts6_a3_idx (cost=0.00..29.50 rows=5000 width=0)
Index Cond: (a3 = 2)
-> Bitmap Index Scan on tmp_facts6_a2_idx (cost=0.00..29.50 rows=5000 width=0)
Index Cond: (a2 = 2)
(10 rows)

select count(*) from tmp_facts6 where a1 in (select 2) and a2 in (select 2)
and a3 in (select 2) and a4 in (select 2);
90
233 ms

explain select * from tmp_facts6 where a1 in (select 2) and a2 in (select 2)
and a3 in (select 2) and a4 in (select 2);
QUERY PLAN
-----------------------------------------------------------------------------------------------------------------------
Hash IN Join (cost=0.11..40561.47 rows=68 width=16)
Hash Cond: ("outer".a1 = "inner"."?column?")
-> Hash IN Join (cost=0.09..40557.01 rows=751 width=16)
Hash Cond: ("outer".a3 = "inner"."?column?")
-> Hash IN Join (cost=0.07..40508.16 rows=8264 width=16)
Hash Cond: ("outer".a4 = "inner"."?column?")
-> Merge Join (cost=0.04..39970.95 rows=90909 width=16)
Merge Cond: ("outer"."?column?" = "inner".a2)
-> Sort (cost=0.04..0.05 rows=1 width=4)
Sort Key: "IN_subquery"."?column?"
-> HashAggregate (cost=0.02..0.03 rows=1 width=4)
-> Result (cost=0.00..0.01 rows=1 width=0)
-> Index Scan using tmp_facts6_a2_idx on tmp_facts6 (cost=0.00..36561.81 rows=1000000 width=16)
-> Hash (cost=0.02..0.02 rows=1 width=4)
-> Result (cost=0.00..0.01 rows=1 width=0)
-> Hash (cost=0.02..0.02 rows=1 width=4)
-> Result (cost=0.00..0.01 rows=1 width=0)
-> Hash (cost=0.02..0.02 rows=1 width=4)
-> Result (cost=0.00..0.01 rows=1 width=0)
(19 rows)

select count(*)
from tmp_facts6
join (select 2 as a1) as x1 on x1.a1=tmp_facts6.a1
join (select 2 as a2) as x2 on x2.a2=tmp_facts6.a2
join (select 2 as a3) as x3 on x3.a3=tmp_facts6.a3
join (select 2 as a4) as x4 on x4.a4=tmp_facts6.a4;
90
205 ms

explain select count(*)
from tmp_facts6
join (select 2 as a1) as x1 on x1.a1=tmp_facts6.a1
join (select 2 as a2) as x2 on x2.a2=tmp_facts6.a2
join (select 2 as a3) as x3 on x3.a3=tmp_facts6.a3
join (select 2 as a4) as x4 on x4.a4=tmp_facts6.a4;
QUERY PLAN
-----------------------------------------------------------------------------------------------------------------------------
Aggregate (cost=40561.63..40561.64 rows=1 width=0)
-> Hash Join (cost=0.10..40561.46 rows=68 width=0)
Hash Cond: ("outer".a1 = "inner".a1)
-> Hash Join (cost=0.08..40557.00 rows=751 width=4)
Hash Cond: ("outer".a3 = "inner".a3)
-> Hash Join (cost=0.05..40508.15 rows=8264 width=8)
Hash Cond: ("outer".a4 = "inner".a4)
-> Merge Join (cost=0.03..39970.94 rows=90909 width=12)
Merge Cond: ("outer".a2 = "inner".a2)
-> Sort (cost=0.03..0.04 rows=1 width=4)
Sort Key: x2.a2
-> Result (cost=0.00..0.01 rows=1 width=0)
-> Index Scan using tmp_facts6_a2_idx on tmp_facts6 (cost=0.00..36561.81 rows=1000000 width=16)
-> Hash (cost=0.02..0.02 rows=1 width=4)
-> Result (cost=0.00..0.01 rows=1 width=0)
-> Hash (cost=0.02..0.02 rows=1 width=4)
-> Result (cost=0.00..0.01 rows=1 width=0)
-> Hash (cost=0.02..0.02 rows=1 width=4)
-> Result (cost=0.00..0.01 rows=1 width=0)
(19 rows)

С композитным индексом:

create index tmp_facts6_complex_idx on tmp_facts6(a1,a2,a3,a4);

select count(*) from tmp_facts6 where a1=2 and a2=2 and a3=2 and a4=2;
90
35 ms

explain select count(*) from tmp_facts6 where a1=2 and a2=2 and a3=2 and a4=2;
QUERY PLAN
---------------------------------------------------------------------------------------------
Aggregate (cost=370.14..370.15 rows=1 width=0)
-> Bitmap Heap Scan on tmp_facts6 (cost=3.12..369.88 rows=102 width=0)
Recheck Cond: ((a1 = 2) AND (a2 = 2) AND (a3 = 2) AND (a4 = 2))
-> Bitmap Index Scan on tmp_facts6_complex_idx (cost=0.00..3.12 rows=102 width=0)
Index Cond: ((a1 = 2) AND (a2 = 2) AND (a3 = 2) AND (a4 = 2))
(5 rows)

select count(*)
from tmp_facts6
join (select 2 as a1) as x1 on x1.a1=tmp_facts6.a1
join (select 2 as a2) as x2 on x2.a2=tmp_facts6.a2
join (select 2 as a3) as x3 on x3.a3=tmp_facts6.a3
join (select 2 as a4) as x4 on x4.a4=tmp_facts6.a4;
90
220 ms

explain select count(*)
from tmp_facts6
join (select 2 as a1) as x1 on x1.a1=tmp_facts6.a1
join (select 2 as a2) as x2 on x2.a2=tmp_facts6.a2
join (select 2 as a3) as x3 on x3.a3=tmp_facts6.a3
join (select 2 as a4) as x4 on x4.a4=tmp_facts6.a4;
QUERY PLAN
-----------------------------------------------------------------------------------------------------------------------------
Aggregate (cost=40561.63..40561.64 rows=1 width=0)
-> Hash Join (cost=0.10..40561.46 rows=68 width=0)
Hash Cond: ("outer".a1 = "inner".a1)
-> Hash Join (cost=0.08..40557.00 rows=751 width=4)
Hash Cond: ("outer".a3 = "inner".a3)
-> Hash Join (cost=0.05..40508.15 rows=8264 width=8)
Hash Cond: ("outer".a4 = "inner".a4)
-> Merge Join (cost=0.03..39970.94 rows=90909 width=12)
Merge Cond: ("outer".a2 = "inner".a2)
-> Sort (cost=0.03..0.04 rows=1 width=4)
Sort Key: x2.a2
-> Result (cost=0.00..0.01 rows=1 width=0)
-> Index Scan using tmp_facts6_a2_idx on tmp_facts6 (cost=0.00..36561.81 rows=1000000 width=16)
-> Hash (cost=0.02..0.02 rows=1 width=4)
-> Result (cost=0.00..0.01 rows=1 width=0)
-> Hash (cost=0.02..0.02 rows=1 width=4)
-> Result (cost=0.00..0.01 rows=1 width=0)
-> Hash (cost=0.02..0.02 rows=1 width=4)
-> Result (cost=0.00..0.01 rows=1 width=0)
(19 rows)



Тест базы 10 М записей.

create table tmp_facts7(a1 int,a2 int,a3 int,a4 int);
insert into tmp_facts7(a1,a2,a3,a4) select (18*random())::int,(18*random())::int,
(18*random())::int,(18*random())::int from generate_series(1,10000000);

create index tmp_facts7_a1_idx on tmp_facts7(a1);
create index tmp_facts7_a2_idx on tmp_facts7(a2);
create index tmp_facts7_a3_idx on tmp_facts7(a3);
create index tmp_facts7_a4_idx on tmp_facts7(a4);

select count(*) from tmp_facts7 where a1=2 and a2=2 and a3=2 and a4=2;
94
370 ms

explain select * from tmp_facts7 where a1=2 and a2=2 and a3=2 and a4=2;
QUERY PLAN
--------------------------------------------------------------------------------------------
Bitmap Heap Scan on tmp_facts7 (cost=858.50..862.52 rows=1 width=16)
Recheck Cond: ((a4 = 2) AND (a3 = 2) AND (a2 = 2))
Filter: (a1 = 2)
-> BitmapAnd (cost=858.50..858.50 rows=1 width=0)
-> Bitmap Index Scan on tmp_facts7_a4_idx (cost=0.00..286.00 rows=50000 width=0)
Index Cond: (a4 = 2)
-> Bitmap Index Scan on tmp_facts7_a3_idx (cost=0.00..286.00 rows=50000 width=0)
Index Cond: (a3 = 2)
-> Bitmap Index Scan on tmp_facts7_a2_idx (cost=0.00..286.00 rows=50000 width=0)
Index Cond: (a2 = 2)
(10 rows)

select count(*) from tmp_facts7 where a1 in (select 2) and a2 in (select 2)
and a3 in (select 2) and a4 in (select 2);
94
1140 ms

explain select * from tmp_facts7 where a1 in (select 2) and a2 in (select 2)
and a3 in (select 2) and a4 in (select 2);
QUERY PLAN
-------------------------------------------------------------------------------------------------------------------------
Hash IN Join (cost=0.10..403957.90 rows=77 width=16)
Hash Cond: ("outer".a1 = "inner"."?column?")
-> Hash IN Join (cost=0.08..403949.81 rows=1458 width=16)
Hash Cond: ("outer".a2 = "inner"."?column?")
-> Hash IN Join (cost=0.05..403796.71 rows=27701 width=16)
Hash Cond: ("outer".a3 = "inner"."?column?")
-> Merge IN Join (cost=0.03..400888.09 rows=526316 width=16)
Merge Cond: ("outer".a4 = "inner"."?column?")
-> Index Scan using tmp_facts7_a4_idx on tmp_facts7 (cost=0.00..366677.53 rows=10000000 width=16)
-> Sort (cost=0.03..0.04 rows=1 width=4)
Sort Key: "IN_subquery"."?column?"
-> Result (cost=0.00..0.01 rows=1 width=0)
-> Hash (cost=0.02..0.02 rows=1 width=4)
-> Result (cost=0.00..0.01 rows=1 width=0)
-> Hash (cost=0.02..0.02 rows=1 width=4)
-> Result (cost=0.00..0.01 rows=1 width=0)
-> Hash (cost=0.02..0.02 rows=1 width=4)
-> Result (cost=0.00..0.01 rows=1 width=0)
(18 rows)

select count(*)
from tmp_facts7
join (select 2 as a1) as x1 on x1.a1=tmp_facts7.a1
join (select 2 as a2) as x2 on x2.a2=tmp_facts7.a2
join (select 2 as a3) as x3 on x3.a3=tmp_facts7.a3
join (select 2 as a4) as x4 on x4.a4=tmp_facts7.a4;
94
1106 ms

explain select count(*)
from tmp_facts7
join (select 2 as a1) as x1 on x1.a1=tmp_facts7.a1
join (select 2 as a2) as x2 on x2.a2=tmp_facts7.a2
join (select 2 as a3) as x3 on x3.a3=tmp_facts7.a3
join (select 2 as a4) as x4 on x4.a4=tmp_facts7.a4;
QUERY PLAN
-------------------------------------------------------------------------------------------------------------------------------
Aggregate (cost=400010.73..400010.74 rows=1 width=0)
-> Hash Join (cost=0.10..400010.53 rows=77 width=0)
Hash Cond: ("outer".a1 = "inner".a1)
-> Hash Join (cost=0.08..400002.45 rows=1458 width=4)
Hash Cond: ("outer".a2 = "inner".a2)
-> Hash Join (cost=0.05..399849.34 rows=27701 width=8)
Hash Cond: ("outer".a3 = "inner".a3)
-> Merge Join (cost=0.03..396940.73 rows=526316 width=12)
Merge Cond: ("outer".a4 = "inner".a4)
-> Sort (cost=0.03..0.04 rows=1 width=4)
Sort Key: x4.a4
-> Result (cost=0.00..0.01 rows=1 width=0)
-> Index Scan using tmp_facts7_a4_idx on tmp_facts7 (cost=0.00..366677.53 rows=10000000 width=16)
-> Hash (cost=0.02..0.02 rows=1 width=4)
-> Result (cost=0.00..0.01 rows=1 width=0)
-> Hash (cost=0.02..0.02 rows=1 width=4)
-> Result (cost=0.00..0.01 rows=1 width=0)
-> Hash (cost=0.02..0.02 rows=1 width=4)
-> Result (cost=0.00..0.01 rows=1 width=0)
(19 rows)

С композитным индексом:

create index tmp_facts7_complex_idx on tmp_facts7(a1,a2,a3,a4);

select count(*) from tmp_facts7 where a1=2 and a2=2 and a3=2 and a4=2;
94
54 ms

explain select count(*) from tmp_facts7 where a1=2 and a2=2 and a3=2 and a4=2;
QUERY PLAN
--------------------------------------------------------------------------------------------
Aggregate (cost=373.44..373.45 rows=1 width=0)
-> Bitmap Heap Scan on tmp_facts7 (cost=3.04..373.20 rows=95 width=0)
Recheck Cond: ((a1 = 2) AND (a2 = 2) AND (a3 = 2) AND (a4 = 2))
-> Bitmap Index Scan on tmp_facts7_complex_idx (cost=0.00..3.04 rows=95 width=0)
Index Cond: ((a1 = 2) AND (a2 = 2) AND (a3 = 2) AND (a4 = 2))
(5 rows)


select count(*)
from tmp_facts7
join (select 2 as a1) as x1 on x1.a1=tmp_facts7.a1
join (select 2 as a2) as x2 on x2.a2=tmp_facts7.a2
join (select 2 as a3) as x3 on x3.a3=tmp_facts7.a3
join (select 2 as a4) as x4 on x4.a4=tmp_facts7.a4;
94
1150 ms

explain select count(*)
from tmp_facts7
join (select 2 as a1) as x1 on x1.a1=tmp_facts7.a1
join (select 2 as a2) as x2 on x2.a2=tmp_facts7.a2
join (select 2 as a3) as x3 on x3.a3=tmp_facts7.a3
join (select 2 as a4) as x4 on x4.a4=tmp_facts7.a4;
QUERY PLAN
-------------------------------------------------------------------------------------------------------------------------------
Aggregate (cost=400010.73..400010.74 rows=1 width=0)
-> Hash Join (cost=0.10..400010.53 rows=77 width=0)
Hash Cond: ("outer".a1 = "inner".a1)
-> Hash Join (cost=0.08..400002.45 rows=1458 width=4)
Hash Cond: ("outer".a2 = "inner".a2)
-> Hash Join (cost=0.05..399849.34 rows=27701 width=8)
Hash Cond: ("outer".a3 = "inner".a3)
-> Merge Join (cost=0.03..396940.73 rows=526316 width=12)
Merge Cond: ("outer".a4 = "inner".a4)
-> Sort (cost=0.03..0.04 rows=1 width=4)
Sort Key: x4.a4
-> Result (cost=0.00..0.01 rows=1 width=0)
-> Index Scan using tmp_facts7_a4_idx on tmp_facts7 (cost=0.00..366677.53 rows=10000000 width=16)
-> Hash (cost=0.02..0.02 rows=1 width=4)
-> Result (cost=0.00..0.01 rows=1 width=0)
-> Hash (cost=0.02..0.02 rows=1 width=4)
-> Result (cost=0.00..0.01 rows=1 width=0)
-> Hash (cost=0.02..0.02 rows=1 width=4)
-> Result (cost=0.00..0.01 rows=1 width=0)
(19 rows)


Тест базы 100 М записей.

drop table tmp_facts8;
create table tmp_facts8(a1 int,a2 int,a3 int,a4 int);
create index tmp_facts8_a1_idx on tmp_facts8(a1);
create index tmp_facts8_a2_idx on tmp_facts8(a2);
create index tmp_facts8_a3_idx on tmp_facts8(a3);
create index tmp_facts8_a4_idx on tmp_facts8(a4);
insert into tmp_facts8(a1,a2,a3,a4) select (33*random())::int,(33*random())::int,
(33*random())::int,(33*random())::int from generate_series(1,10000000);
... выполняем 10 раз для вставки 100 М записей


select count(*) from tmp_facts8 where a1=2 and a2=2 and a3=2 and a4=2;
80
2260 ms

explain select * from tmp_facts8 where a1=2 and a2=2 and a3=2 and a4=2;
QUERY PLAN
------------------------------------------------------------------------------------------------
Bitmap Heap Scan on tmp_facts8 (cost=55213.58..64940.47 rows=78 width=16)
Recheck Cond: ((a1 = 2) AND (a3 = 2) AND (a2 = 2))
Filter: (a4 = 2)
-> BitmapAnd (cost=55213.58..55213.58 rows=2550 width=0)
-> Bitmap Index Scan on tmp_facts8_a1_idx (cost=0.00..18275.05 rows=2765444 width=0)
Index Cond: (a1 = 2)
-> Bitmap Index Scan on tmp_facts8_a3_idx (cost=0.00..18432.87 rows=2789678 width=0)
Index Cond: (a3 = 2)
-> Bitmap Index Scan on tmp_facts8_a2_idx (cost=0.00..18505.16 rows=2799187 width=0)
Index Cond: (a2 = 2)
(10 rows)

select count(*) from tmp_facts8 where a1 in (select 2) and a2 in (select 2)
and a3 in (select 2) and a4 in (select 2);
80
7419 ms

explain select * from tmp_facts8 where a1 in (select 2) and a2 in (select 2)
and a3 in (select 2) and a4 in (select 2);
QUERY PLAN
------------------------------------------------------------------------------------------------------------------
Hash IN Join (cost=100017884.57..100681784.99 rows=69 width=16)
Hash Cond: ("outer".a1 = "inner"."?column?")
-> Hash IN Join (cost=100017884.55..100681772.57 rows=2341 width=16)
Hash Cond: ("outer".a2 = "inner"."?column?")
-> Hash IN Join (cost=100017884.52..100681351.09 rows=79609 width=16)
Hash Cond: ("outer".a4 = "inner"."?column?")
-> Nested Loop (cost=100017884.50..100667021.44 rows=2706708 width=16)
-> HashAggregate (cost=0.02..0.03 rows=1 width=4)
-> Result (cost=0.00..0.01 rows=1 width=0)
-> Bitmap Heap Scan on tmp_facts8 (cost=17884.48..633187.56 rows=2706708 width=16)
Recheck Cond: (tmp_facts8.a3 = "outer"."?column?")
-> Bitmap Index Scan on tmp_facts8_a3_idx (cost=0.00..17884.48 rows=2706708 width=0)
Index Cond: (tmp_facts8.a3 = "outer"."?column?")
-> Hash (cost=0.02..0.02 rows=1 width=4)
-> Result (cost=0.00..0.01 rows=1 width=0)
-> Hash (cost=0.02..0.02 rows=1 width=4)
-> Result (cost=0.00..0.01 rows=1 width=0)
-> Hash (cost=0.02..0.02 rows=1 width=4)
-> Result (cost=0.00..0.01 rows=1 width=0)
(19 rows)



Обсуждение:

Композитный индекс для таблицы 100 М записей протестировать не удалось - создать индекс по заполненной таблицы постгрес не смог (говорит, памяти не хватает), а заполнение индексированной таблицы производится очень медленно, притом скорость заполнения падает; 10 М записей были вставлены за время порядка часа, а вставки следущего набора из 1 М мне уже не удалось дождаться.

Заметно, что планировщик с подзапросами работает плохо, в разы замедляя даже простейший запрос. На мелких базах это не так существенно, но на больших создает определенные проблемы. Следовательно, нужно избегать подзапросов, когда это возможно. При этом и JOIN-ов следует избегать, т.к. с ними возникают точно такие же проблемы. Ну, кому-то достаточно и выборок из одной таблицы, что чаще всего и делают на больших БД - для OLTP и этого бывает достаточно. Только сомнительна необходимость в PostgreSQL для подобных задач, когда есть SQLite, BerkeleyDB (чтобы делать выборку из одной таблицы поддержка SQL не сильно и нужна) и другие намного более эффективные решения.

Грубая прикидка показывает, что деградация производительности при росте размера базы примерно пропорциональна корню квадратному из отношения размеров баз до тех пор, пока база помещается в ОЗУ. После этого деградация становится линейно зависящей от роста размера базы. Как очевидное следствие, работа с базами, не помещающимися в shared_memory, проблематична.

понедельник, 7 сентября 2009 г.

Кэширование вывода в AOL Server

Для кэширования статичного контента в AOL Server можно использовать такую технику:

rename ::html::menu ::html::menu_orig
proc ::html::menu {current} {
with-adp-cache mainmenu,$current [list ::html::menu_orig $current]
}


Здесь мы оборачиваем функцию ::html::menu в кэширующий блок, переименовывая оригинальную функцию.

Сама реализация кэширующей функции может быть такой:

proc with-adp-cache {key script} { 
if {[info procs ns_adp_puts] ne {}} {
uplevel 1 $script
return
}
if {[nsv_exists ns_adp_cache $key] == 1} {
ns_adp_puts [nsv_get ns_adp_cache $key]
return
}
set result [with-adp-return $script]
if {[nsv_exists ns_adp_cache $key] == 0} {
nsv_set ns_adp_cache $key $result
}
ns_adp_puts $result
}

proc with-adp-return {script} {
if {[info commands ns_adp_puts_orig] eq {}} {
rename ns_adp_puts ns_adp_puts_orig
rename _ns_adp_puts ns_adp_puts
}
uplevel 1 $script
if {[info procs ns_adp_puts] ne {}} {
rename ns_adp_puts _ns_adp_puts
rename ns_adp_puts_orig ns_adp_puts
}
set _ns_adp_buffer $::_ns_adp_buffer
unset ::_ns_adp_buffer
return $_ns_adp_buffer
}

proc _ns_adp_puts {args} {
global _ns_adp_buffer
if {[llength $args] == 1} {
append _ns_adp_buffer [lindex $args 0]\n
} elseif {[llength $args] == 2 && [lindex $args 0] eq {-nonewline}} {
append _ns_adp_buffer [lindex $args 1]
} else {
return -code error "Unknown params to ns_adp_puts hook function: [info level 0]"
}
}


Собственно, я использую несколько иную реализацию (у меня ns_adp_puts/ns_adp_append обернуты в более высокоуровневую функцию, которая и реализует кэширование вывода при необходимости), но идея та же - использование переменной-буфера. В AOL Server можно обратиться к встроенному буферу, но насколько такой вариант будет эффективнее, оценить не берусь. Плюс к тому придется делать отсылку содержимого буфера при старте кэширующей функции, что так же далеко не всегда желательно. Интересно, предложит ли кто более другой вариант?

Обсуждение здесь:
cache function for adp pages output

Upd.

В настоящее время использую следующую реализацию:


############################################
# Copyright 2009, Mobile Business Group
############################################

namespace eval ::ns_html:: {}

# функция кэширует и отсылает клиенту результат выполнения кода script
# при повторном вызове блока кода с таким же key функция вернет результат из кэша
# как пример, см. ::html::menu - результат выполнения этой функции зависит только от
# текущего выбранного пункта меню, количество которых ограничено несколькими десятками
proc ::ns_html::cache {key script} {
global _ns_html_buffer
# кэш уже существует, возвращаем его и отменяем выполнение скрипта
# также проверяем на вложенный вызов кэша - должен игнорироваться
if {[info exists _ns_html_buffer] == 0 && [nsv_exists ns_html_cache $key] == 1} {
ns_log Debug "get_CACHED $key"
ns_html::puts [nsv_get ns_html_cache $key]
return
}
# активировать кэширование, если оно еще не было активировано, иначе просто выполнить тело скрипта
if {[info exists _ns_html_buffer] == 0} {
ns_log Debug "set_CACHE $key"
# при существующем буфере ns_html::puts будет сохранять контент в буфер вместо отправки клиенту
set _ns_html_buffer {}
if {[catch {uplevel 1 $script} errmgs]} {
return -code error $errmsg
unset _ns_html_buffer
}
# все результаты выведены в буффер
nsv_set ns_html_cache $key $_ns_html_buffer
# после удаления буфера ns_html::puts отправит контент клиенту
unset _ns_html_buffer
ns_html::puts [nsv_get ns_html_cache $key]
} else {
ns_log Debug "ignore_CACHE $key"
uplevel 1 $script
}
}


Пример:

ns_html cache testpage {
ns_html html ! {
ns_html head ! {
ns_html title - Test
}
ns_html body ! {
ns_html pre ! {
ns_html puts {EN:Page content.} \n {RU:Содержимое страницы} \n
}
}
}
}

(C) Alexey Pechnikov aka MBG, mobigroup.ru