LhxHashTable.h

Go to the documentation of this file.

/*
// $Id: //open/dev/fennel/hashexe/LhxHashTable.h#4 $
// Fennel is a library of data storage and processing components.
// Copyright (C) 2006-2009 The Eigenbase Project
// Copyright (C) 2009-2009 SQLstream, Inc.
// Copyright (C) 2006-2009 LucidEra, Inc.
//
// This program is free software; you can redistribute it and/or modify it
// under the terms of the GNU General Public License as published by the Free
// Software Foundation; either version 2 of the License, or (at your option)
// any later version approved by The Eigenbase Project.
//
// This program is distributed in the hope that it will be useful,
// but WITHOUT ANY WARRANTY; without even the implied warranty of
// MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
// GNU General Public License for more details.
//
// You should have received a copy of the GNU General Public License
// along with this program; if not, write to the Free Software
// Foundation, Inc., 59 Temple Place, Suite 330, Boston, MA  02111-1307  USA
*/

#ifndef Fennel_LhxHashTable_Included
#define Fennel_LhxHashTable_Included

#include "fennel/hashexe/LhxHashGenerator.h"
#include "fennel/tuple/TupleData.h"
#include "fennel/tuple/TupleDataWithBuffer.h"
#include "fennel/tuple/TupleDescriptor.h"
#include "fennel/tuple/TupleAccessor.h"
#include "fennel/tuple/TupleProjectionAccessor.h"
#include "fennel/segment/SegPageLock.h"
#include "fennel/hashexe/LhxHashBase.h"
#include "fennel/exec/AggComputer.h"
#include "fennel/common/FennelExcn.h"
#include "fennel/tuple/TupleOverflowExcn.h"

#include "math.h"

using namespace std;

FENNEL_BEGIN_NAMESPACE

// REVIEW jvs 25-Aug-2006:  This class comment is misplaced.  And
// the other classes could use some comments to explain their purpose
// (or else a reference to a doc with structure diagrams).

class FENNEL_HASHEXE_EXPORT LhxHashNodeAccessor
{
    // REVIEW jvs 25-Aug-2006: These should be doxygen comments.

    /*
     * Offset to the field storing the pointer to the next node.
     */
    uint nextNodeOffset;

    /*
     * Offset to the buffer storing the payload of this node.
     */
    uint nodeBufferOffset;

    /*
     * Node that is currently associated with this accessor.
     */
    PBuffer nodePtr;

public:

    // REVIEW jvs 25-Aug-2006: Fennel convention is to use the keyword
    // "explict" for all constructors, except where implicit conversion is
    // actually desired.  For example, the second constructor here means that a
    // uint can silently be converted into a LhxHasNodeAccessor, which is
    // almost certainly not what one would ever want.  Same comment
    // applies everywhere.

    LhxHashNodeAccessor();

    LhxHashNodeAccessor(uint nextNodeOffsetInit);

    PBuffer getCurrent();

    void setCurrent(PBuffer nodePtrInit);

    void reset();

    PBuffer getBuffer();

    PBuffer getNext();

    PBuffer getNextLocation();

    void setNext(PBuffer nextNode);

    void setNext(PBuffer inputNode, PBuffer nextNode);

    uint getNextFieldSize();

    // REVIEW jvs 25-Aug-2006: offset to the...what?

    uint getBufferOffset();
};

// REVIEW jvs 25-Aug-2006: Seems like a lot of duplication between
// LhxHashKeyAccessor and LhxHashDataAccessor; maybe it's unavoidable.

class FENNEL_HASHEXE_EXPORT LhxHashDataAccessor
    : public LhxHashNodeAccessor
{
    /*
     * Shape of the data tuple stored.
     */
    TupleDescriptor dataDescriptor;

    /*
     * Temporary tuple for holding the unmarshaled data.
     */
    TupleData dataTuple;

    /*
     * Accessor for the data tuple stored.
     */
    TupleAccessor dataAccessor;

public:
    LhxHashDataAccessor() : LhxHashNodeAccessor() {}

    void init(TupleDescriptor const &inputDataDesc);

    void setCurrent(PBuffer nodePtrInit, bool valid);

    inline uint getAvgStorageSize();

    // REVIEW jvs 25-Aug-2006: what's the distinction between
    // buffer size and disk size?  I think buffer size accounts
    // for the in-memory overhead of the hash table pointers,
    // but it would be nice if that were spelled out here.

    inline uint getStorageSize(TupleData const &inputTuple);

    inline uint getDiskStorageSize(TupleData const &inputTuple);

    inline void checkStorageSize(
        TupleData const &inputTuple,
        uint maxBufferSize);

    inline void pack(TupleData const &inputTuple);

    void unpack(TupleData &outputTuple, TupleProjection &destProj);

    string toString();
};

