Tema 8 Flashcards
(8 cards)
Explicació Processament de consultes
- Analitzador lèxic. Identifica els elements del llenguatge (paraules reservades SQL), nom de camps i de taules,…
- Analitzador sintàctic. Comprova la sintaxi de la consulta per veure que estigui d’acord amb SQL.
- Validació. Comprova que tots els noms de camps i taules existeixen i que tinguin un significat semàntic correcte dins la consulta.
- A continuació es crea una representació interna de la consulta, normalment amb una estructura en forma d’arbre anomenada “arbre de consultes”.
- El SGBD ha de desenvolupar una estratègia d’execució per obtenir el resultat final. El més habitual és que hi hagi moltes maneres de resoldre-la.
- El procés d’elecció de l’estratègia més adequada es coneix com a “optimització de consultes”.
- L’optimitzador de consultes s’encarrega de generar un pla d’execució optimitzat.
- El generador de codi s’encarrega de generar el codi per executar la consulta segon el pla d’execució que ha generat l’optimitzador.
- El processador de base de dades en temps d’execució té la funció d’executar el codi ja sigui en modus compilat o interpretat.
- Al final de tot el procés obtenim el resultat de la consulta.
Com es construeix un arbre inicial consulta?
- Suposem que la consulta ja ha estat validada.
- A continuació anem a veure com es crea l’arbre de consulta inicial.
2.1 Traducció de les consultes SQL a àlgebra relacional
- Una vegada validada la consulta es crea una estructura en forma d’arbre anomenada “arbre de consultes”.
- Com ja hem vist una mateixa consulta es pot plantejar de dues maneres, amb àlgebra relacional i amb SQL.
- Un arbre de consultes és una estructura de dades que equival a una expressió de l’àlgebra relacional.
- El SQL és declaratiu, diguem el que volem obtenir però no com fer-ho.
- Amb l’àlgebra relacional sí que especifiquem l’ordre en que s’han d’executar les operacions fins arribar al resultat final.
- La idea és convertir una sentencia SELECT en una expressió de l’àlgebra relacional.
- El motiu és que amb una expressió de l’àlgebra relacional sabem quines operacions cal fer i amb quin ordre.
Construcció d’un arbre de consulta a partir d’un SELECT
- L’analitzador no sap resoldre una sentència SELECT en forma d’àlgebra relacional, però sap construir un arbre de consulta inicial (no optimitzat). Per això:
● Primer colloca totes les taules (figuren després del FROM) en els nodes fulla i les reuneix totes amb una operació “producte cartesià” o bé una operació de reunió si utilitzem JOIN’s.
● A continuació realitza una operació de seleccionar amb tot el que ve a continuació del WHERE.
● Finalment realitza una projecció de tot el que hi ha després del SELECT (i abans del FROM).
Què fa un optimitzador de consultes?
- El SGBD ha de desenvolupar una estratègia d’execució per obtenir el resultat final. El més habitual és que hi hagi moltes maneres de resoldre-la.
- El procés de elecció de l’estratègia més adequada es coneix com la “optimització de consultes”.
- El optimitzador de consultes s’encarrega de generar un pla d’execució optimitzat.
- L’optimització consta de dos passos:
● Optimitzador heurístic que transformi l’arbre de consulta inicial en un de més optimitzat. L’objectiu és reordenar les operacions de l’arbre per tal d’optimitzar el temps de resposta.
● Estimació de cost de les diferents estratègies d’execució i escollir el pla d’execució amb el cost més baix (més ràpida).
Com es fa l’optimització heurística de l’arbre de consulta inicial?
- A partir de l’arbre de consulta inicial s’apliquen un conjunt de regles heurístiques que de manera informal podem expressar com:
● Pas 1. Descomposar l’operació de seleccionar conjuntiva (σc1 and σc2 and …) per (σc1 (σc2 …) amb la finalitat de fer les operacions de selecció tan aviat com sigui possible amb l’objectiu de reduir les tuples del resultat obtingut. En etapes posteriors es treballarà amb moltes menys tuples.
● Pas 2. Aplicar les operacions seleccionar més restrictives quan abans millor. Per exemple fer abans les operacions seleccionar amb una condició d’igualtat sobre un camp clau.
● Pas 3. Substitució del productes cartesians seguits de seleccions per operacions de reunió ja que el producte cartesià és una operació molt ineficient. Si ja tenim operacions de reunió les deixem estar igual.
● Pas 4. Realitzar les operacions projectar quan abans millor amb la finalitat de treballar amb tuples més reduïdes. A més si sobre una taula cal aplicar un seleccionar i un projectar ja ho farà de cop.
Explicació estimació de cost
- L’optimitzador de consultes calcula i compara el cost d’execució de les diferents estratègies d’execució i escull la de menor cost, o sigui escolleix aquells algorismes que ens retornaran el resultat més ràpidament (menor temps d’execució).
- Utilitza tècniques d’optimització que busquen entre les possibles solucions la que minimitza la funció de cost. En aquesta funció de cost intervenen molts de paràmetres.
- Components de cost d’una execució:
● Cost d’accés a disc. Cost de les cerques, lectures i escriptures a disc de les pàgines a ser tractades. Depèn molt de les estructures d’accés de què disposem.
● Cost computacional. Cost d’execució de les operacions en memòria (cerca i ordenació a la memòria, càlculs sobre valors dels camps, etc.) .
● Cost d’ús de la memòria. Buffers que es necessiten durant l’execució.
● Mida de cada fitxer: número de registres, mida mitjana de registre, número de pàgines, …
● Mètodes d’accés de cada fitxer: si tenen índex, de quin tipus (B+, dispersió),…
● Número de valors diferents de cada camp.
● Estadístiques de cost.
Què fa l’optimitzador de consultes?
- Al final l’optimitzador de consultes selecciona la estratègia d’execució de menor cost (temps d’execució més ràpid).
- Per això ha seleccionat els algoritmes més idonis per executar cada una de les operacions de l’arbre de consulta optimitzat.
- A partir dels algoritmes seleccionats i seguint l’ordre marcat per l’arbre de consulta optimitzat (de baix cap a dalt) es generarà i executarà el codi per la resolució de la consulta.
Quins algorismes es poden utilitzar per executar les diferents operacions de l’àlgebra relacional?
- Operació selecció. Hi ha moltes maneres d’executar una operació de selecció (Algunes depenen de les estructures d’accés (índexs).
- Exemples d’operacions de selecció
● σ dni=40512548 (EMPLEAT). Igualtat per camp clau. (Accés directe per valor)
● σ numdep>5 (DEPARTAMENT). Més grans que un valor del camp clau (Accés seqüencial per valor)
● σ numdep=5 (EMPLEAT). Igualtat per un camp no clau (Accés directe per valor)
● σ numdep=5 and sou>1000 and sexe=“F” (EMPLEAT) . (Accés mixte per varis valors) - Mètodes de selecció en una selecció simple.
● Cerca lineal (força bruta). Accedir a tots els registres i mirar si compleixen
les condicions. És el més ineficient. (MTP1) Recorregut si camp no clau i cerca si camp clau.
● Cerca dicotòmica. Ens podria servir si les dades de la taula estiguessin ordenades per aquest camp. Normalment els registres no estan ordenats per cap camp.
● Utilització d’índex. Cal disposar d’un índex pel camp a fer la selecció.
- Arbres B+. Ens permeten en molts pocs accessos fer accessos directes per valor.
També ens permeten els accessos seqüencials per valor.
- Basats en la dispersió. Solament accessos directes per valor.
- Altres tipus d’índex.
- Mètodes de selecció en una selecció complexa.
● Selecció conjuntiva en la que hi ha un camp que disposa d’un índex.
σ dni=40115213 and nota>=5 (MATRICULA). Si dni disposa d’un índex caldrà accedir directament a tots els registres que tinguin aquest dni i comprovar quins són els que tenen la notasuperioracinc. IMOLTSMÉS
- Operació reunió (JOIN). Es la que més temps consumeix. Solament veurem el cas de reunions de dues taules.
● Exemple EMPLEAT ⋈ depemp=depnum DEPARTAMENT
● Exemple DEPARTAMENT ⋈ Dnidirector=Dni EMPLEAT - Mètodes per la implementació de reunions.
● Força bruta (dos esquemes repetitius, un dins l’altre). Per cada registre d’una taula
s’accedeix a tots els registres de l’altre). Molt ineficient.
● Com a mínim un dels camps de la reunió disposi d’un índex. Amb un esquema repetitiu es
va accedint a tots els registres de la taula que no disposa de l’índex. Per cada registre
s’accedeix al valors de l’altra taula mitjançant l’índex.
● Altres mètodes - Operació de projecció. És fàcil d’implementar si en la llista d’atributs s’inclou un camp clau. En aquest cas el resultat tindrà el mateix número de registres que la taula i simplement cal fer una passada a la taula seleccionant els camps de la llista.
- Si no conté un camp clau caldrà eliminar els possibles registres duplicats. Es pot fer ordenant i eliminant els duplicats.
- SQL no elimina els duplicats, solament si s’especifica amb la clàusula DISTINCT.
- Com podem veure hi ha molts algorismes per executar les operacions de l’àlgebra relacional. L’optimitzador de la consulta s’encarrega de trobar quins algoritmes aniran millor per resoldre la consulta seguint l’ordre especificat en l’arbre de consulta.
