The hash table does not support removes. The hash table is not thread safe. More...

#include <old-hash-table.h>

Collaboration diagram for impala::OldHashTable:

Classes
struct	Bucket

class	Iterator
	stl-like iterator interface. More...

struct	Node

Public Member Functions
	OldHashTable (RuntimeState state, const std::vector< ExprContext > &build_expr_ctxs, const std::vector< ExprContext * > &probe_expr_ctxs, int num_build_tuples, bool stores_nulls, bool finds_nulls, int32_t initial_seed, MemTracker *mem_tracker, bool stores_tuples=false, int64_t num_buckets=1024)

void	Close ()
	Call to cleanup any resources. Must be called once. More...

bool IR_ALWAYS_INLINE	Insert (TupleRow *row)

bool IR_ALWAYS_INLINE	Insert (Tuple *tuple)

bool IR_ALWAYS_INLINE	EvalAndHashBuild (TupleRow row, uint32_t hash)

bool IR_ALWAYS_INLINE	EvalAndHashProbe (TupleRow row, uint32_t hash)

Iterator IR_ALWAYS_INLINE	Find (TupleRow *probe_row)

int64_t	size () const
	Returns number of elements in the hash table. More...

int64_t	num_buckets () const
	Returns the number of buckets. More...

float	load_factor () const
	Returns the load factor (the number of non-empty buckets) More...

int64_t	byte_size () const
	Returns the number of bytes allocated to the hash table. More...

bool	mem_limit_exceeded () const

void *	last_expr_value (int expr_idx) const

bool	last_expr_value_null (int expr_idx) const
	Returns if the expr at 'expr_idx' evaluated to NULL for the last row. More...

void	AddBitmapFilters ()

Iterator	Begin ()

Iterator	FirstUnmatched ()

Iterator	End ()
	Returns end marker. More...

llvm::Function *	CodegenEvalTupleRow (RuntimeState *state, bool build_row)

llvm::Function *	CodegenHashCurrentRow (RuntimeState *state)

llvm::Function *	CodegenEquals (RuntimeState *state)

std::string	DebugString (bool skip_empty, bool show_match, const RowDescriptor *build_desc)

Static Public Member Functions
static int64_t	EstimateSize (int64_t num_rows)

Static Public Attributes
static const char *	LLVM_CLASS_NAME = "class.impala::OldHashTable"

Private Member Functions
Bucket *	NextBucket (int64_t *bucket_idx)

void	ResizeBuckets (int64_t num_buckets)
	Resize the hash table to 'num_buckets'. More...

bool IR_ALWAYS_INLINE	InsertImpl (void *data)
	Insert row into the hash table. More...

void	AddToBucket (Bucket bucket, Node node)

void	MoveNode (Bucket from_bucket, Bucket to_bucket, Node node, Node previous_node)

bool	EvalRow (TupleRow row, const std::vector< ExprContext > &ctxs)

bool IR_NO_INLINE	EvalBuildRow (TupleRow *row)

bool IR_NO_INLINE	EvalProbeRow (TupleRow *row)

uint32_t IR_NO_INLINE	HashCurrentRow ()

TupleRow *	GetRow (Node *node) const

uint32_t	HashVariableLenRow ()

bool	Equals (TupleRow *build_row)

void	GrowNodeArray ()
	Grow the node array. More...

void	MemLimitExceeded (int64_t allocation_size)

Private Attributes
RuntimeState *	state_

const std::vector< ExprContext * > &	build_expr_ctxs_

const std::vector< ExprContext * > &	probe_expr_ctxs_

const int	num_build_tuples_
	Number of Tuple* in the build tuple row. More...

const bool	stores_nulls_

const bool	finds_nulls_

const bool	stores_tuples_

const int32_t	initial_seed_

int64_t	num_filled_buckets_
	Number of non-empty buckets. Used to determine when to grow and rehash. More...

int64_t	num_nodes_
	number of nodes stored (i.e. size of hash table) More...

boost::scoped_ptr< MemPool >	mem_pool_
	MemPool used to allocate data pages. More...

int	num_data_pages_
	Number of data pages for nodes. More...

Node *	next_node_
	Next node to insert. More...