class FENNEL_HASHEXE_EXPORT LhxHashKeyAccessor
    : public LhxHashNodeAccessor
{
    /*
     * Offsets to the fields in the node
     */
    uint firstDataOffset;

    /*
     * Offset to "matched" indicator. This indicator is used in both anti join
     * and duplicate removal during set operations(semi join).
     */
    uint isMatchedOffset;

    /*
     * Offset to keys in the next slot.
     */
    uint nextSlotOffset;

    /*
     * Shape of the data tuple stored.
     */
    TupleDescriptor keyDescriptor;

    /*
     * Temporary tuple for holding the unmarshaled data.
     */
    TupleData keyTuple;

    /*
     * Accessor for the data tuple stored.
     */
    TupleAccessor keyAccessor;

    /*
     * Projection containing the key cols
     */
    TupleProjection keyColsProj;

    TupleDescriptor keyColsDesc;

    /*
     * Projection containing the aggregate columns
     */
    TupleProjection aggsProj;

    /*
     * Temp data used to project input key tuple.
     */
    TupleData inputKey;

    /*
     * Temp data used to project stored key tuple in the hash table.
     */
    TupleData currentKey;

    /*
     * Temp data accessor for inserting new data fragments.
     */
    LhxHashDataAccessor firstData;

public:
    LhxHashKeyAccessor();

    void init(
        TupleDescriptor const &keyDescInit,
        TupleProjection const &keyColsProjInit,
        TupleProjection const &aggsProjInit);

    void setCurrent(PBuffer nodePtrInit, bool valid);

    inline PBuffer getFirstData();

    inline void setFirstData(PBuffer inputFirstData);

    inline PBuffer *getNextSlot();

    inline void setNextSlot(PBuffer *nextSlot);

    inline bool isMatched();

    inline void setMatched(bool matched);

    void addData(PBuffer inputData);

    inline uint getAvgStorageSize();

    inline uint getStorageSize(TupleData const &inputTuple);

    inline uint getDiskStorageSize(TupleData const &inputTuple);

    inline void checkStorageSize(
        TupleData const &inputTuple,
        uint maxBufferSize);

    inline void pack(TupleData const &inputTuple);

    void unpack(TupleData &outputTuple, TupleProjection &destProj);

    /*
     * Compare if inputTuple has the same key.
     *
     * @param [in] inputTuple
     * @param [out] inputKeyProj the key fields.
     */
    bool matches(
        TupleData const &inputTuple,
        TupleProjection const &inputKeyProj);

    string toString();
};

class FENNEL_HASHEXE_EXPORT LhxHashBlockAccessor
    : public LhxHashNodeAccessor
{
    uint blockUsableSize;

    uint numSlotsPerBlock;

    PBuffer freePtr;

    PBuffer endPtr;

public:
    LhxHashBlockAccessor() : LhxHashNodeAccessor()
    {
    }

    void init(uint usablePageSize);

    void setCurrent(PBuffer blockPtrInit, bool valid, bool clearContent);

    void reset();

    uint getUsableSize()
    {
        return blockUsableSize;
    }

    uint getSlotsPerBlock()
    {
        return numSlotsPerBlock;
    }

    PBuffer allocBuffer(uint bufSize);

    /*
     * Allocate slots. A slot is a pointer to a hash key. There is no boundary
     * check as the number of slots that can fit into a block is calculated
     * beforehand.
     *
     * @param [in] slotCount number of slots to allocate.
     */
    void allocSlots(uint slotCount = 1);

    PBuffer *getSlot(uint slotNum);
};

class FENNEL_HASHEXE_EXPORT LhxHashTable
{
    /*
     * Inputs to LhxHashTable
     */

    uint numSlots;

    std::vector<PBuffer> slotBlocks;

    PBuffer *firstSlot;
    PBuffer *lastSlot;

    SegmentAccessor scratchAccessor;

    uint maxBlockCount;


    /*
     * Storage for the hash table.
     */

    PBuffer firstBlock;

    PBuffer currentBlock;

    LhxHashBlockAccessor blockAccessor;

