go backsqlschool blogs list

Εισαγωγή στον Query Optimizer του SQL Server 2008

by Antonios Chatzipavlis

Ο Query Optimizer στον SQL Server είναι αυτός που αποφασίζει με ποιο τρόπο (query plan) θα εκτελεστεί το οποιοδήποτε sql statement το οποίο δίνουμε. Επειδή είναι κάτι το οποίο είναι εσωτερικό στη μηχανή του SQL Server, επειδή δεν παρέχει πολλά χαρακτηριστικά, αλλά δεν υπάρχουν και αρκετοί "τρελλοί" που να ασχολούνται με αυτόν , είναι ίσως από τα λίγα κομμάτια του SQL Server που ακούγονται πολύ αλλά δεν εξηγούνται πολύ.

Διαβάζοντας το συγκεκριμένο άρθρο φιλοδοξώ να είστε σε θέση να κατανοείτε, τουλάχιστον σε υψηλό επίπεδο, το γιατί επιλέχθηκε ο συγκεκριμένος τρόπος εκτέλεσης για το sql statement το οποίο δώσατε. Βέβαια ο σκοπός μου δεν είναι αυτός. Ο σκοπός μου είναι να μπορείτε να κάνετε επίλυση των προβλημάτων με τα οποία θα έρθετε αντιμέτωποι. Για να γίνει όμως αυτό θα πρέπει να διαβάσετε και όλα τα επόμενα που θα γράψω για το θέμα αυτό.

Ας πάρουμε τα πράγματα από την αρχή, και ας τα δούμε πρώτα από όλα σε υψηλό επίπεδο.

Σημείωση προς τον αναγνώστη του άρθρου αυτού.

Καλό θα ήταν να ανακαλέσεις στην μνήμη σου όσες γνώσεις έχεις από σχεσιακή άλγεβρα.

Κάθε φορά που δίνετε ένα sql statement για εκτέλεση γνωρίζουμε ότι αυτό γίνεται compile. Στην πραγματικότητα η διαδικασία αυτή περιλαμβάνει τα εξής βήματα τα οποία εκτελούνται με την ακόλουθη σειρά Parse -> Bind -> Optimize -> Execute.

Parsing

Στην φάση αυτή το sql statement μεταφράζεται σε μια δενδροειδής παράσταση (tree representation ή query tree). Κάθε κόμβος (node) της παράστασης αυτής αντιπροσωπεύει και μια "λειτουργία" που πρέπει να γίνει πάνω στο sql statement το οποίο έχουμε δώσει προς εκτέλεση. Στην πραγματικότητα δεν το λέμε λειτουργία αλλά τελεστή (operator), και καλό είναι έτσι να το ξέρουμε, απλά χρησιμοποιώ τον όρο λειτουργία εδώ για γίνει κατανοητό. Από εδώ όμως και στο εξής θα το λέω operator.

Για παράδειγμα έστω ότι έχω το sql statement

SELECT *

FROM CUSTOMERS C

INNER JOIN ORDERS O ON C.CUSTOMERID=O.CUSTOMERID

WHERE O.ORDERDATE ='19960101'

Αυτό στην δενδροειδή μορφή του θα είναι κάτι αντίστοιχο με το παρακάτω σχήμα

clip_image002

Εδώ θα πρέπει να επισημάνω ότι ο query proccesor στην πραγματικότητα προσπαθεί να συνδυάσει τους παραπάνω logical operators με τους παραγματικούς physical operators που είναι και αυτή που εκτελούνται. Μια τέτοια περίπτωση στο παράδειγμα μας είναι το Inner Join όπου είναι ο logical operator, σε αυτή την περίπτωση ο query optimizer επιλέγει τον αλγόριθμο με τον οποίο θα εκτελέσει αυτό (merge, hash ή nested).

Binding

Στην φάση αυτή γίνονται μια σειρά από ελέγχους πάνω στο δεδομένο sql statement, όπως το να διαβαστούν τα metadata και να διασφαλισθεί ότι τα πεδία και οι πίνακες υπάρχουν και μπορούν να προσπελασθούν από τον χρήστη που έστειλε το sql statement. Επίσης στη φάση αυτή ελέγχει αν τα πεδία τα οποία εμφανίζονται σε GROUP BY έγκυρα κ.α.

