ginbulk.c

/*-------------------------------------------------------------------------
 *
 * ginbulk.c
 *   routines for fast build of inverted index
 *
 *
 * Portions Copyright (c) 1996-2025, PostgreSQL Global Development Group
 * Portions Copyright (c) 1994, Regents of the University of California
 *
 * IDENTIFICATION
 *   src/backend/access/gin/ginbulk.c
 *-------------------------------------------------------------------------
 */

#include "postgres.h"

#include <limits.h>

#include "access/gin_private.h"
#include "utils/datum.h"
#include "utils/memutils.h"


#define DEF_NENTRY 2048  /* GinEntryAccumulator allocation quantum */
#define DEF_NPTR 5   /* ItemPointer initial allocation quantum */


/* Combiner function for rbtree.c */
static void
ginCombineData(RBTNode *existing, const RBTNode *newdata, void *arg)
{
 GinEntryAccumulator *eo = (GinEntryAccumulator *) existing;
 const GinEntryAccumulator *en = (const GinEntryAccumulator *) newdata;
 BuildAccumulator *accum = (BuildAccumulator *) arg;

 /*
  * Note this code assumes that newdata contains only one itempointer.
 */
 if (eo->count >= eo->maxcount)
 {
  if (eo->maxcount > INT_MAX)
   ereport(ERROR,
     (errcode(ERRCODE_PROGRAM_LIMIT_EXCEEDED),
      errmsg("posting list is too long"),
      errhint("Reduce \"maintenance_work_mem\".")));

  accum->allocatedMemory -= GetMemoryChunkSpace(eo->list);
  eo->maxcount *= 2;
  eo->list = (ItemPointerData *)
   repalloc_huge(eo->list, sizeof(ItemPointerData) * eo->maxcount);
  accum->allocatedMemory += GetMemoryChunkSpace(eo->list);
 }

 /* If item pointers are not ordered, they will need to be sorted later */
 if (eo->shouldSort == false)
 {
  int   res;

  res = ginCompareItemPointers(eo->list + eo->count - 1, en->list);
  Assert(res != 0);

  if (res > 0)
   eo->shouldSort = true;
 }

 eo->list[eo->count] = en->list[0];
 eo->count++;
}

/* Comparator function for rbtree.c */
static int
cmpEntryAccumulator(const RBTNode *a, const RBTNode *b, void *arg)
{
 const GinEntryAccumulator *ea = (const GinEntryAccumulator *) a;
 const GinEntryAccumulator *eb = (const GinEntryAccumulator *) b;
 BuildAccumulator *accum = (BuildAccumulator *) arg;

 return ginCompareAttEntries(accum->ginstate,
        ea->attnum, ea->key, ea->category,
        eb->attnum, eb->key, eb->category);
}

/* Allocator function for rbtree.c */
static RBTNode *
ginAllocEntryAccumulator(void *arg)
{
 BuildAccumulator *accum = (BuildAccumulator *) arg;
 GinEntryAccumulator *ea;

 /*
  * Allocate memory by rather big chunks to decrease overhead.  We have no
  * need to reclaim RBTNodes individually, so this costs nothing.
 */
 if (accum->entryallocator == NULL || accum->eas_used >= DEF_NENTRY)
 {
  accum->entryallocator = palloc(sizeof(GinEntryAccumulator) * DEF_NENTRY);
  accum->allocatedMemory += GetMemoryChunkSpace(accum->entryallocator);
  accum->eas_used = 0;
 }

 /* Allocate new RBTNode from current chunk */
 ea = accum->entryallocator + accum->eas_used;
 accum->eas_used++;

 return (RBTNode *) ea;
}

void
ginInitBA(BuildAccumulator *accum)
{
 /* accum->ginstate is intentionally not set here */
 accum->allocatedMemory = 0;
 accum->entryallocator = NULL;
 accum->eas_used = 0;
 accum->tree = rbt_create(sizeof(GinEntryAccumulator),
        cmpEntryAccumulator,
        ginCombineData,
        ginAllocEntryAccumulator,
        NULL, /* no freefunc needed */
        accum);
}

/*
 * This is basically the same as datumCopy(), but extended to count
 * palloc'd space in accum->allocatedMemory.
 */
static Datum
getDatumCopy(BuildAccumulator *accum, OffsetNumber attnum, Datum value)
{
 CompactAttribute *att;
 Datum  res;

 att = TupleDescCompactAttr(accum->ginstate->origTupdesc, attnum - 1);
 if (att->attbyval)
  res = value;
 else
 {
  res = datumCopy(value, false, att->attlen);
  accum->allocatedMemory += GetMemoryChunkSpace(DatumGetPointer(res));
 }
 return res;
}