int	node_remaining_current_page_
	Number of nodes left in the current page. More...

MemTracker *	mem_tracker_

bool	mem_limit_exceeded_

std::vector< Bucket >	buckets_

int64_t	num_buckets_
	equal to buckets_.size() but more efficient than the size function More...

int64_t	num_buckets_till_resize_
	The number of filled buckets to trigger a resize. This is cached for efficiency. More...

std::vector< int >	expr_values_buffer_offsets_

int	var_result_begin_
	byte offset into expr_values_buffer_ that begins the variable length results More...

int	results_buffer_size_
	byte size of 'expr_values_buffer_' More...

uint8_t *	expr_values_buffer_

uint8_t *	expr_value_null_bits_

Static Private Attributes
static const float	MAX_BUCKET_OCCUPANCY_FRACTION = 0.75f

Friends
class	Iterator

class	OldHashTableTest

Detailed Description

The hash table does not support removes. The hash table is not thread safe.

TODO: Temporarily moving the old HashTable implementation to make it work with the non-partitioned versions of HJ and AGG. It should be removed once we remove those non-partitioned versions. Hash table implementation designed for hash aggregation and hash joins. This is not templatized and is tailored to the usage pattern for aggregation and joins. The hash table store TupleRows and allows for different exprs for insertions and finds. This is the pattern we use for joins and aggregation where the input/build tuple row descriptor is different from the find/probe descriptor. The table is optimized for the query engine's use case as much as possible and is not intended to be a generic hash table implementation. The API loosely mimics the std::hashset API. The hash table stores evaluated expr results for the current row being processed when possible into a contiguous memory buffer. This allows for very efficient computation for hashing. The implementation is also designed to allow codegen for some paths.The implementation is based on the boost multiset. The hashtable is implemented by two data structures: a vector of buckets and a vector of nodes. Inserted values are stored as nodes (in the order they are inserted). The buckets (indexed by the mod of the hash) contain pointers to the node vector. Nodes that fall in the same bucket are linked together (the bucket pointer gets you the head of that linked list). When growing the hash table, the number of buckets is doubled, and nodes from a particular bucket either stay in place or move to an analogous bucket in the second half of buckets. This behavior allows us to avoid moving about half the nodes each time, and maintains good cache properties by only accessing 2 buckets at a time. The node vector is modified in place. Due to the doubling nature of the buckets, we require that the number of buckets is a power of 2. This allows us to determine if a node needs to move by simply checking a single bit, and further allows us to initially hash nodes using a bitmask. TODO: this is not a fancy hash table in terms of memory access patterns (cuckoo-hashing or something that spills to disk). We will likely want to invest more time into this. TODO: hash-join and aggregation have very different access patterns. Joins insert all the rows and then calls scan to find them. Aggregation interleaves Find() and Inserts(). We can want to optimize joins more heavily for Inserts() (in particular growing). TODO: batched interface for inserts and finds.

Definition at line 84 of file old-hash-table.h.

Constructor & Destructor Documentation

OldHashTable::OldHashTable	(	RuntimeState *	state,
		const std::vector< ExprContext * > &	build_expr_ctxs,
		const std::vector< ExprContext * > &	probe_expr_ctxs,
		int	num_build_tuples,
		bool	stores_nulls,
		bool	finds_nulls,
		int32_t	initial_seed,
		MemTracker *	mem_tracker,
		bool	stores_tuples = `false`,
		int64_t	num_buckets = `1024`
	)

Create a hash table.

build_exprs are the exprs that should be used to evaluate rows during Insert().
probe_exprs are used during Find()
num_build_tuples: number of Tuples in the build tuple row
stores_nulls: if false, TupleRows with nulls are ignored during Insert
finds_nulls: if false, Find() returns End() for TupleRows with nulls even if stores_nulls is true
num_buckets: number of buckets that the hash table should be initialized to
mem_tracker: if non-empty, all memory allocations for nodes and for buckets are tracked; the tracker must be valid until the d'tor is called
initial_seed: Initial seed value to use when computing hashes for rows
stores_tuples: If true, the hash table stores tuples, otherwise it stores tuple rows.

Definition at line 54 of file old-hash-table.cc.

References buckets_, build_expr_ctxs_, impala::Expr::ComputeResultsLayout(), impala::MemTracker::Consume(), expr_value_null_bits_, expr_values_buffer_, expr_values_buffer_offsets_, GrowNodeArray(), MAX_BUCKET_OCCUPANCY_FRACTION, mem_tracker_, num_buckets(), num_buckets_, num_buckets_till_resize_, probe_expr_ctxs_, results_buffer_size_, and var_result_begin_.

Member Function Documentation

void OldHashTable::AddBitmapFilters ( )

Can be called after all insert calls to add bitmap filters for the probe side values. For each probe_expr_ that is a slot ref, generate a bitmap filter on that slot. These filters are added to the runtime state. The bitmap filter is similar to a Bloom filter in that has no false negatives but will have false positives.

Definition at line 128 of file old-hash-table.cc.

References impala::RuntimeState::AddBitmapFilter(), Begin(), build_expr_ctxs_, End(), impala::RawValue::GetHashValue(), impala::OldHashTable::Iterator::GetRow(), initial_seed_, impala::OldHashTable::Iterator::Next(), probe_expr_ctxs_, impala::RuntimeState::slot_filter_bitmap_size(), and state_.

void impala::OldHashTable::AddToBucket	(	Bucket *	bucket,
		Node *	node
	)

inlineprivate

Chains the node at 'node_idx' to 'bucket'. Nodes in a bucket are chained as a linked list; this places the new node at the beginning of the list.

Definition at line 90 of file old-hash-table.inline.h.

References impala::OldHashTable::Node::next, impala::OldHashTable::Bucket::node, and num_filled_buckets_.

Referenced by InsertImpl(), and MoveNode().

OldHashTable::Iterator impala::OldHashTable::Begin ( )

inline

Returns an iterator at the beginning of the hash table. Advancing this iterator will traverse all elements.

Definition at line 38 of file old-hash-table.inline.h.

References End(), Iterator, NextBucket(), and impala::OldHashTable::Bucket::node.

Referenced by AddBitmapFilters(), and impala::OldHashTableTest::FullScan().

int64_t impala::OldHashTable::byte_size ( ) const

inline

Returns the number of bytes allocated to the hash table.

Definition at line 185 of file old-hash-table.h.

References buckets_, node_remaining_current_page_, and num_nodes_.

void OldHashTable::Close ( )

Call to cleanup any resources. Must be called once.

Definition at line 93 of file old-hash-table.cc.

References buckets_, expr_value_null_bits_, expr_values_buffer_, impala::ImpaladMetrics::HASH_TABLE_TOTAL_BYTES, mem_pool_, mem_tracker_, num_data_pages_, PAGE_SIZE, and impala::MemTracker::Release().

Referenced by impala::TEST_F().

Function * OldHashTable::CodegenEquals ( RuntimeState * state )

Codegen for evaluating a TupleRow and comparing equality against 'expr_values_buffer_'. Function signature matches OldHashTable::Equals()

Definition at line 576 of file old-hash-table.cc.

Function * OldHashTable::CodegenEvalTupleRow	(	RuntimeState *	state,
		bool	build_row
	)

Codegen for evaluating a tuple row. Codegen'd function matches the signature for EvalBuildRow and EvalTupleRow. if build_row is true, the codegen uses the build_exprs, otherwise the probe_exprs

Definition at line 242 of file old-hash-table.cc.

References impala::LlvmCodeGen::FnPrototype::AddArgument(), build_expr_ctxs_, impala::LlvmCodeGen::CastPtrToLlvmPtr(), CodegenAssignNullValue(), impala::LlvmCodeGen::context(), impala::CodegenAnyVal::CreateCallWrapped(), expr_value_null_bits_, expr_values_buffer_, expr_values_buffer_offsets_, impala::LlvmCodeGen::false_value(), impala::LlvmCodeGen::FinalizeFunction(), impala::RuntimeState::GetCodegen(), impala::Status::GetDetail(), impala::CodegenAnyVal::GetIsNull(), impala::LlvmCodeGen::GetPtrType(), impala::LlvmCodeGen::GetType(), impala::TupleRow::LLVM_CLASS_NAME, impala::ExprContext::LLVM_CLASS_NAME, LLVM_CLASS_NAME, impala::RuntimeState::LogError(), impala::Status::ok(), probe_expr_ctxs_, impala::LlvmCodeGen::ptr_type(), stores_nulls_, impala::CodegenAnyVal::ToNativePtr(), impala::LlvmCodeGen::true_value(), impala::TYPE_BOOLEAN, impala::TYPE_CHAR, impala::TYPE_DECIMAL, impala::TYPE_TIMESTAMP, and impala::TYPE_TINYINT.

