btr0sea.cc 58.8 KB
Newer Older
1 2
/*****************************************************************************

Sergei Golubchik's avatar
Sergei Golubchik committed
3
Copyright (c) 1996, 2016, Oracle and/or its affiliates. All Rights Reserved.
4
Copyright (c) 2008, Google Inc.
5
Copyright (c) 2017, 2020, MariaDB Corporation.
6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21

Portions of this file contain modifications contributed and copyrighted by
Google, Inc. Those modifications are gratefully acknowledged and are described
briefly in the InnoDB documentation. The contributions by Google are
incorporated with their permission, and subject to the conditions contained in
the file COPYING.Google.

This program is free software; you can redistribute it and/or modify it under
the terms of the GNU General Public License as published by the Free Software
Foundation; version 2 of the License.

This program is distributed in the hope that it will be useful, but WITHOUT
ANY WARRANTY; without even the implied warranty of MERCHANTABILITY or FITNESS
FOR A PARTICULAR PURPOSE. See the GNU General Public License for more details.

You should have received a copy of the GNU General Public License along with
22
this program; if not, write to the Free Software Foundation, Inc.,
Vicențiu Ciorbaru's avatar
Vicențiu Ciorbaru committed
23
51 Franklin Street, Fifth Floor, Boston, MA 02110-1335 USA
24 25 26

*****************************************************************************/

27
/********************************************************************//**
28
@file btr/btr0sea.cc
osku's avatar
osku committed
29 30 31 32 33 34
The index tree adaptive search

Created 2/17/1996 Heikki Tuuri
*************************************************************************/

#include "btr0sea.h"
35
#ifdef BTR_CUR_HASH_ADAPT
osku's avatar
osku committed
36 37 38 39 40 41
#include "buf0buf.h"
#include "page0page.h"
#include "page0cur.h"
#include "btr0cur.h"
#include "btr0pcur.h"
#include "btr0btr.h"
42
#include "srv0mon.h"
osku's avatar
osku committed
43

44 45
/** Is search system enabled.
Search system is protected by array of latches. */
46
char		btr_search_enabled;
47

48
/** Number of adaptive hash index partition. */
49
ulong		btr_ahi_parts;
osku's avatar
osku committed
50

51 52
#ifdef UNIV_SEARCH_PERF_STAT
/** Number of successful adaptive hash index lookups */
53
ulint		btr_search_n_succ	= 0;
54
/** Number of failed adaptive hash index lookups */
55
ulint		btr_search_n_hash_fail	= 0;
56 57
#endif /* UNIV_SEARCH_PERF_STAT */

58 59 60 61
#ifdef UNIV_PFS_RWLOCK
mysql_pfs_key_t	btr_search_latch_key;
#endif /* UNIV_PFS_RWLOCK */

62
/** The adaptive hash index */
63
btr_search_sys_t btr_search_sys;
64

65
/** If the number of records on the page divided by this parameter
osku's avatar
osku committed
66 67
would have been successfully accessed using a hash index, the index
is then built on the page, assuming the global limit has been reached */
68
#define BTR_SEARCH_PAGE_BUILD_LIMIT	16U
osku's avatar
osku committed
69

70
/** The global limit for consecutive potentially successful hash searches,
osku's avatar
osku committed
71
before hash index building is started */
72 73 74 75 76 77 78 79 80 81 82 83 84
#define BTR_SEARCH_BUILD_LIMIT		100U

/** Compute a hash value of a record in a page.
@param[in]	rec		index record
@param[in]	offsets		return value of rec_get_offsets()
@param[in]	n_fields	number of complete fields to fold
@param[in]	n_bytes		number of bytes to fold in the last field
@param[in]	index_id	index tree ID
@return the hash value */
static inline
ulint
rec_fold(
	const rec_t*	rec,
85
	const rec_offs*	offsets,
86 87 88 89 90 91 92 93 94 95 96 97 98
	ulint		n_fields,
	ulint		n_bytes,
	index_id_t	tree_id)
{
	ulint		i;
	const byte*	data;
	ulint		len;
	ulint		fold;
	ulint		n_fields_rec;

	ut_ad(rec_offs_validate(rec, NULL, offsets));
	ut_ad(rec_validate(rec, offsets));
	ut_ad(page_rec_is_leaf(rec));
99
	ut_ad(!page_rec_is_metadata(rec));
100 101 102 103 104 105 106 107 108 109 110 111 112 113 114 115 116 117 118 119 120 121 122 123 124 125 126 127 128 129 130 131 132 133 134 135 136 137 138 139
	ut_ad(n_fields > 0 || n_bytes > 0);

	n_fields_rec = rec_offs_n_fields(offsets);
	ut_ad(n_fields <= n_fields_rec);
	ut_ad(n_fields < n_fields_rec || n_bytes == 0);

	if (n_fields > n_fields_rec) {
		n_fields = n_fields_rec;
	}

	if (n_fields == n_fields_rec) {
		n_bytes = 0;
	}

	fold = ut_fold_ull(tree_id);

	for (i = 0; i < n_fields; i++) {
		data = rec_get_nth_field(rec, offsets, i, &len);

		if (len != UNIV_SQL_NULL) {
			fold = ut_fold_ulint_pair(fold,
						  ut_fold_binary(data, len));
		}
	}

	if (n_bytes > 0) {
		data = rec_get_nth_field(rec, offsets, i, &len);

		if (len != UNIV_SQL_NULL) {
			if (len > n_bytes) {
				len = n_bytes;
			}

			fold = ut_fold_ulint_pair(fold,
						  ut_fold_binary(data, len));
		}
	}

	return(fold);
}
osku's avatar
osku committed
140

141 142 143 144
/** Determine the number of accessed key fields.
@param[in]	n_fields	number of complete fields
@param[in]	n_bytes		number of bytes in an incomplete last field
@return	number of complete or incomplete fields */
145
inline MY_ATTRIBUTE((warn_unused_result))
146 147 148 149 150 151 152 153 154 155 156
ulint
btr_search_get_n_fields(
	ulint	n_fields,
	ulint	n_bytes)
{
	return(n_fields + (n_bytes > 0 ? 1 : 0));
}

/** Determine the number of accessed key fields.
@param[in]	cursor		b-tree cursor
@return	number of complete or incomplete fields */
157
inline MY_ATTRIBUTE((warn_unused_result))
158 159 160 161 162 163 164 165
ulint
btr_search_get_n_fields(
	const btr_cur_t*	cursor)
{
	return(btr_search_get_n_fields(cursor->n_fields, cursor->n_bytes));
}

/** This function should be called before reserving any btr search mutex, if
osku's avatar
osku committed
166 167 168 169 170 171 172
the intended operation might add nodes to the search system hash table.
Because of the latching order, once we have reserved the btr search system
latch, we cannot allocate a free frame from the buffer pool. Checks that
there is a free buffer frame allocated for hash table heap in the btr search
system. If not, allocates a free frames for the heap. This check makes it
probable that, when have reserved the btr search system latch and we need to
allocate a new node to the hash table, it will succeed. However, the check
173 174
will not guarantee success.
@param[in]	index	index handler */
175
static void btr_search_check_free_space_in_heap(const dict_index_t *index)
osku's avatar
osku committed
176
{
177 178 179
  /* Note that we peek the value of heap->free_block without reserving
  the latch: this is ok, because we will not guarantee that there will
  be enough free space in the hash table. */
osku's avatar
osku committed
180

181 182
  buf_block_t *block= buf_block_alloc();
  auto part= btr_search_sys.get_part(*index);
osku's avatar
osku committed
183

184
  part->latch.wr_lock(SRW_LOCK_CALL);
osku's avatar
osku committed
185

186 187 188 189
  if (!btr_search_enabled || part->heap->free_block)
    buf_block_free(block);
  else
    part->heap->free_block= block;
190

191
  part->latch.wr_unlock();
192 193
}

194 195
/** Set index->ref_count = 0 on all indexes of a table.
@param[in,out]	table	table handler */
Marko Mäkelä's avatar
Marko Mäkelä committed
196
static void btr_search_disable_ref_count(dict_table_t *table)
197
{
Marko Mäkelä's avatar
Marko Mäkelä committed
198 199 200
  for (dict_index_t *index= dict_table_get_first_index(table); index;
       index= dict_table_get_next_index(index))
    index->search_info->ref_count= 0;
201 202
}

203 204 205 206 207 208 209
/** Lazily free detached metadata when removing the last reference. */
ATTRIBUTE_COLD static void btr_search_lazy_free(dict_index_t *index)
{
  ut_ad(index->freed());
  dict_table_t *table= index->table;
  /* Perform the skipped steps of dict_index_remove_from_cache_low(). */
  UT_LIST_REMOVE(table->freed_indexes, index);
210
  index->lock.free();
211 212 213 214 215 216 217 218
  dict_mem_index_free(index);

  if (!UT_LIST_GET_LEN(table->freed_indexes) &&
      !UT_LIST_GET_LEN(table->indexes))
  {
    ut_ad(table->id == 0);
    dict_mem_table_free(table);
  }
219 220
}

221 222
/** Disable the adaptive hash search system and empty the index. */
void btr_search_disable()
223
{
Sergei Golubchik's avatar
Sergei Golubchik committed
224 225
	dict_table_t*	table;

Marko Mäkelä's avatar
Marko Mäkelä committed
226
	mutex_enter(&dict_sys.mutex);
227

228 229 230
	btr_search_x_lock_all();

	if (!btr_search_enabled) {
Marko Mäkelä's avatar
Marko Mäkelä committed
231
		mutex_exit(&dict_sys.mutex);
232 233 234 235 236
		btr_search_x_unlock_all();
		return;
	}

	btr_search_enabled = false;
237

Sergei Golubchik's avatar
Sergei Golubchik committed
238 239
	/* Clear the index->search_info->ref_count of every index in
	the data dictionary cache. */
240
	for (table = UT_LIST_GET_FIRST(dict_sys.table_LRU); table;
Sergei Golubchik's avatar
Sergei Golubchik committed
241 242
	     table = UT_LIST_GET_NEXT(table_LRU, table)) {

243 244
		btr_search_disable_ref_count(table);
	}
245

246
	for (table = UT_LIST_GET_FIRST(dict_sys.table_non_LRU); table;
247
	     table = UT_LIST_GET_NEXT(table_LRU, table)) {
Sergei Golubchik's avatar
Sergei Golubchik committed
248

249
		btr_search_disable_ref_count(table);
Sergei Golubchik's avatar
Sergei Golubchik committed
250
	}
251

Marko Mäkelä's avatar
Marko Mäkelä committed
252
	mutex_exit(&dict_sys.mutex);
253

Sergei Golubchik's avatar
Sergei Golubchik committed
254
	/* Set all block->index = NULL. */
255
	buf_pool.clear_hash_index();
Sergei Golubchik's avatar
Sergei Golubchik committed
256 257

	/* Clear the adaptive hash index. */
258
	btr_search_sys.clear();
259

260
	btr_search_x_unlock_all();
261 262
}

263
/** Enable the adaptive hash search system.
Marko Mäkelä's avatar
Marko Mäkelä committed
264
@param resize whether buf_pool_t::resize() is the caller */
Marko Mäkelä's avatar
Marko Mäkelä committed
265
void btr_search_enable(bool resize)
266
{
267
	if (!resize) {
268
		mysql_mutex_lock(&buf_pool.mutex);
Marko Mäkelä's avatar
Marko Mäkelä committed
269
		bool changed = srv_buf_pool_old_size != srv_buf_pool_size;
270
		mysql_mutex_unlock(&buf_pool.mutex);
Marko Mäkelä's avatar
Marko Mäkelä committed
271
		if (changed) {
272 273
			return;
		}
274
	}
275

276
	btr_search_x_lock_all();
Marko Mäkelä's avatar
Marko Mäkelä committed
277
	ulint hash_size = buf_pool_get_curr_size() / sizeof(void *) / 64;
278

279
	if (btr_search_sys.parts[0].heap) {
280 281 282 283 284
		ut_ad(btr_search_enabled);
		btr_search_x_unlock_all();
		return;
	}

285
	btr_search_sys.alloc(hash_size);
286

287 288
	btr_search_enabled = true;
	btr_search_x_unlock_all();
289 290
}

