| 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 |
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 |
return !iterator->i.private_iterator; |
| 126 |
} |
| 127 |
|
| 128 |
#endif /* TIDBITMAP_H */ |