hashjoin 源码

hashjoin 是一种常用的关系型数据库的查询算法，用于将两个表中共同的列进行匹配并连接起来。具体实现可以参考 PostgreSQL 数据库中的代码实现。

在 PostgreSQL 中，hashjoin 的实现主要包括三个部分：构建哈希表、扫描哈希表和匹配结果。

构建哈希表：

static HashJoinTable
ExecHashTableCreate(PlanState *parent,
                    List *hashOperators, /* hash function to use for each join key */
                    long nbuckets,      /* # buckets in hashtable */
                    Size entrysize,     /* size of each entry in hashtable */
                    bool use_variable_hash_iv)
{
    HashJoinTable hashtable;
    int            nbuckets_est = nbuckets;
    int            log2_nbuckets;

    /* Limit nbuckets to at most INT_MAX; must do this before sizing to power of 2 */
    if ((double) nbuckets_est * (double) entrysize > (double) INT_MAX)
        nbuckets_est = (int) floor((double) INT_MAX / (double) entrysize);
    /* Size hash table to a power of 2 */
    log2_nbuckets = my_log2(nbuckets_est);
    hashtable = (HashJoinTable) palloc0(HJTUPLE_OVERHEAD +
                                         sizeof(HashJoinTableData) +
                                         (entrysize * (1 << log2_nbuckets)));
    hashtable->nbuckets = nbuckets_est;
    hashtable->log2_nbuckets = log2_nbuckets;
    hashtable->buckets = (HashJoinTuple *)
        (((char *) hashtable) + HJTUPLE_OVERHEAD + sizeof(HashJoinTableData));
    hashtable->hash_iv = GetPerTupleExprContext(parent)->ecxt_hashjoin_outer;

    /* Initialize all hash bucket headers to empty */
    MemSet(hashtable->buckets, 0, sizeof(HashJoinTuple) << log2_nbuckets);

    /* Set up array containing OIDs of hash operators */
    ExecChooseHashFuncs(hashOperators,
                        hashtable->hashfunctions,
                        hashtable->nbuckets,
                        use_variable_hash_iv);

    return hashtable;
}

扫描哈希表：

static TupleTableSlot *
ExecScanHashBucket(HashJoinState *hjstate,
                   ExprContext *econtext)
{
    HashJoinTable hashtable = hjstate->hj_HashTable;
    AttrNumber *hj_OuterHashKeys = hjstate->hj_OuterHashKeys;
    TupleTableSlot *innerTupleSlot = hjstate->hj_InnerTupleSlot;
    TupleTableSlot *outerTupleSlot = hjstate->hj_OuterTupleSlot;
    HashJoinTuple hashTuple;
    uint32 hashvalue;
    int bucketno;

    /* loop until we find a join tuple */
    for (;;)
    {
        hashvalue = ExecHashGetBucket(hjstate, hashtable,
                                      hj_OuterHashKeys,
                                      econtext,
                                      false);
        bucketno = ExecHashGetBucketNumber(hashvalue, hashtable->log2_nbuckets);

        /*
         * Scan the bucket for matching tuples.
         */
        for (hashTuple = hashtable->buckets[bucketno];
             hashTuple != NULL;
             hashTuple = hashTuple->next)
        {
            if (hashTuple->hashvalue != hashvalue)
                continue;

            /* Found a match?  Then report and save tuple */
            if (ExecQualAndReset(hashTuple->hashressupport, econtext))
            {
                /* save the matching tuple */
                ExecStoreMinimalTuple(HJTUPLE_MINTUPLE(hashTuple),
                                      innerTupleSlot,
                                      false);
                /* set up for next join tuple, if any */
                hjstate->hj_CurHashValue = hashvalue;
                hjstate->hj_CurBucketNo = bucketno;
                return outerTupleSlot;
            }
        }

        /*
         * No match in this bucket; check for additional matches in outer
         * batches.
         */
        if (!ExecScanHashTableForUnmatched(hjstate, econtext))
            return NULL;    /* need new outer tuple */
    }
}

