嵌入式數(shù)據(jù)庫查詢(數(shù)據(jù)庫)

時(shí)間：2022-11-06 10:30:01 | 來源：信息時(shí)代

時(shí)間：2022-11-06 10:30:01 來源：信息時(shí)代

    嵌入式數(shù)據(jù)庫查詢 : 采用自適應(yīng)的查詢處理技術(shù)對(duì)內(nèi)存數(shù)據(jù)的查詢處理。傳統(tǒng)的查詢處理技術(shù)充分地利用大量的主存來存儲(chǔ)一些臨時(shí)數(shù)據(jù)結(jié)構(gòu)(如哈希表)和中間結(jié)果。當(dāng)主存不能滿足數(shù)據(jù)存儲(chǔ)需求時(shí),可采用一些復(fù)雜的算法利用磁盤上的空間來避免內(nèi)存溢出。在嵌入式數(shù)據(jù)庫環(huán)境中,內(nèi)存非常有限,向穩(wěn)定內(nèi)存寫操作很慢,而臨時(shí)的實(shí)體化也不允許。通常也很難提前估計(jì)出內(nèi)存需求,選擇小了將導(dǎo)致內(nèi)存溢出,選擇大了又會(huì)減少有限的內(nèi)存空間; 其次,一些復(fù)雜的算法違背了代碼精簡和壓縮的原則,對(duì)于嵌入式數(shù)據(jù)庫不再適用。
考慮到以上原因,嵌入式數(shù)據(jù)庫系統(tǒng)通常采用自適應(yīng)的查詢處理技術(shù)。整個(gè)數(shù)據(jù)都存儲(chǔ)在內(nèi)存中,查詢處理優(yōu)化的主要目的是減少從內(nèi)存中讀數(shù)據(jù)的次數(shù)。
一個(gè)基本的查詢執(zhí)行通常分為兩個(gè)步驟: 查詢優(yōu)化器首先產(chǎn)生可選的查詢執(zhí)行計(jì)劃(QEP),然后查詢引擎通過一種執(zhí)行模型,利用關(guān)系操作符庫來執(zhí)行QEP。對(duì)于不同的查詢執(zhí)行計(jì)劃有不同的查詢樹形式。在左深樹(left-deep trees)中,操作符順序執(zhí)行,每個(gè)中間結(jié)果都要進(jìn)行實(shí)體化。而右深樹(right-deep trees)是在流水線中執(zhí)行操作符,避免了實(shí)體化中間結(jié)果,但仍需要在內(nèi)存中實(shí)體化所有的左關(guān)系。Bushy樹可以減少處理中間結(jié)果大小和內(nèi)存消耗。
查詢處理需要一個(gè)最優(yōu)的查詢執(zhí)行計(jì)劃,為了減少實(shí)體化操作,左深樹和Bushy樹被排除,而選擇右深樹和極右深樹來表示查詢,具體采用哪個(gè)依賴于存儲(chǔ)中間結(jié)果而能使用的內(nèi)存。查詢優(yōu)化器通常是內(nèi)存標(biāo)識(shí)的。
由于不能保證每個(gè)操作符都能得到整個(gè)內(nèi)存,內(nèi)存必須在全部操作符之間選擇分配。Arvind等人提出一種基于代價(jià)函數(shù)來給操作符分配內(nèi)存的方法。
對(duì)于沒有索引的連接操作,可以使用三種連接方法:
(1)嵌套循環(huán)連接:當(dāng)內(nèi)存較少時(shí),這是一個(gè)理想的選擇,它的優(yōu)點(diǎn)是不需要額外的數(shù)據(jù)結(jié)構(gòu)。
(2)排序合并連接:排序操作需要占用一定的內(nèi)存空間。這種方法在最壞的情況下執(zhí)行得較好。
(3)哈希連接:需要在主存中創(chuàng)建哈希表,在內(nèi)存不限制的情況下,哈希連接的速度是最快的,但選擇一個(gè)好的哈希函數(shù)是關(guān)鍵。
對(duì)于有索引的連接操作,可是采用以下連接操作:
(1)索引嵌套循環(huán)連接:帶索引的那個(gè)關(guān)系作為循環(huán)連接的內(nèi)關(guān)系。
(2)排序合并連接:如果索引在連接屬性上,那么不需要進(jìn)行排序操作。
對(duì)于連接索引,遍歷索引和相關(guān)的指針將產(chǎn)生用于連接的候選元組。
選擇、投影和排序可以直接進(jìn)行,而去重、聚集、集合取合、取差操作能夠通過在關(guān)系上進(jìn)行排序和構(gòu)建哈希索引來計(jì)算得到。聚集、排序和去重操作一般是在物化結(jié)果的基礎(chǔ)上執(zhí)行,然而可以通過在查詢計(jì)劃樹的葉結(jié)點(diǎn)上指定元組到達(dá)順序,來對(duì)這些聚集操作使用流水線操作。