Another example when trying to create two hosts at the same time:

[2015-10-16 13:05:21.931 CEST] [26005]: LOG:  process 26005 still waiting for ShareLock on transaction 299685807 after 1000.079 ms
[2015-10-16 13:05:21.931 CEST] [26005]: CONTEXT:  SQL statement "SELECT 1 FROM ONLY "public"."architectures" x WHERE "id" OPERATOR(pg_catalog.=) $1 FOR SHARE OF x" 
[2015-10-16 13:05:21.931 CEST] [26005]: STATEMENT:  INSERT INTO "hosts" ("architecture_id", "build", "certname", "comment", "compute_profile_id", "compute_resource_id", "created_at", "disk", "enabled", "environment_id", "grub_pass", "hostgroup_id", "image_file", "image_id", "installed_at", "last_compile", "last_report", "location_id", "managed", "medium_id", "model_id", "name", "operatingsystem_id", "organization_id", "otp", "owner_id", "owner_type", "provision_method", "ptable_id", "puppet_ca_proxy_id", "puppet_proxy_id", "puppet_status", "realm_id", "root_pass", "type", "updated_at", "use_image", "uuid") VALUES ($1, $2, $3, $4, $5, $6, $7, $8, $9, $10, $11, $12, $13, $14, $15, $16, $17, $18, $19, $20, $21, $22, $23, $24, $25, $26, $27, $28, $29, $30, $31, $32, $33, $34, $35, $36, $37, $38) RETURNING "id" 
[2015-10-16 13:07:03.397 CEST] [26005]: LOG:  process 26005 acquired ShareLock on transaction 299685807 after 102465.235 ms
[2015-10-16 13:07:03.397 CEST] [26005]: CONTEXT:  SQL statement "SELECT 1 FROM ONLY "public"."architectures" x WHERE "id" OPERATOR(pg_catalog.=) $1 FOR SHARE OF x" 
[2015-10-16 13:07:03.397 CEST] [26005]: STATEMENT:  INSERT INTO "hosts" ("architecture_id", "build", "certname", "comment", "compute_profile_id", "compute_resource_id", "created_at", "disk", "enabled", "environment_id", "grub_pass", "hostgroup_id", "image_file", "image_id", "installed_at", "last_compile", "last_report", "location_id", "managed", "medium_id", "model_id", "name", "operatingsystem_id", "organization_id", "otp", "owner_id", "owner_type", "provision_method", "ptable_id", "puppet_ca_proxy_id", "puppet_proxy_id", "puppet_status", "realm_id", "root_pass", "type", "updated_at", "use_image", "uuid") VALUES ($1, $2, $3, $4, $5, $6, $7, $8, $9, $10, $11, $12, $13, $14, $15, $16, $17, $18, $19, $20, $21, $22, $23, $24, $25, $26, $27, $28, $29, $30, $31, $32, $33, $34, $35, $36, $37, $38) RETURNING "id" 
[2015-10-16 13:07:03.398 CEST] [26005]: LOG:  duration: 102467.738 ms  execute a12: INSERT INTO "hosts" ("architecture_id", "build", "certname", "comment", "compute_profile_id", "compute_resource_id", "created_at", "disk", "enabled", "environment_id", "grub_pass", "hostgroup_id", "image_file", "image_id", "installed_at", "last_compile", "last_report", "location_id", "managed", "medium_id", "model_id", "name", "operatingsystem_id", "organization_id", "otp", "owner_id", "owner_type", "provision_method", "ptable_id", "puppet_ca_proxy_id", "puppet_proxy_id", "puppet_status", "realm_id", "root_pass", "type", "updated_at", "use_image", "uuid") VALUES ($1, $2, $3, $4, $5, $6, $7, $8, $9, $10, $11, $12, $13, $14, $15, $16, $17, $18, $19, $20, $21, $22, $23, $24, $25, $26, $27, $28, $29, $30, $31, $32, $33, $34, $35, $36, $37, $38) RETURNING "id" 

We have now upgraded to postgres 9.4 and get locks related to this (tested with sql query:

SELECT bl.pid                 AS blocked_pid,
         a.usename              AS blocked_user,
         ka.query               AS blocking_statement,
         now() - ka.query_start AS blocking_duration,
         kl.pid                 AS blocking_pid,
         ka.usename             AS blocking_user,
         a.query                AS blocked_statement,
         now() - a.query_start  AS blocked_duration
  FROM  pg_catalog.pg_locks         bl
   JOIN pg_catalog.pg_stat_activity a  ON a.pid = bl.pid
   JOIN pg_catalog.pg_locks         kl ON kl.transactionid = bl.transactionid AND kl.pid != bl.pid
   JOIN pg_catalog.pg_stat_activity ka ON ka.pid = kl.pid
  WHERE NOT bl.GRANTED;

There are two records in the result:

Query 1:

DELETE FROM "taxable_taxonomies" WHERE "taxable_taxonomies"."id" = $1

is waiting for this query:

UPDATE "domains" SET "hostgroups_count" = COALESCE("hostgroups_count", 0) - 1 WHERE "domains"."id" IN (SELECT "domains"."id" FROM "domains"  WHERE "domains"."id" = 2 ORDER BY domains.name)

Query 2:

UPDATE "domains" SET "hostgroups_count" = COALESCE("hostgroups_count", 0) - 1 WHERE "domains"."id" IN (SELECT "domains"."id" FROM "domains"  WHERE "domains"."id" = 2 ORDER BY domains.name)

is waiting for this query:

SELECT "hosts".id FROM "hosts"  WHERE "hosts"."type" IN ('Host::Managed') AND "hosts"."hostgroup_id" = 4292

So it looks like the :hostgroups_count logic in the Domain class (mapping to table domains) is making queries wait also in postgresql 9.4.

Would it be ok to just remove the counter cache? I tested a couple of count(*) queries for 5.5K hosts and they were all pretty fast (less than 3msec).

I share the opinion, one big warning - while it might work just fine on PostgreSQL, the other database MySQL can be the issue. If this turns out to be it, we should go ahead and reopen discussion of dropping MySQL from supported databases.