Optimizarea interogarilor

Optimizarea interogarilor

Alegerea celei mai bune strategii de executie din variantele disponibile. Se evalueaza costurile fiecarei variante si se va alegea cea cu cot minim. Procesul evaluare - costisitor in cazul cererilor complexe, sau care implica multe relatii/fragmente → in locul variantei optime - metode euristice, specifice expertului uman, care reduc aria de cautare (multimea strategiilor), lasand doar cateva strategii eficiente.

O metoda - reducerea cardinalitatii rezultatelor intermediare. Se realizeaza:

• evaluarea operatorilor unari
• ordonarea operatiilor binare in functie de dimensiunea furnizata.

Őzsu si Valduriez, - complexitatea operatiilor algebrei relationale in functie de cardinalitate. Complexitatea - exprimata prin intermediul unei functii O, n, reprezentand cardinalitatea.

Complexitatea operatorilor din algebra relationala in functie de cardinalitatea relatiilor[1]

In SD inca - inlocuirea operatiunilor de join cu cele de semijoin - propusa[2] pentru sistemele mai vechi care erau sustinute de retele de comunicatie de viteze scazute - pentru a contracara handicapul retelei. Chiar daca tehnologiile avansate de comunicatie furnizeaza medii ce confera intarzieri comparabile cu vitezele operatiunilor simple de intrare/iesire, unele SGBDD folosesc si aceasta strategie in scopul castigarii unui avantaj competitiv.

Optimizarea - statica sau dinamica.

• Strategia de optimizare statica - stabilita din timpul compilarii. Lenta, iar amortizarea costurilor se poate realiza prin memorarea acesteia in memoria cache pentru tot restul sesiunii. Se bazeaza pe statisticile memorate in BD locale referitoare la cardinalitatea unor posibile rezultate intermediare. Aceste statistici - ar trebui sa contin:
• numarul de inregistrari din fiecare relatie
• numarul de duplicate ale fiecarui atribut
• numarul de valori diferite
• valorile minime si maxime pentru fiecare atribut, cardinalitati pentru operatiile de baza, etc.

Furniza rezultate cu precizie cum ar fi recomandat sa se actualizeze dupa fiecare operatie de modificare a continutului BD si sa fie ajustate dupa fiecare interogare efectuata. Operatiile fiind mari consumatoare de timp, se indica lansarea procedurilor de actualizare atunci cand activitatea este scazuta, in general in timpul noptii[3]. Daca statisticile nu sunt actualizate, sau exista dispersii mari intre valorile in BD, strategia aleasa nu va fi optima.

• Prelucrarea dinamica - evaluarile - in timpul executiei, strategia - in functie de ultima executie intermediara, la fel ca intr-un joc de sah. Foloseste statistici numai pentru prima operatie. Chiar daca se restrang treptat variantele de alegerea celei mai bune strategii, timpul de executie poate sa creasca pentru ca la fiecare nou pas sunt necesare analize, validari ale interogarii. Rezultatele cele mai bune sunt date de utilizarea unor metode hibride.[4]

Chiar daca uneori solutiile furnizate prin regulile euristice dau rezultate destul de bune, ele nu ajung la atingerea optimului. Őzsu si Valduriez - 4 algoritmi de optimizare:

Comparatie intre algoritmii de optimizare[6]

Gestiunea accesului concurent in medii distribuite

Sistem centralizat - subsistemul tranzactional al unui SGBD: administrator de tranzactii, planificator, administrator de refacere si administrator de buffere.

• Administratorul de tranzactii dirijeaza executia tranzactiilor.
• In functie de caracteristicile tranzactiei, planificatorul va hotari strategia de control al concurentei in situatia curenta. Strategia trebuie sa maximizeze gradul de concurenta, fara sa afecteze intersectarea cu alte tranzactii.

