利用C++實(shí)現(xiàn)?然連接操作算法

更新時(shí)間：2022年08月01日 15:46:49 作者：biyezuopinvip

這篇文章主要介紹了利用C++實(shí)現(xiàn)?然連接操作算法，文章圍繞主題展開詳細(xì)的內(nèi)容介紹，具有一定參考價(jià)值，需要的小伙伴可以參考一下

2. 實(shí)驗(yàn)內(nèi)容

首先，我們讀取兩個(gè)表頭的信息

TableId leftTableId = catalog->getTableId("r");
TableId rightTableId = catalog->getTableId("s");
badgerdb::File left = File::open(catalog->getTableFilename(leftTableId));
badgerdb::File right = File::open(catalog->getTableFilename(rightTableId));

運(yùn)用兩層循環(huán)尋找兩個(gè)表中名稱與類型完全相同的屬性，將他們?nèi)繕?biāo)記出來，用于之后的自然連接操作。

vector<int> leftForeignKeyId;
vector<int> rightForeignKeyId;
for (int i = 0; i < leftTableSchema.getAttrCount(); i++)
{
    for (int j = 0; j < rightTableSchema.getAttrCount(); j++)
    {
        if ((leftTableSchema.getAttrName(i) == rightTableSchema.getAttrName(j)) && (leftTableSchema.getAttrType(i) == rightTableSchema.getAttrType(j)))
        {
            leftForeignKeyId.push_back(i);
            rightForeignKeyId.push_back(j);
            break;
        }
    }
}

準(zhǔn)備操作做完后，開始進(jìn)行自然連接操作。

用循環(huán)從磁盤中讀取兩個(gè)頁(yè)面的信息，記錄 io 操作次數(shù)

for (badgerdb::FileIterator leftPage = left.begin(); leftPage != left.end(); leftPage++)
{
    badgerdb::Page *bufferedLeftPage;
    bufMgr->readPage(&left, (*leftPage).page_number(), bufferedLeftPage);
    numIOs += 1;

    for (badgerdb::FileIterator rightPage = right.begin(); rightPage != right.end(); rightPage++)
    {
        badgerdb::Page *bufferedRightPage;
        bufMgr->readPage(&right, (*rightPage).page_number(), bufferedRightPage);
        numIOs += 1;

之后，從表中讀取全部的元組的信息，進(jìn)行對(duì)比。

讀取的元組信息有特殊的格式，并不能直接利用，所以需要先了解元組在表中儲(chǔ)存的格式，然后進(jìn)行解讀。元組的存儲(chǔ)方式可以從 storage.cpp 中的 createTupleFromSQLStatement 函數(shù)中得知。

switch (dataType) {  // (int) 56 (0011 1000) -> (char) '\0''\0''\0''8'
case INT: {        // convert int value into 4 byte representation
    case CHAR: {  // (char(5) ) 'abc' -> 'abc00'
        case VARCHAR: {  // (varchar(8) ) 'abc' -> '3''abc'  (3 refer to the ascii
            // code number correspond alpha)

于是，我們根據(jù)注釋的存儲(chǔ)方式編寫解析函數(shù)，該函數(shù)輸入為文件中存儲(chǔ)的元組，輸出為數(shù)組表示的直觀的元組內(nèi)容。

vector<string> analyze(string record, badgerdb::TableSchema schema)

先讀取其中一個(gè)表的元組，用塊來存儲(chǔ)。

for (badgerdb::PageIterator leftRecord = bufferedLeftPage->begin(); leftRecord != bufferedLeftPage->end(); leftRecord++)
{
    vector<string> leftInfo = analyze(*leftRecord, leftTableSchema);
    numUsedBufPages += 1;
    block.push_back(leftInfo);
    if (block.size() < BLOCK_SIZE)
    {
        continue;
    }

然后讀取另一個(gè)表的元組信息，

for (badgerdb::PageIterator rightRecord = bufferedRightPage->begin(); rightRecord != bufferedRightPage->end(); rightRecord++)
{
    numUsedBufPages += 1;

將兩個(gè)元組當(dāng)中的屬性名相同的屬性列信息進(jìn)行對(duì)比，

bool f = true;
for(int i = 0; i < leftForeignKeyId.size(); i++)
{
    if(leftInfo[leftForeignKeyId[i]] != rightInfo[rightForeignKeyId[i]])
    {
        f = false;
        break;
    }
}

如果全部相同，則代表需要進(jìn)行自然連接操作。

if(f)
{
    string current_line = "INSERT INTO TEMP_TABLE VALUES (" + leftInfo[0];
    for (int i = 1; i < leftTableSchema.getAttrCount(); i++)
    {
        current_line = current_line + ", " + leftInfo[i];
    }
    for (int i = 0; i < rightTableSchema.getAttrCount(); i++)
    {
        current_line = current_line + ", " + rightInfo[i];
    }
    current_line = current_line + ");";

    string tuple = HeapFileManager::createTupleFromSQLStatement(current_line, catalog);
    numResultTuples += 1;
    HeapFileManager::insertTuple(tuple, resultFile, bufMgr);
}

否則不進(jìn)行任何操作。

在全部循環(huán)都結(jié)束之后，塊中可能還會(huì)有剩余的信息沒有進(jìn)行處理，此時(shí)再單獨(dú)對(duì)剩余信息進(jìn)行處理，代碼基本相同。