PostgreSQL query taking too long

Question

I have database with few hundred millions of rows. I'm running the following query:

select * from "Payments" as p
inner join "PaymentOrders" as po
on po."Id" = p."PaymentOrderId"
inner join "Users" as u
On u."Id" = po."UserId"
INNER JOIN "Roles" as r
on u."RoleId" = r."Id"
Where r."Name" = 'Moses'
LIMIT 1000

When the where clause finds a match in database, I get the result in several milliseconds, but if I modify the query and specify a non-existent r."Name" in where clause, it takes too much time to complete. I guess that PostgreSQL is doing a sequential scan on the Payments table (which contains the most rows), comparing each row one by one.

Isn't postgresql smart enough to check first if Roles table contains any row with Name 'Moses'?

Roles table contains only 15 row, while Payments contains ~350 million.

I'm running PostgreSQL 9.2.1.

BTW, this same query on the same schema/data takes 0.024ms to complete on MS SQL Server.

I'll update the question and post EXPLAIN ANALYSE data in a few hours.

---

Here'e explain analyse results: http://explain.depesz.com/s/7e7

---

And here's server configuration:

version PostgreSQL 9.2.1, compiled by Visual C++ build 1600, 64-bit
client_encoding UNICODE
effective_cache_size    4500MB
fsync   on
lc_collate  English_United States.1252
lc_ctype    English_United States.1252
listen_addresses    *
log_destination stderr
log_line_prefix %t 
logging_collector   on
max_connections 100
max_stack_depth 2MB
port    5432
search_path dbo, "$user", public
server_encoding UTF8
shared_buffers  1500MB
TimeZone    Asia/Tbilisi
wal_buffers 16MB
work_mem    10MB

I'm running postgresql on a i5 cpu (4 core, 3.3 GHz), 8 GB of RAM and Crucial m4 SSD 128GB

---

UPDATE This looks like a bug in query planner. With the recomendation of Erwin Brandstetter I reported it to Postgresql bugs mailing list.

Solution 1

Finally successful attempt

My other idea - as per comment:
What happens if you remove the LIMIT clause for the case where no role is found? I have a suspicion that it will result in the fast plan - making LIMIT the culprit here.

You may be able to solve your problem by pushing down your query into a subquery and applying the LIMIT only to the outer query (untested):

SELECT *
FROM  (
   SELECT *
   FROM   "Roles"         AS r  
   JOIN   "Users"         AS u  ON u."RoleId" = r."Id"
   JOIN   "PaymentOrders" AS po ON po."UserId" = u."Id"
   JOIN   "Payments"      AS p  ON p."PaymentOrderId" = po."Id"
   WHERE  r."Name" = 'Moses'
  ) x
LIMIT  1000;

As per comment: @Davita tested and ruled out this workaround. @Kevin's answer later clarified why the workaround failed: use a CTE instead of the subquery.
Or check for existence of a role, before you employ the big query to eliminate the bad case.

This leaves questions for PostgreSQL concerning the optimization of queries with LIMIT.

There have been a number of recent bug reports concerning query plans with LIMIT. I quote Simon Riggs commenting on one of these reports here:

Very bad plans with LIMIT are frequent. This is bad for us because adding LIMIT usually/is supposed to make queries faster, not slower.

We need to do something.

First attempt with no success

I missed that @Craig already mentioned join_collapse_limit in the comments. So that was of limited use:

Does reordering the JOIN clauses have any effect?

SELECT *
FROM   "Roles"         AS r  
JOIN   "Users"         AS u  ON u."RoleId" = r."Id"
JOIN   "PaymentOrders" AS po ON po."UserId" = u."Id"
JOIN   "Payments"      AS p  ON p."PaymentOrderId" = po."Id"
WHERE  r."Name" = 'Moses'
LIMIT  1000

Related: you did not by chance mess with the setting of join_collapse_limit or geqo_threshold? Very low setting might prevent the planner from reordering your JOIN clauses, which might explain your problem.

If that does not solve the case, I would try to create an index on "Roles"(Name). Not that this makes any sense with only 15 rows, but I would try to eliminate the suspicion that invalid statistics or cost parameters (or even a bug) make the planner believe the sequential scan on "Roles" to be more expensive than it is.

Solution 2

As suggested a couple times on the thread on the PostgreSQL community performance list, you can work around this issue by forcing an optimization barrier using a CTE, like this:

WITH x AS
(
SELECT *
  FROM "Payments" AS p
  JOIN "PaymentOrders" AS po ON po."Id" = p."PaymentOrderId"
  JOIN "Users" as u ON u."Id" = po."UserId"
  JOIN "Roles" as r ON u."RoleId" = r."Id"
  WHERE r."Name" = 'Moses'
)
SELECT * FROM x
  LIMIT 1000;

You may also get a good plan for your original query if you set a higher statistics target for "Roles"."Name" and then ANALYZE. For example:

ALTER TABLE "Roles"
  ALTER COLUMN "Name" SET STATISTICS 1000;
ANALYZE "Roles";

If it expects fewer matching rows to exist in the table, as it is likely to do with more fine-grained statistics, it will assume that it needs to read a higher percentage of the table to find them on a sequential scan. This may cause it to prefer using the index instead of sequentially scanning the table.

You might also get a better plan for the original query by adjusting some of the planner's costing constants and caching assumptions. Things you could try in a single session, with the SET command:

• Reduce random_page_cost. This is largely based on how heavily cached your data is. Given a table with hundreds of millions of rows you probably don't want to go below 2; although if the active data set in your database is heavily cached you can reduce it all the way down to the setting for seq_page_cost, and you may want to reduce both of them by an order of magnitude.

• Make sure that effective_cache_size is set to the sum of shared_buffers and whatever your OS is caching. This doesn't allocate any memory; it just tells the optimizer how likely index pages are to remain in cache during heavy access. A higher setting makes indexes look better when compared to sequential scans.

• Increase cpu_tuple_cost to somewhere in the range of 0.03 to 0.05. I have found the default of 0.01 to be too low. I often get better plans by increasing it, and have never seen a value in the range I suggested cause worse plans to be chosen.

• Make sure that your work_mem setting is reasonable. In most environments that I've run PostgreSQL, that is in the 16MB to 64MB range. This will allow better use of hash tables, bitmap index scans, sorts, etc., and can completely change your plans; almost always for the better. Beware setting this to a level that yields good plans if you have a large number of connections -- you should allow for the fact that each connection can allocate this much memory per node of the query it is running. The "rule of thumb" is to figure you will hit peaks around this setting times max_connections. This is one of the reasons that it is wise to limit your actual number of database connections using a connection pool.

If you find a good combination of settings for these, you might want to make those changes to your postgresql.conf file. If you do that, monitor closely for performance regressions, and be prepared to tweak the settings for the best performance of your overall load.

I agree that we need to do something to nudge the optimizer away from "risky" plans, even if they look like they will run faster on average; but I will be a little surprised if tuning your configuration so that the optimizer better models the actual costs of each alternative doesn't cause it to use an efficient plan.

Comments

[a_horse_with_no_name]

If changing the join order changed something I would consider this a bug in PostgreSQL.

[Davita]

Thanks Erwin, I tried your suggestions, I changed join_collapse_limit to 16 and then 64 but I've got same result. I tried your query and nothing changed. I added a B-TREE index on Roles.Name but no change :| I'm really confused here.

[Erwin Brandstetter]

@a_horse_with_no_name: With a small number of tables the planner reorders JOINs to fit its best estimate. But the optimal order of JOINs is an O(n!) problem. So there is a limit after which more generic attempt on optimization are used. Of course, this shouldn't be a problem at all for just 4 tables. Query execution obviously starts at the wrong end here, therefore my shot in the dark at join_collapse_limit - and the now added geqo_threshold.

[Erwin Brandstetter]

@Davita: Sorry, at least it rules out some possible (theoretical) causes. Did you look at geqo_threshold, too? (Added later.)

[Davita]

@ErwinBrandstetter thanks again Erwin, I just tried setting geqo_threshold(though I've no idea what it is :D) to 40 but still same query plan.

[Erwin Brandstetter]

Next idea: VACUUM FULL ANALYZE "Role" If that doesn't do anything, I'd try VACUUM FULL ANALYZE on the database - will be expensive with millions of rows! So maybe at off hours if you have concurrent load. But these are all just shots in the dark ..

[Davita]

@ErwinBrandstetter thanks Erwin, I already tried VACUUM FULL ANALYZE and it didn't help. I also re-analyzed Role table after adding index.

[vyegorov]

Per documentation, explicit join syntax forces PostgreSQL to join tables in the specified order. So if original query and the one suggested by Erwin produces different plans, something is wrong here.

[Erwin Brandstetter]

@vyegorov: Explicit join syntax only forces the order when join_collapse_limit is lower than the number of tables. You meant that, right?

[Davita]

@ErwinBrandstetter you were right, LIMIT was the cause of an incorrect query plan. I removed LIMIT and everything runs perfectly :) Thank you very much. Could you please update your post so I can accept it and others will find it useful? Thanks again :)

[Davita]

Wonderful, thank you very much for definitive answer. Just one note, by pushing the query in a subquery doesn't solve the issue, looks like this is a big problem in PostgreSQL, but still, checking the existence first is definitely a fix. Maybe someone can give me a hint where can I report this issue (if it is considered as an issue at all?). Thank you very much Erwin.

[Erwin Brandstetter]

@Davita: You have been very cooperative, you are very welcome. You might report this to [email protected] Or use the form provided here. More options: postgresql.org/community/lists I suggest you link to this page for context. I remember having similar problems in the past, may be a long-standing issue ..

[Davita]

@ErwinBrandstetter Thanks again, I reported the issue :)

[Erwin Brandstetter]

@Davita: maybe add a link to the post to the question - once you have it.

[Davita]

@ErwinBrandstetter yes, I sent them the link to this thread and gave them lots of explanation :)

[Erwin Brandstetter]

@Davita: I mean the other way round: add this link archives.postgresql.org/pgsql-bugs/2012-11/msg00089.php to your question. :)

[Davita]

@ErwinBrandstetter sorry, my bad :))

[Erwin Brandstetter]

@Davita: I added a link to similar bug reports to my answer.

[Davita]

@ErwinBrandstetter Ouch, there were already many reports, hope one more won't hurt :)

[Erwin Brandstetter]

@Davita: As I wrote: may be a long-standing issue... A reminder won't hurt. Your case is particularly clear-cut.

[Davita]

Wow, that was a great answer. Thanks friend and +1 :)