Showing posts with label postgresql. Show all posts
Showing posts with label postgresql. Show all posts

2005-12-11

Preferring natural to surrogate key

I was reading an article at The Daily WTF today. The OP (original posts) sparked a debate on the use of surrogate vs. natural key.


It is really sad to see Jeff S. et. al fighting the horde of ignorants, but that is a battle that has been fought many times before and is not what I want to write about here.

What I want to show here is the difference in query time you'd expect to see by trimming down on unnecessary usage of surrogate keys.

A schema with unnecessary surrogate keys.
 
-- Done on postgresql 8.1

dms3_test=> \d document
                                         Table "dms4.document"
    Column     |           Type           |                          Modifiers                          
---------------+--------------------------+-------------------------------------------------------------
 id            | integer                  | not null default nextval('document_id_seq'::regclass)
 state         | text                     | not null
 modified_who  | text                     | not null
 modified_when | timestamp with time zone | not null default ('now'::text)::timestamp(6) with time zone
 created_who   | text                     | not null
 created_when  | timestamp with time zone | not null default ('now'::text)::timestamp(6) with time zone
Indexes:
    "document_pkey" PRIMARY KEY, btree (id)
    "document_created_when" btree (created_when)
    "document_created_who" btree (created_who)
    "document_modified_when" btree (modified_when)
    "document_modified_who" btree (modified_who)
    "document_state" btree (state)
Foreign-key constraints:
    "document_created_who_fkey" FOREIGN KEY (created_who) REFERENCES who(name)
    "document_modified_who_fkey" FOREIGN KEY (modified_who) REFERENCES who(name)
    "document_state_fkey" FOREIGN KEY (state) REFERENCES state(name)

dms3_test=> \d attribute_name
                            Table "public.attribute_name"
 Column |  Type   |                            Modifiers                             
--------+---------+------------------------------------------------------------------
 id     | integer | not null default nextval(('attribute_name_seq'::text)::regclass)
 name   | text    | not null
Indexes:
    "attribute_name_pkey" PRIMARY KEY, btree (id)
    "an_name_idx" UNIQUE, btree (name)

dms3_test=> \d attribute
                          Table "public.attribute"
 Column  |  Type   |                       Modifiers                        
---------+---------+--------------------------------------------------------
 id      | integer | not null default nextval('attribute_id_seq'::regclass)
 name_id | integer | not null
 value   | text    | not null
Indexes:
    "attribute_pkey" PRIMARY KEY, btree (id)
    "attr_nv_idx" UNIQUE, btree (name_id, value)
Foreign-key constraints:
    "$1" FOREIGN KEY (name_id) REFERENCES attribute_name(id)


dms3_test=> \d document_attribute
 Table "public.document_attribute"
    Column    |  Type   | Modifiers 
--------------+---------+-----------
 doc_id       | integer | not null
 attribute_id | integer | not null
Indexes:
    "document_attribute_pkey" PRIMARY KEY, btree (doc_id, attribute_id) CLUSTER
    "da_ad_idx" UNIQUE, btree (attribute_id, doc_id)
    "da_attr_idx" btree (attribute_id)
Foreign-key constraints:
    "$1" FOREIGN KEY (doc_id) REFERENCES public.document(id)
    "$2" FOREIGN KEY (attribute_id) REFERENCES attribute(id)


dms3_test=> 

explain analyze SELECT doc.id FROM attribute as attr0, attribute_name
as an0, attribute_name as an2, document_attribute as da2, document as
doc, attribute_name as an1, attribute as attr3, document_attribute as
da1, attribute as attr2, document_attribute as da0, attribute_name as
an3, attribute as attr1, document_attribute as da3

WHERE 
da0.doc_id = doc.id AND attr0.id = da0.attribute_id AND an0.id = attr0.name_id AND 
da1.doc_id = doc.id AND attr1.id = da1.attribute_id AND an1.id = attr1.name_id AND 
da2.doc_id = doc.id AND attr2.id = da2.attribute_id AND an2.id = attr2.name_id AND 
da3.doc_id = doc.id AND attr3.id = da3.attribute_id AND an3.id = attr3.name_id AND 
an0.name = 'ssis_client' AND attr0.value = 'client1' AND
an1.name = 'ssis_group' AND attr1.value = 'group1' AND
an2.name = 'ssis_type' AND attr2.value = 'type1' AND
an3.name = 'ssis_subtype' AND attr3.value = 'subtype1'
;


                                                                                                                         QUERY PLAN                                                                                                                          
