Kezdőlap / Kidolgozott tételek / DEIK Mérnökinformatikus BSC 2017 / 13. tétel

13. Tétel — Modern processzor megoldások és relációs lekérdezések optimalizálása

Frissítve: 2026-09-09

Ez a tétel két nagyobb témakört fed le: a modern processzorok teljesítménynövelő megoldásait (futószalag, sorrenden kívüli és spekulatív végrehajtás, szuperskalár, VLIW és vektorprocesszorok), valamint a relációs lekérdezések optimalizálását és kiértékelését.

Témák

I. Témakör: Modern processzor megoldások

• Modern processzor megoldások (futószalag elv, hazard, sorrenden kívüli végrehajtás, spekulatív végrehajtás, szuperskalár processzorok, VLIW processzorok, vektor processzorok).

II. Témakör: Relációs lekérdezések optimalizálása és kiértékelése

• Relációs lekérdezések optimalizálása és kiértékelése.
• Relációalgebrai fa alapú optimalizálás.
• Költségalapú optimalizálás.

I. Témakör: Modern processzor megoldások

1. A futószalag elv (Pipelining)

A futószalagos feldolgozás alapjai

A végrehajtási folyamatot több, rövidebb, önálló, egymással párhuzamosítható fázisra bontjuk. Egy klasszikus, ötfázisú futószalag lépései a következők:

• Utasításlehívás (Instruction Fetch - IF): A processzor beolvassa a következő végrehajtandó utasítást a memóriából a programszámláló (Program Counter, PC) által mutatott címről.
• Utasításdekódolás és regiszterolvasás (Instruction Decode - ID): A lehívott utasítást a vezérlőegység dekódolja, meghatározza annak típusát és a szükséges operandusokat, amelyeket kiolvas a regisztertárból.
• Végrehajtás (Execute - EX): Az aritmetikai és logikai egység (ALU) elvégzi a dekódolt utasítás által előírt műveletet (pl. összeadás, logikai ÉS).
• Memóriaelérés (Memory Access - MEM): Amennyiben az utasítás memóriaírást (store) vagy -olvasást (load) igényel, ez a fázis felelős az adatmemória eléréséért.
• Visszaírás (Write-Back - WB): A végrehajtás vagy a memóriaolvasás eredménye visszaíródik a célregiszterbe.

A futószalag akadályai: Veszélyforrások (Hazards)

• Adatveszélyek (Data Hazards): Akkor lépnek fel, amikor egy utasítás eredményétől függ egy későbbi utasítás, de az eredmény még nem áll rendelkezésre. Három altípusa van:
  • RAW (Read After Write - True Dependency): A második utasítás olvasná egy olyan regiszter tartalmát, ahová az első még nem írt be.
  • WAR (Write After Read): A második utasítás írna egy regiszterbe, mielőtt az első kiolvasta volna azt.
  • WAW (Write After Write): Két utasítás ugyanabba a regiszterbe írna, és a sorrend felborulna.
• Vezérlési veszélyek (Control Hazards): Feltételes elágazások esetén fordulnak elő. Mivel a processzor futószalaga előre dolgozik, nem tudja előre, hogy melyik ág fog lefutni, így bizonytalanná válik a következő utasítás címe.
• Strukturális veszélyek (Structural Hazards): Akkor jönnek létre, amikor a hardver erőforrásai nem elegendőek ahhoz, hogy a futószalagban lévő különböző utasítások egyszerre, egyidejűleg igénybe vegyék ugyanazt az egységet.

2. Sorrenden kívüli (Out-of-Order, OoO) végrehajtás

A hagyományos futószalagok teljesítménybeli korlátainak túllépésére fejlesztették ki a szuperskalár processzorokat. Egy szuperskalár architektúra nemcsak átlapolja az utasításokat, hanem több párhuzamos futószalaggal is rendelkezik, így órajelciklusonként egynél több utasítást képes lehívni, dekódolni és kibocsátani.

A szuperskalár rendszerek hatékonyságának kulcsa a sorrenden kívüli végrehajtás. A merev, programozói sorrendet követő (In-Order) feldolgozás során, ha egy utasítás blokkolódik, a mögötte lévő összes utasítás megáll.

Az OoO motor ezzel szemben a következő mechanizmust használja:

• Az utasítások a program szerinti sorrendben érkeznek, de a dekódolás után egy utasítás-ablakba kerülnek.
• A processzor dinamikusan elemzi az utasítások közötti adatfüggőségeket. Ha egy utasítás adatai nem állnak rendelkezésre, de egy későbbi utasítás független és a végrehajtó egység szabad, a processzor előreveszi és végrehajtja a későbbi utasítást (sorrenden kívül).
• Visszarendezés (Retirement / Reorder Buffer – ROB): Annak érdekében, hogy a program helyes szemantikája sérülhetetlen maradjon, a sorrenden kívül végrehajtott utasítások eredményei egy visszarendezési pufferbe kerülnek, és szigorúan az eredeti programozási sorrendben íródnak vissza a regiszterekbe.

3. Szuperskalár processzorok

A szuperskalár processzor olyan mikroarchitektúra-kialakítás, amelyben a processzor képes egyetlen órajel alatt egynél több utasítást végrehajtani azáltal, hogy több párhuzamos végrehajtó egységet alkalmaz.

Azonban a szuperskalár végrehajtásnak is korlátot szabnak a már ismert hazardok, különösen az adatfüggőségek. Egy egyszerű, soron belüli (in-order) szuperskalár processzorban, ha az i. utasítás eredményére van szüksége az i+1. utasításnak, és az i. utasítás egy lassú művelet, akkor az i+1. utasításnak és az összes utána következőnek is várakoznia kell. A párhuzamos futószalagok kihasználatlanul állnak, hiába lennének a programban később olyan, teljesen független utasítások, amelyeket végre lehetne hajtani. Ezt a problémát oldja meg a soron kívüli végrehajtás (Out-of-Order Execution, OoO).

4. Spekulatív végrehajtás (Speculative Execution)

A szuperskalár és OoO processzorok teljesítményét nagymértékben növeli a spekulatív végrehajtás, amely közvetlenül a vezérlési veszélyek (elágazások) negatív hatásait küszöböli ki.

• Működése: Amikor a processzor egy feltételes elágazáshoz (if-else) ér, ahelyett, hogy megvárná a feltétel kiértékelődését és a memóriából/regiszterből érkező adatok megérkezését, egy elágazás-előrejelző (branch predictor) segítségével statisztikai és historikus minták alapján megjósolja az elágazás kimenetelét.
• A processzor a jósolt ágon lévő utasításokat spekulatívan, a háttérben végrehajtja, az eredményeket ideiglenes tárolókban tartva.
• Helyes jóslat esetén: Az eredmények érvényesülnek, így semmilyen órajelciklus nem veszendő kárba.
• Rossz jóslat esetén: A processzor érvényteleníti a spekulatívan végrehajtott utasítások eredményeit (visszaállítja a pipeline-t), és elkezdi a helyes ág feldolgozását. A modern processzorokban a jóslási pontosság gyakran 95-99% körüli, így a spekulatív végrehajtás óriási sebességnövekedést eredményez.

5. VLIW (Very Long Instruction Word) és Vektorprocesszorok

A VLIW architektúra alapgondolata, hogy a párhuzamosan végrehajtható utasítások felkutatásának és ütemezésének terhét vegyük le a processzor hardverének válláról, és adjuk át a fordítóprogramnak. A fordítóprogram, amely a teljes programkódot ismeri, statikusan, fordítási időben elemzi a függőségeket, és több, egymástól független, egyszerű műveletet egyetlen, nagyon hosszú utasításszóba csomagol.

• VLIW (Very Long Instruction Word) architektúrák: Míg a szuperskalár processzorok bonyolult, dinamikus (hardveres) logikával döntik el órajelciklusonként, hogy mely utasítások futtathatók párhuzamosan, addig a VLIW architektúrában ezt a terhet a fordítóprogram (compiler) veszi át. A fordító egyetlen hatalmas, több műveletet tartalmazó (hosszú) utasításszóba csomagolja a független műveleteket, amelyeket a hardver mindenféle extra ütemezési logika nélkül, közvetlenül a párhuzamos végrehajtó egységekre küld. Előnye a hardver egyszerűsége és alacsony energiaigénye, hátránya a merev kódkompatibilitás és a fordítóprogram komplexitása.
• Vektorprocesszorok (SIMD – Single Instruction, Multiple Data): Olyan speciális architektúrák, amelyek egyetlen utasítással képesek adatok egész tömbjein végrehajtani ugyanazt a műveletet. A processzor széles regiszterekkel és párhuzamos ALU-s sorokkal rendelkezik, ami drasztikusan csökkenti a ciklusok számát az adatintenzív feladatokban.

II. Témakör: Relációs lekérdezések optimalizálása és kiértékelése

1. Relációs lekérdezések optimalizálása és kiértékelése

A relációs adatbázis-kezelő rendszerekben a lekérdezések megfogalmazására szolgáló nyelvek (mint például az SQL) deklaratív jellegűek. Ez azt jelenti, hogy a felhasználó vagy a fejlesztő megmondja, hogy mit szeretne kapni az adatbázistól, de nem határozza meg, hogy hogyan, azaz milyen fizikai lépésekkel, milyen sorrendben és milyen algoritmusok alkalmazásával olvassa ki az adatokat a háttértárból a rendszer.

A lekérdezés-optimalizáló (query optimizer) az egyik legfontosabb és legösszetettebb komponense. Feladata, hogy az SQL-utasításból előállítson egy végrehajtási tervet (execution plan), amely minimálisra csökkenti az erőforrás-felhasználást (elsősorban a háttértárból történő lemezműveletek/I/O számát, valamint a CPU-időt).

A lekérdezés feldolgozásának fő fázisai a következők:

• Lexikális és szintaktikai elemzés (Parser): Ellenőrzi az SQL-szabályok helyességét, és szintaxisfát készít.
• Szemantikus elemzés és jogosultság-ellenőrzés: Ellenőrzi, hogy a táblák és oszlopok léteznek-e, és a felhasználónak van-e joga a lekérdezéshez.
• Logikai optimalizálás: A lekérdezést relációalgebrai kifejezéssé (fává) alakítja, és heurisztikus szabályok alapján átstrukturálja.
• Fizikai optimalizálás (Költségalapú): A logikai fához hozzárendeli a konkrétan megvalósító fizikai operátorokat, megbecsüli a költségeket a statisztikák alapján, és kiválasztja a legolcsóbb tervet.
• Kódgenerálás és Végrehajtás: A kiválasztott tervet futtatja a motor.

2. Relációalgebrai fa alapú (Logikai) optimalizálás

A relációalgebra alapjai

A relációalgebra olyan formális matematikai nyelv, amely relációkon végez műveleteket. A legfontosabb relációalgebrai operátorok:

• Szelekció: Sorok szűrése adott feltétel alapján.
• Projekció: Oszlopok kiválasztása.
• Descartes-szorzat: Két reláció kombinációja.
• Összekapcsolás: Feltételes összekapcsolás.
• Unió, Metszet, Különbség.

Heurisztikus átalakítási szabályok (Ekvivalencia-szabályok)

A logikai optimalizálás során a kiinduló relációalgebrai fát úgy alakítjuk át ekvivalens (pontosan ugyanazt az eredményt adó, de kedvezőbb szerkezetű) fává, hogy közben betartunk bizonyos heurisztikus szabályokat:

• Szelekciók feltolása a fában (Push-down selections): A szelekciókat a lehető legkorábban (a fa leveleihez, azaz az alaprelációkhoz legközelebb) kell végrehajtani. Ezzel drasztikusan lecsökkentjük a köztes eredmények, a relációk méretét, amelyeken a későbbi költséges összekapcsolásoknak kell futniuk.
• Szelekciók szétbontása: Ha a szelekció feltétele logikai ÉS kapcsolatból áll, azt különálló egymás alatti szelekciókra bonthatjuk, ami segít a feltolásban. (értsd: disztributivitás)
• Projekciók behúzása és feltolása: A felesleges oszlopokat a lehető leghamarabb el kell dobni, hogy csökkenjen a sorok bájtmérete a memóriában.
• Descartes-szorzatok átalakítása összekapcsolássá: A párosokat mindig át kell alakítani közvetlen összekapcsolási operátorokká, elkerülve a hatalmas méretű Descartes-szorzatok előállítását.
• Részfák átrendezése: Az összekapcsolások kommutativitásának és asszociativitásának kihasználásával a legkisebb méretű relációkat kapcsoljuk össze először.

3. Költségalapú (Fizikai) optimalizálás

Fizikai operátorok és algoritmusok

• Szelekció megvalósításai:
  • Sequential Scan (Táblakeresés): Az egész tábla beolvasása blokkonként.
  • Index Scan (Indexelt keresés): B-fa index használata, ha van megfelelő index a feltételben szereplő oszlopon.
• Összekapcsolások (Joins) algoritmusai:
  • Nested Loop Join (Beágyazott ciklusos összekapcsolás): Külső és belső ciklus.
  • Sort-Merge Join (Rendezve összefésülő): Először rendezi mindkét táblát a join kulcs szerint, majd egy menetben összefésüli őket.
  • Hash Join (Hash-alapú összekapcsolás): A kisebbik relációból hash-táblát épít a memóriában, majd a nagyobbik reláció elemeit átvizsgálva hash-függvénnyel keres egyezést.

A költségmodell elemei és a statisztika

Az optimalizáló matematikai költségfüggvényt használ az alternatív tervek összehasonlítására. A költséget leggyakrabban az alábbi tényezők határozzák meg:

• I/O költség: A háttértárról beolvasott és kiírt adatlapok száma. Ez a domináns tényező, mivel a lemezműveletek nagyságrenddel lassabbak, mint a CPU műveletek.
• CPU költség: A rekordok összehasonlításához, sorba rendezéséhez és hash-eléréséhez szükséges CPU-ciklusok száma.
• Memóriaköltség: A rendelkezésre álló pufferterület mérete.

A költségbecsléshez az RDBMS a katalógusban (System Catalog) tárolt statisztikákat használja:

• Táblák sorszáma.
• Az egyes oszlopok egyedi értékeinek száma.
• Oszlopértékek eloszlási hisztogramjai (amelyek megmutatják, hogy az értékek hogyan oszlanak meg a tartományban).
• Az adatok fizikai elhelyezkedése.