Function * OldHashTable::CodegenHashCurrentRow ( RuntimeState * state )

Codegen for hashing the expr values in 'expr_values_buffer_'. Function prototype matches HashCurrentRow identically.

Definition at line 397 of file old-hash-table.cc.

string OldHashTable::DebugString	(	bool	skip_empty,
		bool	show_match,
		const RowDescriptor *	build_desc
	)

Dump out the entire hash table to string. If skip_empty, empty buckets are skipped. If show_match, it also prints the matched flag of each node. If build_desc is non-null, the build rows will be output. Otherwise just the build row addresses.

Definition at line 747 of file old-hash-table.cc.

References buckets_, impala::OldHashTable::Node::data, GetRow(), impala::OldHashTable::Node::matched, impala::OldHashTable::Node::next, and impala::PrintRow().

Iterator impala::OldHashTable::End ( )

inline

Returns end marker.

Definition at line 223 of file old-hash-table.h.

References Iterator.

Referenced by AddBitmapFilters(), Begin(), Find(), FirstUnmatched(), impala::OldHashTableTest::FullScan(), impala::OldHashTable::Iterator::Next(), impala::OldHashTableTest::ProbeTest(), and impala::TEST_F().

bool OldHashTable::Equals ( TupleRow * build_row )

private

Returns true if the values of build_exprs evaluated over 'build_row' equal the values cached in expr_values_buffer_ This will be replaced by codegen.

Definition at line 507 of file old-hash-table.cc.

References build_expr_ctxs_, impala::RawValue::Eq(), expr_value_null_bits_, expr_values_buffer_, expr_values_buffer_offsets_, and stores_nulls_.

Referenced by Find(), and impala::OldHashTable::Iterator::Next().

static int64_t impala::OldHashTable::EstimateSize ( int64_t num_rows )

inlinestatic

Returns an estimate of the number of bytes needed to build the hash table structure for 'num_rows'.

Assume 50% fill factor.

Definition at line 178 of file old-hash-table.h.

References num_buckets().

bool impala::OldHashTable::EvalAndHashBuild	(	TupleRow *	row,
		uint32_t *	hash
	)

inline