291
/** Updates the search info of an index about hash successes. NOTE that info
osku's avatar
osku committed
292
is NOT protected by any semaphore, to save CPU time! Do not assume its fields
293 294 295
are consistent.
@param[in,out]	info	search info
@param[in]	cursor	cursor which was just positioned */
osku's avatar
osku committed
296 297 298
static
void
btr_search_info_update_hash(
299 300
	btr_search_t*	info,
	btr_cur_t*	cursor)
osku's avatar
osku committed
301
{
302
	dict_index_t*	index = cursor->index;
osku's avatar
osku committed
303 304
	int		cmp;

305
	if (dict_index_is_ibuf(index)) {
osku's avatar
osku committed
306 307 308 309 310 311
		/* So many deletes are performed on an insert buffer tree
		that we do not consider a hash index useful on it: */

		return;
	}

312
	uint16_t n_unique = dict_index_get_n_unique_in_tree(index);
osku's avatar
osku committed
313 314 315 316 317 318 319 320 321 322

	if (info->n_hash_potential == 0) {

		goto set_new_recomm;
	}

	/* Test if the search would have succeeded using the recommended
	hash prefix */

	if (info->n_fields >= n_unique && cursor->up_match >= n_unique) {
323
increment_potential:
osku's avatar
osku committed
324 325 326 327 328 329
		info->n_hash_potential++;

		return;
	}

	cmp = ut_pair_cmp(info->n_fields, info->n_bytes,
330
			  cursor->low_match, cursor->low_bytes);
osku's avatar
osku committed
331

332
	if (info->left_side ? cmp <= 0 : cmp > 0) {
osku's avatar
osku committed
333 334 335 336 337

		goto set_new_recomm;
	}

	cmp = ut_pair_cmp(info->n_fields, info->n_bytes,
338
			  cursor->up_match, cursor->up_bytes);
osku's avatar
osku committed
339

340
	if (info->left_side ? cmp <= 0 : cmp > 0) {
osku's avatar
osku committed
341

342
		goto increment_potential;
osku's avatar
osku committed
343 344 345 346 347 348
	}

set_new_recomm:
	/* We have to set a new recommendation; skip the hash analysis
	for a while to avoid unnecessary CPU time usage when there is no
	chance for success */
349

osku's avatar
osku committed
350
	info->hash_analysis = 0;
351

osku's avatar
osku committed
352
	cmp = ut_pair_cmp(cursor->up_match, cursor->up_bytes,
353
			  cursor->low_match, cursor->low_bytes);
354 355
	info->left_side = cmp >= 0;
	info->n_hash_potential = cmp != 0;
osku's avatar
osku committed
356

357
	if (cmp == 0) {
osku's avatar
osku committed
358 359 360 361 362 363 364 365 366 367 368 369 370
		/* For extra safety, we set some sensible values here */
		info->n_fields = 1;
		info->n_bytes = 0;
	} else if (cmp > 0) {
		info->n_hash_potential = 1;

		if (cursor->up_match >= n_unique) {

			info->n_fields = n_unique;
			info->n_bytes = 0;

		} else if (cursor->low_match < cursor->up_match) {

371 372
			info->n_fields = static_cast<uint16_t>(
				cursor->low_match + 1);
osku's avatar
osku committed
373
			info->n_bytes = 0;
374
		} else {
375 376 377 378
			info->n_fields = static_cast<uint16_t>(
				cursor->low_match);
			info->n_bytes = static_cast<uint16_t>(
				cursor->low_bytes + 1);
osku's avatar
osku committed
379 380 381 382 383 384 385 386
		}
	} else {
		if (cursor->low_match >= n_unique) {

			info->n_fields = n_unique;
			info->n_bytes = 0;
		} else if (cursor->low_match > cursor->up_match) {

387 388
			info->n_fields = static_cast<uint16_t>(
				cursor->up_match + 1);
osku's avatar
osku committed
389
			info->n_bytes = 0;
390
		} else {
391 392 393 394
			info->n_fields = static_cast<uint16_t>(
				cursor->up_match);
			info->n_bytes = static_cast<uint16_t>(
				cursor->up_bytes + 1);
osku's avatar
osku committed
395 396 397
		}
	}
}
398

399 400
/** Update the block search info on hash successes. NOTE that info and
block->n_hash_helps, n_fields, n_bytes, left_side are NOT protected by any
401
semaphore, to save CPU time! Do not assume the fields are consistent.
402 403
@return TRUE if building a (new) hash index on the block is recommended
@param[in,out]	info	search info
404
@param[in,out]	block	buffer block */
osku's avatar
osku committed
405
static
406
bool
407
btr_search_update_block_hash_info(btr_search_t* info, buf_block_t* block)
osku's avatar
osku committed
408
{
409
	ut_ad(block->lock.have_x() || block->lock.have_s());
osku's avatar
osku committed
410 411

	info->last_hash_succ = FALSE;
412 413 414 415 416
	ut_d(auto state= block->page.state());
	ut_ad(state == BUF_BLOCK_NOT_USED
	      || state == BUF_BLOCK_FILE_PAGE
	      || state == BUF_BLOCK_MEMORY
	      || state == BUF_BLOCK_REMOVE_HASH);
417
	ut_ad(info->magic_n == BTR_SEARCH_MAGIC_N);
osku's avatar
osku committed
418 419

	if ((block->n_hash_helps > 0)
420 421 422
	    && (info->n_hash_potential > 0)
	    && (block->n_fields == info->n_fields)
	    && (block->n_bytes == info->n_bytes)
423
	    && (block->left_side == info->left_side)) {
424

Sergei Golubchik's avatar
Sergei Golubchik committed
425
		if ((block->index)
426 427
		    && (block->curr_n_fields == info->n_fields)
		    && (block->curr_n_bytes == info->n_bytes)
428
		    && (block->curr_left_side == info->left_side)) {
osku's avatar
osku committed
429 430 431

			/* The search would presumably have succeeded using
			the hash index */
432

osku's avatar
osku committed
433 434 435 436 437 438 439 440
			info->last_hash_succ = TRUE;
		}

		block->n_hash_helps++;
	} else {
		block->n_hash_helps = 1;
		block->n_fields = info->n_fields;
		block->n_bytes = info->n_bytes;
441
		block->left_side = info->left_side;
osku's avatar
osku committed
442 443 444
	}

	if ((block->n_hash_helps > page_get_n_recs(block->frame)
445 446
	     / BTR_SEARCH_PAGE_BUILD_LIMIT)
	    && (info->n_hash_potential >= BTR_SEARCH_BUILD_LIMIT)) {
osku's avatar
osku committed
447

Sergei Golubchik's avatar
Sergei Golubchik committed
448
		if ((!block->index)
449
		    || (block->n_hash_helps
450
			> 2U * page_get_n_recs(block->frame))
451 452
		    || (block->n_fields != block->curr_n_fields)
		    || (block->n_bytes != block->curr_n_bytes)
453
		    || (block->left_side != block->curr_left_side)) {
osku's avatar
osku committed
454

455
			/* Build a new hash index on the page */
osku's avatar
osku committed
456

457
			return(true);
osku's avatar
osku committed
458 459 460
		}
	}

461
	return(false);
osku's avatar
osku committed
462 463
}

464 465 466 467 468 469 470 471 472 473 474 475 476 477 478 479 480 481 482 483 484 485 486 487 488 489 490 491 492
#if defined UNIV_AHI_DEBUG || defined UNIV_DEBUG
/** Maximum number of records in a page */
constexpr ulint MAX_N_POINTERS = UNIV_PAGE_SIZE_MAX / REC_N_NEW_EXTRA_BYTES;
#endif /* UNIV_AHI_DEBUG || UNIV_DEBUG */

__attribute__((nonnull))
/**
Insert an entry into the hash table. If an entry with the same fold number
is found, its node is updated to point to the new data, and no new node
is inserted.
@param table hash table
@param heap  memory heap
@param fold  folded value of the record
@param block buffer block containing the record
@param data  the record
@retval true on success
@retval false if no more memory could be allocated */
static bool ha_insert_for_fold(hash_table_t *table, mem_heap_t* heap,
                               ulint fold,
#if defined UNIV_AHI_DEBUG || defined UNIV_DEBUG
                               buf_block_t *block, /*!< buffer block of data */
#endif /* UNIV_AHI_DEBUG || UNIV_DEBUG */
                               const rec_t *data)
{
#if defined UNIV_AHI_DEBUG || defined UNIV_DEBUG
  ut_a(block->frame == page_align(data));
#endif /* UNIV_AHI_DEBUG || UNIV_DEBUG */
  ut_ad(btr_search_enabled);

493
  hash_cell_t *cell= &table->array[table->calc_hash(fold)];
494 495 496 497 498 499 500 501 502 503 504 505 506 507 508 509 510 511 512 513 514 515 516 517 518 519 520 521 522 523 524 525 526 527 528 529 530 531 532 533 534 535 536 537 538 539 540 541 542 543 544 545 546 547 548 549 550 551 552 553 554 555 556 557 558 559 560 561 562 563

  for (ha_node_t *prev= static_cast<ha_node_t*>(cell->node); prev;
       prev= prev->next)
  {
    if (prev->fold == fold)
    {
#if defined UNIV_AHI_DEBUG || defined UNIV_DEBUG
      buf_block_t *prev_block= prev->block;
      ut_a(prev_block->frame == page_align(prev->data));
      ut_a(prev_block->n_pointers-- < MAX_N_POINTERS);
      ut_a(block->n_pointers++ < MAX_N_POINTERS);

      prev->block= block;
#endif /* UNIV_AHI_DEBUG || UNIV_DEBUG */
      prev->data= data;
      return true;
    }
  }

  /* We have to allocate a new chain node */
  ha_node_t *node= static_cast<ha_node_t*>(mem_heap_alloc(heap, sizeof *node));

  if (!node)
    return false;

  ha_node_set_data(node, block, data);

#if defined UNIV_AHI_DEBUG || defined UNIV_DEBUG
  ut_a(block->n_pointers++ < MAX_N_POINTERS);
#endif /* UNIV_AHI_DEBUG || UNIV_DEBUG */

  node->fold= fold;
  node->next= nullptr;

  ha_node_t *prev= static_cast<ha_node_t*>(cell->node);
  if (!prev)
    cell->node= node;
  else
  {
    while (prev->next)
      prev= prev->next;
    prev->next= node;
  }
  return true;
}

__attribute__((nonnull))
/** Delete a record.
@param table     hash table
@param heap      memory heap
@param del_node  record to be deleted */
static void ha_delete_hash_node(hash_table_t *table, mem_heap_t *heap,
                                ha_node_t *del_node)
{
  ut_ad(btr_search_enabled);
#if defined UNIV_AHI_DEBUG || defined UNIV_DEBUG
  ut_a(del_node->block->frame == page_align(del_node->data));
  ut_a(del_node->block->n_pointers-- < MAX_N_POINTERS);
#endif /* UNIV_AHI_DEBUG || UNIV_DEBUG */

  const ulint fold= del_node->fold;

  HASH_DELETE(ha_node_t, next, table, fold, del_node);

  ha_node_t *top= static_cast<ha_node_t*>(mem_heap_get_top(heap, sizeof *top));

  if (del_node != top)
  {
    /* Compact the heap of nodes by moving the top in the place of del_node. */
    *del_node= *top;
564
    hash_cell_t *cell= &table->array[table->calc_hash(top->fold)];
565 566 567 568 569 570 571 572 573 574 575 576 577 578 579 580 581 582 583 584 585 586 587 588 589 590 591 592 593 594 595 596 597 598 599 600 601 602 603 604 605 606 607 608 609 610 611 612 613 614 615 616 617 618 619 620 621 622 623 624 625 626 627 628 629 630 631 632 633 634 635 636 637 638 639 640 641 642 643 644 645 646 647 648 649 650 651 652 653 654 655 656 657 658 659 660 661 662 663 664 665 666 667 668 669 670 671 672 673 674 675 676 677

    /* Look for the pointer to the top node, to update it */
    if (cell->node == top)
      /* The top node is the first in the chain */
      cell->node= del_node;
    else
    {
      /* We have to look for the predecessor */
      ha_node_t *node= static_cast<ha_node_t*>(cell->node);

      while (top != HASH_GET_NEXT(next, node))
        node= static_cast<ha_node_t*>(HASH_GET_NEXT(next, node));

      /* Now we have the predecessor node */
      node->next= del_node;
    }
  }

  /* Free the occupied space */
  mem_heap_free_top(heap, sizeof *top);
}

__attribute__((nonnull))
/** Delete all pointers to a page.
@param table     hash table
@param heap      memory heap
@param page      record to be deleted */
static void ha_remove_all_nodes_to_page(hash_table_t *table, mem_heap_t *heap,
                                        ulint fold, const page_t *page)
{
  for (ha_node_t *node= ha_chain_get_first(table, fold); node; )
  {
    if (page_align(ha_node_get_data(node)) == page)
    {
      ha_delete_hash_node(table, heap, node);
      /* The deletion may compact the heap of nodes and move other nodes! */
      node= ha_chain_get_first(table, fold);
    }
    else
      node= ha_chain_get_next(node);
  }
#ifdef UNIV_DEBUG
  /* Check that all nodes really got deleted */
  for (ha_node_t *node= ha_chain_get_first(table, fold); node;
       node= ha_chain_get_next(node))
    ut_ad(page_align(ha_node_get_data(node)) != page);
#endif /* UNIV_DEBUG */
}

/** Delete a record if found.
@param table     hash table
@param heap      memory heap for the hash bucket chain
@param fold      folded value of the searched data
@param data      pointer to the record
@return whether the record was found */
static bool ha_search_and_delete_if_found(hash_table_t *table,
                                          mem_heap_t *heap,
                                          ulint fold, const rec_t *data)
{
  if (ha_node_t *node= ha_search_with_data(table, fold, data))
  {
    ha_delete_hash_node(table, heap, node);
    return true;
  }

  return false;
}

__attribute__((nonnull))
/** Looks for an element when we know the pointer to the data and
updates the pointer to data if found.
@param table     hash table
@param fold      folded value of the searched data
@param data      pointer to the data
@param new_data  new pointer to the data
@return whether the element was found */
static bool ha_search_and_update_if_found(hash_table_t *table, ulint fold,
                                          const rec_t *data,
#if defined UNIV_AHI_DEBUG || defined UNIV_DEBUG
                                          /** block containing new_data */
                                          buf_block_t *new_block,
#endif /* UNIV_AHI_DEBUG || UNIV_DEBUG */
                                          const rec_t *new_data)
{
#if defined UNIV_AHI_DEBUG || defined UNIV_DEBUG
  ut_a(new_block->frame == page_align(new_data));
#endif /* UNIV_AHI_DEBUG || UNIV_DEBUG */

  if (!btr_search_enabled)
    return false;

  if (ha_node_t *node= ha_search_with_data(table, fold, data))
  {
#if defined UNIV_AHI_DEBUG || defined UNIV_DEBUG
    ut_a(node->block->n_pointers-- < MAX_N_POINTERS);
    ut_a(new_block->n_pointers++ < MAX_N_POINTERS);
    node->block= new_block;
#endif /* UNIV_AHI_DEBUG || UNIV_DEBUG */
    node->data= new_data;

    return true;
  }

  return false;
}

#if defined UNIV_AHI_DEBUG || defined UNIV_DEBUG
#else
# define ha_insert_for_fold(t,h,f,b,d) ha_insert_for_fold(t,h,f,d)
# define ha_search_and_update_if_found(table,fold,data,new_block,new_data) \
	ha_search_and_update_if_found(table,fold,data,new_data)
#endif

678
/** Updates a hash node reference when it has been unsuccessfully used in a
osku's avatar
osku committed
679 680 681 682 683
search which could have succeeded with the used hash parameters. This can
happen because when building a hash index for a page, we do not check
what happens at page boundaries, and therefore there can be misleading
hash nodes. Also, collisions in the fold value can lead to misleading
references. This function lazily fixes these imperfections in the hash
684 685 686 687
index.
@param[in]	info	search info
@param[in]	block	buffer block where cursor positioned
@param[in]	cursor	cursor */
osku's avatar
osku committed
688 689 690
static
void
btr_search_update_hash_ref(
691 692 693
	const btr_search_t*	info,
	buf_block_t*		block,
	const btr_cur_t*	cursor)
osku's avatar
osku committed
694 695
{
	ut_ad(cursor->flag == BTR_CUR_HASH_FAIL);
696

697
	ut_ad(block->lock.have_x() || block->lock.have_s());
698 699
	ut_ad(page_align(btr_cur_get_rec(cursor)) == block->frame);
	ut_ad(page_is_leaf(block->frame));
700
	assert_block_ahi_valid(block);
osku's avatar
osku committed
701

702
	dict_index_t* index = block->index;
703

704
	if (!index || !info->n_hash_potential) {
705 706 707
		return;
	}

708
	ut_ad(block->page.id().space() == index->table->space_id);
709 710
	ut_ad(index == cursor->index);
	ut_ad(!dict_index_is_ibuf(index));
711
	auto part = btr_search_sys.get_part(*index);
712
	part->latch.wr_lock(SRW_LOCK_CALL);
713
	ut_ad(!block->index || block->index == index);
714

715
	if (block->index
716 717
	    && (block->curr_n_fields == info->n_fields)
	    && (block->curr_n_bytes == info->n_bytes)
718 719
	    && (block->curr_left_side == info->left_side)
	    && btr_search_enabled) {
osku's avatar
osku committed
720
		mem_heap_t*	heap		= NULL;
721
		rec_offs	offsets_[REC_OFFS_NORMAL_SIZE];
722
		rec_offs_init(offsets_);
osku's avatar
osku committed
723

724
		const rec_t* rec = btr_cur_get_rec(cursor);
725 726

		if (!page_rec_is_user_rec(rec)) {
727
			goto func_exit;
728
		}
osku's avatar
osku committed
729

730 731 732 733 734 735
		ulint fold = rec_fold(
			rec,
			rec_get_offsets(rec, index, offsets_, true,
					ULINT_UNDEFINED, &heap),
			block->curr_n_fields,
			block->curr_n_bytes, index->id);
osku's avatar
osku committed
736 737 738 739
		if (UNIV_LIKELY_NULL(heap)) {
			mem_heap_free(heap);
		}

740
		ha_insert_for_fold(&part->table, part->heap, fold, block, rec);
741 742

		MONITOR_INC(MONITOR_ADAPTIVE_HASH_ROW_ADDED);
osku's avatar
osku committed
743
	}
744 745

func_exit:
746
	part->latch.wr_unlock();
747 748
}

749
/** Checks if a guessed position for a tree cursor is right. Note that if
osku's avatar
osku committed
750
mode is PAGE_CUR_LE, which is used in inserts, and the function returns
751
TRUE, then cursor->up_match and cursor->low_match both have sensible values.
752 753 754 755 756 757 758 759 760 761
@param[in,out]	cursor		guess cursor position
@param[in]	can_only_compare_to_cursor_rec
				if we do not have a latch on the page of cursor,
				but a latch corresponding search system, then
				ONLY the columns of the record UNDER the cursor
				are protected, not the next or previous record
				in the chain: we cannot look at the next or
				previous record to check our guess!
@param[in]	tuple		data tuple
@param[in]	mode		PAGE_CUR_L, PAGE_CUR_LE, PAGE_CUR_G, PAGE_CUR_GE
762
@return	whether a match was found */
osku's avatar
osku committed
763
static
764
bool
osku's avatar
osku committed
765
btr_search_check_guess(
766
	btr_cur_t*	cursor,
767
	bool		can_only_compare_to_cursor_rec,
768
	const dtuple_t*	tuple,
769
	ulint		mode)
osku's avatar
osku committed
770 771 772 773 774 775
{
	rec_t*		rec;
	ulint		n_unique;
	ulint		match;
	int		cmp;
	mem_heap_t*	heap		= NULL;
776 777
	rec_offs	offsets_[REC_OFFS_NORMAL_SIZE];
	rec_offs*	offsets		= offsets_;
osku's avatar
osku committed
778
	ibool		success		= FALSE;
779
	rec_offs_init(offsets_);
osku's avatar
osku committed
780 781

	n_unique = dict_index_get_n_unique_in_tree(cursor->index);
782

osku's avatar
osku committed
783 784 785
	rec = btr_cur_get_rec(cursor);

	ut_ad(page_rec_is_user_rec(rec));
786
	ut_ad(page_rec_is_leaf(rec));
osku's avatar
osku committed
787 788 789

	match = 0;

790
	offsets = rec_get_offsets(rec, cursor->index, offsets, true,
791
				  n_unique, &heap);
792
	cmp = cmp_dtuple_rec_with_match(tuple, rec, offsets, &match);
osku's avatar
osku committed
793 794

	if (mode == PAGE_CUR_GE) {
795
		if (cmp > 0) {
osku's avatar
osku committed
796 797 798 799 800 801 802 803
			goto exit_func;
		}

		cursor->up_match = match;

		if (match >= n_unique) {
			success = TRUE;
			goto exit_func;
804
		}
osku's avatar
osku committed
805
	} else if (mode == PAGE_CUR_LE) {
806
		if (cmp < 0) {
osku's avatar
osku committed
807 808 809 810 811 812
			goto exit_func;
		}

		cursor->low_match = match;

	} else if (mode == PAGE_CUR_G) {
813
		if (cmp >= 0) {
osku's avatar
osku committed
814 815 816
			goto exit_func;
		}
	} else if (mode == PAGE_CUR_L) {
817
		if (cmp <= 0) {
osku's avatar
osku committed
818 819 820 821 822
			goto exit_func;
		}
	}

	if (can_only_compare_to_cursor_rec) {
823 824
		/* Since we could not determine if our guess is right just by
		looking at the record under the cursor, return FALSE */
osku's avatar
osku committed
825 826 827 828 829 830 831
		goto exit_func;
	}

	match = 0;

	if ((mode == PAGE_CUR_G) || (mode == PAGE_CUR_GE)) {
		ut_ad(!page_rec_is_infimum(rec));
832

833
		const rec_t* prev_rec = page_rec_get_prev(rec);
osku's avatar
osku committed
834 835

		if (page_rec_is_infimum(prev_rec)) {
836
			success = !page_has_prev(page_align(prev_rec));
osku's avatar
osku committed
837 838 839 840
			goto exit_func;
		}

		offsets = rec_get_offsets(prev_rec, cursor->index, offsets,
841
					  true, n_unique, &heap);
842 843
		cmp = cmp_dtuple_rec_with_match(
			tuple, prev_rec, offsets, &match);
osku's avatar
osku committed
844
		if (mode == PAGE_CUR_GE) {
845
			success = cmp > 0;
osku's avatar
osku committed
846
		} else {
847
			success = cmp >= 0;
osku's avatar
osku committed
848 849 850
		}
	} else {
		ut_ad(!page_rec_is_supremum(rec));
851

852
		const rec_t* next_rec = page_rec_get_next(rec);
osku's avatar
osku committed
853 854

		if (page_rec_is_supremum(next_rec)) {
855
			if (!page_has_next(page_align(next_rec))) {
osku's avatar
osku committed
856 857 858 859 860 861 862 863
				cursor->up_match = 0;
				success = TRUE;
			}

			goto exit_func;
		}

		offsets = rec_get_offsets(next_rec, cursor->index, offsets,
864
					  true, n_unique, &heap);
865 866
		cmp = cmp_dtuple_rec_with_match(
			tuple, next_rec, offsets, &match);
osku's avatar
osku committed
867
		if (mode == PAGE_CUR_LE) {
868
			success = cmp < 0;
osku's avatar
osku committed
869 870
			cursor->up_match = match;
		} else {
871
			success = cmp <= 0;
osku's avatar
osku committed
872 873 874 875 876 877 878 879 880
		}
	}
exit_func:
	if (UNIV_LIKELY_NULL(heap)) {
		mem_heap_free(heap);
	}
	return(success);
}

881 882 883 884 885 886 887 888 889 890 891 892 893 894 895 896 897
static
void
btr_search_failure(btr_search_t* info, btr_cur_t* cursor)
{
	cursor->flag = BTR_CUR_HASH_FAIL;

#ifdef UNIV_SEARCH_PERF_STAT
	++info->n_hash_fail;

	if (info->n_hash_succ > 0) {
		--info->n_hash_succ;
	}
#endif /* UNIV_SEARCH_PERF_STAT */

	info->last_hash_succ = FALSE;
}

