Overview

 <data>
    <song title="SexyBack (radio version)" length="208.927" sha1="13a4fd349b19aa1a1007c8c1f48a2b53">
        <artist>Justin Timberlake</artist>
        <artist>Timbaland</artist>
        <album>FutureSex/LoveSounds</album>
        <album>SexyBack (single)</album>
    </song>
    <user username='michael' password='test'>
	<rating song='13a4fd349b19aa1a1007c8c1f48a2b53' score='10'/>
    </user>
</data>

tar xvf ~cs186/fa08/hw4/skel.tar

rm -f db/development.sqlite3; sqlite3 db/development.sqlite3 < schema.sql

sqlite3 db/development.sqlite3

script/server -p <port>

sqlite> explain select * from songs WHERE SHA1 = "793d5c8018384ff24983d55b6ca3ad38";;
addr  opcode          p1          p2          p3                               
----  --------------  ----------  ----------  ---------------------------------
0     Goto            0           23                                           
1     Integer         0           0                                            
2     OpenRead        0           2                                            
3     SetNumColumns   0           3                                            
4     Integer         0           0                                            
5     OpenRead        1           3           keyinfo(1,BINARY)                
6     String8         0           0           793d5c8018384ff24983d55b6ca3ad38 
7     IsNull          -1          20                                           
8     MakeRecord      1           0           a                                
9     MemStore        0           0                                            
10    MoveGe          1           20                                           
11    MemLoad         0           0                                            
12    IdxGE           1           20          +                                
13    IdxRowid        1           0                                            

$ ~cs186/pgsql/bin/initdb ~/pgdata $ ~cs186/pgsql/bin/pg_ctl -D ~/pgdata -l hw3.log start $ ~cs186/pgsql/bin/createdb colleges

• Create tables and import data into the database. We are creating three tables: 'rankings' and 'financials' and 'students' 

$ ~cs186/pgsql/bin/psql colleges -f ~cs186/Hw3/hw3.sql

 

1.      SOME EASY STUFF

Start psql and make sure you are running version 8.2.4 (it tells you when it starts up).  Then, using queries in psql, examine the set of tables and access methods in the database you just created. In particular examine the relation Rankings. Answer the following questions:

A. What are the attributes of the Students relation?




B. How many indexes are built on the Rankings relation? Name them and write down their type.




C. How many tuples are there in the Rankings relation?

D. How many distinct values of  “gradrate” does the query planner estimate there are for the Rankings relation?  (hint: Query pg_stats to find out)

E. How many distinct values of “gradrate” are there actually in the rankings table? (hint: it’s probably easiest to run a query to compute this!)

F. What query did you use to find the answer to E? 

 

 

2.      USING THE QUERY PLAN VIEWER

This question requires you to use the PostgreSQL query plan visualization command EXPLAIN. Read the documentation for EXPLAIN at the link given above.   Note that (like System R) EXPLAIN estimates query costs in units of disk I/Os (CPU instructions are added in by multiplying times a conversion factor).
Consider the following query:

SELECT * FROM rankings WHERE state = 'CA'; 

Answer the following questions looking at the query plan generated by the EXPLAIN command:

A. Briefly describe the plan chosen.   (e.g., what kind of scan is used?).

    

B. In what order would the tuples be returned by this plan? Why?

    

    

C. What is the estimated total cost of running the plan?

    

D. What is the estimated result cardinality for this plan? The estimated result cardinality is the number of colleges that the optimizer estimates to be in California.   Looking at the statistics, why does the optimizer come up with this estimate?

    

    

E. How many colleges actually do have “state = 'CA'”?  (hint: it’s probably easiest to run a query to compute this!)

    

F. Looking at the statistics, what are the top 10 states with the most colleges and the percentage of colleges in each of those state? (hint: you can select these by querying on the pg_stats table) 

    

G. Which value of  “state” is actually the most popular, and how many tuples have that “state”? How did you figure this out (what query did you use) ?

 

3.      SELECTS WITH INDEXES

