/*-------------------------------------------------------------------------

 *

 * nodeBitmapHeapscan.c

 *    Routines to support bitmapped scans of relations

 *

 * NOTE: it is critical that this plan type only be used with MVCC-compliant

 * snapshots (ie, regular snapshots, not SnapshotAny or one of the other

 * special snapshots).  The reason is that since index and heap scans are

 * decoupled, there can be no assurance that the index tuple prompting a

 * visit to a particular heap TID still exists when the visit is made.

 * Therefore the tuple might not exist anymore either (which is OK because

 * heap_fetch will cope) --- but worse, the tuple slot could have been

 * re-used for a newer tuple.  With an MVCC snapshot the newer tuple is

 * certain to fail the time qual and so it will not be mistakenly returned,

 * but with anything else we might return a tuple that doesn't meet the

 * required index qual conditions.

 *

 *

 * Portions Copyright (c) 1996-2025, PostgreSQL Global Development Group

 * Portions Copyright (c) 1994, Regents of the University of California

 *

 *

 * IDENTIFICATION

 *    src/backend/executor/nodeBitmapHeapscan.c

 *

 *-------------------------------------------------------------------------

 */

/*

 * INTERFACE ROUTINES

 *    ExecBitmapHeapScan      scans a relation using bitmap info

 *    ExecBitmapHeapNext      workhorse for above

 *    ExecInitBitmapHeapScan    creates and initializes state info.

 *    ExecReScanBitmapHeapScan  prepares to rescan the plan.

 *    ExecEndBitmapHeapScan   releases all storage.

 */

#include "postgres.h"

#include <math.h>

#include "access/relscan.h"

#include "access/tableam.h"

#include "access/visibilitymap.h"

#include "executor/executor.h"

#include "executor/nodeBitmapHeapscan.h"

#include "miscadmin.h"

#include "pgstat.h"

#include "storage/bufmgr.h"

#include "utils/rel.h"

#include "utils/spccache.h"

static void BitmapTableScanSetup(BitmapHeapScanState *node);

static TupleTableSlot *BitmapHeapNext(BitmapHeapScanState *node);

static inline void BitmapDoneInitializingSharedState(ParallelBitmapHeapState *pstate);

static bool BitmapShouldInitializeSharedState(ParallelBitmapHeapState *pstate);

/*

 * Do the underlying index scan, build the bitmap, set up the parallel state

 * needed for parallel workers to iterate through the bitmap, and set up the

 * underlying table scan descriptor.

 */

static void

BitmapTableScanSetup(BitmapHeapScanState *node)

{

  TBMIterator tbmiterator = {0};

  ParallelBitmapHeapState *pstate = node->pstate;

  dsa_area   *dsa = node->ss.ps.state->es_query_dsa;

  if (!pstate)

  {

    node->tbm = (TIDBitmap *) MultiExecProcNode(outerPlanState(node));

    if (!node->tbm || !IsA(node->tbm, TIDBitmap))

      elog(ERROR, "unrecognized result from subplan");

  }

  else if (BitmapShouldInitializeSharedState(pstate))

  {

    /*

     * The leader will immediately come out of the function, but others

     * will be blocked until leader populates the TBM and wakes them up.

     */

    node->tbm = (TIDBitmap *) MultiExecProcNode(outerPlanState(node));

    if (!node->tbm || !IsA(node->tbm, TIDBitmap))

      elog(ERROR, "unrecognized result from subplan");

    /*

     * Prepare to iterate over the TBM. This will return the dsa_pointer

     * of the iterator state which will be used by multiple processes to

     * iterate jointly.

     */

    pstate->tbmiterator = tbm_prepare_shared_iterate(node->tbm);

    /* We have initialized the shared state so wake up others. */

    BitmapDoneInitializingSharedState(pstate);

  }

  tbmiterator = tbm_begin_iterate(node->tbm, dsa,

                  pstate ?

                  pstate->tbmiterator :

                  InvalidDsaPointer);

  /*

   * If this is the first scan of the underlying table, create the table

   * scan descriptor and begin the scan.

   */

  if (!node->ss.ss_currentScanDesc)

  {

    node->ss.ss_currentScanDesc =

      table_beginscan_bm(node->ss.ss_currentRelation,

                 node->ss.ps.state->es_snapshot,

                 0,

                 NULL);

  }

  node->ss.ss_currentScanDesc->st.rs_tbmiterator = tbmiterator;

  node->initialized = true;

}

