* Acquire the sample rows */
  rows = (HeapTuple *) palloc(targrows * sizeof(HeapTuple));
  if (inh) numrows = acquire_inherited_sample_rows(onerel, elevel, rows, targrows, &totalrows, &totaldeadrows);
  else numrows = (*acquirefunc) (onerel, elevel, rows, targrows, &totalrows, &totaldeadrows);

while i < k
    p = k/（K - i）; 
    if V < p
      pick it
      k--;
    i++

typedef struct{
  BlockNumber N;  * number of blocks, known in advance */  抽样对象大小
  int      n;  * desired sample size */
  BlockNumber t;        * current block number */
  int      m;        /* blocks selected so far */
  SamplerRandomState randstate;  /* random generator state */
} BlockSamplerData;
typedef unsigned short SamplerRandomState[3];

BlockSampler_Init(&bs, totalblocks, targrows, random());
while (BlockSampler_HasMore(&bs)){
  BlockNumber targblock = BlockSampler_Next(&bs);
}

BlockNumber BlockSampler_Next(BlockSampler bs) {
  BlockNumber K = bs->N - bs->t;  /* remaining blocks */  // 剩余带抽样数据块
  int      k = bs->n - bs->m;  /* blocks still to sample */  // 还需要抽样的数据块数目
  double    p;        /* probability to skip block */
  double    V;        /* random */
  if ((BlockNumber) k >= K) { /* need all the rest */  // 剩余带抽样数据库不够，剩下的都需要
    bs->m++;        // 当前已抽样数据块数量++
    return bs->t++; // 使用该数据库
  }
  V = sampler_random_fract(bs->randstate); // 产生V 0-1之间的随机数 
  p = 1.0 - (double) k / (double) K;
  while (V < p){    
    bs->t++; /* skip */ // 跳过该数据块
    K--;  /* keep K == N - t */    
    p *= 1.0 - (double) k / (double) K; /* adjust p to be new cutoff point in reduced range */
  }  
  bs->m++; /* select */ // 当前已抽样数据块数量++
  return bs->t++; // 使用该数据块
}

typedef struct
{
  double    W;
  SamplerRandomState randstate;  /* random generator state */
} ReservoirStateData;
typedef unsigned short SamplerRandomState[3];
void reservoir_init_selection_state(ReservoirState rs, int n){  
  sampler_random_init_state(random(), rs->randstate);   /* Reservoir sampling is not used anywhere where it would need to return repeatable results so we can initialize it randomly. */ // 水库采样不用于需要返回可重复结果的任何地方，因此我们可以随机初始化
  rs->W = exp(-log(sampler_random_fract(rs->randstate)) / n); /* Initial value of W (for use when Algorithm Z is first applied) */
}

double reservoir_get_next_S(ReservoirState rs, double t, int n) {
  double    S;  
  if (t <= (22.0 * n)) { /* The magic constant here is T from Vitter's paper */
    /* Process records using Algorithm X until t is large enough */
    double    V, quot;
    V = sampler_random_fract(rs->randstate);  /* Generate V */
    S = 0;
    t += 1;
    /* Note: "num" in Vitter's code is always equal to t - n */
    quot = (t - (double) n) / t;    
    while (quot > V){ /* Find min S satisfying (4.1) */
      S += 1;
      t += 1;
      quot *= (t - (double) n) / t;
    }
  }else{
    /* Now apply Algorithm Z */
    double    W = rs->W;
    double    term = t - (double) n + 1;
    for (;;){
      double    numer,numer_lim,denom;
      double    U,X,lhs,rhs,y,tmp;
      /* Generate U and X */
      U = sampler_random_fract(rs->randstate);
      X = t * (W - 1.0);
      S = floor(X);    /* S is tentatively set to floor(X) */
      /* Test if U <= h(S)/cg(X) in the manner of (6.3) */
      tmp = (t + 1) / term;
      lhs = exp(log(((U * tmp * tmp) * (term + S)) / (t + X)) / n);
      rhs = (((t + X) / (term + S)) * term) / t;
      if (lhs <= rhs){
        W = rhs / lhs;
        break;
      }
      /* Test if U <= f(S)/cg(X) */
      y = (((U * (t + 1)) / term) * (t + S + 1)) / (t + X);
      if ((double) n < S){
        denom = t;
        numer_lim = term + S;
      }else{
        denom = t - (double) n + S;
        numer_lim = t + 1;
      }
      for (numer = t + S; numer >= numer_lim; numer -= 1){
        y *= numer / denom;
        denom -= 1;
      }
      W = exp(-log(sampler_random_fract(rs->randstate)) / n); /* Generate W in advance */
      if (exp(log(y) / n) <= (t + X) / t)
        break;
    }
    rs->W = W;
  }
  return S;
}

