Message-ID: <444ccfcc-06d6-0160-f662-9fa2075229ad@gmail.com>
Date: Sat, 11 Feb 2023 17:49:02 +0530
MIME-Version: 1.0
User-Agent: Mozilla/5.0 (X11; Linux x86_64; rv:102.0) Gecko/20100101
 Thunderbird/102.7.1
Content-Language: en-US
From: Ankit Kumar Pandey <itsankitkp@gmail.com>
Subject: Sort optimizations: Making in-memory sort cache-aware
To: pghackers <pgsql-hackers@lists.postgresql.org>,
 David Rowley <dgrowleyml@gmail.com>
Content-Type: text/plain; charset=UTF-8; format=flowed
Content-Transfer-Encoding: 7bit
Archived-At: <https://www.postgresql.org/message-id/444ccfcc-06d6-0160-f662-9fa2075229ad%40gmail.com>
Precedence: bulk

Hi all,

While working on sort optimization for window function, it was seen that 
performance of sort where

all tuples are in memory was bad when number of tuples were very large [1]

Eg: work_mem = 4 GB, sort on 4 int columns on table having 10 million 
tuples.


Issues we saw were as follows:

1. The comparetup function re-compares the first key again in case of 
tie-break.

2. Frequent cache misses


Issue #1 is being looked in separate patch. I am currently looking at #2.

Possible solution was to batch tuples into groups (which can fit into L3 
cache) before pushing them to sort function.

After looking at different papers on this (multi-Quicksort, memory-tuned 
quicksort, Samplesort and various distributed sorts),

although they look promising (especially samplesort), I would like to 
get more inputs as changes look bit too steep and

may or may not be in of scope of solving actual problem in hand.


Please let me know your opinions, do we really need to re-look at 
quicksort for this use-case or we can

perform optimization without major change in core sorting algorithm? Are 
we are open for trying new algorithms for sort?

Any suggestions to narrow down search space for this problem are welcomed.


[1] 
https://www.postgresql.org/message-id/CAApHDvqh+qOHk4sbvvy=Qr2NjPqAAVYf82oXY0g=Z2hRpC2Vmg@mail.gmail.com


Thanks,

Ankit