← Back to branch summary

~drizzle-trunk/drizzle/development

« back to all changes in this revision

Viewing changes to plugin/innobase/btr/btr0btr.c

  • Committer: Brian Aker
  • Date: 2010-10-20 20:26:18 UTC
  • mfrom: (1859.2.13 refactor)
  • Revision ID: brian@tangent.org-20101020202618-9222n39lm329urv5
Merge for Brian 

Show diffs side-by-side

added added

removed removed

Lines of Context:
plugin/innobase/btr/btr0btr.c
1
1
/*****************************************************************************
2
2
 
3
 
Copyright (C) 1994, 2010, Innobase Oy. All Rights Reserved.
 
3
Copyright (c) 1994, 2009, Innobase Oy. All Rights Reserved.
4
4
 
5
5
This program is free software; you can redistribute it and/or modify it under
6
6
the terms of the GNU General Public License as published by the Free Software
592
592
@return rec_get_offsets() of the node pointer record */
593
593
static
594
594
ulint*
595
 
btr_page_get_father_node_ptr_func(
596
 
/*==============================*/
 
595
btr_page_get_father_node_ptr(
 
596
/*=========================*/
597
597
        ulint*          offsets,/*!< in: work area for the return value */
598
598
        mem_heap_t*     heap,   /*!< in: memory heap to use */
599
599
        btr_cur_t*      cursor, /*!< in: cursor pointing to user record,
600
600
                                out: cursor on node pointer record,
601
601
                                its page x-latched */
602
 
        const char*     file,   /*!< in: file name */
603
 
        ulint           line,   /*!< in: line where called */
604
602
        mtr_t*          mtr)    /*!< in: mtr */
605
603
{
606
604
        dtuple_t*       tuple;
619
617
        ut_ad(dict_index_get_page(index) != page_no);
620
618
 
621
619
        level = btr_page_get_level(btr_cur_get_page(cursor), mtr);
622
 
 
623
620
        user_rec = btr_cur_get_rec(cursor);
624
621
        ut_a(page_rec_is_user_rec(user_rec));
625
622
        tuple = dict_index_build_node_ptr(index, user_rec, 0, heap, level);
626
623
 
627
624
        btr_cur_search_to_nth_level(index, level + 1, tuple, PAGE_CUR_LE,
628
 
                                    BTR_CONT_MODIFY_TREE, cursor, 0,
629
 
                                    file, line, mtr);
 
625
                                    BTR_CONT_MODIFY_TREE, cursor, 0, mtr);
630
626
 
631
627
        node_ptr = btr_cur_get_rec(cursor);
632
628
        ut_ad(!page_rec_is_comp(node_ptr)
674
670
        return(offsets);
675
671
}
676
672
 
677
 
#define btr_page_get_father_node_ptr(of,heap,cur,mtr)                   \
678
 
        btr_page_get_father_node_ptr_func(of,heap,cur,__FILE__,__LINE__,mtr)
679
 
 
680
673
/************************************************************//**
681
674
Returns the upper level node pointer to a page. It is assumed that mtr holds
682
675
an x-latch on the tree.
735
728
        ulint           space,  /*!< in: space where created */
736
729
        ulint           zip_size,/*!< in: compressed page size in bytes
737
730
                                or 0 for uncompressed pages */
738
 
        index_id_t      index_id,/*!< in: index id */
 
731
        dulint          index_id,/*!< in: index id */
739
732
        dict_index_t*   index,  /*!< in: index */
740
733
        mtr_t*          mtr)    /*!< in: mini-transaction handle */
741
734
{
931
924
        ut_a(btr_root_fseg_validate(header, space));
932
925
#endif /* UNIV_BTR_DEBUG */
933
926
 
934
 
        while (!fseg_free_step(header, mtr)) {};
 
927
        while (!fseg_free_step(header, mtr));
935
928
}
936
929
#endif /* !UNIV_HOTBACKUP */
937
930
 
950
943
        dict_index_t*   index,  /*!< in: record descriptor */
951
944
        mtr_t*          mtr)    /*!< in: mtr */