-------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------
 Nested Loop  (cost=655695.94..886471.16 rows=1 width=4) (actual time=188571.542..217327.467 rows=3 loops=1)
   Join Filter: ("outer".id = "inner".name_id)
   ->  Seq Scan on attribute_name an0  (cost=0.00..1.07 rows=1 width=4) (actual time=0.045..0.048 rows=1 loops=1)
         Filter: (name = 'ssis_client'::text)
   ->  Nested Loop  (cost=655695.94..886470.07 rows=1 width=8) (actual time=188571.488..217327.404 rows=3 loops=1)
         Join Filter: ("outer".id = "inner".name_id)
         ->  Seq Scan on attribute_name an5  (cost=0.00..1.07 rows=1 width=4) (actual time=0.008..0.015 rows=1 loops=1)
               Filter: (name = 'ssis_e2xkey'::text)
         ->  Nested Loop  (cost=655695.94..886468.99 rows=1 width=12) (actual time=188571.475..217327.378 rows=3 loops=1)
               Join Filter: ("outer".id = "inner".name_id)
               ->  Seq Scan on attribute_name an4  (cost=0.00..1.07 rows=1 width=4) (actual time=0.007..0.009 rows=1 loops=1)
                     Filter: (name = 'ssis_comment'::text)
               ->  Nested Loop  (cost=655695.94..886467.90 rows=1 width=16) (actual time=188571.453..217327.346 rows=3 loops=1)
                     ->  Hash Join  (cost=655695.94..886463.56 rows=1 width=40) (actual time=183814.259..217326.874 rows=11 loops=1)
                           Hash Cond: ("outer".name_id = "inner".id)
                           ->  Hash Join  (cost=655694.86..886462.45 rows=4 width=44) (actual time=183814.220..217326.774 rows=11 loops=1)
                                 Hash Cond: (("outer".id = "inner".name_id) AND ("outer".attribute_id = "inner".id))
                                 ->  Hash Join  (cost=655692.89..886452.06 rows=838 width=52) (actual time=183795.378..217307.410 rows=951 loops=1)
                                       Hash Cond: ("outer".attribute_id = "inner".id)
                                       ->  Nested Loop  (cost=655690.92..886280.53 rows=32236 width=52) (actual time=183664.609..217269.300 rows=97785 loops=1)
                                             ->  Hash Join  (cost=655688.96..885633.84 rows=16118 width=44) (actual time=183640.064..217012.129 rows=97785 loops=1)
                                                   Hash Cond: ("outer".doc_id = "inner".id)
                                                   ->  Nested Loop  (cost=0.00..191997.58 rows=7557225 width=12) (actual time=12.250..10810.601 rows=7557225 loops=1)
                                                         ->  Index Scan using attribute_name_pkey on attribute_name an3  (cost=0.00..3.08 rows=1 width=4) (actual time=12.218..12.232 rows=1 loops=1)
                                                               Filter: (name = 'ssis_subtype'::text)
                                                         ->  Seq Scan on document_attribute da1  (cost=0.00..116422.25 rows=7557225 width=8) (actual time=0.021..4547.481 rows=7557225 loops=1)
                                                   ->  Hash  (cost=655683.57..655683.57 rows=2155 width=32) (actual time=183565.310..183565.310 rows=0 loops=1)
                                                         ->  Nested Loop  (cost=462162.26..655683.57 rows=2155 width=32) (actual time=128403.334..183556.998 rows=9257 loops=1)
                                                               ->  Hash Join  (cost=462162.26..650853.43 rows=288 width=24) (actual time=128403.319..183498.454 rows=906 loops=1)
                                                                     Hash Cond: ("outer".attribute_id = "inner".id)
                                                                     ->  Hash Join  (cost=462160.29..650793.18 rows=11080 width=24) (actual time=128337.287..183447.336 rows=90804 loops=1)
                                                                           Hash Cond: ("outer".name_id = "inner".id)
                                                                           ->  Nested Loop  (cost=462159.22..650348.93 rows=66476 width=28) (actual time=128337.257..183307.650 rows=90804 loops=1)
                                                                                 ->  Hash Join  (cost=462159.22..501285.43 rows=8888 width=20) (actual time=128306.517..132366.000 rows=8840 loops=1)
                                                                                       Hash Cond: ("outer".id = "inner".doc_id)
                                                                                       ->  Hash Join  (cost=1.06..25599.40 rows=202087 width=4) (actual time=41.568..2754.244 rows=329853 loops=1)
                                                                                             Hash Cond: ("outer".state_id = "inner".id)
                                                                                             ->  Seq Scan on document doc  (cost=0.00..18525.31 rows=1010431 width=8) (actual time=18.767..2089.253 rows=1010431 loops=1)
                                                                                             ->  Hash  (cost=1.06..1.06 rows=1 width=4) (actual time=14.681..14.681 rows=0 loops=1)
                                                                                                   ->  Seq Scan on state  (cost=0.00..1.06 rows=1 width=4) (actual time=0.031..0.035 rows=1 loops=1)
                                                                                                         Filter: (name = 'associated'::text)
                                                                                       ->  Hash  (cost=461808.06..461808.06 rows=44437 width=16) (actual time=128239.687..128239.687 rows=0 loops=1)
                                                                                             ->  Hash Join  (cost=157528.96..461808.06 rows=44437 width=16) (actual time=15479.239..128139.028 rows=27087 loops=1)
                                                                                                   Hash Cond: ("outer".attribute_id = "inner".id)
                                                                                                   ->  Hash Join  (cost=157526.99..452807.67 rows=1710811 width=16) (actual time=15478.512..127203.588 rows=2313438 loops=1)
                                                                                                         Hash Cond: ("outer".doc_id = "inner".doc_id)
                                                                                                         ->  Seq Scan on document_attribute da2  (cost=0.00..116422.25 rows=7557225 width=8) (actual time=0.019..37889.434 rows=7557225 loops=1)
                                                                                                         ->  Hash  (cost=156173.26..156173.26 rows=196292 width=8) (actual time=14908.286..14908.286 rows=0 loops=1)
                                                                                                               ->  Hash Join  (cost=1.97..156173.26 rows=196292 width=8) (actual time=7.750..14650.188 rows=269366 loops=1)
                                                                                                                     Hash Cond: ("outer".attribute_id = "inner".id)
                                                                                                                     ->  Seq Scan on document_attribute da4  (cost=0.00..116422.25 rows=7557225 width=8) (actual time=7.678..11635.892 rows=7557225 loops=1)
                                                                                                                     ->  Hash  (cost=1.96..1.96 rows=2 width=8) (actual time=0.049..0.049 rows=0 loops=1)
                                                                                                                           ->  Seq Scan on attribute attr4  (cost=0.00..1.96 rows=2 width=8) (actual time=0.008..0.047 rows=1 loops=1)
                                                                                                                                 Filter: (value = 'comment1'::text)
                                                                                                   ->  Hash  (cost=1.96..1.96 rows=2 width=8) (actual time=0.046..0.046 rows=0 loops=1)
                                                                                                         ->  Seq Scan on attribute attr2  (cost=0.00..1.96 rows=2 width=8) (actual time=0.007..0.044 rows=1 loops=1)
                                                                                                               Filter: (value = 'type1'::text)
                                                                                 ->  Index Scan using document_attribute_pkey on document_attribute da0  (cost=0.00..16.67 rows=8 width=8) (actual time=5.713..5.748 rows=10 loops=8840)
                                                                                       Index Cond: ("outer".doc_id = da0.doc_id)
                                                                           ->  Hash  (cost=1.07..1.07 rows=1 width=4) (actual time=0.011..0.011 rows=0 loops=1)
                                                                                 ->  Seq Scan on attribute_name an2  (cost=0.00..1.07 rows=1 width=4) (actual time=0.007..0.010 rows=1 loops=1)
                                                                                       Filter: (name = 'ssis_type'::text)
                                                                     ->  Hash  (cost=1.96..1.96 rows=2 width=8) (actual time=0.052..0.052 rows=0 loops=1)
                                                                           ->  Seq Scan on attribute attr0  (cost=0.00..1.96 rows=2 width=8) (actual time=0.014..0.050 rows=1 loops=1)
                                                                                 Filter: (value = 'client1'::text)
                                                               ->  Index Scan using document_attribute_pkey on document_attribute da3  (cost=0.00..16.67 rows=8 width=8) (actual time=0.005..0.049 rows=10 loops=906)
                                                                     Index Cond: (da3.doc_id = "outer".doc_id)
                                             ->  Materialize  (cost=1.96..1.98 rows=2 width=8) (actual time=0.000..0.001 rows=1 loops=97785)
                                                   ->  Seq Scan on attribute attr5  (cost=0.00..1.96 rows=2 width=8) (actual time=18.498..18.537 rows=1 loops=1)
                                                         Filter: (value = 'e2xkey1'::text)
                                       ->  Hash  (cost=1.96..1.96 rows=2 width=8) (actual time=0.045..0.045 rows=0 loops=1)
                                             ->  Seq Scan on attribute attr1  (cost=0.00..1.96 rows=2 width=8) (actual time=0.007..0.044 rows=1 loops=1)
                                                   Filter: (value = 'group1'::text)
                                 ->  Hash  (cost=1.96..1.96 rows=2 width=8) (actual time=18.781..18.781 rows=0 loops=1)
                                       ->  Seq Scan on attribute attr3  (cost=0.00..1.96 rows=2 width=8) (actual time=18.739..18.779 rows=1 loops=1)
                                             Filter: (value = 'subtype1'::text)
                           ->  Hash  (cost=1.07..1.07 rows=1 width=4) (actual time=0.018..0.018 rows=0 loops=1)
                                 ->  Seq Scan on attribute_name an1  (cost=0.00..1.07 rows=1 width=4) (actual time=0.007..0.009 rows=1 loops=1)
                                       Filter: (name = 'ssis_group'::text)
                     ->  Index Scan using document_attribute_pkey on document_attribute da5  (cost=0.00..4.33 rows=1 width=8) (actual time=0.037..0.037 rows=0 loops=11)
                           Index Cond: ((da5.doc_id = "outer".doc_id) AND ("outer".id = da5.attribute_id))
 Total runtime: 217405.692 ms
(82 rows)

Time: 217885.006 ms
The same data but in a schema without trimmed-down surrogate keys.
-- Done on postgresql 8.1

dms3_test=> \d document
                                         Table "dms4.document"
    Column     |           Type           |                          Modifiers                          
---------------+--------------------------+-------------------------------------------------------------
 id            | integer                  | not null default nextval('document_id_seq'::regclass)
 state         | text                     | not null
 modified_who  | text                     | not null
 modified_when | timestamp with time zone | not null default ('now'::text)::timestamp(6) with time zone
 created_who   | text                     | not null
 created_when  | timestamp with time zone | not null default ('now'::text)::timestamp(6) with time zone
Indexes:
    "document_pkey" PRIMARY KEY, btree (id)
    "document_created_when" btree (created_when)
    "document_created_who" btree (created_who)
    "document_modified_when" btree (modified_when)
    "document_modified_who" btree (modified_who)
    "document_state" btree (state)
Foreign-key constraints:
    "document_created_who_fkey" FOREIGN KEY (created_who) REFERENCES who(name)
    "document_modified_who_fkey" FOREIGN KEY (modified_who) REFERENCES who(name)
    "document_state_fkey" FOREIGN KEY (state) REFERENCES state(name)

dms3_test=> \d temp20051206.da
   Table "temp20051206.da"
 Column |  Type   | Modifiers 
--------+---------+-----------
 doc_id | integer | not null
 an     | text    | not null
 av     | text    | not null
Indexes:
    "da_pkey" PRIMARY KEY, btree (doc_id, an, av)
    "da_an_av_idx" UNIQUE, btree (an, av, doc_id)
Foreign-key constraints:
    "da_an_fkey" FOREIGN KEY (an, av) REFERENCES attr(name, value) DEFERRABLE INITIALLY DEFERRED
    "da_doc_id_fkey" FOREIGN KEY (doc_id) REFERENCES public.document(id) DEFERRABLE INITIALLY DEFERRED

dms3_test=> 

explain analyze select doc.id from document as doc, da
da_client, da da_group, da da_type, da da_subtype 

