Message-ID: <79133b5e-5244-4059-1d4a-3748ad4a19bc@enterprisedb.com>
Date: Fri, 14 Jul 2023 17:51:45 +0200
MIME-Version: 1.0
User-Agent: Mozilla/5.0 (X11; Linux x86_64; rv:102.0) Gecko/20100101
 Thunderbird/102.12.0
Subject: Re: PATCH: Using BRIN indexes for sorted output
Content-Language: en-US
To: Matthias van de Meent <boekewurm+postgres@gmail.com>
Cc: Justin Pryzby <pryzby@telsasoft.com>, Andres Freund <andres@anarazel.de>,
 Greg Stark <stark@mit.edu>,
 PostgreSQL Hackers <pgsql-hackers@lists.postgresql.org>
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>
From: Tomas Vondra <tomas.vondra@enterprisedb.com>
In-Reply-To: 
 <CAEze2WhiBeTOnwy8iDVPTb_joZ9-LDR_7DA0xEcZBUeyL_otOw@mail.gmail.com>
Content-Type: text/plain; charset=UTF-8
Content-Transfer-Encoding: 7bit
Archived-At: 
 <https://www.postgresql.org/message-id/79133b5e-5244-4059-1d4a-3748ad4a19bc%40enterprisedb.com>
Precedence: bulk


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