Date: Tue, 27 Sep 2022 11:39:31 +0200
Subject: Re: Insertion Sort Improvements
From: Benjamin Coutu <ben.coutu@zeyos.com>
To: John Naylor <john.naylor@enterprisedb.com>
Cc: pgsql-hackers <pgsql-hackers@postgresql.org>
Message-ID: <6047084d3cc4d8cf4ef7@zeyos.com>
In-Reply-To: 
 <CAFBsxsFKs46nskQc4dt2XxDhtNA86NR=fOXXeg2Kf=6D_ej0CA@mail.gmail.com>
References: 
 <CAFBsxsFKs46nskQc4dt2XxDhtNA86NR=fOXXeg2Kf=6D_ej0CA@mail.gmail.com>
MIME-Version: 1.0
Content-Type: text/plain;
	charset="UTF-8"
Content-Transfer-Encoding: quoted-printable
Archived-At: 
 <https://www.postgresql.org/message-id/6047084d3cc4d8cf4ef7%40zeyos.com>
Precedence: bulk

Getting back to improvements for small sort runs, it might make sense to co=
nsider using in-register based sorting via sorting networks for very small =
runs.=0A=0AThis talk is specific to database sorting and illustrates how su=
ch an approach can be vectorized: https://youtu.be/HeFwVNHsDzc?list=3DPLSE8=
ODhjZXjasmrEd2_Yi1deeE360zv5O&t=3D1090=0A=0AIt looks like some of the comme=
rcial 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 p=
roject now readily supports thanks to your recent efforts?