WHERE
doc.id=da_client.doc_id and doc.id=da_group.doc_id and
doc.id=da_type.doc_id and doc.id=da_subtype.doc_id and
da_client.an='ssis_client' and da_client.av='client1' and 
da_group.an='ssis_group' and da_group.av='group1' and
da_type.an='ssis_type' and da_type.av='type1' and 
da_subtype.an='ssis_subtype' and da_subtype.av='subtype1'
;

                                                                             QUERY PLAN                                                                             
--------------------------------------------------------------------------------------------------------------------------------------------------------------------
 Nested Loop  (cost=40335.69..53871.76 rows=1 width=4) (actual time=17319.458..50292.429 rows=140 loops=1)
   ->  Nested Loop  (cost=40335.69..53864.64 rows=2 width=16) (actual time=17319.392..50260.780 rows=1072 loops=1)
         ->  Nested Loop  (cost=40335.69..53330.49 rows=150 width=12) (actual time=17289.476..35508.467 rows=10153 loops=1)
               ->  Merge Join  (cost=40335.69..40494.44 rows=3558 width=8) (actual time=17263.290..17594.400 rows=10153 loops=1)
                     Merge Cond: ("outer".doc_id = "inner".doc_id)
                     ->  Sort  (cost=20817.14..20849.19 rows=12818 width=4) (actual time=10145.947..10314.729 rows=101159 loops=1)
                           Sort Key: da_client.doc_id
                           ->  Bitmap Heap Scan on da da_client  (cost=155.91..19942.58 rows=12818 width=4) (actual time=1165.917..9800.025 rows=101159 loops=1)
                                 Recheck Cond: ((an = 'ssis_client'::text) AND (av = 'client1'::text))
                                 ->  Bitmap Index Scan on da_an_av_idx  (cost=0.00..155.91 rows=12818 width=0) (actual time=1156.362..1156.362 rows=101159 loops=1)
                                       Index Cond: ((an = 'ssis_client'::text) AND (av = 'client1'::text))
                     ->  Sort  (cost=19518.54..19548.09 rows=11817 width=4) (actual time=7117.330..7188.340 rows=101190 loops=1)
                           Sort Key: da_subtype.doc_id
                           ->  Bitmap Heap Scan on da da_subtype  (cost=143.90..18719.21 rows=11817 width=4) (actual time=913.707..6798.627 rows=101190 loops=1)
                                 Recheck Cond: ((an = 'ssis_subtype'::text) AND (av = 'subtype1'::text))
                                 ->  Bitmap Index Scan on da_an_av_idx  (cost=0.00..143.90 rows=11817 width=0) (actual time=904.720..904.720 rows=101190 loops=1)
                                       Index Cond: ((an = 'ssis_subtype'::text) AND (av = 'subtype1'::text))
               ->  Index Scan using document_pkey on document doc  (cost=0.00..3.60 rows=1 width=4) (actual time=1.762..1.763 rows=1 loops=10153)
                     Index Cond: (doc.id = "outer".doc_id)
         ->  Index Scan using da_pkey on da da_type  (cost=0.00..3.55 rows=1 width=4) (actual time=1.451..1.452 rows=0 loops=10153)
               Index Cond: (("outer".id = da_type.doc_id) AND (da_type.an = 'ssis_type'::text) AND (da_type.av = 'type1'::text))
   ->  Index Scan using da_pkey on da da_group  (cost=0.00..3.55 rows=1 width=4) (actual time=0.028..0.028 rows=0 loops=1072)
         Index Cond: (("outer".id = da_group.doc_id) AND (da_group.an = 'ssis_group'::text) AND (da_group.av = 'group1'::text))
 Total runtime: 50296.288 ms
(24 rows)