Evaluate and hash the build/probe row, returning in *hash. Returns false if this row should be rejected (doesn't need to be processed further) because it contains NULL. These need to be inlined in the IR module so we can find and replace the calls to EvalBuildRow()/EvalProbeRow().

Definition at line 96 of file old-hash-table.inline.h.

References EvalBuildRow(), HashCurrentRow(), and stores_nulls_.

bool impala::OldHashTable::EvalAndHashProbe	(	TupleRow *	row,
		uint32_t *	hash
	)

inline

Definition at line 103 of file old-hash-table.inline.h.

References EvalProbeRow(), finds_nulls_, HashCurrentRow(), and stores_nulls_.

Referenced by Find().

bool IR_NO_INLINE impala::OldHashTable::EvalBuildRow ( TupleRow * row )

inlineprivate

Evaluate 'row' over build exprs caching the results in 'expr_values_buffer_' This will be replaced by codegen. We do not want this function inlined when cross compiled because we need to be able to differentiate between EvalBuildRow and EvalProbeRow by name and the build/probe exprs are baked into the codegen'd function.

Definition at line 374 of file old-hash-table.h.

References build_expr_ctxs_, and EvalRow().

Referenced by EvalAndHashBuild(), and Insert().

bool IR_NO_INLINE impala::OldHashTable::EvalProbeRow ( TupleRow * row )

inlineprivate

Evaluate 'row' over probe exprs caching the results in 'expr_values_buffer_' This will be replaced by codegen.

Definition at line 380 of file old-hash-table.h.

References EvalRow(), and probe_expr_ctxs_.

Referenced by EvalAndHashProbe().

bool OldHashTable::EvalRow	(	TupleRow *	row,
		const std::vector< ExprContext * > &	ctxs
	)

private

Evaluate the exprs over row and cache the results in 'expr_values_buffer_'. Returns whether any expr evaluated to NULL This will be replaced by codegen

Definition at line 107 of file old-hash-table.cc.

References build_expr_ctxs_, expr_value_null_bits_, expr_values_buffer_, expr_values_buffer_offsets_, NULL_VALUE, stores_nulls_, and impala::RawValue::Write().

Referenced by EvalBuildRow(), and EvalProbeRow().

OldHashTable::Iterator impala::OldHashTable::Find ( TupleRow * probe_row )

inline

Returns the start iterator for all rows that match 'probe_row'. 'probe_row' is evaluated with probe exprs. The iterator can be iterated until OldHashTable::End() to find all the matching rows. Only one scan can be in progress at any time (i.e. it is not legal to call Find(), begin iterating through all the matches, call another Find(), and continuing iterator from the first scan iterator). Advancing the returned iterator will go to the next matching row. The matching rows are evaluated lazily (i.e. computed as the Iterator is moved). Returns OldHashTable::End() if there is no match.

Definition at line 23 of file old-hash-table.inline.h.

References buckets_, End(), Equals(), EvalAndHashProbe(), GetRow(), impala::hash, impala::OldHashTable::Node::hash, Iterator, impala::OldHashTable::Node::next, and num_buckets_.

Referenced by impala::OldHashTableTest::ProbeTest(), and impala::TEST_F().

OldHashTable::Iterator impala::OldHashTable::FirstUnmatched ( )

inline

Return an iterator pointing to the first element in the hash table that does not have its matched flag set. Used in right-outer and full-outer joins.

Definition at line 45 of file old-hash-table.inline.h.

References End(), Iterator, impala::OldHashTable::Node::matched, impala::OldHashTable::Node::next, NextBucket(), and impala::OldHashTable::Bucket::node.

TupleRow* impala::OldHashTable::GetRow ( Node * node ) const

inlineprivate

Definition at line 397 of file old-hash-table.h.

References impala::OldHashTable::Node::data, and stores_tuples_.

Referenced by DebugString(), Find(), and impala::OldHashTable::Iterator::Next().

void OldHashTable::GrowNodeArray ( )

private

Grow the node array.

Definition at line 732 of file old-hash-table.cc.

References impala::ImpaladMetrics::HASH_TABLE_TOTAL_BYTES, impala::MemTracker::LimitExceeded(), mem_pool_, mem_tracker_, MemLimitExceeded(), next_node_, node_remaining_current_page_, num_data_pages_, and PAGE_SIZE.

Referenced by InsertImpl(), and OldHashTable().

uint32_t IR_NO_INLINE impala::OldHashTable::HashCurrentRow ( )

inlineprivate

Compute the hash of the values in expr_values_buffer_. This will be replaced by codegen. We don't want this inlined for replacing with codegen'd functions so the function name does not change.

This handles NULLs implicitly since a constant seed value was put into results buffer for nulls.

Definition at line 387 of file old-hash-table.h.

References expr_values_buffer_, impala::HashUtil::Hash(), HashVariableLenRow(), initial_seed_, results_buffer_size_, and var_result_begin_.

Referenced by EvalAndHashBuild(), EvalAndHashProbe(), and InsertImpl().

uint32_t OldHashTable::HashVariableLenRow ( )

private

Compute the hash of the values in expr_values_buffer_ for rows with variable length fields (e.g. strings)

Definition at line 344 of file old-hash-table.cc.

References build_expr_ctxs_, expr_value_null_bits_, expr_values_buffer_, expr_values_buffer_offsets_, impala::hash, impala::HashUtil::Hash(), initial_seed_, impala::StringValue::len, impala::StringValue::ptr, impala::TYPE_STRING, impala::TYPE_VARCHAR, and var_result_begin_.

Referenced by HashCurrentRow().

bool IR_ALWAYS_INLINE impala::OldHashTable::Insert ( TupleRow * row )

inline

Insert row into the hash table. Row will be evaluated over build exprs. This will grow the hash table if necessary. If the hash table has or needs to go over the mem limit, the Insert will be ignored. The caller is assumed to periodically (e.g. per row batch) check the limits to identify this case. The 'row' is not copied by the hash table and the caller must guarantee it stays in memory. Returns false if there was not enough memory to insert the row.

TODO: next prime instead of double?

Definition at line 120 of file old-hash-table.h.

References EvalBuildRow(), InsertImpl(), mem_limit_exceeded_, num_buckets_, num_buckets_till_resize_, num_filled_buckets_, ResizeBuckets(), stores_nulls_, and UNLIKELY.

Referenced by impala::TEST_F().

bool IR_ALWAYS_INLINE impala::OldHashTable::Insert ( Tuple * tuple )

inline

TODO: next prime instead of double?

Definition at line 133 of file old-hash-table.h.

References EvalBuildRow(), InsertImpl(), mem_limit_exceeded_, num_buckets_, num_buckets_till_resize_, num_filled_buckets_, ResizeBuckets(), stores_nulls_, and UNLIKELY.

bool impala::OldHashTable::InsertImpl ( void * data )

inlineprivate

Insert row into the hash table.

Definition at line 72 of file old-hash-table.inline.h.

References AddToBucket(), buckets_, impala::OldHashTable::Node::data, GrowNodeArray(), impala::hash, impala::OldHashTable::Node::hash, HashCurrentRow(), impala::OldHashTable::Node::matched, mem_limit_exceeded_, next_node_, node_remaining_current_page_, num_buckets_, num_nodes_, and UNLIKELY.

Referenced by Insert().

void* impala::OldHashTable::last_expr_value ( int expr_idx ) const

inline

Returns the results of the exprs at 'expr_idx' evaluated over the last row processed by the OldHashTable. This value is invalid if the expr evaluated to NULL. TODO: this is an awkward abstraction but aggregation node can take advantage of it and save some expr evaluation calls.

Definition at line 197 of file old-hash-table.h.

References expr_values_buffer_, and expr_values_buffer_offsets_.

bool impala::OldHashTable::last_expr_value_null ( int expr_idx ) const

inline

Returns if the expr at 'expr_idx' evaluated to NULL for the last row.

Definition at line 202 of file old-hash-table.h.

References expr_value_null_bits_.

float impala::OldHashTable::load_factor ( ) const

inline

Returns the load factor (the number of non-empty buckets)

Definition at line 172 of file old-hash-table.h.

References buckets_, and num_filled_buckets_.

bool impala::OldHashTable::mem_limit_exceeded ( ) const

inline

Definition at line 190 of file old-hash-table.h.

References mem_limit_exceeded_.

Referenced by impala::TEST_F().

void OldHashTable::MemLimitExceeded ( int64_t allocation_size )

private

Sets mem_limit_exceeded_ to true and MEM_LIMIT_EXCEEDED for the query. allocation_size is the attempted size of the allocation that would have brought us over the mem limit.

Definition at line 742 of file old-hash-table.cc.

References mem_limit_exceeded_, mem_tracker_, impala::RuntimeState::SetMemLimitExceeded(), and state_.

Referenced by GrowNodeArray(), and ResizeBuckets().

void impala::OldHashTable::MoveNode	(	Bucket *	from_bucket,
		Bucket *	to_bucket,
		Node *	node,
		Node *	previous_node
	)

inlineprivate

Moves a node from one bucket to another. 'previous_node' refers to the node (if any) that's chained before this node in from_bucket's linked list.

Definition at line 110 of file old-hash-table.inline.h.

References AddToBucket(), impala::OldHashTable::Node::next, impala::OldHashTable::Bucket::node, and num_filled_buckets_.

Referenced by ResizeBuckets().

OldHashTable::Bucket * impala::OldHashTable::NextBucket ( int64_t * bucket_idx )

inlineprivate

Returns the next non-empty bucket and updates idx to be the index of that bucket. If there are no more buckets, returns NULL and sets idx to -1

Definition at line 63 of file old-hash-table.inline.h.

References buckets_, and num_buckets_.

Referenced by Begin(), FirstUnmatched(), and impala::OldHashTable::Iterator::Next().

int64_t impala::OldHashTable::num_buckets ( ) const

inline

Returns the number of buckets.

Definition at line 169 of file old-hash-table.h.

References buckets_.

Referenced by EstimateSize(), OldHashTable(), ResizeBuckets(), and impala::TEST_F().

void OldHashTable::ResizeBuckets ( int64_t num_buckets )

private

Resize the hash table to 'num_buckets'.

Definition at line 678 of file old-hash-table.cc.

References buckets_, impala::hash, impala::OldHashTable::Node::hash, MAX_BUCKET_OCCUPANCY_FRACTION, mem_tracker_, MemLimitExceeded(), MoveNode(), impala::OldHashTable::Node::next, impala::OldHashTable::Bucket::node, num_buckets(), num_buckets_, num_buckets_till_resize_, and impala::MemTracker::TryConsume().

Referenced by Insert(), and impala::OldHashTableTest::ResizeTable().

int64_t impala::OldHashTable::size ( ) const

inline

Returns number of elements in the hash table.

Definition at line 166 of file old-hash-table.h.

References num_nodes_.

Referenced by impala::TEST_F().

Friends And Related Function Documentation

friend class Iterator

friend

Definition at line 323 of file old-hash-table.h.

Referenced by Begin(), End(), Find(), and FirstUnmatched().

friend class OldHashTableTest

friend

Definition at line 324 of file old-hash-table.h.

Member Data Documentation

std::vector<Bucket> impala::OldHashTable::buckets_

private

Definition at line 467 of file old-hash-table.h.

Referenced by byte_size(), Close(), DebugString(), Find(), InsertImpl(), load_factor(), NextBucket(), num_buckets(), OldHashTable(), and ResizeBuckets().

const std::vector<ExprContext*>& impala::OldHashTable::build_expr_ctxs_

private

Definition at line 428 of file old-hash-table.h.

Referenced by AddBitmapFilters(), CodegenEquals(), CodegenEvalTupleRow(), CodegenHashCurrentRow(), Equals(), EvalBuildRow(), EvalRow(), HashVariableLenRow(), and OldHashTable().

uint8_t* impala::OldHashTable::expr_value_null_bits_

private

Use bytes instead of bools to be compatible with llvm. This address must not change once allocated.

Definition at line 491 of file old-hash-table.h.

Referenced by Close(), CodegenEquals(), CodegenEvalTupleRow(), CodegenHashCurrentRow(), Equals(), EvalRow(), HashVariableLenRow(), last_expr_value_null(), and OldHashTable().

uint8_t* impala::OldHashTable::expr_values_buffer_

private

buffer to store evaluated expr results. This address must not change once allocated since the address is baked into the codegen

Definition at line 487 of file old-hash-table.h.

Referenced by Close(), CodegenEquals(), CodegenEvalTupleRow(), CodegenHashCurrentRow(), Equals(), EvalRow(), HashCurrentRow(), HashVariableLenRow(), last_expr_value(), and OldHashTable().

std::vector<int> impala::OldHashTable::expr_values_buffer_offsets_

private

Cache of exprs values for the current row being evaluated. This can either be a build row (during Insert()) or probe row (during Find()).

Definition at line 477 of file old-hash-table.h.

Referenced by CodegenEquals(), CodegenEvalTupleRow(), CodegenHashCurrentRow(), Equals(), EvalRow(), HashVariableLenRow(), last_expr_value(), and OldHashTable().

const bool impala::OldHashTable::finds_nulls_

private

Definition at line 438 of file old-hash-table.h.

Referenced by EvalAndHashProbe().

const int32_t impala::OldHashTable::initial_seed_

private

Definition at line 441 of file old-hash-table.h.

Referenced by AddBitmapFilters(), CodegenHashCurrentRow(), HashCurrentRow(), and HashVariableLenRow().

const char * OldHashTable::LLVM_CLASS_NAME = "class.impala::OldHashTable"

static

Definition at line 238 of file old-hash-table.h.

Referenced by CodegenEquals(), CodegenEvalTupleRow(), and CodegenHashCurrentRow().

const float OldHashTable::MAX_BUCKET_OCCUPANCY_FRACTION = 0.75f

staticprivate

Load factor that will trigger growing the hash table on insert. This is defined as the number of non-empty buckets / total_buckets

Definition at line 424 of file old-hash-table.h.

Referenced by OldHashTable(), and ResizeBuckets().

bool impala::OldHashTable::mem_limit_exceeded_

private

Set to true if the hash table exceeds the memory limit. If this is set, subsequent calls to Insert() will be ignored.

Definition at line 465 of file old-hash-table.h.

Referenced by Insert(), InsertImpl(), mem_limit_exceeded(), and MemLimitExceeded().

boost::scoped_ptr<MemPool> impala::OldHashTable::mem_pool_

private

MemPool used to allocate data pages.

Definition at line 450 of file old-hash-table.h.

Referenced by Close(), and GrowNodeArray().

MemTracker* impala::OldHashTable::mem_tracker_

private

Definition at line 461 of file old-hash-table.h.

Referenced by Close(), GrowNodeArray(), MemLimitExceeded(), OldHashTable(), and ResizeBuckets().

Node* impala::OldHashTable::next_node_

private

Next node to insert.

Definition at line 456 of file old-hash-table.h.

Referenced by GrowNodeArray(), and InsertImpl().

int impala::OldHashTable::node_remaining_current_page_

private

Number of nodes left in the current page.

Definition at line 459 of file old-hash-table.h.

Referenced by byte_size(), GrowNodeArray(), and InsertImpl().

int64_t impala::OldHashTable::num_buckets_

private

equal to buckets_.size() but more efficient than the size function

Definition at line 470 of file old-hash-table.h.

Referenced by Find(), Insert(), InsertImpl(), NextBucket(), OldHashTable(), and ResizeBuckets().

int64_t impala::OldHashTable::num_buckets_till_resize_

private

The number of filled buckets to trigger a resize. This is cached for efficiency.

Definition at line 473 of file old-hash-table.h.

Referenced by Insert(), OldHashTable(), and ResizeBuckets().

const int impala::OldHashTable::num_build_tuples_

private

Number of Tuple* in the build tuple row.

Definition at line 432 of file old-hash-table.h.

int impala::OldHashTable::num_data_pages_

private

Number of data pages for nodes.

Definition at line 453 of file old-hash-table.h.

Referenced by Close(), and GrowNodeArray().

int64_t impala::OldHashTable::num_filled_buckets_

private

Number of non-empty buckets. Used to determine when to grow and rehash.

Definition at line 444 of file old-hash-table.h.

Referenced by AddToBucket(), Insert(), load_factor(), and MoveNode().

int64_t impala::OldHashTable::num_nodes_

private

number of nodes stored (i.e. size of hash table)

Definition at line 447 of file old-hash-table.h.

Referenced by byte_size(), InsertImpl(), and size().

const std::vector<ExprContext*>& impala::OldHashTable::probe_expr_ctxs_

private

Definition at line 429 of file old-hash-table.h.

Referenced by AddBitmapFilters(), CodegenEvalTupleRow(), EvalProbeRow(), and OldHashTable().

int impala::OldHashTable::results_buffer_size_

private

byte size of 'expr_values_buffer_'

Definition at line 483 of file old-hash-table.h.

Referenced by CodegenHashCurrentRow(), HashCurrentRow(), and OldHashTable().

RuntimeState* impala::OldHashTable::state_

private

Definition at line 426 of file old-hash-table.h.

Referenced by AddBitmapFilters(), and MemLimitExceeded().

const bool impala::OldHashTable::stores_nulls_

private

Constants on how the hash table should behave. Joins and aggs have slightly different behavior. TODO: these constants are an ideal candidate to be removed with codegen.

Definition at line 437 of file old-hash-table.h.

Referenced by CodegenEquals(), CodegenEvalTupleRow(), CodegenHashCurrentRow(), Equals(), EvalAndHashBuild(), EvalAndHashProbe(), EvalRow(), and Insert().