Line data    Source code

       1             : /*-------------------------------------------------------------------------
       2             :  *
       3             :  * tidbitmap.h
       4             :  *    PostgreSQL tuple-id (TID) bitmap package
       5             :  *
       6             :  * This module provides bitmap data structures that are spiritually
       7             :  * similar to Bitmapsets, but are specially adapted to store sets of
       8             :  * tuple identifiers (TIDs), or ItemPointers.  In particular, the division
       9             :  * of an ItemPointer into BlockNumber and OffsetNumber is catered for.
      10             :  * Also, since we wish to be able to store very large tuple sets in
      11             :  * memory with this data structure, we support "lossy" storage, in which
      12             :  * we no longer remember individual tuple offsets on a page but only the
      13             :  * fact that a particular page needs to be visited.
      14             :  *
      15             :  *
      16             :  * Copyright (c) 2003-2025, PostgreSQL Global Development Group
      17             :  *
      18             :  * src/include/nodes/tidbitmap.h
      19             :  *
      20             :  *-------------------------------------------------------------------------
      21             :  */
      22             : #ifndef TIDBITMAP_H
      23             : #define TIDBITMAP_H
      24             : 
      25             : #include "access/htup_details.h"
      26             : #include "storage/itemptr.h"
      27             : #include "utils/dsa.h"
      28             : 
      29             : /*
      30             :  * The maximum number of tuples per page is not large (typically 256 with
      31             :  * 8K pages, or 1024 with 32K pages).  So there's not much point in making
      32             :  * the per-page bitmaps variable size.  We just legislate that the size
      33             :  * is this:
      34             :  */
      35             : #define TBM_MAX_TUPLES_PER_PAGE  MaxHeapTuplesPerPage
      36             : 
      37             : /*
      38             :  * Actual bitmap representation is private to tidbitmap.c.  Callers can
      39             :  * do IsA(x, TIDBitmap) on it, but nothing else.
      40             :  */
      41             : typedef struct TIDBitmap TIDBitmap;
      42             : 
      43             : /* Likewise, TBMPrivateIterator is private */
      44             : typedef struct TBMPrivateIterator TBMPrivateIterator;
      45             : typedef struct TBMSharedIterator TBMSharedIterator;
      46             : 
      47             : /*
      48             :  * Callers with both private and shared implementations can use this unified
      49             :  * API.
      50             :  */
      51             : typedef struct TBMIterator
      52             : {
      53             :     bool        shared;
      54             :     union
      55             :     {
      56             :         TBMPrivateIterator *private_iterator;
      57             :         TBMSharedIterator *shared_iterator;
      58             :     }           i;
      59             : } TBMIterator;
      60             : 
      61             : /* Result structure for tbm_iterate */
      62             : typedef struct TBMIterateResult
      63             : {
      64             :     BlockNumber blockno;        /* block number containing tuples */
      65             : 
      66             :     bool        lossy;
      67             : 
      68             :     /*
      69             :      * Whether or not the tuples should be rechecked. This is always true if
      70             :      * the page is lossy but may also be true if the query requires recheck.
      71             :      */
      72             :     bool        recheck;
      73             : 
      74             :     /*
      75             :      * Pointer to the page containing the bitmap for this block. It is a void *
      76             :      * to avoid exposing the details of the tidbitmap PagetableEntry to API
      77             :      * users.
      78             :      */
      79             :     void       *internal_page;
      80             : } TBMIterateResult;
      81             : 
      82             : /* function prototypes in nodes/tidbitmap.c */
      83             : 
      84             : extern TIDBitmap *tbm_create(Size maxbytes, dsa_area *dsa);
      85             : extern void tbm_free(TIDBitmap *tbm);
      86             : extern void tbm_free_shared_area(dsa_area *dsa, dsa_pointer dp);
      87             : 
      88             : extern void tbm_add_tuples(TIDBitmap *tbm,
      89             :                            const ItemPointer tids, int ntids,
      90             :                            bool recheck);
      91             : extern void tbm_add_page(TIDBitmap *tbm, BlockNumber pageno);
      92             : 
      93             : extern void tbm_union(TIDBitmap *a, const TIDBitmap *b);
      94             : extern void tbm_intersect(TIDBitmap *a, const TIDBitmap *b);
      95             : 
      96             : extern int  tbm_extract_page_tuple(TBMIterateResult *iteritem,
      97             :                                    OffsetNumber *offsets,
      98             :                                    uint32 max_offsets);
      99             : 
     100             : extern bool tbm_is_empty(const TIDBitmap *tbm);
     101             : 
     102             : extern TBMPrivateIterator *tbm_begin_private_iterate(TIDBitmap *tbm);
     103             : extern dsa_pointer tbm_prepare_shared_iterate(TIDBitmap *tbm);
     104             : extern bool tbm_private_iterate(TBMPrivateIterator *iterator, TBMIterateResult *tbmres);
     105             : extern bool tbm_shared_iterate(TBMSharedIterator *iterator, TBMIterateResult *tbmres);
     106             : extern void tbm_end_private_iterate(TBMPrivateIterator *iterator);
     107             : extern void tbm_end_shared_iterate(TBMSharedIterator *iterator);
     108             : extern TBMSharedIterator *tbm_attach_shared_iterate(dsa_area *dsa,
     109             :                                                     dsa_pointer dp);
     110             : extern int  tbm_calculate_entries(Size maxbytes);
     111             : 
     112             : extern TBMIterator tbm_begin_iterate(TIDBitmap *tbm,
     113             :                                      dsa_area *dsa, dsa_pointer dsp);
     114             : extern void tbm_end_iterate(TBMIterator *iterator);
     115             : 
     116             : extern bool tbm_iterate(TBMIterator *iterator, TBMIterateResult *tbmres);
     117             : 
     118             : static inline bool
     119       21010 : tbm_exhausted(TBMIterator *iterator)
     120             : {
     121             :     /*
     122             :      * It doesn't matter if we check the private or shared iterator here. If
     123             :      * tbm_end_iterate() was called, they will be NULL
     124             :      */
     125       21010 :     return !iterator->i.private_iterator;
     126             : }
     127             : 
     128             : #endif                          /* TIDBITMAP_H */