898 899 900 901 902 903
/** Clear the adaptive hash index on all pages in the buffer pool. */
inline void buf_pool_t::clear_hash_index()
{
  ut_ad(!resizing);
  ut_ad(!btr_search_enabled);

Marko Mäkelä's avatar
Marko Mäkelä committed
904 905
  std::set<dict_index_t*> garbage;

906
  for (chunk_t *chunk= chunks + n_chunks; chunk-- != chunks; )
907 908 909 910 911 912 913
  {
    for (buf_block_t *block= chunk->blocks, * const end= block + chunk->size;
         block != end; block++)
    {
      dict_index_t *index= block->index;
      assert_block_ahi_valid(block);

Marko Mäkelä's avatar
Marko Mäkelä committed
914
      /* We can clear block->index and block->n_pointers when
915
      holding all AHI latches exclusively; see the comments in buf0buf.h */
Marko Mäkelä's avatar
Marko Mäkelä committed
916

917 918 919 920 921 922 923 924
      if (!index)
      {
# if defined UNIV_AHI_DEBUG || defined UNIV_DEBUG
        ut_a(!block->n_pointers);
# endif /* UNIV_AHI_DEBUG || UNIV_DEBUG */
        continue;
      }

925
      ut_d(buf_page_state state= block->page.state());
926 927 928 929 930 931 932 933 934 935 936
      /* Another thread may have set the state to
      BUF_BLOCK_REMOVE_HASH in buf_LRU_block_remove_hashed().

      The state change in buf_pool_t::realloc() is not observable
      here, because in that case we would have !block->index.

      In the end, the entire adaptive hash index will be removed. */
      ut_ad(state == BUF_BLOCK_FILE_PAGE || state == BUF_BLOCK_REMOVE_HASH);
# if defined UNIV_AHI_DEBUG || defined UNIV_DEBUG
      block->n_pointers= 0;
# endif /* UNIV_AHI_DEBUG || UNIV_DEBUG */
Marko Mäkelä's avatar
Marko Mäkelä committed
937 938
      if (index->freed())
        garbage.insert(index);
939 940 941
      block->index= nullptr;
    }
  }
Marko Mäkelä's avatar
Marko Mäkelä committed
942 943 944

  for (dict_index_t *index : garbage)
    btr_search_lazy_free(index);
945 946 947 948 949 950 951 952 953 954 955 956 957 958 959 960 961 962 963 964 965 966 967 968 969 970
}

/** Get a buffer block from an adaptive hash index pointer.
This function does not return if the block is not identified.
@param ptr  pointer to within a page frame
@return pointer to block, never NULL */
inline buf_block_t* buf_pool_t::block_from_ahi(const byte *ptr) const
{
  chunk_t::map *chunk_map = chunk_t::map_ref;
  ut_ad(chunk_t::map_ref == chunk_t::map_reg);
  ut_ad(!resizing);

  chunk_t::map::const_iterator it= chunk_map->upper_bound(ptr);
  ut_a(it != chunk_map->begin());

  chunk_t *chunk= it == chunk_map->end()
    ? chunk_map->rbegin()->second
    : (--it)->second;

  const size_t offs= size_t(ptr - chunk->blocks->frame) >> srv_page_size_shift;
  ut_a(offs < chunk->size);

  buf_block_t *block= &chunk->blocks[offs];
  /* buf_pool_t::chunk_t::init() invokes buf_block_init() so that
  block[n].frame == block->frame + n * srv_page_size.  Check it. */
  ut_ad(block->frame == page_align(ptr));
971
  /* Read the state of the block without holding hash_lock.
972 973
  A state transition from BUF_BLOCK_FILE_PAGE to
  BUF_BLOCK_REMOVE_HASH is possible during this execution. */
974
  ut_d(const buf_page_state state = block->page.state());
975 976 977 978
  ut_ad(state == BUF_BLOCK_FILE_PAGE || state == BUF_BLOCK_REMOVE_HASH);
  return block;
}

979
/** Tries to guess the right search position based on the hash search info
osku's avatar
osku committed
980 981
of the index. Note that if mode is PAGE_CUR_LE, which is used in inserts,
and the function returns TRUE, then cursor->up_match and cursor->low_match
982
both have sensible values.
983 984 985 986 987 988 989 990 991 992
@param[in,out]	index		index
@param[in,out]	info		index search info
@param[in]	tuple		logical record
@param[in]	mode		PAGE_CUR_L, ....
@param[in]	latch_mode	BTR_SEARCH_LEAF, ...;
				NOTE that only if has_search_latch is 0, we will
				have a latch set on the cursor page, otherwise
				we assume the caller uses his search latch
				to protect the record!
@param[out]	cursor		tree cursor
993 994
@param[in]	ahi_latch	the adaptive hash index latch being held,
				or NULL
995
@param[in]	mtr		mini transaction
996 997
@return whether the search succeeded */
bool
osku's avatar
osku committed
998
btr_search_guess_on_hash(
999 1000 1001 1002 1003 1004
	dict_index_t*	index,
	btr_search_t*	info,
	const dtuple_t*	tuple,
	ulint		mode,
	ulint		latch_mode,
	btr_cur_t*	cursor,
1005
	srw_lock*	ahi_latch,
1006
	mtr_t*		mtr)
osku's avatar
osku committed
1007 1008
{
	ulint		fold;
1009
	index_id_t	index_id;
1010 1011

	ut_ad(mtr->is_active());
1012 1013

	if (!btr_search_enabled) {
Marko Mäkelä's avatar
Marko Mäkelä committed
1014
		return false;
1015 1016
	}

1017
	ut_ad(!index->is_ibuf());
1018 1019
	ut_ad(!ahi_latch
	      || ahi_latch == &btr_search_sys.get_part(*index)->latch);
1020
	ut_ad(latch_mode == BTR_SEARCH_LEAF || latch_mode == BTR_MODIFY_LEAF);
1021 1022
	compile_time_assert(ulint{BTR_SEARCH_LEAF} == ulint{RW_S_LATCH});
	compile_time_assert(ulint{BTR_MODIFY_LEAF} == ulint{RW_X_LATCH});
osku's avatar
osku committed
1023

1024 1025 1026
	/* Not supported for spatial index */
	ut_ad(!dict_index_is_spatial(index));

osku's avatar
osku committed
1027 1028 1029
	/* Note that, for efficiency, the struct info may not be protected by
	any latch here! */

1030
	if (info->n_hash_potential == 0) {
Marko Mäkelä's avatar
Marko Mäkelä committed
1031
		return false;
osku's avatar
osku committed
1032 1033 1034 1035 1036
	}

	cursor->n_fields = info->n_fields;
	cursor->n_bytes = info->n_bytes;

1037
	if (dtuple_get_n_fields(tuple) < btr_search_get_n_fields(cursor)) {
Marko Mäkelä's avatar
Marko Mäkelä committed
1038
		return false;
osku's avatar
osku committed
1039 1040
	}

1041
	index_id = index->id;
osku's avatar
osku committed
1042 1043 1044 1045

#ifdef UNIV_SEARCH_PERF_STAT
	info->n_hash_succ++;
#endif
1046
	fold = dtuple_fold(tuple, cursor->n_fields, cursor->n_bytes, index_id);
osku's avatar
osku committed
1047 1048 1049

	cursor->fold = fold;
	cursor->flag = BTR_CUR_HASH;
1050

1051
	auto part = btr_search_sys.get_part(*index);
Marko Mäkelä's avatar
Marko Mäkelä committed
1052
	const rec_t* rec;
1053

1054
	if (!ahi_latch) {
1055
		part->latch.rd_lock(SRW_LOCK_CALL);
1056

1057 1058
		if (!btr_search_enabled) {
			goto fail;
1059
		}
1060 1061
	} else {
		ut_ad(btr_search_enabled);
osku's avatar
osku committed
1062 1063
	}

Marko Mäkelä's avatar
Marko Mäkelä committed
1064
	rec = static_cast<const rec_t*>(
1065
		ha_search_and_get_data(&part->table, fold));
1066

1067
	if (!rec) {
1068
		if (!ahi_latch) {
1069
fail:
1070
			part->latch.rd_unlock();
1071 1072 1073
		}

		btr_search_failure(info, cursor);
Marko Mäkelä's avatar
Marko Mäkelä committed
1074
		return false;
osku's avatar
osku committed
1075 1076
	}

1077
	buf_block_t* block = buf_pool.block_from_ahi(rec);
1078

1079
	if (!ahi_latch) {
1080
		page_hash_latch* hash_lock = buf_pool.hash_lock_get(
1081
			block->page.id());
1082
		hash_lock->read_lock();
osku's avatar
osku committed
1083

1084
		if (block->page.state() == BUF_BLOCK_REMOVE_HASH) {
1085 1086 1087
			/* Another thread is just freeing the block
			from the LRU list of the buffer pool: do not
			try to access this page. */
1088
			hash_lock->read_unlock();
1089
			goto fail;
osku's avatar
osku committed
1090 1091
		}

1092 1093 1094
		const bool fail = index != block->index
			&& index_id == block->index->id;
		ut_a(!fail || block->index->freed());
1095
		ut_ad(block->page.state() == BUF_BLOCK_FILE_PAGE);
Marko Mäkelä's avatar
Marko Mäkelä committed
1096
		DBUG_ASSERT(fail || block->page.status != buf_page_t::FREED);
1097

1098
		buf_block_buf_fix_inc(block);
1099
		hash_lock->read_unlock();
1100
		block->page.set_accessed();
1101

1102
		buf_page_make_young_if_needed(&block->page);
1103 1104
		mtr_memo_type_t	fix_type;
		if (latch_mode == BTR_SEARCH_LEAF) {
1105
			if (!block->lock.s_lock_try()) {
1106 1107 1108 1109 1110 1111
got_no_latch:
				buf_block_buf_fix_dec(block);
				goto fail;
			}
			fix_type = MTR_MEMO_PAGE_S_FIX;
		} else {
1112
			if (!block->lock.x_lock_try()) {
1113 1114 1115 1116 1117 1118
				goto got_no_latch;
			}
			fix_type = MTR_MEMO_PAGE_X_FIX;
		}
		mtr->memo_push(block, fix_type);

1119
		buf_pool.stat.n_page_gets++;
1120

1121
		part->latch.rd_unlock();
osku's avatar
osku committed
1122

1123 1124 1125 1126 1127 1128 1129
		if (UNIV_UNLIKELY(fail)) {
			goto fail_and_release_page;
		}
	} else if (UNIV_UNLIKELY(index != block->index
				 && index_id == block->index->id)) {
		ut_a(block->index->freed());
		goto fail_and_release_page;
osku's avatar
osku committed
1130 1131
	}

1132
	if (block->page.state() != BUF_BLOCK_FILE_PAGE) {
1133

1134
		ut_ad(block->page.state() == BUF_BLOCK_REMOVE_HASH);
1135

1136
fail_and_release_page:
1137
		if (!ahi_latch) {
1138
			btr_leaf_page_release(block, latch_mode, mtr);
osku's avatar
osku committed
1139 1140
		}

1141
		btr_search_failure(info, cursor);
Marko Mäkelä's avatar
Marko Mäkelä committed
1142
		return false;
osku's avatar
osku committed
1143 1144 1145 1146
	}

	ut_ad(page_rec_is_user_rec(rec));

1147
	btr_cur_position(index, (rec_t*) rec, block, cursor);
osku's avatar
osku committed
1148 1149 1150

	/* Check the validity of the guess within the page */

1151
	/* If we only have the latch on search system, not on the
osku's avatar
osku committed
1152 1153 1154 1155
	page, it only protects the columns of the record the cursor
	is positioned on. We cannot look at the next of the previous
	record to determine if our guess for the cursor position is
	right. */
1156
	if (index_id != btr_page_get_index_id(block->frame)
1157
	    || !btr_search_check_guess(cursor, !!ahi_latch, tuple, mode)) {
1158
		goto fail_and_release_page;
osku's avatar
osku committed
1159 1160
	}

1161
	if (info->n_hash_potential < BTR_SEARCH_BUILD_LIMIT + 5) {
1162

osku's avatar
osku committed
1163 1164 1165 1166 1167 1168
		info->n_hash_potential++;
	}

#ifdef notdefined
	/* These lines of code can be used in a debug version to check
	the correctness of the searched cursor position: */
1169

osku's avatar
osku committed
1170 1171 1172
	info->last_hash_succ = FALSE;

	/* Currently, does not work if the following fails: */
1173
	ut_ad(!ahi_latch);
1174

1175
	btr_leaf_page_release(block, latch_mode, mtr);
osku's avatar
osku committed
1176

1177 1178 1179
	btr_cur_search_to_nth_level(
		index, 0, tuple, mode, latch_mode, &cursor2, 0, mtr);

osku's avatar
osku committed
1180
	if (mode == PAGE_CUR_GE
1181
	    && page_rec_is_supremum(btr_cur_get_rec(&cursor2))) {
osku's avatar
osku committed
1182 1183 1184 1185

		/* If mode is PAGE_CUR_GE, then the binary search
		in the index tree may actually take us to the supremum
		of the previous page */
1186

osku's avatar
osku committed
1187 1188
		info->last_hash_succ = FALSE;

1189 1190 1191
		btr_pcur_open_on_user_rec(
			index, tuple, mode, latch_mode, &pcur, mtr);

osku's avatar
osku committed
1192 1193 1194 1195 1196 1197 1198 1199 1200 1201 1202
		ut_ad(btr_pcur_get_rec(&pcur) == btr_cur_get_rec(cursor));
	} else {
		ut_ad(btr_cur_get_rec(&cursor2) == btr_cur_get_rec(cursor));
	}

	/* NOTE that it is theoretically possible that the above assertions
	fail if the page of the cursor gets removed from the buffer pool
	meanwhile! Thus it might not be a bug. */
#endif
	info->last_hash_succ = TRUE;

1203 1204 1205
#ifdef UNIV_SEARCH_PERF_STAT
	btr_search_n_succ++;
#endif
osku's avatar
osku committed
1206 1207
	/* Increment the page get statistics though we did not really
	fix the page: for user info only */
1208
	++buf_pool.stat.n_page_gets;
osku's avatar
osku committed
1209

1210
	if (!ahi_latch) {
1211
		buf_page_make_young_if_needed(&block->page);
osku's avatar
osku committed
1212 1213
	}

1214
	return true;
osku's avatar
osku committed
1215 1216
}

1217 1218 1219 1220
/** Drop any adaptive hash index entries that point to an index page.
@param[in,out]	block	block containing index page, s- or x-latched, or an
			index page for which we know that
			block->buf_fix_count == 0 or it is an index page which
1221
			has already been removed from the buf_pool.page_hash
1222
			i.e.: it is in state BUF_BLOCK_REMOVE_HASH */
1223
void btr_search_drop_page_hash_index(buf_block_t* block)
osku's avatar
osku committed
1224
{
1225 1226 1227 1228 1229 1230 1231 1232 1233 1234 1235
	ulint			n_fields;
	ulint			n_bytes;
	const page_t*		page;
	const rec_t*		rec;
	ulint			fold;
	ulint			prev_fold;
	ulint			n_cached;
	ulint			n_recs;
	ulint*			folds;
	ulint			i;
	mem_heap_t*		heap;
1236
	rec_offs*		offsets;
osku's avatar
osku committed
1237

1238
retry:
1239
	/* This debug check uses a dirty read that could theoretically cause
1240
	false positives while buf_pool.clear_hash_index() is executing. */
1241
	assert_block_ahi_valid(block);
osku's avatar
osku committed
1242

1243
	if (!block->index) {
1244 1245 1246
		return;
	}

1247 1248
	ut_ad(!block->page.buf_fix_count()
	      || block->page.state() == BUF_BLOCK_REMOVE_HASH
1249
	      || block->lock.have_any());
1250
	ut_ad(page_is_leaf(block->frame));
osku's avatar
osku committed
1251

1252
	/* We must not dereference block->index here, because it could be freed
1253
	if (index->table->n_ref_count == 0 && !mutex_own(&dict_sys.mutex)).
1254
	Determine the ahi_slot based on the block contents. */
osku's avatar
osku committed
1255

1256 1257 1258
	const index_id_t	index_id
		= btr_page_get_index_id(block->frame);

1259 1260 1261
	auto part = btr_search_sys.get_part(index_id,
					    block->page.id().space());

1262
	part->latch.rd_lock(SRW_LOCK_CALL);
1263
	assert_block_ahi_valid(block);
1264

1265
	if (!block->index || !btr_search_enabled) {
1266
		part->latch.rd_unlock();
osku's avatar
osku committed
1267 1268 1269
		return;
	}

1270
	dict_index_t* index = block->index;
1271
#ifdef MYSQL_INDEX_DISABLE_AHI
1272
	ut_ad(!index->disable_ahi);
1273
#endif
1274
	ut_ad(btr_search_enabled);
1275

1276
	ut_ad(block->page.id().space() == index->table->space_id);
1277
	ut_a(index_id == index->id);
1278
	ut_ad(!dict_index_is_ibuf(index));
1279

osku's avatar
osku committed
1280 1281 1282
	n_fields = block->curr_n_fields;
	n_bytes = block->curr_n_bytes;

1283 1284
	/* NOTE: The AHI fields of block must not be accessed after
	releasing search latch, as the index page might only be s-latched! */
osku's avatar
osku committed
1285

1286
	part->latch.rd_unlock();
1287

1288
	ut_a(n_fields > 0 || n_bytes > 0);
1289

Sergei Golubchik's avatar
Sergei Golubchik committed
1290
	page = block->frame;
osku's avatar
osku committed
1291 1292 1293 1294 1295
	n_recs = page_get_n_recs(page);

	/* Calculate and cache fold values into an array for fast deletion
	from the hash index */

1296
	folds = (ulint*) ut_malloc_nokey(n_recs * sizeof(ulint));
osku's avatar
osku committed
1297 1298 1299 1300

	n_cached = 0;

	rec = page_get_infimum_rec(page);
1301
	rec = page_rec_get_next_low(rec, page_is_comp(page));
1302
	if (rec_is_metadata(rec, *index)) {
1303 1304
		rec = page_rec_get_next_low(rec, page_is_comp(page));
	}
osku's avatar
osku committed
1305 1306 1307 1308 1309 1310 1311

	prev_fold = 0;

	heap = NULL;
	offsets = NULL;

	while (!page_rec_is_supremum(rec)) {
1312
		offsets = rec_get_offsets(
1313
			rec, index, offsets, true,
1314 1315
			btr_search_get_n_fields(n_fields, n_bytes),
			&heap);
1316
		fold = rec_fold(rec, offsets, n_fields, n_bytes, index_id);
osku's avatar
osku committed
1317 1318 1319 1320 1321 1322 1323 1324 1325 1326 1327 1328

		if (fold == prev_fold && prev_fold != 0) {

			goto next_rec;
		}

		/* Remove all hash nodes pointing to this page from the
		hash chain */

		folds[n_cached] = fold;
		n_cached++;
next_rec:
1329
		rec = page_rec_get_next_low(rec, page_rec_is_comp(rec));
osku's avatar
osku committed
1330 1331 1332 1333 1334 1335 1336
		prev_fold = fold;
	}

	if (UNIV_LIKELY_NULL(heap)) {
		mem_heap_free(heap);
	}

1337
	part->latch.wr_lock(SRW_LOCK_CALL);
osku's avatar
osku committed
1338

Sergei Golubchik's avatar
Sergei Golubchik committed
1339
	if (UNIV_UNLIKELY(!block->index)) {
1340 1341 1342 1343 1344 1345 1346
		/* Someone else has meanwhile dropped the hash index */

		goto cleanup;
	}

	ut_a(block->index == index);

1347 1348
	if (block->curr_n_fields != n_fields
	    || block->curr_n_bytes != n_bytes) {
1349 1350 1351 1352

		/* Someone else has meanwhile built a new hash index on the
		page, with different parameters */

1353
		part->latch.wr_unlock();
1354

1355
		ut_free(folds);
1356 1357 1358
		goto retry;
	}

osku's avatar
osku committed
1359
	for (i = 0; i < n_cached; i++) {
1360 1361
		ha_remove_all_nodes_to_page(&part->table, part->heap,
					    folds[i], page);
osku's avatar
osku committed
1362 1363
	}

1364 1365 1366 1367 1368 1369 1370 1371
	switch (index->search_info->ref_count--) {
	case 0:
		ut_error;
	case 1:
		if (index->freed()) {
			btr_search_lazy_free(index);
		}
	}
1372

osku's avatar
osku committed
1373
	block->index = NULL;
Sergei Golubchik's avatar
Sergei Golubchik committed
1374

1375 1376 1377
	MONITOR_INC(MONITOR_ADAPTIVE_HASH_PAGE_REMOVED);
	MONITOR_INC_VALUE(MONITOR_ADAPTIVE_HASH_ROW_REMOVED, n_cached);

1378
cleanup:
1379
	assert_block_ahi_valid(block);
1380
	part->latch.wr_unlock();
osku's avatar
osku committed
1381

1382
	ut_free(folds);
osku's avatar
osku committed
1383 1384
}

1385
/** Drop possible adaptive hash index entries when a page is evicted
Marko Mäkelä's avatar
Marko Mäkelä committed
1386
from the buffer pool or freed in a file, or the index is being dropped.
1387
@param[in]	page_id		page id */
1388
void btr_search_drop_page_hash_when_freed(const page_id_t page_id)
osku's avatar
osku committed
1389
{
1390 1391
	buf_block_t*	block;
	mtr_t		mtr;
1392

osku's avatar
osku committed
1393 1394
	mtr_start(&mtr);

Sergei Golubchik's avatar
Sergei Golubchik committed
1395 1396 1397 1398 1399
	/* If the caller has a latch on the page, then the caller must
	have a x-latch on the page and it must have already dropped
	the hash index for the page. Because of the x-latch that we
	are possibly holding, we cannot s-latch the page, but must
	(recursively) x-latch it, even though we are only reading. */
1400

1401
	block = buf_page_get_gen(page_id, 0, RW_X_LATCH, NULL,
1402
				 BUF_PEEK_IF_IN_POOL, &mtr);
osku's avatar
osku committed
1403

1404 1405 1406
	if (block) {
		/* If AHI is still valid, page can't be in free state.
		AHI is dropped when page is freed. */
1407
		DBUG_ASSERT(block->page.status != buf_page_t::FREED);
osku's avatar
osku committed
1408

1409
		if (block->index) {
1410 1411 1412
			/* In all our callers, the table handle should
			be open, or we should be in the process of
			dropping the table (preventing eviction). */
1413
			ut_ad(block->index->table->get_ref_count() > 0
1414
			      || mutex_own(&dict_sys.mutex));
1415 1416
			btr_search_drop_page_hash_index(block);
		}
1417
	}
osku's avatar
osku committed
1418 1419 1420 1421

	mtr_commit(&mtr);
}

1422
/** Build a hash index on a page with the given parameters. If the page already
osku's avatar
osku committed
1423 1424
has a hash index with different parameters, the old hash index is removed.
If index is non-NULL, this function checks if n_fields and n_bytes are
1425 1426 1427
sensible, and does not build a hash index if not.
@param[in,out]	index		index for which to build.
@param[in,out]	block		index page, s-/x- latched.
1428
@param[in,out]	ahi_latch	the adaptive search latch
1429 1430 1431
@param[in]	n_fields	hash this many full fields
@param[in]	n_bytes		hash this many bytes of the next field
@param[in]	left_side	hash for searches from left side */
osku's avatar
osku committed
1432 1433 1434
static
void
btr_search_build_page_hash_index(
1435 1436
	dict_index_t*	index,
	buf_block_t*	block,
1437
	srw_lock*	ahi_latch,
1438 1439 1440
	uint16_t	n_fields,
	uint16_t	n_bytes,
	bool		left_side)