Optimization

Και φτάσαμε στην ουσιαστικότερη φάση. Αφού όλα τα παραπάνω έχουν γίνει επιτυχώς ο Query Optimizer αρχίζει την διαδικασία εύρεσης του καταλληλότερου execution plan. Μια διαδικασία που θα μας πάρει αρκετές γραμμές για να την εξηγήσω, οπότε νομίζω ότι είναι η καλύτερη στιγμή να πάτε να φτιάξετε ένα καφέ, να βάλετε ένα ποτάκι, μια πορτοκαλάδα και να πάρετε και τα χάπια σας.

Υπάρχουν πολλοί τρόποι για την εκτέλεση του query που δίνουμε στον SQL Server. Όμως ποιο είναι το κατάλληλο; Με ποιο τρόπο θα γίνει αυτή η επιλογή; Πόσο γρήγορα θα γίνει αυτή η επιλογή; Είναι σίγουρα η καλύτερη επιλογή;

Πολλά ερωτήματα ε;

Σίγουρα δεν το ποιο απλό πρόβλημα. Είναι δύσκολο, σύνθετο και πολλά άλλα επίθετα.

Ας ξεκινήσουμε όμως σιγά σιγά. Έστω ότι έχω το παρακάτω query

SELECT * FROM A

INNER JOIN B ON A.ACOL=B.BCOL

INNER JOIN C ON B.BCOL=C.CCOL

INNER JOIN D ON C.CCOL=D.DCOL

INNER JOIN E ON D.DCOL=E.ECOL

Το παραπάνω query έχει πολλά execution plans, και αυτό διότι έχει joins τα οποία και μπορούν να υπολογιστούν με διαφορετική σειρά. Θα μπορούσε να εκτελεσθεί με την σειρά ABCDE, ACBDE, ACDBE,… και με διαφορετική τοπολογία A JOIN C, C JOIN B,… .Αυτό σημαίνει ότι ο αριθμός των execution plans είναι μεγαλύτερος από N! (Nx(N-1)x(N-2)x…). Όπως εύκολα γίνεται κατανοητό αν μεγαλώσει ο αριθμός των πινάκων τότε μεγαλώνει και ο αριθμός των συνδιασμών. Αυτό σημαίνει ότι χρειαζόμαστε μνήμη. Και εδώ είναι το θέμα μας. Σε ένα x32 με x86 Intel ο SQL Server έχει 1.6 GB μνήμη διαθέσιμη για κάθε query compilation. Αυτό σημαίνει ότι δεν μπορεί να αποθηκεύσει όλους τους δυνατούς συνδυασμούς σε αυτή. Αλλά ακόμα και να έχει την δυνατότητα αυτή ο χρήστης θα πρέπει να περιμένει αρκετά μέχρι να γίνουν όλοι οι δυνατοί συνδυασμοί. Εδώ έχετε ο φοβερός σχεδιασμός του query optimizer, ο οποίος κάνει χρήση ενός heuristic συστήματος το οποίο οδηγείται από τα στατιστικά (τι έγραψα τώρα, θα το καταλάβετε παρακάτω σιγά σιγά).

Πολλοί πιστεύουν, και για πολλά χρόνια στο παρελθόν ήμουν και εγώ μέσα σε αυτούς, ότι ο query optimizer επιλέγει το καλύτερο , το απόλυτα καλύτερο, execution plan. Όμως αυτό δεν είναι αλήθεια, και εγώ το κατάλαβα με τα χρόνια και με την συνεχή ενασχόληση μου με τον SQL Server. Δεν είναι τυχαίο ότι αρκετές φορές σε ερωτήσεις απαντάω με την έκφραση "εξαρτάται". Και μην αρχίσετε τώρα τα α καλά στην τύχη διαλέγει και άλλα τέτοια, διότι δεν είναι έτσι τα πράγματα. Οι παράγοντες που λαμβάνονται υπόψη είναι πάρα πολλοί, και ο query optimizer έχει την δυνατότητα να βρει το απόλυτα κατάλληλο execution plan, εφόσον όλα είναι στην ιδανική κατάσταση. Αλλά σίγουρα δεν θα επιλέξει το χειρότερο. Η επιλογή του θα είναι τέτοια που θα έχουμε φτάσει στο δυνατό καλύτερο. Μάλιστα είναι έτσι σχεδιασμένος ώστε να έχει την δυνατότητα να φτάσει γρήγορα σε αυτό, και το κάνει. Αλλά για το τέλειο θέλει περισσότερο χρόνο και μνήμη.

