Semantisk optimering av DBMS-frågor

Den aktuella versionen av sidan har ännu inte granskats av erfarna bidragsgivare och kan skilja sig väsentligt från versionen som granskades den 30 september 2021; kontroller kräver 5 redigeringar .

Semantisk DBMS-frågeoptimering  är processen att validera och omvandla frågesyntaxträdet till en form som lämpar sig för ytterligare optimeringssteg.

I detta skede utförs följande:

  1. Konvertera frågor till kanonisk form;
    1. Avslöjande vyer;
    2. Konvertera underfrågor till sammanfogningar;
    3. Härstamning av predikat
  2. Förenkling av villkor och fördelning av predikat;
  3. Konvertera ett villkorsträd till en urvalsväg.

Konvertera frågor till kanonisk form

Frågor kanoniseras, det vill säga skrivs om för att innehålla det minsta antalet SELECT-satser (join-filter-projection). Där det är möjligt bör frågan reduceras till formen av en enda SELECT-sats. Detta kan tillåta att efterföljande optimeringsfaser genererar en mycket effektivare (med 2-3 storleksordningar) exekveringsplan för komplexa frågor.

Expanderande vyer

Vyexpansion används så att den slutliga frågan endast innehåller referenser till materialiserade relationer (tabeller) och det är möjligt att använda datapipelinebearbetning.

ursprungliga begäran Resultat
välj a från V där cond2

där V väljer a, b från T där cond1

välj ett från T där (cond1 och cond2)

Konvertera underfrågor till sammanfogningar

Att konvertera subqueries till joins är nödvändigt för att tillämpa datapipeline-bearbetning och minimera mängden subquery-resultat som samlas på temporär disk eller RAM.

ursprungliga begäran Resultat
välj distinkt Ta från t där Tb in (välj T1.b från T1 där T1.c < Tc) välj distinkt Ta från T,T1 där Tb = T1.b och T1.c < Tc

Predikat härkomst

ursprungliga begäran Resultat
(A sammanfogar B) där condA och condB (A där condA) join (B där condB)

Förenkla villkor och distribuera predikat

Förenkling av villkor

Det utförs genom att konvertera trädet av logiska operationer till CNF och förenkla den resulterande logiska funktionen.

Omvandlingen av trädet för logiska operationer till CNF utförs enligt följande:

  1. För alla disjunktioner som ingår i direkt form tillämpas den distribuerande lagen:
P ELLER (Q OCH R) = (P ELLER Q) OCH (P ELLER R) (P OCH Q) ELLER R = (P ELLER R) OCH (Q ELLER R)
  1. För alla disjunktioner som visas i omvänd form gäller de Morgans regel :
INTE (P ELLER Q) = INTE P OCH INTE Q

Transformationen fortsätter rekursivt tills trädet består av konjunktioner av beståndsdelen 0 .

Den resulterande booleska funktionen är i konjunktiv normal form , men är redundant. För förenkling används logikfunktionsoptimeringsmetoder, såsom Espresso (Logic) eller Quine-McCluskey .

Fördelning av predikat

Predikatfördelning görs

  1. för alla predikat av formen:

AB pred C

som det finns ett predikat för

AB=DE

Som ett resultat får vi predikatet

DB pred C

där C är en konstant; A,D - relationer; B,E - jämförda attribut. Denna förenkling är baserad på antagandet att det ursprungliga predikatet AB pred C kan vara mer effektivt för relation D.

  1. för varje anslutningsvillkor för vy:

AB pred DE

det omvända tillståndet genereras

DE omvänd pre AB

för att kunna ansluta i omvänd ordning.

Konvertera ett villkorsträd till en hämtningsväg

Efter att ha förenklat villkorsträdet är varje konjunktion i trädet en hämtningsväg. Predikat inom konjunktioner är grupperade efter relation. För att erhålla det slutliga resultatet är det nödvändigt att kombinera resultaten från var och en av provtagningsvägarna.

Se även

Litteratur