Re: Can rs_cindex be < 0 for bitmap heap scans? - Mailing list pgsql-hackers

On Fri, Dec 20, 2024 at 7:50 AM Melanie Plageman
<melanieplageman@gmail.com> wrote:
> On Wed, Dec 18, 2024 at 9:50 PM Richard Guo <guofenglinux@gmail.com> wrote:
> > I think this binary search code now has a risk of underflow.  If 'mid'
> > is calculated as zero, the second 'if' branch will cause 'end' to
> > underflow.

> What about this instead:
>
> diff --git a/src/backend/access/heap/heapam_handler.c
> b/src/backend/access/heap/heapam_handler.c
> index 2da4e4da13e..fb90fd869c2 100644
> --- a/src/backend/access/heap/heapam_handler.c
> +++ b/src/backend/access/heap/heapam_handler.c
> @@ -2574,11 +2574,8 @@ SampleHeapTupleVisible(TableScanDesc scan, Buffer buffer,
>
>     if (scan->rs_flags & SO_ALLOW_PAGEMODE)
>     {
> -       uint32      start,
> -                   end;
> -
> -       if (hscan->rs_ntuples == 0)
> -           return false;
> +       uint32      start = 0,
> +                   end = hscan->rs_ntuples;
>
>         /*
>          * In pageatatime mode, heap_prepare_pagescan() already did visibility
> @@ -2589,10 +2586,8 @@ SampleHeapTupleVisible(TableScanDesc scan, Buffer buffer,
>          * in increasing order, but it's not clear that there would be enough
>          * gain to justify the restriction.
>          */
> -       start = 0;
> -       end = hscan->rs_ntuples - 1;
>
> -       while (start <= end)
> +       while (start < end)
>         {
>             uint32      mid = (start + end) / 2;
>             OffsetNumber curoffset = hscan->rs_vistuples[mid];
> @@ -2600,7 +2595,7 @@ SampleHeapTupleVisible(TableScanDesc scan, Buffer buffer,
>             if (tupoffset == curoffset)
>                 return true;
>             else if (tupoffset < curoffset)
> -               end = mid - 1;
> +               end = mid;
>             else
>                 start = mid + 1;
>         }
>
> Or to make it easier to read, here:
>
>         uint32        start = 0,
>               end = hscan->rs_ntuples;
>
>         while (start < end)
>         {
>             uint32        mid = (start + end) / 2;
>             OffsetNumber curoffset = hscan->rs_vistuples[mid];
>
>             if (tupoffset == curoffset)
>                 return true;
>             else if (tupoffset < curoffset)
>                 end = mid;
>             else
>                 start = mid + 1;
>         }
>
> I think this gets rid of any subtraction and is still the same.

Looks correct to me.

BTW, I kind of doubt that the overflow risk fixed in 28328ec87 is a
real issue in real-world scenarios.  Is it realistically possible to
have more than INT_MAX tuples fit on one heap page?

If it is, then the statement below could also be prone to overflow.

    uint32      mid = (start + end) / 2;

Maybe you want to change it to:

    uint32      mid = start + (end - start) / 2;

Thanks
Richard