Στην ουσία ο query optimizer είναι ένα δυνατό search framework, και έχει την δυνατότητα να συγκρίνει πολλά εναλλακτικά execution plans με ακρίβεια. Είναι η χαρά των μαθηματικών αλγορίθμων πληροφορικής. Κάθε γραμμή κώδικα του έχει γίνει με βάση αυτούς τους αλγόριθμους. Αυτό τον κάνει να είναι αξιόπιστος και αποτελεσματικός. Όμως για να πάμε λίγο πιο βαθιά.

Το search framework το οποίο υπάρχει μέσα στον query optimizer αποτελείται από πολλά components τα οποία παρακάτω θα προσπαθήσω να τα εξηγήσω όσο ποιο απλά γίνεται.

Για αρχή θα πρέπει να καταλάβουμε ότι διέπετε από κανόνες (Rules). Τι σημαίνει αυτό; Για κάθε query tree o query optimizer το μετατρέπει στην μνήμη σε κάτι ισοδύναμο αλλά διαφορετικό. Αυτές οι μετατροπές γίνονται με βάση κάποιους κανόνες, για παράδειγμα έχω ένα πίνακα Α που γινεται inner join με ένα πίνακα Β. Αυτό είναι ισοδύναμο με το Β INNER JOIN A, διότι και στις δύο περιπτώσεις θα γυρίσουν τον ίδιο αποτέλεσμα. Σας θυμίζει κάτι αυτό; Αν όχι ας το αποκαλύψουμε, είναι μαθηματικά Α Γυμνασίου, αντιμεταθετική ιδιότητα της πρόσθεσης. Με τους κανόνες αυτούς παράγει τα εναλλακτικά execution plans. Βέβαια δεν είναι όλα απλά μαθηματικά, όπως επίσης πρέπει να ληφθεί υπόψη ότι σημαντικό παράγοντας είναι και ο χρόνος που απαιτείται για να παραχθούν όλα αυτά. Για αυτό το λόγο γίνεται χρήση του heuristic συστήματος που ανέφερα παραπάνω . Με την χρήση των κανόνων γίνεται το "ξαναγράψημο" του query tree σε μια νέα μορφή η οποία ονομάστηκε substitution rules. Οι κανόνες οι οποίοι βασίζονται στα μαθηματικά λέγονται exploration rules. Το παραγόμενο αποτέλεσμα των μετατροπών (substitution) δεν μπορεί να εκτελεστεί, έτσι με κανόνες πάλι γίνεται μετατροπή των λογικών δέντρων σε φυσικά τα οποία είναι αυτά τα οποία μπορούν να εκτελεστούν και τα ονομάζουν implementation rules. Το καλύτερο από αυτά τα φυσικά δέντρα είναι και αυτό που επιλέγεται για να γίνει η εκτέλεση στο sql statement, είναι με άλλα λόγια το τελικό execution plan.

Βέβαια για να γίνουν όλα τα παραπάνω το search framework του query optimizer θα πρέπει να έχει τις απαραίτητες πληροφορίες ώστε να γίνει η σωστή χρήση των κανόνων. Αυτές οι πληροφορίες λέγονται properties (τι άλλο θα μπορούσε να είναι ;)) και είναι στοιχεία που υπάρχουν στον κάθε κόμβο του δέντρου. Για παράδειγμα ένα τέτοιο property είναι το set των πεδίων που φτιάχνουν unique key στα δεδομένα στο παρακάτω query

SELECT A,B,MAX(C) FROM T1 GROUP BY A,B

Αυτό έχει το παρακάτω query tree:

PROJECT (A,B,MAX(C)) ->

GROUP & AGGREGATION (G: A,B - A: MAX(C)) ->

