OmniSciDB  cde582ebc3
 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:458

Member Function Documentation

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

Definition at line 505 of file HashtableRecycler.cpp.

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

507  {
508  std::lock_guard<std::mutex> lock(getCacheLock());
509  for (auto table_key : table_keys) {
510  auto itr = table_key_to_query_plan_dag_map_.try_emplace(table_key).first;
511  itr->second.insert(hashed_query_plan_dag);
512  }
513 }
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 327 of file HashtableRecycler.cpp.

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

Referenced by hasItemInCache(), and putItemToCache().

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

+ 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:654
bool g_is_test_env
Definition: Execute.cpp:141
void sortCacheContainerByQueryMetric(CacheItemType item_type, DeviceIdentifier device_identifier)
Definition: DataRecycler.h:632
void removeCachedItemFromBeginning(CacheItemType item_type, DeviceIdentifier device_identifier, int offset)
Definition: DataRecycler.h:621

+ 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  VLOG(1) << "[" << item_type << ", "
252  << "] clear cache (# items: " << kv.second->size() << ")";
253  kv.second->clear();
254  }
255  }
257 }
static std::string getDeviceIdentifierString(DeviceIdentifier device_identifier)
Definition: DataRecycler.h:138
CacheMetricTracker & getMetricTracker(CacheItemType item_type)
Definition: DataRecycler.h:654
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:664
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 492 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().

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

+ 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 410 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().

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

References EMPTY_HASHED_PLAN_DAG_KEY.

Referenced by getHashtableAccessPathInfo().

348  {
349  auto hashed_join_col_info = EMPTY_HASHED_PLAN_DAG_KEY;
350  boost::hash_combine(
351  hashed_join_col_info,
352  executor->getQueryPlanDagCache().translateColVarsToInfoHash(inner_cols, false));
353  boost::hash_combine(
354  hashed_join_col_info,
355  executor->getQueryPlanDagCache().translateColVarsToInfoHash(outer_cols, false));
356  return hashed_join_col_info;
357 }
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 516 of file HashtableRecycler.cpp.

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

516  {
517  std::lock_guard<std::mutex> lock(getCacheLock());
518  auto it = table_key_to_query_plan_dag_map_.find(table_key);
519  return it != table_key_to_query_plan_dag_map_.end() ? std::make_optional(it->second)
520  : std::nullopt;
521 }
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:528
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 402 of file HashtableRecycler.cpp.

References EMPTY_HASHED_PLAN_DAG_KEY.

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

403  {
404  return cache_keys.empty() ||
405  std::any_of(cache_keys.cbegin(), cache_keys.cend(), [](QueryPlanHash key) {
406  return key == EMPTY_HASHED_PLAN_DAG_KEY;
407  });
408 }
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 359 of file HashtableRecycler.cpp.

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

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

+ 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 259 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().

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

289  {
290  auto hashtable_cache = getCachedItemContainer(item_type, device_identifier);
291  CHECK(hashtable_cache);
292  auto unitary_table_key = DataRecyclerUtil::getUnitaryTableKey();
293  auto key_set_it = table_key_to_query_plan_dag_map_.find(unitary_table_key);
294  if (key_set_it != table_key_to_query_plan_dag_map_.end()) {
295  auto& key_set = key_set_it->second;
296  for (auto key : key_set) {
297  removeItemFromCache(key, item_type, device_identifier, lock);
298  }
299  // after marking all cached hashtable having the given "table_key" as its one of
300  // input, we remove the mapping between the table_key -> hashed_query_plan_dag since
301  // we do not need to care about "already marked" item in the cache
302  removeTableKeyInfoFromQueryPlanDagMap(unitary_table_key);
303  }
304 }
std::shared_ptr< CachedItemContainer > getCachedItemContainer(CacheItemType item_type, DeviceIdentifier device_identifier) const
Definition: DataRecycler.h:528
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:654
constexpr QueryPlanHash EMPTY_HASHED_PLAN_DAG_KEY
std::shared_ptr< CachedItemContainer > getCachedItemContainer(CacheItemType item_type, DeviceIdentifier device_identifier) const
Definition: DataRecycler.h:528
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 523 of file HashtableRecycler.cpp.

References table_key_to_query_plan_dag_map_.

Referenced by markCachedItemAsDirty(), and removeCachedHashtableBuiltFromSyntheticTable().

523  {
524  // this function is called when marking cached item for the given table_key as dirty
525  // and when we do that we already acquire the cache lock so we skip to lock in this func
526  table_key_to_query_plan_dag_map_.erase(table_key);
527 }
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 306 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().

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

+ 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: