Date: Fri, 26 Aug 2022 16:06:16 +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: <ac56d6b6bb4d3a6f65b5@zeyos.com>
In-Reply-To: 
 <CAFBsxsHPrvpqfNpHHC6R9fTe_us=AJ4_REWdUO9NuHcwPFF1tA@mail.gmail.com>
References: 
 <CAFBsxsHPrvpqfNpHHC6R9fTe_us=AJ4_REWdUO9NuHcwPFF1tA@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/ac56d6b6bb4d3a6f65b5%40zeyos.com>
Precedence: bulk

> convenient if you know the type at compile time. See the attached,
> which I had laying around when I was looking at PDQuicksort. I believe
> it's similar to what you have in mind.=0A=0AThat looks very promising.=0A=
I also love your recent proposal of partitioning into null and non-null. I =
suspect that to be a clear winner.=0A
> I think it belongs around 10 now anyway.=0A=0AYeah, I think that change i=
s overdue given modern hardware characteristics (even with the current impl=
ementation).=0A=0AAnother idea could be to run a binary insertion sort and =
use a much higher threshold. This could significantly cut down on compariso=
ns (especially with presorted runs, which are quite common in real workload=
s).=0A=0AIf full binary search turned out to be an issue regarding cache lo=
cality, we could do it in smaller chunks, e.g. do a micro binary search bet=
ween the current position (I) and position minus chunk size (say 6-12 or so=
, whatever fits 1 or 2 cachelines) whenever A[I] < A[I-1] and if we don't f=
ind the position within that chunk we continue with the previous chunk, the=
reby preserving cache locality.=0A=0AWith less comparisons we should start =
keeping track of swaps and use that as an efficient way to determine presor=
tedness. We could change the insertion sort threshold to a swap threshold a=
nd do insertion sort until we hit the swap threshold. I suspect that would =
make the current presorted check obsolete (as binary insertion sort without=
 or even with a few swaps should be faster than the current presorted-check=
).=0A=0ACheers, Ben