From: Tomas Vondra <tomas.vondra@enterprisedb.com>
To: Matthias van de Meent <boekewurm+postgres@gmail.com>
Cc: Justin Pryzby <pryzby@telsasoft.com>
Cc: Andres Freund <andres@anarazel.de>
Cc: Greg Stark <stark@mit.edu>
Cc: PostgreSQL Hackers <pgsql-hackers@lists.postgresql.org>
Subject: Re: PATCH: Using BRIN indexes for sorted output
Date: Fri, 14 Jul 2023 17:51:45 +0200
Message-ID: <79133b5e-5244-4059-1d4a-3748ad4a19bc@enterprisedb.com> (raw)
In-Reply-To: <CAEze2WhiBeTOnwy8iDVPTb_joZ9-LDR_7DA0xEcZBUeyL_otOw@mail.gmail.com>
References: <1607e037-8c5b-1626-9f98-496f067b9eb5@enterprisedb.com>
<CAEze2Whd=MCQ61EEUUWJgohHN5cm3bv027N+vS4o6zOuBTY3tw@mail.gmail.com>
<30f37aae-57fa-e7ab-9444-7b82969ed68f@enterprisedb.com>
<CAEze2WgGueCY+ihQDASaKAWNG9C2Ex0vzoNU5inrMLwWyj3KMA@mail.gmail.com>
<CAEze2Wh5VsGQUyg9FC+xZBLUPLZnm0pOym5uceOM0aG1YnuESA@mail.gmail.com>
<825f648f-2a31-1870-942f-03fba2b6b3cf@enterprisedb.com>
<CAEze2WjWaP+vNC9Y_y0vVAWiX9NF7VtXDtY8+cCd27TQiCSsTg@mail.gmail.com>
<0c331bf8-0cd3-e9fe-ae81-9e3d68f1f95c@enterprisedb.com>
<CAEze2Wj_UjWdpMfDSpYWXFnr2K2yX9zpihsD4iEZ9+JFMLOknw@mail.gmail.com>
<1992ff4f-bf0e-3ad0-a859-cf054f6abc74@enterprisedb.com>
<CAEze2WjOrBXbMEM-xq8OOPJquNdrTn-t6qX1G7FzBfn9nY_a6w@mail.gmail.com>
<5c92f99a-e83e-c1b3-2c47-d75857a70b73@enterprisedb.com>
<CAEze2Wg00Pry5KsNEqJps-uX+T6f=YTm-jyLZPt=yDNO5+3v0Q@mail.gmail.com>
<065bb749-71ee-6bd2-7a4b-1088cb26a31a@enterprisedb.com>
<CAEze2WhiBeTOnwy8iDVPTb_joZ9-LDR_7DA0xEcZBUeyL_otOw@mail.gmail.com>
On 7/14/23 16:42, Matthias van de Meent wrote:
> On Fri, 14 Jul 2023 at 16:21, Tomas Vondra
> <tomas.vondra@enterprisedb.com> wrote:
>>
>>
>>
>>
>> On 7/11/23 13:20, Matthias van de Meent wrote:
>>> On Mon, 10 Jul 2023 at 22:04, Tomas Vondra
>>> <tomas.vondra@enterprisedb.com> wrote:
>>>> Approximation in what sense? My understanding was we'd get a range of
>>>> distances that we know covers all rows in that range. So the results
>>>> should be accurate, no?
>>>
>>> The distance is going to be accurate only to the degree that the
>>> summary can produce accurate distances for the datapoints it
>>> represents. That can be quite imprecise due to the nature of the
>>> contained datapoints: a summary of the points (-1, -1) and (1, 1) will
>>> have a minimum distance of 0 to the origin, where the summary (-1, 0)
>>> and (-1, 0.5) would have a much more accurate distance of 1.
>>
>> Ummm, I'm probably missing something, or maybe my mental model of this
>> is just wrong, but why would the distance for the second summary be more
>> accurate? Or what does "more accurate" mean?
>>
>> Is that about the range of distances for the summary? For the first
>> range the summary is a bounding box [(-1,1), (1,1)] so all we know the
>> points may have distance in range [0, sqrt(2)]. While for the second
>> summary it's [1, sqrt(1.25)].
>
> Yes; I was trying to refer to the difference between what results you
> get from the summary vs what results you get from the actual
> datapoints: In this case, for finding points which are closest to the
> origin, the first bounding box has a less accurate estimate than the
> second.
>
OK. I think regular minmax indexes have a similar issue with
non-distance ordering, because we don't know if the min/max values are
still in the page range (or deleted/updated).
>>> The point I was making is that the summary can only approximate the
>>> distance, and that approximation is fine w.r.t. the BRIN sort
>>> algoritm.
>>>
>>
>> I think as long as the approximation (whatever it means) does not cause
>> differences in results (compared to not using an index), it's OK.
>
I haven't written any code yet, but I think if we don't try to find the
exact min/max distances for the summary (e.g. by calculating the closest
point exactly) but rather "estimates" that are guaranteed to bound the
actual min/max, that's good enough for the sorting.
For the max, this probably is not an issue, as we can just calculate
distance for the corners and use a maximum of that. At least with
reasonable euclidean distance ... in 2D I'm imagining the bounding box
summary as a rectangle, with the "max distance" being a minimum radius
of a circle containing it (the rectangle).
For min we're looking for the largest radius not intersecting with the
box, which seems harder to calculate I think.
However, now that I'm thinking about it - don't (SP-)GiST indexes
already do pretty much exactly this?
regards
--
Tomas Vondra
EnterpriseDB: http://www.enterprisedb.com
The Enterprise PostgreSQL Company
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: tomas.vondra@enterprisedb.com, boekewurm+postgres@gmail.com, pryzby@telsasoft.com, andres@anarazel.de, stark@mit.edu, pgsql-hackers@lists.postgresql.org
Subject: Re: PATCH: Using BRIN indexes for sorted output
In-Reply-To: <79133b5e-5244-4059-1d4a-3748ad4a19bc@enterprisedb.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