From: Benjamin Coutu <ben.coutu@zeyos.com>
To: John Naylor <john.naylor@enterprisedb.com>
Cc: pgsql-hackers <pgsql-hackers@postgresql.org>
Subject: Re: Insertion Sort Improvements
Date: Tue, 27 Sep 2022 11:39:31 +0200
Message-ID: <6047084d3cc4d8cf4ef7@zeyos.com> (raw)
In-Reply-To: <CAFBsxsFKs46nskQc4dt2XxDhtNA86NR=fOXXeg2Kf=6D_ej0CA@mail.gmail.com>
References: <CAFBsxsFKs46nskQc4dt2XxDhtNA86NR=fOXXeg2Kf=6D_ej0CA@mail.gmail.com>
Getting back to improvements for small sort runs, it might make sense to consider using in-register based sorting via sorting networks for very small runs.
This talk is specific to database sorting and illustrates how such an approach can be vectorized: https://youtu.be/HeFwVNHsDzc?list=PLSE8ODhjZXjasmrEd2_Yi1deeE360zv5O&t=1090
It looks like some of the commercial DBMSs do this very successfully. They use 4 512bit registers (AVX-512) in this example, which could technically store 4 * 4 sort-elements (given that the sorting key is 64 bit and the tuple pointer is 64 bit). I wonder whether this could also be done with just SSE (instead of AVX), which the project now readily supports thanks to your recent efforts?
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: pgsql-hackers@postgresql.org
Cc: ben.coutu@zeyos.com, john.naylor@enterprisedb.com
Subject: Re: Insertion Sort Improvements
In-Reply-To: <6047084d3cc4d8cf4ef7@zeyos.com>
* Save the following mbox file, import it into your mail client,
and reply-to-all from there: mbox
This inbox is served by DDX for PostgreSQL; see mirroring instructions
for how to clone and mirror all data and code used for this inbox