Chunk-Compaction-in-Vectorized-Execution/hash_table.h at logical_compaction · embryo-labs/Chunk-Compaction-in-Vectorized-Execution · GitHub

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
//===----------------------------------------------------------------------===//
//
//                         Compaction
//
// hash_table
//
//
//===----------------------------------------------------------------------===//

#pragma once

#include <list>
#include <unordered_map>
#include <functional>
#include <utility>

#include "base.h"
#include "profiler.h"

namespace compaction {

class HashTable;

struct Tuple {
  vector<Attribute> attrs_;
};

class ScanStructure {
 public:
  explicit ScanStructure(size_t count,
                         vector<uint32_t> bucket_sel_vector,
                         vector<list<Tuple> *> buckets,
                         vector<uint32_t> &key_sel_vector,
                         HashTable *ht, DataChunk *buffer)
      : count_(count), buckets_(std::move(buckets)),
        bucket_sel_vector_(std::move(bucket_sel_vector)), key_sel_vector_(key_sel_vector), ht_(ht), buffer_(buffer) {
    iterators_.resize(kBlockSize);
    for (size_t i = 0; i < count; ++i) {
      auto idx = bucket_sel_vector_[i];
      iterators_[idx] = buckets_[idx]->begin();
    }
  }

  void Next(Vector &join_key, DataChunk &input, DataChunk &result, bool compact_mode = true);

  inline bool HasNext() const { return HasBucket() || HasBuffer(); }

 private:
  size_t count_;
  vector<list<Tuple> *> buckets_;
  vector<uint32_t> bucket_sel_vector_;
  vector<uint32_t> &key_sel_vector_;
  vector<list<Tuple>::iterator> iterators_;
  HashTable *ht_;

  // buffer
  DataChunk *buffer_;

  size_t ScanInnerJoin(Vector &join_key, vector<uint32_t> &result_vector);

  inline void AdvancePointers();

  inline void GatherResult(vector<Vector *> cols, vector<uint32_t> &result_vector, size_t count);

  inline bool HasBucket() const { return count_ > 0; }

  inline bool HasBuffer() const { return buffer_ != nullptr && buffer_->count_ > 0; }

  void NextInternal(Vector &join_key, DataChunk &input, DataChunk &result);
};

class HashTable {
 public:
  HashTable(size_t n_rhs_tuples,
            size_t chunk_factor,
            size_t payload_length,
            vector<AttributeType> &schema,
            double load_factor = 0.5);

  ScanStructure Probe(Vector &join_key);

 private:
  size_t n_buckets_;
  vector<unique_ptr<list<Tuple>>> linked_lists_;
  std::hash<Attribute> hash_;
  DataChunk buffer_;
};
}