Consider the same query from previous question: 

SELECT * FROM rankings WHERE state = 'CA'; 

Answer the following questions looking at the plans and the access methods:

A. Create a btree index on the attribute state of the relation Rankings. What is the plan chosen for the query now?   (e.g., what kind of scan is used and what is scanned?).

 

B. What is the estimated total cost of running the plan?

    

    

C. Compare this plan with the plan obtained in question 2.A above.  Which is cheaper and why?

 

 

 

4.      RANGE SELECTS

DROP the index that you created for Question 3. Don't forget to VACUUM ANALYZE

Now analyze the query plan that PostgreSQL comes up for the following query: 

SELECT * FROM rankings WHERE gradrate < 10;

Answer the following questions:

A. How many ranking tuples that have gradrate < 10 does the optimizer think there are?

 

B. How does the optimizer arrive at this estimate of the number of tuples? That is, what calculations does it perform, and where does the supporting data come from?

 

 

    

C. In what order will the tuples be returned by this plan?

 

    

D. What is a value of the constant (i.e. '10' in the above query) such that the optimizer chooses a different plan? What is that plan and why does the optimizer think it will be cheaper than the previous plan when used with this new constant?

 

     

    

E. Explain why one of the access methods is costlier than the other.

 

5.      SIMPLE JOIN

RE-ENABLE (using “SET”) the access method you turned off above.

Create a B-tree index on 'studentfacultyratio' of the rankings table.

Analyze the query plan for the following query that finds the average salary at schools who have a student to faculty ratio < 3.

SELECT R.name, F.avesalary 
FROM rankings R, financials F
WHERE R.id = F.id AND R.studentfacultyratio < 3; 

Answer the following questions:

A. What is the estimated cost of this plan?

    

    

B. What kind of join is used by the plan?

C. Disable the join type used in the above plan and re-optimize the query.  What type of join is used now, and what is the total estimated cost of the query?

 

d. What relations are sorted in this plan, and why?

6.      THREE-WAY JOIN

RE-ENABLE (using “SET”) the join method you turned off above.

Answer the following questions referring to the query below: 

SELECT S.name, R.name, F.avesalary

FROM students S, rankings R, financials F

WHERE S.school = R.id and R.id = F.id;

A. Describe the best plan estimated by the optimizer. List the joins and access methods it uses, and the order in which the relations are joined.

 

 

 

B. What is the Relational Algrebra expression for the above join order?

C. Modify the query by adding a condition R.studentfacultyratio < 10. What are the differences between this plan and the one above? Why is this new join ordering better for the extended query than the ordering obtained in part A?

 

 

 

7.      PLAYING WITH SQL 

Answer the following questions about the database (by writing queries!): 

A. What is the name of the public school (public = 1) with the highest average salary?  (hint: while one way to get close to this is simply to list all schools and the average salary for them sorted by average salary, you may also want to try writing a variant that only produces a single result row – it’s a bit ugly).

B. Find the public school (public = 1) with the largest difference between instate tuition and out of state tuition that has at least one student attending.

C. Show a query to find out some other interesting fact in the database and tell us what the answer is (or at least summarize it).

• Understanding different buffer management strategies
• Examining, understanding and modifying existing code
• Testing your code in a real system

Please skim through this document to the end before getting to work!

Partners

There are two parts to this assignment, the first of which is to be done individually and the second in teams of two people. We will post the deadlines for when and how to register your team with the second part of the assignment.

Deadlines

You have to submit this assignment in two main parts:

1. The first part will test your understanding of different buffer replacement strategies. This part must be done individually and is due at Monday, September 15, 11:59PM
   
2. The second phase requires that you and your partner code a buffer replacement policy and create tests code. The due date for the part is Friday, September 26, 11:59PM
   

Tasks and Grade Percentage

• 30% - Written assignment on "Understanding Different Buffer Replacement Strategies"
• 50% - Implementation of alternate buffer management strategies in postgres
• 20% - Performance analysis of different strategies
  

Part 1: Understanding Different Buffer Replacement Strategies. (30%)

The textbook describes LRU, MRU and CLOCK strategies in section 9.4.1. However, you may need to read the entire section (9.4) to get a full image of a buffer manager in the DBMS. A fourth (more recent) strategy is called 2Q, and is used in Postgres v8.0.3. LRU, MRU, and CLOCK strategies work well enough for most systems so we are going to replace 2Q. But first you'll need to exercise your understanding of the LRU, MRU, and CLOCK buffer replacement strategies.

This part of the assignment requires no code. We will give you the number of page slots that the buffer manager must manage and a sequence of data blocks accessed by the different DBMS layers above the buffer manager layer. You will have to track the behavior of the buffer manager (which pages it has to replace, when, etc.) using your, and yours alone, knowledge of the three aforementioned buffer replacement strategies.

Solution format for this step

You must record your answers in three plain text files called strategy.lru, strategy.mru, strategy.clock. These files will contain the buffer/slot state and buffer manager replacement decisions in accordance to the LRU, MRU, and CLOCK policies respectively. The format of each file is as follows:

• Three columns of text, separated by spaces
• One line of text each time a page miss occurs
• Each row lists the time of a page miss, a space, the buffer pool slot (P1, P2, P3, P4), a space and, if an eviction occurs, the page evicted from memory. Ex: If a miss occurs during time 3, causing us to evict page A and ping buffer pool slot 3 then we would write: "T3 P3 A"
• Nothing will be written when there is a hit.
  

Example workload and solution

For example, assume there are four page slots your buffer manager must manage: P1, P2, P3, P4. All four slots are initially empty. When the buffer pool has unused slots (e.g., in the beginning when all four slots are empty), it will put the newly read data in the first unused slot. The blocks to be read from disk are labeled A through F. For simplicity here, we assume that after each access the page is pinned, and then immediately unpinned. (You cannot make this same assumption when writing the actual code. A page may be pinned for any length of time in a DBMS.)

Given this information and the following workload:

the files should be as follows:

Several points deserve elaboration:

• Certain times (e.g., T2) are missing for each strategy. This is due to the different buffer miss patterns exhibited by the given replacement policy.
• The third column will be blank when the buffer miss does not result in an eviction.
• When there are multiple FREE pages available, the page with the lowest id is chosen (e.g. P2 before P3 and P4 when all are free at T3). You should conform to this tie-breaking criteria.
• In this case, for the given number of pages and sequence of block accesses, MRU emerges the winner (least number of misses).

Now we come to the problem that you will have to solve. Suppose the buffer manager has five page slots to manage: P1, P2, P3, P4, P5. All slots are initially empty. Suppose seven disk blocks (A, B, ..., G) are accessed by the layers above the buffer manager layer in the DBMS.

Clock policy elaboration: we make the following assumptions in the clock policy:

• The pointer doesn't move when filling free frame in buffer
• The pointer doesn't move when there's a hit in the buffer
• The pointer advances after replacing a buffer frame

To get your access pattern, login to your cs186 account and type genpattern.rb at the prompt.

Remember that you must use:

• Your cs186 class account to get your access pattern.
  
• An intel machine with ruby 1.8.6 (icluster.eecs is an example) This is due to the fact we want you to have the same pseudo-random sequence, seeded with you user id, that we will be using to grade you.
  

Based on this information, you should perform a similar analysis as the one above. We will first have you save your pattern by running the following command

$ genpattern.rb > pattern

You must now generate the three files strategy.lru, strategy.mru, and strategy.clock for this problem. Stick to the specified format (e.g., no extra line at the end of a file), as we will use file comparison scripts to evaluate your answers.

How to Submit

You will need to use the unix submit program to hand in your assignment, it will be turned on by Monday 9/8:

1. Save your four files pattern, strategy.lru, strategy.mru, strategy.clock in a directory called "hw1p1" within your cs186 home directory.
2. cd into hw1p1.
3. Run: submit hw1p1