CMSC424: Programming ProjectDue: November 12, 2009This is a group project, and you should use the same groups as for the class project. There are two partsto the programming project. The first one involves generating and analyzing the query plans that Oraclegenerates. The second part asks you to implement some query processing operators in a Toy RelationalDatabase Management System.Part 1 (3 pts)Oracle has following commands to help with analyzing the plans, and tuning the execution. Otherdatabase systems have their own set of commands.• set timing on; : If this is set, the time taken to execute a query is output at the end.• set autotrace on; : The plan used to execute the query is shown at the end of execution.• Oracle Hints: SQLPlus also allows you to provide “hints” to the optimizer on what kinds of algo-rithms to use, what not to use etc. This can be used to change the plan to something else, if you thinkyou know better than Oracle optimizer (not uncommon in practice). Link to detailed usage is on thecourse webpage. Here are a couple of examples you might want to try out:– Changing join method: You can use hints to change the join method used by the optimizer.select /*+ use_nl(f1, f2)*/ count(*)from friends f1, friends f2where f1.userid2 = f2.userid1;Without the use nl there1, this query would probably use hash join or merge join. use nlforces it to use nested loops join for joining those two tables. Change use nl to use merge oruse hash to force Oracle to use other plans.– Enforcing join order: By adding a clause called “ordered”, you can force the optimizer to usethe same join order as specified in the from clauses.– Using index or not using index: Simiarly, say I had an index on results:create index users_userid_idx on users (userid);select /*+ index(users)*/*from userswhere userid = ’user0’;..forces the optimizer to use an index on the results table to execute this query, whereas:select /*+ no_index(users)*/*from userswhere userid = ’user0’;..forces it to not use the index. By default, it would have probably used an index if one existed.1The syntax is very specific. Hints must appear as shown here.Your tasks:1. Oracle (as with all database systems) stores the “metadata” information in some special tables. Forexample, “all tables” stores the names of all tables, and bunch of additional information. A secondtable “all tab columns” contains the information about all the table attributes, and is used to answerqueries such as “describe groups;”. Write a query that returns the same answer as the “describegroups;” query using the second table. Your query must return similar answer, but not identicalanswer – that would be somewhat harder to manage. (Hint: Use “describe” to see the attributes ofsecond table first).2. Use the autotrace feature to find the plan for the following two queries and draw it (as shown in Figure14.5). Note that the autotrace feature actually only prints out the operators; but the indentation levels,and also the order in which operators are printed out, can be used to deduce the query plan. Also, notedown the time it took to execute the query (it will probably be too small to be measurable).(a) Query 1: Draw the query plan for this query.select u1.name, u2.namefrom users u1, friends f, users u2where u1.userid = f.userid1 and f.userid2 = u2.useridand extract(month from u2.birthdate) = 8and extract(day from u2.birthdate) between 16 and 30;(b) Query 2: Draw the query plan for this query.select*from users where userid NOT IN (select userid from status);(c) Query 3: Draw the query plan for this (somewhat complicated) query, and explain it. Morespecifically, describe how the query is being executed, and what operators Oracle is using foranswering this query.with temp as (select groups.groupid, name, count(userid) as num_membersfrom groups, memberswhere groups.groupid = members.groupidgroup by groups.groupid, name)select namefrom tempwhere num_members = (select max(num_members) from temp);3. Force Query 1 from above to use a nested loops join instead of whichever join it uses, draw the planand note down the time it took in this case (use the use nl hint).4. Query 2 can be made more efficient through use of merge aj (or hash aj) hint. Briefly describe whatthe hint does, use it for the above query and draw that plan (NOTE: it is possible Oracle already doeswhat this hint tries to tell Oracle to do, in which only explain the purpose of the hint).It is fine if you are not successful in making Oracle do what you want as long as you used the hints correctly.Oracle may ignore the hints in some cases, and in other cases, there maybe requirements for using the hintthat are not described.Part 2 (7 pts)The second part of the programming assignment requires you to write an operator in a toy RelationalDatabase Management System, built by us.Description of ToyRDBMS: The ToyRDBMS is written in Java, and uses BerkeleyDB as the underlyingstorage engine. BerkeleyDB does not provide any relational interface at all. In essence you can think ofBerkeleyDB as a persistent key-value store. The Data in BerkeleyDB is stored in a set of “Databases”, eachof which is a key-value store.Our ToyRDBMS maps relations to BerkeleyDB Databases. So each Database stores the tuples correspond-ing to a single relation, indexed by the primary key (which must be specified in the CREATE TABLEcommand).ToyRDBMS supports a very small subset of SQL with many restrictions. The supported commands are:1. CREATE TABLE: Only two data types are supported: “integer” and “string”. The primary key mustbe identified, can only consist of a single attribute, and further must be the first attribute in the list.Example: “create table R (i integer primary key, j integer, s string);”2. DROP TABLE.3. INSERT VALUES: The usual SQL syntax should work.4. SELECT: ToyRDBMS supports a very small subset of the form:select <list of attributes>from <list of tables>where <list of predicates>;The Select Clause can either contain ”*” or a list of attributes. No aliasing is allowed in either theselect clause or the from clause. Only equality predicates are allowed. If a predicate of the type ”R.a= 10” is used, ”R.a” must be on the left hand side.Finally, queries should not contain cycles or should not require Cartesian products.Some further details about the implementation follow. Many of the commands listed below are present in thefile “Makefile”. You
View Full Document
Unlocking...