4/19/10&1&Query&Processing&CISC437/637,&Lecture&#13&Ben&Cartere?e&1&Copyright&©&Ben&Cartere?e&Query&EvaluaFon&• To&be&processed&by&the&DBMS,&SQL&queries&need&to&be&1. Parsed&and&translated&into&a&relaFonal,&computable&expression&2. OpFmized&into&an&access%path%and&evalua,on%plan&that&minimizes&computaFon/processing&Fme&3. Evaluated&against&the&actual&data&2&Copyright&©&Ben&Cartere?e&4/19/10&2&Query&EvaluaFon&• Parsing&and&translaFng:&– Check&syntax,&verify&relaFons&– Translate&into&internal&form&corresponding&to&relaFonal&algebra&expression&• OpFmizaFon:&– Formulate&access&path&tree&from&relaFonal&algebra&expression&and&metadata&– Formulate&evaluaFon&plan&• EvaluaFon:&– Execute&evaluaFon&plan&on&indexes&+&tables&to&produce&result&Copyright&©&Ben&Cartere?e& 3&System&Catalog&• The&catalog&stores&metadata&(data&about&data)&for&the&database&– RelaFonal&schema,&informaFon&about&indexes,&informaFon&about&physical&storage&• RelaFon&staFsFcs:&– Ntuples(R),&Npages(R)&• Index&staFsFcs:&– Nkeys(I),&INPages(I),&Iheight(I),&Ilow/IHigh&Copyright&©&Ben&Cartere?e& 4&4/19/10&3&Goals&for&This&Chapter&• Produce&access&paths&and&evaluaFon&plan&– Including&full&algorithmic&specificaFon&• Evaluate&their&cost&(mostly&in&disk&I/O)&– Number&of&disk&seeks&*&average&seek&cost&– Number&of&pages&read&*&average&page&read&cost&– Number&of&pages&wri?en&*&average&page&write&cost&Copyright&©&Ben&Cartere?e& 5&Algorithms&for&EvaluaFng&&RelaFonal&Operators&• Many&different&algorithms,&but&three&common&techniques:&– Indexing:&&if&WHERE&clause&(selecFon&or&join),&use&an&index&to&consider&only&a&small&set&of&records&– Itera,on:&&scan&all&records&in&a&table&in&sequence,&or&all&index&data&entries&in&sequence&– Par,,oning:&&use&sorFng&or&hashing&to&split&input&records;&replace&one&expensive&operaFon&with&a&set&of&cheaper&operaFons&on&smaller&inputs%Copyright&©&Ben&Cartere?e& 6&4/19/10&4&Access&Paths&• Access&paths&consist&of&either&a&file&scan&or&an&index&that&matches&a&selecFon&in&the&query&• Index&match&depends&on&index&type:&– Tree&index&matches&terms&that&involve&a?ributes&in&a&prefix&of&the&search&key&• Index&on&<a,&b,&c>&matches&selecFon&WHERE a=3 AND b=5,&but&not&WHERE b=3!– Hash&indexes&matches&terms&that&involve&every&a?ribute&of&the&search&key&• Index&on&<a,&b,&c>&matches&selecFon&WHERE a=3 AND b=5 AND c=7&but&not&WHERE a=3 AND b=5!Copyright&©&Ben&Cartere?e& 7&Complex&Logical&SelecFons&• SelecFon&criteria&can&include&logical&ANDs&and&ORs&– (a&=&3&AND&b&=&5)&OR&c&=&3&OR&d&<&7&• Before&processing,&these&are&translated&to&conjunc,ve%normal%form&(CNF)&– AND&groups&of&ORs&– (a=3&OR&c=3&OR&d<7)&AND&(b=5&OR&c=3&OR&d<7)&Copyright&©&Ben&Cartere?e& 8&4/19/10&5&SelecFvity&of&Access&Paths&• Selec,vity&is&the&number&of&pages&retrieved&from&disk&by&an&access&path&– Including&index&pages&and&table&pages&• The&most%selec,ve&access&path&is&the&one&that&retrieves&the&fewest&pages&• Each&conjunct&in&the&selecFon&filters&a&table&down&to&just&matching&records;&the&number&of&these&is&the&reduc,on%factor&Copyright&©&Ben&Cartere?e& 9&SelecFon&Algorithms&• We&have&discussed&the&cost&of&selecFon&in&the&context&of&indexing&– Scan&cost,&equality&query&cost,&range&query&cost&– SelecFvity,&clustered&vs&unclustered&• That&discussion&applies&to&query&processing&as&well&– Although&now&we&must&calculate&cost&given&a&parFcular&index&type,&rather&than&choosing&an&index&type&to&minimize&cost&• Focus&on&conjuncFons&and&disjuncFons&Copyright&©&Ben&Cartere?e& 12&4/19/10&6&EvaluaFng&ConjuncFonkOnly&SelecFons&• Simple&approach:&– Use&one&index&that&matches&one&of&the&clauses&– Scan&matching&records&for&matches&to&other&clauses&• Be?er&approach:&– Composite&key&index&• Possibly&be?er&approach:&– MulFple&indexes&with&record&pointers&– Intersect&sets&of&pointers&before&retrieving&records&Copyright&©&Ben&Cartere?e& 13&EvaluaFng&SelecFons&with&DisjuncFons&• Analogous&to&conjuncFons:&– Get&record&pointers&from&indexes&– Find&union&of&pointer&sets&before&retrieving&records&• The&catch:&– If&even&one&field&is&not&indexed,&it&will&require&a&full&scan&to&complete&the&union&– It&is&not&usually&wise&to&keep&indexes&on&everything&• DisjuncFons&are&not&easy&to&do&efficiently&Copyright&©&Ben&Cartere?e& 14&4/19/10&7&ProjecFon&Algorithms&• Efficient&computaFon&of&projecFons&is&only&necessary&when&DISTINCT&is&specified&– EliminaFng&duplicates&is&the&hard&part&• Use&parFFoning:&– Sort&records&by&the&projecFon&fields&• SorFng&places&duplicates&next&to&each&other&• Linear&scan&can&be&used&to&eliminate&them&– Or&build&hash&table&on&projecFon&fields&• Duplicates&idenFfied&while&table&is&built&• Not&so&good&if&data&too&large&for&memory&Copyright&©&Ben&Cartere?e& 15&Join&Algorithms&• Joins&are&very&common&but&expensive—efficient&algorithms&are&valuable&• Two&common&algorithms:&– Nestedkloop&join&– Sortkmerge&join&• Simple&unindexed,&uncached&nestedkloop&join&of&R1&and&R2&involves&scanning&R2&for&each&record&in&R1&Copyright&©&Ben&Cartere?e& 16&4/19/10&8&Indexed&NestedkLoop&Join&• If&there’s&an&index&on&the&join&condiFon&in&one&of&the&relaFons,&use&it&to&improve&efficiency&– Specifically,&use&the&indexed&relaFon&in&the&inner&loop&– This&ensures&that&each&record&in&the&inner&relaFon&is&processed&at&most&once&Copyright&©&Ben&Cartere?e& 17&SortkMerge&Join&• Use&idea&of&merge&sort:&– Sort&both&relaFons&by&the&join&condiFon&– Scan&sorted&relaFons&concurrently&– Matching&records&added&to&result&• This&can&be&done&with&no&indexes&• It&is&actually&more&efficient&that&an&indexed&nested&loop&– Assuming&sorFng&can&be&done&efficiently&– And&depending&on&selecFvity&Copyright&©&Ben&Cartere?e& 18&4/19/10&9&Complex&Joins&• ConjuncFve&joins:&– A&join&with&many&condiFons&ANDed&together&– Use&nestedkloop,&or&compute&join&on&one&of&the&condiFons&then&scan&remaining&records&• DisjuncFve&joins:&– A&join&with&many&condiFons&ORed&together&– Use&nestedkloop,&or&compute&joins&for&each&condiFon&separately&then&take&set&union&Copyright&©&Ben&Cartere?e& 19&AggregaFon&• Similar&to&duplicate&eliminaFon:&&&–