952
945
{
953
 
        buf_pool_t*     buf_pool        = buf_pool_from_bpage(&block->page);
954
946
        page_t*         page            = buf_block_get_frame(block);
955
947
        page_zip_des_t* page_zip        = buf_block_get_page_zip(block);
956
948
        buf_block_t*    temp_block;
981
973
        log_mode = mtr_set_log_mode(mtr, MTR_LOG_NONE);
982
974
 
983
975
#ifndef UNIV_HOTBACKUP
984
 
        temp_block = buf_block_alloc(buf_pool, 0);
 
976
        temp_block = buf_block_alloc(0);
985
977
#else /* !UNIV_HOTBACKUP */
986
978
        ut_ad(block == back_block1);
987
979
        temp_block = back_block2;
1018
1010
                /* In crash recovery, dict_index_is_sec_or_ibuf() always
1019
1011
                returns TRUE, even for clustered indexes.  max_trx_id is
1020
1012
                unused in clustered index pages. */
1021
 
                ut_ad(max_trx_id != 0 || recovery);
 
1013
                ut_ad(!ut_dulint_is_zero(max_trx_id) || recovery);
1022
1014
        }
1023
1015
 
1024
1016
        if (UNIV_LIKELY_NULL(page_zip)
1120
1112
btr_parse_page_reorganize(
1121
1113
/*======================*/
1122
1114
        byte*           ptr,    /*!< in: buffer */
1123
 
        byte*           /*end_ptr __attribute__((unused))*/,
 
1115
        byte*           end_ptr __attribute__((unused)),
1124
1116
                                /*!< in: buffer end */
1125
1117
        dict_index_t*   index,  /*!< in: record descriptor */
1126
1118
        buf_block_t*    block,  /*!< in: page to be reorganized, or NULL */
1453
1445
its half-page when the split is performed. We assume in this function
1454
1446
only that the cursor page has at least one user record.
1455
1447
@return split record, or NULL if tuple will be the first record on
1456
 
the lower or upper half-page (determined by btr_page_tuple_smaller()) */
 
1448
upper half-page */
1457
1449
static
1458
1450
rec_t*
1459
 
btr_page_get_split_rec(
1460
 
/*===================*/
 
1451
btr_page_get_sure_split_rec(
 
1452
/*========================*/
1461
1453
        btr_cur_t*      cursor, /*!< in: cursor at which insert should be made */
1462
1454
        const dtuple_t* tuple,  /*!< in: tuple to insert */
1463
1455
        ulint           n_ext)  /*!< in: number of externally stored columns */
1670
1662
that mtr holds an x-latch on the tree. */
1671
1663
UNIV_INTERN
1672
1664
void
1673
 
btr_insert_on_non_leaf_level_func(
1674
 
/*==============================*/
 
1665
btr_insert_on_non_leaf_level(
 
1666
/*=========================*/
1675
1667
        dict_index_t*   index,  /*!< in: index */
1676
1668
        ulint           level,  /*!< in: level, must be > 0 */
1677
1669
        dtuple_t*       tuple,  /*!< in: the record to be inserted */
1678
 
        const char*     file,   /*!< in: file name */
1679
 
        ulint           line,   /*!< in: line where called */
1680
1670
        mtr_t*          mtr)    /*!< in: mtr */
1681
1671
{
1682
1672
        big_rec_t*      dummy_big_rec;
1688
1678
 
1689
1679
        btr_cur_search_to_nth_level(index, level, tuple, PAGE_CUR_LE,
1690
1680
                                    BTR_CONT_MODIFY_TREE,
1691
 
                                    &cursor, 0, file, line, mtr);
 
1681
                                    &cursor, 0, mtr);
1692
1682
 
1693
1683
        err = btr_cur_pessimistic_insert(BTR_NO_LOCKING_FLAG
1694
1684
                                         | BTR_KEEP_SYS_FLAG
1834
1824
}
1835
1825
 
1836
1826
/*************************************************************//**
1837
 
Determine if a tuple is smaller than any record on the page.
1838
 
@return TRUE if smaller */
1839
 
static
1840
 
ibool
1841
 
btr_page_tuple_smaller(
1842
 
/*===================*/
1843
 
        btr_cur_t*      cursor, /*!< in: b-tree cursor */
1844
 
        const dtuple_t* tuple,  /*!< in: tuple to consider */
1845
 
        ulint*          offsets,/*!< in/out: temporary storage */
1846
 
        ulint           n_uniq, /*!< in: number of unique fields
1847
 
                                in the index page records */
1848
 
        mem_heap_t**    heap)   /*!< in/out: heap for offsets */
1849
 
{
1850
 
        buf_block_t*    block;
1851
 
        const rec_t*    first_rec;
1852
 
        page_cur_t      pcur;
1853
 
 
1854
 
        /* Read the first user record in the page. */
1855
 
        block = btr_cur_get_block(cursor);
1856
 
        page_cur_set_before_first(block, &pcur);
1857
 
        page_cur_move_to_next(&pcur);
1858
 
        first_rec = page_cur_get_rec(&pcur);
1859
 
 
1860
 
        offsets = rec_get_offsets(
1861
 
                first_rec, cursor->index, offsets,
1862
 
                n_uniq, heap);
1863
 
 
1864
 
        return(cmp_dtuple_rec(tuple, first_rec, offsets) < 0);
1865
 
}
1866
 
 
1867
 
/*************************************************************//**
1868
1827
Splits an index page to halves and inserts the tuple. It is assumed
1869
1828
that mtr holds an x-latch to the index tree. NOTE: the tree x-latch is
1870
1829
released within this function! NOTE that the operation of this
1897
1856
        buf_block_t*    left_block;
1898
1857
        buf_block_t*    right_block;
1899
1858
        buf_block_t*    insert_block;
 
1859
        page_t*         insert_page;
1900
1860
        page_cur_t*     page_cursor;
1901
1861
        rec_t*          first_rec;
1902
1862
        byte*           buf = 0; /* remove warning */
1933
1893
        /* 1. Decide the split record; split_rec == NULL means that the
1934
1894
        tuple to be inserted should be the first record on the upper
1935
1895
        half-page */
1936
 
        insert_left = FALSE;
1937
1896
 
1938
1897
        if (n_iterations > 0) {
1939
1898
                direction = FSP_UP;
1940
1899
                hint_page_no = page_no + 1;
1941
 
                split_rec = btr_page_get_split_rec(cursor, tuple, n_ext);
 
1900
                split_rec = btr_page_get_sure_split_rec(cursor, tuple, n_ext);
1942
1901
 
1943
 
                if (UNIV_UNLIKELY(split_rec == NULL)) {
1944
 
                        insert_left = btr_page_tuple_smaller(
1945
 
                                cursor, tuple, offsets, n_uniq, &heap);
1946
 
                }
1947
1902
        } else if (btr_page_get_split_rec_to_right(cursor, &split_rec)) {
1948
1903
                direction = FSP_UP;
1949
1904
                hint_page_no = page_no + 1;
 
1905
 
1950
1906
        } else if (btr_page_get_split_rec_to_left(cursor, &split_rec)) {
1951
1907
                direction = FSP_DOWN;
1952
1908
                hint_page_no = page_no - 1;
1953
 
                ut_ad(split_rec);
1954
1909
        } else {
1955
1910
                direction = FSP_UP;
1956
1911
                hint_page_no = page_no + 1;
1957
 
                /* If there is only one record in the index page, we
1958
 
                can't split the node in the middle by default. We need
1959
 
                to determine whether the new record will be inserted
1960
 
                to the left or right. */
1961
 
 
1962
 
                if (page_get_n_recs(page) > 1) {
1963
 
                  split_rec = page_get_middle_rec(page);
1964
 
                } else if (btr_page_tuple_smaller(cursor, tuple,
1965
 
                                                  offsets, n_uniq, &heap)) {
1966
 
                        split_rec = page_rec_get_next(
1967
 
                                page_get_infimum_rec(page));
 
1912
 
 
1913
                if (page_get_n_recs(page) == 1) {
 
1914
                        page_cur_t      pcur;
 
1915
 
 
1916
                        /* There is only one record in the index page
 
1917
                        therefore we can't split the node in the middle
 
1918
                        by default. We need to determine whether the
 
1919
                        new record will be inserted to the left or right. */
 
1920
 
 
1921
                        /* Read the first (and only) record in the page. */
 
1922
                        page_cur_set_before_first(block, &pcur);
 
1923
                        page_cur_move_to_next(&pcur);
 
1924
                        first_rec = page_cur_get_rec(&pcur);
 
1925
 
 
1926
                        offsets = rec_get_offsets(
 
1927
                                first_rec, cursor->index, offsets,
 
1928
                                n_uniq, &heap);
 
1929
 
 
1930
                        /* If the new record is less than the existing record
 
1931
                        the the split in the middle will copy the existing
 
1932
                        record to the new node. */
 
1933
                        if (cmp_dtuple_rec(tuple, first_rec, offsets) < 0) {
 
1934
                                split_rec = page_get_middle_rec(page);
 
1935
                        } else {
 
1936
                                split_rec = NULL;
 
1937
                        }
1968
1938
                } else {
1969
 
                        split_rec = NULL;
 
1939
                        split_rec = page_get_middle_rec(page);
1970
1940
                }
1971
1941
        }
1972
1942
 
1996
1966
                        avoid further splits by inserting the record
1997
1967
                        to an empty page. */
1998
1968
                        split_rec = NULL;
1999
 
                        goto insert_empty;
 
1969
                        goto insert_right;
2000
1970
                }
2001
 
        } else if (UNIV_UNLIKELY(insert_left)) {
2002
 
                ut_a(n_iterations > 0);
2003
 
                first_rec = page_rec_get_next(page_get_infimum_rec(page));
2004
 
                move_limit = page_rec_get_next(btr_cur_get_rec(cursor));
2005
1971
        } else {
2006
 
insert_empty:
2007
 
                ut_ad(!split_rec);
2008
 
                ut_ad(!insert_left);
2009
 
                buf = (unsigned char *)mem_alloc(rec_get_converted_size(cursor->index,
2010
 
                                                                        tuple, n_ext));
 
1972
insert_right:
 
1973
                insert_left = FALSE;
 
1974
                buf = mem_alloc(rec_get_converted_size(cursor->index,
 
1975
                                                       tuple, n_ext));
2011
1976
 
2012
1977
                first_rec = rec_convert_dtuple_to_rec(buf, cursor->index,
2013
1978
                                                      tuple, n_ext);
2029
1994
                        && btr_page_insert_fits(cursor, split_rec,
2030
1995
                                                offsets, tuple, n_ext, heap);
2031
1996
        } else {
2032
 
                if (!insert_left) {
2033
 
                        mem_free(buf);
2034
 
                        buf = NULL;
2035
 
                }
2036
 
 
 
1997
                mem_free(buf);
2037
1998
                insert_will_fit = !new_page_zip
2038
1999
                        && btr_page_insert_fits(cursor, NULL,
2039
2000
                                                NULL, tuple, n_ext, heap);
2152
2113
                insert_block = right_block;
2153
2114
        }
2154
2115
 
 
2116
        insert_page = buf_block_get_frame(insert_block);
 
2117
 
2155
2118
        /* 7. Reposition the cursor for insert and try insertion */
2156
2119
        page_cursor = btr_cur_get_page_cur(cursor);
2157
2120
 
2163
2126
 
2164
2127
#ifdef UNIV_ZIP_DEBUG
2165
2128
        {
2166
 
                page_t*         insert_page
2167
 
                        = buf_block_get_frame(insert_block);
2168
 
 
2169
2129
                page_zip_des_t* insert_page_zip
2170
2130
                        = buf_block_get_page_zip(insert_block);
2171
 
 
2172
2131
                ut_a(!insert_page_zip
2173
2132
                     || page_zip_validate(insert_page_zip, insert_page));
2174
2133
        }
2501
2460
 
2502
2461
        /* Go upward to root page, decrementing levels by one. */
2503
2462
        for (i = 0; i < n_blocks; i++, page_level++) {
2504
 
                page_t*         inner_page      = buf_block_get_frame(blocks[i]);
 
2463
                page_t*         page    = buf_block_get_frame(blocks[i]);
2505
2464
                page_zip_des_t* page_zip= buf_block_get_page_zip(blocks[i]);
2506
2465
 
2507
2466
                ut_ad(btr_page_get_level(page, mtr) == page_level + 1);
2508
2467
 
2509
 
                btr_page_set_level(inner_page, page_zip, page_level, mtr);
 
2468
                btr_page_set_level(page, page_zip, page_level, mtr);
2510
2469
#ifdef UNIV_ZIP_DEBUG
2511
 
                ut_a(!page_zip || page_zip_validate(page_zip, inner_page));
 
2470
                ut_a(!page_zip || page_zip_validate(page_zip, page));
2512
2471
#endif /* UNIV_ZIP_DEBUG */
2513
2472
        }
2514
2473
 
2561
2520
        ulint           n_recs;
2562
2521
        ulint           max_ins_size;
2563
2522
        ulint           max_ins_size_reorg;
 
2523
        ulint           level;
2564
2524
 
2565
2525
        block = btr_cur_get_block(cursor);
2566
2526
        page = btr_cur_get_page(cursor);
2570
2530
        ut_ad(mtr_memo_contains(mtr, dict_index_get_lock(index),
2571
2531
                                MTR_MEMO_X_LOCK));
2572
2532
        ut_ad(mtr_memo_contains(mtr, block, MTR_MEMO_PAGE_X_FIX));
 
2533
        level = btr_page_get_level(page, mtr);
2573
2534
        space = dict_index_get_space(index);
2574
2535
        zip_size = dict_table_zip_size(index->table);
2575
2536
 
2878
2839
                ibuf_reset_free_bits(block);
2879
2840
 
2880
2841
                if (page_is_leaf(buf_block_get_frame(block))) {
2881
 
                        ut_a(max_trx_id);
 
2842
                        ut_a(!ut_dulint_is_zero(max_trx_id));
2882
2843
                        page_set_max_trx_id(block,
2883
2844
                                            buf_block_get_page_zip(block),
2884
2845
                                            max_trx_id, mtr);