Source Code Anylysis of Mysql Index Interface

CREATE TABLE Customer(
ID INT NOT NULL,
LastName CHAR(30) NOT NULL,
FirstName CHAR(30) NOT NULL,
Email CHAR(50) NOT NULL,
INDEX (Email),
PRIMARY KEY(ID)
);

901    /* Primary key index number, used in TABLE::key_info[] */
   1   uint primary_key{0};

## where clause中的条件包含索引键的相等判断

> select * from table_a \
> where id = 1;

> update table_a \
> set name = 'foo' \
> where id = 1;

## where clause中的条件是索引键的范围判断

> select * from table_a \
> where id > 1 and id < 10;
...

## 基类handler当中索引相关的接口
ha_index_init()
ha_index_end()
ha_read_range_first()
|- read_range_first()
ha_read_range_next()
|- read_range_next()
ha_index_read_map()
ha_index_read_last_map()
ha_index_read_idx_map()
ha_index_next()
ha_index_prev()
ha_index_first()
ha_index_last()
ha_index_next_same()
ha_index_or_rnd_end()

## 子类需要具体实现的索引接口（handler中索引相关的虚函数）
index_read_map()
index_read()
index_read_last_map()
index_read_last()
index_read_idx_map()
index_next()
index_prev()
index_first()
index_last()
index_next_same()
read_range_first()
read_range_next()

/**
  Initialize use of index.

  @param idx     Index to use
  @param sorted  Use sorted order

  @return Operation status
    @retval 0     Success
    @retval != 0  Error (error code returned)
*/

int handler::ha_index_init(uint idx, bool sorted) {
  int result;
  if (!(result = index_init(idx, sorted))) inited = INDEX;
  end_range = nullptr;
  return result;
}

/**
  End use of index.

  @return Operation status
    @retval 0     Success
    @retval != 0  Error (error code returned)
*/

int handler::ha_index_end() {
  inited = NONE;
  end_range = nullptr;
  m_record_buffer = nullptr;
  if (m_unique) m_unique->reset(false);
  return index_end();
}

int handler::ha_read_range_first(const key_range *start_key,
                                 const key_range *end_key, bool eq_range,
                                 bool sorted) {
  ...
  result = read_range_first(start_key, end_key, eq_range, sorted);
  ...
}

/** @brief
  Read first row between two ranges.
  Store ranges for future calls to read_range_next.

  @param start_key		Start key. Is 0 if no min range
  @param end_key		End key.  Is 0 if no max range
  @param eq_range_arg	        Set to 1 if start_key == end_key
  @param sorted		Set to 1 if result should be sorted per key

  @note
    Record is read into table->record[0]

  @retval
    0			Found row
  @retval
    HA_ERR_END_OF_FILE	No rows in range
*/
int handler::read_range_first(const key_range *start_key,
                              const key_range *end_key, bool eq_range_arg,
                              bool sorted MY_ATTRIBUTE((unused))) {
  ...
  eq_range = eq_range_arg;
  set_end_range(end_key, RANGE_SCAN_ASC);

  range_key_part = table->key_info[active_index].key_part;
  if (!start_key)  // Read first record
    result = ha_index_first(table->record[0]);
  else
    result = ha_index_read_map(table->record[0], start_key->key,
                               start_key->keypart_map, start_key->flag);
  if (result)
    return (result == HA_ERR_KEY_NOT_FOUND) ? HA_ERR_END_OF_FILE : result;
  if (compare_key(end_range) > 0) {
    /*
      The last read row does not fall in the range. So request
      storage engine to release row lock if possible.
    */
    unlock_row();
    result = HA_ERR_END_OF_FILE;
  }
  return result;
}

int handler::ha_read_range_next() {
  ...
  result = read_range_next();
  ...
}

/** @brief
  Read next row between two endpoints.

  @note
    Record is read into table->record[0]

  @retval
    0			Found row
  @retval
    HA_ERR_END_OF_FILE	No rows in range
*/
int handler::read_range_next() {
  DBUG_TRACE;

  int result;
  if (eq_range) {
    /* We trust that index_next_same always gives a row in range */
    result =
        ha_index_next_same(table->record[0], end_range->key, end_range->length);
  } else {
    result = ha_index_next(table->record[0]);
    if (result) return result;

    if (compare_key(end_range) > 0) {
      /*
        The last read row does not fall in the range. So request
        storage engine to release row lock if possible.
      */
      unlock_row();
      result = HA_ERR_END_OF_FILE;
    }
  }
  return result;
}