osku's avatar
osku committed
1441
{
1442 1443
	const rec_t*	rec;
	const rec_t*	next_rec;
osku's avatar
osku committed
1444 1445 1446 1447 1448
	ulint		fold;
	ulint		next_fold;
	ulint		n_cached;
	ulint		n_recs;
	ulint*		folds;
1449
	const rec_t**	recs;
osku's avatar
osku committed
1450
	mem_heap_t*	heap		= NULL;
1451 1452
	rec_offs	offsets_[REC_OFFS_NORMAL_SIZE];
	rec_offs*	offsets		= offsets_;
osku's avatar
osku committed
1453

1454 1455 1456 1457
#ifdef MYSQL_INDEX_DISABLE_AHI
	if (index->disable_ahi) return;
#endif
	if (!btr_search_enabled) {
1458 1459 1460 1461
		return;
	}

	rec_offs_init(offsets_);
1462
	ut_ad(ahi_latch == &btr_search_sys.get_part(*index)->latch);
osku's avatar
osku committed
1463
	ut_ad(index);
1464
	ut_ad(block->page.id().space() == index->table->space_id);
1465
	ut_ad(!dict_index_is_ibuf(index));
1466
	ut_ad(page_is_leaf(block->frame));
osku's avatar
osku committed
1467

1468
	ut_ad(block->lock.have_x() || block->lock.have_s());
1469
	ut_ad(block->page.id().page_no() >= 3);
osku's avatar
osku committed
1470

1471
	ahi_latch->rd_lock(SRW_LOCK_CALL);
Sergei Golubchik's avatar
Sergei Golubchik committed
1472

Marko Mäkelä's avatar
Marko Mäkelä committed
1473 1474
	const bool enabled = btr_search_enabled;
	const bool rebuild = enabled && block->index
1475 1476 1477
		&& (block->curr_n_fields != n_fields
		    || block->curr_n_bytes != n_bytes
		    || block->curr_left_side != left_side);
osku's avatar
osku committed
1478

1479
	ahi_latch->rd_unlock();
osku's avatar
osku committed
1480

Marko Mäkelä's avatar
Marko Mäkelä committed
1481 1482 1483
	if (!enabled) {
		return;
	}
osku's avatar
osku committed
1484

1485
	if (rebuild) {
1486
		btr_search_drop_page_hash_index(block);
osku's avatar
osku committed
1487 1488
	}

1489
	/* Check that the values for hash index build are sensible */
osku's avatar
osku committed
1490

1491
	if (n_fields == 0 && n_bytes == 0) {
osku's avatar
osku committed
1492 1493 1494 1495

		return;
	}

1496 1497
	if (dict_index_get_n_unique_in_tree(index)
	    < btr_search_get_n_fields(n_fields, n_bytes)) {
osku's avatar
osku committed
1498 1499 1500
		return;
	}

1501
	page_t*		page	= buf_block_get_frame(block);
1502 1503 1504 1505
	n_recs = page_get_n_recs(page);

	if (n_recs == 0) {

osku's avatar
osku committed
1506 1507 1508
		return;
	}

1509 1510
	rec = page_rec_get_next_const(page_get_infimum_rec(page));

1511
	if (rec_is_metadata(rec, *index)) {
1512 1513 1514 1515
		rec = page_rec_get_next_const(rec);
		if (!--n_recs) return;
	}

osku's avatar
osku committed
1516 1517 1518
	/* Calculate and cache fold values and corresponding records into
	an array for fast insertion to the hash index */

1519 1520 1521
	folds = static_cast<ulint*>(ut_malloc_nokey(n_recs * sizeof *folds));
	recs = static_cast<const rec_t**>(
		ut_malloc_nokey(n_recs * sizeof *recs));
osku's avatar
osku committed
1522 1523 1524

	n_cached = 0;

Sergei Golubchik's avatar
Sergei Golubchik committed
1525
	ut_a(index->id == btr_page_get_index_id(page));
osku's avatar
osku committed
1526

1527
	offsets = rec_get_offsets(
1528
		rec, index, offsets, true,
1529 1530 1531
		btr_search_get_n_fields(n_fields, n_bytes),
		&heap);
	ut_ad(page_rec_is_supremum(rec)
1532
	      || n_fields == rec_offs_n_fields(offsets) - (n_bytes > 0));
osku's avatar
osku committed
1533

Sergei Golubchik's avatar
Sergei Golubchik committed
1534
	fold = rec_fold(rec, offsets, n_fields, n_bytes, index->id);
osku's avatar
osku committed
1535

1536
	if (left_side) {
osku's avatar
osku committed
1537 1538 1539 1540 1541

		folds[n_cached] = fold;
		recs[n_cached] = rec;
		n_cached++;
	}
1542

osku's avatar
osku committed
1543
	for (;;) {
1544
		next_rec = page_rec_get_next_const(rec);
osku's avatar
osku committed
1545 1546 1547

		if (page_rec_is_supremum(next_rec)) {

1548
			if (!left_side) {
1549

osku's avatar
osku committed
1550 1551 1552 1553 1554
				folds[n_cached] = fold;
				recs[n_cached] = rec;
				n_cached++;
			}

1555
			break;
osku's avatar
osku committed
1556 1557
		}

1558
		offsets = rec_get_offsets(
1559
			next_rec, index, offsets, true,
1560
			btr_search_get_n_fields(n_fields, n_bytes), &heap);
osku's avatar
osku committed
1561
		next_fold = rec_fold(next_rec, offsets, n_fields,
Sergei Golubchik's avatar
Sergei Golubchik committed
1562
				     n_bytes, index->id);
osku's avatar
osku committed
1563 1564 1565 1566

		if (fold != next_fold) {
			/* Insert an entry into the hash index */

1567
			if (left_side) {
osku's avatar
osku committed
1568 1569 1570 1571 1572 1573 1574 1575 1576 1577 1578 1579 1580 1581 1582

				folds[n_cached] = next_fold;
				recs[n_cached] = next_rec;
				n_cached++;
			} else {
				folds[n_cached] = fold;
				recs[n_cached] = rec;
				n_cached++;
			}
		}

		rec = next_rec;
		fold = next_fold;
	}

1583
	btr_search_check_free_space_in_heap(index);
osku's avatar
osku committed
1584

1585
	ahi_latch->wr_lock(SRW_LOCK_CALL);
osku's avatar
osku committed
1586

1587
	if (!btr_search_enabled) {
1588 1589 1590
		goto exit_func;
	}

1591 1592 1593 1594 1595
	/* This counter is decremented every time we drop page
	hash index entries and is incremented here. Since we can
	rebuild hash index for a page that is already hashed, we
	have to take care not to increment the counter in that
	case. */
Sergei Golubchik's avatar
Sergei Golubchik committed
1596
	if (!block->index) {
1597
		assert_block_ahi_empty(block);
1598
		index->search_info->ref_count++;
1599 1600 1601 1602
	} else if (block->curr_n_fields != n_fields
		   || block->curr_n_bytes != n_bytes
		   || block->curr_left_side != left_side) {
		goto exit_func;
1603 1604
	}

osku's avatar
osku committed
1605
	block->n_hash_helps = 0;
1606

1607 1608 1609
	block->curr_n_fields = n_fields & dict_index_t::MAX_N_FIELDS;
	block->curr_n_bytes = n_bytes & ((1U << 15) - 1);
	block->curr_left_side = left_side;
osku's avatar
osku committed
1610 1611
	block->index = index;

1612 1613 1614 1615 1616 1617
	{
		auto part = btr_search_sys.get_part(*index);
		for (ulint i = 0; i < n_cached; i++) {
			ha_insert_for_fold(&part->table, part->heap,
					   folds[i], block, recs[i]);
		}
osku's avatar
osku committed
1618 1619
	}

1620 1621
	MONITOR_INC(MONITOR_ADAPTIVE_HASH_PAGE_ADDED);
	MONITOR_INC_VALUE(MONITOR_ADAPTIVE_HASH_ROW_ADDED, n_cached);
osku's avatar
osku committed
1622
exit_func:
1623
	assert_block_ahi_valid(block);
1624
	ahi_latch->wr_unlock();
osku's avatar
osku committed
1625

1626 1627
	ut_free(folds);
	ut_free(recs);
osku's avatar
osku committed
1628 1629 1630 1631 1632
	if (UNIV_LIKELY_NULL(heap)) {
		mem_heap_free(heap);
	}
}

1633 1634 1635 1636 1637 1638
/** Updates the search info.
@param[in,out]	info	search info
@param[in,out]	cursor	cursor which was just positioned */
void
btr_search_info_update_slow(btr_search_t* info, btr_cur_t* cursor)
{
1639
	srw_lock*	ahi_latch = &btr_search_sys.get_part(*cursor->index)
1640
		->latch;
1641 1642 1643 1644 1645 1646 1647 1648 1649
	buf_block_t*	block = btr_cur_get_block(cursor);

	/* NOTE that the following two function calls do NOT protect
	info or block->n_fields etc. with any semaphore, to save CPU time!
	We cannot assume the fields are consistent when we return from
	those functions! */

	btr_search_info_update_hash(info, cursor);

1650
	bool build_index = btr_search_update_block_hash_info(info, block);
1651 1652 1653 1654 1655 1656 1657 1658 1659 1660 1661 1662 1663 1664 1665 1666 1667 1668 1669 1670 1671 1672 1673 1674 1675 1676 1677 1678

	if (build_index || (cursor->flag == BTR_CUR_HASH_FAIL)) {

		btr_search_check_free_space_in_heap(cursor->index);
	}

	if (cursor->flag == BTR_CUR_HASH_FAIL) {
		/* Update the hash node reference, if appropriate */

#ifdef UNIV_SEARCH_PERF_STAT
		btr_search_n_hash_fail++;
#endif /* UNIV_SEARCH_PERF_STAT */

		btr_search_update_hash_ref(info, block, cursor);
	}

	if (build_index) {
		/* Note that since we did not protect block->n_fields etc.
		with any semaphore, the values can be inconsistent. We have
		to check inside the function call that they make sense. */
		btr_search_build_page_hash_index(cursor->index, block,
						 ahi_latch,
						 block->n_fields,
						 block->n_bytes,
						 block->left_side);
	}
}

1679 1680 1681 1682 1683 1684
/** Move or delete hash entries for moved records, usually in a page split.
If new_block is already hashed, then any hash index for block is dropped.
If new_block is not hashed, and block is hashed, then a new hash index is
built to new_block with the same parameters as block.
@param[in,out]	new_block	destination page
@param[in,out]	block		source page (subject to deletion later) */
osku's avatar
osku committed
1685 1686
void
btr_search_move_or_delete_hash_entries(
1687
	buf_block_t*	new_block,
1688
	buf_block_t*	block)
osku's avatar
osku committed
1689
{
1690 1691
	ut_ad(block->lock.have_x());
	ut_ad(new_block->lock.have_x());
osku's avatar
osku committed
1692

1693 1694 1695
	if (!btr_search_enabled) {
		return;
	}
1696

1697 1698 1699 1700 1701 1702
	dict_index_t* index = block->index;
	if (!index) {
		index = new_block->index;
	} else {
		ut_ad(!new_block->index || index == new_block->index);
	}
1703 1704
	assert_block_ahi_valid(block);
	assert_block_ahi_valid(new_block);
Sergei Golubchik's avatar
Sergei Golubchik committed
1705

1706
	srw_lock* ahi_latch = index
1707 1708
		? &btr_search_sys.get_part(*index)->latch
		: nullptr;
1709

Sergei Golubchik's avatar
Sergei Golubchik committed
1710
	if (new_block->index) {
1711
		btr_search_drop_page_hash_index(block);
1712 1713
		return;
	}
osku's avatar
osku committed
1714

1715
	if (!index) {
osku's avatar
osku committed
1716 1717
		return;
	}
1718

1719
	ahi_latch->rd_lock(SRW_LOCK_CALL);
osku's avatar
osku committed
1720

Sergei Golubchik's avatar
Sergei Golubchik committed
1721
	if (block->index) {
1722 1723 1724
		uint16_t n_fields = block->curr_n_fields;
		uint16_t n_bytes = block->curr_n_bytes;
		bool left_side = block->curr_left_side;
osku's avatar
osku committed
1725 1726 1727

		new_block->n_fields = block->curr_n_fields;
		new_block->n_bytes = block->curr_n_bytes;
1728
		new_block->left_side = left_side;
osku's avatar
osku committed
1729

1730
		ahi_latch->rd_unlock();
osku's avatar
osku committed
1731

1732
		ut_a(n_fields > 0 || n_bytes > 0);
osku's avatar
osku committed
1733

1734
		btr_search_build_page_hash_index(
1735 1736
			index, new_block, ahi_latch,
			n_fields, n_bytes, left_side);
1737 1738 1739
		ut_ad(n_fields == block->curr_n_fields);
		ut_ad(n_bytes == block->curr_n_bytes);
		ut_ad(left_side == block->curr_left_side);
osku's avatar
osku committed
1740 1741 1742
		return;
	}

1743
	ahi_latch->rd_unlock();
osku's avatar
osku committed
1744 1745
}