• Administratorul de refacere intervine la intreruperea sau perturbarea executiei. Repune in functiune sistemul si aduce BD in cea mai apropiata stare de consistenta posibila.
• Administratorul de buffere gestioneaza memoria tampon aferenta executiei tranzactiilor si asigura transferul bidirectional intre memoria de lucru si dispozitivul fizic de stocare.[8]

Toate componentele - in cadrul fiecarui sit al unui SD. Pe langa acestea mai avem un administrator de tranzactii global sau coordonator de tranzactii responsabil cu executia tranzactiilor globale sau locale initiate de situl respectiv. Comunicarea dintre situri - prin componenta de comunicatii de date, care nu este specifica procesului tranzactional.[9]

In SD un controlul al concurentei:

• flexibil la caderile partiale ale sistemului
• sa permita un grad inalt de paralelism al tranzactiilor in conditiile mentinerii integritatii BD
• sa genereze un trafic rezonabil al retelei
• sa nu suprasolicite resursele sistemului
• sa impuna cat mai rar intreruperea tranzactiilor.[10]

Controlul concurentei la sisteme centralizate - evitarea unor anomalii ce caracterizeaza executia simultana a unor tranzactii ce reclama aceleasi resurse: actualizarea pierduta, dependenta nefinalizata si analiza inconsistenta. O metoda de evitare - transformarea accesului concurent in acces secvential - aplicabila doar teoretic. Rezultatul executiilor seriale este reperul in controlul corectitudinii executiilor paralele. Daca exista posibilitatea interferarii unor tranzactii, o planificare este considerata buna ↔ daca rezultatul ei este identic cu al unei planificari seriale - planificare serializabila. Identificarea acestor planificari in momentul executiei nu este o solutie buna. Se recomanda utilizarea unor metode ce garanteaza planificari serializabile. In functie de gradul de concurenta, de probabilitatea de aparitie a interferentelor si de complexitatea si costul implementarii anumitor strategii se pot aplica metode pesimiste, optimiste si mixte.

In SD poate apare incoerenta copiilor multiple. Apare la BD cu fragmente replicate total sau partial, dar si cand e vorba de actualizarea dictionarelor sau cataloagelor.

Cu cat in sistem coexista in acelasi moment mai multe tranzactii care isi pot disputa aceleasi date, cu atat gestiunea lor devine mai complexa. Tranzactiile globale, subtranzactiile acestora si toate care ruleaza, trebuie sa asigure transparenta la nivelul concurentei si a tolerantei la defecte.

Si in cazul SD comparatia se face cu executia seriala a tuturor tranzactiilor. Problema concurentei in SD se complica deoarece avem tranzactii globale, si subtranzactii ale lor care asigura indeplinirea cerintelor tranzactiei globale si sa nu interfereze nici intre ele si nici cu alte tranzactii din sistem. Situatia se agraveaza la aparitia replicilor unor fragmente. O tranzactie globala este responsabila atat de coerenta subtranzactiilor sale, cat si de propagarea eventualelor modificari facute de acestea in toate replicile fragmentelor implicare. Conform atomicitatii tranzactiilor, solutia ar fi ca actualizarile tuturor copiilor - sau niciuna - sa se faca concomitent si inainte de instructiunea COMMIT a interogarii globale. Acest tip de actualizare este greu de realizat in practica - anumite situri s-ar putea sa fie inoperabile in acea perioada, astfel incat copiile fragmentelor stocate pe acesta nu vor putea fi accesate.

Efectuarea actualizarilor copiilor tranzactiilor care ruleaza in SD - cea a actualizarii copiei primare. Copia primara - una din replicile unui obiect, care va propaga actualizarile in copiile care nu sunt primare. Copiile primare - distribuite in toata reteaua nu se incalca principiul autonomiei sau al independentei fata de un sit central → o tranzactie - considerata definitiva in momentul actualizarii copiei primare. Daca copia primara reuseste sa faca toate actualizarile instantaneu si deci inainte de COMMIT-ul tranzactiei globale - reproducere sincrona. Nu intotdeauna se reuseste sincronizarea.

Actualizarea completa - poate fi la un moment ulterior specificat de utilizator, dar aflat inainte de incheierea tranzactiei globale, fie dupa. Produsele comerciale de BDD au incercat sa rezolve esecurile strategiei bazate pe copia primara, prin implementarea unor variante de reproducere asincrona. Daca actualizarile sunt intarziate dupa COMMIT-ul tranzactiei globale ele devin periculoase - se incalca atomicitatea tranzactiilor, creandu-se premiza incoerentei BD. Problema actualizarilor intarziate poate fi tratata prin utilizarea instantelor.[11]

O alta problema a tratarii prin copii primare - indisponibilitatea copiei primare. Rezolvarea acestui impas - alocarea dinamica a statutului de copie primara - in orice moment de functionare, printre toate copiile obiectelor de pe siturile disponibile sa avem copiile primare ale acestora.

Daca in SD daca planificarile subtranzactiilor apartinand unei tranzactii globale, sunt serializabile, → planificarea tranzactiei globale = reuniunea planificarilor subtranzactiilor, va fi si serializabila. Toate subtranzactiile trebuie sa apara in aceeasi ordine in planificarile seriale ale fiecarui sit implicat, indiferent daca se aplica protocoale de control al concurentei bazate pe marci de timp sau pe blocari.

Uneori in BDD nu trebuie aplicate masuri suplimentare de precautie fata de BD centralizate - cazul bazelor de date partitionate. Pentru acele SD in care pentru anumite, sau pentru toate fragmentele exista replici, se impune folosirea unor masuri de precautie suplimentare. Acestea, nu numai ca trebuie sa garanteze serializabilitatea, dar ele trebuie sa evite si situatiile care pot conduce la impasuri.[12]

Controlul accesului prin blocare

Cele mai cunoscute si utilizate protocoale de blocare din cadrul unui mediu centralizat sunt cele din familia 2PL[13].

Protocolul 2PL centralizat - Ipoteza: toate informatiile necesare blocarii si deblocarii sunt mentinute in cadrul unui sit → sistemul detine doar un singur administrator al blocarilor.[14] Functionarea protocolului:

1. Coordonatorul de tranzactii din situl care a lansat tranzactia globala, in functie de informatiile pastrate in catalogul sistemului, va imparti tranzactia in subtranzactii aferente celorlalte situri. Mentinerea coerentei BD - sarcina coordonatorului - daca tranzactia implica actualizari ale unui fragment replicat, coordonatorul - se ocupa de propagarea actualizarii in toate copiile → utilizarea unor blocaje la scriere pentru toate copiile implicate. Copia utilizata ca reper va fi oricare dintre copii, daca se exista chiar cea din nodul curent;
2. Administratorii de tranzactii locali, sau coordonatorul de tranzactii solicita instaurarea si eliberarea de blocaje de la administratorul central;
3. Administratorul global verifica daca blocajele deja existente sunt compatibile cu cele solicitate de fiecare sit. Daca exista compatibilitate sau resursa inca nu a fost blocata se poate acorda blocajul cerut, solicitantul fiind informat de aprobarea primita. In caz contrar, cererea este plasata in coada de asteptare.

Avantajele acestui protocol - gestionarea impasurilor (care nu implica probleme speciale fata de varianta sistemului centralizat), simplitatea lui si costurile reduse de comunicatie, fiind necesare doar n+3 mesaje (1 cerere de blocare, 1 mesaj de acordare a blocajului, n mesaje de actualizare, n confirmari si o cerere de deblocare).

Dezavantajele - posibilitatile multiple de strangulare a nodului care detine controlul tranzactiilor. Mai mult, fie cedeaza tot sistemul, fie terminarea sau lansarea unor noi tranzactii va deveni imposibila in cazul caderii nodului principal.[15]

Abordarea contravine autonomiei solicitate de SD.

Protocolul 2PL de copie primara - administratorii de blocare sunt raspanditi intre mai multe situri si nu - un nod care sa gestioneze acest aspect in mod centralizat. Dintre copiile unui fragment una este copie primara, celelalte fiind considerate copii sclav. Alegerea este intamplatoare. Situl insarcinat cu gestiunea blocarilor pentru situl ce detine copia primara nu trebuie sa fie acelasi cu detinatorul acestei copii.[16]

Acest protocol - o imbunatatire a protocolului 2PL centralizat. Diferenta consta - atunci cand se actualizeaza date din cadrul unui fragment replicat, trebuie identificat atat situl care detine copia primara, cat si cel care se ocupa de gestiunea tranzactiilor pentru situl respectiv. E necesara blocarea la scriere a articolelor de date din copia primara, dupa actualizare modificarile fiind propagate in copiile sclav. Este indicata propagarea actualizarilor cat mai rapid posibil, insa cu permisiunea incalcarii proprietatii de atomicitate. Tranzactia principala este responsabila doar de actualizarea copiei primare → BD va fi temporar inconsistenta. Protocol se recomanda doar in acele BDD in care datele replicate necesita rareori actualizari.

Pot sa intervina probleme atunci cand siturile, care controleaza subtranzactiile pentru un sit ce detine o copie primara, sunt afectate. De aceea, se recomanda existenta unor situri secundare, care intervin doar cand cele primare cad. Chiar daca implementarea este mai complexa, acest protocol e mai eficient si presupune mai putine blocari "la distanta".[17]

Protocolul 2PL distribuit

Administratorii de blocare sunt prezenti in fiecare sit, fiecare fiind responsabil de blocarea resurselor din situl respectiv. Se aplica in System R*.[18] In conditiile nereplicarii datelor, acest protocol este identic cu cel de blocare a copiei primare. In cazul unui mediu replicat se va folosi metoda ROWA pentru controlul actualizarii reproducerilor. Aceasta inseamna ca toate copiile sunt disponibile pentru operatii de citire, dar pentru scrieri, vor fi blocate toate, inainte ca o fractiune a unuia dintre ele sa fie actualizate.

Abordarea blocarii - in mod descentralizat. Gestiunea situatiei de interblocare devine o problema mai complexa decat in cazul protocoalelor amintite anterior, iar costul comunicatiei devine mai ridicat, avand cu n-1 mai multe cereri de blocare, de acordare a lor si de deblocare, rezultand asadar un total de 5n. Se poate ajunge la 4n in cazul in care deblocarea se trateaza ca si in cazul protocolului 2PL strict (deblocarile sunt lasate pe seama COMMIT-ului final).[20]

Protocolul de zavorare a majoritatii - optimizare a protocolului distribuit pentru ca nu implica blocarile si actualizarile tuturor copiilor inainte de finalizarea tranzactiei globale, ci doar a 1/2 din acele copii. Cererile de blocare nu vor fi transmise tuturor celor n situri care detin copia articolului de date, ci doar la cel putin (n+1)/2 din ele. Tranzactia nu se poate derula decat atunci cand s-a ajuns majoritatea intr-o perioada de timp prestabilita. Daca aceasta perioada expira, atunci vor fi anulate toate cererile. Indiferent de rezultatul actiunii siturile vor fi informate asupra starii blocajelor. O singura tranzactie poate detine blocaje la scriere simultane asupra mai multor copii, pe cand atunci cand e vorba de blocaje de citire numarul tranzactiilor este nelimitat.

Dezavantajele - desi fata de cazul anterior numarul mesajelor de cerere de blocaje si de eliberare a lor a scazut de la 2n la n+1, totusi algoritmul genereaza un trafic exagerat tocmai datorita universalizarii principiului "(n+1)/2" si in cazul blocajelor la citire, adica acolo unde ar fi fost de ajuns pentru o singura.[21]

