← Back to branch summary

~drizzle-trunk/drizzle/development

« back to all changes in this revision

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

  • Committer: Lee Bieber
  • Date: 2010-12-03 01:16:19 UTC
  • mfrom: (1819.9.81 update-innobase)
  • Revision ID: kalebral@gmail.com-20101203011619-n6v584rijwdet05b
Merge Stewart - update Innobase plugin based on InnoDB 1.1.2

Show diffs side-by-side

added added

removed removed

Lines of Context:
plugin/innobase/btr/btr0cur.c
660
660
                buf_block_dbg_add_level(block, SYNC_TREE_NODE);
661
661
        }
662
662
 
663
 
        ut_ad(0 == ut_dulint_cmp(index->id, btr_page_get_index_id(page)));
 
663
        ut_ad(index->id == btr_page_get_index_id(page));
664
664
 
665
665
        if (UNIV_UNLIKELY(height == ULINT_UNDEFINED)) {
666
666
                /* We are in the root node */
854
854
                                         RW_NO_LATCH, NULL, BUF_GET,
855
855
                                         file, line, mtr);
856
856
                page = buf_block_get_frame(block);
857
 
                ut_ad(0 == ut_dulint_cmp(index->id,
858
 
                                         btr_page_get_index_id(page)));
 
857
                ut_ad(index->id == btr_page_get_index_id(page));
859
858
 
860
859
                block->check_index_page_at_flush = TRUE;
861
860
 
975
974
                                         RW_NO_LATCH, NULL, BUF_GET,
976
975
                                         file, line, mtr);
977
976
                page = buf_block_get_frame(block);
978
 
                ut_ad(0 == ut_dulint_cmp(index->id,
979
 
                                         btr_page_get_index_id(page)));
 
977
                ut_ad(index->id == btr_page_get_index_id(page));
980
978
 
981
979
                if (height == ULINT_UNDEFINED) {
982
980
                        /* We are in the root node */
1135
1133
        const char*             op)     /*!< in: operation */
1136
1134
{
1137
1135
        fprintf(stderr, "Trx with id " TRX_ID_FMT " going to ",
1138
 
                TRX_ID_PREP_PRINTF(trx->id));
 
1136
                (ullint) trx->id);
1139
1137
        fputs(op, stderr);
1140
1138
        dict_index_name_print(stderr, trx, index);
1141
1139
        putc('\n', stderr);
1826
1824
        page_zip_des_t* page_zip;
1827
1825
        ulint           err;
1828
1826
        rec_t*          rec;
1829
 
        roll_ptr_t      roll_ptr        = ut_dulint_zero;
 
1827
        roll_ptr_t      roll_ptr        = 0;
1830
1828
        trx_t*          trx;
1831
1829
        ulint           was_delete_marked;
1832
1830
        mem_heap_t*     heap            = NULL;
3155
3153
{
3156
3154
        btr_path_t*     slot;
3157
3155
        rec_t*          rec;
 
3156
        page_t*         page;
3158
3157
 
3159
3158
        ut_a(cursor->path_arr);
3160
3159
 
3177
3176
 
3178
3177
        slot = cursor->path_arr + (root_height - height);
3179
3178
 
 
3179
        page = page_align(rec);
 
3180
 
3180
3181
        slot->nth_rec = page_rec_get_n_recs_before(rec);
3181
 
        slot->n_recs = page_get_n_recs(page_align(rec));
 
3182
        slot->n_recs = page_get_n_recs(page);
 
3183
        slot->page_no = page_get_page_no(page);
 
3184
        slot->page_level = btr_page_get_level_low(page);
 
3185
}
 
3186
 
 
3187
/*******************************************************************//**
 
3188
Estimate the number of rows between slot1 and slot2 for any level on a
 
3189
B-tree. This function starts from slot1->page and reads a few pages to
 
3190
the right, counting their records. If we reach slot2->page quickly then
 
3191
we know exactly how many records there are between slot1 and slot2 and
 
3192
we set is_n_rows_exact to TRUE. If we cannot reach slot2->page quickly
 
3193
then we calculate the average number of records in the pages scanned
 
3194
so far and assume that all pages that we did not scan up to slot2->page
 
3195
contain the same number of records, then we multiply that average to
 
3196
the number of pages between slot1->page and slot2->page (which is
 
3197
n_rows_on_prev_level). In this case we set is_n_rows_exact to FALSE.
 
3198
@return number of rows (exact or estimated) */
 
3199
static
 
3200
ib_int64_t
 
