Berkeley COMPSCI 262A - Grammer-like Functional Rules for Representing Query Optimization Alternative (10 pages)

Previewing pages 1, 2, 3 of 10 page document View the full content.
View Full Document

Grammer-like Functional Rules for Representing Query Optimization Alternative



Previewing pages 1, 2, 3 of actual document.

View the full content.
View Full Document
View Full Document

Grammer-like Functional Rules for Representing Query Optimization Alternative

53 views


Pages:
10
School:
University of California, Berkeley
Course:
Compsci 262a - Advanced Topics in Computer Systems
Unformatted text preview:

Grammar like Functional Rules for Representing Query Optimization Alternatives Guy M L man IBM Almaden Research Center San Jose CA 95120 BERN 811 BloomJoms BABB 79 MACK 861 parallel on fragments CWONG 831 Jam mdexes CHAER 78 VALD 871 dynanuc creauon of mdexes h4ACK 861 and many other vanatlons of tradmonal processmgstrateges The recent surge m mterest 111extensible database systems CSTON 86 CARE 86 SCHW 86 BAT0 861 has only exacerbated the burden on optlnuzers addmg the need to custonuze a database system for a part cuhu class of appbcations such as geograptuc CLOHM 831 CAD CAM or expert systems Now optmuzen must adapt to new access methods storage managers data types user defmed functions etc all combmed m novel ways Clearly the titlonal speclficatlon of aU feasible strateges m the optmuzer code cannot support such flu y Abstract S IIUJOUIS JOUB Extensible query optmuxahon reqmres that the repertoue of alternatIve strate esfor executmg quenes be represented as data not embedded m the optumzer code Recogmzmg that query optmuzers are essentlaliy expert systems several researchers have suggested usmg strategy rules to transform query execution plans into alternatlve or better plans Though extremely flexrble these systemscan be very mefflclent at any step m the processmg many rules may be ehable for apphcatlon and comphcated cond ons must be tested to detemune that ehgbtity dunng umfuzatlon We present a constructwe buddmg blocks approach to defmmg alternative plans m which the rules defmmg alternatives are an extension of the productlons of a grammar to resemblethe defuution of a funcuon m mathematics The extensions pernut each token of the grammar to be parametnzed and each of its alternative deflmtlons to have a complex con tlon The termmals of the grammar are base level database operations on tables that are mterpreted at run me The non termmals are defined declaratively by productlon rules that combme those operauons mto meamngful plans for executton Each producuon produces a set of alternative plans each havmg a vector of propeties mcludmg the estunated cost of producmg that plan Producttons can reqmre certam propertles of theu mputs such as tuple order and location and we descnbe a sue mechamsmfor augmentmg plans to a eve the reqmred propertles We ve detaded examples to dustrate the power and robustnessof our rules and to contrast them Hnthrelated Ideas Perhapsthe most challengmgaspect of extensible query optmuzatlon is the representation of alternative execution strateges Ideally this representation should be ready understood and mod d by the Database Custormzer DBC Recogmzmg that query optumxers are expert systems several authors have observed that rules show great prormsefor t purpose CULLM 85 FREY 87 GRAE 87al Rules provide a high level declamt ve I e non procedural and compact speclftcatlon of legal altematwes wluch may be mput as dota to the optmuzer and traced to explam the ongm of any execution plan Thus makes tt easy to m y the strate eswthout unpactlng the optmuzer and to encapsulatethe strate esexecutable by a particular processor m a heterogeneous network But how should rules represent alternative strate es The EXODUS project CGRAE 87a GRAE 87bl and Freytag FREY 871 use rules to transform a gwen execution plan mto other feasible plans The NAIL project CULLM 85 MORR 861 employs capture rules to determme whch of a set of avadable plans can be used to execute a query I Introduction In ti paper we use rules to descnbe how to construct rather than to alter or to match plans Our rules compose low level databaseoperations on tables such as ACCESS JOIN and SORT mto higher level operations that can be re used m other defuutions These constructive bmldmg blocks rules which resemble the productions of a grammar have two major advantages over plan transformation rules Ever smce the fast query optumzers WONG 76 SELI 791 were budt for relational databases revlsmg the repertoue of ways to construct a procedural executton plan from a non procedural query has reqmred comphcated and costly changes to the optmuzer code Itself ms has hted the repertoire of any one optmuzer by dlscouragmgor slowmg expenmentation wth and lmplementatlon of all the new advances m relational technology such as unproved loin methods CBABB 79 BRAT 84 DEWI 851 drstnbuted query optmzation CEPST 78 CHU 82 DANI 82 LOHM 851 l y are more readily understood because they enable the DBC to budd mcreasmglycomplex plans from common buddmg blocks the detads of which may be transparent to bun and They can be processedmore efliereatly dunng optlmlzatron by simply fmdmg the deflmtlon of any buddmg block that IS referenced usmg a sunple dnztlonarysearch much as ts done m macro expanders By contrast plan transformation rules usually must Permlsslonto copy wlthout fee all or part of this materml ISgranted provided that the COPES are not madeor mstnbuted for duect commercmladvantage the ACM copyrlght notxe and the title of the pubhcation and Its date appear and notlce ISgwen that copymg ISby perrmsaon of the Assoclatlon for Computmg Machmery To copy othemse or to repubhsh reqmresa fee and or specdk pertntsston I Reproduced by consent of IBM 0 1988ACM 0 89791 268 3 88 ooo6 0018 1 50 18 We feel ths termmoreaccuratelydescribesthe role of adaptmgan uaplemented bat extensibledatabasesystemthan doesthe term DorobclreImpkmntw DBI WIT by cmy et at CARE 861 examme a large set of rules and apply comphcated condtttons on each of a large set of plans generated thus far m order to detemune tf that plan matches the pattern to which that rule apphes As new rules create new patterns extstmg rules may have to add condrtronsthat deal wtth those new patterns can make extensrons to rules properttes and database operators Havmg thoroughly described our approach we contrast tt wrth related work m Sectton 6 and conclude m Sectton 7 2 Plan Generation Our grammar hke approach IS founded upon a few fundamental observatrons about query opttmrxatton l In thm sectron we descnbe the form of our rules We must first define what we want to produce wrth these rules namely a query evaluahon plan and tts constttuents Ail database operators cunsome and produce a common object a table viewed as a stream of tuples that ISgeneratedby accessmg a table BAT0 87al The output of one operatton becomesthe input of the next Streams from mdrvrdual tables are merged by Jorns eventually mto a single stream FREY 87 GRAB 87al l 2 1 Plans Optumxers construct iegai sequences of


View Full Document

Access the best Study Guides, Lecture Notes and Practice Exams

Loading Unlocking...
Login

Join to view Grammer-like Functional Rules for Representing Query Optimization Alternative and access 3M+ class-specific study document.

or
We will never post anything without your permission.
Don't have an account?
Sign Up

Join to view Grammer-like Functional Rules for Representing Query Optimization Alternative and access 3M+ class-specific study document.

or

By creating an account you agree to our Privacy Policy and Terms Of Use

Already a member?