Issues with BlockAccess::ba_linearSearch()

[SaintNerevar]

There are a few modifications to be made to the algorithm

• slot = previous record id's slot + 1
• Add the while loop around the part that loops
• Make use of return values E_OUTOFBOUND and E_FREESLOT of getRecord() to get the next slot and block. Change to next block on getting E_OUTOFBOUND and break the loop on getting E_FREESLOT
• Mention how to get attribute offset from attribute name
• Replace OpenRelTable::setPrevRecId() with RelCacheTable::setSearchIndex()

[jessiyajoy]

Linear search function was mistakenly not synced from the implementation repo to documentation. The updated algorithm for ba_linearSearch has now been pushed to doc website. Please check it out @SaintNerevar.

slot = previous record id's slot + 1 -> DONE

Add the while loop around the part that loops -> DONE

Make use of return values E_OUTOFBOUND and E_FREESLOT of getRecord() to get the next slot and block. Change to next block on getting E_OUTOFBOUND and break the loop on getting E_FREESLOT --- The same functionality is explicitly done using slot map and right block field of header.

E_OUTOFBOUND can be used but it is returned in 2 cases from the getRecord function

• when block number is invalid
• when slot number is invalid This might make it hard to understand if the current slot is the last slot + 1 or if the block is invalid(right block of the last linked list element)

Mention how to get attribute offset from attribute name -> DONE

Replace OpenRelTable::setPrevRecId() with RelCacheTable::setSearchIndex() -> DONE

[SaintNerevar]

This might make it hard to understand if the current slot is the last slot + 1 or if the block is invalid(right block of the last linked list element)

This actually isn't a problem if the loop checks for block number != -1. Then inside the loop, the only other possibility is slot number being last slot + 1. I think it makes the algorithm simpler. As for breaking the loop on getting E_FREESLOT, I realized it's wrong because the Catalogs can have gaps in between the records. So we just increase the slot number and continue. I have attached my implementation for clarity. Check it out and tell me if it's more understandable

// Get the current search index
  RecId currSearchIndex;
  RelCacheTable::getSearchIndex(relId, &currSearchIndex);

  // Set the block, slot based on whether current search index exists
  int block, slot;
  if (currSearchIndex.block == -1 && currSearchIndex.slot == -1) {
    RelCatEntry relCatEntry;
    RelCacheTable::getRelCatEntry(relId, &relCatEntry);
    block = relCatEntry.firstBlk;
    slot = 0;
  } else {
    block = currSearchIndex.block;
    slot = currSearchIndex.slot + 1;
  }

  // Loop to find the next hit based on attrval.
  while (block != -1) {    // This works even when there are no records in the relation
    RecBuffer recBuffer{block};
    Attribute record[6];
    int retval;
    retval = recBuffer.getRecord(record, slot);

    if (retval == E_FREESLOT) {
      slot++;
      continue;
    }

    if (retval == E_OUTOFBOUND) {
      HeadInfo header;
      recBuffer.getHeader(&header);
      block = header.rblock;
      slot = 0;
      continue;
    }

    int cond = 0;

    AttrCatEntry attrCatEntry;
    AttrCacheTable::getAttrCatEntry(relId, attrName, &attrCatEntry);
    int offset = attrCatEntry.offset;
    int attrType = attrCatEntry.attrType;

    int flag = compare(attrval, record[offset], attrType);

    switch (op) {
      case NE:
        if (flag != 0) cond = 1;
        break;

      case LT:
        if (flag < 0) cond = 1;
        break;

      case LE:
        if (flag <= 0) cond = 1;
        break;

      case GT:
        if (flag > 0) cond = 1;
        break;

      case GE:
        if (flag >= 0) cond = 1;
        break;

      case EQ:
        if (flag == 0) cond = 1;
        break;
    }

    if (cond == 1) {
      RecId recId{block, slot};
      RelCacheTable::setSearchIndex(relId, &recId);
      return recId;
    }

    slot++;
  }

  // No hits
  return RecId{-1, -1};

[jessiyajoy]

This seems more clear. Will update the algorithm this way.

[SaintNerevar]

I just realised that there is an error in my impementation in https://github.com/Nitcbase/nitcbase-documentation-v2-code/issues/42#issuecomment-1108790547.

Attribute record[6] is wrong. It should be Attribute record[#Attributes]. This should also be noted in the algorithm. We need to get the #Attributes from RelCacheTable beforehand.

[SaintNerevar]

Also, RST and PRJCT operators are not mentioned in the algorithm. These are referenced in the Arguments section and in ba_search()

[jessiyajoy]

Updated Algorithm for linearSearch: Please check it out @SaintNerevar

RecId BlockAccess::linearSearch(int relId, char attrName[ATTR_SIZE], union Attribute attrVal, int op) {
    // get the previous search index of the relation relId from the relation cache
    // (use RelCacheTable::getSearchIndex() function)

    // let block and slot denote the record id of the record being currently checked

    // if the current search index record is invalid(i.e. both block and slot = -1)
    if (prevRecId.block == -1 && prevRecId.slot == -1)
    {
        // (no hits from previous search; search should start from the first record itself)

        // get the first record block of the relation from the relation cache
        // (use RelCacheTable::getRelCatEntry() function of Cache Layer)

        // block = first record block of the relation
        // slot = 0
    }
    else 
    {
        //  (there is a hit from previous search; search should start from the record next to the search index record)

        // block = search index's block
        // slot = search index's slot + 1
    }

    // The following code searches for the next record in the relation that satisfies the given condition
    // Start from the record id (block, slot) and iterate over the remaining records of the relation
    while (block != -1)
    {

        // create a RecBuffer object for block (use RecBuffer Constructor for existing block)

        // get the record with id (block, slot) using RecBuffer::getRecord() function
        // get header of the block using RecBuffer::getHeader() function
        // get slot map of the block using RecBuffer::getSlotMap() function

        // If slot >= the number of slots per block(i.e. no more slots in this block)
        {
            // update block = right block of block
            // update slot = 0
        }

        // if slot is free skip the loop
        // (i.e. check if slot'th entry in slot map of block contains SLOT_UNOCCUPIED)
        {
            // and continue to the next record slot
            // (i.e. increment slot and continue)
        }

        // let cond be a variable of int type

        if ( op != PRJCT ) 
        {
            // compare record's attribute value to the the given attrVal as below:
            /*
                firstly get the attribute offset for the attrName attribute
                from the attribute cache entry of the relation using AttrCacheTable::getAttrCatEntry
            */
            // use the attribute offset to get the value of the attribute from current record
            // perform comparison using compare function and store the outcome of comparison in the variable flag

            // initialize cond = UNSET

            // Next task is to check whether this record satisfies the given condition.
            // It is determined based on the output of previous comparison and the op value received.
            // The following code sets the cond variable if the condition is satisfied.
            switch (op) {

                case NE:
                    // if op is "not equal to"
                    // if the record's attribute value is not equal to the given attrVal
                    if (flag != 0) {
                        // SET the cond variable (i.e. cond = SET)
                    }
                    break;

                case LT:
                    // if op is "less than"
                    // if the record's attribute value is less than the given attrVal
                    if (flag < 0) {
                        // SET the cond variable (i.e. cond = SET)
                    }
                    break;

                case LE:
                    // if op is "less than or equal to"
                    // if the record's attribute value is less than or equal to the given attrVal
                    if (flag <= 0) {
                        // SET the cond variable (i.e. cond = SET)
                    }
                    break;

                case EQ:
                    // op is "equal to"
                    // if the record's attribute value is equal to the given attrVal
                    if (flag == 0) {
                        // SET the cond variable (i.e. cond = SET)
                    }
                    break;

                case GT:
                    // if op is "greater than"
                    // if the record's attribute value is greater than the given attrVal
                    if (flag > 0) {
                        // SET the cond variable (i.e. cond = SET)
                    }
                    break;

                case GE:
                    // if op is "greater than or equal to"
                    // if the record's attribute value is greater than or equal to the given attrVal
                    if (flag >= 0) {
                        // SET the cond variable (i.e. cond = SET)
                    }
                    break;
            }
        }

        if (cond == SET || op == PRJCT) {
            /*
                set the search index in the relation cache as
                the record id of the record that satisfies the given condition
                (use RelCacheTable::setSearchIndex function)
            */

            return RecId{block, slot};
        }

    }

    // no record in the relation with Id relid satisfies the given condition
    return {-1, -1};
}

[SaintNerevar]

// If slot >= the number of slots per block(i.e. no more slots in this block) { // update block = right block of block // update slot = 0 }

@jessiyajoy Just add a continue inside this and remove RST from op description in Arguments section