| <!DOCTYPE html PUBLIC "-//W3C//DTD XHTML 1.0 Transitional//EN" "http://www.w3.org/TR/xhtml1/DTD/xhtml1-transitional.dtd"> |
| <html xmlns="http://www.w3.org/1999/xhtml"> |
| <head> |
| <meta http-equiv="Content-Type" content="text/xhtml;charset=UTF-8"/> |
| <meta http-equiv="X-UA-Compatible" content="IE=9"/> |
| <meta name="generator" content="Doxygen 1.8.6"/> |
| <title>Impala: impala::HashTable Class Reference</title> |
| <link href="tabs.css" rel="stylesheet" type="text/css"/> |
| <script type="text/javascript" src="jquery.js"></script> |
| <script type="text/javascript" src="dynsections.js"></script> |
| <link href="navtree.css" rel="stylesheet" type="text/css"/> |
| <script type="text/javascript" src="resize.js"></script> |
| <script type="text/javascript" src="navtree.js"></script> |
| <script type="text/javascript"> |
| $(document).ready(initResizable); |
| $(window).load(resizeHeight); |
| </script> |
| <link href="search/search.css" rel="stylesheet" type="text/css"/> |
| <script type="text/javascript" src="search/search.js"></script> |
| <script type="text/javascript"> |
| $(document).ready(function() { searchBox.OnSelectItem(0); }); |
| </script> |
| <link href="doxygen.css" rel="stylesheet" type="text/css" /> |
| </head> |
| <body> |
| <div id="top"><!-- do not remove this div, it is closed by doxygen! --> |
| <div id="titlearea"> |
| <table cellspacing="0" cellpadding="0"> |
| <tbody> |
| <tr style="height: 56px;"> |
| <td style="padding-left: 0.5em;"> |
| <div id="projectname">Impala |
| </div> |
| <div id="projectbrief">Impalaistheopensource,nativeanalyticdatabaseforApacheHadoop.</div> |
| </td> |
| </tr> |
| </tbody> |
| </table> |
| </div> |
| <!-- end header part --> |
| <!-- Generated by Doxygen 1.8.6 --> |
| <script type="text/javascript"> |
| var searchBox = new SearchBox("searchBox", "search",false,'Search'); |
| </script> |
| <div id="navrow1" class="tabs"> |
| <ul class="tablist"> |
| <li><a href="index.html"><span>Main Page</span></a></li> |
| <li><a href="namespaces.html"><span>Namespaces</span></a></li> |
| <li class="current"><a href="annotated.html"><span>Classes</span></a></li> |
| <li><a href="files.html"><span>Files</span></a></li> |
| <li> |
| <div id="MSearchBox" class="MSearchBoxInactive"> |
| <span class="left"> |
| <img id="MSearchSelect" src="search/mag_sel.png" |
| onmouseover="return searchBox.OnSearchSelectShow()" |
| onmouseout="return searchBox.OnSearchSelectHide()" |
| alt=""/> |
| <input type="text" id="MSearchField" value="Search" accesskey="S" |
| onfocus="searchBox.OnSearchFieldFocus(true)" |
| onblur="searchBox.OnSearchFieldFocus(false)" |
| onkeyup="searchBox.OnSearchFieldChange(event)"/> |
| </span><span class="right"> |
| <a id="MSearchClose" href="javascript:searchBox.CloseResultsWindow()"><img id="MSearchCloseImg" border="0" src="search/close.png" alt=""/></a> |
| </span> |
| </div> |
| </li> |
| </ul> |
| </div> |
| <div id="navrow2" class="tabs2"> |
| <ul class="tablist"> |
| <li><a href="annotated.html"><span>Class List</span></a></li> |
| <li><a href="classes.html"><span>Class Index</span></a></li> |
| <li><a href="inherits.html"><span>Class Hierarchy</span></a></li> |
| <li><a href="functions.html"><span>Class Members</span></a></li> |
| </ul> |
| </div> |
| </div><!-- top --> |
| <div id="side-nav" class="ui-resizable side-nav-resizable"> |
| <div id="nav-tree"> |
| <div id="nav-tree-contents"> |
| <div id="nav-sync" class="sync"></div> |
| </div> |
| </div> |
| <div id="splitbar" style="-moz-user-select:none;" |
| class="ui-resizable-handle"> |
| </div> |
| </div> |
| <script type="text/javascript"> |
| $(document).ready(function(){initNavTree('classimpala_1_1HashTable.html','');}); |
| </script> |
| <div id="doc-content"> |
| <!-- window showing the filter options --> |
| <div id="MSearchSelectWindow" |
| onmouseover="return searchBox.OnSearchSelectShow()" |
| onmouseout="return searchBox.OnSearchSelectHide()" |
| onkeydown="return searchBox.OnSearchSelectKey(event)"> |
| <a class="SelectItem" href="javascript:void(0)" onclick="searchBox.OnSelectItem(0)"><span class="SelectionMark"> </span>All</a><a class="SelectItem" href="javascript:void(0)" onclick="searchBox.OnSelectItem(1)"><span class="SelectionMark"> </span>Classes</a><a class="SelectItem" href="javascript:void(0)" onclick="searchBox.OnSelectItem(2)"><span class="SelectionMark"> </span>Namespaces</a><a class="SelectItem" href="javascript:void(0)" onclick="searchBox.OnSelectItem(3)"><span class="SelectionMark"> </span>Files</a><a class="SelectItem" href="javascript:void(0)" onclick="searchBox.OnSelectItem(4)"><span class="SelectionMark"> </span>Functions</a><a class="SelectItem" href="javascript:void(0)" onclick="searchBox.OnSelectItem(5)"><span class="SelectionMark"> </span>Variables</a><a class="SelectItem" href="javascript:void(0)" onclick="searchBox.OnSelectItem(6)"><span class="SelectionMark"> </span>Typedefs</a><a class="SelectItem" href="javascript:void(0)" onclick="searchBox.OnSelectItem(7)"><span class="SelectionMark"> </span>Enumerations</a><a class="SelectItem" href="javascript:void(0)" onclick="searchBox.OnSelectItem(8)"><span class="SelectionMark"> </span>Enumerator</a><a class="SelectItem" href="javascript:void(0)" onclick="searchBox.OnSelectItem(9)"><span class="SelectionMark"> </span>Friends</a><a class="SelectItem" href="javascript:void(0)" onclick="searchBox.OnSelectItem(10)"><span class="SelectionMark"> </span>Macros</a></div> |
| |
| <!-- iframe showing the search results (closed by default) --> |
| <div id="MSearchResultsWindow"> |
| <iframe src="javascript:void(0)" frameborder="0" |
| name="MSearchResults" id="MSearchResults"> |
| </iframe> |
| </div> |
| |
| <div class="header"> |
| <div class="summary"> |
| <a href="#nested-classes">Classes</a> | |
| <a href="#pub-methods">Public Member Functions</a> | |
| <a href="#pub-static-methods">Static Public Member Functions</a> | |
| <a href="#pri-methods">Private Member Functions</a> | |
| <a href="#pri-attribs">Private Attributes</a> | |
| <a href="#pri-static-attribs">Static Private Attributes</a> | |
| <a href="#friends">Friends</a> | |
| <a href="classimpala_1_1HashTable-members.html">List of all members</a> </div> |
| <div class="headertitle"> |
| <div class="title">impala::HashTable Class Reference</div> </div> |
| </div><!--header--> |
| <div class="contents"> |
| |
| <p><code>#include <<a class="el" href="hash-table_8h_source.html">hash-table.h</a>></code></p> |
| <div class="dynheader"> |
| Collaboration diagram for impala::HashTable:</div> |
| <div class="dyncontent"> |
| <div class="center"><div class="zoom"><iframe scrolling="no" frameborder="0" src="classimpala_1_1HashTable__coll__graph.svg" width="100%" height="600"><p><b>This browser is not able to show SVG: try Firefox, Chrome, Safari, or Opera instead.</b></p></iframe></div></div> |
| </div> |
| <table class="memberdecls"> |
| <tr class="heading"><td colspan="2"><h2 class="groupheader"><a name="nested-classes"></a> |
| Classes</h2></td></tr> |
| <tr class="memitem:"><td class="memItemLeft" align="right" valign="top">struct  </td><td class="memItemRight" valign="bottom"><a class="el" href="structimpala_1_1HashTable_1_1Bucket.html">Bucket</a></td></tr> |
| <tr class="separator:"><td class="memSeparator" colspan="2"> </td></tr> |
| <tr class="memitem:"><td class="memItemLeft" align="right" valign="top">struct  </td><td class="memItemRight" valign="bottom"><a class="el" href="structimpala_1_1HashTable_1_1DuplicateNode.html">DuplicateNode</a></td></tr> |
| <tr class="memdesc:"><td class="mdescLeft"> </td><td class="mdescRight">Linked list of entries used for duplicates. <a href="structimpala_1_1HashTable_1_1DuplicateNode.html#details">More...</a><br/></td></tr> |
| <tr class="separator:"><td class="memSeparator" colspan="2"> </td></tr> |
| <tr class="memitem:"><td class="memItemLeft" align="right" valign="top">union  </td><td class="memItemRight" valign="bottom"><a class="el" href="unionimpala_1_1HashTable_1_1HtData.html">HtData</a></td></tr> |
| <tr class="memdesc:"><td class="mdescLeft"> </td><td class="mdescRight">Either the row in the tuple stream or a pointer to the single tuple of this row. <a href="unionimpala_1_1HashTable_1_1HtData.html#details">More...</a><br/></td></tr> |
| <tr class="separator:"><td class="memSeparator" colspan="2"> </td></tr> |
| <tr class="memitem:"><td class="memItemLeft" align="right" valign="top">class  </td><td class="memItemRight" valign="bottom"><a class="el" href="classimpala_1_1HashTable_1_1Iterator.html">Iterator</a></td></tr> |
| <tr class="memdesc:"><td class="mdescLeft"> </td><td class="mdescRight">stl-like iterator interface. <a href="classimpala_1_1HashTable_1_1Iterator.html#details">More...</a><br/></td></tr> |
| <tr class="separator:"><td class="memSeparator" colspan="2"> </td></tr> |
| </table><table class="memberdecls"> |
| <tr class="heading"><td colspan="2"><h2 class="groupheader"><a name="pub-methods"></a> |
| Public Member Functions</h2></td></tr> |
| <tr class="memitem:af1cccf76b721c82e567a687b5660613d"><td class="memItemLeft" align="right" valign="top"> </td><td class="memItemRight" valign="bottom"><a class="el" href="classimpala_1_1HashTable.html#af1cccf76b721c82e567a687b5660613d">HashTable</a> (<a class="el" href="classimpala_1_1RuntimeState.html">RuntimeState</a> *state, <a class="el" href="structimpala_1_1BufferedBlockMgr_1_1Client.html">BufferedBlockMgr::Client</a> *client, int num_build_tuples, <a class="el" href="classimpala_1_1BufferedTupleStream.html">BufferedTupleStream</a> *tuple_stream, int64_t max_num_buckets, int64_t initial_num_buckets=1024)</td></tr> |
| <tr class="separator:af1cccf76b721c82e567a687b5660613d"><td class="memSeparator" colspan="2"> </td></tr> |
| <tr class="memitem:ae8b96ae30e44e104c678d17d0a686d32"><td class="memItemLeft" align="right" valign="top"> </td><td class="memItemRight" valign="bottom"><a class="el" href="classimpala_1_1HashTable.html#ae8b96ae30e44e104c678d17d0a686d32">HashTable</a> (<a class="el" href="classimpala_1_1MemPool.html">MemPool</a> *<a class="el" href="expr-benchmark_8cc.html#a3a5de7bd423fbc0afc4cf935c166ca6b">pool</a>, <a class="el" href="classbool.html">bool</a> quadratic_probing, int <a class="el" href="classimpala_1_1HashTable.html#aa240fc7c128e0f6bd1e99b1b26e564ac">num_buckets</a>)</td></tr> |
| <tr class="separator:ae8b96ae30e44e104c678d17d0a686d32"><td class="memSeparator" colspan="2"> </td></tr> |
| <tr class="memitem:a25f62c459962b594afd0922f71a50433"><td class="memItemLeft" align="right" valign="top"><a class="el" href="classbool.html">bool</a> </td><td class="memItemRight" valign="bottom"><a class="el" href="classimpala_1_1HashTable.html#a25f62c459962b594afd0922f71a50433">Init</a> ()</td></tr> |
| <tr class="memdesc:a25f62c459962b594afd0922f71a50433"><td class="mdescLeft"> </td><td class="mdescRight">Allocates the initial bucket structure. Returns false if OOM. <a href="#a25f62c459962b594afd0922f71a50433">More...</a><br/></td></tr> |
| <tr class="separator:a25f62c459962b594afd0922f71a50433"><td class="memSeparator" colspan="2"> </td></tr> |
| <tr class="memitem:a849d5e05fa77c04ec11efc6fcf266284"><td class="memItemLeft" align="right" valign="top">void </td><td class="memItemRight" valign="bottom"><a class="el" href="classimpala_1_1HashTable.html#a849d5e05fa77c04ec11efc6fcf266284">Close</a> ()</td></tr> |
| <tr class="memdesc:a849d5e05fa77c04ec11efc6fcf266284"><td class="mdescLeft"> </td><td class="mdescRight">Call to cleanup any resources. Must be called once. <a href="#a849d5e05fa77c04ec11efc6fcf266284">More...</a><br/></td></tr> |
| <tr class="separator:a849d5e05fa77c04ec11efc6fcf266284"><td class="memSeparator" colspan="2"> </td></tr> |
| <tr class="memitem:a60e5c8ae0744eb588bfbb8ae98bbeaf0"><td class="memItemLeft" align="right" valign="top"><a class="el" href="classbool.html">bool</a> <a class="el" href="impala-ir_8h.html#af2b653018219cda8c9a2d9efc0ce3f44">IR_ALWAYS_INLINE</a> </td><td class="memItemRight" valign="bottom"><a class="el" href="classimpala_1_1HashTable.html#a60e5c8ae0744eb588bfbb8ae98bbeaf0">Insert</a> (<a class="el" href="classimpala_1_1HashTableCtx.html">HashTableCtx</a> *ht_ctx, const <a class="el" href="structimpala_1_1BufferedTupleStream_1_1RowIdx.html">BufferedTupleStream::RowIdx</a> &idx, <a class="el" href="classimpala_1_1TupleRow.html">TupleRow</a> *row, uint32_t <a class="el" href="namespaceimpala.html#a50b59c9628eedf49aa82643ce601967d">hash</a>)</td></tr> |
| <tr class="separator:a60e5c8ae0744eb588bfbb8ae98bbeaf0"><td class="memSeparator" colspan="2"> </td></tr> |
| <tr class="memitem:a055d0c676428583f876058dcfbfb15a4"><td class="memItemLeft" align="right" valign="top"><a class="el" href="classbool.html">bool</a> <a class="el" href="impala-ir_8h.html#af2b653018219cda8c9a2d9efc0ce3f44">IR_ALWAYS_INLINE</a> </td><td class="memItemRight" valign="bottom"><a class="el" href="classimpala_1_1HashTable.html#a055d0c676428583f876058dcfbfb15a4">Insert</a> (<a class="el" href="classimpala_1_1HashTableCtx.html">HashTableCtx</a> *ht_ctx, <a class="el" href="classimpala_1_1Tuple.html">Tuple</a> *tuple, uint32_t <a class="el" href="namespaceimpala.html#a50b59c9628eedf49aa82643ce601967d">hash</a>)</td></tr> |
| <tr class="separator:a055d0c676428583f876058dcfbfb15a4"><td class="memSeparator" colspan="2"> </td></tr> |
| <tr class="memitem:ac128e2d41168cc9e08b40c34e1a29bc3"><td class="memItemLeft" align="right" valign="top"><a class="el" href="classimpala_1_1HashTable_1_1Iterator.html">Iterator</a> <a class="el" href="impala-ir_8h.html#af2b653018219cda8c9a2d9efc0ce3f44">IR_ALWAYS_INLINE</a> </td><td class="memItemRight" valign="bottom"><a class="el" href="classimpala_1_1HashTable.html#ac128e2d41168cc9e08b40c34e1a29bc3">Find</a> (<a class="el" href="classimpala_1_1HashTableCtx.html">HashTableCtx</a> *ht_ctx, uint32_t <a class="el" href="namespaceimpala.html#a50b59c9628eedf49aa82643ce601967d">hash</a>)</td></tr> |
| <tr class="separator:ac128e2d41168cc9e08b40c34e1a29bc3"><td class="memSeparator" colspan="2"> </td></tr> |
| <tr class="memitem:ae7006f3aff0395a0251fbb2765634b96"><td class="memItemLeft" align="right" valign="top">int64_t </td><td class="memItemRight" valign="bottom"><a class="el" href="classimpala_1_1HashTable.html#ae7006f3aff0395a0251fbb2765634b96">size</a> () const </td></tr> |
| <tr class="memdesc:ae7006f3aff0395a0251fbb2765634b96"><td class="mdescLeft"> </td><td class="mdescRight">Returns number of elements inserted in the hash table. <a href="#ae7006f3aff0395a0251fbb2765634b96">More...</a><br/></td></tr> |
| <tr class="separator:ae7006f3aff0395a0251fbb2765634b96"><td class="memSeparator" colspan="2"> </td></tr> |
| <tr class="memitem:a4a5e511b2e7945673ce5a0bc6319b55f"><td class="memItemLeft" align="right" valign="top">int64_t </td><td class="memItemRight" valign="bottom"><a class="el" href="classimpala_1_1HashTable.html#a4a5e511b2e7945673ce5a0bc6319b55f">EmptyBuckets</a> () const </td></tr> |
| <tr class="memdesc:a4a5e511b2e7945673ce5a0bc6319b55f"><td class="mdescLeft"> </td><td class="mdescRight">Returns the number of empty buckets. <a href="#a4a5e511b2e7945673ce5a0bc6319b55f">More...</a><br/></td></tr> |
| <tr class="separator:a4a5e511b2e7945673ce5a0bc6319b55f"><td class="memSeparator" colspan="2"> </td></tr> |
| <tr class="memitem:aa240fc7c128e0f6bd1e99b1b26e564ac"><td class="memItemLeft" align="right" valign="top">int64_t </td><td class="memItemRight" valign="bottom"><a class="el" href="classimpala_1_1HashTable.html#aa240fc7c128e0f6bd1e99b1b26e564ac">num_buckets</a> () const </td></tr> |
| <tr class="memdesc:aa240fc7c128e0f6bd1e99b1b26e564ac"><td class="mdescLeft"> </td><td class="mdescRight">Returns the number of buckets. <a href="#aa240fc7c128e0f6bd1e99b1b26e564ac">More...</a><br/></td></tr> |
| <tr class="separator:aa240fc7c128e0f6bd1e99b1b26e564ac"><td class="memSeparator" colspan="2"> </td></tr> |
| <tr class="memitem:a463369a1c40b9254b0805264077b3d8a"><td class="memItemLeft" align="right" valign="top">double </td><td class="memItemRight" valign="bottom"><a class="el" href="classimpala_1_1HashTable.html#a463369a1c40b9254b0805264077b3d8a">load_factor</a> () const </td></tr> |
| <tr class="memdesc:a463369a1c40b9254b0805264077b3d8a"><td class="mdescLeft"> </td><td class="mdescRight">Returns the load factor (the number of non-empty buckets) <a href="#a463369a1c40b9254b0805264077b3d8a">More...</a><br/></td></tr> |
| <tr class="separator:a463369a1c40b9254b0805264077b3d8a"><td class="memSeparator" colspan="2"> </td></tr> |
| <tr class="memitem:ab01f3fe1ea91d152a0ff15540e4fc6f6"><td class="memItemLeft" align="right" valign="top">int64_t </td><td class="memItemRight" valign="bottom"><a class="el" href="classimpala_1_1HashTable.html#ab01f3fe1ea91d152a0ff15540e4fc6f6">CurrentMemSize</a> () const </td></tr> |
| <tr class="separator:ab01f3fe1ea91d152a0ff15540e4fc6f6"><td class="memSeparator" colspan="2"> </td></tr> |
| <tr class="memitem:a008c8765a5a4c57a17abf299882d79c2"><td class="memItemLeft" align="right" valign="top"><a class="el" href="classbool.html">bool</a> </td><td class="memItemRight" valign="bottom"><a class="el" href="classimpala_1_1HashTable.html#a008c8765a5a4c57a17abf299882d79c2">CheckAndResize</a> (<a class="el" href="classuint64__t.html">uint64_t</a> buckets_to_fill, <a class="el" href="classimpala_1_1HashTableCtx.html">HashTableCtx</a> *ht_ctx)</td></tr> |
| <tr class="separator:a008c8765a5a4c57a17abf299882d79c2"><td class="memSeparator" colspan="2"> </td></tr> |
| <tr class="memitem:a9ead10df58713f8150ea8c2330820506"><td class="memItemLeft" align="right" valign="top">int64_t </td><td class="memItemRight" valign="bottom"><a class="el" href="classimpala_1_1HashTable.html#a9ead10df58713f8150ea8c2330820506">byte_size</a> () const </td></tr> |
| <tr class="memdesc:a9ead10df58713f8150ea8c2330820506"><td class="mdescLeft"> </td><td class="mdescRight">Returns the number of bytes allocated to the hash table. <a href="#a9ead10df58713f8150ea8c2330820506">More...</a><br/></td></tr> |
| <tr class="separator:a9ead10df58713f8150ea8c2330820506"><td class="memSeparator" colspan="2"> </td></tr> |
| <tr class="memitem:a98f48e7cfbdb196b9a9e9413f6c7fcff"><td class="memItemLeft" align="right" valign="top"><a class="el" href="classimpala_1_1HashTable_1_1Iterator.html">Iterator</a> </td><td class="memItemRight" valign="bottom"><a class="el" href="classimpala_1_1HashTable.html#a98f48e7cfbdb196b9a9e9413f6c7fcff">Begin</a> (<a class="el" href="classimpala_1_1HashTableCtx.html">HashTableCtx</a> *ht_ctx)</td></tr> |
| <tr class="separator:a98f48e7cfbdb196b9a9e9413f6c7fcff"><td class="memSeparator" colspan="2"> </td></tr> |
| <tr class="memitem:ac03658dce51b9f2582daebec0646e80a"><td class="memItemLeft" align="right" valign="top"><a class="el" href="classimpala_1_1HashTable_1_1Iterator.html">Iterator</a> </td><td class="memItemRight" valign="bottom"><a class="el" href="classimpala_1_1HashTable.html#ac03658dce51b9f2582daebec0646e80a">FirstUnmatched</a> (<a class="el" href="classimpala_1_1HashTableCtx.html">HashTableCtx</a> *ctx)</td></tr> |
| <tr class="separator:ac03658dce51b9f2582daebec0646e80a"><td class="memSeparator" colspan="2"> </td></tr> |
| <tr class="memitem:aab2de3f4ada5cdf02366f71e763c967d"><td class="memItemLeft" align="right" valign="top"><a class="el" href="classbool.html">bool</a> </td><td class="memItemRight" valign="bottom"><a class="el" href="classimpala_1_1HashTable.html#aab2de3f4ada5cdf02366f71e763c967d">HasMatches</a> () const </td></tr> |
| <tr class="memdesc:aab2de3f4ada5cdf02366f71e763c967d"><td class="mdescLeft"> </td><td class="mdescRight">Return true if there was a least one match. <a href="#aab2de3f4ada5cdf02366f71e763c967d">More...</a><br/></td></tr> |
| <tr class="separator:aab2de3f4ada5cdf02366f71e763c967d"><td class="memSeparator" colspan="2"> </td></tr> |
| <tr class="memitem:ac62ebb8f6c388dff042794e69de596a9"><td class="memItemLeft" align="right" valign="top"><a class="el" href="classimpala_1_1HashTable_1_1Iterator.html">Iterator</a> </td><td class="memItemRight" valign="bottom"><a class="el" href="classimpala_1_1HashTable.html#ac62ebb8f6c388dff042794e69de596a9">End</a> ()</td></tr> |
| <tr class="memdesc:ac62ebb8f6c388dff042794e69de596a9"><td class="mdescLeft"> </td><td class="mdescRight">Return end marker. <a href="#ac62ebb8f6c388dff042794e69de596a9">More...</a><br/></td></tr> |
| <tr class="separator:ac62ebb8f6c388dff042794e69de596a9"><td class="memSeparator" colspan="2"> </td></tr> |
| <tr class="memitem:ae83037529a3f307470860bbeb3e71024"><td class="memItemLeft" align="right" valign="top">std::string </td><td class="memItemRight" valign="bottom"><a class="el" href="classimpala_1_1HashTable.html#ae83037529a3f307470860bbeb3e71024">DebugString</a> (<a class="el" href="classbool.html">bool</a> skip_empty, <a class="el" href="classbool.html">bool</a> show_match, const <a class="el" href="classimpala_1_1RowDescriptor.html">RowDescriptor</a> *build_desc)</td></tr> |
| <tr class="separator:ae83037529a3f307470860bbeb3e71024"><td class="memSeparator" colspan="2"> </td></tr> |
| <tr class="memitem:a47c85016bff3fd0e9092b378993b4b15"><td class="memItemLeft" align="right" valign="top">void </td><td class="memItemRight" valign="bottom"><a class="el" href="classimpala_1_1HashTable.html#a47c85016bff3fd0e9092b378993b4b15">DebugStringTuple</a> (std::stringstream &ss, <a class="el" href="unionimpala_1_1HashTable_1_1HtData.html">HtData</a> &htdata, const <a class="el" href="classimpala_1_1RowDescriptor.html">RowDescriptor</a> *desc)</td></tr> |
| <tr class="memdesc:a47c85016bff3fd0e9092b378993b4b15"><td class="mdescLeft"> </td><td class="mdescRight">Print the content of a bucket or node. <a href="#a47c85016bff3fd0e9092b378993b4b15">More...</a><br/></td></tr> |
| <tr class="separator:a47c85016bff3fd0e9092b378993b4b15"><td class="memSeparator" colspan="2"> </td></tr> |
| <tr class="memitem:a44aeea6af10973c12e6801dc409d7847"><td class="memItemLeft" align="right" valign="top">std::string </td><td class="memItemRight" valign="bottom"><a class="el" href="classimpala_1_1HashTable.html#a44aeea6af10973c12e6801dc409d7847">PrintStats</a> () const </td></tr> |
| <tr class="memdesc:a44aeea6af10973c12e6801dc409d7847"><td class="mdescLeft"> </td><td class="mdescRight">Update and print some statistics that can be used for performance debugging. <a href="#a44aeea6af10973c12e6801dc409d7847">More...</a><br/></td></tr> |
| <tr class="separator:a44aeea6af10973c12e6801dc409d7847"><td class="memSeparator" colspan="2"> </td></tr> |
| </table><table class="memberdecls"> |
| <tr class="heading"><td colspan="2"><h2 class="groupheader"><a name="pub-static-methods"></a> |
| Static Public Member Functions</h2></td></tr> |
| <tr class="memitem:a5cc6716b7f775323d6c6f32cacbb23b5"><td class="memItemLeft" align="right" valign="top">static int64_t </td><td class="memItemRight" valign="bottom"><a class="el" href="classimpala_1_1HashTable.html#a5cc6716b7f775323d6c6f32cacbb23b5">EstimateNumBuckets</a> (int64_t num_rows)</td></tr> |
| <tr class="separator:a5cc6716b7f775323d6c6f32cacbb23b5"><td class="memSeparator" colspan="2"> </td></tr> |
| <tr class="memitem:ab4f7267cccc84203f4891ed1e574b644"><td class="memItemLeft" align="right" valign="top">static int64_t </td><td class="memItemRight" valign="bottom"><a class="el" href="classimpala_1_1HashTable.html#ab4f7267cccc84203f4891ed1e574b644">EstimateSize</a> (int64_t num_rows)</td></tr> |
| <tr class="separator:ab4f7267cccc84203f4891ed1e574b644"><td class="memSeparator" colspan="2"> </td></tr> |
| </table><table class="memberdecls"> |
| <tr class="heading"><td colspan="2"><h2 class="groupheader"><a name="pri-methods"></a> |
| Private Member Functions</h2></td></tr> |
| <tr class="memitem:a0c1d67cc8cebd5cd2fb855fa5d0a4a57"><td class="memItemLeft" align="right" valign="top">int64_t <a class="el" href="impala-ir_8h.html#af2b653018219cda8c9a2d9efc0ce3f44">IR_ALWAYS_INLINE</a> </td><td class="memItemRight" valign="bottom"><a class="el" href="classimpala_1_1HashTable.html#a0c1d67cc8cebd5cd2fb855fa5d0a4a57">Probe</a> (<a class="el" href="structimpala_1_1HashTable_1_1Bucket.html">Bucket</a> *buckets, int64_t <a class="el" href="classimpala_1_1HashTable.html#aa240fc7c128e0f6bd1e99b1b26e564ac">num_buckets</a>, <a class="el" href="classimpala_1_1HashTableCtx.html">HashTableCtx</a> *ht_ctx, uint32_t <a class="el" href="namespaceimpala.html#a50b59c9628eedf49aa82643ce601967d">hash</a>, <a class="el" href="classbool.html">bool</a> *found)</td></tr> |
| <tr class="memdesc:a0c1d67cc8cebd5cd2fb855fa5d0a4a57"><td class="mdescLeft"> </td><td class="mdescRight">There are wrappers of this function that perform the Find and Insert logic. <a href="#a0c1d67cc8cebd5cd2fb855fa5d0a4a57">More...</a><br/></td></tr> |
| <tr class="separator:a0c1d67cc8cebd5cd2fb855fa5d0a4a57"><td class="memSeparator" colspan="2"> </td></tr> |
| <tr class="memitem:a6695a051bc94f74a1d277254d6523f29"><td class="memItemLeft" align="right" valign="top"><a class="el" href="unionimpala_1_1HashTable_1_1HtData.html">HtData</a> *<a class="el" href="impala-ir_8h.html#af2b653018219cda8c9a2d9efc0ce3f44">IR_ALWAYS_INLINE</a> </td><td class="memItemRight" valign="bottom"><a class="el" href="classimpala_1_1HashTable.html#a6695a051bc94f74a1d277254d6523f29">InsertInternal</a> (<a class="el" href="classimpala_1_1HashTableCtx.html">HashTableCtx</a> *ht_ctx, uint32_t <a class="el" href="namespaceimpala.html#a50b59c9628eedf49aa82643ce601967d">hash</a>)</td></tr> |
| <tr class="separator:a6695a051bc94f74a1d277254d6523f29"><td class="memSeparator" colspan="2"> </td></tr> |
| <tr class="memitem:a67951a6c7296d85edb7a08b5fe143352"><td class="memItemLeft" align="right" valign="top">void </td><td class="memItemRight" valign="bottom"><a class="el" href="classimpala_1_1HashTable.html#a67951a6c7296d85edb7a08b5fe143352">NextFilledBucket</a> (int64_t *bucket_idx, <a class="el" href="structimpala_1_1HashTable_1_1DuplicateNode.html">DuplicateNode</a> **node)</td></tr> |
| <tr class="separator:a67951a6c7296d85edb7a08b5fe143352"><td class="memSeparator" colspan="2"> </td></tr> |
| <tr class="memitem:aeb7b0e3316dd455066ee922464ee695b"><td class="memItemLeft" align="right" valign="top"><a class="el" href="classbool.html">bool</a> </td><td class="memItemRight" valign="bottom"><a class="el" href="classimpala_1_1HashTable.html#aeb7b0e3316dd455066ee922464ee695b">ResizeBuckets</a> (int64_t <a class="el" href="classimpala_1_1HashTable.html#aa240fc7c128e0f6bd1e99b1b26e564ac">num_buckets</a>, <a class="el" href="classimpala_1_1HashTableCtx.html">HashTableCtx</a> *ht_ctx)</td></tr> |
| <tr class="memdesc:aeb7b0e3316dd455066ee922464ee695b"><td class="mdescLeft"> </td><td class="mdescRight">Resize the hash table to 'num_buckets'. Returns false on OOM. <a href="#aeb7b0e3316dd455066ee922464ee695b">More...</a><br/></td></tr> |
| <tr class="separator:aeb7b0e3316dd455066ee922464ee695b"><td class="memSeparator" colspan="2"> </td></tr> |
| <tr class="memitem:a9298e0fdd6056ad976cc5d8f38c24e81"><td class="memItemLeft" align="right" valign="top"><a class="el" href="structimpala_1_1HashTable_1_1DuplicateNode.html">DuplicateNode</a> *<a class="el" href="impala-ir_8h.html#af2b653018219cda8c9a2d9efc0ce3f44">IR_ALWAYS_INLINE</a> </td><td class="memItemRight" valign="bottom"><a class="el" href="classimpala_1_1HashTable.html#a9298e0fdd6056ad976cc5d8f38c24e81">AppendNextNode</a> (<a class="el" href="structimpala_1_1HashTable_1_1Bucket.html">Bucket</a> *bucket)</td></tr> |
| <tr class="separator:a9298e0fdd6056ad976cc5d8f38c24e81"><td class="memSeparator" colspan="2"> </td></tr> |
| <tr class="memitem:a4664c5c1d82ab068f7005a2c830910e4"><td class="memItemLeft" align="right" valign="top"><a class="el" href="structimpala_1_1HashTable_1_1DuplicateNode.html">DuplicateNode</a> *<a class="el" href="impala-ir_8h.html#af2b653018219cda8c9a2d9efc0ce3f44">IR_ALWAYS_INLINE</a> </td><td class="memItemRight" valign="bottom"><a class="el" href="classimpala_1_1HashTable.html#a4664c5c1d82ab068f7005a2c830910e4">InsertDuplicateNode</a> (int64_t bucket_idx)</td></tr> |
| <tr class="separator:a4664c5c1d82ab068f7005a2c830910e4"><td class="memSeparator" colspan="2"> </td></tr> |
| <tr class="memitem:a4222254505940c65b0b817c4836a1021"><td class="memItemLeft" align="right" valign="top">void <a class="el" href="impala-ir_8h.html#af2b653018219cda8c9a2d9efc0ce3f44">IR_ALWAYS_INLINE</a> </td><td class="memItemRight" valign="bottom"><a class="el" href="classimpala_1_1HashTable.html#a4222254505940c65b0b817c4836a1021">PrepareBucketForInsert</a> (int64_t bucket_idx, uint32_t <a class="el" href="namespaceimpala.html#a50b59c9628eedf49aa82643ce601967d">hash</a>)</td></tr> |
| <tr class="separator:a4222254505940c65b0b817c4836a1021"><td class="memSeparator" colspan="2"> </td></tr> |
| <tr class="memitem:aba3b5b944609bf0d2debbfaffb8ed767"><td class="memItemLeft" align="right" valign="top"><a class="el" href="classimpala_1_1TupleRow.html">TupleRow</a> * </td><td class="memItemRight" valign="bottom"><a class="el" href="classimpala_1_1HashTable.html#aba3b5b944609bf0d2debbfaffb8ed767">GetRow</a> (<a class="el" href="unionimpala_1_1HashTable_1_1HtData.html">HtData</a> &htdata, <a class="el" href="classimpala_1_1TupleRow.html">TupleRow</a> *row) const </td></tr> |
| <tr class="memdesc:aba3b5b944609bf0d2debbfaffb8ed767"><td class="mdescLeft"> </td><td class="mdescRight">Return the <a class="el" href="classimpala_1_1TupleRow.html">TupleRow</a> pointed by 'htdata'. <a href="#aba3b5b944609bf0d2debbfaffb8ed767">More...</a><br/></td></tr> |
| <tr class="separator:aba3b5b944609bf0d2debbfaffb8ed767"><td class="memSeparator" colspan="2"> </td></tr> |
| <tr class="memitem:a65e7a1bd56c401b2f3a7d0a4509b9b7e"><td class="memItemLeft" align="right" valign="top"><a class="el" href="classimpala_1_1TupleRow.html">TupleRow</a> * </td><td class="memItemRight" valign="bottom"><a class="el" href="classimpala_1_1HashTable.html#a65e7a1bd56c401b2f3a7d0a4509b9b7e">GetRow</a> (<a class="el" href="structimpala_1_1HashTable_1_1Bucket.html">Bucket</a> *bucket, <a class="el" href="classimpala_1_1TupleRow.html">TupleRow</a> *row) const </td></tr> |
| <tr class="separator:a65e7a1bd56c401b2f3a7d0a4509b9b7e"><td class="memSeparator" colspan="2"> </td></tr> |
| <tr class="memitem:aa7f625824191cf1eb85af0d4c79cd255"><td class="memItemLeft" align="right" valign="top"><a class="el" href="classbool.html">bool</a> </td><td class="memItemRight" valign="bottom"><a class="el" href="classimpala_1_1HashTable.html#aa7f625824191cf1eb85af0d4c79cd255">GrowNodeArray</a> ()</td></tr> |
| <tr class="memdesc:aa7f625824191cf1eb85af0d4c79cd255"><td class="mdescLeft"> </td><td class="mdescRight">Grow the node array. Returns false on OOM. <a href="#aa7f625824191cf1eb85af0d4c79cd255">More...</a><br/></td></tr> |
| <tr class="separator:aa7f625824191cf1eb85af0d4c79cd255"><td class="memSeparator" colspan="2"> </td></tr> |
| </table><table class="memberdecls"> |
| <tr class="heading"><td colspan="2"><h2 class="groupheader"><a name="pri-attribs"></a> |
| Private Attributes</h2></td></tr> |
| <tr class="memitem:ac4f83b6445d06ccc7b9c25a67c900cf9"><td class="memItemLeft" align="right" valign="top"><a class="el" href="classimpala_1_1RuntimeState.html">RuntimeState</a> * </td><td class="memItemRight" valign="bottom"><a class="el" href="classimpala_1_1HashTable.html#ac4f83b6445d06ccc7b9c25a67c900cf9">state_</a></td></tr> |
| <tr class="separator:ac4f83b6445d06ccc7b9c25a67c900cf9"><td class="memSeparator" colspan="2"> </td></tr> |
| <tr class="memitem:ab9cd09fae6e57ed0fb9fedade5f7293a"><td class="memItemLeft" align="right" valign="top"><a class="el" href="structimpala_1_1BufferedBlockMgr_1_1Client.html">BufferedBlockMgr::Client</a> * </td><td class="memItemRight" valign="bottom"><a class="el" href="classimpala_1_1HashTable.html#ab9cd09fae6e57ed0fb9fedade5f7293a">block_mgr_client_</a></td></tr> |
| <tr class="memdesc:ab9cd09fae6e57ed0fb9fedade5f7293a"><td class="mdescLeft"> </td><td class="mdescRight">Client to allocate data pages with. <a href="#ab9cd09fae6e57ed0fb9fedade5f7293a">More...</a><br/></td></tr> |
| <tr class="separator:ab9cd09fae6e57ed0fb9fedade5f7293a"><td class="memSeparator" colspan="2"> </td></tr> |
| <tr class="memitem:a53e8f6764f9f739c3a2f478c5c5e7d4c"><td class="memItemLeft" align="right" valign="top"><a class="el" href="classimpala_1_1BufferedTupleStream.html">BufferedTupleStream</a> * </td><td class="memItemRight" valign="bottom"><a class="el" href="classimpala_1_1HashTable.html#a53e8f6764f9f739c3a2f478c5c5e7d4c">tuple_stream_</a></td></tr> |
| <tr class="separator:a53e8f6764f9f739c3a2f478c5c5e7d4c"><td class="memSeparator" colspan="2"> </td></tr> |
| <tr class="memitem:a0f4c922a525b11eaf26d82a808f6c233"><td class="memItemLeft" align="right" valign="top"><a class="el" href="classimpala_1_1MemPool.html">MemPool</a> * </td><td class="memItemRight" valign="bottom"><a class="el" href="classimpala_1_1HashTable.html#a0f4c922a525b11eaf26d82a808f6c233">data_page_pool_</a></td></tr> |
| <tr class="memdesc:a0f4c922a525b11eaf26d82a808f6c233"><td class="mdescLeft"> </td><td class="mdescRight">Only used for tests to allocate data pages instead of the block mgr. <a href="#a0f4c922a525b11eaf26d82a808f6c233">More...</a><br/></td></tr> |
| <tr class="separator:a0f4c922a525b11eaf26d82a808f6c233"><td class="memSeparator" colspan="2"> </td></tr> |
| <tr class="memitem:aea176ae316a2d2e6a6ec1210c0ba7373"><td class="memItemLeft" align="right" valign="top">const <a class="el" href="classbool.html">bool</a> </td><td class="memItemRight" valign="bottom"><a class="el" href="classimpala_1_1HashTable.html#aea176ae316a2d2e6a6ec1210c0ba7373">stores_tuples_</a></td></tr> |
| <tr class="separator:aea176ae316a2d2e6a6ec1210c0ba7373"><td class="memSeparator" colspan="2"> </td></tr> |
| <tr class="memitem:a1ad3c64c070af80571ca8c79f2ed9f9a"><td class="memItemLeft" align="right" valign="top">const <a class="el" href="classbool.html">bool</a> </td><td class="memItemRight" valign="bottom"><a class="el" href="classimpala_1_1HashTable.html#a1ad3c64c070af80571ca8c79f2ed9f9a">quadratic_probing_</a></td></tr> |
| <tr class="memdesc:a1ad3c64c070af80571ca8c79f2ed9f9a"><td class="mdescLeft"> </td><td class="mdescRight">Quadratic probing enabled (as opposed to linear). <a href="#a1ad3c64c070af80571ca8c79f2ed9f9a">More...</a><br/></td></tr> |
| <tr class="separator:a1ad3c64c070af80571ca8c79f2ed9f9a"><td class="memSeparator" colspan="2"> </td></tr> |
| <tr class="memitem:a554127ece2fc15868faacb0892fb8360"><td class="memItemLeft" align="right" valign="top">std::vector<br class="typebreak"/> |
| < <a class="el" href="classimpala_1_1BufferedBlockMgr_1_1Block.html">BufferedBlockMgr::Block</a> * > </td><td class="memItemRight" valign="bottom"><a class="el" href="classimpala_1_1HashTable.html#a554127ece2fc15868faacb0892fb8360">data_pages_</a></td></tr> |
| <tr class="memdesc:a554127ece2fc15868faacb0892fb8360"><td class="mdescLeft"> </td><td class="mdescRight">Data pages for all nodes. These are always pinned. <a href="#a554127ece2fc15868faacb0892fb8360">More...</a><br/></td></tr> |
| <tr class="separator:a554127ece2fc15868faacb0892fb8360"><td class="memSeparator" colspan="2"> </td></tr> |
| <tr class="memitem:af7b361bdfb31e9438075ce2b67fd91ba"><td class="memItemLeft" align="right" valign="top">int64_t </td><td class="memItemRight" valign="bottom"><a class="el" href="classimpala_1_1HashTable.html#af7b361bdfb31e9438075ce2b67fd91ba">total_data_page_size_</a></td></tr> |
| <tr class="memdesc:af7b361bdfb31e9438075ce2b67fd91ba"><td class="mdescLeft"> </td><td class="mdescRight">Byte size of all buffers in data_pages_. <a href="#af7b361bdfb31e9438075ce2b67fd91ba">More...</a><br/></td></tr> |
| <tr class="separator:af7b361bdfb31e9438075ce2b67fd91ba"><td class="memSeparator" colspan="2"> </td></tr> |
| <tr class="memitem:ac7049a35b4d1716e54bb46d9c3ed890d"><td class="memItemLeft" align="right" valign="top"><a class="el" href="structimpala_1_1HashTable_1_1DuplicateNode.html">DuplicateNode</a> * </td><td class="memItemRight" valign="bottom"><a class="el" href="classimpala_1_1HashTable.html#ac7049a35b4d1716e54bb46d9c3ed890d">next_node_</a></td></tr> |
| <tr class="memdesc:ac7049a35b4d1716e54bb46d9c3ed890d"><td class="mdescLeft"> </td><td class="mdescRight">Next duplicate node to insert. Vaild when node_remaining_current_page_ > 0. <a href="#ac7049a35b4d1716e54bb46d9c3ed890d">More...</a><br/></td></tr> |
| <tr class="separator:ac7049a35b4d1716e54bb46d9c3ed890d"><td class="memSeparator" colspan="2"> </td></tr> |
| <tr class="memitem:ae1cda955b2701205694fdf8407f90138"><td class="memItemLeft" align="right" valign="top">int </td><td class="memItemRight" valign="bottom"><a class="el" href="classimpala_1_1HashTable.html#ae1cda955b2701205694fdf8407f90138">node_remaining_current_page_</a></td></tr> |
| <tr class="memdesc:ae1cda955b2701205694fdf8407f90138"><td class="mdescLeft"> </td><td class="mdescRight">Number of nodes left in the current page. <a href="#ae1cda955b2701205694fdf8407f90138">More...</a><br/></td></tr> |
| <tr class="separator:ae1cda955b2701205694fdf8407f90138"><td class="memSeparator" colspan="2"> </td></tr> |
| <tr class="memitem:afad2ad0b627b41b7fe072598f762c0ae"><td class="memItemLeft" align="right" valign="top">int64_t </td><td class="memItemRight" valign="bottom"><a class="el" href="classimpala_1_1HashTable.html#afad2ad0b627b41b7fe072598f762c0ae">num_duplicate_nodes_</a></td></tr> |
| <tr class="memdesc:afad2ad0b627b41b7fe072598f762c0ae"><td class="mdescLeft"> </td><td class="mdescRight">Number of duplicate nodes. <a href="#afad2ad0b627b41b7fe072598f762c0ae">More...</a><br/></td></tr> |
| <tr class="separator:afad2ad0b627b41b7fe072598f762c0ae"><td class="memSeparator" colspan="2"> </td></tr> |
| <tr class="memitem:a41ec948e01fcfa27711c3382dd5d1ffd"><td class="memItemLeft" align="right" valign="top">const int64_t </td><td class="memItemRight" valign="bottom"><a class="el" href="classimpala_1_1HashTable.html#a41ec948e01fcfa27711c3382dd5d1ffd">max_num_buckets_</a></td></tr> |
| <tr class="separator:a41ec948e01fcfa27711c3382dd5d1ffd"><td class="memSeparator" colspan="2"> </td></tr> |
| <tr class="memitem:ac461c88f6a7b8f9b0fdfc1cd42344837"><td class="memItemLeft" align="right" valign="top"><a class="el" href="structimpala_1_1HashTable_1_1Bucket.html">Bucket</a> * </td><td class="memItemRight" valign="bottom"><a class="el" href="classimpala_1_1HashTable.html#ac461c88f6a7b8f9b0fdfc1cd42344837">buckets_</a></td></tr> |
| <tr class="separator:ac461c88f6a7b8f9b0fdfc1cd42344837"><td class="memSeparator" colspan="2"> </td></tr> |
| <tr class="memitem:acc898ddea6c8c1d54f21fea4af1bcf7b"><td class="memItemLeft" align="right" valign="top">int64_t </td><td class="memItemRight" valign="bottom"><a class="el" href="classimpala_1_1HashTable.html#acc898ddea6c8c1d54f21fea4af1bcf7b">num_buckets_</a></td></tr> |
| <tr class="memdesc:acc898ddea6c8c1d54f21fea4af1bcf7b"><td class="mdescLeft"> </td><td class="mdescRight">Total number of buckets (filled and empty). <a href="#acc898ddea6c8c1d54f21fea4af1bcf7b">More...</a><br/></td></tr> |
| <tr class="separator:acc898ddea6c8c1d54f21fea4af1bcf7b"><td class="memSeparator" colspan="2"> </td></tr> |
| <tr class="memitem:a4ce8e82c4e985189eed19deb26471cc2"><td class="memItemLeft" align="right" valign="top">int64_t </td><td class="memItemRight" valign="bottom"><a class="el" href="classimpala_1_1HashTable.html#a4ce8e82c4e985189eed19deb26471cc2">num_filled_buckets_</a></td></tr> |
| <tr class="memdesc:a4ce8e82c4e985189eed19deb26471cc2"><td class="mdescLeft"> </td><td class="mdescRight">Number of non-empty buckets. Used to determine when to resize. <a href="#a4ce8e82c4e985189eed19deb26471cc2">More...</a><br/></td></tr> |
| <tr class="separator:a4ce8e82c4e985189eed19deb26471cc2"><td class="memSeparator" colspan="2"> </td></tr> |
| <tr class="memitem:a92d8c35c802147adf40685e7c1bdcca7"><td class="memItemLeft" align="right" valign="top">int64_t </td><td class="memItemRight" valign="bottom"><a class="el" href="classimpala_1_1HashTable.html#a92d8c35c802147adf40685e7c1bdcca7">num_buckets_with_duplicates_</a></td></tr> |
| <tr class="separator:a92d8c35c802147adf40685e7c1bdcca7"><td class="memSeparator" colspan="2"> </td></tr> |
| <tr class="memitem:a6d7e2d70c48ad221333f5b939745134b"><td class="memItemLeft" align="right" valign="top">int </td><td class="memItemRight" valign="bottom"><a class="el" href="classimpala_1_1HashTable.html#a6d7e2d70c48ad221333f5b939745134b">num_build_tuples_</a></td></tr> |
| <tr class="separator:a6d7e2d70c48ad221333f5b939745134b"><td class="memSeparator" colspan="2"> </td></tr> |
| <tr class="memitem:a63154f1e57a11b4d9362943bae38ef5a"><td class="memItemLeft" align="right" valign="top"><a class="el" href="classbool.html">bool</a> </td><td class="memItemRight" valign="bottom"><a class="el" href="classimpala_1_1HashTable.html#a63154f1e57a11b4d9362943bae38ef5a">has_matches_</a></td></tr> |
| <tr class="separator:a63154f1e57a11b4d9362943bae38ef5a"><td class="memSeparator" colspan="2"> </td></tr> |
| <tr class="memitem:ad5cafb9172df65844a941a43a0e80b3e"><td class="memItemLeft" align="right" valign="top">int64_t </td><td class="memItemRight" valign="bottom"><a class="el" href="classimpala_1_1HashTable.html#ad5cafb9172df65844a941a43a0e80b3e">num_probes_</a></td></tr> |
| <tr class="separator:ad5cafb9172df65844a941a43a0e80b3e"><td class="memSeparator" colspan="2"> </td></tr> |
| <tr class="memitem:a3f5da1f068a86b1cae6f207dfce96710"><td class="memItemLeft" align="right" valign="top">int64_t </td><td class="memItemRight" valign="bottom"><a class="el" href="classimpala_1_1HashTable.html#a3f5da1f068a86b1cae6f207dfce96710">num_failed_probes_</a></td></tr> |
| <tr class="memdesc:a3f5da1f068a86b1cae6f207dfce96710"><td class="mdescLeft"> </td><td class="mdescRight">Number of probes that failed and had to fall back to linear probing without cap. <a href="#a3f5da1f068a86b1cae6f207dfce96710">More...</a><br/></td></tr> |
| <tr class="separator:a3f5da1f068a86b1cae6f207dfce96710"><td class="memSeparator" colspan="2"> </td></tr> |
| <tr class="memitem:a8cc7932cc1427f6279ced8e9b915f00e"><td class="memItemLeft" align="right" valign="top">int64_t </td><td class="memItemRight" valign="bottom"><a class="el" href="classimpala_1_1HashTable.html#a8cc7932cc1427f6279ced8e9b915f00e">travel_length_</a></td></tr> |
| <tr class="separator:a8cc7932cc1427f6279ced8e9b915f00e"><td class="memSeparator" colspan="2"> </td></tr> |
| <tr class="memitem:ae21db224cca645cb112fc27d323e9048"><td class="memItemLeft" align="right" valign="top">int64_t </td><td class="memItemRight" valign="bottom"><a class="el" href="classimpala_1_1HashTable.html#ae21db224cca645cb112fc27d323e9048">num_hash_collisions_</a></td></tr> |
| <tr class="separator:ae21db224cca645cb112fc27d323e9048"><td class="memSeparator" colspan="2"> </td></tr> |
| <tr class="memitem:afea6437f65ec39ca574fe85afe0992e7"><td class="memItemLeft" align="right" valign="top">int64_t </td><td class="memItemRight" valign="bottom"><a class="el" href="classimpala_1_1HashTable.html#afea6437f65ec39ca574fe85afe0992e7">num_resizes_</a></td></tr> |
| <tr class="memdesc:afea6437f65ec39ca574fe85afe0992e7"><td class="mdescLeft"> </td><td class="mdescRight">How many times this table has resized so far. <a href="#afea6437f65ec39ca574fe85afe0992e7">More...</a><br/></td></tr> |
| <tr class="separator:afea6437f65ec39ca574fe85afe0992e7"><td class="memSeparator" colspan="2"> </td></tr> |
| </table><table class="memberdecls"> |
| <tr class="heading"><td colspan="2"><h2 class="groupheader"><a name="pri-static-attribs"></a> |
| Static Private Attributes</h2></td></tr> |
| <tr class="memitem:a16ecff93c19dfa4090ec393d34385f95"><td class="memItemLeft" align="right" valign="top">static const double </td><td class="memItemRight" valign="bottom"><a class="el" href="classimpala_1_1HashTable.html#a16ecff93c19dfa4090ec393d34385f95">MAX_FILL_FACTOR</a> = 0.75f</td></tr> |
| <tr class="separator:a16ecff93c19dfa4090ec393d34385f95"><td class="memSeparator" colspan="2"> </td></tr> |
| </table><table class="memberdecls"> |
| <tr class="heading"><td colspan="2"><h2 class="groupheader"><a name="friends"></a> |
| Friends</h2></td></tr> |
| <tr class="memitem:a9830fc407400559db7e7783cc10a9394"><td class="memItemLeft" align="right" valign="top">class </td><td class="memItemRight" valign="bottom"><a class="el" href="classimpala_1_1HashTable.html#a9830fc407400559db7e7783cc10a9394">Iterator</a></td></tr> |
| <tr class="separator:a9830fc407400559db7e7783cc10a9394"><td class="memSeparator" colspan="2"> </td></tr> |
| <tr class="memitem:a96d0236d3388688bbf272e9516dc8fda"><td class="memItemLeft" align="right" valign="top">class </td><td class="memItemRight" valign="bottom"><a class="el" href="classimpala_1_1HashTable.html#a96d0236d3388688bbf272e9516dc8fda">HashTableTest</a></td></tr> |
| <tr class="separator:a96d0236d3388688bbf272e9516dc8fda"><td class="memSeparator" colspan="2"> </td></tr> |
| </table> |
| <a name="details" id="details"></a><h2 class="groupheader">Detailed Description</h2> |
| <div class="textblock"><p>The hash table consists of a contiguous array of buckets that contain a pointer to the data, the hash value and three flags: whether this bucket is filled, whether this entry has been matched (used in right and full joins) and whether this entry has duplicates. If there are duplicates, then the data is pointing to the head of a linked list of duplicate nodes that point to the actual data. Note that the duplicate nodes do not contain the hash value, because all the linked nodes have the same hash value, the one in the bucket. The data is either a tuple stream index or a Tuple*. This array of buckets is sparse, we are shooting for up to 3/4 fill factor (75%). The data allocated by the hash table comes from the <a class="el" href="classimpala_1_1BufferedBlockMgr.html">BufferedBlockMgr</a>. </p> |
| |
| <p>Definition at line <a class="el" href="hash-table_8h_source.html#l00281">281</a> of file <a class="el" href="hash-table_8h_source.html">hash-table.h</a>.</p> |
| </div><h2 class="groupheader">Constructor & Destructor Documentation</h2> |
| <a class="anchor" id="af1cccf76b721c82e567a687b5660613d"></a> |
| <div class="memitem"> |
| <div class="memproto"> |
| <table class="memname"> |
| <tr> |
| <td class="memname">HashTable::HashTable </td> |
| <td>(</td> |
| <td class="paramtype"><a class="el" href="classimpala_1_1RuntimeState.html">RuntimeState</a> * </td> |
| <td class="paramname"><em>state</em>, </td> |
| </tr> |
| <tr> |
| <td class="paramkey"></td> |
| <td></td> |
| <td class="paramtype"><a class="el" href="structimpala_1_1BufferedBlockMgr_1_1Client.html">BufferedBlockMgr::Client</a> * </td> |
| <td class="paramname"><em>client</em>, </td> |
| </tr> |
| <tr> |
| <td class="paramkey"></td> |
| <td></td> |
| <td class="paramtype">int </td> |
| <td class="paramname"><em>num_build_tuples</em>, </td> |
| </tr> |
| <tr> |
| <td class="paramkey"></td> |
| <td></td> |
| <td class="paramtype"><a class="el" href="classimpala_1_1BufferedTupleStream.html">BufferedTupleStream</a> * </td> |
| <td class="paramname"><em>tuple_stream</em>, </td> |
| </tr> |
| <tr> |
| <td class="paramkey"></td> |
| <td></td> |
| <td class="paramtype">int64_t </td> |
| <td class="paramname"><em>max_num_buckets</em>, </td> |
| </tr> |
| <tr> |
| <td class="paramkey"></td> |
| <td></td> |
| <td class="paramtype">int64_t </td> |
| <td class="paramname"><em>initial_num_buckets</em> = <code>1024</code> </td> |
| </tr> |
| <tr> |
| <td></td> |
| <td>)</td> |
| <td></td><td></td> |
| </tr> |
| </table> |
| </div><div class="memdoc"> |
| <p>Create a hash table.</p> |
| <ul> |
| <li>client: block mgr client to allocate data pages from.</li> |
| <li>num_build_tuples: number of Tuples in the build tuple row.</li> |
| <li>tuple_stream: the tuple stream which contains the tuple rows index by the hash table. Can be NULL if the rows contain only a single tuple, in which the 'tuple_stream' is unused.</li> |
| <li>max_num_buckets: the maximum number of buckets that can be stored. If we try to grow the number of buckets to a larger number, the inserts will fail. -1, if it unlimited.</li> |
| <li>initial_num_buckets: number of buckets that the hash table should be initialized with. </li> |
| </ul> |
| |
| <p>Definition at line <a class="el" href="hash-table_8cc_source.html#l00192">192</a> of file <a class="el" href="hash-table_8cc_source.html">hash-table.cc</a>.</p> |
| |
| <p>References <a class="el" href="hash-table_8h_source.html#l00602">stores_tuples_</a>.</p> |
| |
| </div> |
| </div> |
| <a class="anchor" id="ae8b96ae30e44e104c678d17d0a686d32"></a> |
| <div class="memitem"> |
| <div class="memproto"> |
| <table class="memname"> |
| <tr> |
| <td class="memname">HashTable::HashTable </td> |
| <td>(</td> |
| <td class="paramtype"><a class="el" href="classimpala_1_1MemPool.html">MemPool</a> * </td> |
| <td class="paramname"><em>pool</em>, </td> |
| </tr> |
| <tr> |
| <td class="paramkey"></td> |
| <td></td> |
| <td class="paramtype"><a class="el" href="classbool.html">bool</a> </td> |
| <td class="paramname"><em>quadratic_probing</em>, </td> |
| </tr> |
| <tr> |
| <td class="paramkey"></td> |
| <td></td> |
| <td class="paramtype">int </td> |
| <td class="paramname"><em>num_buckets</em> </td> |
| </tr> |
| <tr> |
| <td></td> |
| <td>)</td> |
| <td></td><td></td> |
| </tr> |
| </table> |
| </div><div class="memdoc"> |
| <p>Ctor used only for testing. Memory is allocated from the 'pool' instead of the block mgr. </p> |
| |
| <p>Definition at line <a class="el" href="hash-table_8cc_source.html#l00219">219</a> of file <a class="el" href="hash-table_8cc_source.html">hash-table.cc</a>.</p> |
| |
| <p>References <a class="el" href="hash-table_8cc_source.html#l00245">Init()</a>.</p> |
| |
| </div> |
| </div> |
| <h2 class="groupheader">Member Function Documentation</h2> |
| <a class="anchor" id="a9298e0fdd6056ad976cc5d8f38c24e81"></a> |
| <div class="memitem"> |
| <div class="memproto"> |
| <table class="mlabels"> |
| <tr> |
| <td class="mlabels-left"> |
| <table class="memname"> |
| <tr> |
| <td class="memname"><a class="el" href="structimpala_1_1HashTable_1_1DuplicateNode.html">HashTable::DuplicateNode</a> * impala::HashTable::AppendNextNode </td> |
| <td>(</td> |
| <td class="paramtype"><a class="el" href="structimpala_1_1HashTable_1_1Bucket.html">Bucket</a> * </td> |
| <td class="paramname"><em>bucket</em></td><td>)</td> |
| <td></td> |
| </tr> |
| </table> |
| </td> |
| <td class="mlabels-right"> |
| <span class="mlabels"><span class="mlabel">inline</span><span class="mlabel">private</span></span> </td> |
| </tr> |
| </table> |
| </div><div class="memdoc"> |
| <p>Appends the <a class="el" href="structimpala_1_1HashTable_1_1DuplicateNode.html" title="Linked list of entries used for duplicates. ">DuplicateNode</a> pointed by next_node_ to 'bucket' and moves the next_node_ pointer to the next <a class="el" href="structimpala_1_1HashTable_1_1DuplicateNode.html" title="Linked list of entries used for duplicates. ">DuplicateNode</a> in the page, updating the remaining node counter. </p> |
| |
| <p>Definition at line <a class="el" href="hash-table_8inline_8h_source.html#l00175">175</a> of file <a class="el" href="hash-table_8inline_8h_source.html">hash-table.inline.h</a>.</p> |
| |
| <p>References <a class="el" href="structimpala_1_1HashTable_1_1Bucket.html#aef6be21fddf0a939b50561f53398fe09">impala::HashTable::Bucket::bucketData</a>, <a class="el" href="hash-table_8h_source.html#l00324">impala::HashTable::Bucket::duplicates</a>, <a class="el" href="hash-table_8h_source.html#l00614">next_node_</a>, <a class="el" href="hash-table_8h_source.html#l00617">node_remaining_current_page_</a>, and <a class="el" href="hash-table_8h_source.html#l00620">num_duplicate_nodes_</a>.</p> |
| |
| <p>Referenced by <a class="el" href="hash-table_8inline_8h_source.html#l00183">InsertDuplicateNode()</a>.</p> |
| |
| </div> |
| </div> |
| <a class="anchor" id="a98f48e7cfbdb196b9a9e9413f6c7fcff"></a> |
| <div class="memitem"> |
| <div class="memproto"> |
| <table class="mlabels"> |
| <tr> |
| <td class="mlabels-left"> |
| <table class="memname"> |
| <tr> |
| <td class="memname"><a class="el" href="classimpala_1_1HashTable_1_1Iterator.html">HashTable::Iterator</a> impala::HashTable::Begin </td> |
| <td>(</td> |
| <td class="paramtype"><a class="el" href="classimpala_1_1HashTableCtx.html">HashTableCtx</a> * </td> |
| <td class="paramname"><em>ht_ctx</em></td><td>)</td> |
| <td></td> |
| </tr> |
| </table> |
| </td> |
| <td class="mlabels-right"> |
| <span class="mlabels"><span class="mlabel">inline</span></span> </td> |
| </tr> |
| </table> |
| </div><div class="memdoc"> |
| <p>Returns an iterator at the beginning of the hash table. Advancing this iterator will traverse all elements. </p> |
| |
| <p>Definition at line <a class="el" href="hash-table_8inline_8h_source.html#l00128">128</a> of file <a class="el" href="hash-table_8inline_8h_source.html">hash-table.inline.h</a>.</p> |
| |
| <p>References <a class="el" href="hash-table_8h_source.html#l00453">impala::HashTable::Iterator::BUCKET_NOT_FOUND</a>, <a class="el" href="hash-table_8h_source.html#l00517">Iterator</a>, <a class="el" href="hash-table_8inline_8h_source.html#l00150">NextFilledBucket()</a>, and <a class="el" href="hash-table_8h_source.html#l00127">impala::HashTableCtx::row()</a>.</p> |
| |
| <p>Referenced by <a class="el" href="hash-table-test_8cc_source.html#l00095">impala::HashTableTest::FullScan()</a>, and <a class="el" href="hash-table_8cc_source.html#l00293">ResizeBuckets()</a>.</p> |
| |
| </div> |
| </div> |
| <a class="anchor" id="a9ead10df58713f8150ea8c2330820506"></a> |
| <div class="memitem"> |
| <div class="memproto"> |
| <table class="mlabels"> |
| <tr> |
| <td class="mlabels-left"> |
| <table class="memname"> |
| <tr> |
| <td class="memname">int64_t impala::HashTable::byte_size </td> |
| <td>(</td> |
| <td class="paramname"></td><td>)</td> |
| <td> const</td> |
| </tr> |
| </table> |
| </td> |
| <td class="mlabels-right"> |
| <span class="mlabels"><span class="mlabel">inline</span></span> </td> |
| </tr> |
| </table> |
| </div><div class="memdoc"> |
| |
| <p>Returns the number of bytes allocated to the hash table. </p> |
| |
| <p>Definition at line <a class="el" href="hash-table_8h_source.html#l00419">419</a> of file <a class="el" href="hash-table_8h_source.html">hash-table.h</a>.</p> |
| |
| <p>References <a class="el" href="hash-table_8h_source.html#l00611">total_data_page_size_</a>.</p> |
| |
| </div> |
| </div> |
| <a class="anchor" id="a008c8765a5a4c57a17abf299882d79c2"></a> |
| <div class="memitem"> |
| <div class="memproto"> |
| <table class="memname"> |
| <tr> |
| <td class="memname"><a class="el" href="classbool.html">bool</a> HashTable::CheckAndResize </td> |
| <td>(</td> |
| <td class="paramtype"><a class="el" href="classuint64__t.html">uint64_t</a> </td> |
| <td class="paramname"><em>buckets_to_fill</em>, </td> |
| </tr> |
| <tr> |
| <td class="paramkey"></td> |
| <td></td> |
| <td class="paramtype"><a class="el" href="classimpala_1_1HashTableCtx.html">HashTableCtx</a> * </td> |
| <td class="paramname"><em>ht_ctx</em> </td> |
| </tr> |
| <tr> |
| <td></td> |
| <td>)</td> |
| <td></td><td></td> |
| </tr> |
| </table> |
| </div><div class="memdoc"> |
| <p>Calculates the fill factor if 'buckets_to_fill' additional buckets were to be filled and resizes the hash table so that the projected fill factor is below the max fill factor. If it returns true, then it is guaranteed at least 'rows_to_add' rows can be inserted without need to resize. </p> |
| |
| <p>Definition at line <a class="el" href="hash-table_8cc_source.html#l00282">282</a> of file <a class="el" href="hash-table_8cc_source.html">hash-table.cc</a>.</p> |
| |
| <p>References <a class="el" href="hash-table_8h_source.html#l00583">MAX_FILL_FACTOR</a>, <a class="el" href="hash-table_8h_source.html#l00629">num_buckets_</a>, <a class="el" href="hash-table_8h_source.html#l00632">num_filled_buckets_</a>, and <a class="el" href="hash-table_8cc_source.html#l00293">ResizeBuckets()</a>.</p> |
| |
| <p>Referenced by <a class="el" href="hash-table-test_8cc_source.html#l00190">impala::HashTableTest::BasicTest()</a>, <a class="el" href="hash-table-test_8cc_source.html#l00298">impala::HashTableTest::GrowTableTest()</a>, and <a class="el" href="hash-table-test_8cc_source.html#l00247">impala::HashTableTest::ScanTest()</a>.</p> |
| |
| </div> |
| </div> |
| <a class="anchor" id="a849d5e05fa77c04ec11efc6fcf266284"></a> |
| <div class="memitem"> |
| <div class="memproto"> |
| <table class="memname"> |
| <tr> |
| <td class="memname">void HashTable::Close </td> |
| <td>(</td> |
| <td class="paramname"></td><td>)</td> |
| <td></td> |
| </tr> |
| </table> |
| </div><div class="memdoc"> |
| |
| <p>Call to cleanup any resources. Must be called once. </p> |
| |
| <p>Definition at line <a class="el" href="hash-table_8cc_source.html#l00257">257</a> of file <a class="el" href="hash-table_8cc_source.html">hash-table.cc</a>.</p> |
| |
| <p>References <a class="el" href="runtime-state_8h_source.html#l00194">impala::RuntimeState::block_mgr()</a>, <a class="el" href="hash-table_8h_source.html#l00588">block_mgr_client_</a>, <a class="el" href="hash-table_8h_source.html#l00626">buckets_</a>, <a class="el" href="hash-table_8h_source.html#l00608">data_pages_</a>, <a class="el" href="impalad-metrics_8h_source.html#l00126">impala::ImpaladMetrics::HASH_TABLE_TOTAL_BYTES</a>, <a class="el" href="hash-table_8h_source.html#l00629">num_buckets_</a>, <a class="el" href="hash-table_8h_source.html#l00650">num_probes_</a>, <a class="el" href="hash-table_8cc_source.html#l00424">PrintStats()</a>, <a class="el" href="buffered-block-mgr_8cc_source.html#l00354">impala::BufferedBlockMgr::ReleaseMemory()</a>, <a class="el" href="hash-table_8h_source.html#l00585">state_</a>, and <a class="el" href="hash-table_8h_source.html#l00611">total_data_page_size_</a>.</p> |
| |
| <p>Referenced by <a class="el" href="hash-table-test_8cc_source.html#l00190">impala::HashTableTest::BasicTest()</a>, <a class="el" href="hash-table-test_8cc_source.html#l00298">impala::HashTableTest::GrowTableTest()</a>, <a class="el" href="hash-table-test_8cc_source.html#l00352">impala::HashTableTest::InsertFullTest()</a>, <a class="el" href="hash-table-test_8cc_source.html#l00247">impala::HashTableTest::ScanTest()</a>, and <a class="el" href="hash-table-test_8cc_source.html#l00161">impala::HashTableTest::SetupTest()</a>.</p> |
| |
| </div> |
| </div> |
| <a class="anchor" id="ab01f3fe1ea91d152a0ff15540e4fc6f6"></a> |
| <div class="memitem"> |
| <div class="memproto"> |
| <table class="memname"> |
| <tr> |
| <td class="memname">int64_t HashTable::CurrentMemSize </td> |
| <td>(</td> |
| <td class="paramname"></td><td>)</td> |
| <td> const</td> |
| </tr> |
| </table> |
| </div><div class="memdoc"> |
| <p>Returns the memory occupied by the hash table, takes into account the number of duplicates. </p> |
| |
| <p>Definition at line <a class="el" href="hash-table_8cc_source.html#l00278">278</a> of file <a class="el" href="hash-table_8cc_source.html">hash-table.cc</a>.</p> |
| |
| <p>References <a class="el" href="hash-table_8h_source.html#l00629">num_buckets_</a>, and <a class="el" href="hash-table_8h_source.html#l00620">num_duplicate_nodes_</a>.</p> |
| |
| </div> |
| </div> |
| <a class="anchor" id="ae83037529a3f307470860bbeb3e71024"></a> |
| <div class="memitem"> |
| <div class="memproto"> |
| <table class="memname"> |
| <tr> |
| <td class="memname">string HashTable::DebugString </td> |
| <td>(</td> |
| <td class="paramtype"><a class="el" href="classbool.html">bool</a> </td> |
| <td class="paramname"><em>skip_empty</em>, </td> |
| </tr> |
| <tr> |
| <td class="paramkey"></td> |
| <td></td> |
| <td class="paramtype"><a class="el" href="classbool.html">bool</a> </td> |
| <td class="paramname"><em>show_match</em>, </td> |
| </tr> |
| <tr> |
| <td class="paramkey"></td> |
| <td></td> |
| <td class="paramtype">const <a class="el" href="classimpala_1_1RowDescriptor.html">RowDescriptor</a> * </td> |
| <td class="paramname"><em>build_desc</em> </td> |
| </tr> |
| <tr> |
| <td></td> |
| <td>)</td> |
| <td></td><td></td> |
| </tr> |
| </table> |
| </div><div class="memdoc"> |
| <p>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 printed. Otherwise, only the the addresses of the build rows will be printed. </p> |
| |
| <p>Definition at line <a class="el" href="hash-table_8cc_source.html#l00387">387</a> of file <a class="el" href="hash-table_8cc_source.html">hash-table.cc</a>.</p> |
| |
| <p>References <a class="el" href="structimpala_1_1HashTable_1_1Bucket.html#aef6be21fddf0a939b50561f53398fe09">impala::HashTable::Bucket::bucketData</a>, <a class="el" href="hash-table_8h_source.html#l00626">buckets_</a>, <a class="el" href="hash-table_8cc_source.html#l00373">DebugStringTuple()</a>, <a class="el" href="hash-table_8h_source.html#l00324">impala::HashTable::Bucket::duplicates</a>, <a class="el" href="hash-table_8h_source.html#l00300">impala::HashTable::DuplicateNode::htdata</a>, <a class="el" href="hash-table_8h_source.html#l00323">impala::HashTable::Bucket::htdata</a>, <a class="el" href="hash-table_8h_source.html#l00299">impala::HashTable::DuplicateNode::next</a>, and <a class="el" href="hash-table_8h_source.html#l00629">num_buckets_</a>.</p> |
| |
| </div> |
| </div> |
| <a class="anchor" id="a47c85016bff3fd0e9092b378993b4b15"></a> |
| <div class="memitem"> |
| <div class="memproto"> |
| <table class="memname"> |
| <tr> |
| <td class="memname">void HashTable::DebugStringTuple </td> |
| <td>(</td> |
| <td class="paramtype">std::stringstream & </td> |
| <td class="paramname"><em>ss</em>, </td> |
| </tr> |
| <tr> |
| <td class="paramkey"></td> |
| <td></td> |
| <td class="paramtype"><a class="el" href="unionimpala_1_1HashTable_1_1HtData.html">HtData</a> & </td> |
| <td class="paramname"><em>htdata</em>, </td> |
| </tr> |
| <tr> |
| <td class="paramkey"></td> |
| <td></td> |
| <td class="paramtype">const <a class="el" href="classimpala_1_1RowDescriptor.html">RowDescriptor</a> * </td> |
| <td class="paramname"><em>desc</em> </td> |
| </tr> |
| <tr> |
| <td></td> |
| <td>)</td> |
| <td></td><td></td> |
| </tr> |
| </table> |
| </div><div class="memdoc"> |
| |
| <p>Print the content of a bucket or node. </p> |
| |
| <p>Definition at line <a class="el" href="hash-table_8cc_source.html#l00373">373</a> of file <a class="el" href="hash-table_8cc_source.html">hash-table.cc</a>.</p> |
| |
| <p>References <a class="el" href="buffered-tuple-stream_8h_source.html#l00129">impala::BufferedTupleStream::RowIdx::block()</a>, <a class="el" href="hash-table_8inline_8h_source.html#l00210">GetRow()</a>, <a class="el" href="buffered-tuple-stream_8h_source.html#l00137">impala::BufferedTupleStream::RowIdx::idx()</a>, <a class="el" href="hash-table_8h_source.html#l00286">impala::HashTable::HtData::idx</a>, <a class="el" href="hash-table_8h_source.html#l00640">num_build_tuples_</a>, <a class="el" href="buffered-tuple-stream_8h_source.html#l00133">impala::BufferedTupleStream::RowIdx::offset()</a>, <a class="el" href="debug-util_8cc_source.html#l00192">impala::PrintRow()</a>, <a class="el" href="hash-table_8h_source.html#l00602">stores_tuples_</a>, and <a class="el" href="hash-table_8h_source.html#l00287">impala::HashTable::HtData::tuple</a>.</p> |
| |
| <p>Referenced by <a class="el" href="hash-table_8cc_source.html#l00387">DebugString()</a>.</p> |
| |
| </div> |
| </div> |
| <a class="anchor" id="a4a5e511b2e7945673ce5a0bc6319b55f"></a> |
| <div class="memitem"> |
| <div class="memproto"> |
| <table class="mlabels"> |
| <tr> |
| <td class="mlabels-left"> |
| <table class="memname"> |
| <tr> |
| <td class="memname">int64_t impala::HashTable::EmptyBuckets </td> |
| <td>(</td> |
| <td class="paramname"></td><td>)</td> |
| <td> const</td> |
| </tr> |
| </table> |
| </td> |
| <td class="mlabels-right"> |
| <span class="mlabels"><span class="mlabel">inline</span></span> </td> |
| </tr> |
| </table> |
| </div><div class="memdoc"> |
| |
| <p>Returns the number of empty buckets. </p> |
| |
| <p>Definition at line <a class="el" href="hash-table_8h_source.html#l00385">385</a> of file <a class="el" href="hash-table_8h_source.html">hash-table.h</a>.</p> |
| |
| <p>References <a class="el" href="hash-table_8h_source.html#l00629">num_buckets_</a>, and <a class="el" href="hash-table_8h_source.html#l00632">num_filled_buckets_</a>.</p> |
| |
| <p>Referenced by <a class="el" href="hash-table-test_8cc_source.html#l00352">impala::HashTableTest::InsertFullTest()</a>.</p> |
| |
| </div> |
| </div> |
| <a class="anchor" id="ac62ebb8f6c388dff042794e69de596a9"></a> |
| <div class="memitem"> |
| <div class="memproto"> |
| <table class="mlabels"> |
| <tr> |
| <td class="mlabels-left"> |
| <table class="memname"> |
| <tr> |
| <td class="memname"><a class="el" href="classimpala_1_1HashTable_1_1Iterator.html">Iterator</a> impala::HashTable::End </td> |
| <td>(</td> |
| <td class="paramname"></td><td>)</td> |
| <td></td> |
| </tr> |
| </table> |
| </td> |
| <td class="mlabels-right"> |
| <span class="mlabels"><span class="mlabel">inline</span></span> </td> |
| </tr> |
| </table> |
| </div><div class="memdoc"> |
| |
| <p>Return end marker. </p> |
| |
| <p>Definition at line <a class="el" href="hash-table_8h_source.html#l00434">434</a> of file <a class="el" href="hash-table_8h_source.html">hash-table.h</a>.</p> |
| |
| <p>References <a class="el" href="hash-table_8h_source.html#l00517">Iterator</a>.</p> |
| |
| <p>Referenced by <a class="el" href="hash-table_8inline_8h_source.html#l00117">Find()</a>.</p> |
| |
| </div> |
| </div> |
| <a class="anchor" id="a5cc6716b7f775323d6c6f32cacbb23b5"></a> |
| <div class="memitem"> |
| <div class="memproto"> |
| <table class="mlabels"> |
| <tr> |
| <td class="mlabels-left"> |
| <table class="memname"> |
| <tr> |
| <td class="memname">static int64_t impala::HashTable::EstimateNumBuckets </td> |
| <td>(</td> |
| <td class="paramtype">int64_t </td> |
| <td class="paramname"><em>num_rows</em></td><td>)</td> |
| <td></td> |
| </tr> |
| </table> |
| </td> |
| <td class="mlabels-right"> |
| <span class="mlabels"><span class="mlabel">inline</span><span class="mlabel">static</span></span> </td> |
| </tr> |
| </table> |
| </div><div class="memdoc"> |
| <p>Returns an estimate of the number of bytes needed to build the hash table structure for 'num_rows'. To do that, it estimates the number of buckets, rounded up to a power of two, and also assumes that there are no duplicates. </p> |
| <p>Assume max 66% fill factor and no duplicates. </p> |
| |
| <p>Definition at line <a class="el" href="hash-table_8h_source.html#l00398">398</a> of file <a class="el" href="hash-table_8h_source.html">hash-table.h</a>.</p> |
| |
| <p>References <a class="el" href="bit-util_8h_source.html#l00050">impala::BitUtil::NextPowerOfTwo()</a>.</p> |
| |
| <p>Referenced by <a class="el" href="partitioned-hash-join-node_8cc_source.html#l00301">impala::PartitionedHashJoinNode::Partition::BuildHashTableInternal()</a>, and <a class="el" href="hash-table_8h_source.html#l00402">EstimateSize()</a>.</p> |
| |
| </div> |
| </div> |
| <a class="anchor" id="ab4f7267cccc84203f4891ed1e574b644"></a> |
| <div class="memitem"> |
| <div class="memproto"> |
| <table class="mlabels"> |
| <tr> |
| <td class="mlabels-left"> |
| <table class="memname"> |
| <tr> |
| <td class="memname">static int64_t impala::HashTable::EstimateSize </td> |
| <td>(</td> |
| <td class="paramtype">int64_t </td> |
| <td class="paramname"><em>num_rows</em></td><td>)</td> |
| <td></td> |
| </tr> |
| </table> |
| </td> |
| <td class="mlabels-right"> |
| <span class="mlabels"><span class="mlabel">inline</span><span class="mlabel">static</span></span> </td> |
| </tr> |
| </table> |
| </div><div class="memdoc"> |
| |
| <p>Definition at line <a class="el" href="hash-table_8h_source.html#l00402">402</a> of file <a class="el" href="hash-table_8h_source.html">hash-table.h</a>.</p> |
| |
| <p>References <a class="el" href="hash-table_8h_source.html#l00398">EstimateNumBuckets()</a>, and <a class="el" href="hash-table_8h_source.html#l00388">num_buckets()</a>.</p> |
| |
| <p>Referenced by <a class="el" href="partitioned-hash-join-node_8cc_source.html#l00239">impala::PartitionedHashJoinNode::Partition::EstimatedInMemSize()</a>.</p> |
| |
| </div> |
| </div> |
| <a class="anchor" id="ac128e2d41168cc9e08b40c34e1a29bc3"></a> |
| <div class="memitem"> |
| <div class="memproto"> |
| <table class="mlabels"> |
| <tr> |
| <td class="mlabels-left"> |
| <table class="memname"> |
| <tr> |
| <td class="memname"><a class="el" href="classimpala_1_1HashTable_1_1Iterator.html">HashTable::Iterator</a> impala::HashTable::Find </td> |
| <td>(</td> |
| <td class="paramtype"><a class="el" href="classimpala_1_1HashTableCtx.html">HashTableCtx</a> * </td> |
| <td class="paramname"><em>ht_ctx</em>, </td> |
| </tr> |
| <tr> |
| <td class="paramkey"></td> |
| <td></td> |
| <td class="paramtype">uint32_t </td> |
| <td class="paramname"><em>hash</em> </td> |
| </tr> |
| <tr> |
| <td></td> |
| <td>)</td> |
| <td></td><td></td> |
| </tr> |
| </table> |
| </td> |
| <td class="mlabels-right"> |
| <span class="mlabels"><span class="mlabel">inline</span></span> </td> |
| </tr> |
| </table> |
| </div><div class="memdoc"> |
| <p>Returns an iterator to the bucket matching the last row evaluated in 'ht_ctx'. Returns <a class="el" href="classimpala_1_1HashTable.html#ac62ebb8f6c388dff042794e69de596a9" title="Return end marker. ">HashTable::End()</a> if no match is found. The iterator can be iterated until <a class="el" href="classimpala_1_1HashTable.html#ac62ebb8f6c388dff042794e69de596a9" title="Return end marker. ">HashTable::End()</a> to find all the matching rows. Advancing the returned iterator will go to the next matching row. The matching rows do not need to be evaluated since all the nodes of a bucket are duplicates. One scan can be in progress for each 'ht_ctx'. Used during the probe phase of hash joins. </p> |
| |
| <p>Definition at line <a class="el" href="hash-table_8inline_8h_source.html#l00117">117</a> of file <a class="el" href="hash-table_8inline_8h_source.html">hash-table.inline.h</a>.</p> |
| |
| <p>References <a class="el" href="structimpala_1_1HashTable_1_1Bucket.html#aef6be21fddf0a939b50561f53398fe09">impala::HashTable::Bucket::bucketData</a>, <a class="el" href="hash-table_8h_source.html#l00626">buckets_</a>, <a class="el" href="hash-table_8h_source.html#l00324">impala::HashTable::Bucket::duplicates</a>, <a class="el" href="hash-table_8h_source.html#l00434">End()</a>, <a class="el" href="url-parser_8cc_source.html#l00041">impala::hash</a>, <a class="el" href="hash-table_8h_source.html#l00517">Iterator</a>, <a class="el" href="hash-table_8h_source.html#l00629">num_buckets_</a>, <a class="el" href="hash-table_8h_source.html#l00650">num_probes_</a>, <a class="el" href="hash-table_8inline_8h_source.html#l00037">Probe()</a>, and <a class="el" href="hash-table_8h_source.html#l00127">impala::HashTableCtx::row()</a>.</p> |
| |
| <p>Referenced by <a class="el" href="hash-table-test_8cc_source.html#l00298">impala::HashTableTest::GrowTableTest()</a>, <a class="el" href="hash-table-test_8cc_source.html#l00352">impala::HashTableTest::InsertFullTest()</a>, <a class="el" href="hash-table-test_8cc_source.html#l00126">impala::HashTableTest::ProbeTest()</a>, and <a class="el" href="partitioned-hash-join-node-ir_8cc_source.html#l00040">impala::PartitionedHashJoinNode::ProcessProbeBatch()</a>.</p> |
| |
| </div> |
| </div> |
| <a class="anchor" id="ac03658dce51b9f2582daebec0646e80a"></a> |
| <div class="memitem"> |
| <div class="memproto"> |
| <table class="mlabels"> |
| <tr> |
| <td class="mlabels-left"> |
| <table class="memname"> |
| <tr> |
| <td class="memname"><a class="el" href="classimpala_1_1HashTable_1_1Iterator.html">HashTable::Iterator</a> impala::HashTable::FirstUnmatched </td> |
| <td>(</td> |
| <td class="paramtype"><a class="el" href="classimpala_1_1HashTableCtx.html">HashTableCtx</a> * </td> |
| <td class="paramname"><em>ctx</em></td><td>)</td> |
| <td></td> |
| </tr> |
| </table> |
| </td> |
| <td class="mlabels-right"> |
| <span class="mlabels"><span class="mlabel">inline</span></span> </td> |
| </tr> |
| </table> |
| </div><div class="memdoc"> |
| <p>Return an iterator pointing to the first element (<a class="el" href="structimpala_1_1HashTable_1_1Bucket.html">Bucket</a> or <a class="el" href="structimpala_1_1HashTable_1_1DuplicateNode.html" title="Linked list of entries used for duplicates. ">DuplicateNode</a>, if the bucket has duplicates) in the hash table that does not have its matched flag set. Used in right joins and full-outer joins. </p> |
| |
| <p>Definition at line <a class="el" href="hash-table_8inline_8h_source.html#l00135">135</a> of file <a class="el" href="hash-table_8inline_8h_source.html">hash-table.inline.h</a>.</p> |
| |
| <p>References <a class="el" href="hash-table_8h_source.html#l00453">impala::HashTable::Iterator::BUCKET_NOT_FOUND</a>, <a class="el" href="hash-table_8h_source.html#l00626">buckets_</a>, <a class="el" href="hash-table_8inline_8h_source.html#l00150">NextFilledBucket()</a>, and <a class="el" href="hash-table_8h_source.html#l00127">impala::HashTableCtx::row()</a>.</p> |
| |
| </div> |
| </div> |
| <a class="anchor" id="aba3b5b944609bf0d2debbfaffb8ed767"></a> |
| <div class="memitem"> |
| <div class="memproto"> |
| <table class="mlabels"> |
| <tr> |
| <td class="mlabels-left"> |
| <table class="memname"> |
| <tr> |
| <td class="memname"><a class="el" href="classimpala_1_1TupleRow.html">TupleRow</a> * impala::HashTable::GetRow </td> |
| <td>(</td> |
| <td class="paramtype"><a class="el" href="unionimpala_1_1HashTable_1_1HtData.html">HtData</a> & </td> |
| <td class="paramname"><em>htdata</em>, </td> |
| </tr> |
| <tr> |
| <td class="paramkey"></td> |
| <td></td> |
| <td class="paramtype"><a class="el" href="classimpala_1_1TupleRow.html">TupleRow</a> * </td> |
| <td class="paramname"><em>row</em> </td> |
| </tr> |
| <tr> |
| <td></td> |
| <td>)</td> |
| <td></td><td> const</td> |
| </tr> |
| </table> |
| </td> |
| <td class="mlabels-right"> |
| <span class="mlabels"><span class="mlabel">inline</span><span class="mlabel">private</span></span> </td> |
| </tr> |
| </table> |
| </div><div class="memdoc"> |
| |
| <p>Return the <a class="el" href="classimpala_1_1TupleRow.html">TupleRow</a> pointed by 'htdata'. </p> |
| |
| <p>Definition at line <a class="el" href="hash-table_8inline_8h_source.html#l00210">210</a> of file <a class="el" href="hash-table_8inline_8h_source.html">hash-table.inline.h</a>.</p> |
| |
| <p>References <a class="el" href="buffered-tuple-stream_8inline_8h_source.html#l00049">impala::BufferedTupleStream::GetTupleRow()</a>, <a class="el" href="hash-table_8h_source.html#l00286">impala::HashTable::HtData::idx</a>, <a class="el" href="hash-table_8h_source.html#l00602">stores_tuples_</a>, <a class="el" href="hash-table_8h_source.html#l00287">impala::HashTable::HtData::tuple</a>, and <a class="el" href="hash-table_8h_source.html#l00593">tuple_stream_</a>.</p> |
| |
| <p>Referenced by <a class="el" href="hash-table_8cc_source.html#l00373">DebugStringTuple()</a>, <a class="el" href="hash-table_8inline_8h_source.html#l00230">impala::HashTable::Iterator::GetRow()</a>, <a class="el" href="hash-table_8inline_8h_source.html#l00219">GetRow()</a>, and <a class="el" href="hash-table_8inline_8h_source.html#l00037">Probe()</a>.</p> |
| |
| </div> |
| </div> |
| <a class="anchor" id="a65e7a1bd56c401b2f3a7d0a4509b9b7e"></a> |
| <div class="memitem"> |
| <div class="memproto"> |
| <table class="mlabels"> |
| <tr> |
| <td class="mlabels-left"> |
| <table class="memname"> |
| <tr> |
| <td class="memname"><a class="el" href="classimpala_1_1TupleRow.html">TupleRow</a> * impala::HashTable::GetRow </td> |
| <td>(</td> |
| <td class="paramtype"><a class="el" href="structimpala_1_1HashTable_1_1Bucket.html">Bucket</a> * </td> |
| <td class="paramname"><em>bucket</em>, </td> |
| </tr> |
| <tr> |
| <td class="paramkey"></td> |
| <td></td> |
| <td class="paramtype"><a class="el" href="classimpala_1_1TupleRow.html">TupleRow</a> * </td> |
| <td class="paramname"><em>row</em> </td> |
| </tr> |
| <tr> |
| <td></td> |
| <td>)</td> |
| <td></td><td> const</td> |
| </tr> |
| </table> |
| </td> |
| <td class="mlabels-right"> |
| <span class="mlabels"><span class="mlabel">inline</span><span class="mlabel">private</span></span> </td> |
| </tr> |
| </table> |
| </div><div class="memdoc"> |
| <p>Returns the <a class="el" href="classimpala_1_1TupleRow.html">TupleRow</a> of the pointed 'bucket'. In case of duplicates, it returns the content of the first chained duplicate node of the bucket. </p> |
| |
| <p>Definition at line <a class="el" href="hash-table_8inline_8h_source.html#l00219">219</a> of file <a class="el" href="hash-table_8inline_8h_source.html">hash-table.inline.h</a>.</p> |
| |
| <p>References <a class="el" href="structimpala_1_1HashTable_1_1Bucket.html#aef6be21fddf0a939b50561f53398fe09">impala::HashTable::Bucket::bucketData</a>, <a class="el" href="hash-table_8h_source.html#l00324">impala::HashTable::Bucket::duplicates</a>, <a class="el" href="hash-table_8inline_8h_source.html#l00210">GetRow()</a>, <a class="el" href="hash-table_8h_source.html#l00315">impala::HashTable::Bucket::hasDuplicates</a>, <a class="el" href="hash-table_8h_source.html#l00300">impala::HashTable::DuplicateNode::htdata</a>, <a class="el" href="hash-table_8h_source.html#l00323">impala::HashTable::Bucket::htdata</a>, and <a class="el" href="compiler-util_8h_source.html#l00033">UNLIKELY</a>.</p> |
| |
| </div> |
| </div> |
| <a class="anchor" id="aa7f625824191cf1eb85af0d4c79cd255"></a> |
| <div class="memitem"> |
| <div class="memproto"> |
| <table class="mlabels"> |
| <tr> |
| <td class="mlabels-left"> |
| <table class="memname"> |
| <tr> |
| <td class="memname"><a class="el" href="classbool.html">bool</a> HashTable::GrowNodeArray </td> |
| <td>(</td> |
| <td class="paramname"></td><td>)</td> |
| <td></td> |
| </tr> |
| </table> |
| </td> |
| <td class="mlabels-right"> |
| <span class="mlabels"><span class="mlabel">private</span></span> </td> |
| </tr> |
| </table> |
| </div><div class="memdoc"> |
| |
| <p>Grow the node array. Returns false on OOM. </p> |
| |
| <p>Definition at line <a class="el" href="hash-table_8cc_source.html#l00345">345</a> of file <a class="el" href="hash-table_8cc_source.html">hash-table.cc</a>.</p> |
| |
| <p>References <a class="el" href="mem-pool_8h_source.html#l00092">impala::MemPool::Allocate()</a>, <a class="el" href="buffered-block-mgr_8h_source.html#l00160">impala::BufferedBlockMgr::Block::Allocate()</a>, <a class="el" href="runtime-state_8h_source.html#l00194">impala::RuntimeState::block_mgr()</a>, <a class="el" href="hash-table_8h_source.html#l00588">block_mgr_client_</a>, <a class="el" href="hash-table_8h_source.html#l00596">data_page_pool_</a>, <a class="el" href="hash-table_8h_source.html#l00608">data_pages_</a>, <a class="el" href="buffered-block-mgr_8cc_source.html#l00382">impala::BufferedBlockMgr::GetNewBlock()</a>, <a class="el" href="impalad-metrics_8h_source.html#l00126">impala::ImpaladMetrics::HASH_TABLE_TOTAL_BYTES</a>, <a class="el" href="hash-table_8cc_source.html#l00080">INITIAL_DATA_PAGE_SIZES</a>, <a class="el" href="mem-tracker_8h_source.html#l00257">impala::MemTracker::LimitExceeded()</a>, <a class="el" href="buffered-block-mgr_8h_source.html#l00386">impala::BufferedBlockMgr::max_block_size()</a>, <a class="el" href="mem-pool_8h_source.html#l00151">impala::MemPool::mem_tracker()</a>, <a class="el" href="hash-table_8h_source.html#l00614">next_node_</a>, <a class="el" href="hash-table_8h_source.html#l00617">node_remaining_current_page_</a>, <a class="el" href="hash-table_8cc_source.html#l00081">NUM_SMALL_DATA_PAGES</a>, <a class="el" href="status_8h_source.html#l00172">impala::Status::ok()</a>, <a class="el" href="hash-table_8h_source.html#l00585">state_</a>, <a class="el" href="hash-table_8cc_source.html#l00040">TEST_PAGE_SIZE</a>, and <a class="el" href="hash-table_8h_source.html#l00611">total_data_page_size_</a>.</p> |
| |
| <p>Referenced by <a class="el" href="hash-table_8cc_source.html#l00245">Init()</a>, and <a class="el" href="hash-table_8inline_8h_source.html#l00183">InsertDuplicateNode()</a>.</p> |
| |
| </div> |
| </div> |
| <a class="anchor" id="aab2de3f4ada5cdf02366f71e763c967d"></a> |
| <div class="memitem"> |
| <div class="memproto"> |
| <table class="mlabels"> |
| <tr> |
| <td class="mlabels-left"> |
| <table class="memname"> |
| <tr> |
| <td class="memname"><a class="el" href="classbool.html">bool</a> impala::HashTable::HasMatches </td> |
| <td>(</td> |
| <td class="paramname"></td><td>)</td> |
| <td> const</td> |
| </tr> |
| </table> |
| </td> |
| <td class="mlabels-right"> |
| <span class="mlabels"><span class="mlabel">inline</span></span> </td> |
| </tr> |
| </table> |
| </div><div class="memdoc"> |
| |
| <p>Return true if there was a least one match. </p> |
| |
| <p>Definition at line <a class="el" href="hash-table_8h_source.html#l00431">431</a> of file <a class="el" href="hash-table_8h_source.html">hash-table.h</a>.</p> |
| |
| <p>References <a class="el" href="hash-table_8h_source.html#l00645">has_matches_</a>.</p> |
| |
| </div> |
| </div> |
| <a class="anchor" id="a25f62c459962b594afd0922f71a50433"></a> |
| <div class="memitem"> |
| <div class="memproto"> |
| <table class="memname"> |
| <tr> |
| <td class="memname"><a class="el" href="classbool.html">bool</a> HashTable::Init </td> |
| <td>(</td> |
| <td class="paramname"></td><td>)</td> |
| <td></td> |
| </tr> |
| </table> |
| </div><div class="memdoc"> |
| |
| <p>Allocates the initial bucket structure. Returns false if OOM. </p> |
| |
| <p>Definition at line <a class="el" href="hash-table_8cc_source.html#l00245">245</a> of file <a class="el" href="hash-table_8cc_source.html">hash-table.cc</a>.</p> |
| |
| <p>References <a class="el" href="runtime-state_8h_source.html#l00194">impala::RuntimeState::block_mgr()</a>, <a class="el" href="hash-table_8h_source.html#l00588">block_mgr_client_</a>, <a class="el" href="hash-table_8h_source.html#l00626">buckets_</a>, <a class="el" href="buffered-block-mgr_8cc_source.html#l00278">impala::BufferedBlockMgr::ConsumeMemory()</a>, <a class="el" href="hash-table_8cc_source.html#l00345">GrowNodeArray()</a>, <a class="el" href="hash-table_8h_source.html#l00629">num_buckets_</a>, and <a class="el" href="hash-table_8h_source.html#l00585">state_</a>.</p> |
| |
| <p>Referenced by <a class="el" href="hash-table_8cc_source.html#l00219">HashTable()</a>.</p> |
| |
| </div> |
| </div> |
| <a class="anchor" id="a60e5c8ae0744eb588bfbb8ae98bbeaf0"></a> |
| <div class="memitem"> |
| <div class="memproto"> |
| <table class="mlabels"> |
| <tr> |
| <td class="mlabels-left"> |
| <table class="memname"> |
| <tr> |
| <td class="memname"><a class="el" href="classbool.html">bool</a> impala::HashTable::Insert </td> |
| <td>(</td> |
| <td class="paramtype"><a class="el" href="classimpala_1_1HashTableCtx.html">HashTableCtx</a> * </td> |
| <td class="paramname"><em>ht_ctx</em>, </td> |
| </tr> |
| <tr> |
| <td class="paramkey"></td> |
| <td></td> |
| <td class="paramtype">const <a class="el" href="structimpala_1_1BufferedTupleStream_1_1RowIdx.html">BufferedTupleStream::RowIdx</a> & </td> |
| <td class="paramname"><em>idx</em>, </td> |
| </tr> |
| <tr> |
| <td class="paramkey"></td> |
| <td></td> |
| <td class="paramtype"><a class="el" href="classimpala_1_1TupleRow.html">TupleRow</a> * </td> |
| <td class="paramname"><em>row</em>, </td> |
| </tr> |
| <tr> |
| <td class="paramkey"></td> |
| <td></td> |
| <td class="paramtype">uint32_t </td> |
| <td class="paramname"><em>hash</em> </td> |
| </tr> |
| <tr> |
| <td></td> |
| <td>)</td> |
| <td></td><td></td> |
| </tr> |
| </table> |
| </td> |
| <td class="mlabels-right"> |
| <span class="mlabels"><span class="mlabel">inline</span></span> </td> |
| </tr> |
| </table> |
| </div><div class="memdoc"> |
| <p>Inserts the row to the hash table. Returns true if the insertion was successful. 'idx' is the index into tuple_stream_ for this row. If the row contains more than one tuple, the 'idx' is stored instead of the 'row'. The 'row' is not copied by the hash table and the caller must guarantee it stays in memory. This will not grow the hash table. In the case that there is a need to insert a duplicate node, instead of filling a new bucket, and there is not enough memory to insert a duplicate node, the insert fails and this function returns false. Used during the build phase of hash joins. </p> |
| |
| <p>Definition at line <a class="el" href="hash-table_8inline_8h_source.html#l00094">94</a> of file <a class="el" href="hash-table_8inline_8h_source.html">hash-table.inline.h</a>.</p> |
| |
| <p>References <a class="el" href="tuple-row_8h_source.html#l00030">impala::TupleRow::GetTuple()</a>, <a class="el" href="url-parser_8cc_source.html#l00041">impala::hash</a>, <a class="el" href="gen__ir__descriptions_8py_source.html#l00215">gen_ir_descriptions::idx</a>, <a class="el" href="hash-table_8inline_8h_source.html#l00077">InsertInternal()</a>, <a class="el" href="compiler-util_8h_source.html#l00032">LIKELY</a>, and <a class="el" href="hash-table_8h_source.html#l00602">stores_tuples_</a>.</p> |
| |
| <p>Referenced by <a class="el" href="hash-table-test_8cc_source.html#l00190">impala::HashTableTest::BasicTest()</a>, <a class="el" href="hash-table-test_8cc_source.html#l00298">impala::HashTableTest::GrowTableTest()</a>, <a class="el" href="hash-table-test_8cc_source.html#l00352">impala::HashTableTest::InsertFullTest()</a>, and <a class="el" href="hash-table-test_8cc_source.html#l00247">impala::HashTableTest::ScanTest()</a>.</p> |
| |
| </div> |
| </div> |
| <a class="anchor" id="a055d0c676428583f876058dcfbfb15a4"></a> |
| <div class="memitem"> |
| <div class="memproto"> |
| <table class="mlabels"> |
| <tr> |
| <td class="mlabels-left"> |
| <table class="memname"> |
| <tr> |
| <td class="memname"><a class="el" href="classbool.html">bool</a> impala::HashTable::Insert </td> |
| <td>(</td> |
| <td class="paramtype"><a class="el" href="classimpala_1_1HashTableCtx.html">HashTableCtx</a> * </td> |
| <td class="paramname"><em>ht_ctx</em>, </td> |
| </tr> |
| <tr> |
| <td class="paramkey"></td> |
| <td></td> |
| <td class="paramtype"><a class="el" href="classimpala_1_1Tuple.html">Tuple</a> * </td> |
| <td class="paramname"><em>tuple</em>, </td> |
| </tr> |
| <tr> |
| <td class="paramkey"></td> |
| <td></td> |
| <td class="paramtype">uint32_t </td> |
| <td class="paramname"><em>hash</em> </td> |
| </tr> |
| <tr> |
| <td></td> |
| <td>)</td> |
| <td></td><td></td> |
| </tr> |
| </table> |
| </td> |
| <td class="mlabels-right"> |
| <span class="mlabels"><span class="mlabel">inline</span></span> </td> |
| </tr> |
| </table> |
| </div><div class="memdoc"> |
| <p>Same as <a class="el" href="classimpala_1_1HashTable.html#a60e5c8ae0744eb588bfbb8ae98bbeaf0">Insert()</a> but for inserting a single <a class="el" href="classimpala_1_1Tuple.html" title="A tuple with 0 materialised slots is represented as NULL. ">Tuple</a>. The 'tuple' is not copied by the hash table and the caller must guarantee it stays in memory. </p> |
| |
| <p>Definition at line <a class="el" href="hash-table_8inline_8h_source.html#l00106">106</a> of file <a class="el" href="hash-table_8inline_8h_source.html">hash-table.inline.h</a>.</p> |
| |
| <p>References <a class="el" href="hash-table_8inline_8h_source.html#l00077">InsertInternal()</a>, <a class="el" href="compiler-util_8h_source.html#l00032">LIKELY</a>, <a class="el" href="hash-table_8h_source.html#l00602">stores_tuples_</a>, and <a class="el" href="hash-table_8h_source.html#l00287">impala::HashTable::HtData::tuple</a>.</p> |
| |
| </div> |
| </div> |
| <a class="anchor" id="a4664c5c1d82ab068f7005a2c830910e4"></a> |
| <div class="memitem"> |
| <div class="memproto"> |
| <table class="mlabels"> |
| <tr> |
| <td class="mlabels-left"> |
| <table class="memname"> |
| <tr> |
| <td class="memname"><a class="el" href="structimpala_1_1HashTable_1_1DuplicateNode.html">HashTable::DuplicateNode</a> * impala::HashTable::InsertDuplicateNode </td> |
| <td>(</td> |
| <td class="paramtype">int64_t </td> |
| <td class="paramname"><em>bucket_idx</em></td><td>)</td> |
| <td></td> |
| </tr> |
| </table> |
| </td> |
| <td class="mlabels-right"> |
| <span class="mlabels"><span class="mlabel">inline</span><span class="mlabel">private</span></span> </td> |
| </tr> |
| </table> |
| </div><div class="memdoc"> |
| <p>Creates a new <a class="el" href="structimpala_1_1HashTable_1_1DuplicateNode.html" title="Linked list of entries used for duplicates. ">DuplicateNode</a> for a entry and chains it to the bucket with index 'bucket_idx'. The duplicate nodes of a bucket are chained as a linked list. This places the new duplicate node at the beginning of the list. If this is the first duplicate entry inserted in this bucket, then the entry already contained by the bucket is converted to a <a class="el" href="structimpala_1_1HashTable_1_1DuplicateNode.html" title="Linked list of entries used for duplicates. ">DuplicateNode</a>. That is, the contents of 'data' of the bucket are copied to a <a class="el" href="structimpala_1_1HashTable_1_1DuplicateNode.html" title="Linked list of entries used for duplicates. ">DuplicateNode</a> and 'data' is updated to pointing to a <a class="el" href="structimpala_1_1HashTable_1_1DuplicateNode.html" title="Linked list of entries used for duplicates. ">DuplicateNode</a>. Returns NULL if the node array could not grow, i.e. there was not enough memory to allocate a new <a class="el" href="structimpala_1_1HashTable_1_1DuplicateNode.html" title="Linked list of entries used for duplicates. ">DuplicateNode</a>. </p> |
| |
| <p>Definition at line <a class="el" href="hash-table_8inline_8h_source.html#l00183">183</a> of file <a class="el" href="hash-table_8inline_8h_source.html">hash-table.inline.h</a>.</p> |
| |
| <p>References <a class="el" href="hash-table_8inline_8h_source.html#l00175">AppendNextNode()</a>, <a class="el" href="structimpala_1_1HashTable_1_1Bucket.html#aef6be21fddf0a939b50561f53398fe09">impala::HashTable::Bucket::bucketData</a>, <a class="el" href="hash-table_8h_source.html#l00626">buckets_</a>, <a class="el" href="hash-table_8h_source.html#l00324">impala::HashTable::Bucket::duplicates</a>, <a class="el" href="hash-table_8h_source.html#l00305">impala::HashTable::Bucket::filled</a>, <a class="el" href="hash-table_8cc_source.html#l00345">GrowNodeArray()</a>, <a class="el" href="hash-table_8h_source.html#l00315">impala::HashTable::Bucket::hasDuplicates</a>, <a class="el" href="hash-table_8h_source.html#l00300">impala::HashTable::DuplicateNode::htdata</a>, <a class="el" href="hash-table_8h_source.html#l00323">impala::HashTable::Bucket::htdata</a>, <a class="el" href="hash-table_8h_source.html#l00286">impala::HashTable::HtData::idx</a>, <a class="el" href="hash-table_8h_source.html#l00297">impala::HashTable::DuplicateNode::matched</a>, <a class="el" href="hash-table_8h_source.html#l00311">impala::HashTable::Bucket::matched</a>, <a class="el" href="hash-table_8h_source.html#l00299">impala::HashTable::DuplicateNode::next</a>, <a class="el" href="hash-table_8h_source.html#l00614">next_node_</a>, <a class="el" href="hash-table_8h_source.html#l00629">num_buckets_</a>, <a class="el" href="hash-table_8h_source.html#l00636">num_buckets_with_duplicates_</a>, and <a class="el" href="compiler-util_8h_source.html#l00033">UNLIKELY</a>.</p> |
| |
| <p>Referenced by <a class="el" href="hash-table_8inline_8h_source.html#l00077">InsertInternal()</a>.</p> |
| |
| </div> |
| </div> |
| <a class="anchor" id="a6695a051bc94f74a1d277254d6523f29"></a> |
| <div class="memitem"> |
| <div class="memproto"> |
| <table class="mlabels"> |
| <tr> |
| <td class="mlabels-left"> |
| <table class="memname"> |
| <tr> |
| <td class="memname"><a class="el" href="unionimpala_1_1HashTable_1_1HtData.html">HashTable::HtData</a> * impala::HashTable::InsertInternal </td> |
| <td>(</td> |
| <td class="paramtype"><a class="el" href="classimpala_1_1HashTableCtx.html">HashTableCtx</a> * </td> |
| <td class="paramname"><em>ht_ctx</em>, </td> |
| </tr> |
| <tr> |
| <td class="paramkey"></td> |
| <td></td> |
| <td class="paramtype">uint32_t </td> |
| <td class="paramname"><em>hash</em> </td> |
| </tr> |
| <tr> |
| <td></td> |
| <td>)</td> |
| <td></td><td></td> |
| </tr> |
| </table> |
| </td> |
| <td class="mlabels-right"> |
| <span class="mlabels"><span class="mlabel">inline</span><span class="mlabel">private</span></span> </td> |
| </tr> |
| </table> |
| </div><div class="memdoc"> |
| <p>Performs the insert logic. Returns the HtData* of the bucket or duplicate node where the data should be inserted. Returns NULL if the insert was not successful. </p> |
| |
| <p>Definition at line <a class="el" href="hash-table_8inline_8h_source.html#l00077">77</a> of file <a class="el" href="hash-table_8inline_8h_source.html">hash-table.inline.h</a>.</p> |
| |
| <p>References <a class="el" href="hash-table_8h_source.html#l00453">impala::HashTable::Iterator::BUCKET_NOT_FOUND</a>, <a class="el" href="structimpala_1_1HashTable_1_1Bucket.html#aef6be21fddf0a939b50561f53398fe09">impala::HashTable::Bucket::bucketData</a>, <a class="el" href="hash-table_8h_source.html#l00626">buckets_</a>, <a class="el" href="hash-table_8h_source.html#l00300">impala::HashTable::DuplicateNode::htdata</a>, <a class="el" href="hash-table_8h_source.html#l00323">impala::HashTable::Bucket::htdata</a>, <a class="el" href="hash-table_8inline_8h_source.html#l00183">InsertDuplicateNode()</a>, <a class="el" href="hash-table_8h_source.html#l00629">num_buckets_</a>, <a class="el" href="hash-table_8h_source.html#l00650">num_probes_</a>, <a class="el" href="hash-table_8inline_8h_source.html#l00163">PrepareBucketForInsert()</a>, <a class="el" href="hash-table_8inline_8h_source.html#l00037">Probe()</a>, and <a class="el" href="compiler-util_8h_source.html#l00033">UNLIKELY</a>.</p> |
| |
| <p>Referenced by <a class="el" href="hash-table_8inline_8h_source.html#l00094">Insert()</a>.</p> |
| |
| </div> |
| </div> |
| <a class="anchor" id="a463369a1c40b9254b0805264077b3d8a"></a> |
| <div class="memitem"> |
| <div class="memproto"> |
| <table class="mlabels"> |
| <tr> |
| <td class="mlabels-left"> |
| <table class="memname"> |
| <tr> |
| <td class="memname">double impala::HashTable::load_factor </td> |
| <td>(</td> |
| <td class="paramname"></td><td>)</td> |
| <td> const</td> |
| </tr> |
| </table> |
| </td> |
| <td class="mlabels-right"> |
| <span class="mlabels"><span class="mlabel">inline</span></span> </td> |
| </tr> |
| </table> |
| </div><div class="memdoc"> |
| |
| <p>Returns the load factor (the number of non-empty buckets) </p> |
| |
| <p>Definition at line <a class="el" href="hash-table_8h_source.html#l00391">391</a> of file <a class="el" href="hash-table_8h_source.html">hash-table.h</a>.</p> |
| |
| <p>References <a class="el" href="hash-table_8h_source.html#l00629">num_buckets_</a>, and <a class="el" href="hash-table_8h_source.html#l00632">num_filled_buckets_</a>.</p> |
| |
| </div> |
| </div> |
| <a class="anchor" id="a67951a6c7296d85edb7a08b5fe143352"></a> |
| <div class="memitem"> |
| <div class="memproto"> |
| <table class="mlabels"> |
| <tr> |
| <td class="mlabels-left"> |
| <table class="memname"> |
| <tr> |
| <td class="memname">void impala::HashTable::NextFilledBucket </td> |
| <td>(</td> |
| <td class="paramtype">int64_t * </td> |
| <td class="paramname"><em>bucket_idx</em>, </td> |
| </tr> |
| <tr> |
| <td class="paramkey"></td> |
| <td></td> |
| <td class="paramtype"><a class="el" href="structimpala_1_1HashTable_1_1DuplicateNode.html">DuplicateNode</a> ** </td> |
| <td class="paramname"><em>node</em> </td> |
| </tr> |
| <tr> |
| <td></td> |
| <td>)</td> |
| <td></td><td></td> |
| </tr> |
| </table> |
| </td> |
| <td class="mlabels-right"> |
| <span class="mlabels"><span class="mlabel">inline</span><span class="mlabel">private</span></span> </td> |
| </tr> |
| </table> |
| </div><div class="memdoc"> |
| <p>Updates 'bucket_idx' to the index of the next non-empty bucket. If the bucket has duplicates, 'node' will be pointing to the head of the linked list of duplicates. Otherwise, 'node' should not be used. If there are no more buckets, sets 'bucket_idx' to BUCKET_NOT_FOUND. </p> |
| |
| <p>Definition at line <a class="el" href="hash-table_8inline_8h_source.html#l00150">150</a> of file <a class="el" href="hash-table_8inline_8h_source.html">hash-table.inline.h</a>.</p> |
| |
| <p>References <a class="el" href="hash-table_8h_source.html#l00453">impala::HashTable::Iterator::BUCKET_NOT_FOUND</a>, <a class="el" href="structimpala_1_1HashTable_1_1Bucket.html#aef6be21fddf0a939b50561f53398fe09">impala::HashTable::Bucket::bucketData</a>, <a class="el" href="hash-table_8h_source.html#l00626">buckets_</a>, <a class="el" href="hash-table_8h_source.html#l00324">impala::HashTable::Bucket::duplicates</a>, and <a class="el" href="hash-table_8h_source.html#l00629">num_buckets_</a>.</p> |
| |
| <p>Referenced by <a class="el" href="hash-table_8inline_8h_source.html#l00128">Begin()</a>, <a class="el" href="hash-table_8inline_8h_source.html#l00135">FirstUnmatched()</a>, and <a class="el" href="hash-table_8cc_source.html#l00293">ResizeBuckets()</a>.</p> |
| |
| </div> |
| </div> |
| <a class="anchor" id="aa240fc7c128e0f6bd1e99b1b26e564ac"></a> |
| <div class="memitem"> |
| <div class="memproto"> |
| <table class="mlabels"> |
| <tr> |
| <td class="mlabels-left"> |
| <table class="memname"> |
| <tr> |
| <td class="memname">int64_t impala::HashTable::num_buckets </td> |
| <td>(</td> |
| <td class="paramname"></td><td>)</td> |
| <td> const</td> |
| </tr> |
| </table> |
| </td> |
| <td class="mlabels-right"> |
| <span class="mlabels"><span class="mlabel">inline</span></span> </td> |
| </tr> |
| </table> |
| </div><div class="memdoc"> |
| |
| <p>Returns the number of buckets. </p> |
| |
| <p>Definition at line <a class="el" href="hash-table_8h_source.html#l00388">388</a> of file <a class="el" href="hash-table_8h_source.html">hash-table.h</a>.</p> |
| |
| <p>References <a class="el" href="hash-table_8h_source.html#l00629">num_buckets_</a>.</p> |
| |
| <p>Referenced by <a class="el" href="hash-table-test_8cc_source.html#l00190">impala::HashTableTest::BasicTest()</a>, <a class="el" href="hash-table_8h_source.html#l00402">EstimateSize()</a>, <a class="el" href="hash-table_8cc_source.html#l00293">ResizeBuckets()</a>, and <a class="el" href="hash-table-test_8cc_source.html#l00247">impala::HashTableTest::ScanTest()</a>.</p> |
| |
| </div> |
| </div> |
| <a class="anchor" id="a4222254505940c65b0b817c4836a1021"></a> |
| <div class="memitem"> |
| <div class="memproto"> |
| <table class="mlabels"> |
| <tr> |
| <td class="mlabels-left"> |
| <table class="memname"> |
| <tr> |
| <td class="memname">void impala::HashTable::PrepareBucketForInsert </td> |
| <td>(</td> |
| <td class="paramtype">int64_t </td> |
| <td class="paramname"><em>bucket_idx</em>, </td> |
| </tr> |
| <tr> |
| <td class="paramkey"></td> |
| <td></td> |
| <td class="paramtype">uint32_t </td> |
| <td class="paramname"><em>hash</em> </td> |
| </tr> |
| <tr> |
| <td></td> |
| <td>)</td> |
| <td></td><td></td> |
| </tr> |
| </table> |
| </td> |
| <td class="mlabels-right"> |
| <span class="mlabels"><span class="mlabel">inline</span><span class="mlabel">private</span></span> </td> |
| </tr> |
| </table> |
| </div><div class="memdoc"> |
| <p>Resets the contents of the bucket with index 'bucket_idx', in preparation for an insert. Sets all the fields of the bucket other than 'data'. </p> |
| |
| <p>Definition at line <a class="el" href="hash-table_8inline_8h_source.html#l00163">163</a> of file <a class="el" href="hash-table_8inline_8h_source.html">hash-table.inline.h</a>.</p> |
| |
| <p>References <a class="el" href="hash-table_8h_source.html#l00626">buckets_</a>, <a class="el" href="hash-table_8h_source.html#l00305">impala::HashTable::Bucket::filled</a>, <a class="el" href="hash-table_8h_source.html#l00315">impala::HashTable::Bucket::hasDuplicates</a>, <a class="el" href="url-parser_8cc_source.html#l00041">impala::hash</a>, <a class="el" href="hash-table_8h_source.html#l00319">impala::HashTable::Bucket::hash</a>, <a class="el" href="hash-table_8h_source.html#l00311">impala::HashTable::Bucket::matched</a>, <a class="el" href="hash-table_8h_source.html#l00629">num_buckets_</a>, and <a class="el" href="hash-table_8h_source.html#l00632">num_filled_buckets_</a>.</p> |
| |
| <p>Referenced by <a class="el" href="hash-table_8inline_8h_source.html#l00077">InsertInternal()</a>.</p> |
| |
| </div> |
| </div> |
| <a class="anchor" id="a44aeea6af10973c12e6801dc409d7847"></a> |
| <div class="memitem"> |
| <div class="memproto"> |
| <table class="memname"> |
| <tr> |
| <td class="memname">string HashTable::PrintStats </td> |
| <td>(</td> |
| <td class="paramname"></td><td>)</td> |
| <td> const</td> |
| </tr> |
| </table> |
| </div><div class="memdoc"> |
| |
| <p>Update and print some statistics that can be used for performance debugging. </p> |
| |
| <p>Definition at line <a class="el" href="hash-table_8cc_source.html#l00424">424</a> of file <a class="el" href="hash-table_8cc_source.html">hash-table.cc</a>.</p> |
| |
| <p>References <a class="el" href="hash-table_8h_source.html#l00629">num_buckets_</a>, <a class="el" href="hash-table_8h_source.html#l00636">num_buckets_with_duplicates_</a>, <a class="el" href="hash-table_8h_source.html#l00620">num_duplicate_nodes_</a>, <a class="el" href="hash-table_8h_source.html#l00653">num_failed_probes_</a>, <a class="el" href="hash-table_8h_source.html#l00632">num_filled_buckets_</a>, <a class="el" href="hash-table_8h_source.html#l00661">num_hash_collisions_</a>, <a class="el" href="hash-table_8h_source.html#l00650">num_probes_</a>, <a class="el" href="hash-table_8h_source.html#l00664">num_resizes_</a>, and <a class="el" href="hash-table_8h_source.html#l00657">travel_length_</a>.</p> |
| |
| <p>Referenced by <a class="el" href="hash-table_8cc_source.html#l00257">Close()</a>.</p> |
| |
| </div> |
| </div> |
| <a class="anchor" id="a0c1d67cc8cebd5cd2fb855fa5d0a4a57"></a> |
| <div class="memitem"> |
| <div class="memproto"> |
| <table class="mlabels"> |
| <tr> |
| <td class="mlabels-left"> |
| <table class="memname"> |
| <tr> |
| <td class="memname">int64_t impala::HashTable::Probe </td> |
| <td>(</td> |
| <td class="paramtype"><a class="el" href="structimpala_1_1HashTable_1_1Bucket.html">Bucket</a> * </td> |
| <td class="paramname"><em>buckets</em>, </td> |
| </tr> |
| <tr> |
| <td class="paramkey"></td> |
| <td></td> |
| <td class="paramtype">int64_t </td> |
| <td class="paramname"><em>num_buckets</em>, </td> |
| </tr> |
| <tr> |
| <td class="paramkey"></td> |
| <td></td> |
| <td class="paramtype"><a class="el" href="classimpala_1_1HashTableCtx.html">HashTableCtx</a> * </td> |
| <td class="paramname"><em>ht_ctx</em>, </td> |
| </tr> |
| <tr> |
| <td class="paramkey"></td> |
| <td></td> |
| <td class="paramtype">uint32_t </td> |
| <td class="paramname"><em>hash</em>, </td> |
| </tr> |
| <tr> |
| <td class="paramkey"></td> |
| <td></td> |
| <td class="paramtype"><a class="el" href="classbool.html">bool</a> * </td> |
| <td class="paramname"><em>found</em> </td> |
| </tr> |
| <tr> |
| <td></td> |
| <td>)</td> |
| <td></td><td></td> |
| </tr> |
| </table> |
| </td> |
| <td class="mlabels-right"> |
| <span class="mlabels"><span class="mlabel">inline</span><span class="mlabel">private</span></span> </td> |
| </tr> |
| </table> |
| </div><div class="memdoc"> |
| |
| <p>There are wrappers of this function that perform the Find and Insert logic. </p> |
| <p>Performs the probing operation according to the probing algorithm (linear or quadratic. Returns one of the following: (a) the index of the bucket that contains the entry that matches with the last row evaluated in 'ht_ctx'. If 'ht_ctx' is NULL then it does not check for row equality and returns the index of the first empty bucket. (b) the index of the first empty bucket according to the probing algorithm (linear or quadratic), if the entry is not in the hash table or 'ht_ctx' is NULL. (c) <a class="el" href="classimpala_1_1HashTable_1_1Iterator.html#a4ae05474c3eb4e4c308e20db50836071" title="Bucket index value when probe is not successful. ">Iterator::BUCKET_NOT_FOUND</a> if the probe was not successful, i.e. the maximum distance was traveled without finding either an empty or a matching bucket. Using the returned index value, the caller can create an iterator that can be iterated until <a class="el" href="classimpala_1_1HashTable.html#ac62ebb8f6c388dff042794e69de596a9" title="Return end marker. ">End()</a> to find all the matching rows. EvalAndHashBuild() or EvalAndHashProb(e) must have been called before calling this. 'hash' must be the hash returned by these functions. 'found' indicates that a bucket that contains an equal row is found. </p> |
| |
| <p>Definition at line <a class="el" href="hash-table_8inline_8h_source.html#l00037">37</a> of file <a class="el" href="hash-table_8inline_8h_source.html">hash-table.inline.h</a>.</p> |
| |
| <p>References <a class="el" href="hash-table_8h_source.html#l00453">impala::HashTable::Iterator::BUCKET_NOT_FOUND</a>, <a class="el" href="hash-table_8cc_source.html#l00171">impala::HashTableCtx::Equals()</a>, <a class="el" href="hash-table_8h_source.html#l00305">impala::HashTable::Bucket::filled</a>, <a class="el" href="hash-table_8inline_8h_source.html#l00210">GetRow()</a>, <a class="el" href="url-parser_8cc_source.html#l00041">impala::hash</a>, <a class="el" href="hash-table_8h_source.html#l00319">impala::HashTable::Bucket::hash</a>, <a class="el" href="compiler-util_8h_source.html#l00032">LIKELY</a>, <a class="el" href="hash-table_8h_source.html#l00632">num_filled_buckets_</a>, <a class="el" href="hash-table_8h_source.html#l00661">num_hash_collisions_</a>, <a class="el" href="hash-table_8h_source.html#l00605">quadratic_probing_</a>, <a class="el" href="hash-table_8h_source.html#l00266">impala::HashTableCtx::row_</a>, and <a class="el" href="hash-table_8h_source.html#l00657">travel_length_</a>.</p> |
| |
| <p>Referenced by <a class="el" href="hash-table_8inline_8h_source.html#l00117">Find()</a>, <a class="el" href="hash-table_8inline_8h_source.html#l00077">InsertInternal()</a>, and <a class="el" href="hash-table_8cc_source.html#l00293">ResizeBuckets()</a>.</p> |
| |
| </div> |
| </div> |
| <a class="anchor" id="aeb7b0e3316dd455066ee922464ee695b"></a> |
| <div class="memitem"> |
| <div class="memproto"> |
| <table class="mlabels"> |
| <tr> |
| <td class="mlabels-left"> |
| <table class="memname"> |
| <tr> |
| <td class="memname"><a class="el" href="classbool.html">bool</a> HashTable::ResizeBuckets </td> |
| <td>(</td> |
| <td class="paramtype">int64_t </td> |
| <td class="paramname"><em>num_buckets</em>, </td> |
| </tr> |
| <tr> |
| <td class="paramkey"></td> |
| <td></td> |
| <td class="paramtype"><a class="el" href="classimpala_1_1HashTableCtx.html">HashTableCtx</a> * </td> |
| <td class="paramname"><em>ht_ctx</em> </td> |
| </tr> |
| <tr> |
| <td></td> |
| <td>)</td> |
| <td></td><td></td> |
| </tr> |
| </table> |
| </td> |
| <td class="mlabels-right"> |
| <span class="mlabels"><span class="mlabel">private</span></span> </td> |
| </tr> |
| </table> |
| </div><div class="memdoc"> |
| |
| <p>Resize the hash table to 'num_buckets'. Returns false on OOM. </p> |
| |
| <p>Definition at line <a class="el" href="hash-table_8cc_source.html#l00293">293</a> of file <a class="el" href="hash-table_8cc_source.html">hash-table.cc</a>.</p> |
| |
| <p>References <a class="el" href="hash-table_8h_source.html#l00492">impala::HashTable::Iterator::AtEnd()</a>, <a class="el" href="hash-table_8inline_8h_source.html#l00128">Begin()</a>, <a class="el" href="runtime-state_8h_source.html#l00194">impala::RuntimeState::block_mgr()</a>, <a class="el" href="hash-table_8h_source.html#l00588">block_mgr_client_</a>, <a class="el" href="hash-table_8h_source.html#l00453">impala::HashTable::Iterator::BUCKET_NOT_FOUND</a>, <a class="el" href="hash-table_8h_source.html#l00626">buckets_</a>, <a class="el" href="buffered-block-mgr_8cc_source.html#l00278">impala::BufferedBlockMgr::ConsumeMemory()</a>, <a class="el" href="hash-table_8h_source.html#l00319">impala::HashTable::Bucket::hash</a>, <a class="el" href="hash-table_8h_source.html#l00622">max_num_buckets_</a>, <a class="el" href="hash-table_8inline_8h_source.html#l00150">NextFilledBucket()</a>, <a class="el" href="hash-table_8h_source.html#l00388">num_buckets()</a>, <a class="el" href="hash-table_8h_source.html#l00629">num_buckets_</a>, <a class="el" href="hash-table_8h_source.html#l00632">num_filled_buckets_</a>, <a class="el" href="hash-table_8h_source.html#l00664">num_resizes_</a>, <a class="el" href="hash-table_8inline_8h_source.html#l00037">Probe()</a>, <a class="el" href="buffered-block-mgr_8cc_source.html#l00354">impala::BufferedBlockMgr::ReleaseMemory()</a>, and <a class="el" href="hash-table_8h_source.html#l00585">state_</a>.</p> |
| |
| <p>Referenced by <a class="el" href="hash-table_8cc_source.html#l00282">CheckAndResize()</a>, and <a class="el" href="hash-table-test_8cc_source.html#l00087">impala::HashTableTest::ResizeTable()</a>.</p> |
| |
| </div> |
| </div> |
| <a class="anchor" id="ae7006f3aff0395a0251fbb2765634b96"></a> |
| <div class="memitem"> |
| <div class="memproto"> |
| <table class="mlabels"> |
| <tr> |
| <td class="mlabels-left"> |
| <table class="memname"> |
| <tr> |
| <td class="memname">int64_t impala::HashTable::size </td> |
| <td>(</td> |
| <td class="paramname"></td><td>)</td> |
| <td> const</td> |
| </tr> |
| </table> |
| </td> |
| <td class="mlabels-right"> |
| <span class="mlabels"><span class="mlabel">inline</span></span> </td> |
| </tr> |
| </table> |
| </div><div class="memdoc"> |
| |
| <p>Returns number of elements inserted in the hash table. </p> |
| |
| <p>Definition at line <a class="el" href="hash-table_8h_source.html#l00380">380</a> of file <a class="el" href="hash-table_8h_source.html">hash-table.h</a>.</p> |
| |
| <p>References <a class="el" href="hash-table_8h_source.html#l00636">num_buckets_with_duplicates_</a>, <a class="el" href="hash-table_8h_source.html#l00620">num_duplicate_nodes_</a>, and <a class="el" href="hash-table_8h_source.html#l00632">num_filled_buckets_</a>.</p> |
| |
| <p>Referenced by <a class="el" href="hash-table-test_8cc_source.html#l00190">impala::HashTableTest::BasicTest()</a>, <a class="el" href="hash-table-test_8cc_source.html#l00298">impala::HashTableTest::GrowTableTest()</a>, and <a class="el" href="partitioned-hash-join-node_8cc_source.html#l01310">impala::PartitionedHashJoinNode::NodeDebugString()</a>.</p> |
| |
| </div> |
| </div> |
| <h2 class="groupheader">Friends And Related Function Documentation</h2> |
| <a class="anchor" id="a96d0236d3388688bbf272e9516dc8fda"></a> |
| <div class="memitem"> |
| <div class="memproto"> |
| <table class="mlabels"> |
| <tr> |
| <td class="mlabels-left"> |
| <table class="memname"> |
| <tr> |
| <td class="memname">friend class <a class="el" href="classimpala_1_1HashTableTest.html">HashTableTest</a></td> |
| </tr> |
| </table> |
| </td> |
| <td class="mlabels-right"> |
| <span class="mlabels"><span class="mlabel">friend</span></span> </td> |
| </tr> |
| </table> |
| </div><div class="memdoc"> |
| |
| <p>Definition at line <a class="el" href="hash-table_8h_source.html#l00518">518</a> of file <a class="el" href="hash-table_8h_source.html">hash-table.h</a>.</p> |
| |
| </div> |
| </div> |
| <a class="anchor" id="a9830fc407400559db7e7783cc10a9394"></a> |
| <div class="memitem"> |
| <div class="memproto"> |
| <table class="mlabels"> |
| <tr> |
| <td class="mlabels-left"> |
| <table class="memname"> |
| <tr> |
| <td class="memname">friend class <a class="el" href="classimpala_1_1HashTable_1_1Iterator.html">Iterator</a></td> |
| </tr> |
| </table> |
| </td> |
| <td class="mlabels-right"> |
| <span class="mlabels"><span class="mlabel">friend</span></span> </td> |
| </tr> |
| </table> |
| </div><div class="memdoc"> |
| |
| <p>Definition at line <a class="el" href="hash-table_8h_source.html#l00517">517</a> of file <a class="el" href="hash-table_8h_source.html">hash-table.h</a>.</p> |
| |
| <p>Referenced by <a class="el" href="hash-table_8inline_8h_source.html#l00128">Begin()</a>, <a class="el" href="hash-table_8h_source.html#l00434">End()</a>, and <a class="el" href="hash-table_8inline_8h_source.html#l00117">Find()</a>.</p> |
| |
| </div> |
| </div> |
| <h2 class="groupheader">Member Data Documentation</h2> |
| <a class="anchor" id="ab9cd09fae6e57ed0fb9fedade5f7293a"></a> |
| <div class="memitem"> |
| <div class="memproto"> |
| <table class="mlabels"> |
| <tr> |
| <td class="mlabels-left"> |
| <table class="memname"> |
| <tr> |
| <td class="memname"><a class="el" href="structimpala_1_1BufferedBlockMgr_1_1Client.html">BufferedBlockMgr::Client</a>* impala::HashTable::block_mgr_client_</td> |
| </tr> |
| </table> |
| </td> |
| <td class="mlabels-right"> |
| <span class="mlabels"><span class="mlabel">private</span></span> </td> |
| </tr> |
| </table> |
| </div><div class="memdoc"> |
| |
| <p>Client to allocate data pages with. </p> |
| |
| <p>Definition at line <a class="el" href="hash-table_8h_source.html#l00588">588</a> of file <a class="el" href="hash-table_8h_source.html">hash-table.h</a>.</p> |
| |
| <p>Referenced by <a class="el" href="hash-table_8cc_source.html#l00257">Close()</a>, <a class="el" href="hash-table_8cc_source.html#l00345">GrowNodeArray()</a>, <a class="el" href="hash-table_8cc_source.html#l00245">Init()</a>, and <a class="el" href="hash-table_8cc_source.html#l00293">ResizeBuckets()</a>.</p> |
| |
| </div> |
| </div> |
| <a class="anchor" id="ac461c88f6a7b8f9b0fdfc1cd42344837"></a> |
| <div class="memitem"> |
| <div class="memproto"> |
| <table class="mlabels"> |
| <tr> |
| <td class="mlabels-left"> |
| <table class="memname"> |
| <tr> |
| <td class="memname"><a class="el" href="structimpala_1_1HashTable_1_1Bucket.html">Bucket</a>* impala::HashTable::buckets_</td> |
| </tr> |
| </table> |
| </td> |
| <td class="mlabels-right"> |
| <span class="mlabels"><span class="mlabel">private</span></span> </td> |
| </tr> |
| </table> |
| </div><div class="memdoc"> |
| <p>Array of all buckets. Owned by this node. Using c-style array to control control memory footprint. </p> |
| |
| <p>Definition at line <a class="el" href="hash-table_8h_source.html#l00626">626</a> of file <a class="el" href="hash-table_8h_source.html">hash-table.h</a>.</p> |
| |
| <p>Referenced by <a class="el" href="hash-table_8cc_source.html#l00257">Close()</a>, <a class="el" href="hash-table_8cc_source.html#l00387">DebugString()</a>, <a class="el" href="hash-table_8inline_8h_source.html#l00117">Find()</a>, <a class="el" href="hash-table_8inline_8h_source.html#l00135">FirstUnmatched()</a>, <a class="el" href="hash-table_8inline_8h_source.html#l00230">impala::HashTable::Iterator::GetRow()</a>, <a class="el" href="hash-table_8cc_source.html#l00245">Init()</a>, <a class="el" href="hash-table_8inline_8h_source.html#l00183">InsertDuplicateNode()</a>, <a class="el" href="hash-table_8inline_8h_source.html#l00077">InsertInternal()</a>, <a class="el" href="hash-table_8inline_8h_source.html#l00150">NextFilledBucket()</a>, <a class="el" href="hash-table_8inline_8h_source.html#l00163">PrepareBucketForInsert()</a>, and <a class="el" href="hash-table_8cc_source.html#l00293">ResizeBuckets()</a>.</p> |
| |
| </div> |
| </div> |
| <a class="anchor" id="a0f4c922a525b11eaf26d82a808f6c233"></a> |
| <div class="memitem"> |
| <div class="memproto"> |
| <table class="mlabels"> |
| <tr> |
| <td class="mlabels-left"> |
| <table class="memname"> |
| <tr> |
| <td class="memname"><a class="el" href="classimpala_1_1MemPool.html">MemPool</a>* impala::HashTable::data_page_pool_</td> |
| </tr> |
| </table> |
| </td> |
| <td class="mlabels-right"> |
| <span class="mlabels"><span class="mlabel">private</span></span> </td> |
| </tr> |
| </table> |
| </div><div class="memdoc"> |
| |
| <p>Only used for tests to allocate data pages instead of the block mgr. </p> |
| |
| <p>Definition at line <a class="el" href="hash-table_8h_source.html#l00596">596</a> of file <a class="el" href="hash-table_8h_source.html">hash-table.h</a>.</p> |
| |
| <p>Referenced by <a class="el" href="hash-table_8cc_source.html#l00345">GrowNodeArray()</a>.</p> |
| |
| </div> |
| </div> |
| <a class="anchor" id="a554127ece2fc15868faacb0892fb8360"></a> |
| <div class="memitem"> |
| <div class="memproto"> |
| <table class="mlabels"> |
| <tr> |
| <td class="mlabels-left"> |
| <table class="memname"> |
| <tr> |
| <td class="memname">std::vector<<a class="el" href="classimpala_1_1BufferedBlockMgr_1_1Block.html">BufferedBlockMgr::Block</a>*> impala::HashTable::data_pages_</td> |
| </tr> |
| </table> |
| </td> |
| <td class="mlabels-right"> |
| <span class="mlabels"><span class="mlabel">private</span></span> </td> |
| </tr> |
| </table> |
| </div><div class="memdoc"> |
| |
| <p>Data pages for all nodes. These are always pinned. </p> |
| |
| <p>Definition at line <a class="el" href="hash-table_8h_source.html#l00608">608</a> of file <a class="el" href="hash-table_8h_source.html">hash-table.h</a>.</p> |
| |
| <p>Referenced by <a class="el" href="hash-table_8cc_source.html#l00257">Close()</a>, and <a class="el" href="hash-table_8cc_source.html#l00345">GrowNodeArray()</a>.</p> |
| |
| </div> |
| </div> |
| <a class="anchor" id="a63154f1e57a11b4d9362943bae38ef5a"></a> |
| <div class="memitem"> |
| <div class="memproto"> |
| <table class="mlabels"> |
| <tr> |
| <td class="mlabels-left"> |
| <table class="memname"> |
| <tr> |
| <td class="memname"><a class="el" href="classbool.html">bool</a> impala::HashTable::has_matches_</td> |
| </tr> |
| </table> |
| </td> |
| <td class="mlabels-right"> |
| <span class="mlabels"><span class="mlabel">private</span></span> </td> |
| </tr> |
| </table> |
| </div><div class="memdoc"> |
| <p>Flag used to disable spilling hash tables that already had matches in case of right joins (IMPALA-1488). TODO: Not fail when spilling hash tables with matches in right joins </p> |
| |
| <p>Definition at line <a class="el" href="hash-table_8h_source.html#l00645">645</a> of file <a class="el" href="hash-table_8h_source.html">hash-table.h</a>.</p> |
| |
| <p>Referenced by <a class="el" href="hash-table_8h_source.html#l00431">HasMatches()</a>.</p> |
| |
| </div> |
| </div> |
| <a class="anchor" id="a16ecff93c19dfa4090ec393d34385f95"></a> |
| <div class="memitem"> |
| <div class="memproto"> |
| <table class="mlabels"> |
| <tr> |
| <td class="mlabels-left"> |
| <table class="memname"> |
| <tr> |
| <td class="memname">const double HashTable::MAX_FILL_FACTOR = 0.75f</td> |
| </tr> |
| </table> |
| </td> |
| <td class="mlabels-right"> |
| <span class="mlabels"><span class="mlabel">static</span><span class="mlabel">private</span></span> </td> |
| </tr> |
| </table> |
| </div><div class="memdoc"> |
| <p>Load factor that will trigger growing the hash table on insert. This is defined as the number of non-empty buckets / total_buckets </p> |
| |
| <p>Definition at line <a class="el" href="hash-table_8h_source.html#l00583">583</a> of file <a class="el" href="hash-table_8h_source.html">hash-table.h</a>.</p> |
| |
| <p>Referenced by <a class="el" href="hash-table_8cc_source.html#l00282">CheckAndResize()</a>.</p> |
| |
| </div> |
| </div> |
| <a class="anchor" id="a41ec948e01fcfa27711c3382dd5d1ffd"></a> |
| <div class="memitem"> |
| <div class="memproto"> |
| <table class="mlabels"> |
| <tr> |
| <td class="mlabels-left"> |
| <table class="memname"> |
| <tr> |
| <td class="memname">const int64_t impala::HashTable::max_num_buckets_</td> |
| </tr> |
| </table> |
| </td> |
| <td class="mlabels-right"> |
| <span class="mlabels"><span class="mlabel">private</span></span> </td> |
| </tr> |
| </table> |
| </div><div class="memdoc"> |
| |
| <p>Definition at line <a class="el" href="hash-table_8h_source.html#l00622">622</a> of file <a class="el" href="hash-table_8h_source.html">hash-table.h</a>.</p> |
| |
| <p>Referenced by <a class="el" href="hash-table_8cc_source.html#l00293">ResizeBuckets()</a>.</p> |
| |
| </div> |
| </div> |
| <a class="anchor" id="ac7049a35b4d1716e54bb46d9c3ed890d"></a> |
| <div class="memitem"> |
| <div class="memproto"> |
| <table class="mlabels"> |
| <tr> |
| <td class="mlabels-left"> |
| <table class="memname"> |
| <tr> |
| <td class="memname"><a class="el" href="structimpala_1_1HashTable_1_1DuplicateNode.html">DuplicateNode</a>* impala::HashTable::next_node_</td> |
| </tr> |
| </table> |
| </td> |
| <td class="mlabels-right"> |
| <span class="mlabels"><span class="mlabel">private</span></span> </td> |
| </tr> |
| </table> |
| </div><div class="memdoc"> |
| |
| <p>Next duplicate node to insert. Vaild when node_remaining_current_page_ > 0. </p> |
| |
| <p>Definition at line <a class="el" href="hash-table_8h_source.html#l00614">614</a> of file <a class="el" href="hash-table_8h_source.html">hash-table.h</a>.</p> |
| |
| <p>Referenced by <a class="el" href="hash-table_8inline_8h_source.html#l00175">AppendNextNode()</a>, <a class="el" href="hash-table_8cc_source.html#l00345">GrowNodeArray()</a>, and <a class="el" href="hash-table_8inline_8h_source.html#l00183">InsertDuplicateNode()</a>.</p> |
| |
| </div> |
| </div> |
| <a class="anchor" id="ae1cda955b2701205694fdf8407f90138"></a> |
| <div class="memitem"> |
| <div class="memproto"> |
| <table class="mlabels"> |
| <tr> |
| <td class="mlabels-left"> |
| <table class="memname"> |
| <tr> |
| <td class="memname">int impala::HashTable::node_remaining_current_page_</td> |
| </tr> |
| </table> |
| </td> |
| <td class="mlabels-right"> |
| <span class="mlabels"><span class="mlabel">private</span></span> </td> |
| </tr> |
| </table> |
| </div><div class="memdoc"> |
| |
| <p>Number of nodes left in the current page. </p> |
| |
| <p>Definition at line <a class="el" href="hash-table_8h_source.html#l00617">617</a> of file <a class="el" href="hash-table_8h_source.html">hash-table.h</a>.</p> |
| |
| <p>Referenced by <a class="el" href="hash-table_8inline_8h_source.html#l00175">AppendNextNode()</a>, and <a class="el" href="hash-table_8cc_source.html#l00345">GrowNodeArray()</a>.</p> |
| |
| </div> |
| </div> |
| <a class="anchor" id="acc898ddea6c8c1d54f21fea4af1bcf7b"></a> |
| <div class="memitem"> |
| <div class="memproto"> |
| <table class="mlabels"> |
| <tr> |
| <td class="mlabels-left"> |
| <table class="memname"> |
| <tr> |
| <td class="memname">int64_t impala::HashTable::num_buckets_</td> |
| </tr> |
| </table> |
| </td> |
| <td class="mlabels-right"> |
| <span class="mlabels"><span class="mlabel">private</span></span> </td> |
| </tr> |
| </table> |
| </div><div class="memdoc"> |
| |
| <p>Total number of buckets (filled and empty). </p> |
| |
| <p>Definition at line <a class="el" href="hash-table_8h_source.html#l00629">629</a> of file <a class="el" href="hash-table_8h_source.html">hash-table.h</a>.</p> |
| |
| <p>Referenced by <a class="el" href="hash-table_8cc_source.html#l00282">CheckAndResize()</a>, <a class="el" href="hash-table_8cc_source.html#l00257">Close()</a>, <a class="el" href="hash-table_8cc_source.html#l00278">CurrentMemSize()</a>, <a class="el" href="hash-table_8cc_source.html#l00387">DebugString()</a>, <a class="el" href="hash-table_8h_source.html#l00385">EmptyBuckets()</a>, <a class="el" href="hash-table_8inline_8h_source.html#l00117">Find()</a>, <a class="el" href="hash-table_8cc_source.html#l00245">Init()</a>, <a class="el" href="hash-table_8inline_8h_source.html#l00183">InsertDuplicateNode()</a>, <a class="el" href="hash-table_8inline_8h_source.html#l00077">InsertInternal()</a>, <a class="el" href="hash-table_8h_source.html#l00391">load_factor()</a>, <a class="el" href="hash-table_8inline_8h_source.html#l00150">NextFilledBucket()</a>, <a class="el" href="hash-table_8h_source.html#l00388">num_buckets()</a>, <a class="el" href="hash-table_8inline_8h_source.html#l00163">PrepareBucketForInsert()</a>, <a class="el" href="hash-table_8cc_source.html#l00424">PrintStats()</a>, and <a class="el" href="hash-table_8cc_source.html#l00293">ResizeBuckets()</a>.</p> |
| |
| </div> |
| </div> |
| <a class="anchor" id="a92d8c35c802147adf40685e7c1bdcca7"></a> |
| <div class="memitem"> |
| <div class="memproto"> |
| <table class="mlabels"> |
| <tr> |
| <td class="mlabels-left"> |
| <table class="memname"> |
| <tr> |
| <td class="memname">int64_t impala::HashTable::num_buckets_with_duplicates_</td> |
| </tr> |
| </table> |
| </td> |
| <td class="mlabels-right"> |
| <span class="mlabels"><span class="mlabel">private</span></span> </td> |
| </tr> |
| </table> |
| </div><div class="memdoc"> |
| <p>Number of (non-empty) buckets with duplicates. These buckets do not point to slots in the tuple stream, rather than to a linked list of Nodes. </p> |
| |
| <p>Definition at line <a class="el" href="hash-table_8h_source.html#l00636">636</a> of file <a class="el" href="hash-table_8h_source.html">hash-table.h</a>.</p> |
| |
| <p>Referenced by <a class="el" href="hash-table_8inline_8h_source.html#l00183">InsertDuplicateNode()</a>, <a class="el" href="hash-table_8cc_source.html#l00424">PrintStats()</a>, and <a class="el" href="hash-table_8h_source.html#l00380">size()</a>.</p> |
| |
| </div> |
| </div> |
| <a class="anchor" id="a6d7e2d70c48ad221333f5b939745134b"></a> |
| <div class="memitem"> |
| <div class="memproto"> |
| <table class="mlabels"> |
| <tr> |
| <td class="mlabels-left"> |
| <table class="memname"> |
| <tr> |
| <td class="memname">int impala::HashTable::num_build_tuples_</td> |
| </tr> |
| </table> |
| </td> |
| <td class="mlabels-right"> |
| <span class="mlabels"><span class="mlabel">private</span></span> </td> |
| </tr> |
| </table> |
| </div><div class="memdoc"> |
| <p>Number of build tuples, used for constructing temp row* for probes. TODO: We should remove it. </p> |
| |
| <p>Definition at line <a class="el" href="hash-table_8h_source.html#l00640">640</a> of file <a class="el" href="hash-table_8h_source.html">hash-table.h</a>.</p> |
| |
| <p>Referenced by <a class="el" href="hash-table_8cc_source.html#l00373">DebugStringTuple()</a>.</p> |
| |
| </div> |
| </div> |
| <a class="anchor" id="afad2ad0b627b41b7fe072598f762c0ae"></a> |
| <div class="memitem"> |
| <div class="memproto"> |
| <table class="mlabels"> |
| <tr> |
| <td class="mlabels-left"> |
| <table class="memname"> |
| <tr> |
| <td class="memname">int64_t impala::HashTable::num_duplicate_nodes_</td> |
| </tr> |
| </table> |
| </td> |
| <td class="mlabels-right"> |
| <span class="mlabels"><span class="mlabel">private</span></span> </td> |
| </tr> |
| </table> |
| </div><div class="memdoc"> |
| |
| <p>Number of duplicate nodes. </p> |
| |
| <p>Definition at line <a class="el" href="hash-table_8h_source.html#l00620">620</a> of file <a class="el" href="hash-table_8h_source.html">hash-table.h</a>.</p> |
| |
| <p>Referenced by <a class="el" href="hash-table_8inline_8h_source.html#l00175">AppendNextNode()</a>, <a class="el" href="hash-table_8cc_source.html#l00278">CurrentMemSize()</a>, <a class="el" href="hash-table_8cc_source.html#l00424">PrintStats()</a>, and <a class="el" href="hash-table_8h_source.html#l00380">size()</a>.</p> |
| |
| </div> |
| </div> |
| <a class="anchor" id="a3f5da1f068a86b1cae6f207dfce96710"></a> |
| <div class="memitem"> |
| <div class="memproto"> |
| <table class="mlabels"> |
| <tr> |
| <td class="mlabels-left"> |
| <table class="memname"> |
| <tr> |
| <td class="memname">int64_t impala::HashTable::num_failed_probes_</td> |
| </tr> |
| </table> |
| </td> |
| <td class="mlabels-right"> |
| <span class="mlabels"><span class="mlabel">private</span></span> </td> |
| </tr> |
| </table> |
| </div><div class="memdoc"> |
| |
| <p>Number of probes that failed and had to fall back to linear probing without cap. </p> |
| |
| <p>Definition at line <a class="el" href="hash-table_8h_source.html#l00653">653</a> of file <a class="el" href="hash-table_8h_source.html">hash-table.h</a>.</p> |
| |
| <p>Referenced by <a class="el" href="hash-table_8cc_source.html#l00424">PrintStats()</a>.</p> |
| |
| </div> |
| </div> |
| <a class="anchor" id="a4ce8e82c4e985189eed19deb26471cc2"></a> |
| <div class="memitem"> |
| <div class="memproto"> |
| <table class="mlabels"> |
| <tr> |
| <td class="mlabels-left"> |
| <table class="memname"> |
| <tr> |
| <td class="memname">int64_t impala::HashTable::num_filled_buckets_</td> |
| </tr> |
| </table> |
| </td> |
| <td class="mlabels-right"> |
| <span class="mlabels"><span class="mlabel">private</span></span> </td> |
| </tr> |
| </table> |
| </div><div class="memdoc"> |
| |
| <p>Number of non-empty buckets. Used to determine when to resize. </p> |
| |
| <p>Definition at line <a class="el" href="hash-table_8h_source.html#l00632">632</a> of file <a class="el" href="hash-table_8h_source.html">hash-table.h</a>.</p> |
| |
| <p>Referenced by <a class="el" href="hash-table_8cc_source.html#l00282">CheckAndResize()</a>, <a class="el" href="hash-table_8h_source.html#l00385">EmptyBuckets()</a>, <a class="el" href="hash-table_8h_source.html#l00391">load_factor()</a>, <a class="el" href="hash-table_8inline_8h_source.html#l00163">PrepareBucketForInsert()</a>, <a class="el" href="hash-table_8cc_source.html#l00424">PrintStats()</a>, <a class="el" href="hash-table_8inline_8h_source.html#l00037">Probe()</a>, <a class="el" href="hash-table_8cc_source.html#l00293">ResizeBuckets()</a>, and <a class="el" href="hash-table_8h_source.html#l00380">size()</a>.</p> |
| |
| </div> |
| </div> |
| <a class="anchor" id="ae21db224cca645cb112fc27d323e9048"></a> |
| <div class="memitem"> |
| <div class="memproto"> |
| <table class="mlabels"> |
| <tr> |
| <td class="mlabels-left"> |
| <table class="memname"> |
| <tr> |
| <td class="memname">int64_t impala::HashTable::num_hash_collisions_</td> |
| </tr> |
| </table> |
| </td> |
| <td class="mlabels-right"> |
| <span class="mlabels"><span class="mlabel">private</span></span> </td> |
| </tr> |
| </table> |
| </div><div class="memdoc"> |
| <p>The number of cases where we had to compare buckets with the same hash value, but the row equality failed. </p> |
| |
| <p>Definition at line <a class="el" href="hash-table_8h_source.html#l00661">661</a> of file <a class="el" href="hash-table_8h_source.html">hash-table.h</a>.</p> |
| |
| <p>Referenced by <a class="el" href="hash-table_8cc_source.html#l00424">PrintStats()</a>, and <a class="el" href="hash-table_8inline_8h_source.html#l00037">Probe()</a>.</p> |
| |
| </div> |
| </div> |
| <a class="anchor" id="ad5cafb9172df65844a941a43a0e80b3e"></a> |
| <div class="memitem"> |
| <div class="memproto"> |
| <table class="mlabels"> |
| <tr> |
| <td class="mlabels-left"> |
| <table class="memname"> |
| <tr> |
| <td class="memname">int64_t impala::HashTable::num_probes_</td> |
| </tr> |
| </table> |
| </td> |
| <td class="mlabels-right"> |
| <span class="mlabels"><span class="mlabel">private</span></span> </td> |
| </tr> |
| </table> |
| </div><div class="memdoc"> |
| <p>The stats below can be used for debugging perf. TODO: Should we make these statistics atomic? Number of calls to either Find, Insert or FindOrInsert an entry. </p> |
| |
| <p>Definition at line <a class="el" href="hash-table_8h_source.html#l00650">650</a> of file <a class="el" href="hash-table_8h_source.html">hash-table.h</a>.</p> |
| |
| <p>Referenced by <a class="el" href="hash-table_8cc_source.html#l00257">Close()</a>, <a class="el" href="hash-table_8inline_8h_source.html#l00117">Find()</a>, <a class="el" href="hash-table_8inline_8h_source.html#l00077">InsertInternal()</a>, and <a class="el" href="hash-table_8cc_source.html#l00424">PrintStats()</a>.</p> |
| |
| </div> |
| </div> |
| <a class="anchor" id="afea6437f65ec39ca574fe85afe0992e7"></a> |
| <div class="memitem"> |
| <div class="memproto"> |
| <table class="mlabels"> |
| <tr> |
| <td class="mlabels-left"> |
| <table class="memname"> |
| <tr> |
| <td class="memname">int64_t impala::HashTable::num_resizes_</td> |
| </tr> |
| </table> |
| </td> |
| <td class="mlabels-right"> |
| <span class="mlabels"><span class="mlabel">private</span></span> </td> |
| </tr> |
| </table> |
| </div><div class="memdoc"> |
| |
| <p>How many times this table has resized so far. </p> |
| |
| <p>Definition at line <a class="el" href="hash-table_8h_source.html#l00664">664</a> of file <a class="el" href="hash-table_8h_source.html">hash-table.h</a>.</p> |
| |
| <p>Referenced by <a class="el" href="hash-table_8cc_source.html#l00424">PrintStats()</a>, and <a class="el" href="hash-table_8cc_source.html#l00293">ResizeBuckets()</a>.</p> |
| |
| </div> |
| </div> |
| <a class="anchor" id="a1ad3c64c070af80571ca8c79f2ed9f9a"></a> |
| <div class="memitem"> |
| <div class="memproto"> |
| <table class="mlabels"> |
| <tr> |
| <td class="mlabels-left"> |
| <table class="memname"> |
| <tr> |
| <td class="memname">const <a class="el" href="classbool.html">bool</a> impala::HashTable::quadratic_probing_</td> |
| </tr> |
| </table> |
| </td> |
| <td class="mlabels-right"> |
| <span class="mlabels"><span class="mlabel">private</span></span> </td> |
| </tr> |
| </table> |
| </div><div class="memdoc"> |
| |
| <p>Quadratic probing enabled (as opposed to linear). </p> |
| |
| <p>Definition at line <a class="el" href="hash-table_8h_source.html#l00605">605</a> of file <a class="el" href="hash-table_8h_source.html">hash-table.h</a>.</p> |
| |
| <p>Referenced by <a class="el" href="hash-table_8inline_8h_source.html#l00037">Probe()</a>.</p> |
| |
| </div> |
| </div> |
| <a class="anchor" id="ac4f83b6445d06ccc7b9c25a67c900cf9"></a> |
| <div class="memitem"> |
| <div class="memproto"> |
| <table class="mlabels"> |
| <tr> |
| <td class="mlabels-left"> |
| <table class="memname"> |
| <tr> |
| <td class="memname"><a class="el" href="classimpala_1_1RuntimeState.html">RuntimeState</a>* impala::HashTable::state_</td> |
| </tr> |
| </table> |
| </td> |
| <td class="mlabels-right"> |
| <span class="mlabels"><span class="mlabel">private</span></span> </td> |
| </tr> |
| </table> |
| </div><div class="memdoc"> |
| |
| <p>Definition at line <a class="el" href="hash-table_8h_source.html#l00585">585</a> of file <a class="el" href="hash-table_8h_source.html">hash-table.h</a>.</p> |
| |
| <p>Referenced by <a class="el" href="hash-table_8cc_source.html#l00257">Close()</a>, <a class="el" href="hash-table_8cc_source.html#l00345">GrowNodeArray()</a>, <a class="el" href="hash-table_8cc_source.html#l00245">Init()</a>, and <a class="el" href="hash-table_8cc_source.html#l00293">ResizeBuckets()</a>.</p> |
| |
| </div> |
| </div> |
| <a class="anchor" id="aea176ae316a2d2e6a6ec1210c0ba7373"></a> |
| <div class="memitem"> |
| <div class="memproto"> |
| <table class="mlabels"> |
| <tr> |
| <td class="mlabels-left"> |
| <table class="memname"> |
| <tr> |
| <td class="memname">const <a class="el" href="classbool.html">bool</a> impala::HashTable::stores_tuples_</td> |
| </tr> |
| </table> |
| </td> |
| <td class="mlabels-right"> |
| <span class="mlabels"><span class="mlabel">private</span></span> </td> |
| </tr> |
| </table> |
| </div><div class="memdoc"> |
| <p>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. TODO: ..or with template-ization </p> |
| |
| <p>Definition at line <a class="el" href="hash-table_8h_source.html#l00602">602</a> of file <a class="el" href="hash-table_8h_source.html">hash-table.h</a>.</p> |
| |
| <p>Referenced by <a class="el" href="hash-table_8cc_source.html#l00373">DebugStringTuple()</a>, <a class="el" href="hash-table_8inline_8h_source.html#l00210">GetRow()</a>, <a class="el" href="hash-table_8cc_source.html#l00192">HashTable()</a>, and <a class="el" href="hash-table_8inline_8h_source.html#l00094">Insert()</a>.</p> |
| |
| </div> |
| </div> |
| <a class="anchor" id="af7b361bdfb31e9438075ce2b67fd91ba"></a> |
| <div class="memitem"> |
| <div class="memproto"> |
| <table class="mlabels"> |
| <tr> |
| <td class="mlabels-left"> |
| <table class="memname"> |
| <tr> |
| <td class="memname">int64_t impala::HashTable::total_data_page_size_</td> |
| </tr> |
| </table> |
| </td> |
| <td class="mlabels-right"> |
| <span class="mlabels"><span class="mlabel">private</span></span> </td> |
| </tr> |
| </table> |
| </div><div class="memdoc"> |
| |
| <p>Byte size of all buffers in data_pages_. </p> |
| |
| <p>Definition at line <a class="el" href="hash-table_8h_source.html#l00611">611</a> of file <a class="el" href="hash-table_8h_source.html">hash-table.h</a>.</p> |
| |
| <p>Referenced by <a class="el" href="hash-table_8h_source.html#l00419">byte_size()</a>, <a class="el" href="hash-table_8cc_source.html#l00257">Close()</a>, and <a class="el" href="hash-table_8cc_source.html#l00345">GrowNodeArray()</a>.</p> |
| |
| </div> |
| </div> |
| <a class="anchor" id="a8cc7932cc1427f6279ced8e9b915f00e"></a> |
| <div class="memitem"> |
| <div class="memproto"> |
| <table class="mlabels"> |
| <tr> |
| <td class="mlabels-left"> |
| <table class="memname"> |
| <tr> |
| <td class="memname">int64_t impala::HashTable::travel_length_</td> |
| </tr> |
| </table> |
| </td> |
| <td class="mlabels-right"> |
| <span class="mlabels"><span class="mlabel">private</span></span> </td> |
| </tr> |
| </table> |
| </div><div class="memdoc"> |
| <p>Total distance traveled for each probe. That is the sum of the diff between the end position of a probe (find/insert) and its start position (hash & (num_buckets_ - 1)). </p> |
| |
| <p>Definition at line <a class="el" href="hash-table_8h_source.html#l00657">657</a> of file <a class="el" href="hash-table_8h_source.html">hash-table.h</a>.</p> |
| |
| <p>Referenced by <a class="el" href="hash-table_8cc_source.html#l00424">PrintStats()</a>, and <a class="el" href="hash-table_8inline_8h_source.html#l00037">Probe()</a>.</p> |
| |
| </div> |
| </div> |
| <a class="anchor" id="a53e8f6764f9f739c3a2f478c5c5e7d4c"></a> |
| <div class="memitem"> |
| <div class="memproto"> |
| <table class="mlabels"> |
| <tr> |
| <td class="mlabels-left"> |
| <table class="memname"> |
| <tr> |
| <td class="memname"><a class="el" href="classimpala_1_1BufferedTupleStream.html">BufferedTupleStream</a>* impala::HashTable::tuple_stream_</td> |
| </tr> |
| </table> |
| </td> |
| <td class="mlabels-right"> |
| <span class="mlabels"><span class="mlabel">private</span></span> </td> |
| </tr> |
| </table> |
| </div><div class="memdoc"> |
| <p>Stream contains the rows referenced by the hash table. Can be NULL if the row only contains a single tuple, in which case the <a class="el" href="classimpala_1_1TupleRow.html">TupleRow</a> indirection is removed by the hash table. </p> |
| |
| <p>Definition at line <a class="el" href="hash-table_8h_source.html#l00593">593</a> of file <a class="el" href="hash-table_8h_source.html">hash-table.h</a>.</p> |
| |
| <p>Referenced by <a class="el" href="hash-table_8inline_8h_source.html#l00210">GetRow()</a>.</p> |
| |
| </div> |
| </div> |
| <hr/>The documentation for this class was generated from the following files:<ul> |
| <li>be/src/exec/<a class="el" href="hash-table_8h_source.html">hash-table.h</a></li> |
| <li>be/src/exec/<a class="el" href="hash-table_8cc_source.html">hash-table.cc</a></li> |
| <li>be/src/exec/<a class="el" href="hash-table_8inline_8h_source.html">hash-table.inline.h</a></li> |
| </ul> |
| </div><!-- contents --> |
| </div><!-- doc-content --> |
| <!-- start footer part --> |
| <div id="nav-path" class="navpath"><!-- id is needed for treeview function! --> |
| <ul> |
| <li class="navelem"><a class="el" href="namespaceimpala.html">impala</a></li><li class="navelem"><a class="el" href="classimpala_1_1HashTable.html">HashTable</a></li> |
| <li class="footer">Generated on Thu May 7 2015 16:10:47 for Impala by |
| <a href="http://www.doxygen.org/index.html"> |
| <img class="footer" src="doxygen.png" alt="doxygen"/></a> 1.8.6 </li> |
| </ul> |
| </div> |
| </body> |
| </html> |