/* ----------------------------------------------------------------

 *    BitmapHeapNext

 *

 *    Retrieve next tuple from the BitmapHeapScan node's currentRelation

 * ----------------------------------------------------------------

 */

static TupleTableSlot *

BitmapHeapNext(BitmapHeapScanState *node)

{

  ExprContext *econtext = node->ss.ps.ps_ExprContext;

  TupleTableSlot *slot = node->ss.ss_ScanTupleSlot;

  /*

   * If we haven't yet performed the underlying index scan, do it, and begin

   * the iteration over the bitmap.

   */

  if (!node->initialized)

    BitmapTableScanSetup(node);

  while (table_scan_bitmap_next_tuple(node->ss.ss_currentScanDesc,

                    slot, &node->recheck,

                    &node->stats.lossy_pages,

                    &node->stats.exact_pages))

  {

    /*

     * Continuing in previously obtained page.

     */

    CHECK_FOR_INTERRUPTS();

    /*

     * If we are using lossy info, we have to recheck the qual conditions

     * at every tuple.

     */

    if (node->recheck)

    {

      econtext->ecxt_scantuple = slot;

      if (!ExecQualAndReset(node->bitmapqualorig, econtext))

      {

        /* Fails recheck, so drop it and loop back for another */

        InstrCountFiltered2(node, 1);

        ExecClearTuple(slot);

        continue;

      }

    }

    /* OK to return this tuple */

    return slot;

  }

  /*

   * if we get here it means we are at the end of the scan..

   */

  return ExecClearTuple(slot);

}

/*

 *  BitmapDoneInitializingSharedState - Shared state is initialized

 *

 *  By this time the leader has already populated the TBM and initialized the

 *  shared state so wake up other processes.

 */

static inline void

BitmapDoneInitializingSharedState(ParallelBitmapHeapState *pstate)

{

  SpinLockAcquire(&pstate->mutex);

  pstate->state = BM_FINISHED;

  SpinLockRelease(&pstate->mutex);

  ConditionVariableBroadcast(&pstate->cv);

}

/*

 * BitmapHeapRecheck -- access method routine to recheck a tuple in EvalPlanQual

 */

static bool

BitmapHeapRecheck(BitmapHeapScanState *node, TupleTableSlot *slot)

{

  ExprContext *econtext;

  /*

   * extract necessary information from index scan node

   */

  econtext = node->ss.ps.ps_ExprContext;

  /* Does the tuple meet the original qual conditions? */

  econtext->ecxt_scantuple = slot;

  return ExecQualAndReset(node->bitmapqualorig, econtext);

}

/* ----------------------------------------------------------------

 *    ExecBitmapHeapScan(node)

 * ----------------------------------------------------------------

 */

static TupleTableSlot *

ExecBitmapHeapScan(PlanState *pstate)

{

  BitmapHeapScanState *node = castNode(BitmapHeapScanState, pstate);

  return ExecScan(&node->ss,

          (ExecScanAccessMtd) BitmapHeapNext,

          (ExecScanRecheckMtd) BitmapHeapRecheck);

}

/* ----------------------------------------------------------------

 *    ExecReScanBitmapHeapScan(node)

 * ----------------------------------------------------------------

 */

void

ExecReScanBitmapHeapScan(BitmapHeapScanState *node)

