OmniSciDB  a47db9e897
 All Classes Namespaces Files Functions Variables Typedefs Enumerations Enumerator Friends Macros Pages
JoinLoop.h
Go to the documentation of this file.
1 /*
2  * Copyright 2017 MapD Technologies, 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 "Shared/Logger.h"
23 
24 #include "../../Shared/sqldefs.h"
25 #include "../IRCodegenUtils.h"
26 
27 #include <functional>
28 #include <vector>
29 
30 enum class JoinLoopKind {
31  UpperBound, // loop join
32  Set, // one to many hash join
33  Singleton // one to one hash join
34 };
35 
36 // The domain of iteration for a join:
37 // 1. For loop join, from 0 to `upper_bound`.
38 // 2. For one-to-one joins, at most one value: `slot_lookup_result` if valid (greater than
39 // or equal to zero).
40 // 3. For one-to-many joins, the `element_count` values in `values_buffer`.
42  union {
43  llvm::Value* upper_bound; // for UpperBound
44  llvm::Value* element_count; // for Set
45  llvm::Value* slot_lookup_result; // for Singleton
46  };
47  llvm::Value* values_buffer; // used for Set
48 };
49 
50 // Any join is logically a loop. Hash joins just limit the domain of iteration,
51 // which can be as little as one element for one to one hash join, in which case
52 // we'll not generate IR for an actual loop.
53 class JoinLoop {
54  public:
55  JoinLoop(const JoinLoopKind,
56  const JoinType,
57  const std::function<JoinLoopDomain(const std::vector<llvm::Value*>&)>&,
58  const std::function<llvm::Value*(const std::vector<llvm::Value*>&)>&,
59  const std::function<void(llvm::Value*)>&,
60  const std::function<llvm::Value*(const std::vector<llvm::Value*>& prev_iters,
61  llvm::Value*)>&,
62  const std::string& name = "");
63 
64  static llvm::BasicBlock* codegen(
65  const std::vector<JoinLoop>& join_loops,
66  const std::function<llvm::BasicBlock*(const std::vector<llvm::Value*>&)>&
67  body_codegen,
68  llvm::Value* outer_iter,
69  llvm::BasicBlock* exit_bb,
70  llvm::IRBuilder<>& builder);
71 
72  private:
73  static std::pair<llvm::BasicBlock*, llvm::Value*> evaluateOuterJoinCondition(
74  const JoinLoop& join_loop,
75  const JoinLoopDomain& iteration_domain,
76  const std::vector<llvm::Value*>& iterators,
77  llvm::Value* iteration_counter,
78  llvm::Value* have_more_inner_rows,
79  llvm::Value* found_an_outer_match_ptr,
80  llvm::IRBuilder<>& builder);
81 
83  // SQL type of the join.
84  const JoinType type_;
85  // Callback provided from the executor which generates the code for the given join
86  // domain of iteration.
87  const std::function<JoinLoopDomain(const std::vector<llvm::Value*>&)>
89  // Callback provided from the executor which generates true iff the outer condition
90  // evaluates to true.
91  const std::function<llvm::Value*(const std::vector<llvm::Value*>&)>
93  // Callback provided from the executor which receives the IR boolean value which tracks
94  // whether there are matches for the current iteration.
95  const std::function<void(llvm::Value*)> found_outer_matches_;
96  // Callback provided from the executor which returns if the current row (given by
97  // position) is deleted. The second argument is true iff the iteration isn't done yet.
98  // Useful for UpperBound and Set, which need to avoid fetching the deleted column from a
99  // past-the-end position. It's null for Singleton.
100  const std::function<llvm::Value*(const std::vector<llvm::Value*>& prev_iters,
101  llvm::Value*)>
103  const std::string name_;
104 };
JoinType
Definition: sqldefs.h:98
llvm::Value * element_count
Definition: JoinLoop.h:44
llvm::Value * values_buffer
Definition: JoinLoop.h:47
const std::function< llvm::Value *(const std::vector< llvm::Value * > &)> outer_condition_match_
Definition: JoinLoop.h:92
const JoinType type_
Definition: JoinLoop.h:84
const JoinLoopKind kind_
Definition: JoinLoop.h:82
const std::function< JoinLoopDomain(const std::vector< llvm::Value * > &)> iteration_domain_codegen_
Definition: JoinLoop.h:88
const std::function< void(llvm::Value *)> found_outer_matches_
Definition: JoinLoop.h:95
const std::string name_
Definition: JoinLoop.h:103
llvm::Value * slot_lookup_result
Definition: JoinLoop.h:45
llvm::Value * upper_bound
Definition: JoinLoop.h:43
const std::function< llvm::Value *(const std::vector< llvm::Value * > &prev_iters, llvm::Value *)> is_deleted_
Definition: JoinLoop.h:102
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::IRBuilder<> &builder)
Definition: JoinLoop.cpp:207
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, llvm::IRBuilder<> &builder)
Definition: JoinLoop.cpp:45
JoinLoop(const JoinLoopKind, const JoinType, const std::function< JoinLoopDomain(const std::vector< llvm::Value * > &)> &, const std::function< llvm::Value *(const std::vector< llvm::Value * > &)> &, const std::function< void(llvm::Value *)> &, const std::function< llvm::Value *(const std::vector< llvm::Value * > &prev_iters, llvm::Value *)> &, const std::string &name="")
Definition: JoinLoop.cpp:24
JoinLoopKind
Definition: JoinLoop.h:30