/**
  Read [part of] row via [part of] index.
  @param[out] buf          buffer where store the data
  @param      key          Key to search for
  @param      keypart_map  Which part of key to use
  @param      find_flag    Direction/condition on key usage

  @returns Operation status
    @retval  0                   Success (found a record, and function has
                                 set table status to "has row")
    @retval  HA_ERR_END_OF_FILE  Row not found (function has set table status
                                 to "no row"). End of index passed.
    @retval  HA_ERR_KEY_NOT_FOUND Row not found (function has set table status
                                 to "no row"). Index cursor positioned.
    @retval  != 0                Error

  @note Positions an index cursor to the index specified in the handle.
  Fetches the row if available. If the key value is null,
  begin at the first key of the index.
  ha_index_read_map can be restarted without calling index_end on the previous
  index scan and without calling ha_index_init. In this case the
  ha_index_read_map is on the same index as the previous ha_index_scan.
  This is particularly used in conjunction with multi read ranges.
*/

int handler::ha_index_read_map(uchar *buf, const uchar *key,
                               key_part_map keypart_map,
                               enum ha_rkey_function find_flag) {
  ...
  MYSQL_TABLE_IO_WAIT(PSI_TABLE_FETCH_ROW, active_index, result, {
    result = index_read_map(buf, key, keypart_map, find_flag);
  })
  ...
}

(gdb) ptype ha_rkey_function
type = enum ha_rkey_function : int {HA_READ_KEY_EXACT, HA_READ_KEY_OR_NEXT, HA_READ_KEY_OR_PREV, HA_READ_AFTER_KEY, HA_READ_BEFORE_KEY, HA_READ_PREFIX,
    HA_READ_PREFIX_LAST, HA_READ_PREFIX_LAST_OR_PREV, HA_READ_MBR_CONTAIN, HA_READ_MBR_INTERSECT, HA_READ_MBR_WITHIN, HA_READ_MBR_DISJOINT,
    HA_READ_MBR_EQUAL, HA_READ_INVALID = -1}

int ha_index_read_last_map(uchar *buf, const uchar *key,
                             key_part_map keypart_map);

## 具体实现随着存储引擎的不同而变化,在index_read_last_map中实现.

/**
  Initializes an index and read it.

  @see handler::ha_index_read_map.
*/

int handler::ha_index_read_idx_map(uchar *buf, uint index, const uchar *key,
                                   key_part_map keypart_map,
                                   enum ha_rkey_function find_flag);

/**
  Reads the next row via index.

  @param[out] buf  Row data

  @return Operation status.
    @retval  0                   Success
    @retval  HA_ERR_END_OF_FILE  Row not found
    @retval  != 0                Error
*/

int handler::ha_index_next(uchar *buf) {
  ...
  MYSQL_TABLE_IO_WAIT(PSI_TABLE_FETCH_ROW, active_index, result,
                      { result = index_next(buf); })
  ...
}

type = class KEY {
  public:
    uint key_length;
    ulong flags;
    ulong actual_flags;
    uint user_defined_key_parts;
    uint actual_key_parts;
    uint unused_key_parts;
    uint usable_key_parts;
    uint block_size;
    ha_key_alg algorithm;
    bool is_algorithm_explicit;
    plugin_ref parser;
    LEX_CSTRING parser_name;
    KEY_PART_INFO *key_part;
    const char *name;
    ulong *rec_per_key;
    LEX_CSTRING engine_attribute;
    LEX_CSTRING secondary_engine_attribute;
  private:
    double m_in_memory_estimate;
    rec_per_key_t *rec_per_key_float;
  public:
    bool is_visible;
    TABLE *table;
    LEX_CSTRING comment;

    bool is_functional_index(void) const;
    bool has_records_per_key(uint) const;
    rec_per_key_t records_per_key(uint) const;
    void set_records_per_key(uint, rec_per_key_t);
    bool supports_records_per_key(void) const;
    void set_rec_per_key_array(ulong *, rec_per_key_t *);
    double in_memory_estimate(void) const;
    void set_in_memory_estimate(double);
}

(gdb) ptype KEY_PART_INFO
type = class KEY_PART_INFO {
  public:
    Field *field;
    uint offset;
    uint null_offset;
    uint16 length;
    uint16 store_length;
    uint16 fieldnr;
    uint16 key_part_flag;
    uint8 type;
    uint8 null_bit;
    bool bin_cmp;

    void init_from_field(Field *);
    void init_flags(void);
}

