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:

for x in a:
for y in b:
if a == y:
return row

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:

Nested Loop (cost=18539.46..30587.66 rows=22 width=111)
(actual time=160.149..291490.221 rows=35005 loops=1)

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.

Hans-Juergen Schoenig
Hans-Jürgen Schönig has 15 years of experience with PostgreSQL. He is consultant and CEO of the company „Cybertec Schönig & Schönig GmbH“ (www.cybertec.at, www.postgresql-support.de), which has served countless customers around the globe.