OmniSciDB  c0231cc57d
 All Classes Namespaces Files Functions Variables Typedefs Enumerations Enumerator Friends Macros Groups Pages
HashtableRecycler Class Reference

#include <HashtableRecycler.h>

+ Inheritance diagram for HashtableRecycler:
+ Collaboration diagram for HashtableRecycler:

Public Member Functions

 HashtableRecycler (CacheItemType hashtable_type, int num_gpus)
 
void putItemToCache (QueryPlanHash key, std::shared_ptr< HashTable > item_ptr, CacheItemType item_type, DeviceIdentifier device_identifier, size_t item_size, size_t compute_time, std::optional< HashtableCacheMetaInfo > meta_info=std::nullopt) override
 
void initCache () override
 
void clearCache () override
 
void markCachedItemAsDirty (size_t table_key, std::unordered_set< QueryPlanHash > &key_set, CacheItemType item_type, DeviceIdentifier device_identifier) override
 
std::string toString () const override
 
bool checkOverlapsHashtableBucketCompatability (const OverlapsHashTableMetaInfo &candidate_bucket_dim, const OverlapsHashTableMetaInfo &target_bucket_dim) const
 
std::tuple< QueryPlanHash,
std::shared_ptr< HashTable >
, std::optional
< HashtableCacheMetaInfo > > 
getCachedHashtableWithoutCacheKey (std::set< size_t > &visited, CacheItemType hash_table_type, DeviceIdentifier device_identifier)
 
void addQueryPlanDagForTableKeys (size_t hashed_query_plan_dag, const std::unordered_set< size_t > &table_keys)
 
std::optional
< std::unordered_set< size_t > > 
getMappedQueryPlanDagsWithTableKey (size_t table_key) const
 
void removeTableKeyInfoFromQueryPlanDagMap (size_t table_key)
 
- Public Member Functions inherited from DataRecycler< std::shared_ptr< HashTable >, HashtableCacheMetaInfo >
 DataRecycler (const std::vector< CacheItemType > &item_types, size_t total_cache_size, size_t max_item_size, int num_gpus)
 
virtual ~DataRecycler ()=default
 
virtual std::shared_ptr
< HashTable
getItemFromCache (QueryPlanHash key, CacheItemType item_type, DeviceIdentifier device_identifier, std::optional< HashtableCacheMetaInfo > meta_info=std::nullopt)=0
 
void markCachedItemAsDirtyImpl (QueryPlanHash key, CachedItemContainer &m) const
 
bool isCachedItemDirty (QueryPlanHash key, CachedItemContainer &m) const
 
std::shared_ptr
< CachedItemContainer
getCachedItemContainer (CacheItemType item_type, DeviceIdentifier device_identifier) const
 
std::optional< CachedItem
< std::shared_ptr< HashTable >
, HashtableCacheMetaInfo > > 
getCachedItemWithoutConsideringMetaInfo (QueryPlanHash key, CacheItemType item_type, DeviceIdentifier device_identifier, CachedItemContainer &m, std::lock_guard< std::mutex > &lock)
 
size_t getCurrentNumCachedItems (CacheItemType item_type, DeviceIdentifier device_identifier) const
 
size_t getCurrentNumDirtyCachedItems (CacheItemType item_type, DeviceIdentifier device_identifier) const
 
size_t getCurrentNumCleanCachedItems (CacheItemType item_type, DeviceIdentifier device_identifier) const
 
size_t getCurrentCacheSizeForDevice (CacheItemType item_type, DeviceIdentifier device_identifier) const
 
std::shared_ptr< CacheItemMetricgetCachedItemMetric (CacheItemType item_type, DeviceIdentifier device_identifier, QueryPlanHash key) const
 
void setTotalCacheSize (CacheItemType item_type, size_t new_total_cache_size)
 
void setMaxCacheItemSize (CacheItemType item_type, size_t new_max_cache_item_size)
 

Static Public Member Functions

static HashtableAccessPathInfo getHashtableAccessPathInfo (const std::vector< InnerOuter > &inner_outer_pairs, const std::vector< InnerOuterStringOpInfos > &inner_outer_string_op_infos_pairs, const SQLOps op_type, const JoinType join_type, const HashTableBuildDagMap &hashtable_build_dag_map, int device_count, int shard_count, const std::vector< std::vector< Fragmenter_Namespace::FragmentInfo >> &frags_for_device, Executor *executor)
 
static size_t getJoinColumnInfoHash (std::vector< const Analyzer::ColumnVar * > &inner_cols, std::vector< const Analyzer::ColumnVar * > &outer_cols, Executor *executor)
 
static bool isSafeToCacheHashtable (const TableIdToNodeMap &table_id_to_node_map, bool need_dict_translation, const std::vector< InnerOuterStringOpInfos > &inner_outer_string_op_info_pairs, const int table_id)
 
static bool isInvalidHashTableCacheKey (const std::vector< QueryPlanHash > &cache_keys)
 

Public Attributes

 g_hashtable_cache_total_bytes
 
 g_max_cacheable_hashtable_size_bytes
 
 num_gpus
 

Private Member Functions

bool hasItemInCache (QueryPlanHash key, CacheItemType item_type, DeviceIdentifier device_identifier, std::lock_guard< std::mutex > &lock, std::optional< HashtableCacheMetaInfo > meta_info=std::nullopt) const override
 
void removeItemFromCache (QueryPlanHash key, CacheItemType item_type, DeviceIdentifier device_identifier, std::lock_guard< std::mutex > &lock, std::optional< HashtableCacheMetaInfo > meta_info=std::nullopt) override
 
void cleanupCacheForInsertion (CacheItemType item_type, DeviceIdentifier device_identifier, size_t required_size, std::lock_guard< std::mutex > &lock, std::optional< HashtableCacheMetaInfo > meta_info=std::nullopt) override
 
void removeCachedHashtableBuiltFromSyntheticTable (CacheItemType item_type, DeviceIdentifier device_identifier, std::lock_guard< std::mutex > &lock)
 

