OmniSciDB  a987f07e93
 All Classes Namespaces Files Functions Variables Typedefs Enumerations Enumerator Friends Macros Groups Pages
JoinLoop.h
Go to the documentation of this file.
1 /*
2  * Copyright 2022 HEAVY.AI, Inc.
3  *
4  * Licensed under the Apache License, Version 2.0 (the "License");
5  * you may not use this file except in compliance with the License.
6  * You may obtain a copy of the License at
7  *
8  * http://www.apache.org/licenses/LICENSE-2.0
9  *
10  * Unless required by applicable law or agreed to in writing, software
11  * distributed under the License is distributed on an "AS IS" BASIS,
12  * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
13  * See the License for the specific language governing permissions and
14  * limitations under the License.
15  */
16 
17 #pragma once
18 
19 #include <llvm/IR/BasicBlock.h>
20 #include <llvm/IR/IRBuilder.h>
21 #include <llvm/IR/Value.h>
22 #include "Logger/Logger.h"
23 
24 #include "../../Shared/sqldefs.h"
25 #include "../CgenState.h"
26 #include "../IRCodegenUtils.h"
27 
28 #include <functional>
29 #include <vector>
30 
31 enum class JoinLoopKind {
32  UpperBound, // loop join
33  Set, // one to many hash join
34  Singleton, // one to one hash join
35  MultiSet // many to many hash join
36 };
37 
38 // The domain of iteration for a join:
39 // 1. For loop join, from 0 to `upper_bound`.
40 // 2. For one-to-one joins, at most one value: `slot_lookup_result` if valid (greater than
41 // or equal to zero).
42 // 3. For one-to-many joins, the `element_count` values in `values_buffer`.
44  union {
45  llvm::Value* upper_bound; // for UpperBound
46  llvm::Value* element_count; // for Set
47  llvm::Value* slot_lookup_result; // for Singleton
48  };
49  llvm::Value* values_buffer; // used for Set
50 };
51 
52 // Any join is logically a loop. Hash joins just limit the domain of iteration,
53 // which can be as little as one element for one to one hash join, in which case
54 // we'll not generate IR for an actual loop.
55 class JoinLoop {
56  public:
57  using HoistedFiltersCallback = std::function<llvm::BasicBlock*(llvm::BasicBlock*,
58  llvm::BasicBlock*,
59  const std::string&,
60  llvm::Function*,
62 
63  JoinLoop(const JoinLoopKind,
64  const JoinType,
65  const std::function<JoinLoopDomain(const std::vector<llvm::Value*>&)>&
66  iteration_domain_codegen,
67  const std::function<llvm::Value*(const std::vector<llvm::Value*>&)>&
68  outer_condition_match,
69  const std::function<void(llvm::Value*)>& found_outer_matches,
70  const HoistedFiltersCallback& hoisted_filters,
71  const std::function<llvm::Value*(const std::vector<llvm::Value*>& prev_iters,
72  llvm::Value*)>& is_deleted,
73  const bool nested_loop_join = false,
74  const std::string& name = "");
75 
76  static llvm::BasicBlock* codegen(
77  const std::vector<JoinLoop>& join_loops,
78  const std::function<llvm::BasicBlock*(const std::vector<llvm::Value*>&)>&
79  body_codegen,
80  llvm::Value* outer_iter,
81  llvm::BasicBlock* exit_bb,
82  CgenState* cgen_state);
83 
84  JoinLoopKind kind() const { return kind_; }
85 
86  bool isNestedLoopJoin() const { return nested_loop_join_; }
87 
88  private:
89  static std::pair<llvm::BasicBlock*, llvm::Value*> evaluateOuterJoinCondition(
90  const JoinLoop& join_loop,
91  const JoinLoopDomain& iteration_domain,
92  const std::vector<llvm::Value*>& iterators,
93  llvm::Value* iteration_counter,
94  llvm::Value* have_more_inner_rows,
95  llvm::Value* found_an_outer_match_ptr,
96  llvm::Value* current_condition_match_ptr,
97  CgenState* cgen_state);
98 
100  // SQL type of the join.
102  // Callback provided from the executor which generates the code for the given join
103  // domain of iteration.
104  const std::function<JoinLoopDomain(const std::vector<llvm::Value*>&)>
106  // Callback provided from the executor which generates true iff the outer condition
107  // evaluates to true.
108  const std::function<llvm::Value*(const std::vector<llvm::Value*>&)>
110  // Callback provided from the executor which receives the IR boolean value which tracks
111  // whether there are matches for the current iteration.
112  const std::function<void(llvm::Value*)> found_outer_matches_;
113  // Callback to hoist left hand side filters through the join, evaluating the filters
114  // prior to evaluating the join (but within the same kernel)
116  // Callback provided from the executor which returns if the current row (given by
117  // position) is deleted. The second argument is true iff the iteration isn't done yet.
118  // Useful for UpperBound and Set, which need to avoid fetching the deleted column from a
119  // past-the-end position. It's null for Singleton.
120  const std::function<llvm::Value*(const std::vector<llvm::Value*>& prev_iters,
121  llvm::Value*)>
123  // true if the join loop is for nested loop join
124  const bool nested_loop_join_;
125  const std::string name_;
126 };
JoinType
Definition: sqldefs.h:164
llvm::Value * element_count
Definition: JoinLoop.h:46
llvm::Value * values_buffer
Definition: JoinLoop.h:49
std::function< llvm::BasicBlock *(llvm::BasicBlock *, llvm::BasicBlock *, const std::string &, llvm::Function *, CgenState *)> HoistedFiltersCallback
Definition: JoinLoop.h:61
const std::function< llvm::Value *(const std::vector< llvm::Value * > &)> outer_condition_match_
Definition: JoinLoop.h:109
const JoinType type_
Definition: JoinLoop.h:101
const JoinLoopKind kind_
Definition: JoinLoop.h:99
const std::function< JoinLoopDomain(const std::vector< llvm::Value * > &)> iteration_domain_codegen_
Definition: JoinLoop.h:105
const std::function< void(llvm::Value *)> found_outer_matches_
Definition: JoinLoop.h:112
const std::string name_
Definition: JoinLoop.h:125
static llvm::BasicBlock * codegen(const std::vector< JoinLoop > &join_loops, const std::function< llvm::BasicBlock *(const std::vector< llvm::Value * > &)> &body_codegen, llvm::Value *outer_iter, llvm::BasicBlock *exit_bb, CgenState *cgen_state)
Definition: JoinLoop.cpp:50
JoinLoopKind kind() const
Definition: JoinLoop.h:84
llvm::Value * slot_lookup_result
Definition: JoinLoop.h:47
llvm::Value * upper_bound
Definition: JoinLoop.h:45
JoinLoop(const JoinLoopKind, const JoinType, const std::function< JoinLoopDomain(const std::vector< llvm::Value * > &)> &iteration_domain_codegen, const std::function< llvm::Value *(const std::vector< llvm::Value * > &)> &outer_condition_match, const std::function< void(llvm::Value *)> &found_outer_matches, const HoistedFiltersCallback &hoisted_filters, const std::function< llvm::Value *(const std::vector< llvm::Value * > &prev_iters, llvm::Value *)> &is_deleted, const bool nested_loop_join=false, const std::string &name="")
Definition: JoinLoop.cpp:25
const std::function< llvm::Value *(const std::vector< llvm::Value * > &prev_iters, llvm::Value *)> is_deleted_
Definition: JoinLoop.h:122
JoinLoopKind
Definition: JoinLoop.h:31
const bool nested_loop_join_
Definition: JoinLoop.h:124
bool isNestedLoopJoin() const
Definition: JoinLoop.h:86
string name
Definition: setup.in.py:72
const HoistedFiltersCallback hoisted_filters_
Definition: JoinLoop.h:115
static std::pair< llvm::BasicBlock *, llvm::Value * > evaluateOuterJoinCondition(const JoinLoop &join_loop, const JoinLoopDomain &iteration_domain, const std::vector< llvm::Value * > &iterators, llvm::Value *iteration_counter, llvm::Value *have_more_inner_rows, llvm::Value *found_an_outer_match_ptr, llvm::Value *current_condition_match_ptr, CgenState *cgen_state)
Definition: JoinLoop.cpp:297