{

  PlanState  *outerPlan = outerPlanState(node);

  TableScanDesc scan = node->ss.ss_currentScanDesc;

  if (scan)

  {

    /*

     * End iteration on iterators saved in scan descriptor if they have

     * not already been cleaned up.

     */

    if (!tbm_exhausted(&scan->st.rs_tbmiterator))

      tbm_end_iterate(&scan->st.rs_tbmiterator);

    /* rescan to release any page pin */

    table_rescan(node->ss.ss_currentScanDesc, NULL);

  }

  /* release bitmaps and buffers if any */

  if (node->tbm)

    tbm_free(node->tbm);

  node->tbm = NULL;

  node->initialized = false;

  node->recheck = true;

  ExecScanReScan(&node->ss);

  /*

   * if chgParam of subnode is not null then plan will be re-scanned by

   * first ExecProcNode.

   */

  if (outerPlan->chgParam == NULL)

    ExecReScan(outerPlan);

}

/* ----------------------------------------------------------------

 *    ExecEndBitmapHeapScan

 * ----------------------------------------------------------------

 */

void

ExecEndBitmapHeapScan(BitmapHeapScanState *node)

{

  TableScanDesc scanDesc;

  /*

   * When ending a parallel worker, copy the statistics gathered by the

   * worker back into shared memory so that it can be picked up by the main

   * process to report in EXPLAIN ANALYZE.

   */

  if (node->sinstrument != NULL && IsParallelWorker())

  {

    BitmapHeapScanInstrumentation *si;

    Assert(ParallelWorkerNumber <= node->sinstrument->num_workers);

    si = &node->sinstrument->sinstrument[ParallelWorkerNumber];

    /*

     * Here we accumulate the stats rather than performing memcpy on

     * node->stats into si.  When a Gather/GatherMerge node finishes it

     * will perform planner shutdown on the workers.  On rescan it will

     * spin up new workers which will have a new BitmapHeapScanState and

     * zeroed stats.

     */

    si->exact_pages += node->stats.exact_pages;

    si->lossy_pages += node->stats.lossy_pages;

  }

  /*

   * extract information from the node

   */

  scanDesc = node->ss.ss_currentScanDesc;

  /*

   * close down subplans

   */

  ExecEndNode(outerPlanState(node));

  if (scanDesc)

  {

    /*

     * End iteration on iterators saved in scan descriptor if they have

     * not already been cleaned up.

     */

    if (!tbm_exhausted(&scanDesc->st.rs_tbmiterator))

      tbm_end_iterate(&scanDesc->st.rs_tbmiterator);

    /*

     * close table scan

     */

    table_endscan(scanDesc);

  }

  /*

   * release bitmaps and buffers if any

   */

  if (node->tbm)

    tbm_free(node->tbm);

}

/* ----------------------------------------------------------------

 *    ExecInitBitmapHeapScan

 *

 *    Initializes the scan's state information.

 * ----------------------------------------------------------------

 */

BitmapHeapScanState *

ExecInitBitmapHeapScan(BitmapHeapScan *node, EState *estate, int eflags)

{

  BitmapHeapScanState *scanstate;

  Relation  currentRelation;

  /* check for unsupported flags */

  Assert(!(eflags & (EXEC_FLAG_BACKWARD | EXEC_FLAG_MARK)));

  /*

   * Assert caller didn't ask for an unsafe snapshot --- see comments at

   * head of file.

   */

  Assert(IsMVCCSnapshot(estate->es_snapshot));

  /*

   * create state structure

   */

  scanstate = makeNode(BitmapHeapScanState);

  scanstate->ss.ps.plan = (Plan *) node;

  scanstate->ss.ps.state = estate;

  scanstate->ss.ps.ExecProcNode = ExecBitmapHeapScan;

  scanstate->tbm = NULL;

  /* Zero the statistics counters */

  memset(&scanstate->stats, 0, sizeof(BitmapHeapScanInstrumentation));

  scanstate->initialized = false;

  scanstate->pstate = NULL;

  scanstate->recheck = true;

  /*

   * Miscellaneous initialization

   *

   * create expression context for node

   */

  ExecAssignExprContext(estate, &scanstate->ss.ps);

  /*

   * open the scan relation

   */

  currentRelation = ExecOpenScanRelation(estate, node->scan.scanrelid, eflags);

  /*

   * initialize child nodes

   */

  outerPlanState(scanstate) = ExecInitNode(outerPlan(node), estate, eflags);

  /*

   * get the scan type from the relation descriptor.

   */

  ExecInitScanTupleSlot(estate, &scanstate->ss,

              RelationGetDescr(currentRelation),

              table_slot_callbacks(currentRelation));

  /*

   * Initialize result type and projection.

   */

  ExecInitResultTypeTL(&scanstate->ss.ps);

  ExecAssignScanProjectionInfo(&scanstate->ss);

  /*

   * initialize child expressions

   */

  scanstate->ss.ps.qual =

    ExecInitQual(node->scan.plan.qual, (PlanState *) scanstate);

  scanstate->bitmapqualorig =

    ExecInitQual(node->bitmapqualorig, (PlanState *) scanstate);

  scanstate->ss.ss_currentRelation = currentRelation;

  /*

   * all done.

   */

  return scanstate;

}

/*----------------

 *    BitmapShouldInitializeSharedState

 *

 *    The first process to come here and see the state to the BM_INITIAL

 *    will become the leader for the parallel bitmap scan and will be

 *    responsible for populating the TIDBitmap.  The other processes will

 *    be blocked by the condition variable until the leader wakes them up.

 * ---------------

 */

static bool

BitmapShouldInitializeSharedState(ParallelBitmapHeapState *pstate)

{

  SharedBitmapState state;

  while (1)

  {

    SpinLockAcquire(&pstate->mutex);

    state = pstate->state;

    if (pstate->state == BM_INITIAL)

      pstate->state = BM_INPROGRESS;

    SpinLockRelease(&pstate->mutex);

    /* Exit if bitmap is done, or if we're the leader. */

    if (state != BM_INPROGRESS)

      break;

    /* Wait for the leader to wake us up. */

    ConditionVariableSleep(&pstate->cv, WAIT_EVENT_PARALLEL_BITMAP_SCAN);

  }

  ConditionVariableCancelSleep();

  return (state == BM_INITIAL);

}

/* ----------------------------------------------------------------

 *    ExecBitmapHeapEstimate

 *

 *    Compute the amount of space we'll need in the parallel

 *    query DSM, and inform pcxt->estimator about our needs.

 * ----------------------------------------------------------------

 */

void

ExecBitmapHeapEstimate(BitmapHeapScanState *node,

             ParallelContext *pcxt)

{

  Size    size;

  size = MAXALIGN(sizeof(ParallelBitmapHeapState));

  /* account for instrumentation, if required */

  if (node->ss.ps.instrument && pcxt->nworkers > 0)

  {

    size = add_size(size, offsetof(SharedBitmapHeapInstrumentation, sinstrument));

    size = add_size(size, mul_size(pcxt->nworkers, sizeof(BitmapHeapScanInstrumentation)));

  }

  shm_toc_estimate_chunk(&pcxt->estimator, size);

  shm_toc_estimate_keys(&pcxt->estimator, 1);

}

/* ----------------------------------------------------------------

 *    ExecBitmapHeapInitializeDSM

 *

 *    Set up a parallel bitmap heap scan descriptor.

 * ----------------------------------------------------------------

 */

void

ExecBitmapHeapInitializeDSM(BitmapHeapScanState *node,

              ParallelContext *pcxt)