Private Attributes

std::unordered_map< size_t,
std::unordered_set< size_t > > 
table_key_to_query_plan_dag_map_
 

Additional Inherited Members

- Public Types inherited from DataRecycler< std::shared_ptr< HashTable >, HashtableCacheMetaInfo >
using CachedItemContainer = std::vector< CachedItem< std::shared_ptr< HashTable >, HashtableCacheMetaInfo >>
 
using PerDeviceCacheItemContainer = std::unordered_map< DeviceIdentifier, std::shared_ptr< CachedItemContainer >>
 
using PerTypeCacheItemContainer = std::unordered_map< CacheItemType, std::shared_ptr< PerDeviceCacheItemContainer >>
 
using PerTypeCacheMetricTracker = std::unordered_map< CacheItemType, CacheMetricTracker >
 
- Protected Member Functions inherited from DataRecycler< std::shared_ptr< HashTable >, HashtableCacheMetaInfo >
void removeCachedItemFromBeginning (CacheItemType item_type, DeviceIdentifier device_identifier, int offset)
 
void sortCacheContainerByQueryMetric (CacheItemType item_type, DeviceIdentifier device_identifier)
 
std::mutex & getCacheLock () const
 
CacheMetricTrackergetMetricTracker (CacheItemType item_type)
 
CacheMetricTracker const & getMetricTracker (CacheItemType item_type) const
 
std::unordered_set
< CacheItemType > const & 
getCacheItemType () const
 
PerTypeCacheItemContainer const & getItemCache () const
 

Detailed Description

Definition at line 53 of file HashtableRecycler.h.

Constructor & Destructor Documentation

HashtableRecycler::HashtableRecycler ( CacheItemType  hashtable_type,
int  num_gpus 
)
inline

Definition at line 56 of file HashtableRecycler.h.

