MIME-Version: 1.0
References: <CAApHDvoTTtoQYfp3d0kTPF6y1pjexgLwquzKmjzvjC9NCw4RGw@mail.gmail.com>
 <CAFBsxsEBH7Jx+butn1SO2KXHOOfMwHPiK4skRupxOUUULOJMdw@mail.gmail.com>
 <CAApHDvrPzb0RFZJN8HD7oEazF6L6ZTAWdtnBmTQwdtZiYv2pCg@mail.gmail.com> <CAFBsxsH9bQ+wXJc_C4KiRR7FQ8Fbz=N5fHCjbRWmaW=v+nQJaw@mail.gmail.com>
In-Reply-To: <CAFBsxsH9bQ+wXJc_C4KiRR7FQ8Fbz=N5fHCjbRWmaW=v+nQJaw@mail.gmail.com>
From: John Naylor <john.naylor@enterprisedb.com>
Date: Thu, 26 Jan 2023 17:29:25 +0700
Message-ID: <CAFBsxsH=3UA+8Sp2sgUs=piYOmR2CQ-Rq5sUhCX-M3Gqv4TRog@mail.gmail.com>
Subject: Re: Considering additional sort specialisation functions for PG16
To: David Rowley <dgrowleyml@gmail.com>
Cc: PostgreSQL Developers <pgsql-hackers@lists.postgresql.org>, 
	Thomas Munro <thomas.munro@gmail.com>
Content-Type: multipart/alternative; boundary="000000000000c1656905f3283967"
Archived-At: <https://www.postgresql.org/message-id/CAFBsxsH%3D3UA%2B8Sp2sgUs%3DpiYOmR2CQ-Rq5sUhCX-M3Gqv4TRog%40mail.gmail.com>
Precedence: bulk

--000000000000c1656905f3283967
Content-Type: text/plain; charset="UTF-8"

On Tue, Aug 23, 2022 at 1:13 PM John Naylor <john.naylor@enterprisedb.com>
wrote:
>
> On Tue, Aug 23, 2022 at 11:24 AM David Rowley <dgrowleyml@gmail.com>
wrote:
> >
> > On Tue, 23 Aug 2022 at 15:22, John Naylor <john.naylor@enterprisedb.com>
wrote:
> > > Did you happen to see
> > >
> > >
https://www.postgresql.org/message-id/CAFBsxsFhq8VUSkUL5YO17cFXbCPwtbbxBu%2Bd9MFrrsssfDXm3Q%40mail.gmail.com
> >
> > I missed that.  It looks like a much more promising idea than what I
> > came up with. I've not looked at your code yet, but I'm interested and
> > will aim to look soon.
>
> Note that I haven't actually implemented this idea yet, just tried to
> model the effects by lobotomizing the current comparators. I think
> it's worth pursuing and will try to come back to it this cycle, but if
> you or anyone else wants to try, that's fine of course.

Coming back to this, I wanted to sketch out this idea in a bit more detail.

Have two memtuple arrays, one for first sortkey null and one for first
sortkey non-null:
- Qsort the non-null array, including whatever specialization is available.
Existing specialized comparators could ignore nulls (and their ordering)
taking less space in the binary.
- Only if there is more than one sort key, qsort the null array. Ideally at
some point we would have a method of ignoring the first sortkey (this is an
existing opportunity that applies elsewhere as well).
- To handle two arrays, grow_memtuples() would need some adjustment, as
would any callers that read the final result of an in-memory sort -- they
would need to retrieve the tuples starting with the appropriate array
depending on NULLS FIRST/LAST behavior.

I believe external merges wouldn't have to do anything different, since
when writing out the tapes, we read from the arrays in the right order.

(One could extend this idea further and have two pools of tapes for null
and non-null first sortkey, that are merged separately, in the right order.
That sounds like quite a bit more complexity than is worth, however.)

--
John Naylor
EDB: http://www.enterprisedb.com

--000000000000c1656905f3283967
Content-Type: text/html; charset="UTF-8"
Content-Transfer-Encoding: quoted-printable

<div dir=3D"ltr"><div dir=3D"ltr"><br>On Tue, Aug 23, 2022 at 1:13 PM John =
Naylor &lt;<a href=3D"mailto:john.naylor@enterprisedb.com">john.naylor@ente=
rprisedb.com</a>&gt; wrote:<br>&gt;<br>&gt; On Tue, Aug 23, 2022 at 11:24 A=
M David Rowley &lt;<a href=3D"mailto:dgrowleyml@gmail.com">dgrowleyml@gmail=
.com</a>&gt; wrote:<br>&gt; &gt;<br>&gt; &gt; On Tue, 23 Aug 2022 at 15:22,=
 John Naylor &lt;<a href=3D"mailto:john.naylor@enterprisedb.com">john.naylo=
r@enterprisedb.com</a>&gt; wrote:<br>&gt; &gt; &gt; Did you happen to see<b=
r>&gt; &gt; &gt;<br>&gt; &gt; &gt; <a href=3D"https://www.postgresql.org/me=
ssage-id/CAFBsxsFhq8VUSkUL5YO17cFXbCPwtbbxBu%2Bd9MFrrsssfDXm3Q%40mail.gmail=
.com">https://www.postgresql.org/message-id/CAFBsxsFhq8VUSkUL5YO17cFXbCPwtb=
bxBu%2Bd9MFrrsssfDXm3Q%40mail.gmail.com</a><br>&gt; &gt;<br>&gt; &gt; I mis=
sed that.=C2=A0 It looks like a much more promising idea than what I<br>&gt=
; &gt; came up with. I&#39;ve not looked at your code yet, but I&#39;m inte=
rested and<br>&gt; &gt; will aim to look soon.<br>&gt;<br>&gt; Note that I =
haven&#39;t actually implemented this idea yet, just tried to<br>&gt; model=
 the effects by lobotomizing the current comparators. I think<br>&gt; it=
9;s worth pursuing and will try to come back to it this cycle, but if<br>&g=
t; you or anyone else wants to try, that&#39;s fine of course.<br><br>Comin=
g back to this, I wanted to sketch out this idea in=C2=A0a bit more detail.=
<br><br>Have two memtuple arrays, one for first sortkey null and one for fi=
rst sortkey non-null:<br>- Qsort the non-null array, including whatever spe=
cialization is available. Existing specialized comparators could ignore nul=
ls (and their ordering) taking less space in the binary.<br>- Only if there=
 is more than one sort key, qsort the null array. Ideally at some point we =
would have a method of ignoring the first sortkey (this is an existing oppo=
rtunity that applies elsewhere as well).<br>- To handle two arrays, grow_me=
mtuples() would need some adjustment, as would any callers that read the fi=
nal result of an in-memory sort -- they would need to retrieve the tuples s=
tarting with the appropriate array depending on NULLS FIRST/LAST behavior.<=
br><br>I believe external merges wouldn&#39;t have to do anything different=
, since when writing out the tapes, we read from the arrays in the right or=
der.</div><div dir=3D"ltr"><br></div><div dir=3D"ltr">(One could extend thi=
s idea further and have two pools of tapes for null and non-null first sort=
key, that are merged separately, in the right order. That sounds like quite=
 a bit more complexity than is worth, however.)<br><br></div><div dir=3D"lt=
r">--<br>John Naylor<br>EDB: <a href=3D"http://www.enterprisedb.com" target=
=3D"_blank">http://www.enterprisedb.com</a></div>
</div>

--000000000000c1656905f3283967--