Issues with BlockAccess::ba_insert()

SaintNerevar commented 2 years ago

A few modifications

In the part where the rblock is updated for the previous block, blockNum should be replaced by prevBlockNum
I realised that we don't initialize the slot map in the RecBuffer constructor. Doing that would remove the need to do that in ba_insert()
In the loop to find a free slot, we do not need to set SLOT_OCCUPIED because we do that at the end anyway.
In case a free slot is not found, when we update the Last Block, we need to update the first block too in the case the relation is empty at the time of insertion

gokulsreekumar commented 2 years ago

@jessiyajoy please look into it

jessiyajoy commented 2 years ago

A few modifications

I realized that we don't initialize the slot map in the RecBuffer constructor. Doing that would remove the need to do that in ba_insert()

Suggestions for this:

But then shouldn't the header initialization be moved there as well? (As it might be better to keep all the block metadata(header and slot map) initializations in one place)
Also, such metadata initialization only happens in only 2 places(which is BlockAcess::insert() and also in b+ insert since new blocks are allocated only here). And for header even if the constructor initializes the block header with default values like left block = -1; The caller BlockAcess::insert will set the actual values for left block right block etc immediately after returning from the constructor.
And also, maybe the buffer layer need not be concerned about what the metadata/data actually should be in the block. Instead only concern itself with setting the headers, slot map, and record from the data provided to it by higher layers.

jessiyajoy commented 2 years ago

A few modifications

In the loop to find a free slot, we do not need to set SLOT_OCCUPIED because we do that at the end anyway.

In case a free slot is not found, when we update the Last Block, we need to update the first block too in the case the relation is empty at the time of insertion

These issues are corrected in the implementation and will be updated in documentation soon.

jessiyajoy commented 2 years ago

In the part where the rblock is updated for the previous block, blockNum should be replaced by prevBlockNum

Is this correct? Won't blockNum be -1 on exiting the loop? @SaintNerevar

Currently this is being done:

// if prevBlockNum != -1
if (prevBlockNum != -1) {
    // create a RecBuffer object for prevBlockNum(use constructor for existing block)
    // get the header of the block prevBlockNum
    // update the rblock field of the header to the new block number(i.e. rec_id.block)
    // (use BlockBuffer::setHeader() function)
    RecBuffer recBufferForPrevBlock = RecBuffer(prevBlockNum);
    HeadInfo headerForPrevBlock{};
    recBufferForPrevBlock.getHeader(&headerForPrevBlock);
    headerForPrevBlock.rblock = rec_id.block;
    recBufferForPrevBlock.setHeader(&headerForPrevBlock);

} else {
    // update first block field in the relation catalogue entry to the new block
    // (use RelCacheTable::setRelCatEntry() function of Cache Layer)
    relCatEntry.firstBlk = rec_id.block;
    RelCacheTable::setRelCatEntry(relId, &relCatEntry);
}

jessiyajoy commented 2 years ago

Updated Algorithm for BlockAccess::insert Please check it out @SaintNerevar

int BlockAccess::insert(int relId, Attribute *record) {
    // get the relation catalog entry from relation cache
    // ( use RelCacheTable::getRelCatEntry() of Cache Layer)

    // let blockNum denote the first record block of the relation (obtained from relation catalog entry)

    // Let rec_id denote the record id of the slot where the new record will be inserted
    RecId rec_id = {-1, -1};

    // let numOfSlots denote the number of slots per record block (obtained from relation catalog entry)
    // let numOfAttributes denote the number of attributes of the relation (obtained from relation catalog entry)

    // let prevBlockNum denote the block number of the last element in the linked list = -1;

    /*
        Traversing the linked list of existing record blocks of the relation
        until a free slot is found OR
        until the end of the list is reached
    */
    while (blockNum != -1) {
        // create a RecBuffer object for blockNum(use constructor for existing block)

        // get header of block(blockNum) using RecBuffer::getHeader() function

        // get slot map of block(blockNum) using RecBuffer::getSlotMap() function

        // search for free slot in the block 'blockNum' and store it's record id in rec_id
        // (Free slot can be found by iterating over the slot map of the block)
        // slot map stores SLOT_UNOCCUPIED if slot is free and SLOT_OCCUPIED if slot is occupied)

        // if a free slot is found, discontinue the traversal of the linked list of record blocks

        // otherwise, continue to check the next block by updating the block numebers as follows:
        // update prevBlockNum = blockNum
        // update blockNum = header.rblock (next element in the linked list of record blocks)
    }

    //  if no free slot is found in existing record blocks
    {
        // if relation is RELCAT, do not allocate any more blocks (i.e. if relId = RELCAT_RELID)
        //      return E_MAXRELATIONS;

        // Otherwise,
        // get a new record block by calling RecBuffer Constructor for new block
        // get the block number of the newly allocated block
        // (use BlockBuffer::getBlockNum() function)
        // let ret be the return value of getBlockNum() function call
        if (ret == E_DISKFULL) {
            // disk is full
            return E_DISKFULL;
        }

        // Assign rec_id.block = new block number(i.e. ret) and rec_id.slot = 0

        /*
            set the header of the new record block such that it links with existing record blocks of the relation
            set the block's header as follows:
            blockType: REC, pblock: -1
            lblock
                    = -1 (if linked list of existing record blocks was empty)
                    = prevBlockNum (otherwise),
            rblock: -1, numEntries: 0,
            numSlots: numOfSlots, numAttrs: numOfAttributes
            (use BlockBuffer::setHeader() function)
        */

        /*
            set block's slot map with all slots marked as free
            (i.e. store SLOT_UNOCCUPIED for all the entries)
            (use RecBuffer::setSlotMap() function)
        */

        // if prevBlockNum != -1 
        {
            // create a RecBuffer object for prevBlockNum(use constructor for existing block)
            // get the header of the block prevBlockNum
            // update the rblock field of the header to the new block number(i.e. rec_id.block)
            // (use BlockBuffer::setHeader() function)
        }
        // else
        {
            // update first block field in the relation catalogue entry to the new block(i.e. rec_id.block)
            // (use RelCacheTable::setRelCatEntry() function of Cache Layer)
        }

        // update last block field in the relation catalogue entry to the new block(i.e. rec_id.block)
        // (use RelCacheTable::setRelCatEntry() function of Cache Layer)
    }

    // create a RecBuffer object for rec_id.block(use constructor for existing block)
    // insert the record into rec_id'th slot by calling RecBuffer::setRecord() function)

    // update the slot map of the block by marking entry of the slot to which record was inserted as occupied)
    // (ie store SLOT_OCCUPIED in free_slot'th entry of slot map)
    // (use RecBuffer::getSlotMap() and RecBuffer::setSlotMap() functions)

    // increment the num_entries field in the header of the block (to which record was inserted)
    // (use BlockBuffer::getHeader() and BlockBuffer::setHeader() functions)

    // Increment the number of records field in the relation cache entry for the relation.
    // (use RelCacheTable::setRelCatEntry function)

    /*
        B+ tree insertions
     */
    // Let flag = SUCCESS
    flag = SUCCESS;
    // Iterate over all the attributes of the relation
    // Let attrOffset be iterator ranging from 0 to numOfAttributes-1
    {
        // get the attribute catalog entry for the attribute from the attribute cache
        // (use AttrCacheTable::getAttrCatEntry() function with arguments relId and attrOffset)

        // get the root block field from the attribute catalog entry

        // if index exists for the attribute(i.e. rootBlock != -1)
        {
            // TODO: Update once BPlus Layer algorithms are completed
            // BPlusTree bPlusTree = BPlusTree(relId, attrName);
            // int retVal = bPlusTree.bPlusInsert(record[attrOffset], rec_id);
            // if (retVal == E_DISKFULL) {
            // delete the b+ tree for the attribute using ? function

            // flag = E_INDEX_BLOCKS_RELEASED
        }
    }

    //  return flag;
}

SaintNerevar commented 2 years ago

All good!

NITCbase / nitcbase.github.io

Issues with BlockAccess::ba_insert() #44