a_ogawa

2009-06-10

[]faster version of AllocSetFreeIndex for x86 architecture

http://archives.postgresql.org/pgsql-hackers/2009-06/msg00159.php

Postgresqlのmemory managerで、空きブロックリストのインデックスを計算する処理を高速化するパッチ。

現在のコードは、以下のようにループして計算しているが

static inline int
AllocSetFreeIndex(Size size)
{
	int         idx = 0;

	if (size > 0)
	{
		size = (size - 1) >> ALLOC_MINBITS;
		while (size != 0)
		{
			idx++;
			size >>= 1;
		}
		Assert(idx < ALLOCSET_NUM_FREELISTS);
	}

	return idx;
}

これを、x86 CPUのbsrで計算するようにした

static inline int
AllocSetFreeIndex(Size size)
{
    int idx;

    if (__builtin_expect(size < (1 << ALLOC_MINBITS), 0))
		size = (1 << ALLOC_MINBITS);

    /* bsr(Bit Scan Reverse): Search the most significant set bit */
    __asm__ ("bsr %1, %0" :"=r"(idx) :"g"(size - 1));

    return idx - (ALLOC_MINBITS - 1);
}

パッチの効果 (pgbench -c 1 -t 50000を実行し、oprofileで計測)

パッチ適用前

CPU: P4 / Xeon with 2 hyper-threads, speed 2793.55 MHz (estimated)
Counted GLOBAL_POWER_EVENTS events
samples  %        symbol name
66854     6.6725  AllocSetAlloc
11817     1.1794  AllocSetFree

パッチ適用後

CPU: P4 / Xeon with 2 hyper-threads, speed 2793.55 MHz (estimated)
Counted GLOBAL_POWER_EVENTS events
with a unit mask of 0x01 (mandatory) count 100000
samples  %        symbol name
47610     4.9333  AllocSetAlloc
6248      0.6474  AllocSetFree
トラックバック - http://d.hatena.ne.jp/a_ogawa/20090610

2006-05-07

[]

UNIV_EXPECT

gccでは以下のように定義される。

# define UNIV_EXPECT(expr,constant) __builtin_expect(expr, constant)

__builtin_expectはプログラマが指定できる分岐予測の情報で、exprで指定した条件がconstantで指定した結果になる可能性が高いことをコンパイラに知らせる。

以下のマクロも定義されている。

#define UNIV_LIKELY_NULL(ptr) __builtin_expect((ulint) ptr, 0)
#define UNIV_LIKELY(cond) UNIV_EXPECT(cond, TRUE)
#define UNIV_UNLIKELY(cond) UNIV_EXPECT(cond, FALSE)

例:

if(UNIV_LIKELY(a == 1)) {
    /* こちらが実行される可能性が高い */
} else {
}

if(UNIV_UNLIKELY(a == 1)) {
} else {
    /* こちらが実行される可能性が高い */
}

mysqlとinnodb間のカラムデータの変換

row_mysql_store_col_in_innobase_format (mysql->innobase)

row_sel_field_store_in_mysql_format (innobase->mysql)

mysqlとinnodbでデータをやり取りするとき、カラムのデータ型を変換する関数。

integer型はmysqlはlittle endian、innobaseはbig endianなのでバイトオーダーを変換する。また、char型は後ろをスペースで埋める処理なども行っている。

トラックバック - http://d.hatena.ne.jp/a_ogawa/20060507

2006-05-03

[] transaction

read_view_open_now

read_view_t(現在実行中のトランザクションIDのリスト: PostgreSQLのsnapshotに相当する)を作成する。

(1)read_view_create_lowでメモリを確保。

実行中のトランザクション数は、trx_sys->trx_listに登録されている。

(2)view->low_limit_noとview->low_limit_idに、trx_sys->max_trx_idを設定。

low_limit_noは後続の処理で変更される場合がある。

(3)view->trx_ids配列に、アクティブなトランザクションIDを追加する。

(4)view->up_limit_idに、trx_ids内の最小トランザクションIDを追加する。

read_view_tはトランザクションの分離レベルがREPEATABLE READの場合、トランザクションが終了するまで保持される。

分離レベルをREAD COMMITTED以下にすると、毎回削除される。

     if (trx->isolation_level <= TRX_ISO_READ_COMMITTED
                             && trx->global_read_view) {
             /* At low transaction isolation levels we let
         each consistent read set its own snapshot */
 
             read_view_close_for_mysql(trx);
     }

read_view_sees_trx_id