Time: 50301.853 ms
 
 
(originally from http://microjet.ath.cx/WebWiki/2005.12.11_PreferringNaturalToSurrogateKey.html)

Table partitioning

Postgresql could benefit from an implementation of table partitioning. Also see: http://groups.google.com/group/pgsql.general/tree/browse_frm/thread/e72ead84aa16bc8e/64d61f78425b119b?rnum=1&q=partition&_done=%2Fgroup%2Fpgsql.general%2Fbrowse_frm%2Fthread%2Fe72ead84aa16bc8e%2F121bab4de037ce6a%3Fq%3Dpartition%26rnum%3D7%26#doc_64d61f78425b119b

All in one table

dms3_test=> select count(doc.id) from document as doc, da da_client, da
da_group, da da_type, da da_subtype where doc.id=da_client.doc_id and
doc.id=da_group.doc_id and doc.id=da_type.doc_id and
doc.id=da_subtype.doc_id and da_client.an='ssis_client' and
da_group.an='ssis_group' and da_type.an='ssis_type' and
da_subtype.an='ssis_subtype' and da_client.av='client1' and
da_group.av='group1' and da_type.av='type1' and da_subtype.av='subtype1';

 count 
-------
   140
(1 row)

Time: 60882.964 ms


Separated out
 
 
dms3_test=> select count(doc.id) from document as doc, ssis_client as sc,
ssis_group as sg, ssis_type as st, ssis_subtype as sst where
doc.id=sc.doc_id and doc.id=sg.doc_id and doc.id=st.doc_id and
doc.id=sst.doc_id and sc.value='client1' and sg.value='group1' and
st.value='type1' and sst.value='subtype1';

 count 
-------
   140
(1 row)

Time: 3912.358 ms

Explain analyze of all in one table
 
 
dms3_test=> explain analyze select doc.id from document as doc, da
da_client, da da_group, da da_type, da da_subtype where
doc.id=da_client.doc_id and doc.id=da_group.doc_id and
doc.id=da_type.doc_id and doc.id=da_subtype.doc_id and
da_client.an='ssis_client' and da_group.an='ssis_group' and
da_type.an='ssis_type' and da_subtype.an='ssis_subtype' and
da_client.av='client1' and da_group.av='group1' and da_type.av='type1' and
da_subtype.av='subtype1'

                                                                             QUERY PLAN                                                                             
--------------------------------------------------------------------------------------------------------------------------------------------------------------------
 Nested Loop  (cost=40335.69..53871.76 rows=1 width=4) (actual time=17319.458..50292.429 rows=140 loops=1)
   ->  Nested Loop  (cost=40335.69..53864.64 rows=2 width=16) (actual time=17319.392..50260.780 rows=1072 loops=1)
         ->  Nested Loop  (cost=40335.69..53330.49 rows=150 width=12) (actual time=17289.476..35508.467 rows=10153 loops=1)
               ->  Merge Join  (cost=40335.69..40494.44 rows=3558 width=8) (actual time=17263.290..17594.400 rows=10153 loops=1)
                     Merge Cond: ("outer".doc_id = "inner".doc_id)
                     ->  Sort  (cost=20817.14..20849.19 rows=12818 width=4) (actual time=10145.947..10314.729 rows=101159 loops=1)
                           Sort Key: da_client.doc_id
                           ->  Bitmap Heap Scan on da da_client  (cost=155.91..19942.58 rows=12818 width=4) (actual time=1165.917..9800.025 rows=101159 loops=1)
                                 Recheck Cond: ((an = 'ssis_client'::text) AND (av = 'client1'::text))
                                 ->  Bitmap Index Scan on da_an_av_idx  (cost=0.00..155.91 rows=12818 width=0) (actual time=1156.362..1156.362 rows=101159 loops=1)
                                       Index Cond: ((an = 'ssis_client'::text) AND (av = 'client1'::text))
                     ->  Sort  (cost=19518.54..19548.09 rows=11817 width=4) (actual time=7117.330..7188.340 rows=101190 loops=1)
                           Sort Key: da_subtype.doc_id
                           ->  Bitmap Heap Scan on da da_subtype  (cost=143.90..18719.21 rows=11817 width=4) (actual time=913.707..6798.627 rows=101190 loops=1)
                                 Recheck Cond: ((an = 'ssis_subtype'::text) AND (av = 'subtype1'::text))
                                 ->  Bitmap Index Scan on da_an_av_idx  (cost=0.00..143.90 rows=11817 width=0) (actual time=904.720..904.720 rows=101190 loops=1)
                                       Index Cond: ((an = 'ssis_subtype'::text) AND (av = 'subtype1'::text))
               ->  Index Scan using document_pkey on document doc  (cost=0.00..3.60 rows=1 width=4) (actual time=1.762..1.763 rows=1 loops=10153)
                     Index Cond: (doc.id = "outer".doc_id)
         ->  Index Scan using da_pkey on da da_type  (cost=0.00..3.55 rows=1 width=4) (actual time=1.451..1.452 rows=0 loops=10153)
               Index Cond: (("outer".id = da_type.doc_id) AND (da_type.an = 'ssis_type'::text) AND (da_type.av = 'type1'::text))
   ->  Index Scan using da_pkey on da da_group  (cost=0.00..3.55 rows=1 width=4) (actual time=0.028..0.028 rows=0 loops=1072)
         Index Cond: (("outer".id = da_group.doc_id) AND (da_group.an = 'ssis_group'::text) AND (da_group.av = 'group1'::text))
 Total runtime: 50296.288 ms
(24 rows)

Time: 50301.853 ms

Explain analyze of separated out
 
 
dms3_test=> explain analyze select doc.id from document as doc, ssis_client
as sc, ssis_group as sg, ssis_type as st, ssis_subtype as sst where
doc.id=sc.doc_id and doc.id=sg.doc_id and doc.id=st.doc_id and
doc.id=sst.doc_id and sc.value='client1' and sg.value='group1' and
st.value='type1' and sst.value='subtype1';

                                                                           QUERY PLAN                                                                           
----------------------------------------------------------------------------------------------------------------------------------------------------------------
 Nested Loop  (cost=48763.53..76529.21 rows=108 width=4) (actual time=3947.647..5401.517 rows=140 loops=1)
   ->  Nested Loop  (cost=48763.53..76139.59 rows=108 width=16) (actual time=3947.592..5377.496 rows=140 loops=1)
         ->  Hash Join  (cost=48763.53..71836.53 rows=1019 width=12) (actual time=3947.454..5027.993 rows=993 loops=1)
               Hash Cond: ("outer".doc_id = "inner".doc_id)
               ->  Seq Scan on ssis_group sg  (cost=0.00..22537.39 rows=105085 width=4) (actual time=169.102..1161.228 rows=100924 loops=1)
                     Filter: (value = 'group1'::text)
               ->  Hash  (cost=48739.02..48739.02 rows=9802 width=8) (actual time=3777.630..3777.630 rows=10153 loops=1)
                     ->  Hash Join  (cost=23168.26..48739.02 rows=9802 width=8) (actual time=2108.108..3770.001 rows=10153 loops=1)
                           Hash Cond: ("outer".doc_id = "inner".doc_id)
                           ->  Seq Scan on ssis_client sc  (cost=0.00..22537.39 rows=100706 width=4) (actual time=201.259..1662.239 rows=101159 loops=1)
                                 Filter: (value = 'client1'::text)
                           ->  Hash  (cost=22537.39..22537.39 rows=98349 width=4) (actual time=1904.210..1904.210 rows=101190 loops=1)
                                 ->  Seq Scan on ssis_subtype sst  (cost=0.00..22537.39 rows=98349 width=4) (actual time=234.704..1828.887 rows=101190 loops=1)
                                       Filter: (value = 'subtype1'::text)
         ->  Index Scan using ssis_type_pkey on ssis_type st  (cost=0.00..4.21 rows=1 width=4) (actual time=0.351..0.351 rows=0 loops=993)
               Index Cond: ("outer".doc_id = st.doc_id)
               Filter: (value = 'type1'::text)
   ->  Index Scan using document_pkey on document doc  (cost=0.00..3.60 rows=1 width=4) (actual time=0.169..0.169 rows=1 loops=140)
         Index Cond: (doc.id = "outer".doc_id)
 Total runtime: 5401.958 ms
(20 rows)

Time: 5406.568 ms 
 
 
(originally from http://microjet.ath.cx/WebWiki/2005.12.11_TablePartitioning.html)

2005-11-12

2005.12.11_Index Clustering

Index clustering can improve your query time, if your query can take advantage of the ordering.
Following are the queries from 2005.12.11_TablePartitioning.html redone with index clustering.

The all in one table. A 10x improvement.

dms3_test=> \d da
   Table "temp20051206.da"
 Column |  Type   | Modifiers 
--------+---------+-----------
 doc_id | integer | not null
 an     | text    | not null
 av     | text    | not null
Indexes:
    "da_pkey" PRIMARY KEY, btree (doc_id, an, av)
    "da_an_av_idx" UNIQUE, btree (an, av, doc_id) CLUSTER
Foreign-key constraints:
    "da_an_fkey" FOREIGN KEY (an, av) REFERENCES attr(name, value) DEFERRABLE INITIALLY DEFERRED
    "da_doc_id_fkey" FOREIGN KEY (doc_id) REFERENCES public.document(id) DEFERRABLE INITIALLY DEFERRED



dms3_test=> explain analyze select doc.id from document as doc, da
da_client, da da_group, da da_type, da da_subtype where
doc.id=da_client.doc_id and doc.id=da_group.doc_id and
doc.id=da_type.doc_id and doc.id=da_subtype.doc_id and
da_client.an='ssis_client' and da_group.an='ssis_group' and
da_type.an='ssis_type' and da_subtype.an='ssis_subtype' and
da_client.av='client1' and da_group.av='group1' and da_type.av='type1'
and da_subtype.av='subtype1';
                                                                            QUERY PLAN                                                                            
------------------------------------------------------------------------------------------------------------------------------------------------------------------
 Nested Loop  (cost=40335.69..53871.76 rows=1 width=4) (actual time=1904.361..5277.128 rows=140 loops=1)
   ->  Nested Loop  (cost=40335.69..53864.64 rows=2 width=16) (actual time=1904.289..5221.572 rows=1072 loops=1)
         ->  Nested Loop  (cost=40335.69..53330.49 rows=150 width=12) (actual time=1904.216..3747.333 rows=10153 loops=1)
               ->  Merge Join  (cost=40335.69..40494.44 rows=3558 width=8) (actual time=1882.068..2082.534 rows=10153 loops=1)
                     Merge Cond: ("outer".doc_id = "inner".doc_id)
                     ->  Sort  (cost=20817.14..20849.19 rows=12818 width=4) (actual time=778.661..835.451 rows=101159 loops=1)
                           Sort Key: da_client.doc_id
                           ->  Bitmap Heap Scan on da da_client  (cost=155.91..19942.58 rows=12818 width=4) (actual time=432.318..521.484 rows=101159 loops=1)
                                 Recheck Cond: ((an = 'ssis_client'::text) AND (av = 'client1'::text))
                                 ->  Bitmap Index Scan on da_an_av_idx  (cost=0.00..155.91 rows=12818 width=0) (actual time=418.064..418.064 rows=101159 loops=1)
                                       Index Cond: ((an = 'ssis_client'::text) AND (av = 'client1'::text))
                     ->  Sort  (cost=19518.54..19548.09 rows=11817 width=4) (actual time=1103.395..1160.311 rows=101190 loops=1)
                           Sort Key: da_subtype.doc_id
                           ->  Bitmap Heap Scan on da da_subtype  (cost=143.90..18719.21 rows=11817 width=4) (actual time=633.951..751.246 rows=101190 loops=1)
                                 Recheck Cond: ((an = 'ssis_subtype'::text) AND (av = 'subtype1'::text))
                                 ->  Bitmap Index Scan on da_an_av_idx  (cost=0.00..143.90 rows=11817 width=0) (actual time=633.700..633.700 rows=101190 loops=1)
                                       Index Cond: ((an = 'ssis_subtype'::text) AND (av = 'subtype1'::text))
               ->  Index Scan using document_pkey on document doc  (cost=0.00..3.60 rows=1 width=4) (actual time=0.162..0.163 rows=1 loops=10153)
                     Index Cond: (doc.id = "outer".doc_id)
         ->  Index Scan using da_pkey on da da_type  (cost=0.00..3.55 rows=1 width=4) (actual time=0.144..0.144 rows=0 loops=10153)
               Index Cond: (("outer".id = da_type.doc_id) AND (da_type.an = 'ssis_type'::text) AND (da_type.av = 'type1'::text))
   ->  Index Scan using da_pkey on da da_group  (cost=0.00..3.55 rows=1 width=4) (actual time=0.050..0.050 rows=0 loops=1072)
         Index Cond: (("outer".id = da_group.doc_id) AND (da_group.an = 'ssis_group'::text) AND (da_group.av = 'group1'::text))
 Total runtime: 5280.891 ms
(24 rows)

Time: 5287.639 ms


The separated out data. About 2x improvement.
 
 
dms3_test=> \d ssis_client
                                        Table "attr.ssis_client"
    Column     |           Type           |                          Modifiers                          
---------------+--------------------------+-------------------------------------------------------------
 doc_id        | integer                  | not null
 created_when  | timestamp with time zone | not null default ('now'::text)::timestamp(6) with time zone
 created_who   | integer                  | not null
 modified_when | timestamp with time zone | not null default ('now'::text)::timestamp(6) with time zone
v modified_who  | integer                  | not null
 value         | text                     | not null
 value_id      | integer                  | not null
Indexes:
    "ssis_client_pkey" PRIMARY KEY, btree (doc_id)
    "ssis_client_value_id_idx" btree (value_id)
    "ssis_client_value_idx" btree (value) CLUSTER
Foreign-key constraints:
    "ssis_client_created_who_fkey" FOREIGN KEY (created_who) REFERENCES public.who(id)
    "ssis_client_doc_id_fkey" FOREIGN KEY (doc_id) REFERENCES public.document(id)
    "ssis_client_modified_who_fkey" FOREIGN KEY (modified_who) REFERENCES public.who(id)
    "ssis_client_value_id_fkey" FOREIGN KEY (value_id) REFERENCES ssis_client_value(id)

dms3_test=> explain analyze select doc.id from document as doc,
ssis_client as sc, ssis_group as sg, ssis_type as st, ssis_subtype as
sst where doc.id=sc.doc_id and doc.id=sg.doc_id and doc.id=st.doc_id
and doc.id=sst.doc_id and sc.value='client1' and sg.value='group1' and
st.value='type1' and sst.value='subtype1';

                                                                                            QUERY PLAN                                                                                            
--------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------
 Nested Loop  (cost=12322.80..16099.97 rows=108 width=4) (actual time=1941.188..2329.004 rows=140 loops=1)
   ->  Hash Join  (cost=12322.80..15710.34 rows=108 width=16) (actual time=1941.144..2306.762 rows=140 loops=1)
         Hash Cond: ("outer".doc_id = "inner".doc_id)
         ->  Index Scan using ssis_type_value_idx on ssis_type st  (cost=0.00..2850.93 rows=107106 width=4) (actual time=75.017..406.128 rows=100825 loops=1)
               Index Cond: (value = 'type1'::text)
         ->  Hash  (cost=12320.26..12320.26 rows=1019 width=12) (actual time=1862.846..1862.846 rows=993 loops=1)
               ->  Hash Join  (cost=8986.99..12320.26 rows=1019 width=12) (actual time=1531.920..1861.824 rows=993 loops=1)
                     Hash Cond: ("outer".doc_id = "inner".doc_id)
                     ->  Index Scan using ssis_group_value_idx on ssis_group sg  (cost=0.00..2797.65 rows=105085 width=4) (actual time=39.136..291.236 rows=100924 loops=1)
                           Index Cond: (value = 'group1'::text)
                     ->  Hash  (cost=8962.49..8962.49 rows=9802 width=8) (actual time=1481.859..1481.859 rows=10153 loops=1)
                           ->  Hash Join  (cost=3248.58..8962.49 rows=9802 width=8) (actual time=981.952..1474.601 rows=10153 loops=1)
                                 Hash Cond: ("outer".doc_id = "inner".doc_id)
                                 ->  Index Scan using ssis_client_value_idx on ssis_client sc  (cost=0.00..2680.53 rows=100706 width=4) (actual time=43.766..317.779 rows=101159 loops=1)
                                       Index Cond: (value = 'client1'::text)
                                 ->  Hash  (cost=2617.71..2617.71 rows=98349 width=4) (actual time=918.689..918.689 rows=101190 loops=1)
                                       ->  Index Scan using ssis_subtype_value_idx on ssis_subtype sst  (cost=0.00..2617.71 rows=98349 width=4) (actual time=53.700..820.030 rows=101190 loops=1)
                                             Index Cond: (value = 'subtype1'::text)
   ->  Index Scan using document_pkey on document doc  (cost=0.00..3.60 rows=1 width=4) (actual time=0.156..0.156 rows=1 loops=140)
         Index Cond: (doc.id = "outer".doc_id)
 Total runtime: 2329.395 ms
(21 rows)

Time: 2334.097 ms 
 
 
(originally from http://microjet.ath.cx/WebWiki/2005.12.11_IndexClustering.html)

2005-08-23

Result pagination with postgresql

A common problem with webapps is providing an interface to page through result set like what various search engines do.
I have yet to find a website that discuss this in depth. So, here is a summary of solutions I came up with by looking at various pieces in the Web for doing result pagination with Postgresql. I hope this would give the sorely needed encouragement for people to start sharing their findings.
The problem actually has three components:
  • displaying result for a certain page,
  • not causing undue latency in page display, and
  • counting number of results.
Counting the accurate number of results would almost always require the full result set to be counted. Applications would usually cache this number. How exactly is the counting done depends on the approach taken.
And there are two basic approaches:
  • operating on piecemeal result set
  • operating on full result set
Please realise that there is no 'best' approach. Each comes with its own pros and cons.
To illustrate the pros and cons, I am employing two kind of queries: cheap and expensive. I categorise queries according to the effort exacted from pgsql: cheap and expensive. This categorisation is only for simplicity purposes as there are, of course, grey areas, queries that are neither cheap nor expensive; not to mention that cheap and expensive are subjective terms anyway.
dms3_test=> create view cheap as select id from document;
CREATE VIEW
Time: 150.078 ms

dms3_test=> create view expensive as SELECT doc.id FROM
attribute as attr0, attribute_name as an0, document as doc, state,
document_attribute as da0 WHERE state.id = doc.state_id AND state.name
= 'new' AND da0.doc_id = doc.id AND attr0.id = da0.attribute_id AND
an0.id = attr0.name_id AND an0.name = 'ssis_client' AND attr0.value
ILIKE 'client1';
CREATE VIEW
Time: 120.979 ms
Since what is pro and what is con depend very much against the context, I simply list the characteristics of each approach without further labelling.

Operating on Piecemeal Result Set (New Query for Each Page)

In this approach, a new query is run for each page. Each query differs only in OFFSET and LIMIT clauses.
For example, for the first page, the query would be executed with OFFSET 0 and LIMIT 10. The second page would be OFFSET 11 LIMIT 10.
This approach is popular and is found in various web applications. It is simple to implement and has an acceptable performance on cheap queries.
Number of matching results could be counted with a SELECT COUNT(*) in the beginning. This number could be cached as well so as to reduce the load on the server.
The latency in page display is low in the beginning and degrades linearly as user moves deeper.
The problem with this approach is it does not reuse previous effort. This is especially problematic if the query is expensive.
Another problem is each query would potentially see different snapshot of the data. If user is browsing page n and the underlying data changes, refreshing or revisiting page n would show a different data.
cheap query
dms3_test=> abort; 
begin; 
select count(*) from cheap; 
select * from cheap order by id offset 0 limit 10; 
select * from cheap order by id offset 50000 limit 10;

ROLLBACK
Time: 1.640 ms
BEGIN
Time: 6.187 ms
  count  
---------
 1010431
(1 row)

Time: 1094.187 ms
 id 
----
  1
  2
  3
  4
  5
  6
  9
 10
 11
 12
(10 rows)

Time: 57.371 ms
  id   
-------
 50003
 50004
 50005
 50006
 50007
 50008
 50009
 50010
 50011
 50012
(10 rows)

Time: 134.610 ms
expensive query
dms3_test=> abort; 
begin; 
select count(*) from expensive; 
select * from expensive order by id offset 0 limit 10; 
select * from expensive order by id offset 50000 limit 10;

ROLLBACK
Time: 2.698 ms
BEGIN
Time: 4.584 ms
count 
-------
 68276
(1 row)

Time: 18034.510 ms
 id  
-----
   6
  50
  55
  65
  89
 109
 110
 133
 144
 155
(10 rows)

Time: 76.929 ms
   id   
--------
 749659
 749661
 749667
 749685
 749692
 749720
 749732
 749740
 749741
 749778
(10 rows)

Time: 14424.053 ms
Characteristics:
  • simple implementation
  • no setup cost
  • suitable for cheap queries
  • suitable if user is expected to browse through only few pages
  • not isolated from underlying changes
  • latency degrades linearly

Operating on Full Result Set

This approach takes off from the previous one by reusing previous effort. The database takes a hit only on new query criteria, instead of every time the user changes pages.
This approach could be implemented by using either a temporary table or a without hold cursor. Both implementations require the webapp to maintain and reuse the transaction in which the table or cursor is defined.
A common strategy is to maintain a fixed number of connections to the database and assign one connection to the processing of a query in a round-robin way, i.e. map a specific query criteria to a specific connection.
In each connection, a transaction is held open throughout the duration of the webapp. This transaction would hold various temporary tables or cursors. You would want to keep the transaction open as long as possible.
Warning: keeping a transaction open for a long time would have the
following negative side-effects:
  • prevents vacuum from removing all dead tuples.
  • blocks changes to schema
  • may block other transactions if data is modified within the transaction
Moreover, transactions may become invalid at any time due to some unforeseen event like Bob spilling his soda over the ethernet switch.
Therefore, your webapp should be able to re-connect and re-setup the temporary tables or cursors setup if the existing connection or transaction is no longer valid.
Being able to re-setup would also allow the DBA to vacuum thoroughly and/or make schema updates by simply killing and temporarily blocking connections from your webapp during low-traffic hours without having to restart your webapp. This is a big deal if the DBA person is not the sysadmin or have permission to restart your webapp.
Before processing each query, it is recommended to generate a SAVEPOINT so that any error in processing a query would not destroy the transaction.

Using Temporary Tables

The result set could be piped into a temporary table via the CREATE TEMPORARY TABLE foo AS command. It is important to remember to use a temporary table since it is not journalled into the WAL (write-ahead logging) which would have negative impact on performance.
The implementation gives you a free count of matching result when you do the CREATE TEMPORARY TABLE AS. I am not sure why psql does not show the count, but it is accessible from within a stored procedure or your DB driver.
cheap query
dms3_test=> abort;
begin;
create temporary table foo as select * from cheap order by id;
select * from foo order by id offset 0 limit 10; 
select * from foo order by id offset 50000 limit 10;

ROLLBACK
Time: 60.744 ms
BEGIN
Time: 0.686 ms
SELECT
Time: 15125.956 ms
 id 
----
  1
  2
  3
  4
  5
  6
  9
 10
 11
 12
(10 rows)

Time: 4397.762 ms
  id   
-------
 50003
 50004
 50005
 50006
 50007
 50008
 50009
 50010
 50011
 50012
(10 rows)

Time: 4413.789 ms
expensive query
dms3_test=> abort;
begin;
create temporary table foo as select * from expensive order by id;
select * from foo order by id offset 0 limit 10; 
select * from foo order by id offset 50000 limit 10;

ROLLBACK
Time: 52.777 ms
BEGIN
Time: 3.683 ms
SELECT
Time: 18666.615 ms
 id  
-----
   6
  50
  55
  65
  89
 109
 110
 133
 144
 155
(10 rows)

Time: 314.754 ms
   id   
--------
 749659
 749661
 749667
 749685
 749692
 749720
 749732
 749740
 749741
 749778
(10 rows)

Time: 342.207 ms
Characteristics:
  • complex implementation
  • high setup cost
  • free result count as a side-effect
  • suitable for expensive queries
  • suitable if user is expected to comprehensively browse the result set
  • isolated from underlying changes
  • latency still degrades linearly but more gently

Using Without Hold Cursors

Without hold cursors are destroyed at the end of transaction, similar to temporary tables. On the other hand, with hold cursors outlive the creating transaction, although they are still bounded within a session. I recommend using without hold cursors to simplify garbage management.
cheap query
dms3_test=> abort;
begin;
declare cheap_cursor scroll cursor for select * from cheap order by id;
move all from cheap_cursor;
move first from cheap_cursor;
fetch 10 from cheap_cursor;
move absolute 50000 from cheap_cursor;
fetch 10 from cheap_cursor;

ROLLBACK
Time: 4.054 ms
BEGIN
Time: 0.970 ms
DECLARE CURSOR
Time: 1.022 ms
MOVE 1010431
Time: 12434.136 ms
MOVE 1
Time: 4.409 ms
 id 
----
  2
  3
  4
  5
  6
  9
 10
 11
 12
 13
(10 rows)

Time: 4.418 ms
MOVE 1
Time: 30.055 ms
  id   
-------
 50003
 50004
 50005
 50006
 50007
 50008
 50009
 50010
 50011
 50012
(10 rows)

Time: 3.875 ms
expensive query
dms3_test=> abort;
begin;
declare expensive_cursor scroll cursor for select * from expensive order by id;
move all from expensive_cursor;
move first from expensive_cursor;
fetch 10 from expensive_cursor;
move absolute 50000 from expensive_cursor;
fetch 10 from expensive_cursor;

ROLLBACK
Time: 2.044 ms
BEGIN
Time: 0.739 ms
DECLARE CURSOR
Time: 51.912 ms
MOVE 68276
Time: 19036.148 ms
MOVE 1
Time: 1.055 ms
 id  
-----
  50
  55
  65
  89
 109
 110
 133
 144
 155
 186
(10 rows)

Time: 0.911 ms
MOVE 1
Time: 30.226 ms
   id   
--------
 749659
 749661
 749667
 749685
 749692
 749720
 749732
 749740
 749741
 749778
(10 rows)

Time: 1.736 ms
Characteristics:
  • complex implementation
  • high setup cost
  • suitable for expensive queries
  • suitable if user is expected to comprehensively browse the result set
  • isolated from underlying changes
  • barely noticeable latency

Hybrid Approach

One could do a hybrid approach. The implementation would be even more complex, but in some cases, it could combine the no setup cost benefit of the piecemeal approach and the low latency of the full result approach.
The hybrid approach would operate on piecemeal result set until a certain threshold is reached, e.g.: paging past page 7. When that happens, one of the full result set approach is executed, preferably in the background. The webapp could transition to using the full result set when it is ready.

Summary

                              Summary of Implementations                              
Query Type Implementation        Setup(ms) Counting(ms) First Page(ms) 5000th Page(ms)
         
         
         
Cheap    
         
         
         
          
New query per page  
                     
      N/A
         
    1094.187
            
        57.371
              
        134.610
               
Temporary Table     
                     
15125.956
         
         N/A
            
      4397.762
              
       4413.789
               
Cursor              
                     
    1.022
         
   12434.136
            
         8.827
              
         33.930
               
         
         
         
Expensive
         
         
         
          
New query per page  
                     
      N/A
         
   18034.510
            
        76.929
              
      14424.053
               
Temporary Table     
                     
18666.615
         
         N/A
            
       314.754
              
        342.207
               
Cursor              
                     
   51.921
         
   19036.148
            
         1.966
              
         31.962
               

 
 
(originally from http://microjet.ath.cx/WebWiki/ResultPaginationWithPostgresql.html)

2005-02-10

The Thirty Million Question

Recently I went for an interview where I was asked this question: How do you load thirty millions entries from a file into a database within 4 hours. 

I was puzzled on its significance. I have been using postgresql and loading 30 million entries is nothing special at all


Turned out they were using MS SQL. I was not sure what the deal was with batch loading of 30 million entries in MS SQL as I have minimum experience with that product. They cited a problem they encountered: apparently, they could not load 30 million entries within 4 hours without resorting to a technique which they had expected me to answer. Also, they said there was a problem with transaction log being overflowed. Beat me up, but I don't expect MS SQL to be having such problems, especially not on a high-end database machine that they had (it had 24 CPU, and I assume an equally impressive disk system and memory)

 I was not able to come up with an answer that they were looking for, that is, to break up the data into sections and bulk-load each section from separate session. Each session was to be initiated from a different computer, so as to reduce the load. (Note, though, that the question was highly MSSQL-specific. As I demonstrate below, postgresql has not any problem with loading 30 million entries).


Of course, the point of their question was not that loading 30 millions entries was hard, but rather, how do you load a large data within as short a time as possible.
 
So I was left thinking how loading from different sessions could hasten the loading process. Sure, I've read debates on postgresql mailing list on how loading from multiple sessions could reduce the time, but I have never paid any attention to it since I was not interested in it at that time.
I did not know much about the subject and had no opinion on that. So I accepted their answer for the time being. But, ever the curious type, I decided to conduct my own experiment.
I set on trying to answer three questions:
  1. Is loading 30 millions data in 4 hours hard to accomplish with postgresql?
  2. Does postgresql have any problem with loading 30 millions data in a single transaction?
  3. Does loading data from multiple sessions hasten the process?
For questions #1 and #2, the experiment was done on my laptop, a 1.3 GHz Pentium M with 512 MB RAM and a 4200 RPM disk, and running the assorted programs that I usually run: emacs, X, kde, etc.
This was, by no means, a dedicated database nor powerful machine. The experiment was going on while I continued doing what I usually do: web browsing, software development, chatting, etc. I do not expect to get consistent results between runs due to other ongoing activities nor do consistent results matter much since what I was looking for was an upper bound.

The experiment to answer question #3 was performed on a two 3 GHz Pentium 4 machine with 512 MB RAM and a RAID-5 array with 10K RPM SCSI disks. This was a dedicated database machine and I expected to get a more consistent results.

I expected that if multiple sessions turn out to hasten the process, then the gain would depend on how many indexes in the table. Data loading itself is an IO-bound activity, so, even with multiple sessions, the total write throughput would still be constrained by the maximum write rate of the disk system. On the other hand, indexing would involve a significant amount of computation. So, that would be limited by the amount of computing power available. You could probably run more than n sessions on a n-CPU computer since the CPUs would be idle some of the time while waiting for disk I/O. Yet, at some point, the overhead of context switches would be too big, so certainly there is a limit on the number of sessions. What is the limit? I don't know but I suspect that would depend very much on your system.

 

Questions #1 and #2

First, I write a simple script to generate the data:
#!/usr/bin/env ruby1.8
#/tmp/gen_data.rb

ARGV[0].to_i.upto(ARGV[1].to_i){|x|
  puts "#{x}\t#{10000+x}\t#{rand 500}\tdescription-#{x}"
} 
 
Sure, the data file they are importing would not be this simple. But that should not matter much since the most important thing, i.e.: reserving a row for the new data, is done equal amount of times. Populating the row mostly depends on your write throughput of your I/O data.
Then I generated 4 data files:
 
dede:~$ /usr/bin/time /tmp/gen_data.rb 1 30000000 > /tmp/data1.txt
333.07user 13.80system 6:29.38elapsed 89%CPU (0avgtext+0avgdata 0maxresident)k
0inputs+0outputs (5major+501minor)pagefaults 0swaps

dede:~$ /usr/bin/time /tmp/gen_data.rb 30000001 60000000 > /tmp/data2.txt
331.99user 13.95system 6:25.52elapsed 89%CPU (0avgtext+0avgdata 0maxresident)k
0inputs+0outputs (11major+477minor)pagefaults 0swaps

dede:~$ /usr/bin/time /tmp/gen_data.rb 60000001 90000000 > /tmp/data3.txt
322.55user 13.38system 6:13.09elapsed 90%CPU (0avgtext+0avgdata 0maxresident)k
0inputs+0outputs (0major+488minor)pagefaults 0swaps

dede:~$ /usr/bin/time /tmp/gen_data.rb 90000001 120000000 > /tmp/data4.txt
324.78user 13.67system 7:19.02elapsed 77%CPU (0avgtext+0avgdata 0maxresident)k
0inputs+0outputs (0major+488minor)pagefaults 0swaps

dede:~$ ls -lah /tmp/data*.txt
-rw-r--r--  1 ysantoso ysantoso 1.2G Feb  9 21:20 /tmp/data1.txt
-rw-r--r--  1 ysantoso ysantoso 1.2G Feb  9 21:45 /tmp/data2.txt
-rw-r--r--  1 ysantoso ysantoso 1.2G Feb  9 22:05 /tmp/data3.txt
-rw-r--r--  1 ysantoso ysantoso 1.3G Feb 10 22:30 /tmp/data4.txt

dede:~$ head -1 /tmp/data1.txt
0       10000   389     description-0

dede:~$ tail -1 /tmp/data1.txt
30000000 30010000 278 description-30000000

Then I created a database and a table in postgresql v. 7.4.6:
thirtymillion=> create table transactions (tid int4, mssinceunixepoch int4, amount int8, description text);
CREATE TABLE
thirtymillion=> \d transactions
      Table "public.transactions"
      Column      |  Type   | Modifiers
------------------+---------+-----------
 tid              | integer |
 mssinceunixepoch | integer |
 amount           | bigint  |
 description      | text    |

All the column names are fictitious.
I did not declare a primary key yet because I wanted to time data loading without any indexing as having a primary key implies having a unique index.
 
thirtymillion=# copy transactions from '/tmp/data.txt';
COPY
Time: 1639971.939 ms (27m20s)
So, 27m20s to load the first 30 millions. That's not bad at all. But how much time does indexing takes?
thirtymillion=> alter table transactions add primary key (tid);
NOTICE:  ALTER TABLE / ADD PRIMARY KEY will create implicit index "transactions_pkey" for table "transactions"
ALTER TABLE
Time: 1374100.087 ms (22m54s)

The total for loading and indexing the first thirty millions was: 27m20s + 22m54s = 50m14s.
Good news! That was nowhere near 4 hours! Could this be a fluke?
Let's load the next three thirty-million datasets:
 
dede:~$ echo "copy transactions from '/tmp/data2.txt' "| /usr/bin/time sudo -u postgres psql thirtymillion
COPY
0.01user 0.00system 38:19.59elapsed 0%CPU (0avgtext+0avgdata 0maxresident)k
0inputs+0outputs (0major+2286minor)pagefaults 0swaps

dede:~$ echo "copy transactions from '/tmp/data3.txt' "| /usr/bin/time sudo -u postgres psql thirtymillion
COPY
0.02user 0.01system 44:00.94elapsed 0%CPU (0avgtext+0avgdata 0maxresident)k
0inputs+0outputs (12major+2274minor)pagefaults 0swaps

dede:~$ echo "copy transactions from '/tmp/data4.txt' "| /usr/bin/time sudo -u postgres psql thirtymillion
COPY
0.01user 0.01system 45:03.43elapsed 0%CPU (0avgtext+0avgdata 0maxresident)k
0inputs+0outputs (22major+2264minor)pagefaults 0swaps

Don't heed the 0%CPU figure, as that's the CPU consumption of the client (psql), and not the server.
But, as you can see, the figures: 38m20s, 44m01s, and 45m03s are not that different from each other, and more importantly, all are under 4 hours. Notice that loading the first dataset took significantly longer than the rest. I do not know exactly why that was the case, but my hypothesis is the disk cache effectiveness is low if the loading and indexing are done separately. Perhaps the hypothesis is wrong, but what is important is I could now answer the first two questions:

  • Is loading 30 millions data in 4 hours hard to accomplish with postgresql? No
  • Does postgresql have any problem with loading 30 millions data in a single transaction? No

 

Question #3

I setup several data files, each contained 30 million entries for four sub-experiments:
  1. Time separate loading and indexing as in the previous experiment
  2. Time combined loading and indexing.
  3. Time two concurrent loading and indexing sessions. The machine had two CPUs, so each CPU handled at most a session.
  4. Time six concurrent loading and indexing sessions. The idea was to simulate high CPU and IO consumptions condition.
A sample of data generation:
 
$ /usr/bin/time ./gen_data.rb 1 30000000 > data1.txt
180.55user 4.74system 3:05.40elapsed 99%CPU (0avgtext+0avgdata 0maxresident)k
0inputs+0outputs (17major+531minor)pagefaults 0swaps

Now, let's time loading the first thirty million without indexing it:
 
$ echo "copy transactions from '/c1/tmp/30mil/data1.txt'"| sudo -u postgres /usr/bin/time psql thirtymillion
COPY
0.00user 0.01system 12:26.37elapsed 0%CPU (0avgtext+0avgdata 0maxresident)k
0inputs+0outputs (0major+2015minor)pagefaults 0swaps

The time, 12m26s, about half of 27m20s as in the laptop case, was as expected since loading should be an IO-bound process. A 10K RPM disk should be able to write data about twice as quickly as a 4200 RPM disk.

Indexing it:
 
$ echo "alter table transactions add primary key (tid)" | /usr/bin/time psql thirtymillion
NOTICE:  ALTER TABLE / ADD PRIMARY KEY will create implicit index "transactions_pkey" for table "transactions"
ALTER TABLE
0.00user 0.01system 8:55.03elapsed 0%CPU (0avgtext+0avgdata 0maxresident)k
0inputs+0outputs (0major+2024minor)pagefaults 0swaps

Total time for the first batch was: 12m26s + 8m55s = 21m21s.

As expected, indexing benefited from a more powerful CPU. Then, could concurrent sessions reduce the total time simply because that uses the other CPU? Before I went on answering that question, I timed the combined loading and indexing of the data.
 
$ echo "copy transactions from '/c1/tmp/30mil/data2.txt'"| sudo -u postgres /usr/bin/time psql thirtymillion
COPY
0.00user 0.01system 15:00.04elapsed 0%CPU (0avgtext+0avgdata 0maxresident)k
0inputs+0outputs (0major+2025minor)pagefaults 0swaps

15m00s, a bit faster than doing the loading and indexing separately.
Now let's time two-concurrent loading and indexing:
 
$ echo "copy transactions from '/c1/tmp/30mil/data3.txt'"| sudo -u postgres /usr/bin/time psql thirtymillion & 
echo "copy transactions from '/c1/tmp/30mil/data4.txt'"| sudo -u postgres /usr/bin/time psql thirtymillion &

COPY
0.01user 0.01system 30:41.26elapsed 0%CPU (0avgtext+0avgdata 0maxresident)k
0inputs+0outputs (1major+2016minor)pagefaults 0swaps
COPY
0.01user 0.01system 31:05.41elapsed 0%CPU (0avgtext+0avgdata 0maxresident)k
0inputs+0outputs (1major+2017minor)pagefaults 0swaps
 
It took about 30min to load 2*30=60 millions rows. It's twice as long as loading 30 million rows. The loading time seems to grow linearly.
If the time taken is linear at 30million/15mins, then 6*30mil=180 million rows should take about 6*15min=1h30min. Let's verify:
 
 
 
$ echo "copy transactions from '/c1/tmp/30mil/data5.txt'"| sudo -u postgres /usr/bin/time psql thirtymillion &
echo "copy transactions from '/c1/tmp/30mil/data6.txt'"| sudo -u postgres /usr/bin/time psql thirtymillion &
echo "copy transactions from '/c1/tmp/30mil/data7.txt'"| sudo -u postgres /usr/bin/time psql thirtymillion &
echo "copy transactions from '/c1/tmp/30mil/data8.txt'"| sudo -u postgres /usr/bin/time psql thirtymillion &
echo "copy transactions from '/c1/tmp/30mil/data9.txt'"| sudo -u postgres /usr/bin/time psql thirtymillion &
echo "copy transactions from '/c1/tmp/30mil/data10.txt'"| sudo -u postgres /usr/bin/time psql thirtymillion &

COPY
0.01user 0.01system 1:36:44elapsed 0%CPU (0avgtext+0avgdata 0maxresident)k
0inputs+0outputs (0major+2022minor)pagefaults 0swaps
COPY
0.01user 0.01system 1:38:23elapsed 0%CPU (0avgtext+0avgdata 0maxresident)k
0inputs+0outputs (0major+2023minor)pagefaults 0swaps
COPY
0.01user 0.01system 1:39:05elapsed 0%CPU (0avgtext+0avgdata 0maxresident)k
0inputs+0outputs (0major+2011minor)pagefaults 0swaps
COPY
0.01user 0.02system 1:39:09elapsed 0%CPU (0avgtext+0avgdata 0maxresident)k
0inputs+0outputs (0major+2016minor)pagefaults 0swaps
COPY
0.01user 0.01system 1:39:18elapsed 0%CPU (0avgtext+0avgdata 0maxresident)k
0inputs+0outputs (0major+2011minor)pagefaults 0swaps
COPY
0.01user 0.02system 1:39:20elapsed 0%CPU (0avgtext+0avgdata 0maxresident)k
0inputs+0outputs (0major+2020minor)pagefaults 0swaps 
 
Indeed! 180 million rows took about 1h30min.
 
So, 12*30million= 360 millions should take about 12*15min = 3 hours. Let's verify:
Twelve! concurrent bulk-loading with only 2 CPUs to perform those: 
$ echo "copy transactions from '/c1/tmp/30mil/data11.txt'"| sudo -u postgres /usr/bin/time psql thirtymillion &
echo "copy transactions from '/c1/tmp/30mil/data12.txt'"| sudo -u postgres /usr/bin/time psql thirtymillion &
echo "copy transactions from '/c1/tmp/30mil/data13.txt'"| sudo -u postgres /usr/bin/time psql thirtymillion &
echo "copy transactions from '/c1/tmp/30mil/data14.txt'"| sudo -u postgres /usr/bin/time psql thirtymillion &
echo "copy transactions from '/c1/tmp/30mil/data15.txt'"| sudo -u postgres /usr/bin/time psql thirtymillion &
echo "copy transactions from '/c1/tmp/30mil/data16.txt'"| sudo -u postgres /usr/bin/time psql thirtymillion &
echo "copy transactions from '/c1/tmp/30mil/data17.txt'"| sudo -u postgres /usr/bin/time psql thirtymillion &
echo "copy transactions from '/c1/tmp/30mil/data18.txt'"| sudo -u postgres /usr/bin/time psql thirtymillion &
echo "copy transactions from '/c1/tmp/30mil/data19.txt'"| sudo -u postgres /usr/bin/time psql thirtymillion &
echo "copy transactions from '/c1/tmp/30mil/data20.txt'"| sudo -u postgres /usr/bin/time psql thirtymillion &
echo "copy transactions from '/c1/tmp/30mil/data21.txt'"| sudo -u postgres /usr/bin/time psql thirtymillion &
echo "copy transactions from '/c1/tmp/30mil/data22.txt'"| sudo -u postgres /usr/bin/time psql thirtymillion &

COPY
0.01user 0.02system 3:29:18elapsed 0%CPU (0avgtext+0avgdata 0maxresident)k
0inputs+0outputs (0major+2018minor)pagefaults 0swaps
COPY
0.01user 0.02system 3:32:57elapsed 0%CPU (0avgtext+0avgdata 0maxresident)k
0inputs+0outputs (0major+2016minor)pagefaults 0swaps
COPY
0.01user 0.01system 3:33:27elapsed 0%CPU (0avgtext+0avgdata 0maxresident)k
0inputs+0outputs (0major+2017minor)pagefaults 0swaps
COPY
0.01user 0.02system 3:33:41elapsed 0%CPU (0avgtext+0avgdata 0maxresident)k
0inputs+0outputs (0major+2017minor)pagefaults 0swaps
COPY
0.01user 0.02system 3:33:52elapsed 0%CPU (0avgtext+0avgdata 0maxresident)k
0inputs+0outputs (0major+2021minor)pagefaults 0swaps
COPY
0.01user 0.02system 3:34:12elapsed 0%CPU (0avgtext+0avgdata 0maxresident)k
0inputs+0outputs (0major+2016minor)pagefaults 0swaps
COPY
0.01user 0.01system 3:34:37elapsed 0%CPU (0avgtext+0avgdata 0maxresident)k
0inputs+0outputs (0major+2019minor)pagefaults 0swaps
COPY
0.01user 0.02system 3:34:39elapsed 0%CPU (0avgtext+0avgdata 0maxresident)k
0inputs+0outputs (0major+2019minor)pagefaults 0swaps
COPY
0.01user 0.02system 3:35:08elapsed 0%CPU (0avgtext+0avgdata 0maxresident)k
0inputs+0outputs (0major+2019minor)pagefaults 0swaps
COPY
0.01user 0.01system 3:35:16elapsed 0%CPU (0avgtext+0avgdata 0maxresident)k
0inputs+0outputs (0major+2014minor)pagefaults 0swaps
COPY
0.01user 0.01system 3:35:19elapsed 0%CPU (0avgtext+0avgdata 0maxresident)k
0inputs+0outputs (0major+2012minor)pagefaults 0swaps
COPY
0.01user 0.01system 3:35:23elapsed 0%CPU (0avgtext+0avgdata 0maxresident)k
0inputs+0outputs (0major+2011minor)pagefaults 0swaps 
 
It's close. Predicted 3 hours, actual 3h35min. 
 
I didn't really pay attention to the CPU consumption during the run, so I couldn't tell if the slowdown was due to the process being CPU-bound or IO-bound.
But I now can answer question #3:

  • Does loading data from multiple sessions hasten the process? No.
If anything, loading data from too many sessions actually slows down the process.
 
 
By the end of the experimentation, I've loaded more than 500 million rows into pgsql at a remarkably steady rate of 30 million rows /15 mins. I am not sure why they needed 4 hours to do the same. Even accounting for various referential integrity checkings that may be present, 4 hours is still 16x 15 mins.

I think they need to look closer at their DBA...