Grammar-like Functional Rules for Representing Query Optimization Alternatives Guy M. L&man IBM Almaden Research Center San Jose, CA 95120 Abstract Extensible query optmuxahon reqmres that the “repertoue” of alternatIve strate@es for executmg quenes be represented as data, not embedded m the optumzer code Recogmzmg that query op- tmuzers 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 systems can 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 al- ternative plans, m which the rules defmmg alternatives are an extension of the productlons of a grammar to resemble the 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 prop- ertles of theu mputs, such as tuple order and location, and we descnbe a “sue” mechamsm for augmentmg plans to a&eve the reqmred propertles We @ve detaded examples to dustrate the power and robustness of our rules and to contrast them Hnth related Ideas I. Introduction 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 dlscouragmg or slowmg expenmentation wth - and lmplementatlon of - all the new advances m relational technology, such as un- proved loin methods CBABB 79, BRAT 84, DEWI 851, drstnbuted query optmzation CEPST 78, CHU 82, DANI 82, LOHM 851, Permlsslon to copy wlthout fee all or part of this materml IS granted provided that the COPES are not made or mstnbuted for duect commercml advantage, the ACM copyrlght notxe and the title of the pubhcation and Its date appear, and notlce IS gwen that copymg IS by perrmsaon of the Assoclatlon for Computmg Machmery To copy othemse, or to repubhsh, reqmres a fee and/or specdk pertntsston Reproduced by consent of IBM 0 1988 ACM 0-89791-268-3/88/ooo6/0018 $1 50 S~IIUJOUIS [BERN 811, BloomJoms [BABB 79, MACK 861, parallel JOUB on fragments CWONG 831, Jam mdexes CHAER 78, VALD 871, dynanuc creauon of mdexes h4ACK 861, and many other vanatlons of tradmonal processmg strateges The recent surge m mterest 111 extensible database systems CSTON 86, CARE 86, SCHW 86, BAT0 861 has only exacerbated the burden on optl- nuzers, addmg the need to custonuze a database system for a part~cuhu class of appbcations. such as geograptuc CLOHM 83 1, 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 Perhaps the most challengmg aspect 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 optumx- ers are expert systems, several authors have observed that rules show great prormse for 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@es wthout unpactlng the optmuzer, and to encapsulate the strate@es executable 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 In ti paper, we use rules to descnbe how to construct - rather than to alter or to match - plans Our rules “compose” low-level database operations 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 . ‘l&?y are more readily understood, because they enable the DBC to budd mcreasmgly complex plans from common buddmg blocks, the detads of which may be transparent to bun, and . They can be processed more efliereatly dunng optlmlzatron, by simply fmdmg the deflmtlon of any buddmg block that IS refer- enced, usmg a sunple dnztlonary search, much as ts done m macro expanders By contrast, plan transformation rules usually must I We feel ths term more accurately describes the role of adaptmg an uaplemented bat extensible database system than does the term Dorobclre Impkmntw (DBI), WIT by cmy et at [CARE 861 18examme 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 condrtrons that deal wtth those new patterns Our grammar-hke approach IS founded upon a few fundamental observatrons about query opttmrxatton l Ail database operators cunsome and produce a common object - a table, viewed as a stream of tuples that IS generated by accessmg a table [BAT0 87al The output of one operatton becomes the input of the next Streams from mdrvrdual