public inbox for [email protected]  

help / color / mirror / Atom feed

From: Ankit Kumar Pandey <[email protected]>
To: pghackers <[email protected]>
To: David Rowley <[email protected]>
Subject: Sort optimizations: Making in-memory sort cache-aware
Date: Sat, 11 Feb 2023 17:49:02 +0530
Message-ID: <[email protected]> (raw)

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/[email protected]...


Thanks,

Ankit

view thread (2+ messages)

reply

Reply instructions:

You may reply publicly to this message via plain-text email
using any one of the following methods:

* Reply to all the recipients using the --to and --cc options:
  reply via email

  To: [email protected]
  Cc: [email protected], [email protected], [email protected]
  Subject: Re: Sort optimizations: Making in-memory sort cache-aware
  In-Reply-To: <[email protected]>

* Save the following mbox file, import it into your mail client,
  and reply-to-all from there: mbox

This inbox is served by agora; see mirroring instructions
for how to clone and mirror all data and code used for this inbox