GET (T1)

Εάν στον πίνακα μας δεν έχουμε unique constraint στα πεδία (Α,Β) τότε θα πρέπει να γίνει η ΜΑΧ(C) για όλα τα records που εκπληρώνουν το group by. Έτσι το execution plan θα είναι το παρακάτω.

clip_image004

Αν όμως έχω unique key στα πεδία (Α,Β) τότε έχω μοναδικότητα και η MAX(C) δεν έχει να υπολογίσει παρά μόνο ένα record. Αυτό έχει σαν αποτέλεσμα το παρακάτω execution plan. Όπως θα παρατηρήσετε σε αυτό δεν υπάρχει grouping (Sort & stream Aggregate).

clip_image006

Πληροφορίες (properties) σαν αυτή συλλέγονται κατά την φάση του optimization ώστε να βοηθήσουν τους κανόνες ώστε να παράξουν γρηγορότερα το execution plan. Ενδεικτικά αναφέρω μερικές όπως predicates, join conditions, partitioning, check constraints.

Μέχρι τώρα έχουμε αναφέρει ότι παράγονται πολλά εναλλακτικά πλάνα εκτέλεσης. Σε κάποια sql statements ενδεχομένως να είναι τεράστιος ο αριθμός τους. Σε αυτές τις περιπτώσεις υπάρχουν μηχανισμοί οι οποίοι αποτρέπουν τα διπλά όμοια. Αυτό φυσικά γίνεται για να εξοικονομηθούν μνήμη και χρόνος, γιατί όπως έχω αναφέρει παραπάνω είναι δεδομένη το πόση μνήμη θα χρησιμοποιήσει για κάθε query κατά την φάση στην οποία είμαστε (optimization) (1,6 GB). Η δομή αυτή ονομάζεται Memo structure και ένας από τους βασικούς της σκοπούς είναι να βρίσκει τα προηγούμενα sub-trees ώστε να μην τα ξανακάνει optimize. H διάρκεια ζωής του είναι όσο διαρκεί το optimization. Δουλεύει με την λογική να αποθηκεύει το ισοδύναμα δέντρα σε groups. Επίσης θα πρέπει να αναφερθεί ότι στις περιπτώσεις που υπάρχει μεγάλο πλήθος από groups και εγκυμονείτε ο κίνδυνος να είναι run out of memory, o query optimizer επιλέγει το καλύτερο από τα υπάρχοντα.

Execution

Με όλα τα παραπάνω υπομάλης η επόμενη φάση είναι να γίνει η εκτέλεση και να πάρουμε το αποτέλεσμα.

Εδώ σταματάει η εισαγωγή μου για το συγκεκριμένο θέμα. Σύντομα θα προχωρήσω σε περισσότερο βάθος στο θέμα. Αυτό που θέλω όμως να επισημάνω είναι ότι θέμα είναι αρκετά περίπλοκο με πολλά internal components και features. Αυτό σημαίνει ότι είναι φυσιολογικό κανείς μας να έχει την απόλυτη γνώση του query optimizer, και αυτό διότι από έκδοση σε έκδοση μπαίνουν νέα, αλλάζουν παλιά. Όμως όσο περισσότερα γνωρίζουμε για αυτόν τόσο ευκολότερα θα είμαστε σε θέση να εξετάζουμε τα execution plans και να βρίσκουμε τα τυχόν προβλήματα τους. Επίσης θα μας βοηθήσει αυτή η γνώση στον καλύτερο σχεδιασμό των βάσεων μας, με αποτέλεσμα να έχουμε καλύτερη ποιότητα εφαρμογών.

Ημερομηνία: 13 June 2010 16:00
Αξιολόγηση:
Κατηγορίες:
Tags:
Share it:

Αφήστε το σχόλιο σας - Leave your comment

Τα σχόλια έχουν κλείσει.
Επιτρέπονται μόνο τα σχόλια από τα μέλη του SqlSchool.gr.


newsletter subscription

Εάν επιθυμείτε να λαμβάνετε ενημέρωση από εμάς, δώστε μας το e-mail σας.
PASS chapter logo
Official Professional Association for SQL Server (PASS) chapter for Greece
Join to PASS