static int acquire_sample_rows(Relation onerel, int elevel, HeapTuple *rows, int targrows, double *totalrows, double *totaldeadrows) {
  int      numrows = 0;  /* # rows now in reservoir */
  double    samplerows = 0/* total # rows collected */, liverows = 0/* # live rows seen */, deadrows = 0/* # dead rows seen */, rowstoskip = -1 /* -1 means not set yet */;   
  BlockNumber totalblocks;
  TransactionId OldestXmin;
  BlockSamplerData bs;
  ReservoirStateData rstate;
  TupleTableSlot *slot;
  TableScanDesc scan;




  totalblocks = RelationGetNumberOfBlocks(onerel); // 首先获取该表有多少数据块  
  OldestXmin = GetOldestXmin(onerel, PROCARRAY_FLAGS_VACUUM); /* Need a cutoff xmin for HeapTupleSatisfiesVacuum */  
  BlockSampler_Init(&bs, totalblocks, targrows, random()); /* Prepare for sampling block numbers */ //Algorithm Z算法采样数据行准备工作
  reservoir_init_selection_state(&rstate, targrows); /* Prepare for sampling rows */ //Algorithm Z算法采样数据行准备工作




  scan = table_beginscan_analyze(onerel);
  slot = table_slot_create(onerel, NULL);  
  while (BlockSampler_HasMore(&bs)) { /* Outer loop over blocks to sample */
    BlockNumber targblock = BlockSampler_Next(&bs);  // 获取目标数据块
    vacuum_delay_point();
    if (!table_scan_analyze_next_block(scan, targblock, vac_strategy)) continue;  // 目标数据块不适合采样
    while (table_scan_analyze_next_tuple(scan, OldestXmin, &liverows, &deadrows, slot)) {
      /* The first targrows sample rows are simply copied into the reservoir. Then we start replacing tuples in the sample until we reach the end of the relation.  This algorithm is from Jeff Vitter's paper (see full citation in utils/misc/sampling.c). It works by repeatedly computing the number of tuples to skip before selecting a tuple, which replaces a randomly chosen element of the reservoir (current set of tuples).  At all times the reservoir is a true random sample of the tuples we've passed over so far, so when we fall off the end of the relation we're done. */ // 第一个目标行样本行简单地复制到水库中。然后我们开始替换样本中的元组，直到到达表的末尾。该算法来自Jeff Vitter的论文（参见utils/misc/sampling.c中的完整引用）。它的工作原理是在选择元组之前重复计算要跳过的元组数，这将替换随机选择的库元素（当前元组集）。在任何时候，水库中都是到目前为止传递的元组的真正随机样本，所以当我们扫描到表的结尾时，我们就完成了
      if (numrows < targrows) rows[numrows++] = ExecCopySlotHeapTuple(slot); // tuple拷贝到rows中
      else { /* t in Vitter's paper is the number of records already processed.  If we need to compute a new S value, we must use the not-yet-incremented value of samplerows as t. */
        if (rowstoskip < 0) rowstoskip = reservoir_get_next_S(&rstate, samplerows, targrows);
        if (rowstoskip <= 0) { /* Found a suitable tuple, so save it, replacing one old tuple at random */ // 替换水库中的采样元素
          int      k = (int) (targrows * sampler_random_fract(rstate.randstate));
          heap_freetuple(rows[k]);
          rows[k] = ExecCopySlotHeapTuple(slot);
        }
        rowstoskip -= 1;
      }
      samplerows += 1;
    }
  }
  ExecDropSingleTupleTableSlot(slot);
  table_endscan(scan);




  /* If we didn't find as many tuples as we wanted then we're done. No sort is needed, since they're already in order. Otherwise we need to sort the collected tuples by position (itempointer). It's not worth worrying about corner cases where the tuples are already sorted. */ // 如果我们找不到我们想要的那么多元组，那么我们就完了。不需要排序，因为它们已经排序好了。否则，我们需要按位置（itempointer）对收集的元组进行排序。不必担心元组已经排序的corner cases 。
  if (numrows == targrows) qsort((void *) rows, numrows, sizeof(HeapTuple), compare_rows);
  /* Estimate total numbers of live and dead rows in relation, extrapolating on the assumption that the average tuple density in pages we didn't scan is the same as in the pages we did scan.  Since what we scanned is a random sample of the pages in the relation, this should be a good assumption. */ // 估计相关的活行和死行总数，假设我们未扫描的页面中的平均元组密度与我们扫描的页面相同。由于我们扫描的是关系中页面的随机样本，这应该是一个很好的假设
  if (bs.m > 0){
    *totalrows = floor((liverows / bs.m) * totalblocks + 0.5); // live行数/采样样本行数*总数据块 + 0.5
    *totaldeadrows = floor((deadrows / bs.m) * totalblocks + 0.5); // dead行数/采样样本行数*总数据块 + 0.5
  }else{
    *totalrows = 0.0;
    *totaldeadrows = 0.0;
  }
  return numrows;
}