取り出したタプルが現在のトランザクションから参照可能か評価する。

 ha_innobase::index_first
   -> ha_innobase::index_read
      -> row_search_for_mysql
         -> lock_clust_rec_cons_read_sees
            -> read_view_sees_trx_id

trx_id: タプルのトランザクションID

view: 現在のトランザクションの情報 (snapshot)

(1)trx_idがview->up_limit_idより小さかったら見える

(2)trx_idがview->low_limit_id以上だったら見えない

(3)view->trx_idsに登録されているトランザクションID(=実行中のトランザクション)と一致したら見えない

    /* We go through the trx ids in the array smallest first: this order
    may save CPU time, because if there was a very long running
    transaction in the trx id array, its trx id is looked at first, and
    the first two comparisons may well decide the visibility of trx_id. */

    n_ids = view->n_trx_ids;

    for (i = 0; i < n_ids; i++) {

        cmp = ut_dulint_cmp(trx_id,
                read_view_get_nth_trx_id(view, n_ids - i - 1));
        if (cmp <= 0) {
            return(cmp < 0);
        }
    }

read_view_get_nth_trx_idで、view->trx_idx配列からトランザクションIDを取得する。trx_id == view->trx_idx[X]になったら、実行中のトランザクションが更新したタプルなので、参照できない。(FALSEを返す)

view->trx_ids配列には、降順でトランザクションIDが入っていて、小さいトランザクションから比較している。trx_id < view->trx_idx[X]が成立した時点で、それ以降にtrx_idと一致することはないので、TRUEを返すことができる。

長時間実行中のトランザクションが1つある場合、最初の2回の比較で結果が分かる可能性が高いので、小さい方からチェックしている。

トランザクションの分離レベルがREAD UNCOMMITTEDの場合、commit前であっても常に最新のタプルを参照するためread_view_sees_trx_idは実行されない。

また、分離レベルがSERIALIZABLEのときは、テーブルを共有ロックしてから検索するため、read_view_sees_trx_idは実行されない。(共有ロックが取得できたということは、更新中(未commit)のタプルが存在しないから。)

syfzafszyisyfzafszyi 2007/03/15 18:05 Hi! Very nice site! Thanks you very much! vglmhibnspf

ntvwdhfyylntvwdhfyyl 2007/03/16 08:07 <a href=http://cakerslqbk.com>zujio</a>

トラックバック - http://d.hatena.ne.jp/a_ogawa/20060503

2006-05-02

[]memory manager (2)

mem_heap_create_func

memory heapを作成する。mem_heap_createなどのマクロから実行される。

(関数名がXXXXX_funcなどとなっている場合、マクロ経由で実行される)

引数

n: 先頭のブロックサイズを指定する。0を指定した場合はデフォルトサイズ

(MEM_BLOCK_START_SIZE)になる。

init_blockを指定した場合は、init_blockのサイズを指定する。

init_block: memory heapの作成を高速化したい場合に、mem_heap_create_funcの呼び出し側で先頭のブロックのメモリを確保してinit_blockに指定する。これにより、mem_heap_create_func内で先頭のブロックをmalloc/freeする必要がなくなる。

type: heap typeを指定。

file_name: mem_heap_createなどのマクロを実行したファイル名

line: マクロを実行した行番号

(1)mem_heap_create_blockで先頭ブロック(block)を作成

(2)UT_LIST_INITでblock->baseを初期化

(3)UT_LIST_ADD_FIRSTでblockをリストの先頭に登録

(4)コンパイルオプションにUNIV_MEM_DEBUGが指定されているときは、mem_hash_insertでblockを登録する

(5)blockをreturnする

mem_heap_free_func

memory heapを開放する。mem_heap_freeマクロから実行される。

(1)最後のブロックを取得

block = UT_LIST_GET_LAST(heap->base);

(2)heap->free_blockがある場合、それを開放する。

(3)ループでブロックリストを前にたどりながら、全部のブロックを開放していく。先頭ブロックがheap自身なので、これでheapを開放できる。

mem_heap_alloc

memory heapからメモリを割り当てる。

(1)heap->baseのブロックリストから一番後ろのブロックを取得

    block = UT_LIST_GET_LAST(heap->base);