Controlul accesului prin utilizarea marcilor de timp

Functioneaza asemanator cu cele din cadrul sistemelor centralizate. Datorita marcilor de timp pe care tranzactiile si granulele le-au primit la initializare, in momentul in care mai multe tranzactii cer aceleasi resurse, prioritatea va fi de partea tranzactiei mai "in varsta", adica cea cu marca de timp mai mica. Acest criteriu - interpretabil, uneori performantele absolute sau relative masurandu-se in numarul de tranzactii ce ar trebui rulate inapoi, costul anularii anumitor tranzactii etc.

O alta problema - generarea numerelor de secventa. Nu se poate permite generarea marcilor de timp nici centralizat (incalcarea autonomiei, dezastre in cazul caderii generatorului) si nici local fara calificarea sitului care a emis marca → am avea sisteme de numaratoare paralele in care acelasi numar de secventa - eliberat de situri diferite - ar genera incurcaturi in stabilirea ordinii de executie. Se recomanda sincronizarea siturilor in generarea secventelor si calificarea prin intermediul identificatorului de sit. Toate statiile implicate in rezolvarea unei cereri globale vor trebui sa comunice intre ele → prilejul eventualelor ajustari ale marcilor de timp. Astfel, daca un sit primeste un mesaj care contine deja o marca de timp, in mod evident marca ce va fi emisa de catre acesta din urma va fi mai mare decat cea receptionata. Rolul calificarii sitului in cadrul numarului de secventa este doar de a stabili identitatea sitului emitent si nu de gestionare a ordinii.

Avantajele si dezavantajele SD

BDD in general au mai multe avantaje decat dezavantaje, ramanand insa la latitudinea factorilor decizionali sa stabileasca daca un SD si ce SD ar fi bun.

Error! Reference source not found., Error! Reference source not found. sintetizeaza avantajele si dezavantajele SD.

Avantaje

o      Structura organizationala - SD - adapteaza firesc cerintelor organizatorice ale intreprinderilor. Spatiul de lucru - distribuit geografic in cladire, localitate, judet, sau tara. Similitudini cu circulatia informatiilor intr-o intreprindere. Un utilizator efectueaza tranzactii asupra BD locale, pe cand un director de agentie, filiala etc. prin interogari globale poate sa consulte datele tuturor utilizatorilor agentiei sau activitatea intregii intreprinderi.[22]

o      Caracterul partajabil si autonomia locala - Chiar daca o organizatie este distribuita geografic, prin utilizarea unui SD datele nu vor fi proprietatea sitului local. Intre utilizatori - posibilitatea de partajare a anumitor informatii, cum ar fi rapoartele. Un utilizator poate accesa si folosi atat datele din BD locala cat si din celelalte situri. Informatia solicitata cel mai des trebuie sa poata sa fie gasita in vecinatatea imediata. Chiar daca datele sunt partajabile, acest lucru nu va afecta autonomiile individuale. Fiecare sit este autonom si poate functiona si in cazul in care resursele din alte situri nu sunt disponibile. Problematica autonomiei locale - structura organizationala descentralizata. In structuri centralizate, SD - artificiala, deoarece aceste sisteme urmaresc sablonul comportamental al organizatiilor descentralizate.

o      Disponibilitate si fiabilitate crescute - Sistemele centralizate slabe la fiabilitate. Dacanodul central cade, intreg sistemul va deveni inoperabil. SD - datorita fragmentarii si replicarii datelor - functioneaza chiar si in cazul avariei unor situri sau a liniei de comunicatie. Doar situl in cauza va fi afectat si nu vor exista pierderi informationale.

o      Performante imbunatatite - In SD datele sunt plasate in locul in care sunt solicitate cel mai des. Daca nu este situl local, trebuie sa fie relativ apropiat. Cand vorbim despre "distanta" nu ne referim neaparat la proximitate fizica. Un rol important il poate juca lungimea mediului de transmisie (daca exista), viteza si dimensiunea canalului de comunicatie etc.