匹配结果：

static TupleTableSlot *
ExecHashJoin(HashJoinState *node)
{
    PlanState  *outerNode = outerPlanState(node);
    HashJoinTable hashtable = node->hj_HashTable;
    TupleTableSlot *innerTupleSlot = node->hj_InnerTupleSlot;
    TupleTableSlot *outerTupleSlot = node->hj_OuterTupleSlot;
    ExprContext *econtext = node->js.ps.ps_ExprContext;
    TupleTableSlot *result;
    MinimalTuple tuple;

    /*
     * Reset per-tuple memory context to free any expression evaluation
     * storage allocated in the previous tuple cycle.
     */
    ResetExprContext(econtext);

    /*
     * if first time through, read all inner tuples into hashtable
     */
    if (!node->hj_CurHashValue)
    {
        /* Reset hash table to empty */
        ExecHashTableReset(hashtable);

        /* Load hashtable with inner tuples */
        ExecHashJoinNewBatch(node);

        /* If inner relation is completely empty, return no rows */
        if (hashtable->totalTuples == 0)
            return NULL;
    }

    /*
     * We read the outer tuple in the previous iteration, which means that we
     * have to check for additional join matches for it before continuing.
     */
    if (node->hj_JoinState == HJ_NEED_NEW_OUTER)
    {
        if (!ExecScanHashTableForUnmatched(node, econtext))
            return NULL;    /* need new outer tuple */
    }

    /*
     * Now check for any matches
     */
    for (;;)
    {
        /*
         * If we've run out of inner tuples, then the current outer tuple
         * can't have a match, so we're done with it.
         */
        if (node->hj_CurTuple == NULL)
        {
            if (!ExecScanHashTableForUnmatched(node, econtext))
                break;      /* need new outer tuple */

            continue;       /* search next hash bucket */
        }

        /*
         * Check for join match.
         */
        if (ExecQual(node->js.ps.qual, econtext))
        {
            /*
             * qualification was satisfied so we project and return the
             * slot containing joined tuples, making sure that the slot is
             * labeled with the join's rowtype.
             */
            ExecProject(node->js.ps.ps_ProjInfo);
            result = node->js.ps.ps_ProjInfo->pi_slot;

            /*
             * We return the first (and only) qualifying join tuple.  The
             * executor doesn't support the idea of generating multiple
             * join rows from one outer tuple when there are multiple
             * matching inner tuples (compare the semantics of a nested
             * loops join).
             */
            if (hashtable->nbatch == 1)
            {
                /* In single-batch case, just return the result */
                return result;
            }
            else
            {
                /*
                 * Before returning the first join tuple, force the
                 * other tuples in the same join group to be fetched and
                 * appended to the result list.
                 */
                tuple = ExecFetchSlotMinimalTuple(innerTupleSlot);
                ExecHashTableMarkCurBucket(hjstate);
                ExecHashTableGetBucketAndBatch(hashtable,
                                               node->hj_CurHashValue,
                                               &node->hj_CurBucketNo,
                                               &node->hj_CurTuple,
                                               &node->hj_CurBucketBuf);

                /*
                 * Set the next tuple to return, if any.  Done in this order
                 * so that if there is only one tuple in the group, we don't
                 * advance the pointers at all.
                 */
                if (node->hj_CurTuple != NULL)
                    node->hj_NextTuple = node->hj_CurTuple->next;
                else
                    node->hj_NextTuple = NULL;

                /* Remember there's a join tuple available */
                node->hj_JoinState = HJ_NEED_NEW_OUTER;

                /* And return the first tuple */
                return result;
            }
        }

        /*
         * Didn't match this time.  Try next tuple in inner relation.
         */
        node->hj_CurTuple = node->hj_CurTuple->next;
    }

    /*
     * no more matches
     */
    return NULL;
}

以上代码是 PostgreSQL 中 hashjoin 的基本实现，可以作为参考。