Date: Wed, 28 Sep 2022 09:04: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: <c4a2e53116648187ce0f@zeyos.com>
In-Reply-To: 
 <CAFBsxsFs5=0yHx+-03EYkf+Y_s0evkgDYstUXFeQvogTi7dSig@mail.gmail.com>
References: 
 <CAFBsxsFs5=0yHx+-03EYkf+Y_s0evkgDYstUXFeQvogTi7dSig@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/c4a2e53116648187ce0f%40zeyos.com>
Precedence: bulk

> "Looks like"?=0A=0AI cannot find the reference, but I've read a while bac=
k that a well-known company from Redwood uses it for their in-memory column=
ar storage. That might have just been a rumor or might have been research o=
nly - not sure. It does not really matter anyways.=0A=0A> SortTuples are cu=
rrently 24 bytes, and supported vector registers are 16 bytes, so not sure =
how you think that would work.=0A=0AThe thought was to logically group mult=
iple sort tuples together and then create a vectorized version of that grou=
p with just the primitive type sort key as well as a small-sized index/offs=
et into that sort group to later swap the corresponding sort tuple referenc=
ed by that index/offset. The sorting network would allow us to do branch-le=
ss register based sorting for a particular sort run. I guess this idea is m=
oot, given ...=0A=0A> More broadly, the more invasive a change=C2=A0is, the=
 more risk is involved,=C2=A0and the more effort to test and evaluate. If y=
ou're serious about trying to improve insertion sort performance, the simpl=
e idea we discussed at the start of the thread is a much=C2=A0more modest s=
tep that=C2=A0has a good chance of justifying the time put into it. That is=
 not to say it's easy, however, because testing is a non-trivial amount of =
work.=0A=0AI absolutely agree. Let's concentrate on improving things increm=
entally.=0APlease excuse me wondering given that you have contributed some =
of the recent vectorization stuff and seeing that you have obviously experi=
mented a lot with the sort code, that you might already have tried somethin=
g along those lines or researched the subject - it is definitely a very int=
eresting topic.=0A=0ACheers, Ben