57  : DataRecycler({hashtable_type},
DataRecycler(const std::vector< CacheItemType > &item_types, size_t total_cache_size, size_t max_item_size, int num_gpus)
Definition: DataRecycler.h:460

Member Function Documentation

void HashtableRecycler::addQueryPlanDagForTableKeys ( size_t  hashed_query_plan_dag,
const std::unordered_set< size_t > &  table_keys 
)

Definition at line 507 of file HashtableRecycler.cpp.

References DataRecycler< std::shared_ptr< HashTable >, HashtableCacheMetaInfo >::getCacheLock(), and table_key_to_query_plan_dag_map_.

509  {
510  std::lock_guard<std::mutex> lock(getCacheLock());
511  for (auto table_key : table_keys) {
512  auto itr = table_key_to_query_plan_dag_map_.try_emplace(table_key).first;
513  itr->second.insert(hashed_query_plan_dag);
514  }
515 }
std::unordered_map< size_t, std::unordered_set< size_t > > table_key_to_query_plan_dag_map_

+ Here is the call graph for this function:

bool HashtableRecycler::checkOverlapsHashtableBucketCompatability ( const OverlapsHashTableMetaInfo candidate_bucket_dim,
const OverlapsHashTableMetaInfo target_bucket_dim 
) const

Definition at line 329 of file HashtableRecycler.cpp.

References OverlapsHashTableMetaInfo::bucket_sizes, OverlapsHashTableMetaInfo::overlaps_bucket_threshold, and OverlapsHashTableMetaInfo::overlaps_max_table_size_bytes.

Referenced by hasItemInCache(), and putItemToCache().

331  {
332  if (candidate.bucket_sizes.size() != target.bucket_sizes.size()) {
333  return false;
334  }
335  for (size_t i = 0; i < candidate.bucket_sizes.size(); i++) {
336  if (std::abs(target.bucket_sizes[i] - candidate.bucket_sizes[i]) > 1e-4) {
337  return false;
338  }
339  }
340  auto threshold_check =
341  candidate.overlaps_bucket_threshold == target.overlaps_bucket_threshold;
342  auto hashtable_size_check =
343  candidate.overlaps_max_table_size_bytes == target.overlaps_max_table_size_bytes;
344  return threshold_check && hashtable_size_check;
345 }

+ Here is the caller graph for this function:

void HashtableRecycler::cleanupCacheForInsertion ( CacheItemType  item_type,
DeviceIdentifier  device_identifier,
size_t  required_size,
std::lock_guard< std::mutex > &  lock,
std::optional< HashtableCacheMetaInfo meta_info = std::nullopt 
)
overrideprivatevirtual

Implements DataRecycler< std::shared_ptr< HashTable >, HashtableCacheMetaInfo >.

Definition at line 202 of file HashtableRecycler.cpp.

References g_is_test_env, DataRecycler< std::shared_ptr< HashTable >, HashtableCacheMetaInfo >::getMetricTracker(), REMOVE, DataRecycler< std::shared_ptr< HashTable >, HashtableCacheMetaInfo >::removeCachedItemFromBeginning(), and DataRecycler< std::shared_ptr< HashTable >, HashtableCacheMetaInfo >::sortCacheContainerByQueryMetric().

Referenced by putItemToCache().

207  {
208  // sort the vector based on the importance of the cached items (by # referenced, size
209  // and compute time) and then remove unimportant cached items
210  int elimination_target_offset = 0;
211  size_t removed_size = 0;
212  auto& metric_tracker = getMetricTracker(item_type);
213  auto actual_space_to_free = metric_tracker.getTotalCacheSize() / 2;
214  if (!g_is_test_env && required_size < actual_space_to_free) {
215  // remove enough items to avoid too frequent cache cleanup
216  // we do not apply thin to test code since test scenarios are designed to
217  // specific size of items and their caches
218  required_size = actual_space_to_free;
219  }
220  metric_tracker.sortCacheInfoByQueryMetric(device_identifier);
221  auto cached_item_metrics = metric_tracker.getCacheItemMetrics(device_identifier);
222  sortCacheContainerByQueryMetric(item_type, device_identifier);
223 
224  // collect targets to eliminate
225  for (auto& metric : cached_item_metrics) {
226  auto target_size = metric->getMemSize();
227  ++elimination_target_offset;
228  removed_size += target_size;
229  if (removed_size > required_size) {
230  break;
231  }
232  }
233 
234  // eliminate targets in 1) cache container and 2) their metrics
235  removeCachedItemFromBeginning(item_type, device_identifier, elimination_target_offset);
236  metric_tracker.removeMetricFromBeginning(device_identifier, elimination_target_offset);
237 
238  // update the current cache size after this cleanup
239  metric_tracker.updateCurrentCacheSize(
240  device_identifier, CacheUpdateAction::REMOVE, removed_size);
241 }
CacheMetricTracker & getMetricTracker(CacheItemType item_type)
Definition: DataRecycler.h:656
bool g_is_test_env
Definition: Execute.cpp:141
void sortCacheContainerByQueryMetric(CacheItemType item_type, DeviceIdentifier device_identifier)
Definition: DataRecycler.h:634
void removeCachedItemFromBeginning(CacheItemType item_type, DeviceIdentifier device_identifier, int offset)
Definition: DataRecycler.h:623

+ Here is the call graph for this function:

+ Here is the caller graph for this function:

void HashtableRecycler::clearCache ( )
overridevirtual

Implements DataRecycler< std::shared_ptr< HashTable >, HashtableCacheMetaInfo >.

Definition at line 243 of file HashtableRecycler.cpp.

References CacheMetricTracker::clearCacheMetricTracker(), DataRecyclerUtil::CPU_DEVICE_IDENTIFIER, DataRecycler< std::shared_ptr< HashTable >, HashtableCacheMetaInfo >::getCacheItemType(), DataRecycler< std::shared_ptr< HashTable >, HashtableCacheMetaInfo >::getCacheLock(), DataRecyclerUtil::getDeviceIdentifierString(), DataRecycler< std::shared_ptr< HashTable >, HashtableCacheMetaInfo >::getItemCache(), DataRecycler< std::shared_ptr< HashTable >, HashtableCacheMetaInfo >::getMetricTracker(), table_key_to_query_plan_dag_map_, and VLOG.

243  {
244  std::lock_guard<std::mutex> lock(getCacheLock());
245  for (auto& item_type : getCacheItemType()) {
247  auto item_cache = getItemCache().find(item_type)->second;
248  for (auto& kv : *item_cache) {
249  if (!kv.second->empty()) {
250  VLOG(1) << "[" << item_type << ", "
253  << "] clear cache (# items: " << kv.second->size() << ")";
254  kv.second->clear();
255  }
256  }
257  }
259 }
static std::string getDeviceIdentifierString(DeviceIdentifier device_identifier)
Definition: DataRecycler.h:138
CacheMetricTracker & getMetricTracker(CacheItemType item_type)
Definition: DataRecycler.h:656
void clearCacheMetricTracker()
Definition: DataRecycler.h:319
std::unordered_map< size_t, std::unordered_set< size_t > > table_key_to_query_plan_dag_map_
std::unordered_set< CacheItemType > const & getCacheItemType() const
Definition: DataRecycler.h:666
static constexpr DeviceIdentifier CPU_DEVICE_IDENTIFIER
Definition: DataRecycler.h:136
#define VLOG(n)
Definition: Logger.h:316

+ Here is the call graph for this function:

std::tuple< QueryPlanHash, std::shared_ptr< HashTable >, std::optional< HashtableCacheMetaInfo > > HashtableRecycler::getCachedHashtableWithoutCacheKey ( std::set< size_t > &  visited,
CacheItemType  hash_table_type,
DeviceIdentifier  device_identifier 
)

Definition at line 494 of file HashtableRecycler.cpp.

References EMPTY_HASHED_PLAN_DAG_KEY, DataRecycler< std::shared_ptr< HashTable >, HashtableCacheMetaInfo >::getCachedItemContainer(), and DataRecycler< std::shared_ptr< HashTable >, HashtableCacheMetaInfo >::getCacheLock().

496  {
497  std::lock_guard<std::mutex> lock(getCacheLock());
498  auto hashtable_cache = getCachedItemContainer(hash_table_type, device_identifier);
499  for (auto& ht : *hashtable_cache) {
500  if (!visited.count(ht.key)) {
501  return std::make_tuple(ht.key, ht.cached_item, ht.meta_info);
502  }
503  }
504  return std::make_tuple(EMPTY_HASHED_PLAN_DAG_KEY, nullptr, std::nullopt);
505 }
constexpr QueryPlanHash EMPTY_HASHED_PLAN_DAG_KEY
std::shared_ptr< CachedItemContainer > getCachedItemContainer(CacheItemType item_type, DeviceIdentifier device_identifier) const
Definition: DataRecycler.h:530

+ Here is the call graph for this function:

HashtableAccessPathInfo HashtableRecycler::getHashtableAccessPathInfo ( const std::vector< InnerOuter > &  inner_outer_pairs,
const std::vector< InnerOuterStringOpInfos > &  inner_outer_string_op_infos_pairs,
const SQLOps  op_type,
const JoinType  join_type,
const HashTableBuildDagMap hashtable_build_dag_map,
int  device_count,
int  shard_count,
const std::vector< std::vector< Fragmenter_Namespace::FragmentInfo >> &  frags_for_device,
Executor executor 
)
static

Definition at line 412 of file HashtableRecycler.cpp.

References CHECK_GE, CHECK_GT, HashJoin::collectFragmentIds(), EMPTY_HASHED_PLAN_DAG_KEY, getJoinColumnInfoHash(), HashtableAccessPathInfo::hashed_query_plan_dag, kDirect, HashtableAccessPathInfo::table_keys, and toString().

Referenced by PerfectJoinHashTable::reify(), RangeJoinHashTable::reifyWithLayout(), OverlapsJoinHashTable::reifyWithLayout(), and BaselineJoinHashTable::reifyWithLayout().

421  {
422  CHECK_GT(device_count, (int)0);
423  CHECK_GE(shard_count, (int)0);
424  std::vector<const Analyzer::ColumnVar*> inner_cols_vec, outer_cols_vec;
425  size_t join_qual_info = EMPTY_HASHED_PLAN_DAG_KEY;
426  for (auto& join_col_pair : inner_outer_pairs) {
427  inner_cols_vec.push_back(join_col_pair.first);
428  // extract inner join col's id
429  // b/c when the inner col comes from a subquery's resulset,
430  // table id / rte_index can be different even if we have the same
431  // subquery's semantic, i.e., project col A from table T
432  boost::hash_combine(join_qual_info,
433  executor->getQueryPlanDagCache().getJoinColumnsInfoHash(
434  join_col_pair.first, JoinColumnSide::kDirect, true));
435  boost::hash_combine(join_qual_info, op_type);
436  boost::hash_combine(join_qual_info, join_type);
437  auto outer_col_var = dynamic_cast<const Analyzer::ColumnVar*>(join_col_pair.second);
438  boost::hash_combine(join_qual_info, join_col_pair.first->get_type_info().toString());
439  if (outer_col_var) {
440  outer_cols_vec.push_back(outer_col_var);
441  if (join_col_pair.first->get_type_info().is_dict_encoded_string()) {
442  // add comp param for dict encoded string
443  boost::hash_combine(join_qual_info,
444  executor->getQueryPlanDagCache().getJoinColumnsInfoHash(
445  outer_col_var, JoinColumnSide::kDirect, true));
446  boost::hash_combine(join_qual_info, outer_col_var->get_type_info().toString());
447  }
448  }
449  }
450 
451  if (inner_outer_string_op_infos_pairs.size()) {
452  boost::hash_combine(join_qual_info, ::toString(inner_outer_string_op_infos_pairs));
453  }
454 
455  auto join_cols_info = getJoinColumnInfoHash(inner_cols_vec, outer_cols_vec, executor);
456  HashtableAccessPathInfo access_path_info(device_count);
457  auto it = hashtable_build_dag_map.find(join_cols_info);
458  if (it != hashtable_build_dag_map.end()) {
459  size_t hashtable_access_path = EMPTY_HASHED_PLAN_DAG_KEY;
460  boost::hash_combine(hashtable_access_path, it->second.inner_cols_access_path);
461  boost::hash_combine(hashtable_access_path, join_qual_info);
462  if (inner_cols_vec.front()->get_type_info().is_dict_encoded_string()) {
463  boost::hash_combine(hashtable_access_path, it->second.outer_cols_access_path);
464  }
465  boost::hash_combine(hashtable_access_path, shard_count);
466 
467  if (!shard_count) {
468  const auto frag_list = HashJoin::collectFragmentIds(frags_for_device[0]);
469  auto cache_key_for_device = hashtable_access_path;
470  // no sharding, so all devices have the same fragments
471  boost::hash_combine(cache_key_for_device, frag_list);
472  for (int i = 0; i < device_count; ++i) {
473  access_path_info.hashed_query_plan_dag[i] = cache_key_for_device;
474  }
475  } else {
476  // we need to retrieve specific fragments for each device
477  // and consider them to make a cache key for it
478  for (int i = 0; i < device_count; ++i) {
479  const auto frag_list_for_device =
480  HashJoin::collectFragmentIds(frags_for_device[i]);
481  auto cache_key_for_device = hashtable_access_path;
482  boost::hash_combine(cache_key_for_device, frag_list_for_device);
483  access_path_info.hashed_query_plan_dag[i] = cache_key_for_device;
484  }
485  }
486  access_path_info.table_keys = it->second.inputTableKeys;
487  }
488  return access_path_info;
489 }
static std::vector< int > collectFragmentIds(const std::vector< Fragmenter_Namespace::FragmentInfo > &fragments)
Definition: HashJoin.cpp:446
constexpr QueryPlanHash EMPTY_HASHED_PLAN_DAG_KEY
static size_t getJoinColumnInfoHash(std::vector< const Analyzer::ColumnVar * > &inner_cols, std::vector< const Analyzer::ColumnVar * > &outer_cols, Executor *executor)
#define CHECK_GE(x, y)
Definition: Logger.h:235
#define CHECK_GT(x, y)
Definition: Logger.h:234
std::string toString() const override

+ Here is the call graph for this function:

+ Here is the caller graph for this function:

size_t HashtableRecycler::getJoinColumnInfoHash ( std::vector< const Analyzer::ColumnVar * > &  inner_cols,
std::vector< const Analyzer::ColumnVar * > &  outer_cols,
Executor executor 
)
static

Definition at line 347 of file HashtableRecycler.cpp.

References EMPTY_HASHED_PLAN_DAG_KEY.

Referenced by getHashtableAccessPathInfo().

350  {
351  auto hashed_join_col_info = EMPTY_HASHED_PLAN_DAG_KEY;
352  boost::hash_combine(
353  hashed_join_col_info,
354  executor->getQueryPlanDagCache().translateColVarsToInfoHash(inner_cols, false));
355  boost::hash_combine(
356  hashed_join_col_info,
357  executor->getQueryPlanDagCache().translateColVarsToInfoHash(outer_cols, false));
358  return hashed_join_col_info;
359 }
constexpr QueryPlanHash EMPTY_HASHED_PLAN_DAG_KEY

+ Here is the caller graph for this function:

std::optional< std::unordered_set< size_t > > HashtableRecycler::getMappedQueryPlanDagsWithTableKey ( size_t  table_key) const

Definition at line 518 of file HashtableRecycler.cpp.

References DataRecycler< std::shared_ptr< HashTable >, HashtableCacheMetaInfo >::getCacheLock(), and table_key_to_query_plan_dag_map_.

518  {
519  std::lock_guard<std::mutex> lock(getCacheLock());
520  auto it = table_key_to_query_plan_dag_map_.find(table_key);
521  return it != table_key_to_query_plan_dag_map_.end() ? std::make_optional(it->second)
522  : std::nullopt;
523 }
std::unordered_map< size_t, std::unordered_set< size_t > > table_key_to_query_plan_dag_map_

+ Here is the call graph for this function:

bool HashtableRecycler::hasItemInCache ( QueryPlanHash  key,
CacheItemType  item_type,
DeviceIdentifier  device_identifier,
std::lock_guard< std::mutex > &  lock,
std::optional< HashtableCacheMetaInfo meta_info = std::nullopt 
) const
overrideprivatevirtual

Implements DataRecycler< std::shared_ptr< HashTable >, HashtableCacheMetaInfo >.

Definition at line 21 of file HashtableRecycler.cpp.

References CHECK, checkOverlapsHashtableBucketCompatability(), EMPTY_HASHED_PLAN_DAG_KEY, g_enable_data_recycler, g_use_hashtable_cache, DataRecycler< std::shared_ptr< HashTable >, HashtableCacheMetaInfo >::getCachedItemContainer(), and OVERLAPS_HT.

Referenced by putItemToCache().

26  {
29  return false;
30  }
31  auto hashtable_cache = getCachedItemContainer(item_type, device_identifier);
32  // hashtable cache of the *any* device type should be properly initialized
33  CHECK(hashtable_cache);
34  auto candidate_ht_it = std::find_if(
35  hashtable_cache->begin(), hashtable_cache->end(), [&key](const auto& cached_item) {
36  return cached_item.key == key;
37  });
38  if (candidate_ht_it != hashtable_cache->end()) {
39  if (item_type == OVERLAPS_HT) {
40  CHECK(candidate_ht_it->meta_info && candidate_ht_it->meta_info->overlaps_meta_info);
41  CHECK(meta_info && meta_info->overlaps_meta_info);
43  *candidate_ht_it->meta_info->overlaps_meta_info,
44  *meta_info->overlaps_meta_info)) {
45  return true;
46  }
47  } else {
48  return true;
49  }
50  }
51  return false;
52 }
constexpr QueryPlanHash EMPTY_HASHED_PLAN_DAG_KEY
std::shared_ptr< CachedItemContainer > getCachedItemContainer(CacheItemType item_type, DeviceIdentifier device_identifier) const
Definition: DataRecycler.h:530
bool g_enable_data_recycler
Definition: Execute.cpp:146
bool checkOverlapsHashtableBucketCompatability(const OverlapsHashTableMetaInfo &candidate_bucket_dim, const OverlapsHashTableMetaInfo &target_bucket_dim) const
#define CHECK(condition)
Definition: Logger.h:222
bool g_use_hashtable_cache
Definition: Execute.cpp:147

