Rendezés

• Sok művelet hatékony kiértékelése
• Explicit kéni is lehet
  • ORDER BY

Két fő megvalósítás létezik

Belső rendeés

• Ha a rekordok elférnek a memóriába
• Betöltés: \(B_R\) művelet
• Memóriába rendezés: 0 művelet
• Kiírás: \(B_R\) művelet
• Összköltség: \(2 B_R\)

Külső rendezés

• Ha nem fér be az egész a memóriába
• SORT-MERGE

Rendező lépések

Rendezett futamok létrehozása

• M - memória mérete blokkokban
• N - futamok száma

Algo

~fun doFutam(M: Int, R: Relation, K: List<File>) : Int{
    var i = 0;
    do{
        val memory: List<Record>= R.in.read(pageCount= M)
        memory.sort()
        K[i].write(memory)
        i+=1
    } while(R.in.isEmpty())
    return i;
~}

??? title="Don't like kotlin?" fine, that's what ea gave us:

```dbea
M // a memória mérete blokkokban

i=0;
ismétlés
    M lap beolvasása az R relációból a memóriába
    az M lap rendezése
    kiírás az R_i fájlba (futamba)
    i növelése
amíg el nem fogynak a lapok
N = i       // futamok száma
```

Összevonási lépés

• Rendezett futamok összefésülése

~ fun merge(M: Int, N: Int, K: List<File>, Out:File){
    assert(N<M)
    for (file in K){
        file.lockPage()
    }
    var Pages: List<Page> = K.map{ it.lockedPage.sorted() }
    while(!Pages.isEmpty()){
        val firstRecords: List<Record> = Pages.map(::first)
        Out.writeAll(firstRecords)
        Pages.map(::pop)
        Pages = Pages.filter(::isEmpty)
    }
~ }

??? title="Don't like kotlin??!" You are bein' rude, you know that....

```dbea
// feltéve, hogy N < M
minden R_i fájlhoz egy lap lefoglalása // N lap lefoglalása
minden R_i-ből egy-egy P_i lap beolvasása
ismétlés
    az N lap közül (a rendezés szerint) első rekord kiválasztása, legyen ez a P_j lapon
    a rekord kiírása a kimenetre és törlése a P_j lapról
    ha üres a lap, a következő P_j' beolvasása R_J-ből
amíg minden lap ki nem ürül
```

Összefésüléses rendezés költsége

• \(B_R\)
• Rendezési lépés
  • Reláció írása, olvasása: \(2*B_R\)
• Összevonási lépés
  • Rendezett futamból M-1 összefésülése
  • Kezdetben \(\dfrac{\href{./05_1_CostMath.md#br}{B_R}}{M}\) összevonandó futam
  • Metenetnként \(M-1\) futamot rentez, tehát annyival osztjuk
  • Összesem \(\left|\log_{M-1}\left(\dfrac{\href{./05_1_CostMath.md#br}{B_R}}{M}\right)\right|\)
  • Minden esetben \(2*B_R\) lapot olvasunk
    • reláció I/O, kivéve az utolsó kiírást

Teljes-teljes számolási költség: