6/8/2023 0 Comments Hash tableWhen the first pair of chunk files is processed, we move to the next pair of chunk files, continuing until all pair of chunk files has been processed. ![]() After the build chunk is loaded, we read the corresponding chunk file from the probe input and probe for matches in the hash table, just like when everything fits in memory. This explains why we want the largest chunk to fit exactly in memory if the chunk files are too big we need to split it up in even smaller chunks. We load the first chunk file from the build input into the in-memory hash table. In general, the server does a build and probe phase using the first set of chunk files as the build and probe input. When the probe phase is done, we start reading chunk files from disk. This way, we know for sure that matching rows between the two inputs will be located in the same pair of chunk files. Which chunk file a row is written to is determined using the same hash function and formula that is used when the build input is written to disk. Thus, each row from the probe input is also written to a set of chunk files. ![]() But in addition, a row may also match one of the rows from the build input that is written to disk. We will see why a bit later.ĭuring the probe phase, the server probes for matching rows in the hash table, just like when everything fits in memory. Note that in the illustration, there is a different hash function used than the one used in the in-memory build phase. Which chunk file a row is written to is determined by calculating a hash of the join attribute. The server tries to set the number of chunks so that the largest chunk fits exactly in memory (we will see why soon), but MySQL has a hard upper limit of 128 chunk files per input. When the memory goes full during the build phase, the server writes the rest of the build input out to a number of chunk files on disk. But what happens if the build input is bigger than the available memory? We spill to disk! Spill to disk The amount of memory available is controlled by the system variable join_buffer_size, and can be adjusted at runtime. This works very well given that the server can store the entire build input in memory. In the end, the server has scanned each input only once, using constant time lookup to find matching rows between the two inputs. For each match, a joined row is sent to the client. ![]() For each row, the server probes the hash table for matching rows using the value from ‘untry_id’ as the lookup key. Once all the rows has been stored in the hash table, the build phase is done.ĭuring the probe phase, the server starts reading rows from the probe input ( ‘persons’ in our example). Since ‘untry_id’ is the join condition that belongs to the build input, this is used as the key in the hash table. Ideally, the server will choose the smaller of the two inputs as the build input (measured in bytes, not number of rows). This input is also known as the build input, and let us assume that ‘countries’ is designated as the build input. In the build phase, the server builds an in-memory hash table where rows from one of the inputs are stored, using the join attribute(s) as the hash table key. The literature usually divides hash join in two phases the build phase and the probe phase.
0 Comments
Leave a Reply. |