OmniSciDB  1dac507f6e
 All Classes Namespaces Files Functions Variables Typedefs Enumerations Enumerator Friends Macros Pages
StreamingTopN.h File Reference

Streaming Top N algorithm. More...

#include <cstddef>
#include <cstdint>
#include <vector>
+ Include dependency graph for StreamingTopN.h:
+ This graph shows which files directly or indirectly include this file:

Go to the source code of this file.

Namespaces

 streaming_top_n
 
 Analyzer
 

Functions

size_t streaming_top_n::get_heap_size (const size_t row_size, const size_t n, const size_t thread_count)
 
size_t streaming_top_n::get_rows_offset_of_heaps (const size_t n, const size_t thread_count)
 
std::vector< int8_t > streaming_top_n::get_rows_copy_from_heaps (const int64_t *heaps, const size_t heaps_size, const size_t n, const size_t thread_count)
 
bool use_streaming_top_n (const RelAlgExecutionUnit &ra_exe_unit, const bool output_columnar)
 
size_t get_heap_key_slot_index (const std::vector< Analyzer::Expr * > &target_exprs, const size_t target_idx)
 

Detailed Description

Streaming Top N algorithm.

Author
Minggang Yu miyu@.nosp@m.mapd.nosp@m..com Copyright (c) 2017 MapD Technologies, Inc. All rights reserved.

Definition in file StreamingTopN.h.

Function Documentation

size_t get_heap_key_slot_index ( const std::vector< Analyzer::Expr * > &  target_exprs,
const size_t  target_idx 
)

Definition at line 81 of file StreamingTopN.cpp.

References advance_slot(), g_bigint_count, and get_target_info().

Referenced by GroupByAndAggregate::codegenOutputSlot().

82  {
83  size_t slot_idx = 0;
84  for (size_t i = 0; i < target_idx; ++i) {
85  auto agg_info = get_target_info(target_exprs[i], g_bigint_count);
86  slot_idx = advance_slot(slot_idx, agg_info, false);
87  }
88  return slot_idx;
89 }
TargetInfo get_target_info(const PointerType target_expr, const bool bigint_count)
Definition: TargetInfo.h:65
size_t advance_slot(const size_t j, const TargetInfo &target_info, const bool separate_varlen_storage)
bool g_bigint_count

+ Here is the call graph for this function:

+ Here is the caller graph for this function:

bool use_streaming_top_n ( const RelAlgExecutionUnit ra_exe_unit,
const bool  output_columnar 
)

Definition at line 46 of file StreamingTopN.cpp.

References SortInfo::algorithm, CHECK_GT, CHECK_LE, g_cluster, SortInfo::limit, SortInfo::offset, SortInfo::order_entries, RelAlgExecutionUnit::sort_info, StreamingTopN, and RelAlgExecutionUnit::target_exprs.

Referenced by GroupByAndAggregate::codegen(), GroupByAndAggregate::codegenOutputSlot(), QueryMemoryInitializer::copyGroupByBuffersFromGpu(), QueryMemoryDescriptor::getBufferSizeBytes(), QueryExecutionContext::launchCpuCode(), QueryExecutionContext::launchGpuCode(), and QueryMemoryInitializer::QueryMemoryInitializer().

47  {
48  if (g_cluster) {
49  return false; // TODO(miyu)
50  }
51 
52  for (const auto target_expr : ra_exe_unit.target_exprs) {
53  if (dynamic_cast<const Analyzer::AggExpr*>(target_expr)) {
54  return false;
55  }
56  if (dynamic_cast<const Analyzer::WindowFunction*>(target_expr)) {
57  return false;
58  }
59  }
60 
61  // TODO: Allow streaming top n for columnar output
62  if (!output_columnar && ra_exe_unit.sort_info.order_entries.size() == 1 &&
63  ra_exe_unit.sort_info.limit &&
65  const auto only_order_entry = ra_exe_unit.sort_info.order_entries.front();
66  CHECK_GT(only_order_entry.tle_no, int(0));
67  CHECK_LE(static_cast<size_t>(only_order_entry.tle_no),
68  ra_exe_unit.target_exprs.size());
69  const auto order_entry_expr = ra_exe_unit.target_exprs[only_order_entry.tle_no - 1];
70  const auto n = ra_exe_unit.sort_info.offset + ra_exe_unit.sort_info.limit;
71  if ((order_entry_expr->get_type_info().is_number() ||
72  order_entry_expr->get_type_info().is_time()) &&
73  n <= 100000) { // TODO(miyu): relax?
74  return true;
75  }
76  }
77 
78  return false;
79 }
std::vector< Analyzer::Expr * > target_exprs
bool g_cluster
const std::list< Analyzer::OrderEntry > order_entries
const SortAlgorithm algorithm
#define CHECK_GT(x, y)
Definition: Logger.h:202
const size_t limit
const SortInfo sort_info
#define CHECK_LE(x, y)
Definition: Logger.h:201
const size_t offset

+ Here is the caller graph for this function: