The other day we had a moderate complex query which involved around 270000 rows but run for over an hour. After updating the statistics the query finished in only 4 seconds.
The query looked like so:
WITH input_rows as ( SELECT [270000 rows] FROM source WHERE [filter] ), subset_of_input_rows as ( SELECT [13000 rows] FROM input_rows ), join_both_ctes as ( SELECT [270000 input_rows] LEFT JOIN [13000 subset_of_input_rows] )
Let’s set aside the application and take the two keypoints from this query:
- an initial subset of a source table is selected
- a JOIN operation needs to be done on the selected subset
This is by no means a convoluted query, however it still took 1 hour even though we set up indices.
Looking into the execution plan reveals two main problems:
- the optimizer assumes the input_rows cte would return a resultset of 1
- Building on that, it uses a NESTED LOOP JOIN to join both sets of data
nested loop join: The right relation is scanned once for every row found in the left relation. This strategy is easy to implement but can be very time consuming (postgres doc)
Because it assumed a wrong number of rows to be worked on, the optimizer utilizes a nested loop join, which just takes the smaller relation and for every row checks, whether that row is included within the bigger relation, which means it would check 13000 rows from subset_of_input_rows x 270000 rows from input_rows resulting in enormous workload.
“Most queries retrieve only a fraction of the rows in a table, due to
WHERE clauses that restrict the rows to be examined. The planner thus needs to make an estimate of the selectivity of
WHERE clauses, that is, the fraction of rows that match each condition in the
WHERE clause. The information used for this task is stored in the
pg_statistic system catalog” (postgres doc)
The key to solving this problem was to tell the optimizer a better approximation of input rows. That was eventually done with ANALYZE (postgres doc), which updates statistics and thus the optimizer managed to approximate a better resultset and deciding for a way more efficient Merge Join than a Nested Loop Join.