{

  ParallelBitmapHeapState *pstate;

  SharedBitmapHeapInstrumentation *sinstrument = NULL;

  dsa_area   *dsa = node->ss.ps.state->es_query_dsa;

  char     *ptr;

  Size    size;

  /* If there's no DSA, there are no workers; initialize nothing. */

  if (dsa == NULL)

    return;

  size = MAXALIGN(sizeof(ParallelBitmapHeapState));

  if (node->ss.ps.instrument && pcxt->nworkers > 0)

  {

    size = add_size(size, offsetof(SharedBitmapHeapInstrumentation, sinstrument));

    size = add_size(size, mul_size(pcxt->nworkers, sizeof(BitmapHeapScanInstrumentation)));

  }

  ptr = shm_toc_allocate(pcxt->toc, size);

  pstate = (ParallelBitmapHeapState *) ptr;

  ptr += MAXALIGN(sizeof(ParallelBitmapHeapState));

  if (node->ss.ps.instrument && pcxt->nworkers > 0)

    sinstrument = (SharedBitmapHeapInstrumentation *) ptr;

  pstate->tbmiterator = 0;

  /* Initialize the mutex */

  SpinLockInit(&pstate->mutex);

  pstate->state = BM_INITIAL;

  ConditionVariableInit(&pstate->cv);

  if (sinstrument)

  {

    sinstrument->num_workers = pcxt->nworkers;

    /* ensure any unfilled slots will contain zeroes */

    memset(sinstrument->sinstrument, 0,

         pcxt->nworkers * sizeof(BitmapHeapScanInstrumentation));

  }

  shm_toc_insert(pcxt->toc, node->ss.ps.plan->plan_node_id, pstate);

  node->pstate = pstate;

  node->sinstrument = sinstrument;

}

/* ----------------------------------------------------------------

 *    ExecBitmapHeapReInitializeDSM

 *

 *    Reset shared state before beginning a fresh scan.

 * ----------------------------------------------------------------

 */

void

ExecBitmapHeapReInitializeDSM(BitmapHeapScanState *node,

                ParallelContext *pcxt)

{

  ParallelBitmapHeapState *pstate = node->pstate;

  dsa_area   *dsa = node->ss.ps.state->es_query_dsa;

  /* If there's no DSA, there are no workers; do nothing. */

  if (dsa == NULL)

    return;

  pstate->state = BM_INITIAL;

  if (DsaPointerIsValid(pstate->tbmiterator))

    tbm_free_shared_area(dsa, pstate->tbmiterator);

  pstate->tbmiterator = InvalidDsaPointer;

}

/* ----------------------------------------------------------------

 *    ExecBitmapHeapInitializeWorker

 *

 *    Copy relevant information from TOC into planstate.

 * ----------------------------------------------------------------

 */

void

ExecBitmapHeapInitializeWorker(BitmapHeapScanState *node,

                 ParallelWorkerContext *pwcxt)

{

  char     *ptr;

  Assert(node->ss.ps.state->es_query_dsa != NULL);

  ptr = shm_toc_lookup(pwcxt->toc, node->ss.ps.plan->plan_node_id, false);

  node->pstate = (ParallelBitmapHeapState *) ptr;

  ptr += MAXALIGN(sizeof(ParallelBitmapHeapState));

  if (node->ss.ps.instrument)

    node->sinstrument = (SharedBitmapHeapInstrumentation *) ptr;

}

/* ----------------------------------------------------------------

 *    ExecBitmapHeapRetrieveInstrumentation

 *

 *    Transfer bitmap heap scan statistics from DSM to private memory.

 * ----------------------------------------------------------------

 */

void

ExecBitmapHeapRetrieveInstrumentation(BitmapHeapScanState *node)

{

  SharedBitmapHeapInstrumentation *sinstrument = node->sinstrument;

  Size    size;

  if (sinstrument == NULL)

    return;

  size = offsetof(SharedBitmapHeapInstrumentation, sinstrument)

    + sinstrument->num_workers * sizeof(BitmapHeapScanInstrumentation);

  node->sinstrument = palloc(size);

  memcpy(node->sinstrument, sinstrument, size);

}