Optimize join probe stage if one hash table key has many entries

[windtalker]

Enhancement

In TiFlash, the entry of a join hash table is <key, RowRefList>, where RowRefList is a list of the rows that has the same key, and each element if the RowRefList is a pair of <block_index, row_index>. During hash join probe stage, if a probe row has an existing key in the hash table, it will combine all the matched rows in the RowRefList using AddFound, inside AddFound, it just iterator over the RowRefList and insert the data row by row

tiflash/dbms/src/Interpreters/JoinPartition.cpp

Lines 1321 to 1329 in e597b78

	for (auto current = &static_cast<const typename Map::mapped_type::Base_t &>(it->getMapped());
	current != nullptr;
	current = current->next)
	{
	for (size_t j = 0; j < num_columns_to_add; ++j)
	added_columns[j]->insertFrom(
	*current->block->getByPosition(right_indexes[j]).column.get(),
	current->row_num);
	}

If the list is very long (~10000), it will take a lot if time in AddFound. We need to find a way to optimize this implementation.

A straightforward optimization is to cache AddFound result of such key, so next time when a probe row which has the same key comes, we can just use insertRange to batch insert the data instead of iterator over RowRefList and insert the data row by row