(2)ブロックの空き領域が足りなかったら、mem_heap_add_blockで新しいブロックを追加する。ブロックが作成できなかったらNULLを返す。

    if (mem_block_get_len(block) 
            < mem_block_get_free(block) + MEM_SPACE_NEEDED(n)) {
        block = mem_heap_add_block(heap, n);

(3)ブロックの空き領域のオフセットを取得。

    free = mem_block_get_free(block);

(4)使用するバッファの先頭位置を計算する。

    buf = (byte*)block + free;

(5)ブロックの空き領域のオフセット位置を移動する。

    mem_block_set_free(block, free + MEM_SPACE_NEEDED(n));

(6)確保したメモリのポインタを返す。

mem_heap_get_heap_top

memory heapの現在の空き領域の先頭ポインタを取得する。

(1)最後のブロックを取得

    block = UT_LIST_GET_LAST(heap->base);

(2)空き領域のポインタを取得

    buf = (byte*)block + mem_block_get_free(block);
    return(buf);

mem_heap_get_free_heap_top

引数(old_top)で指定した位置以降に確保したメモリを開放する。

mem_heap_get_heap_topで空き領域の先頭位置を取得しておいて、複数のメモリを取得したあと、mem_heap_get_free_heap_topを実行することによって、メモリの開放をまとめて実行できる。スタックポインタをシフトすることによってメモリを開放する動作に似ている。

(mem_heap_get_heap_top/mem_heap_get_free_heap_topの仕組みを利用している

箇所は見当たらなかった。mem_heap_get_free_heap_topはmem_heap_emptyで使用

されている。)

(1)最後のブロックを取得

    block = UT_LIST_GET_LAST(heap->base);

(2)old_topが含まれるブロックが見つかるまで、リストを前にたどっていく

old_topが含まれないブロックは、mem_heap_block_freeで開放していく

    while (block != NULL) {
        if (((byte*)block + mem_block_get_free(block) >= old_top)
                        && ((byte*)block <= old_top)) {
            /* Found the right block */
            break;
        }
        /* Store prev_block value before freeing the current block
        (the current block will be erased in freeing) */
        prev_block = UT_LIST_GET_PREV(list, block);

        mem_heap_block_free(heap, block);
        block = prev_block;
    }

(3)ブロックの空き領域のoffsetを、old_topに設定する

    mem_block_set_free(block, old_top - (byte*)block); 

(4)ブロックのstartとfreeが同じになった場合、そのブロックは全く使用されて

いないので開放する。ただし先頭ブロックは開放しない。

(先頭ブロックかどうかはheap != blockでチェックしている)

    /* If free == start, we may free the block if it is not the first
    one */
    if ((heap != block) && (mem_block_get_free(block) == 
                            mem_block_get_start(block))) {
        mem_heap_block_free(heap, block);
    }

mem_heap_empty

memory heapを空にする。

先頭ブロックのバッファの開始位置を指定して、mem_heap_free_heap_topを実行している。

    mem_heap_free_heap_top(heap, (byte*)heap + mem_block_get_start(heap));
 heap->free_blockがある場合、それも開放する。

[]Improvement of search for a binary operator

http://archives.postgresql.org/pgsql-patches/2006-04/msg00228.php

'='などの演算子(operator)を、どのように処理するか決める処理を高速化するパッチ。operatorはシステムカタログpg_operatorに登録されており、ユーザーがcreate operatorで登録することもできる。

pg_operatorのprimary keyは以下のようになっている。

・operatorの文字列

・operatorの左右に指定されたデータの型

・現在のセッションのnamespaceのサーチパス

従来の処理:

(1)システムカタログ(pg_operator)を演算子名をキーに検索する。検索結果からnamespaceの優先順位を考慮した演算子のリストを作成する。この処理はOpernameGetCandidate()で実行される。'='などの一般的なoperatorの場合、リストの大きさが50以上になり負荷が大きい。

(2)(1)のリストから、operatorの左右に指定されたデータ型に一致するoperatorを探す。

(3)(2)で見つからない場合、データ型の変換ルールを適用して、リストから一致するoperatorを探す。

OpernameGetCandidateの処理が重いので、(1)と(2)を入れ替える。(2)ではリストを検索する代わりに、演算子名と左右のデータ型をキーにシステムカタログ(pg_operator)を検索する。システムカタログに一致するデータが見つからない場合、(1)と(3)の処理を実行する。

eoiwpxzpodeoiwpxzpod 2007/03/15 18:05 Hi! Very nice site! Thanks you very much! pnzuqxyhzu

fxmzignaknfxmzignakn 2007/03/16 08:07 <a href=http://cmuracdaq.com>mdpiw</a>

トラックバック - http://d.hatena.ne.jp/a_ogawa/20060502

2006-04-19

[] memory manager

innobaseのmemory managerはmemory poolとmemory heapで構成されている。

memory poolは、最初にmysqlのパラメータinnobase_additional_mem_pool_sizeで指定された大きさのバッファを確保して、そこから必要なメモリを割り当てていく。このバッファからメモリを割り当てることが出来なくなったら、ut_mallocでメモリを割り当てる。(ut_mallocはmallocのラッパ)

memory heapはmemory poolからメモリを割り当てて作成される。

mem_pool_create

memory poolを作成する。sizeはバッファサイズ。

(1)ut_mallocでmem_pool_tのメモリを割り当てる

    pool = ut_malloc(sizeof(mem_pool_t));

(2)ut_malloc_lowでpool->bufのメモリを割り当てる

    pool->buf = ut_malloc_low(size, FALSE, TRUE);

2番目の引数をFALSEにして、確保したメモリを0で初期化しないようにしている

(3)pool->sizeを設定

(4)pool->mutexを作成

(5)freeリストを初期化(64個ある)

    for (i = 0; i < 64; i++) {
        UT_LIST_INIT(pool->free_list[i]);
    }

(6)free listにメモリを登録

できるだけ大きいメモリブロック単位で、リストに登録する

    used = 0;

    while (size - used >= MEM_AREA_MIN_SIZE) {
        i = ut_2_log(size - used);
        if (ut_2_exp(i) > size - used) {
            /* ut_2_log rounds upward */
            i--;
        }
        area = (mem_area_t*)(pool->buf + used);

        mem_area_set_size(area, ut_2_exp(i));
        mem_area_set_free(area, TRUE);

        UT_LIST_ADD_FIRST(free_list, pool->free_list[i], area);
        used = used + ut_2_exp(i);
    }

(7)pool->reservedを設定

(8)poolを返す

mem_pool_fill_free_list

iで指定したfree listよりも大きいサイズのfree listに登録されているメモリを分割して、iのfree listに割り当てる。

(1)free_list[i + 1]のメモリを取得

    area = UT_LIST_GET_FIRST(pool->free_list[i + 1]);

(2)free_list[i + 1]が空だったら、mem_pool_fill_free_listを再帰コールして、さらに上のリストのメモリを、free_list[i + 1]に割り当てる

    if (area == NULL) {
        ret = mem_pool_fill_free_list(i + 1, pool);
        if (ret == FALSE) {
            return(FALSE);
        }
        area = UT_LIST_GET_FIRST(pool->free_list[i + 1]);
    }

(3)free list[i + 1]から先頭のメモリ(area)を削除する

    UT_LIST_REMOVE(free_list, pool->free_list[i + 1], area);

(4)areaを2分割してfree list[i]に登録

    // 後ろ半分の処理
    area2 = (mem_area_t*)(((byte*)area) + ut_2_exp(i));      // 位置を計算
    mem_area_set_size(area2, ut_2_exp(i));                   // サイズを設定
    mem_area_set_free(area2, TRUE);                          // free flagを設定
    UT_LIST_ADD_FIRST(free_list, pool->free_list[i], area2); // listに登録

    // 前半分の処理 (free flagは変更する必要がない)
    mem_area_set_size(area, ut_2_exp(i));                    // サイズを設定
    UT_LIST_ADD_FIRST(free_list, pool->free_list[i], area);  // listに登録

mem_area_alloc

memory poolからメモリを割り当てる

(1)使用するfree listを計算

    n = ut_2_log(ut_max(size + MEM_AREA_EXTRA_SIZE, MEM_AREA_MIN_SIZE));

(2)mutexをロック

    mutex_enter(&(pool->mutex));
    mem_n_threads_inside++;

(3)free_list[n]からmemory areaを取得

    area = UT_LIST_GET_FIRST(pool->free_list[n]);

(4)free_list[n]が空だった場合、mem_pool_fill_free_listでfree_list[n + 1]以降から、free_list[n]にメモリを割り当てる

free_list[n + 1]以降からメモリが割り当てられなかった場合、ut_mallocでメモリを割り当てて返す。

    if (area == NULL) {
        ret = mem_pool_fill_free_list(n, pool);

        if (ret == FALSE) {
            /* Out of memory in memory pool: we try to allocate
            from the operating system with the regular malloc: */

            mem_n_threads_inside--;
            mutex_exit(&(pool->mutex));

            return(ut_malloc(size));
        }

        area = UT_LIST_GET_FIRST(pool->free_list[n]);
    }

(5)使用するmemory areaのfree flagを降ろす

    mem_area_set_free(area, FALSE);

(6)memory areaをfree_list[n]から削除

    UT_LIST_REMOVE(free_list, pool->free_list[n], area);

(7)pool->reservedを増加させる

    pool->reserved += mem_area_get_size(area);

(8)mutexを開放

    mem_n_threads_inside--;
    mutex_exit(&(pool->mutex));

(9)確保したメモリを返す

areaの先頭はstruct mem_area_structの領域なので、その後ろのポインタを返す。

    return((void*)(MEM_AREA_EXTRA_SIZE + ((byte*)area))); 

mem_area_get_buddy

memory areaの兄弟エリアを取得する

(1)areaとbufの差が(2 * size)で割り切れるとき、buddyは右(higher address)にある

    if (((((byte*)area) - pool->buf) % (2 * size)) == 0) {
        /* The buddy is in a higher address */
        buddy = (mem_area_t*)(((byte*)area) + size);

        // pool->bufをオーバーしないようにする
        if ((((byte*)buddy) - pool->buf) + size > pool->size) {
            /* The buddy is not wholly contained in the pool:
            there is no buddy */
            buddy = NULL;
        }

(2)areaとbufの差が(2 * size)で割り切れないとき、buddyは左(lower address)にある

    } else {
        /* The buddy is in a lower address; NOTE that area cannot
        be at the pool lower end, because then we would end up to
        the upper branch in this if-clause: the remainder would be
        0 */
        buddy = (mem_area_t*)(((byte*)area) - size);
    }

mem_area_free

mem_area_allocで割り当てたメモリを開放する。

(1)ptrがpool->buf〜(pool->buf + pool->size)の間にない場合、ut_mallocで

割り当てられたメモリなので、ut_freeを実行する。

    if ((byte*)ptr < pool->buf || (byte*)ptr >= pool->buf + pool->size) {
        ut_free(ptr);
        return;
    }

(2)ptrからmemory areaのポインタを計算

    area = (mem_area_t*) (((byte*)ptr) - MEM_AREA_EXTRA_SIZE);

(3)memory areaのサイズを取得

    size = mem_area_get_size(area);

(4)memory areaの兄弟area(隣のarea)を取得

    buddy = mem_area_get_buddy(area, size, pool);

(5)free_listのindexを計算

    n = ut_2_log(size);

(6)mutexをロック

(7)兄弟areaが存在して、兄弟areaが未使用(mem_area_get_freeがTRUE)で、

兄弟areaのサイズがfreeするareaと同じとき、2つのareaをくっつけて

上位のfree_list[n + 1]に登録する。

    if (buddy && mem_area_get_free(buddy)
              && (size == mem_area_get_size(buddy))) {
        /* The buddy is in a free list */
        if ((byte*)buddy < (byte*)area) {  // buddyがareaの左にある
            // buddyをfree_list[n + 1]に登録するための準備
            new_ptr = ((byte*)buddy) + MEM_AREA_EXTRA_SIZE;
            mem_area_set_size(buddy, 2 * size);
            mem_area_set_free(buddy, FALSE);
        } else {                           // buddyがareaの右にある
            // ptrをfree_list[n + 1]に登録するための準備
            new_ptr = ptr;
            mem_area_set_size(area, 2 * size);
        }

        /* Remove the buddy from its free list and merge it to area */
        // buddyをfree_list[n]から削除
        UT_LIST_REMOVE(free_list, pool->free_list[n], buddy);
        pool->reserved += ut_2_exp(n);

        mem_n_threads_inside--;
        mutex_exit(&(pool->mutex));

        // mem_area_freeを再帰コールして、free_list[n + 1]に登録する
        mem_area_free(new_ptr, pool);
        return;

(8)buddyが使えない場合((7)の条件を満たさない場合)、ptrをfree_list[n]に登録する

        UT_LIST_ADD_FIRST(free_list, pool->free_list[n], area);
        mem_area_set_free(area, TRUE);
        ut_ad(pool->reserved >= size);
        pool->reserved -= size;

(9)mutexを開放

llurtczrwhllurtczrwh 2007/03/15 18:05 Hi! Very nice site! Thanks you very much! rrealfkmyt

dnikiwanyvdnikiwanyv 2007/03/16 08:07 <a href=http://cstfsehhh.com>kxarjjskj</a>

トラックバック - http://d.hatena.ne.jp/a_ogawa/20060419

2006-04-15

[]hash

mysqlのハッシュテーブルは、PostgreSQLと同じリニアハッシュ・アルゴリズムを使用している。

(PostgreSQLのハッシュテーブル:http://www.hi-ho.ne.jp/a_ogawa/document/pg_dynahash.pdf)

PostgreSQLと違う点。

- ハッシュテーブルにデータを登録するたびに、テーブルを拡張する。 (データ数 = Bucket数になる)

- ハッシュ番地が衝突したときは、データを空いているBucketに登録して、 線形リストでリンクする。

typedef struct st_hash {
  uint key_offset,key_length;       /* Length of key if const length */
  uint records,blength,current_record;
  uint flags;
  DYNAMIC_ARRAY array;              /* Place for hash_keys */
  hash_get_key get_key;
  void (*free)(void *);
  CHARSET_INFO *charset;
} HASH;

_hash_init

HASHを初期化する。

CALLER_INFOを受け取るために、hash_initマクロ経由で実行される。

CHARSET_INFO

include/m_ctype.hで定義されている。

my_hash_insert

ハッシュテーブルにデータを登録する。

関数の前半部分は、リニアハッシュのBucketを拡張する処理。

後半部分(/* Check if we are at the empty position */以降)がデータ登録処理。

rec_hashnr

unsigned int rec_hashnr(HASH *hash,const byte *record)
{
  uint length;
  byte *key= (byte*) hash_key(hash,record,&length,0);
  return calc_hash(hash,key,length);
}

hash_keyでキーを取り出した後、calc_hashでハッシュ値を計算する

hash_key

static inline char*
hash_key(HASH *hash,const byte *record,uint *length,my_bool first)
{
  if (hash->get_key)
    return (*hash->get_key)(record,length,first);
  *length=hash->key_length;
  return (byte*) record+hash->key_offset;
}

ハッシュのキーとキーの長さを取り出す。

HASH->get_keyに関数ポインタが設定されているときは、その関数を使う。

たとえばtable_def_cacheでは、get_keyにtable_def_key関数が使われる。

get_keyが指定されていないときは、長さ(length)にHASH->key_lengthが設定され、キーにrecord + hash->key_offsetを返す。

calc_hash

static uint calc_hash(HASH *hash,const byte *key,uint length)
{
  ulong nr1=1, nr2=4;
  hash->charset->coll->hash_sort(hash->charset,(uchar*) key,length,&nr1,&nr2);
  return nr1;
}

HASH->charset->coll->hash_sortの関数を使って、ハッシュ値を計算する。

たとえばtable_def_cacheでは、hash_sortにmy_hash_sort_binが使用される。

fdvpeyegbrfdvpeyegbr 2007/03/15 18:05 Hi! Very nice site! Thanks you very much! codngfcfzvv

fkojrmijmqfkojrmijmq 2007/03/16 08:07 <a href=http://khzfsibj.com>myjaxrqbr</a>

トラックバック - http://d.hatena.ne.jp/a_ogawa/20060415

2006-03-29

[] innodbのレコードの構造

レコードのフォーマットはrem0rec.cに詳しい説明がある。

OLD STYLEとNEW STYLEの2種類がある。

(MySQL Internals Manualの説明はOLD STYLEのもの)

index->table->compが1だとNEW STYLE。

compはdict_mem_table_create()で設定している。

ha_innobase::create -> create_table_def -> dict_mem_table_create

create tableで、row_format=redundantのとき、compがFALSEになる。

それ以外(default, compressedなど)のときは、compはTRUEになる。

指定しなかったときもTRUEになる。

システムカタログ(SYS_TABLESなど)は、comp = FALSE。

MySQL 5.0.3 Release Notes
---------------------------------------------------------------------
InnoDB: Introduced a compact record format that does not store
the number of columns or the lengths of fixed-size columns.
The old format can be requested by specifying ROW_FORMAT=REDUNDANT.
The new format (ROW_FORMAT=COMPACT) is the default. 
---------------------------------------------------------------------

OLD_STYLEのRecord Format

Record Formatは、大きくわけて3つのデータからなる。

(1)データへのオフセットリスト

最終フィールドから順に設定される。

(2)レコードの情報 (6bytes)

各種フラグや次のレコードへのポインタなど、レコードの情報が格納される。

(3)データ

データリスト。各フィールドのデータは、オフセットリストで指定された位置に存在する。

レコードの先頭アドレス(Origin of the record)は、データリストの先頭位置が使用される。オフセットリストに指定されるオフセットは、これが基点になるので、先頭フィールドのオフセットは0。

以下のようなレイアウトになる。

 最終フィールドのデータ末尾のoffset
 ......
 2番目のフィールドのデータ末尾のoffset
 先頭フィールドのデータ末尾のoffset
 レコード情報(6 bytes)
                        <---- ここがOrigin of the recordのポインタ
 先頭フィールドのデータ
 2番目のフィールドのデータ
 ......
 最終フィールドのデータ

オフセットについて:オフセットの先頭ビットはNULLフラグとして使用される。レコード長(データの長さの合計値)が127byte未満のときは、各フィールドのオフセットは1byteで表現される。それ以上のときは2byte使う。オフセット長が1byteか2byteかどうかは、レコード情報のフラグに設定される。

また、2byteのときは、2番目のビットはデータが別ページに保存されたことを示すフラグとして使用される。

オフセットには各フィールドの末尾の位置が設定されるので、あるフィールドの先頭のオフセットを知りたいときは、1つ前のフィールドのオフセットを見る。

レコード情報のレイアウトは以下のとおり。

 未使用 (2 bits)
 削除フラグ (1 bit)
 min_rec_flag (1 bit)
 このレコードが保持しているレコード数 (4 bits)
 レコード番号 (13 bits)
 フィールドの数 (10 bits)
 1byteオフセットフラグ (1 bit)  1だったらオフセットは1byte。0だったら2byte。
 次のレコードへのポインタ (16 bits)

NEW_STYLEのRecord Format

NEW_STYLEはレコードサイズが小さくなるように、以下の工夫をしている

(1)各レコードにフィールド数をもたない

(2)オフセットではなく、データ長をもつ

(3)各レコードに固定長のデータ長はもたない

(4)NULLフィールドのデータ長はもたない

レコードのレイアウトは以下のようになる。

 可変長でNULLではない最終フィールドの長さ
 ......
 可変長でNULLではない先頭フィールドの長さ
 NULLフラグ(NULLが許可されているフィールドにつき1bit。byte単位で確保される)
 レコード情報 (4 bytes)
   <-- Origin of the record
 先頭レコードのデータ
 ......
 最終レコードのデータ

フィールド長:
 テーブル定義のフィールド長が255bytes以内のときは、1byte(0〜255)。
 フィールド長が256bytes以上のときは、以下のようになる
  データ長が127bytes以内のときは1byte。(0〜127)
  データ長が128以上のときは2byteが使用される。先頭ビットは常に1で、
  2番目のビットはextern storage flagとして使用される。データ長として
  使用できるのは14 bits(128〜16383)。

レコード情報:
 未使用 (2 bits)
 削除フラグ (1 bit)
 min_rec_flag (1 bit)
 このレコードが保持しているレコード数 (4 bits)
 レコード番号 (13 bits)
 レコードタイプ (3 bits)
 次のレコードへのポインタ (16 bits)

レコードタイプ:
 000: conventional
 001: node pointer (inside B-tree)
 010: infimum
 011: supremum
 1xx: reserved

システムカラム

各レコードの先頭には、以下のシステム用のカラムが追加される。

(1)Row ID (6 bytes)

(2)Transaction ID (6 bytes)

(3)Rollback pointer (7 bytes)

ただし、Primary keyが定義されているときは、Row IDの代わりにPrimary keyが使用される。

Primary keyなし
 Row ID
 Transaction ID
 Rollback pointer
 ユーザー定義のカラム1
 ユーザー定義のカラム2
 .....

Primary keyあり
 Primary key (ユーザー定義のカラム1)
 Transaction ID
 Rollback pointer
 ユーザー定義のカラム2
 .....

bgxpthkgygbgxpthkgyg 2007/03/15 18:05 Hi! Very nice site! Thanks you very much! iakuvpclqvmce

wbzzitauozwbzzitauoz 2007/03/16 08:07 <a href=http://vyuacobck.com>ceyexj</a>

トラックバック - http://d.hatena.ne.jp/a_ogawa/20060329

2006-02-13

[] mysql-5.1のstorage engine

storage engineの実装は、storageディレクトリにある

bdb heap innobase myisam myisammrg ndbがある

storage engineのインタフェースには、handlerとhandlertonがある

handlerはinsertやselectなど、テーブルを操作するインターフェースを定義したclass。sql/handler.hで定義されている。各storage engineは、handlerを継承してstorage engineごとのテーブル操作を実装している。handlerのインスタンスは、各テーブルの操作ごとに生成される。例えばinnodbのAAAというテーブルを検索するとき、AAAを操作するためのha_innobase(innodbのhandler)が生成(new)される。

handlerton(handler + singleton)は、各storage engineにつき1つだけ実体を持つ構造体。sql/handler.hで定義されている。storage engineの情報や、storage engineを操作するためのインタフェースを定義している。handlertonには、handlerを生成する関数や、commit/rollbackなどstorage engine全体を操作する関数が設定される。

innodbのhandlertonとhandlerは、sql/ha_innodb.ccに定義されている。

gdb memo

callコマンドで関数を実行できる。

例) innodbのrecordの情報を出力する

(1)ブレークポイントを設定

break rec_init_offsets

(2)ブレークしたらデバッグ用の関数を実行

call rec_print(stderr, rec, index)
continue

これでmysqlのerrファイル(mysqlhome/varにある)に出力される

出力例)

PHYSICAL RECORD: n_fields 6; compact format; info bits 0
 0: len 4; hex 80000001; asc     ;;
 1: len 6; hex 000000000302; asc       ;;
 2: len 7; hex 800000002d0110; asc     -  ;;
 3: len 4; hex 80000001; asc     ;;
 4: len 4; hex 80000000; asc     ;;
 5: len 1; hex 41; asc A;;

[] Improve the comparison of NUMERIC data

patch applied.

http://archives.postgresql.org/pgsql-patches/2006-02/msg00080.php

crgkftiucocrgkftiuco 2007/03/15 18:05 Hi! Very nice site! Thanks you very much! rcuduughahy

whscyzuseswhscyzuses 2007/03/16 08:08 <a href=http://mrdpuvjb.com>tiknm</a>

トラックバック - http://d.hatena.ne.jp/a_ogawa/20060213

2005-12-01

[] Allow an alias for the target table in UPDATE/DELETE

UPDATE accounts AS a SET a.abalance = a.abalance + 10 WHERE a.aid = 1;

のようにupdateやdelete対象のテーブルに、別名をつけることが出来るようにするパッチ。

http://www.hi-ho.ne.jp/a_ogawa/document/patches/allow_alias_update.patch

sknhmrskkbsknhmrskkb 2007/03/15 18:05 Hi! Very nice site! Thanks you very much! pttsviumoao

aanmeehnbkaanmeehnbk 2007/03/16 08:07 <a href=http://jjkiblb.com>xaxoqv</a>

トラックバック - http://d.hatena.ne.jp/a_ogawa/20051201

2005-11-21

[] Virtual tuple slots versus TOAST: big problem

TOASTが必要なTupleをinsert/updateした時、backendがcrushする問題について。

http://archives.postgresql.org/pgsql-hackers/2005-11/msg01016.php

(1)ExecInsertにTupleTableSlot(slot)が渡される。

このときslotのvirtual tuple領域(slot->tts_valuesなど)にデータが設定されている。

(2)ExecMaterializeSlotでslotのvirtual tupleから、physical tuple(slot->tts_tuple)に変換する。slotのvirtual tupleはクリアされる。

(3)ExecConstraintsで制約チェックを実行する。

slotのphysical tupleからチェックするカラムのデータを取り出す。このとき、取り出したカラムとそれより前にあるカラムのデータはslotのvirtual tuple領域にcacheされる。

(4)heap_insertにslotのphysical tupleを渡して、ページにtupleを登録する。

heap_insertでは、tupleサイズがTOAST_TUPLE_THRESHOLDより大きい場合、heap_tuple_toast_attrsを実行する。heap_tuple_toast_attrsは、tupleを上書きして再構成するため、tupleのサイズや各カラムのデータの位置などが変わる。

(*)ここでslotのphysical tupleとvirtual tuple cacheの情報が矛盾してしまう

(5)(ExecInsertに戻って)ExecInsertIndexTuplesを実行してindexにデータを登録するとき、index用のtupleを構築するためにslotのphysical tupleまたはvirtual tupleから、indexに必要なカラムのデータを取り出す。

virtual tupleの情報はphysical tupleの情報と矛盾しているため、virtual tupleの情報を参照したときに正しくない位置のメモリを読んでしまい、backendがcrushするか、間違ったデータを取り出してしまう。

updateについても同様の問題が発生する。

当面の解決策はheap_insert/heap_updateの実行後にvirtual tuple cacheを無効にすること。

トラックバック - http://d.hatena.ne.jp/a_ogawa/20051121