o      Dezvoltare modulara - In BD centralizate adaugarea unuia sau mai multor membri putea sa creeze probleme serioase datorita SGBD-ului, capacitatea si performanta dispozitivului de stocare, performanta tehnica a nodului central si performanta retelei de calculatoare. La SD expansiunea se poate trata modular, fara a fi afectata activitatea celorlalte situri.

o      Economie - In anii '60 - '70 se considera ca puterea de calcul se reflecta intr-o anumita proportie in costul suplimentar investit intr-un singur sistem de calcul. Cu un cost se putea procura forta de calcul egala cu patratul diferentei de bani investite. Legea lui Grosch - nu -   valabila in ultima perioada. S-a demonstrat ca este mai ieftin sa se investeasca in mai multe calculatoare de performante mai modeste decat sa se mareasca sau sa se achizitioneze un singur calculator de aceeasi putere cu performantele insumate ale acelor calculatoare. Acesta a favorizat expansiunea SD in detrimentul celor centralizate. Alt avantaj financiar - SD pot reduce costul comunicatiei pe distante mari specific unor sisteme centralizate.

Dezavantaje

o      Complexitatea - conceperea si intretinerea unui SD - mai greu decat a unui sistem centralizat. Cerintele lui Date, ingreuneaza munca implementatorilor si administratorilor BD. Natura distribuita, eterogenitati, diferitele grade de transparenta, fragmentarea, replicarea si alocarea complica lucrurile la actualizarea BD, gestiunea tranzactiilor sau prelucrarea si optimizarea interogarilor. Connolly - daca intr-un SD nu se trateaza corect aspectele specifice - riscam ca avantajele se transforme in dezavantaje fata de sistemele centralizate.

o      Lipsa de standarde - in diferite sectoare ale SD: de la arhitecturi, la protocoale specifice accesului la date. Se reflecta in modul de abordare a proiectarii sistemelor. Cu rigoarea ei, aplicarea standardizarii ar conduce si la elaborarea daca nu a unor instrumente, cel putin a unor metodologii de translatare a unui sistem centralizat intr-unul distribuit. Acest lucru este influentat si de respectarea unor standarde pentru sistemele centralizate.

o      Securitatea - atat avantaje cat si dezavantaje. Avantajul - in cazul unor atacuri informatice un SD este mai putin afectat fata de unul centralizat, daca tinta este chiar nodul central. In alte cazuri, SD va dezavantajate - atacul asupra oricarui sit al sistemului centralizat nu va afecta BD, pentru ca aceasta este stocata pe nodul central. SD sunt predispuse unor astfel de atacuri, tocmai datorita naturii lor distribuite. Cu cat se utilizeaza mai mult reteaua de comunicatie, si cu cat intinderea ei este mai mare, cu atat acesta devine un punct mai vulnerabil.

o      Dificultatea controlului integritatii si a concurentei - integritatea datelor - mai greu in SD; BD - fragmente si chiar replicarea lor. Regulile de integritate nu se mentin in totalitate si in cadrul BD divizate. Controlul concurentei se realizeaza in general mai greu in cadrul SD - este necesara transferarea continua a unui volum de mesaje prin intermediul retelei. Uneori se sacrifica tocmai aceste functionalitati primordiale in vederea reducerii traficului in mediul de comunicatie.

o      Lipsa de experienta - Implementarea si proiectarea unui SD necesita persoane cu experienta in proiectare, pe piata nu exista prea multe optiuni pentru alegerea unui SGBDD la preturi rezonabile, ca sa fie la indemana oricarei organizatii care ar avea nevoie de asa ceva.

o      Dificultatea de inlocuire sau schimbare - SD sunt facute la comanda beneficiarului si pe specificul activitatii sale. Daca   intervin elemente noi, implementarea necesita un efort mai mare decat in cazul sistemelor centralizate.