DBMS-ə qoşulur

Sistem dizaynı ilə bağlı müsahibə sualları o qədər açıq ola bilər ki, düzgün hazırlaşmağı bilmək çox çətindir. İndi satın aldıqdan sonra Amazon, Microsoft və Adobe-nin dizayn dövrlərini sındıra bilirəm Bu kitabı. Gündəlik bir yenidən nəzərdən keçirin dizayn sualı və söz verirəm ki, dizayn dövrünü sındıra bilərsiniz.

Müxtəlif növ birləşmə metodlarımız var. Sorğulardakı birləşmələrdən istifadə etdiyimiz zaman sorğu optimizatoru hansı birləşmələrin istifadə olunacağına qərar verir. Sorğunun daha yaxşı qiymətinə əsasən, sorğu optimallaşdırıcısı tərəfindən aşağıdakı birləşmə metodlarından hər hansı biri istifadə ediləcəkdir.

Tutaq ki, ikisinə qoşulaq masaları T və S qoşulma şərti ilə θ. T və s sırasıyla T və S dəki qeydlər olsun. Tutaq ki, T cədvəlində hər blokda BT qeydləri və ümumi NT qeydləri var. Eynilə S cədvəlində hər blokda BS qeydləri və ümumi NS qeydləri var. Məqalənin qalan hissələrində istifadə olunan fərqli işarələr arasındakı fərqi başa düşmək üçün aşağıdakı diaqrama ətraflı baxın. Zəhmət olmasa mövzulara yalnız fərqlər çox aydın olduqda davam edin.

İç-içə Döngə Qoşulması (NLJ)

Bu metodla masaları birləşdirdiyimiz zaman masa qeydlərinə əsaslanan daxili və xarici döngələr yaradılır. Vəziyyət ən daxili dövrədə yoxlanılır və təmin edərsə, nəticə dəstində saxlanacaq, əks halda növbəti qeyd təsdiqlənəcəkdir. Bu metod üçün alqoritm aşağıdakı kimi yazıla bilər

For each record t in T 
Loop
	For each record s in S
	Loop
		Check θ on (t, s)
		If matches then copy to result set
		Else move to next record
		End If
	End Loop
End Loop

Yuxarıda göstərilən alqoritmdə, xarici cədvəlin hər bir qeydinin daxili cədvəlin hər s ilə qeyd olunduğunu görə bilərik, buna görə çox bahalı birləşmə növüdür.
Ən pis halda bunu tələb edir NT + BT axtarır və (NT * BS) + BT Transferləri bloklayın. Yaddaşına yerləşdirilibsə, daxili dövrəyə daha kiçik cədvəllər qoymaq həmişə yaxşıdır. O zaman maliyyət 2 axtarışa qədər azalacaq və BT + BS Transferləri bloklayın.

Tutaq ki, aşağıdakı sayda qeydlər və bloklarla ƏMƏKDAŞ və DEPT masalarımız var. Bu rəqəmlərə və daha böyük və kiçik cədvəllərin mövqeyinə əsasən xərclərini görək. Kiçik cədvəl DEPT xarici cədvəl olaraq təyin olunduqda, blok köçürmə sayı, axtarış sayının azaldığı yerdə iki dəfə artdığı 1 və 2-ci vəziyyətə baxın. Hər iki cədvəlin yaddaş blokuna yerləşdiyi 3 halda, axtarış sayı 2-yə endirilir və blok ötürülməsi də xeyli azalır. Ancaq həqiqi fərqi yalnız kiçik DEPT cədvəlinin yaddaşa sığması və 4-cü vəziyyətdə daxili cədvəl kimi qəbul edildiyi zaman müşahidə edə bilərik. Xarici döngədə cədvəllərdən istifadə etmək üçün baş barmaq qaydası həmişə kiçik cədvəldir. Kiçik cədvəl yaddaşa sığdıqda, daxili dövrədə istifadə edin.

 

ssYuxarıdakı nümunələrdən başa düşə bilərik ki, iç içə döngə birləşməsinin qiyməti qeydlərin sayı, bloklar və cədvəllərin yerləşdirilməsi oyunudur. Bununla birlikdə, aşağıda göstərilən digər birləşmələrə nisbətən iç içə döngə birləşməsinin dəyəri çox bahadır.

Blok Nested Loop Join (BNLJ)

Bu metodda, hər bir qeydin xarici və daxili cədvəllərdə halqalanması ilə yanaşı, loopları da blokları əlavə edilir. Beləliklə, bu metod həm cədvəllərdən qeydlər blokunu seçir və içindəki qeydləri müqayisə edir. Beləliklə, emal blok müdrik şəkildə aparılır.

For each Block BT in T 
Loop
	For each Block BS in S
	Loop
For each record t in BT
Loop
	For each record s in BS
	Loop
		Check θ on (t, s)
		If matches then copy to result set
		Else move to next record
		End If
	End Loop
End Loop
End Loop
End Loop

Burada, hər bir qeyd blokunu bir döngədə keçir. Xarici blokların hər birinin daxili cədvəl qeydlərini yalnız bir dəfə oxuduğunu müşahidə edə bilərik. İçəridəki döngədə olduğu kimi, daxili cədvəl qeydlərini oxumaq üçün istifadə olunan hər cədvəli xarici cədvəldə birləşdirin. Beləliklə, bu metodun dəyəri, iç içə döngə metoduna nisbətən ən pis vəziyyət maliyyətinə malikdir. Tələb olunan axtarış sayı 2 BT və blok köçürmə sayı kimi verilir (BT * BS) + BT. Hər iki cədvəlin qeydlərinin yaddaş blokuna uyğun gəldiyi ən yaxşı halda, xərc 2 axtarış və olaraq verilir BS + BT blok köçürmələri

Yaddaş bloklarını daxili və xarici cədvəllərə ayırarkən yuxarıdakı metodda cüzi dəyişiklik edə bilərik. Tutaq ki, M yaddaşdakı mövcud olan ümumi blokdur, BTBS müvafiq cədvəllərdəki hər blokdakı qeydlərin sayı. Sonra xarici əlaqələr üçün M-2 blokları ayırın və daxili və xarici xəritələr üçün 2 blok ayırın. Sonra maliyyət dəyişəcək 2 (BT / (M-2)) və blok köçürmə sayı kimi verilir ((BT / (M-2)) * BS + BT). Qarışıq olduqda yuxarıdakı diaqrama baxın.

Tutaq ki, qoşulma şərti cədvəllərin namizəd açarındadır, o zaman bütün cədvəl və ya daxili cədvəl bloklarından keçməməlidir. Bir nöqtədə özünü axtarın, qeydləri alacaqsınız.

İndeksli iç içə döngə birləşməsi (INLJ)

Yuxarıdakı BNLJ-nin son cümləsi, qoşulma şərtində istifadə olunan sütunlarda indeks varsa nə olacağını düşünməyə vadar edir. İndekslərdən istifadə edildikdə, qeydlərin ardıcıl taranması olmur. Bu da burada tətbiq olunur. Birləşdirmə şəraitində istifadə olunan sütunlarda indekslər istifadə edildikdə, daxili cədvəlin hər qeydini taramayacaq. Bu birbaşa uyğun rekord gətirəcəkdir. Ancaq indeks cədvəlindəki indeksin alınması üçün xərclərimiz olacaq. İndekslər təbii birləşmələrin birləşdirildiyi və ya bərabərliklərin istifadə edildiyi zaman faydalıdır. Beləliklə, sütunlarda indekslər müəyyənləşdirilməyibsə, sorğunu aparmaq üçün müvəqqəti indekslər yarada bilərik.

Ən pis halda, INLJ-nin dəyəri belə hesablanır BT * (RT + RS) + NT * C, burada RT və RS sırasıyla T və S cədvəllərinin hər bir qeydidir və C indeks cədvəlində tək bir qeydin alınma xərcidir.

Tutaq ki, bizdə EMP və DEPT cədvəlləri var və indeks yaradılıb EMP-dən DEPT_ID. Tutaq ki, DEPT xarici cədvəl, EMP isə daxili cədvəldir. yəni; DEPT∞DEPT_ID EMP. Fərz edək ki, EMP cədvəlində B + 4 ağac indeksindən istifadə olunur və hər bir uşaq qovşağında 20 indeks sahəsi olacaqdır.

Aşağıdakı kimi digər dəyişənlər üçün dəyəri götürək:

  • DEPT (NT) içindəki qeydlərin sayı: 5000
  • ƏMİP-dəki qeydlərin sayı: 10000
  • T (BT) blok başına qeydlərin sayı: 100
  • S (BS) blok başına qeydlərin sayı: 400

İndi indeks cədvəlindən istifadə edərək bir qeyd almağın qiyməti, C = İndeksi almaq üçün B + ağacının hündürlüyü + Biri həqiqi qeydləri yaddaşdan götürməyə çalışır = 4 +1 = 5
RT + RS yalnız bir qeyd götürdüyümüz üçün burada göz ardı edilə bilər.

Aşağıdakı hər birləşdirmə növünün ümumi qiymətinə baxaq (blok köçürmələri və axtarışları):
Xərcləri NLJP = (NT + BT) + (NT * BS) + BT = (5000 + 100) + (5000 * 400) +100 = 20, 05,200
Xərcləri BNLJ = 2 BT + (BT * BS) + BT = 2 * 100 + (100 * 400) + 100 = 40,300
Ümumi dəyəri INLJ = BT * (RT + RS) + NT * C = 100 + (5000 * 5) = 25,100

Yuxarıdakı nümunədən birləşdirmənin bütün üç növü arasındakı fərqi aydın şəkildə müəyyən edə bilərik. INLJ hamısı arasında ən səmərəlidir.

Birləşdirin

Qoşulma sorğusunda istifadə olunan masalar sıralana bilər və ya sıralanmır. Sıralanan masalar qatılarkən səmərəli xərclər verir. Bu metodda, hər iki cədvəli birləşdirmək üçün istifadə olunan sütun, iki cədvəli sıralamaq üçün istifadə olunur. Qeydləri iki cədvəldə sıralamaq üçün birləşmə-sort texnikasından istifadə olunur. Sıralama tamamlandıqdan sonra nəticə əldə etmək üçün qoşulma şərti tətbiq olunur. Qoşulma digər birləşmələrə də bənzəyir, lakin iki qeyd eyni sütun dəyərinə malikdirsə, qeydlərin bütün sütunlarına əsasən qeydləri sıralamağa diqqət yetirilməlidir. Bu metod ümumiyyətlə təbii birləşmələrdə və ya bərabər yerlərdə istifadə olunur. Bütün qeydlərin yaddaş blokuna yerləşdirilə biləcəyini düşünək. Hər bir qeyd bloku qoşulmaq üçün yalnız bir dəfə oxunur. O zaman bu qoşulmanın dəyəri olacaqdır

Axtarışın qiyməti: BT / M + BS / M
Blok köçürməsinin dəyəri: BT + BS
Cədvəllər çeşidlənməyibsə, birləşmə çeşidlənməsi üçün xərclər də yuxarıdakı qiymətə daxil edilir.

Hash buyurun

Bu metod təbii və bərabərlik vəziyyətində də faydalıdır. Hər cədvəlin qeydlərini fərqli bloklara bölmək üçün birləşmə sütununda h funksiyasından istifadə edirik. Bu hash bölünmüş qeyd bloklarının hər birinin yaddaş blokuna uyğun olduğunu və NH sayda bölünmüş blokların olduğunu düşünək.

DT0, DT1, DT2, DTN : DTi = h (RT (joinCol)) və RT-nin T cədvəlindəki hər hansı birində olduğu və DTi bölməsində olduğu T cədvəlinin qarışıq bölünmüş bloklarıdır.
DS0, DS1, DS2, DSN : DSi = h (RS (joinCol)) və RT-nin S cədvəlindəki hər hansı birində olduğu və DSi bölməsində olduğu S cədvəlinin bölünmüş bloklarıdır.

Cədvəllər bölündükdə giriş üçün bir yaddaş bloku, hər bölmənin çıxış buferi üçün bir yaddaş bloku qorunur. Yaddaş bloklarının qalan hissəsi giriş tamponları və çıxışları üçün bərabər şəkildə bölünür. Sonra hash alqoritmi aşağıdakı kimi yazıla bilər

For each partition i Loop
 	Load DSi into memory and build a hash index on the joining column
	Retrieve each record DTi from memory, for each record in DSi build a hash index on joining column and find the matching record in DSi
		If matching records are found, then join the records RT and RS into output
	End loop
End Loop

Məsələn, sütunu DEPT_ID olaraq qoşaraq EMP və DEPT masalarını götürün. DEPT_ID-də bir hash funksiyası masanın hər biri üçün bölünmüş blok (hash bölməsi) yaratmaq üçün istifadə olunur. Hər masa üçün 5 bölmə yaratdığını düşünək. Alqoritmə görə

Yaddaş blokunun ümumi sayı M, hash bölməsinin sayı isə i olarsa

  • mən
  • i> = M: Cədvəllərə qoşulmaq üçün rekursiv bölmə metodu istifadə olunur. Yəni hər iki cədvəl M-1 bloklarına bölünür və birləşdirməyə davam edin və bölmənin qalan hissəsi üçün bölməni yenidən təkrarlayın.

Bəzi pis bir hash funksiyası və ya qoşulma şərtinə görə bir neçə eyni qeyd alacağımız bəzi hallar var. Bu vəziyyətdə, bütün qeydləri bir bölmə blokuna yerləşdirmək çətindir. Buna hah masasının daşması deyilir. Cədvəlləri diqqətlə bölməklə bunun qarşısını almaq olar. Bu, başqa bir hash funksiyasından istifadə edərək alt bölmələr yaratmaqla bölmənin özü yaradılarkən həll edilə bilər. Ancaq hər iki cədvəl eyni şəkildə bölünməlidir. Ancaq cədvəllərdə çox sayda təkrarlanan dəyər varsa və yenə də BNLJ metodundan istifadə etməli olsaq yenə də daşqın yaşayacağıq.

Bəzi bölümlərin digər bölmələrə nisbətən çox sayda qeydlərə sahib olacağı əyri bölmə adlı başqa bir məsələ var. Bu da masalara qoşulmaq üçün yaxşı deyil.

Haş qoşulmaların qiymətini görək.

Bir nümunəni nəzərdən keçirək. Tutaq
Yaddaşdakı ümumi blok sayı, M = 20
EMP-də blok sayı, BT = 100
DEPT-də blok sayı, BS = 400
Bölmənin ümumi sayı, I = 5

Sonra, EMP-nin hər bölməsində hər biri 20 blok, DEPT-də isə hər biri 80 blok olacaqdır. Bu, EMP mənasında i = M deməkdir.

Beləliklə, ümumi axtarır = 2 ((BT / B) + (BS / B) = 2 ((100/3) + (400/3)) = 336
Ümumi blok köçürmə = 3 (BT + BS) + 4 * Ni = 3 (100 + 400) = 1500, burada qismən doldurulmuş arakəsmələri nəzərə almadığımız üçün 4Ni nəzərə alınmır.

Crack Sistemi Dizayn Müsahibələri
Translate »