Exploding runtime: How nested loops can destroy speed

Sometimes it happens that a query slows down dramatically for no obvious reason. In other cases queries go south in case a certain set of input parameters is used. In some of those situations, wrong optimizer estimates can be the root cause of all evil. One of my “favorite” issues with wrong planner estimates: Underestimated nested loops.

What are nested loops?

Nested loops are a means to join things. They are usually used if “one side” of the join consists of only a small set of data. Here is some pseudo code explaining how it works:

Maybe you can join a table containing millions of people with a table containing only a handful of genders - this might be a good candidate for a nested loop.

What can go wrong

But what will happen if the optimizer underestimates the number of rows involved in a nested loop? Runtime will go through the roof. A nested loop is O(n^2) so runtime will grow very fast as the amount of data grows. Logically the consequences will be a disaster.

Here is an example:

In this example the optimizer thinks that 22 rows will be needed. However, in reality the nested loop ended up finding 35005 rows. Why is that critical? Just look at the “actual time”. It went up from 160 ms to a staggering 291490 ms. Runtime has simply exploded.

There are a couple of ways to attack the problem:

• Fix estimates
• Turn nested loops for the specific query off

As you can imagine a.) is definitely the best solution. However, in some cases this is not possible so running “SET enable_nestloop TO off” before the query might just fix the problem. However, make sure they are turned on again after the query in doubt has completed.

In case you need any assistance, please feel free to contact us.
 

In order to receive regular updates on important changes in PostgreSQL, subscribe to our newsletter, or follow us on Facebook or LinkedIn.