/*
 * Find/store one entry from indexed value.
 */
static void
ginInsertBAEntry(BuildAccumulator *accum,
     ItemPointer heapptr, OffsetNumber attnum,
     Datum key, GinNullCategory category)
{
 GinEntryAccumulator eatmp;
 GinEntryAccumulator *ea;
 bool  isNew;

 /*
  * For the moment, fill only the fields of eatmp that will be looked at by
  * cmpEntryAccumulator or ginCombineData.
 */
 eatmp.attnum = attnum;
 eatmp.key = key;
 eatmp.category = category;
 /* temporarily set up single-entry itempointer list */
 eatmp.list = heapptr;

 ea = (GinEntryAccumulator *) rbt_insert(accum->tree, (RBTNode *) &eatmp,
           &isNew);

 if (isNew)
 {
  /*
   * Finish initializing new tree entry, including making permanent
   * copies of the datum (if it's not null) and itempointer.
 */
  if (category == GIN_CAT_NORM_KEY)
   ea->key = getDatumCopy(accum, attnum, key);
  ea->maxcount = DEF_NPTR;
  ea->count = 1;
  ea->shouldSort = false;
  ea->list =
   (ItemPointerData *) palloc(sizeof(ItemPointerData) * DEF_NPTR);
  ea->list[0] = *heapptr;
  accum->allocatedMemory += GetMemoryChunkSpace(ea->list);
 }
 else
 {
  /*
   * ginCombineData did everything needed.
 */
 }
}

/*
 * Insert the entries for one heap pointer.
 *
 * Since the entries are being inserted into a balanced binary tree, you
 * might think that the order of insertion wouldn't be critical, but it turns
 * out that inserting the entries in sorted order results in a lot of
 * rebalancing operations and is slow.  To prevent this, we attempt to insert
 * the nodes in an order that will produce a nearly-balanced tree if the input
 * is in fact sorted.
 *
 * We do this as follows.  First, we imagine that we have an array whose size
 * is the smallest power of two greater than or equal to the actual array
 * size.  Second, we insert the middle entry of our virtual array into the
 * tree; then, we insert the middles of each half of our virtual array, then
 * middles of quarters, etc.
 */
void
ginInsertBAEntries(BuildAccumulator *accum,
       ItemPointer heapptr, OffsetNumber attnum,
       Datum *entries, GinNullCategory *categories,
       int32 nentries)
{
 uint32  step = nentries;

 if (nentries <= 0)
  return;

 Assert(ItemPointerIsValid(heapptr) && attnum >= FirstOffsetNumber);

 /*
  * step will contain largest power of 2 and <= nentries
 */
 step |= (step >> 1);
 step |= (step >> 2);
 step |= (step >> 4);
 step |= (step >> 8);
 step |= (step >> 16);
 step >>= 1;
 step++;

 while (step > 0)
 {
  int   i;

  for (i = step - 1; i < nentries && i >= 0; i += step << 1 /* *2 */ )
   ginInsertBAEntry(accum, heapptr, attnum,
        entries[i], categories[i]);

  step >>= 1;    /* /2 */
 }
}

static int
qsortCompareItemPointers(const void *a, const void *b)
{
 int   res = ginCompareItemPointers((ItemPointer) a, (ItemPointer) b);

 /* Assert that there are no equal item pointers being sorted */
 Assert(res != 0);
 return res;
}

/* Prepare to read out the rbtree contents using ginGetBAEntry */
void
ginBeginBAScan(BuildAccumulator *accum)
{
 rbt_begin_iterate(accum->tree, LeftRightWalk, &accum->tree_walk);
}

/*
 * Get the next entry in sequence from the BuildAccumulator's rbtree.
 * This consists of a single key datum and a list (array) of one or more
 * heap TIDs in which that key is found.  The list is guaranteed sorted.
 */
ItemPointerData *
ginGetBAEntry(BuildAccumulator *accum,
     OffsetNumber *attnum, Datum *key, GinNullCategory *category,
     uint32 *n)
{
 GinEntryAccumulator *entry;
 ItemPointerData *list;

 entry = (GinEntryAccumulator *) rbt_iterate(&accum->tree_walk);

 if (entry == NULL)
  return NULL;   /* no more entries */

 *attnum = entry->attnum;
 *key = entry->key;
 *category = entry->category;
 list = entry->list;
 *n = entry->count;

 Assert(list != NULL && entry->count > 0);

 if (entry->shouldSort && entry->count > 1)
  qsort(list, entry->count, sizeof(ItemPointerData),
     qsortCompareItemPointers);

 return list;
}