Subject: Re: PATCH: Using BRIN indexes for sorted output

From: Tomas Vondra <[email-masked]>
Date: Fri, 24 Feb 2023 17:04:17 +0100

On 2/24/23 16:14, Alvaro Herrera wrote:
> On 2023-Feb-24, Tomas Vondra wrote:
> 
>> I guess the easiest fix would be to do the arithmetic in 64 bits. That'd
>> eliminate the overflow.
> 
> Yeah, that might be easy to set up.  We then don't have to worry about
> it until BlockNumber is enlarged to 64 bits ... but by that time surely
> we can just grow it again to a 128 bit loop variable.
> 
>> Alternatively, we could do something like
>>
>>   prevHeapBlk = 0;
>>   for (heapBlk = 0; (heapBlk < nblocks) && (prevHeapBlk <= heapBlk);
>>        heapBlk += pagesPerRange)
>>   {
>>     ...
>>     prevHeapBlk = heapBlk;
>>   }
> 
> I think a formulation of this kind has the benefit that it works after
> BlockNumber is enlarged to 64 bits, and doesn't have to be changed ever
> again (assuming it is correct).
> 

Did anyone even propose doing that? I suspect this is unlikely to be the
only place that'd might be broken by that.

> ... if pagesPerRange is not a whole divisor of MaxBlockNumber, I think
> this will neglect the last range in the table.
> 

Why would it? Let's say BlockNumber is uint8, i.e. 255 max. And there
are 10 pages per range. That's 25 "full" ranges, and the last range
being just 5 pages. So we get into

   prevHeapBlk = 240
   heapBlk = 250

and we read the last 5 pages. And then we update

   prevHeapBlk = 250
   heapBlk = (250 + 10) % 255 = 5

and we don't do that loop. Or did I get this wrong, somehow?

regards

-- 
Tomas Vondra
EnterpriseDB: http://www.enterprisedb.com
The Enterprise PostgreSQL Company

---

From: Matthias van de Meent <[email-masked]>
Date: Fri, 24 Feb 2023 17:11:21 +0100

> and we don't do that loop. Or did I get this wrong, somehow?

The result is off-by-one due to (u)int8 overflows being mod-256, but
apart from that your result is accurate.

The condition only stops the loop when we wrap around or when we go
past the last block, but no earlier than that.

Kind regards,

Matthias van de Meent

---

From: Alvaro Herrera <[email-masked]>
Date: Wed, 1 Mar 2023 19:33:01 +0100

> only place that'd might be broken by that.

True about other places also needing fixes, and no I haven't see anyone;
but while 32 TB does seem very far away to us now, it might be not
*that* far away.  So I think doing it the other way is better.

> and we don't do that loop. Or did I get this wrong, somehow?

I stand corrected.

-- 
Álvaro Herrera               48°01'N 7°57'E  —  https://www.EnterpriseDB.com/