+ Here is the call graph for this function:

+ Here is the caller graph for this function:

void HashtableRecycler::initCache ( )
inlineoverridevirtual
bool HashtableRecycler::isInvalidHashTableCacheKey ( const std::vector< QueryPlanHash > &  cache_keys)
static

Definition at line 404 of file HashtableRecycler.cpp.

References EMPTY_HASHED_PLAN_DAG_KEY.

Referenced by PerfectJoinHashTable::reify(), RangeJoinHashTable::reifyWithLayout(), OverlapsJoinHashTable::reifyWithLayout(), and BaselineJoinHashTable::reifyWithLayout().

405  {
406  return cache_keys.empty() ||
407  std::any_of(cache_keys.cbegin(), cache_keys.cend(), [](QueryPlanHash key) {
408  return key == EMPTY_HASHED_PLAN_DAG_KEY;
409  });
410 }
constexpr QueryPlanHash EMPTY_HASHED_PLAN_DAG_KEY
size_t QueryPlanHash

+ Here is the caller graph for this function:

bool HashtableRecycler::isSafeToCacheHashtable ( const TableIdToNodeMap table_id_to_node_map,
bool  need_dict_translation,
const std::vector< InnerOuterStringOpInfos > &  inner_outer_string_op_info_pairs,
const int  table_id 
)
static

Definition at line 361 of file HashtableRecycler.cpp.

Referenced by PerfectJoinHashTable::initHashTableForDevice(), BaselineJoinHashTable::initHashTableForDevice(), PerfectJoinHashTable::reify(), and BaselineJoinHashTable::reifyWithLayout().

365  {
366  // if hashtable is built from subquery's resultset we need to check
367  // 1) whether resulset rows can have inconsistency, e.g., rows can randomly be
368  // permutated per execution and 2) whether it needs dictionary translation for hashtable
369  // building to recycle the hashtable safely
370  auto getNodeByTableId =
371  [&table_id_to_node_map](const int table_id) -> const RelAlgNode* {
372  auto it = table_id_to_node_map.find(table_id);
373  if (it != table_id_to_node_map.end()) {
374  return it->second;
375  }
376  return nullptr;
377  };
378  bool found_sort_node = false;
379  bool found_project_node = false;
380  if (table_id < 0) {
381  auto origin_table_id = table_id * -1;
382  auto inner_node = getNodeByTableId(origin_table_id);
383  if (!inner_node) {
384  // we have to keep the node info of temporary resultset
385  // so in this case we are not safe to recycle the hashtable
386  return false;
387  }
388  // it is not safe to recycle the hashtable when
389  // this resultset may have resultset ordering inconsistency and/or
390  // need dictionary translation for hashtable building
391  auto sort_node = dynamic_cast<const RelSort*>(inner_node);
392  if (sort_node) {
393  found_sort_node = true;
394  } else {
395  auto project_node = dynamic_cast<const RelProject*>(inner_node);
396  if (project_node) {
397  found_project_node = true;
398  }
399  }
400  }
401  return !(found_sort_node || (found_project_node && need_dict_translation));
402 }

+ Here is the caller graph for this function:

void HashtableRecycler::markCachedItemAsDirty ( size_t  table_key,
std::unordered_set< QueryPlanHash > &  key_set,
CacheItemType  item_type,
DeviceIdentifier  device_identifier 
)
overridevirtual

Implements DataRecycler< std::shared_ptr< HashTable >, HashtableCacheMetaInfo >.

Definition at line 261 of file HashtableRecycler.cpp.

References g_enable_data_recycler, g_use_hashtable_cache, DataRecycler< std::shared_ptr< HashTable >, HashtableCacheMetaInfo >::getCachedItemContainer(), DataRecycler< std::shared_ptr< HashTable >, HashtableCacheMetaInfo >::getCacheLock(), DataRecycler< std::shared_ptr< HashTable >, HashtableCacheMetaInfo >::markCachedItemAsDirtyImpl(), removeCachedHashtableBuiltFromSyntheticTable(), and removeTableKeyInfoFromQueryPlanDagMap().

264  {
265  if (!g_enable_data_recycler || !g_use_hashtable_cache || key_set.empty()) {
266  return;
267  }
268  std::lock_guard<std::mutex> lock(getCacheLock());
269  auto hashtable_cache = getCachedItemContainer(item_type, device_identifier);
270  for (auto key : key_set) {
271  markCachedItemAsDirtyImpl(key, *hashtable_cache);
272  }
273  // after marking all cached hashtable having the given "table_key" as its one of input,
274  // we remove the mapping between the table_key -> hashed_query_plan_dag
275  // since we do not need to care about "already marked" item in the cache
277 
278  // hash tables built from synthetically generated tables have no chance to be cleared
279  // since we assume their table keys as {-1, -1}
280  // this means that typically we do not have a chance to invalidate cached items
281  // by calling invalidation request with table key {-1, -1}
282  // thus, we manually invalidate them here to maintain cache space based on the
283  // assumption that synthetically generated table is not frequently used as typical
284  // tables do
285  removeCachedHashtableBuiltFromSyntheticTable(item_type, device_identifier, lock);
286 }
std::shared_ptr< CachedItemContainer > getCachedItemContainer(CacheItemType item_type, DeviceIdentifier device_identifier) const
Definition: DataRecycler.h:530
void markCachedItemAsDirtyImpl(QueryPlanHash key, CachedItemContainer &m) const
Definition: DataRecycler.h:506
bool g_enable_data_recycler
Definition: Execute.cpp:146
void removeCachedHashtableBuiltFromSyntheticTable(CacheItemType item_type, DeviceIdentifier device_identifier, std::lock_guard< std::mutex > &lock)
void removeTableKeyInfoFromQueryPlanDagMap(size_t table_key)
bool g_use_hashtable_cache
Definition: Execute.cpp:147

+ Here is the call graph for this function:

void HashtableRecycler::putItemToCache ( QueryPlanHash  key,
std::shared_ptr< HashTable item_ptr,
CacheItemType  item_type,
DeviceIdentifier  device_identifier,
size_t  item_size,
size_t  compute_time,
std::optional< HashtableCacheMetaInfo meta_info = std::nullopt 
)
overridevirtual

Implements DataRecycler< std::shared_ptr< HashTable >, HashtableCacheMetaInfo >.

Definition at line 93 of file HashtableRecycler.cpp.

References AVAILABLE_AFTER_CLEANUP, CHECK, CHECK_EQ, checkOverlapsHashtableBucketCompatability(), cleanupCacheForInsertion(), EMPTY_HASHED_PLAN_DAG_KEY, g_enable_data_recycler, g_use_hashtable_cache, DataRecycler< std::shared_ptr< HashTable >, HashtableCacheMetaInfo >::getCachedItemContainer(), DataRecycler< std::shared_ptr< HashTable >, HashtableCacheMetaInfo >::getCacheLock(), DataRecyclerUtil::getDeviceIdentifierString(), DataRecycler< std::shared_ptr< HashTable >, HashtableCacheMetaInfo >::getMetricTracker(), hasItemInCache(), OVERLAPS_HT, removeItemFromCache(), UNAVAILABLE, and VLOG.

99  {
101  key == EMPTY_HASHED_PLAN_DAG_KEY) {
102  return;
103  }
104  std::lock_guard<std::mutex> lock(getCacheLock());
105  auto has_cached_ht = hasItemInCache(key, item_type, device_identifier, lock, meta_info);
106  if (has_cached_ht) {
107  // check to see whether the cached one is in a dirty status
108  auto hashtable_cache = getCachedItemContainer(item_type, device_identifier);
109  auto candidate_it =
110  std::find_if(hashtable_cache->begin(),
111  hashtable_cache->end(),
112  [&key](const auto& cached_item) { return cached_item.key == key; });
113  bool found_candidate = false;
114  if (candidate_it != hashtable_cache->end()) {
115  if (item_type == OVERLAPS_HT) {
116  // we have to check hashtable metainfo for overlaps join hashtable
117  CHECK(candidate_it->meta_info && candidate_it->meta_info->overlaps_meta_info);
118  CHECK(meta_info && meta_info->overlaps_meta_info);
120  *candidate_it->meta_info->overlaps_meta_info,
121  *meta_info->overlaps_meta_info)) {
122  found_candidate = true;
123  }
124  } else {
125  found_candidate = true;
126  }
127  if (found_candidate && candidate_it->isDirty()) {
128  // remove the dirty item from the cache and make a room for the new one
130  key, item_type, device_identifier, lock, candidate_it->meta_info);
131  has_cached_ht = false;
132  }
133  }
134  }
135 
136  if (!has_cached_ht) {
137  // check cache's space availability
138  auto& metric_tracker = getMetricTracker(item_type);
139  auto cache_status = metric_tracker.canAddItem(device_identifier, item_size);
140  if (cache_status == CacheAvailability::UNAVAILABLE) {
141  // hashtable is too large
142  return;
143  } else if (cache_status == CacheAvailability::AVAILABLE_AFTER_CLEANUP) {
144  // we need to cleanup some cached hashtables to make a room to insert this hashtable
145  // here we try to cache the new one anyway since we don't know the importance of
146  // this hashtable yet and if it is not that frequently reused it is removed
147  // in a near future
148  auto required_size = metric_tracker.calculateRequiredSpaceForItemAddition(
149  device_identifier, item_size);
150  cleanupCacheForInsertion(item_type, device_identifier, required_size, lock);
151  }
152  // put hashtable's metric to metric tracker
153  auto new_cache_metric_ptr = metric_tracker.putNewCacheItemMetric(
154  key, device_identifier, item_size, compute_time);
155  CHECK_EQ(item_size, new_cache_metric_ptr->getMemSize());
156  // put hashtable to cache
157  VLOG(1) << "[" << item_type << ", "
158  << DataRecyclerUtil::getDeviceIdentifierString(device_identifier)
159  << "] Put item to cache (key: " << key << ")";
160  auto hashtable_cache = getCachedItemContainer(item_type, device_identifier);
161  hashtable_cache->emplace_back(key, item_ptr, new_cache_metric_ptr, meta_info);
162  }
163  // we have a cached hashtable in a clean status
164  return;
165 }
#define CHECK_EQ(x, y)
Definition: Logger.h:230
bool hasItemInCache(QueryPlanHash key, CacheItemType item_type, DeviceIdentifier device_identifier, std::lock_guard< std::mutex > &lock, std::optional< HashtableCacheMetaInfo > meta_info=std::nullopt) const override
static std::string getDeviceIdentifierString(DeviceIdentifier device_identifier)
Definition: DataRecycler.h:138
CacheMetricTracker & getMetricTracker(CacheItemType item_type)
Definition: DataRecycler.h:656
constexpr QueryPlanHash EMPTY_HASHED_PLAN_DAG_KEY
std::shared_ptr< CachedItemContainer > getCachedItemContainer(CacheItemType item_type, DeviceIdentifier device_identifier) const
Definition: DataRecycler.h:530
bool g_enable_data_recycler
Definition: Execute.cpp:146
void cleanupCacheForInsertion(CacheItemType item_type, DeviceIdentifier device_identifier, size_t required_size, std::lock_guard< std::mutex > &lock, std::optional< HashtableCacheMetaInfo > meta_info=std::nullopt) override
void removeItemFromCache(QueryPlanHash key, CacheItemType item_type, DeviceIdentifier device_identifier, std::lock_guard< std::mutex > &lock, std::optional< HashtableCacheMetaInfo > meta_info=std::nullopt) override
bool checkOverlapsHashtableBucketCompatability(const OverlapsHashTableMetaInfo &candidate_bucket_dim, const OverlapsHashTableMetaInfo &target_bucket_dim) const
#define CHECK(condition)
Definition: Logger.h:222
bool g_use_hashtable_cache
Definition: Execute.cpp:147
#define VLOG(n)
Definition: Logger.h:316

+ Here is the call graph for this function:

void HashtableRecycler::removeCachedHashtableBuiltFromSyntheticTable ( CacheItemType  item_type,
DeviceIdentifier  device_identifier,
std::lock_guard< std::mutex > &  lock 
)
private

Definition at line 288 of file HashtableRecycler.cpp.

References CHECK, DataRecycler< std::shared_ptr< HashTable >, HashtableCacheMetaInfo >::getCachedItemContainer(), DataRecyclerUtil::getUnitaryTableKey(), removeItemFromCache(), removeTableKeyInfoFromQueryPlanDagMap(), and table_key_to_query_plan_dag_map_.

Referenced by markCachedItemAsDirty().

291  {
292  auto hashtable_cache = getCachedItemContainer(item_type, device_identifier);
293  CHECK(hashtable_cache);
294  auto unitary_table_key = DataRecyclerUtil::getUnitaryTableKey();
295  auto key_set_it = table_key_to_query_plan_dag_map_.find(unitary_table_key);
296  if (key_set_it != table_key_to_query_plan_dag_map_.end()) {
297  auto& key_set = key_set_it->second;
298  for (auto key : key_set) {
299  removeItemFromCache(key, item_type, device_identifier, lock);
300  }
301  // after marking all cached hashtable having the given "table_key" as its one of
302  // input, we remove the mapping between the table_key -> hashed_query_plan_dag since
303  // we do not need to care about "already marked" item in the cache
304  removeTableKeyInfoFromQueryPlanDagMap(unitary_table_key);
305  }
306 }
std::shared_ptr< CachedItemContainer > getCachedItemContainer(CacheItemType item_type, DeviceIdentifier device_identifier) const
Definition: DataRecycler.h:530
std::unordered_map< size_t, std::unordered_set< size_t > > table_key_to_query_plan_dag_map_
static QueryPlanHash getUnitaryTableKey()
Definition: DataRecycler.h:145
void removeItemFromCache(QueryPlanHash key, CacheItemType item_type, DeviceIdentifier device_identifier, std::lock_guard< std::mutex > &lock, std::optional< HashtableCacheMetaInfo > meta_info=std::nullopt) override
#define CHECK(condition)
Definition: Logger.h:222
void removeTableKeyInfoFromQueryPlanDagMap(size_t table_key)

+ Here is the call graph for this function:

+ Here is the caller graph for this function:

void HashtableRecycler::removeItemFromCache ( QueryPlanHash  key,
CacheItemType  item_type,
DeviceIdentifier  device_identifier,
std::lock_guard< std::mutex > &  lock,
std::optional< HashtableCacheMetaInfo meta_info = std::nullopt 
)
overrideprivatevirtual

Implements DataRecycler< std::shared_ptr< HashTable >, HashtableCacheMetaInfo >.

Definition at line 167 of file HashtableRecycler.cpp.

References CHECK, EMPTY_HASHED_PLAN_DAG_KEY, g_enable_data_recycler, g_use_hashtable_cache, DataRecycler< std::shared_ptr< HashTable >, HashtableCacheMetaInfo >::getCachedItemContainer(), DataRecyclerUtil::getDeviceIdentifierString(), DataRecycler< std::shared_ptr< HashTable >, HashtableCacheMetaInfo >::getMetricTracker(), REMOVE, and VLOG.

Referenced by putItemToCache(), and removeCachedHashtableBuiltFromSyntheticTable().

172  {
174  key == EMPTY_HASHED_PLAN_DAG_KEY) {
175  return;
176  }
177  auto& cache_metrics = getMetricTracker(item_type);
178  // remove cached item from the cache
179  auto cache_metric = cache_metrics.getCacheItemMetric(key, device_identifier);
180  CHECK(cache_metric);
181  auto hashtable_size = cache_metric->getMemSize();
182  auto hashtable_container = getCachedItemContainer(item_type, device_identifier);
183  auto filter = [key](auto const& item) { return item.key == key; };
184  auto itr =
185  std::find_if(hashtable_container->cbegin(), hashtable_container->cend(), filter);
186  if (itr == hashtable_container->cend()) {
187  return;
188  } else {
189  VLOG(1) << "[" << item_type << ", "
190  << DataRecyclerUtil::getDeviceIdentifierString(device_identifier)
191  << "] remove cached item from cache (key: " << key << ")";
192  hashtable_container->erase(itr);
193  }
194  // remove cache metric
195  cache_metrics.removeCacheItemMetric(key, device_identifier);
196  // update current cache size
197  cache_metrics.updateCurrentCacheSize(
198  device_identifier, CacheUpdateAction::REMOVE, hashtable_size);
199  return;
200 }
static std::string getDeviceIdentifierString(DeviceIdentifier device_identifier)
Definition: DataRecycler.h:138
CacheMetricTracker & getMetricTracker(CacheItemType item_type)
Definition: DataRecycler.h:656
constexpr QueryPlanHash EMPTY_HASHED_PLAN_DAG_KEY
std::shared_ptr< CachedItemContainer > getCachedItemContainer(CacheItemType item_type, DeviceIdentifier device_identifier) const
Definition: DataRecycler.h:530
bool g_enable_data_recycler
Definition: Execute.cpp:146
#define CHECK(condition)
Definition: Logger.h:222
bool g_use_hashtable_cache
Definition: Execute.cpp:147
#define VLOG(n)
Definition: Logger.h:316

+ Here is the call graph for this function:

+ Here is the caller graph for this function:

void HashtableRecycler::removeTableKeyInfoFromQueryPlanDagMap ( size_t  table_key)

Definition at line 525 of file HashtableRecycler.cpp.

References table_key_to_query_plan_dag_map_.

Referenced by markCachedItemAsDirty(), and removeCachedHashtableBuiltFromSyntheticTable().

525  {
526  // this function is called when marking cached item for the given table_key as dirty
527  // and when we do that we already acquire the cache lock so we skip to lock in this func
528  table_key_to_query_plan_dag_map_.erase(table_key);
529 }
std::unordered_map< size_t, std::unordered_set< size_t > > table_key_to_query_plan_dag_map_

+ Here is the caller graph for this function:

std::string HashtableRecycler::toString ( ) const
overridevirtual

Implements DataRecycler< std::shared_ptr< HashTable >, HashtableCacheMetaInfo >.

Definition at line 308 of file HashtableRecycler.cpp.

References DataRecycler< std::shared_ptr< HashTable >, HashtableCacheMetaInfo >::getCacheItemType(), DataRecyclerUtil::getDeviceIdentifierString(), DataRecycler< std::shared_ptr< HashTable >, HashtableCacheMetaInfo >::getItemCache(), and DataRecycler< std::shared_ptr< HashTable >, HashtableCacheMetaInfo >::getMetricTracker().

Referenced by getHashtableAccessPathInfo().

308  {
309  std::ostringstream oss;
310  oss << "A current status of the Hashtable Recycler:\n";
311  for (auto& item_type : getCacheItemType()) {
312  oss << "\t" << item_type;
313  auto& metric_tracker = getMetricTracker(item_type);
314  oss << "\n\t# cached hashtables:\n";
315  auto item_cache = getItemCache().find(item_type)->second;
316  for (auto& cache_container : *item_cache) {
317  oss << "\t\tDevice"
318  << DataRecyclerUtil::getDeviceIdentifierString(cache_container.first)
319  << ", # hashtables: " << cache_container.second->size() << "\n";
320  for (auto& ht : *cache_container.second) {
321  oss << "\t\t\tHT] " << ht.item_metric->toString() << "\n";
322  }
323  }
324  oss << "\t" << metric_tracker.toString() << "\n";
325  }
326  return oss.str();
327 }
static std::string getDeviceIdentifierString(DeviceIdentifier device_identifier)
Definition: DataRecycler.h:138
CacheMetricTracker & getMetricTracker(CacheItemType item_type)
Definition: DataRecycler.h:656
std::unordered_set< CacheItemType > const & getCacheItemType() const
Definition: DataRecycler.h:666

+ Here is the call graph for this function:

+ Here is the caller graph for this function:

Member Data Documentation

HashtableRecycler::g_hashtable_cache_total_bytes

Definition at line 57 of file HashtableRecycler.h.

HashtableRecycler::g_max_cacheable_hashtable_size_bytes

Definition at line 57 of file HashtableRecycler.h.

HashtableRecycler::num_gpus
Initial value:
{}
std::shared_ptr<HashTable> getItemFromCache(
CacheItemType item_type,
DeviceIdentifier device_identifier,
std::optional<HashtableCacheMetaInfo> meta_info = std::nullopt) override

Definition at line 60 of file HashtableRecycler.h.

std::unordered_map<size_t, std::unordered_set<size_t> > HashtableRecycler::table_key_to_query_plan_dag_map_
private

The documentation for this class was generated from the following files: