PostgreSQL 技术内幕(十一)位图扫描

xiaoming=# explain select * from t1;
                         QUERY PLAN
-------------------------------------------------------------
 Seq Scan on t1  (cost=0.00..30811.00 rows=2000000 width=12)
(1 row)

xiaoming=# SELECT relpages, current_setting('seq_page_cost') AS seq_page_cost,
  relpages * current_setting('seq_page_cost')::real AS io_cost
FROM pg_class WHERE relname='t1';
 relpages | seq_page_cost | io_cost
----------+---------------+---------
    10811 | 1             |   10811
(1 row)
cpu_cost = cpu_tuple_cost * reltuples
xiaoming=# select reltuples, current_setting('cpu_tuple_cost') as cpu_tuple_cost,
reltuples * current_setting('cpu_tuple_cost')::real AS cpu_cost
from pg_class where relname='t1';
 reltuples | cpu_tuple_cost | cpu_cost
-----------+----------------+----------
     2e+06 | 0.01           |    20000
(1 row)

xiaoming=# explain select * from t1 where a <= 10000;
                        QUERY PLAN
-----------------------------------------------------------
 Seq Scan on t1  (cost=0.00..35811.00 rows=20557 width=12)
   Filter: (a <= 10000)
(2 rows)

disk_run_cost = spc_seq_page_cost * baserel->pages;
/* CPU costs */
get_restriction_qual_cost(root, baserel, param_info, &qpqual_cost);
startup_cost += qpqual_cost.startup;
cpu_per_tuple = cpu_tuple_cost + qpqual_cost.per_tuple;
cpu_run_cost = cpu_per_tuple * baserel->tuples;
/* tlist eval costs are paid per output row, not per tuple scanned */
startup_cost += path->pathtarget->cost.startup;
cpu_run_cost += path->pathtarget->cost.per_tuple * path->rows;
... 
... 
total_cost = startup_cost + cpu_run_cost + disk_run_cost;

xiaoming=# explain select * from t1 where a <= 10000;
                                 QUERY PLAN
----------------------------------------------------------------------------
 Index Scan using idx_a_t1 on t1  (cost=0.43..32243.95 rows=20557 width=12)
   Index Cond: (a <= 10000)
(2 rows)

SELECT round(
  current_setting('random_page_cost')::real * pages +
  current_setting('cpu_index_tuple_cost')::real * tuples +
  current_setting('cpu_operator_cost')::real * tuples
) as bitmap_index_scan
FROM (
  SELECT relpages * 0.01027850 AS pages, reltuples * 0.01027850 AS tuples
  FROM pg_class WHERE relname = 'idx_a_t1'
) c;
 bitmap_index_scan
-------------------
               358
(1 row)

// io_cost
csquared = indexCorrelation * indexCorrelation;
run_cost += max_IO_cost + csquared * (min_IO_cost - max_IO_cost);
// cpu_cost
cpu_per_tuple = cpu_tuple_cost + qpqual_cost.per_tuple;
cpu_run_cost += cpu_per_tuple * tuples_fetched;

xiaoming=# explain select * from t1 where a <= 10000;
                                                        QUERY PLAN
--------------------------------------------------------------------------------------------------
 Bitmap Heap Scan on t1  (cost=363.74..11559.98 rows=20557 width=12) (actual time=0.988..4.097 rows=20000 loops=1)
   Recheck Cond: (a <= 10000)
   Heap Blocks: exact=110
   ->  Bitmap Index Scan on idx_a_t1  (cost=0.00..358.61 rows=20557 width=0) (actual time=0.954..0.955 rows=20000 loops=1)
         Index Cond: (a <= 10000)
 Planning Time: 0.100 ms
 Execution Time: 4.971 ms

typedef struct BMScanOpaqueData
{
    // 记录当前扫描的位置
    BMScanPosition      bm_currPos;
    bool                cur_pos_valid;
    /* XXX: should we pull out mark pos? */
    BMScanPosition      bm_markPos;
    // bmmarkpos() -- save the current scan position. 
    bool                mark_pos_valid;
} BMScanOpaqueData;

typedef enum
{
    TBM_EMPTY,                  /* no hashtable, nentries == 0 */
    TBM_ONE_PAGE,               /* entry1 contains the single entry */
    TBM_HASH                    /* pagetable is valid, entry1 is not */
} TBMStatus;
typedef struct PagetableEntry
{
    BlockNumber blockno;        /* page number (hashtable key) */
    char        status;         /* hash entry status */
    bool        ischunk;        /* T = lossy storage, F = exact */
    bool        recheck;        /* should the tuples be rechecked? */
    tbm_bitmapword  words[Max(WORDS_PER_PAGE, WORDS_PER_CHUNK)];
} PagetableEntry;
struct TIDBitmap
{
    NodeTag     type;           /* to make it a valid Node */
    MemoryContext mcxt;         /* memory context containing me */
    TBMStatus   status;         /* see codes above */
    struct pagetable_hash *pagetable;   /* hash table of PagetableEntry's */
    int         nentries;       /* number of entries in pagetable */
    int         nentries_hwm;   /* high-water mark for number of entries */
    int         maxentries;     /* limit on same to meet maxbytes */
    int         npages;         /* number of exact entries in pagetable */
    int         nchunks;        /* number of lossy entries in pagetable */
    TBMIteratingState iterating;    /* tbm_begin_iterate called? */
    uint32      lossify_start;  /* offset to start lossifying hashtable at */
    PagetableEntry entry1;      /* used when status == TBM_ONE_PAGE */
    /* these are valid when iterating is true: */
    PagetableEntry **spages;    /* sorted exact-page list, or NULL */
    PagetableEntry **schunks;   /* sorted lossy-chunk list, or NULL */
    dsa_pointer dsapagetable;   /* dsa_pointer to the element array */
    dsa_pointer dsapagetableold;    /* dsa_pointer to the old element array */
    dsa_pointer ptpages;        /* dsa_pointer to the page array */
    dsa_pointer ptchunks;       /* dsa_pointer to the chunk array */
    dsa_area   *dsa;            /* reference to per-query dsa area */
};

typedef struct PagetableEntry
{
    BlockNumber blockno;        /* page number (hashtable key) */
    char        status;         /* hash entry status */
    bool        ischunk;        /* T = lossy storage, F = exact */
    bool        recheck;        /* should the tuples be rechecked? */
    tbm_bitmapword  words[Max(WORDS_PER_PAGE, WORDS_PER_CHUNK)];
} PagetableEntry;

xiaoming=# explain select * from t1 where a <= 10000 and b <= 10000;
                                    QUERY PLAN
--------------------------------------------------------------------
 Bitmap Heap Scan on t1  (cost=717.57..1469.55 rows=211 width=12)
   Recheck Cond: ((b <= 10000) AND (a <= 10000))
   ->  BitmapAnd  (cost=717.57..717.57 rows=211 width=0)
         ->  Bitmap Index Scan on idx_b_t1  (cost=0.00..358.61 rows=20557 width=0)
               Index Cond: (b <= 10000)
         ->  Bitmap Index Scan on idx_a_t1  (cost=0.00..358.61 rows=20557 width=0)
               Index Cond: (a <= 10000)

xiaoming=# explain select * from t1 where a <= 10000;
                                                        QUERY PLAN
--------------------------------------------------------------------------------------------------
 Bitmap Heap Scan on t1  (cost=363.74..11559.98 rows=20557 width=12) (actual time=0.988..4.097 rows=20000 loops=1)
   Recheck Cond: (a <= 10000)
   Heap Blocks: exact=110
         -> ... Bitmap Index Scan || Bitmap And || Bitmap Or

static TupleTableSlot *BitmapHeapNext(BitmapHeapScanState *node) {
    //下级节点返回TIDBitmap结构
    tbm = (TIDBitmap *) MultiExecProcNode(outerPlanState(node));
    node->tbm = tbm;
    // 初始化扫描迭代器，构造tbm->spages和tbm->schunks用于扫描，
    // 并两个数组按照page id排序
    node->tbmiterator = tbmiterator = tbm_begin_iterate(tbm);
    node->tbmres = tbmres = tbm_iterate(tbmiterator);


    // 读取一个block，lossy page就是在这个case下处理的
    // 读取一整个heap page, 保存在scan的buffer中，用于下次扫描
    table_scan_bitmap_next_block(scan, tbmres)


    // 如果是lossy的，则会循环读取，直到找到一个满足Filter条件的tuple.
    // 如果是exact的，则直接根据tmbres中的当前entry指针，直接seek
    // 到next offset指向的tuple..
    table_scan_bitmap_next_tuple(scan, tbmres, slot)


    return slot;
}

SELECT round(
  current_setting('random_page_cost')::real * pages +
  current_setting('cpu_index_tuple_cost')::real * tuples +
  current_setting('cpu_operator_cost')::real * tuples
) as bitmap_index_scan
FROM (
  SELECT relpages * 0.01027850 AS pages, reltuples * 0.01027850 AS tuples
  FROM pg_class WHERE relname = 'idx_a_t1'
) c;
 bitmap_index_scan
-------------------
               358
(1 row)

WITH t AS (
  SELECT relpages,
    least(
      (2 * relpages * reltuples * 0.01027850) 
      (2 * relpages + reltuples * 0.01027850), relpages
    ) AS pages_fetched,
    round(reltuples * 0.01027850) AS tuples_fetched,
    current_setting('random_page_cost')::real AS rnd_cost,
    current_setting('seq_page_cost')::real AS seq_cost
  FROM pg_class WHERE relname = 't1'
), s AS(
  select pages_fetched, rnd_cost - (rnd_cost - seq_cost) *
  sqrt(pages_fetched / relpages) AS cost_per_page, tuples_fetched 
  tuples_fetched from t
),
costs(startup_cost, run_cost) AS (
  SELECT
    ( SELECT round(
        358 /* child node cost */ +
        0.1 * current_setting('cpu_operator_cost')::real *
        reltuples * 0.01027850
      )
      FROM pg_class WHERE relname = 'idx_a_t1'
    ),
    ( SELECT round(
        cost_per_page * pages_fetched +
        current_setting('cpu_tuple_cost')::real * tuples_fetched +
        current_setting('cpu_operator_cost')::real * tuples_fetched
      )
      FROM s
    )
)
SELECT startup_cost, run_cost, startup_cost + run_cost AS total_cost
FROM costs;
 startup_cost | run_cost | total_cost
--------------+----------+------------
          363 |    11197 |      11560
(1 row)

欢迎大家扫描下方二维码

添加企微小助手联系我们

获取HashData产品与活动最新资讯！