enum { NONE = 0, INDEX, RND, SAMPLING } inited;

/**
    End value for a range scan. If this is NULL the range scan has no
    end value. Should also be NULL when there is no ongoing range scan.
    Used by the read_range() functions and also evaluated by pushed
    index conditions.
  */
  key_range *end_range;

(gdb) ptype key_range
type = struct key_range {
    const uchar *key;
    uint length;
    key_part_map keypart_map;
    ha_rkey_function flag;
}
## 由于key中的组成部分可能不会全部使用,结束边界以及判定方法也依赖于调用时的情况,
## 所以需要key_range这一类型表达范围查询的边界.

Record_buffer *m_record_buffer = nullptr;  ///< Buffer for multi-row reads.

/* Filter row ids to weed out duplicates when multi-valued index is used */
  Unique_on_insert *m_unique;

bool eq_range

/**
  This class represents a buffer that can be used for multi-row reads. It is
  allocated by the executor and given to the storage engine through the
  handler, using handler::ha_set_record_buffer(), so that the storage engine
  can fill the buffer with multiple rows in a single read call.

  For now, the record buffer is only used internally by the storage engine as
  a prefetch cache. The storage engine fills the record buffer when the
  executor requests the first record, but it returns a single record only to
  the executor. If the executor wants to access the records in the buffer, it
  has to call a handler function such as handler::ha_index_next() or
  handler::ha_rnd_next(). Then the storage engine will copy the next record
  from the record buffer to the memory area specified in the arguments of the
  handler function, typically TABLE::record[0].
*/
class Record_buffer {
  /// The maximum number of records that can be stored in the buffer.
  ha_rows m_max_records;
  /// The number of bytes available for each record.
  size_t m_record_size;
  /// The number of records currently stored in the buffer.
  ha_rows m_count = 0;
  /// The @c uchar buffer that holds the records.
  uchar *m_buffer;
  /// Tells if end-of-range was found while filling the buffer.
  bool m_out_of_range = false;

 public:
  /**
    Create a new record buffer with the specified size.

    @param records      the number of records that can be stored in the buffer
    @param record_size  the size of each record
    @param buffer       the @c uchar buffer that will hold the records (its
                        size should be at least
                        `Record_buffer::buffer_size(records, record_size)`)
  */
  Record_buffer(ha_rows records, size_t record_size, uchar *buffer)
      : m_max_records(records), m_record_size(record_size), m_buffer(buffer) {}

  /**
    This function calculates how big the @c uchar buffer provided to
    Record_buffer's constructor must be, given a number of records and
    the record size.

    @param records      the maximum number of records in the buffer
    @param record_size  the size of each record
    @return the total number of bytes needed for all the records
  */
  static constexpr size_t buffer_size(ha_rows records, size_t record_size) {
    return static_cast<size_t>(records * record_size);
  }

  /**
    Get the number of records that can be stored in the buffer.
    @return the maximum number of records in the buffer
  */
  ha_rows max_records() const { return m_max_records; }

  /**
    Get the amount of space allocated for each record in the buffer.
    @return the record size
  */
  size_t record_size() const { return m_record_size; }

  /**
    Get the number of records currently stored in the buffer.
    @return the number of records stored in the buffer
  */
  ha_rows records() const { return m_count; }

  /**
    Get the buffer that holds the record on position @a pos.
    @param pos the record number (must be smaller than records())
    @return the @c uchar buffer that holds the specified record
  */
  uchar *record(ha_rows pos) const {
    assert(pos < max_records());
    return m_buffer + m_record_size * pos;
  }

  /**
    Add a new record at the end of the buffer.
    @return the @c uchar buffer of the added record
  */
  uchar *add_record() {
    assert(m_count < max_records());
    return record(m_count++);
  }

  /**
    Remove the record that was last added to the buffer.
  */
  void remove_last() {
    assert(m_count > 0);
    --m_count;
  }

  /**
    Clear the buffer. Remove all the records. The end-of-range flag is
    preserved.
  */
  void clear() { m_count = 0; }

  /**
    Reset the buffer. Remove all records and clear the end-of-range flag.
  */
  void reset() {
    m_count = 0;
    set_out_of_range(false);
  }

  /**
    Set whether the end of the range was reached while filling the buffer.
    @param val true if end of range was reached, false if still within range
  */
  void set_out_of_range(bool val) { m_out_of_range = val; }