1746 1747 1748
/** Updates the page hash index when a single record is deleted from a page.
@param[in]	cursor	cursor which was positioned on the record to delete
			using btr_cur_search_, the record is not yet deleted.*/
1749
void btr_search_update_hash_on_delete(btr_cur_t* cursor)
osku's avatar
osku committed
1750 1751
{
	buf_block_t*	block;
Sergei Golubchik's avatar
Sergei Golubchik committed
1752
	const rec_t*	rec;
osku's avatar
osku committed
1753
	ulint		fold;
Sergei Golubchik's avatar
Sergei Golubchik committed
1754
	dict_index_t*	index;
1755
	rec_offs	offsets_[REC_OFFS_NORMAL_SIZE];
osku's avatar
osku committed
1756
	mem_heap_t*	heap		= NULL;
1757
	rec_offs_init(offsets_);
osku's avatar
osku committed
1758

1759
	ut_ad(page_is_leaf(btr_cur_get_page(cursor)));
1760 1761 1762
#ifdef MYSQL_INDEX_DISABLE_AHI
	if (cursor->index->disable_ahi) return;
#endif
1763

1764
	if (!btr_search_enabled) {
1765 1766 1767
		return;
	}

1768
	block = btr_cur_get_block(cursor);
osku's avatar
osku committed
1769

1770
	ut_ad(block->lock.have_x());
osku's avatar
osku committed
1771

1772
	assert_block_ahi_valid(block);
Sergei Golubchik's avatar
Sergei Golubchik committed
1773 1774 1775
	index = block->index;

	if (!index) {
osku's avatar
osku committed
1776 1777 1778 1779

		return;
	}

1780
	ut_ad(block->page.id().space() == index->table->space_id);
Sergei Golubchik's avatar
Sergei Golubchik committed
1781
	ut_a(index == cursor->index);
1782
	ut_a(block->curr_n_fields > 0 || block->curr_n_bytes > 0);
1783
	ut_ad(!dict_index_is_ibuf(index));
osku's avatar
osku committed
1784

Sergei Golubchik's avatar
Sergei Golubchik committed
1785 1786
	rec = btr_cur_get_rec(cursor);

1787
	fold = rec_fold(rec, rec_get_offsets(rec, index, offsets_, true,
1788
					     ULINT_UNDEFINED, &heap),
Sergei Golubchik's avatar
Sergei Golubchik committed
1789
			block->curr_n_fields, block->curr_n_bytes, index->id);
osku's avatar
osku committed
1790 1791 1792
	if (UNIV_LIKELY_NULL(heap)) {
		mem_heap_free(heap);
	}
Sergei Golubchik's avatar
Sergei Golubchik committed
1793

1794
	auto part = btr_search_sys.get_part(*index);
1795

1796
	part->latch.wr_lock(SRW_LOCK_CALL);
1797
	assert_block_ahi_valid(block);
osku's avatar
osku committed
1798

1799 1800
	if (block->index && btr_search_enabled) {
		ut_a(block->index == index);
1801

1802 1803 1804 1805 1806
		if (ha_search_and_delete_if_found(&part->table, part->heap,
						  fold, rec)) {
			MONITOR_INC(MONITOR_ADAPTIVE_HASH_ROW_REMOVED);
		} else {
			MONITOR_INC(MONITOR_ADAPTIVE_HASH_ROW_REMOVE_NOT_FOUND);
1807
		}
1808 1809

		assert_block_ahi_valid(block);
Sergei Golubchik's avatar
Sergei Golubchik committed
1810
	}
osku's avatar
osku committed
1811

1812
	part->latch.wr_unlock();
osku's avatar
osku committed
1813 1814
}

1815 1816 1817
/** Updates the page hash index when a single record is inserted on a page.
@param[in]	cursor	cursor which was positioned to the place to insert
			using btr_cur_search_, and the new record has been
1818 1819
			inserted next to the cursor.
@param[in]	ahi_latch	the adaptive hash index latch */
1820 1821
void btr_search_update_hash_node_on_insert(btr_cur_t *cursor,
                                           srw_lock *ahi_latch)
osku's avatar
osku committed
1822 1823
{
	buf_block_t*	block;
Sergei Golubchik's avatar
Sergei Golubchik committed
1824
	dict_index_t*	index;
osku's avatar
osku committed
1825 1826
	rec_t*		rec;

1827
	ut_ad(ahi_latch == &btr_search_sys.get_part(*cursor->index)->latch);
1828 1829 1830 1831
#ifdef MYSQL_INDEX_DISABLE_AHI
	if (cursor->index->disable_ahi) return;
#endif
	if (!btr_search_enabled) {
1832 1833 1834
		return;
	}

osku's avatar
osku committed
1835 1836
	rec = btr_cur_get_rec(cursor);

1837
	block = btr_cur_get_block(cursor);
osku's avatar
osku committed
1838

1839
	ut_ad(block->lock.have_x());
osku's avatar
osku committed
1840

Sergei Golubchik's avatar
Sergei Golubchik committed
1841 1842 1843
	index = block->index;

	if (!index) {
osku's avatar
osku committed
1844 1845 1846 1847

		return;
	}

Sergei Golubchik's avatar
Sergei Golubchik committed
1848
	ut_a(cursor->index == index);
1849
	ut_ad(!dict_index_is_ibuf(index));
1850
	ahi_latch->wr_lock(SRW_LOCK_CALL);
osku's avatar
osku committed
1851

1852
	if (!block->index || !btr_search_enabled) {
Sergei Golubchik's avatar
Sergei Golubchik committed
1853 1854 1855 1856 1857 1858

		goto func_exit;
	}

	ut_a(block->index == index);

osku's avatar
osku committed
1859
	if ((cursor->flag == BTR_CUR_HASH)
1860 1861
	    && (cursor->n_fields == block->curr_n_fields)
	    && (cursor->n_bytes == block->curr_n_bytes)
1862
	    && !block->curr_left_side) {
1863

1864
		if (ha_search_and_update_if_found(
1865 1866
			&btr_search_sys.get_part(*cursor->index)->table,
			cursor->fold, rec, block,
1867 1868 1869
			page_rec_get_next(rec))) {
			MONITOR_INC(MONITOR_ADAPTIVE_HASH_ROW_UPDATED);
		}
osku's avatar
osku committed
1870

Sergei Golubchik's avatar
Sergei Golubchik committed
1871
func_exit:
1872
		assert_block_ahi_valid(block);
1873
		ahi_latch->wr_unlock();
osku's avatar
osku committed
1874
	} else {
1875
		ahi_latch->wr_unlock();
osku's avatar
osku committed
1876

1877
		btr_search_update_hash_on_insert(cursor, ahi_latch);
osku's avatar
osku committed
1878 1879 1880
	}
}

1881 1882
/** Updates the page hash index when a single record is inserted on a page.
@param[in,out]	cursor		cursor which was positioned to the
osku's avatar
osku committed
1883 1884
				place to insert using btr_cur_search_...,
				and the new record has been inserted next
1885 1886
				to the cursor
@param[in]	ahi_latch	the adaptive hash index latch */
1887 1888
void btr_search_update_hash_on_insert(btr_cur_t *cursor,
                                      srw_lock *ahi_latch)
osku's avatar
osku committed
1889 1890
{
	buf_block_t*	block;
Sergei Golubchik's avatar
Sergei Golubchik committed
1891
	dict_index_t*	index;
1892 1893 1894
	const rec_t*	rec;
	const rec_t*	ins_rec;
	const rec_t*	next_rec;
osku's avatar
osku committed
1895 1896 1897 1898 1899 1900
	ulint		fold;
	ulint		ins_fold;
	ulint		next_fold = 0; /* remove warning (??? bug ???) */
	ulint		n_fields;
	ulint		n_bytes;
	mem_heap_t*	heap		= NULL;
1901 1902
	rec_offs	offsets_[REC_OFFS_NORMAL_SIZE];
	rec_offs*	offsets		= offsets_;
1903
	rec_offs_init(offsets_);
osku's avatar
osku committed
1904

1905
	ut_ad(ahi_latch == &btr_search_sys.get_part(*cursor->index)->latch);
1906
	ut_ad(page_is_leaf(btr_cur_get_page(cursor)));
1907 1908 1909 1910
#ifdef MYSQL_INDEX_DISABLE_AHI
	if (cursor->index->disable_ahi) return;
#endif
	if (!btr_search_enabled) {
1911 1912 1913
		return;
	}

1914
	block = btr_cur_get_block(cursor);
osku's avatar
osku committed
1915

1916
	ut_ad(block->lock.have_x());
1917
	assert_block_ahi_valid(block);
1918

Sergei Golubchik's avatar
Sergei Golubchik committed
1919 1920 1921
	index = block->index;

	if (!index) {
osku's avatar
osku committed
1922 1923 1924 1925

		return;
	}

1926
	ut_ad(block->page.id().space() == index->table->space_id);
1927
	btr_search_check_free_space_in_heap(index);
1928 1929 1930

	rec = btr_cur_get_rec(cursor);

1931
#ifdef MYSQL_INDEX_DISABLE_AHI
1932
	ut_a(!index->disable_ahi);
1933
#endif
Sergei Golubchik's avatar
Sergei Golubchik committed
1934
	ut_a(index == cursor->index);
1935
	ut_ad(!dict_index_is_ibuf(index));
osku's avatar
osku committed
1936 1937 1938

	n_fields = block->curr_n_fields;
	n_bytes = block->curr_n_bytes;
1939
	const bool left_side = block->curr_left_side;
osku's avatar
osku committed
1940

1941 1942
	ins_rec = page_rec_get_next_const(rec);
	next_rec = page_rec_get_next_const(ins_rec);
osku's avatar
osku committed
1943

1944
	offsets = rec_get_offsets(ins_rec, index, offsets, true,
1945
				  ULINT_UNDEFINED, &heap);
Sergei Golubchik's avatar
Sergei Golubchik committed
1946
	ins_fold = rec_fold(ins_rec, offsets, n_fields, n_bytes, index->id);
osku's avatar
osku committed
1947 1948

	if (!page_rec_is_supremum(next_rec)) {
1949
		offsets = rec_get_offsets(
1950
			next_rec, index, offsets, true,
1951
			btr_search_get_n_fields(n_fields, n_bytes), &heap);
osku's avatar
osku committed
1952
		next_fold = rec_fold(next_rec, offsets, n_fields,
Sergei Golubchik's avatar
Sergei Golubchik committed
1953
				     n_bytes, index->id);
osku's avatar
osku committed
1954 1955
	}

Marko Mäkelä's avatar
Marko Mäkelä committed
1956 1957
	/* We must not look up "part" before acquiring ahi_latch. */
	btr_search_sys_t::partition* part= nullptr;
1958 1959
	bool locked = false;

1960
	if (!page_rec_is_infimum(rec) && !rec_is_metadata(rec, *index)) {
1961
		offsets = rec_get_offsets(
1962
			rec, index, offsets, true,
1963
			btr_search_get_n_fields(n_fields, n_bytes), &heap);
Sergei Golubchik's avatar
Sergei Golubchik committed
1964
		fold = rec_fold(rec, offsets, n_fields, n_bytes, index->id);
osku's avatar
osku committed
1965
	} else {
1966
		if (left_side) {
1967
			locked = true;
1968
			ahi_latch->wr_lock(SRW_LOCK_CALL);
osku's avatar
osku committed
1969

1970
			if (!btr_search_enabled || !block->index) {
Sergei Golubchik's avatar
Sergei Golubchik committed
1971 1972 1973
				goto function_exit;
			}

Marko Mäkelä's avatar
Marko Mäkelä committed
1974
			part = btr_search_sys.get_part(*index);
1975 1976 1977
			ha_insert_for_fold(&part->table, part->heap,
					   ins_fold, block, ins_rec);
			MONITOR_INC(MONITOR_ADAPTIVE_HASH_ROW_ADDED);
osku's avatar
osku committed
1978 1979 1980 1981 1982
		}

		goto check_next_rec;
	}

1983 1984 1985
	if (fold != ins_fold) {

		if (!locked) {
1986
			locked = true;
1987
			ahi_latch->wr_lock(SRW_LOCK_CALL);
Sergei Golubchik's avatar
Sergei Golubchik committed
1988

1989
			if (!btr_search_enabled || !block->index) {
Sergei Golubchik's avatar
Sergei Golubchik committed
1990 1991
				goto function_exit;
			}
1992

Marko Mäkelä's avatar
Marko Mäkelä committed
1993
			part = btr_search_sys.get_part(*index);
osku's avatar
osku committed
1994 1995
		}

1996
		if (!left_side) {
1997 1998
			ha_insert_for_fold(&part->table, part->heap,
					   fold, block, rec);
osku's avatar
osku committed
1999
		} else {
2000 2001
			ha_insert_for_fold(&part->table, part->heap,
					   ins_fold, block, ins_rec);
osku's avatar
osku committed
2002
		}
2003
		MONITOR_INC(MONITOR_ADAPTIVE_HASH_ROW_ADDED);
osku's avatar
osku committed
2004 2005 2006 2007 2008
	}

check_next_rec:
	if (page_rec_is_supremum(next_rec)) {

2009
		if (!left_side) {
2010
			if (!locked) {
2011
				locked = true;
2012
				ahi_latch->wr_lock(SRW_LOCK_CALL);
Sergei Golubchik's avatar
Sergei Golubchik committed
2013

2014
				if (!btr_search_enabled || !block->index) {
Sergei Golubchik's avatar
Sergei Golubchik committed
2015 2016
					goto function_exit;
				}
2017

Marko Mäkelä's avatar
Marko Mäkelä committed
2018
				part = btr_search_sys.get_part(*index);
osku's avatar
osku committed
2019
			}
2020

2021 2022 2023
			ha_insert_for_fold(&part->table, part->heap,
					   ins_fold, block, ins_rec);
			MONITOR_INC(MONITOR_ADAPTIVE_HASH_ROW_ADDED);
osku's avatar
osku committed
2024 2025 2026 2027
		}

		goto function_exit;
	}
2028

osku's avatar
osku committed
2029
	if (ins_fold != next_fold) {
2030
		if (!locked) {
2031
			locked = true;
2032
			ahi_latch->wr_lock(SRW_LOCK_CALL);
Sergei Golubchik's avatar
Sergei Golubchik committed
2033

2034
			if (!btr_search_enabled || !block->index) {
Sergei Golubchik's avatar
Sergei Golubchik committed
2035 2036
				goto function_exit;
			}
2037

Marko Mäkelä's avatar
Marko Mäkelä committed
2038
			part = btr_search_sys.get_part(*index);
osku's avatar
osku committed
2039 2040
		}

2041
		if (!left_side) {
2042 2043
			ha_insert_for_fold(&part->table, part->heap,
					   ins_fold, block, ins_rec);
osku's avatar
osku committed
2044
		} else {
2045 2046
			ha_insert_for_fold(&part->table, part->heap,
					   next_fold, block, next_rec);
osku's avatar
osku committed
2047
		}
2048
		MONITOR_INC(MONITOR_ADAPTIVE_HASH_ROW_ADDED);
2049 2050
	}

osku's avatar
osku committed
2051 2052 2053 2054 2055
function_exit:
	if (UNIV_LIKELY_NULL(heap)) {
		mem_heap_free(heap);
	}
	if (locked) {
2056
		ahi_latch->wr_unlock();
osku's avatar
osku committed
2057 2058 2059
	}
}