    LhxHashBlockAccessor nodeBlockAccessor;

    SegPageLock bufferLock;

    uint  currentBlockCount;

    bool filterNull;
    TupleProjection filterNullKeyProj;

    bool removeDuplicate;

    // TODO rchen fix doxygen comments

    uint partitionLevel;
    LhxHashGenerator hashGen;
    LhxHashGenerator hashGenSub;

    TupleProjection keyColsAndAggsProj;
    TupleProjection keyColsProj;
    TupleProjection aggsProj;
    TupleProjection dataProj;
    vector<LhxHashTrim> isKeyColVarChar;

    LhxHashKeyAccessor hashKeyAccessor;
    LhxHashDataAccessor hashDataAccessor;

    uint maxBufferSize;

    bool isGroupBy;

    bool hasAggregates;

    AggComputerList *aggComputers;
    TupleData aggWorkingTuple;

    TupleDataWithBuffer aggResultTuple;

    PBuffer allocBlock();

    PBuffer allocBuffer(uint bufSize);

    string printSlot(uint slotNum);

    bool addKeyData(TupleData const &inputTuple);

    bool addData(PBuffer keyNode, TupleData const &inputTuple);

    bool aggData(PBuffer destKeyLoc, TupleData const &inputTuple);

    static inline uint slotsNeeded(RecordNum cndKeys);

    PBuffer findKeyLocation(
        TupleData const &inputTuple,
        TupleProjection const &inputKeyProj,
        bool isProbing,
        bool removeDuplicateProbe);

    TupleData tmpKeyTuple;
    TupleData tmpDataTuple;

public:

    // REVIEW jvs 25-Aug-2006:  No need to repeat LhxHashTable qualifier
    // in name here; Fennel convention should be something like
    // MIN_SCRATCH_PAGES.  Same comment applies elsewhere
    // (e.g. LhxSubPartCount).
    static const uint LhxHashTableMinPages = 2;

    void init(
        uint partitionLevelInit,
        LhxHashInfo const &hashInfo,
        AggComputerList *aggList,
        uint buildInputIndex);

    void init(
        uint partitionLevelInit,
        LhxHashInfo const &hashInfo,
        uint buildInputIndex);

    // REVIEW jvs 25-Aug-2006:  Every place this is called, the caller
    // asserts that the return code is true.  So, it would probably
    // be better to return void, and fail inside of this method.  In
    // particular, this is a rather serious error if it occurs, so
    // probably use permAssert or permFail so that it will fail-fast
    // in an optimized build too.
    bool allocateResources(bool reuse = false);

    void releaseResources(bool reuse = false);

    void calculateSize(
        LhxHashInfo const &hashInfo,
        uint inputIndex,
        BlockNum &numBlocks);

    void calculateNumSlots(
        RecordNum cndKeys,
        uint usablePageSize,
        BlockNum numBlocks);

    PBuffer findKey(
        TupleData const &inputTuple,
        TupleProjection const &inputKeyProj,
        bool removeDuplicateProbe);

    bool addTuple(TupleData const &inputTuple);

    PBuffer *getSlot(uint slotNum);

    inline uint getNumSlots() const;

    inline PBuffer *getFirstSlot() const;

    inline PBuffer *getNextSlot(PBuffer *curSlot);

    inline bool isHashGroupBy() const;

    string toString();
};

class FENNEL_HASHEXE_EXPORT LhxHashTableReader
{
    LhxHashTable *hashTable;

    // REVIEW jvs 25-Aug-2006: Can't this be derived from hashTable->isGroupBy?
    bool isGroupBy;

    PBuffer *curSlot;
    PBuffer curKey;
    PBuffer curData;

    // REVIEW jvs 25-Aug-2006: Matching key means matching the key
    // marshalled in boundKey?  Or is it a node pointer?
    PBuffer boundKey;

    bool returnUnMatched;

    bool isPositioned;

    LhxHashKeyAccessor hashKeyAccessor;
    LhxHashDataAccessor hashDataAccessor;

    // REVIEW jvs 25-Aug-2006: Aren't these also redundant with
    // corresponding fields in hashTable?
    TupleProjection keyColsAndAggsProj;
    TupleProjection dataProj;

    bool advanceSlot();

    bool advanceKey();

    bool advanceData();

    void produceTuple(TupleData &outputTuple);

    inline void bind(PBuffer key);

public:
    void init(
        LhxHashTable *hashTableInit,
        LhxHashInfo const &hashInfo,
        uint buildInputIndex);