3201
btr_estimate_n_rows_in_range_on_level(
 
3202
/*==================================*/
 
3203
        dict_index_t*   index,                  /*!< in: index */
 
3204
        btr_path_t*     slot1,                  /*!< in: left border */
 
3205
        btr_path_t*     slot2,                  /*!< in: right border */
 
3206
        ib_int64_t      n_rows_on_prev_level,   /*!< in: number of rows
 
3207
                                                on the previous level for the
 
3208
                                                same descend paths; used to
 
3209
                                                determine the numbe of pages
 
3210
                                                on this level */
 
3211
        ibool*          is_n_rows_exact)        /*!< out: TRUE if the returned
 
3212
                                                value is exact i.e. not an
 
3213
                                                estimation */
 
3214
{
 
3215
        ulint           space;
 
3216
        ib_int64_t      n_rows;
 
3217
        ulint           n_pages_read;
 
3218
        ulint           page_no;
 
3219
        ulint           zip_size;
 
3220
        ulint           level;
 
3221
 
 
3222
        space = dict_index_get_space(index);
 
3223
 
 
3224
        n_rows = 0;
 
3225
        n_pages_read = 0;
 
3226
 
 
3227
        /* Assume by default that we will scan all pages between
 
3228
        slot1->page_no and slot2->page_no */
 
3229
        *is_n_rows_exact = TRUE;
 
3230
 
 
3231
        /* add records from slot1->page_no which are to the right of
 
3232
        the record which serves as a left border of the range, if any */
 
3233
        if (slot1->nth_rec < slot1->n_recs) {
 
3234
                n_rows += slot1->n_recs - slot1->nth_rec;
 
3235
        }
 
3236
 
 
3237
        /* add records from slot2->page_no which are to the left of
 
3238
        the record which servers as a right border of the range, if any */
 
3239
        if (slot2->nth_rec > 1) {
 
3240
                n_rows += slot2->nth_rec - 1;
 
3241
        }
 
3242
 
 
3243
        /* count the records in the pages between slot1->page_no and
 
3244
        slot2->page_no (non inclusive), if any */
 
3245
 
 
3246
        zip_size = fil_space_get_zip_size(space);
 
3247
 
 
3248
        /* Do not read more than this number of pages in order not to hurt
 
3249
        performance with this code which is just an estimation. If we read
 
3250
        this many pages before reaching slot2->page_no then we estimate the
 
3251
        average from the pages scanned so far */
 
3252
        #define N_PAGES_READ_LIMIT      10
 
3253
 
 
3254
        page_no = slot1->page_no;
 
3255
        level = slot1->page_level;
 
3256
 
 
3257
        do {
 
3258
                mtr_t           mtr;
 
3259
                page_t*         page;
 
3260
                buf_block_t*    block;
 
3261
 
 
3262
                mtr_start(&mtr);
 
3263
 
 
3264
                /* fetch the page */
 
3265
                block = buf_page_get(space, zip_size, page_no, RW_S_LATCH,
 
3266
                                     &mtr);
 
3267
 
 
3268
                page = buf_block_get_frame(block);
 
3269
 
 
3270
                /* It is possible that the tree has been reorganized in the
 
3271
                meantime and this is a different page. If this happens the
 
3272
                calculated estimate will be bogus, which is not fatal as
 
3273
                this is only an estimate. We are sure that a page with
 
3274
                page_no exists because InnoDB never frees pages, only
 
3275
                reuses them. */
 
3276
                if (fil_page_get_type(page) != FIL_PAGE_INDEX
 
3277
                    || btr_page_get_index_id(page) != index->id
 
3278
                    || btr_page_get_level_low(page) != level) {
 
3279
 
 
3280
                        /* The page got reused for something else */
 
3281
                        goto inexact;
 
3282
                }
 
3283
 
 
3284
                n_pages_read++;
 
3285
 
 
3286
                if (page_no != slot1->page_no) {
 
3287
                        /* Do not count the records on slot1->page_no,
 
3288
                        we already counted them before this loop. */
 
3289
                        n_rows += page_get_n_recs(page);
 
3290
                }
 
3291
 
 
3292
                page_no = btr_page_get_next(page, &mtr);
 
3293
 
 
3294
                mtr_commit(&mtr);
 
3295
 
 
3296
                if (n_pages_read == N_PAGES_READ_LIMIT
 
3297
                    || page_no == FIL_NULL) {
 
3298
                        /* Either we read too many pages or
 
3299
                        we reached the end of the level without passing
 
3300
                        through slot2->page_no, the tree must have changed
 
3301
                        in the meantime */
 
3302
                        goto inexact;
 
3303
                }
 
3304
 
 
3305
        } while (page_no != slot2->page_no);
 
3306
 
 
3307
        return(n_rows);
 
3308
 
 
3309
inexact:
 
3310
 
 
3311
        *is_n_rows_exact = FALSE;
 
3312
 
 
3313
        /* We did interrupt before reaching slot2->page */
 
3314
 
 
3315
        if (n_pages_read > 0) {
 
3316
                /* The number of pages on this level is
 
3317
                n_rows_on_prev_level, multiply it by the
 
3318
                average number of recs per page so far */
 
3319
                n_rows = n_rows_on_prev_level
 
3320
                        * n_rows / n_pages_read;
 
3321
        } else {
 
3322
                /* The tree changed before we could even
 
3323
                start with slot1->page_no */
 
3324
                n_rows = 10;
 
3325
        }
 
3326
 
 
3327
        return(n_rows);
3182
3328
}
3183
3329
 
3184
3330
/*******************************************************************//**
3203
3349
        ibool           diverged_lot;
3204
3350
        ulint           divergence_level;
3205
3351
        ib_int64_t      n_rows;
 
3352
        ibool           is_n_rows_exact;
3206
3353
        ulint           i;
3207
3354
        mtr_t           mtr;
3208
3355
 
3245
3392
        /* We have the path information for the range in path1 and path2 */
3246
3393
 
3247
3394
        n_rows = 1;
 
3395
        is_n_rows_exact = TRUE;
3248
3396
        diverged = FALSE;           /* This becomes true when the path is not
3249
3397
                                    the same any more */
3250
3398
        diverged_lot = FALSE;       /* This becomes true when the paths are
3260
3408
                if (slot1->nth_rec == ULINT_UNDEFINED
3261
3409
                    || slot2->nth_rec == ULINT_UNDEFINED) {
3262
3410
 
3263
 
                        if (i > divergence_level + 1) {
 
3411
                        if (i > divergence_level + 1 && !is_n_rows_exact) {
3264
3412
                                /* In trees whose height is > 1 our algorithm
3265
3413
                                tends to underestimate: multiply the estimate
3266
3414
                                by 2: */
3272
3420
                        to over 1 / 2 of the estimated rows in the whole
3273
3421
                        table */
3274
3422
 
3275
 
                        if (n_rows > index->table->stat_n_rows / 2) {
 
3423
                        if (n_rows > index->table->stat_n_rows / 2
 
3424
                            && !is_n_rows_exact) {
 
3425
 
3276
3426
                                n_rows = index->table->stat_n_rows / 2;
3277
3427
 
3278
3428
                                /* If there are just 0 or 1 rows in the table,
3298
3448
                                        divergence_level = i;
3299
3449
                                }
3300
3450
                        } else {
3301
 
                                /* Maybe the tree has changed between
3302
 
                                searches */
3303
 
 
3304
 
                                return(10);
 
3451
                                /* It is possible that
 
3452
                                slot1->nth_rec >= slot2->nth_rec
 
3453
                                if, for example, we have a single page
 
3454
                                tree which contains (inf, 5, 6, supr)
 
3455
                                and we select where x > 20 and x < 30;
 
3456
                                in this case slot1->nth_rec will point
 
3457
                                to the supr record and slot2->nth_rec
 
3458
                                will point to 6 */
 
3459
                                n_rows = 0;
3305
3460
                        }
3306
3461
 
3307
3462
                } else if (diverged && !diverged_lot) {
3325
3480
                        }
3326
3481
                } else if (diverged_lot) {
3327
3482
 
3328
 
                        n_rows = (n_rows * (slot1->n_recs + slot2->n_recs))
3329
 
                                / 2;
 
3483
                        n_rows = btr_estimate_n_rows_in_range_on_level(
 
3484
                                index, slot1, slot2, n_rows,
 
3485
                                &is_n_rows_exact);
3330
3486
                }
3331
3487
        }
3332
3488
}
4936
5092
 
4937
5093
/*******************************************************************//**
4938
5094
Copies an externally stored field of a record to mem heap.
4939
 
@return the field copied to heap */
 
5095
@return the field copied to heap, or NULL if the field is incomplete */
4940
5096
UNIV_INTERN
4941
5097
byte*
4942
5098
btr_rec_copy_externally_stored_field(
4966
5122
 
4967
5123
        data = rec_get_nth_field(rec, offsets, no, &local_len);
4968
5124
 
 
5125
        ut_a(local_len >= BTR_EXTERN_FIELD_REF_SIZE);
 
5126
 
 
5127
        if (UNIV_UNLIKELY
 
5128
            (!memcmp(data + local_len - BTR_EXTERN_FIELD_REF_SIZE,
 
5129
                     field_ref_zero, BTR_EXTERN_FIELD_REF_SIZE))) {
 
5130
                /* The externally stored field was not written yet.
 
5131
                This record should only be seen by
 
5132
                recv_recovery_rollback_active() or any
 
5133
                TRX_ISO_READ_UNCOMMITTED transactions. */
 
5134
                return(NULL);
 
5135
        }
 
5136
 
4969
5137
        return(btr_copy_externally_stored_field(len, data,
4970
5138
                                                zip_size, local_len, heap));
4971
5139
}