  /**
    Check if the end of the range was reached while filling the buffer.
    @retval true if the end range was reached
    @retval false if the scan is still within the range
  */
  bool is_out_of_range() const { return m_out_of_range; }
};

## 与Unique_on_insert一同定义的还有Class Unique,这里也一并看一下Unique的定义.

/**
   Unique -- class for unique (removing of duplicates).
   Puts all values to the TREE. If the tree becomes too big,
   it's dumped to the file. User can request sorted values, or
   just iterate through them. In the last case tree merging is performed in
   memory simultaneously with iteration, so it should be ~2-3x faster.

   Unique values can be read only from final result (not on insert) because
   duplicate values can be contained in different dumped tree files.
*/

class Unique {
  /// Array of file pointers
  Prealloced_array<Merge_chunk, 16> file_ptrs;
  /// Max elements in memory buffer
  ulong max_elements;
  /// Memory buffer size
  ulonglong max_in_memory_size;
  /// Cache file for unique values retrieval fo table read AM in executor
  IO_CACHE file;
  /// Tree to filter duplicates in memory
  TREE tree;
  uchar *record_pointers;
  /// Flush tree to disk
  bool flush();
  /// Element size
  uint size;

 public:
  ulong elements;
  Unique(qsort2_cmp comp_func, void *comp_func_fixed_arg, uint size_arg,
         ulonglong max_in_memory_size_arg);
  ~Unique();
  ulong elements_in_tree() { return tree.elements_in_tree; }

  /**
    Add new value to Unique

    @details The value is inserted either to the tree, or to the duplicate
    weedout table, depending on the mode of operation. If tree's mem buffer is
    full, it's flushed to the disk.

    @param ptr  pointer to the binary string to insert

    @returns
      false  error or duplicate
      true   the value was inserted
  */
  inline bool unique_add(void *ptr) {
    DBUG_TRACE;
    DBUG_PRINT("info", ("tree %u - %lu", tree.elements_in_tree, max_elements));
    if (tree.elements_in_tree > max_elements && flush()) return true;
    return !tree_insert(&tree, ptr, 0, tree.custom_arg);
  }

  bool get(TABLE *table);

  typedef Bounds_checked_array<uint> Imerge_cost_buf_type;

  static double get_use_cost(Imerge_cost_buf_type buffer, uint nkeys,
                             uint key_size, ulonglong max_in_memory_size,
                             const Cost_model_table *cost_model);

  // Returns the number of elements needed in Imerge_cost_buf_type.
  inline static size_t get_cost_calc_buff_size(ulong nkeys, uint key_size,
                                               ulonglong max_in_memory_size) {
    ulonglong max_elems_in_tree =
        (max_in_memory_size / ALIGN_SIZE(sizeof(TREE_ELEMENT) + key_size));
    return 1 + static_cast<size_t>(nkeys / max_elems_in_tree);
  }

  void reset();
  bool walk(tree_walk_action action, void *walk_action_arg);

  uint get_size() const { return size; }
  ulonglong get_max_in_memory_size() const { return max_in_memory_size; }
  bool is_in_memory() { return elements == 0; }
  friend int unique_write_to_file(void *v_key, element_count count,
                                  void *unique);
  friend int unique_write_to_ptrs(void *v_key, element_count count,
                                  void *unique);
};

/**
  Unique_on_insert -- similar to above, but rejects duplicates on insert, not
  just on read of the final result.
  To achieve this values are inserted into mem tmp table which uses index to
  detect duplicate keys. When memory buffer is full, tmp table is dumped to a
  disk-based tmp table.
*/

class Unique_on_insert {
  /// Element size
  uint m_size;
  /// Duplicate weedout tmp table
  TABLE *m_table{nullptr};

 public:
  Unique_on_insert(uint size) : m_size(size) {}
  /**
    Add row id to the filter

    @param ptr pointer to the rowid

    @returns
      false  rowid successfully inserted
      true   duplicate or error
  */
  bool unique_add(void *ptr);

  /**
    Initialize duplicate filter - allocate duplicate weedout tmp table

    @returns
      false initialization succeeded
      true  an error occur
  */
  bool init();

  /**
    Reset filter - drop all rowid records

    @param reinit  Whether to restart index scan
  */
  void reset(bool reinit);

  /**
    Cleanup unique filter
  */
  void cleanup();
};