    inline void bindKey(PBuffer key);

    inline void bindUnMatched();

    bool getNext(TupleData &outputTuple);

    inline LhxHashTable *getHashTable();
};

inline LhxHashNodeAccessor::LhxHashNodeAccessor()
{
    nextNodeOffset = 0;
    nodeBufferOffset = nextNodeOffset + getNextFieldSize();
}

inline LhxHashNodeAccessor::LhxHashNodeAccessor(uint nextNodeOffsetInit)
{
    nextNodeOffset = nextNodeOffsetInit;
    nodeBufferOffset = nextNodeOffset + getNextFieldSize();
}

inline PBuffer LhxHashNodeAccessor::getCurrent()
{
    return nodePtr;
}

inline PBuffer LhxHashNodeAccessor::getBuffer()
{
    return (nodePtr + nodeBufferOffset);
}

inline void LhxHashNodeAccessor::setCurrent(PBuffer nodePtrInit)
{
    nodePtr = nodePtrInit;
}

inline void LhxHashNodeAccessor::reset()
{
    setCurrent(NULL);
}

inline PBuffer LhxHashNodeAccessor::getNext()
{
    // REVIEW jvs 25-Aug-2006:  Under what circumstances would
    // alignment be off?  Tuple sizes are always aligned.  Is it
    // because of the match indicator?  If so, it might make sense to
    // fold that into the tuple.
    /*
     * nodePtr+nextNodeOffset might not be aligned so copy the pointer
     * value out.
     */
    PBuffer returnPtr;
    memcpy((PBuffer)&returnPtr, nodePtr+nextNodeOffset, sizeof(PBuffer));
    return returnPtr;
}

inline PBuffer LhxHashNodeAccessor::getNextLocation()
{
    return nodePtr + nextNodeOffset;
}

inline void LhxHashNodeAccessor::setNext(PBuffer nextNode)
{
    memcpy(nodePtr+nextNodeOffset, (PBuffer)&nextNode, getNextFieldSize());
}

inline void LhxHashNodeAccessor::setNext(PBuffer inputNode, PBuffer nextNode)
{
    memcpy(inputNode+nextNodeOffset, (PBuffer)&nextNode, getNextFieldSize());
}

inline uint LhxHashNodeAccessor::getNextFieldSize()
{
    return sizeof(PBuffer);
}

inline uint LhxHashNodeAccessor::getBufferOffset()
{
    return nodeBufferOffset;
}

inline void LhxHashDataAccessor::setCurrent(PBuffer nodePtrInit, bool valid)
{
    LhxHashNodeAccessor::setCurrent(nodePtrInit);
    dataAccessor.setCurrentTupleBuf(getBuffer(), valid);
}

inline uint LhxHashDataAccessor::getAvgStorageSize()
{
    // compute the average based on the min and max
    // TODO - use stats to compute a more realistic average
    return
        ((dataAccessor.getMaxByteCount() +
            dataAccessor.getMinByteCount()) / 2) +
        getBufferOffset();
}

inline uint LhxHashDataAccessor::getStorageSize(TupleData const &inputTuple)
{
    return dataAccessor.getByteCount(inputTuple) + getBufferOffset();
}

inline uint LhxHashDataAccessor::getDiskStorageSize(
    TupleData const &inputTuple)
{
    return dataAccessor.getByteCount(inputTuple);
}

inline void LhxHashDataAccessor::checkStorageSize(
    TupleData const &inputTuple,
    uint maxBufferSize)
{
    uint storageSize = getStorageSize(inputTuple);

    if (storageSize > maxBufferSize) {
        throw TupleOverflowExcn(
            dataDescriptor,
            inputTuple,
            storageSize,
            maxBufferSize);
    }
}

inline void LhxHashKeyAccessor::pack(TupleData const &inputTuple)
{
    PBuffer buf = getBuffer();

    assert(buf != NULL && inputTuple.size() == keyAccessor.size());

    /*
     * Copy the input tuple into the buffer associated with this accessor.
     */
     keyAccessor.marshal(inputTuple, buf);
}

inline void LhxHashDataAccessor::pack(
    TupleData const &inputTuple)
{
    PBuffer buf = getBuffer();

    assert(buf != NULL && inputTuple.size() == dataAccessor.size());

    /*
     * Copy the input tuple into the buffer associated with this accessor.
     */
    dataAccessor.marshal(inputTuple, buf);
}

inline void LhxHashKeyAccessor::setCurrent(PBuffer nodePtrInit, bool valid)
{
    LhxHashNodeAccessor::setCurrent(nodePtrInit);
    keyAccessor.setCurrentTupleBuf(getBuffer(), valid);
}

inline uint LhxHashKeyAccessor::getAvgStorageSize()
{
    return
        ((keyAccessor.getMaxByteCount() + keyAccessor.getMinByteCount()) / 2) +
        getBufferOffset();
}

inline uint LhxHashKeyAccessor::getStorageSize(TupleData const &inputTuple)
{
    return keyAccessor.getByteCount(inputTuple) + getBufferOffset();
}

inline uint LhxHashKeyAccessor::getDiskStorageSize(TupleData const &inputTuple)
{
    return keyAccessor.getByteCount(inputTuple);
}

inline PBuffer LhxHashKeyAccessor::getFirstData()
{
    PBuffer returnPtr;
    memcpy(
        (PBuffer) &returnPtr,
        (PBuffer) (getCurrent() + firstDataOffset),
        sizeof(PBuffer));
    return returnPtr;
}

inline void LhxHashKeyAccessor::setFirstData(PBuffer inputFirstData)
{
    memcpy(
        (PBuffer)(getCurrent() + firstDataOffset),
        (PBuffer)&inputFirstData,
        sizeof(PBuffer));
}

inline PBuffer *LhxHashKeyAccessor::getNextSlot()
{
    PBuffer *returnPtr;
    memcpy(
        (PBuffer) &returnPtr,
        (PBuffer) (getCurrent() + nextSlotOffset),
        sizeof(PBuffer *));
    return returnPtr;
}

inline void LhxHashKeyAccessor::setNextSlot(PBuffer *nextSlot)
{
    memcpy(
        (PBuffer)(getCurrent() + nextSlotOffset),
        (PBuffer)&nextSlot,
        sizeof(PBuffer*));
}

inline bool LhxHashKeyAccessor::isMatched()
{
    return (*(uint8_t *)(getCurrent() + isMatchedOffset) == 1);
}

inline void LhxHashKeyAccessor::setMatched(bool matched)
{
    *(getCurrent() + isMatchedOffset) = (matched ? 0x01 : 0);
}

inline void LhxHashKeyAccessor::checkStorageSize(
    TupleData const &inputTuple,
    uint maxBufferSize)
{
    uint storageSize = getStorageSize(inputTuple);

    if (storageSize > maxBufferSize) {
        throw TupleOverflowExcn(
            keyDescriptor,
            inputTuple,
            storageSize,
            maxBufferSize);
    }
}

inline void LhxHashBlockAccessor::reset()
{
    LhxHashNodeAccessor::reset();
    freePtr = endPtr = NULL;
}

inline void LhxHashBlockAccessor::allocSlots(uint slotCount)
{
    /*
     * A slot is a pointer to a hash key.
     */
    PBuffer bufPtr = allocBuffer(slotCount * sizeof(PBuffer));
    assert (bufPtr != NULL);
}

inline uint LhxHashTable::slotsNeeded(RecordNum cndKeys)
{
    RecordNum cKeys = RecordNum(ceil(cndKeys * 1.2));
    if (cKeys >= uint(MAXU)) {
        return uint(MAXU) - 1;
    } else {
        return uint(cKeys);
    }
}

inline uint LhxHashTable::getNumSlots() const
{
    return numSlots;
}

inline PBuffer *LhxHashTable::getFirstSlot() const
{
    return firstSlot;
}

inline PBuffer *LhxHashTable::getNextSlot(PBuffer *curSlot)
{
    hashKeyAccessor.setCurrent((*curSlot), true);
    return hashKeyAccessor.getNextSlot();
}

inline bool LhxHashTable::isHashGroupBy() const
{
    return isGroupBy;
}

inline LhxHashTable *LhxHashTableReader::getHashTable()
{
    return hashTable;
}

inline void LhxHashTableReader::bind(PBuffer key)
{
    boundKey = curKey = key;
    curSlot = NULL;
    curData = NULL;
    isPositioned = false;
}

inline void LhxHashTableReader::bindKey(PBuffer key)
{
    returnUnMatched = false;
    bind(key);
}

inline void LhxHashTableReader::bindUnMatched()
{
    returnUnMatched = true;
    bind(NULL);
}

FENNEL_END_NAMESPACE

#endif

// End LhxHashTable.h

---