2060
#if defined UNIV_AHI_DEBUG || defined UNIV_DEBUG
2061 2062 2063 2064 2065 2066 2067 2068 2069 2070 2071 2072 2073 2074 2075 2076 2077 2078 2079 2080 2081 2082 2083 2084 2085
__attribute__((nonnull))
/** @return whether a range of the cells is valid */
static bool ha_validate(const hash_table_t *table,
                        ulint start_index, ulint end_index)
{
  ut_a(start_index <= end_index);
  ut_a(end_index < table->n_cells);

  bool ok= true;

  for (ulint i= start_index; i <= end_index; i++)
  {
    for (auto node= static_cast<const ha_node_t*>(table->array[i].node); node;
         node= node->next)
    {
      if (table->calc_hash(node->fold) != i) {
        ib::error() << "Hash table node fold value " << node->fold
		    << " does not match the cell number " << i;
	ok= false;
      }
    }
  }

  return ok;
}
2086 2087 2088 2089 2090

/** Validates the search system for given hash table.
@param[in]	hash_table_id	hash table to validate
@return TRUE if ok */
static
osku's avatar
osku committed
2091
ibool
2092
btr_search_hash_table_validate(ulint hash_table_id)
osku's avatar
osku committed
2093 2094 2095 2096
{
	ha_node_t*	node;
	ibool		ok		= TRUE;
	ulint		i;
2097
	ulint		cell_count;
osku's avatar
osku committed
2098
	mem_heap_t*	heap		= NULL;
2099 2100
	rec_offs	offsets_[REC_OFFS_NORMAL_SIZE];
	rec_offs*	offsets		= offsets_;
2101

2102
	btr_search_x_lock_all();
2103
	if (!btr_search_enabled) {
2104
		btr_search_x_unlock_all();
2105 2106 2107
		return(TRUE);
	}

2108
	/* How many cells to check before temporarily releasing
2109
	search latches. */
2110
	ulint		chunk_size = 10000;
2111

2112
	rec_offs_init(offsets_);
2113

2114
	mysql_mutex_lock(&buf_pool.mutex);
osku's avatar
osku committed
2115

2116 2117
	auto &part = btr_search_sys.parts[hash_table_id];

2118
	cell_count = part.table.n_cells;
2119

2120
	for (i = 0; i < cell_count; i++) {
2121
		/* We release search latches every once in a while to
2122 2123
		give other queries a chance to run. */
		if ((i != 0) && ((i % chunk_size) == 0)) {
2124

2125
			mysql_mutex_unlock(&buf_pool.mutex);
2126 2127
			btr_search_x_unlock_all();

2128
			os_thread_yield();
2129 2130

			btr_search_x_lock_all();
2131 2132 2133 2134 2135 2136

			if (!btr_search_enabled) {
				ok = true;
				goto func_exit;
			}

2137
			mysql_mutex_lock(&buf_pool.mutex);
2138

2139
			ulint curr_cell_count = part.table.n_cells;
2140 2141 2142 2143 2144 2145 2146 2147 2148

			if (cell_count != curr_cell_count) {

				cell_count = curr_cell_count;

				if (i >= cell_count) {
					break;
				}
			}
2149
		}
2150

2151
		node = static_cast<ha_node_t*>(part.table.array[i].node);
osku's avatar
osku committed
2152

2153
		for (; node != NULL; node = node->next) {
2154
			const buf_block_t*	block
2155
				= buf_pool.block_from_ahi((byte*) node->data);
2156
			index_id_t		page_index_id;
irana's avatar
irana committed
2157

2158
			if (UNIV_LIKELY(block->page.state()
2159 2160 2161 2162 2163 2164 2165
					== BUF_BLOCK_FILE_PAGE)) {

				/* The space and offset are only valid
				for file blocks.  It is possible that
				the block is being freed
				(BUF_BLOCK_REMOVE_HASH, see the
				assertion and the comment below) */
2166 2167 2168 2169 2170 2171 2172
				const page_id_t id(block->page.id());
				if (const buf_page_t* hash_page
				    = buf_pool.page_hash_get_low(
					    id, id.fold())) {
					ut_ad(hash_page == &block->page);
					goto state_ok;
				}
2173 2174
			}

2175 2176 2177 2178 2179 2180 2181
			/* When a block is being freed,
			buf_LRU_search_and_free_block() first removes
			the block from buf_pool.page_hash by calling
			buf_LRU_block_remove_hashed_page(). Then it
			invokes btr_search_drop_page_hash_index(). */
			ut_a(block->page.state() == BUF_BLOCK_REMOVE_HASH);
state_ok:
2182
			ut_ad(!dict_index_is_ibuf(block->index));
2183
			ut_ad(block->page.id().space()
Marko Mäkelä's avatar
Marko Mäkelä committed
2184
			      == block->index->table->space_id);
2185

Sergei Golubchik's avatar
Sergei Golubchik committed
2186 2187
			page_index_id = btr_page_get_index_id(block->frame);

2188
			offsets = rec_get_offsets(
2189
				node->data, block->index, offsets, true,
2190 2191 2192 2193 2194 2195 2196 2197 2198 2199 2200
				btr_search_get_n_fields(block->curr_n_fields,
							block->curr_n_bytes),
				&heap);

			const ulint	fold = rec_fold(
				node->data, offsets,
				block->curr_n_fields,
				block->curr_n_bytes,
				page_index_id);

			if (node->fold != fold) {
2201 2202
				const page_t*	page = block->frame;

osku's avatar
osku committed
2203
				ok = FALSE;
2204 2205 2206

				ib::error() << "Error in an adaptive hash"
					<< " index pointer to page "
2207
					<< block->page.id()
2208 2209 2210 2211 2212 2213
					<< ", ptr mem address "
					<< reinterpret_cast<const void*>(
						node->data)
					<< ", index id " << page_index_id
					<< ", node fold " << node->fold
					<< ", rec fold " << fold;
osku's avatar
osku committed
2214 2215

				fputs("InnoDB: Record ", stderr);
Sergei Golubchik's avatar
Sergei Golubchik committed
2216
				rec_print_new(stderr, node->data, offsets);
osku's avatar
osku committed
2217
				fprintf(stderr, "\nInnoDB: on that page."
Sergei Golubchik's avatar
Sergei Golubchik committed
2218
					" Page mem address %p, is hashed %p,"
2219
					" n fields %lu\n"
2220
					"InnoDB: side %lu\n",
Sergei Golubchik's avatar
Sergei Golubchik committed
2221
					(void*) page, (void*) block->index,
2222
					(ulong) block->curr_n_fields,
2223
					(ulong) block->curr_left_side);
2224
				ut_ad(0);
osku's avatar
osku committed
2225 2226 2227 2228
			}
		}
	}

2229
	for (i = 0; i < cell_count; i += chunk_size) {
2230
		/* We release search latches every once in a while to
2231 2232
		give other queries a chance to run. */
		if (i != 0) {
2233
			mysql_mutex_unlock(&buf_pool.mutex);
2234 2235
			btr_search_x_unlock_all();

2236
			os_thread_yield();
2237 2238

			btr_search_x_lock_all();
2239 2240 2241 2242 2243 2244

			if (!btr_search_enabled) {
				ok = true;
				goto func_exit;
			}

2245
			mysql_mutex_lock(&buf_pool.mutex);
2246

2247
			ulint curr_cell_count = part.table.n_cells;
2248 2249 2250 2251 2252 2253 2254 2255 2256

			if (cell_count != curr_cell_count) {

				cell_count = curr_cell_count;

				if (i >= cell_count) {
					break;
				}
			}
2257 2258
		}

2259 2260
		ulint end_index = ut_min(i + chunk_size - 1, cell_count - 1);

2261
		if (!ha_validate(&part.table, i, end_index)) {
2262 2263
			ok = FALSE;
		}
osku's avatar
osku committed
2264 2265
	}

2266
	mysql_mutex_unlock(&buf_pool.mutex);
2267
func_exit:
2268 2269
	btr_search_x_unlock_all();

osku's avatar
osku committed
2270 2271 2272 2273 2274 2275
	if (UNIV_LIKELY_NULL(heap)) {
		mem_heap_free(heap);
	}

	return(ok);
}
2276 2277 2278 2279 2280 2281 2282 2283 2284 2285 2286 2287 2288 2289 2290

/** Validate the search system.
@return true if ok. */
bool
btr_search_validate()
{
	for (ulint i = 0; i < btr_ahi_parts; ++i) {
		if (!btr_search_hash_table_validate(i)) {
			return(false);
		}
	}

	return(true);
}

2291
#endif /* defined UNIV_AHI_DEBUG || defined UNIV_DEBUG */
2292
#endif /* BTR_CUR_HASH_ADAPT */