Content-Type: multipart/alternative;
 boundary="------------juLiX0FD7C660vGZuKWvaeEp"
Message-ID: <07b89cad-b2a1-48c2-8a14-67d1b93098c9@negora.com>
Date: Thu, 18 Apr 2024 13:00:38 +0200
MIME-Version: 1.0
User-Agent: Mozilla Thunderbird
From: negora <public@negora.com>
Content-Language: en-US, es-ES, en-GB
To: PostgreSQL - General <pgsql-general@lists.postgresql.org>
Subject: Why does it sort rows after a nested loop that uses already-sorted
 indexes?
Archived-At: <https://www.postgresql.org/message-id/07b89cad-b2a1-48c2-8a14-67d1b93098c9%40negora.com>
Precedence: bulk

This is a multi-part message in MIME format.
--------------juLiX0FD7C660vGZuKWvaeEp
Content-Type: text/plain; charset=UTF-8; format=flowed
Content-Transfer-Encoding: 8bit

Hi:

I've a question regarding nested loops and the order in which they 
return rows. Can you help me, please?

Suppose that I've two tables:

     - Table [sales_order]

         * Columns [id]
         * Index [sales_order_pkey] on [id]

     - Table [order_line]

         * Columns [id], [sales_order_id]
         * Index [order_line_ukey] on [sales_order_id], [id]

Then, I run the following query:

-----------------------------------------------------------

SELECT sales_order.id, order_line.id

FROM main.sales_order

JOIN main.order_line ON order_line.sales_order_id = sales_order.id

WHERE sales_order.customer_id = 2

ORDER BY sales_order.id, order_line.id;

-----------------------------------------------------------

The query planner decides to use the following nested loop:

-----------------------------------------------------------

Incremental Sort  (cost=26.90..16020.06 rows=144955 width=8)

   Sort Key: sales_order.id, order_line.id

   Presorted Key: sales_order.id

   ->  Nested Loop  (cost=0.70..4593.99 rows=144955 width=8)

         ->  Index Scan using sales_order_pkey on sales_order  
(cost=0.28..19.31 rows=79 width=4)

               Filter: (customer_id = 2)

         ->  Index Only Scan using order_line_ukey on order_line  
(cost=0.42..39.22 rows=1869 width=8)

               Index Cond: (sales_order_id = sales_order.id)

-----------------------------------------------------------

As you can see, the planner does detect that the outer loop returns the 
rows presorted by [sales_order.id]. However, it's unable to detect that 
the rows returned by the inner loop are also sorted by [sales_order.id] 
first, and then by [order_line.id].

Why is it? Is it because the planner is designed to always ignore the 
order of the inner loop, even although it could take advantage of it 
(for example, because the analysis time rarely is worth it)? Or is there 
something that I'm missing?

If I'm not mistaken, in this case both index scans seem to be done 
serially, in an N x M style, so I think the row order would be 
preserved, Right?

Thank you!

negora


--------------juLiX0FD7C660vGZuKWvaeEp
Content-Type: text/html; charset=UTF-8
Content-Transfer-Encoding: 8bit

<!DOCTYPE html>
<html>
  <head>

    <meta http-equiv="content-type" content="text/html; charset=UTF-8">
    <style>#CustomCSS-add-on-marker{}
.code {
    padding: 0.00em 0.30em 0.00em 0.30em;
    background-color: #ebf6e8;
    color: #003a0f;
    font-family: "DejaVu Sans Mono", monospace;
    font-size: 1.00em;
}
.code a:link {
    color: #003a0f;
    text-decoration: underline;
}
</style>
  </head>
  <body>
    <p>Hi:<br>
      <br>
      I've a question regarding nested loops and the order in which they
      return rows. Can you help me, please?<br>
      <br>
      Suppose that I've two tables:<br>
      <br>
          - Table [sales_order]<br>
      <br>
              * Columns [id]<br>
              * Index [sales_order_pkey] on [id]<br>
      <br>
          - Table [order_line]<br>
      <br>
              * Columns [id], [sales_order_id]<br>
              * Index [order_line_ukey] on [sales_order_id], [id]<br>
      <br>
      Then, I run the following query:<br>
      <br>
      -----------------------------------------------------------<br>
    </p>
    <pre><font size="4">SELECT sales_order.id, order_line.id</font></pre>
    <pre><font size="4">FROM main.sales_order</font></pre>
    <pre><font size="4">JOIN main.order_line ON order_line.sales_order_id = sales_order.id</font></pre>
    <pre><font size="4">WHERE sales_order.customer_id = 2</font></pre>
    <pre><font size="4">ORDER BY sales_order.id, order_line.id;</font></pre>
    <p>-----------------------------------------------------------<br>
      <br>
      The query planner decides to use the following nested loop:<br>
      <br>
      -----------------------------------------------------------<br>
    </p>
    <pre><font size="4">Incremental Sort  (cost=26.90..16020.06 rows=144955 width=8)</font></pre>
    <pre><font size="4">  Sort Key: sales_order.id, order_line.id</font></pre>
    <pre><font size="4">  Presorted Key: sales_order.id</font></pre>
    <pre><font size="4">  -&gt;  Nested Loop  (cost=0.70..4593.99 rows=144955 width=8)</font></pre>
    <pre><font size="4">        -&gt;  Index Scan using sales_order_pkey on sales_order  (cost=0.28..19.31 rows=79 width=4)</font></pre>
    <pre><font size="4">              Filter: (customer_id = 2)</font></pre>
    <pre><font size="4">        -&gt;  Index Only Scan using order_line_ukey on order_line  (cost=0.42..39.22 rows=1869 width=8)</font></pre>
    <pre><font size="4">              Index Cond: (sales_order_id = sales_order.id)</font></pre>
    <p>-----------------------------------------------------------<br>
      <br>
      As you can see, the planner does detect that the outer loop
      returns the rows presorted by [sales_order.id]. However, it's
      unable to detect that the rows returned by the inner loop are also
      sorted by [sales_order.id] first, and then by [order_line.id].<br>
      <br>
      Why is it? Is it because the planner is designed to always ignore
      the order of the inner loop, even although it could take advantage
      of it (for example, because the analysis time rarely is worth it)?
      Or is there something that I'm missing?<br>
      <br>
      If I'm not mistaken, in this case both index scans seem to be done
      serially, in an N x M style, so I think the row order would be
      preserved, Right?</p>
    <p>Thank you!<br>
    </p>
    <p>negora</p>
    <p><br>
    </p>
  </body>
</html>

--------------juLiX0FD7C660vGZuKWvaeEp--