CSCD43 DATABASE SYSTEM TECHNOLOGY
Assignment 1
Assigned January 17
Due Monday February 4
Weight: 10% of your final grade
Buffer Management
1 Introduction
In this assignment, you will modify the PostgreSQL 7.4.13 Buffer Manager. Before starting this assignment,
you should have already downloaded, compiled and installed PostgreSQL 7.4.13. The goal of this assignment
is to understand and evaluate various memory management strategies in a database system. The actual
coding for this assignment is minimal, but you will be modifying existing source code in a very large codebase;
therefore, it may be a bit challenging.
Start early!
2 Experimental setup
2.1 Data Generation and loading:
The table we will be working with can be created using the following SQL statement:
CREATE TABLE Data (
ID INTEGER PRIMARY KEY,
A INTEGER,
B INTEGER,
C INTEGER);
1. You have to write a script to generate a 5000-line file from which the table will be uploaded. In
addition, you will have to make sure that:
• the ID column is unique, and
• the numbers inserted in the other columns are uniformly-random generated between 1-100.
Each line in this file should be of the form:
, , ,
An example of such file is the following:
1,56,89,23
2,45,78,45
...
2. Upload this file into the table Data using the COPY command in psql. Your data should now be ready.
Suggestion: you can check the correctness of your data using some queries.
CSCD43 DATABASE SYSTEM TECHNOLOGY
Assignment 1
2.2 Queries
1. Write 10 queries of the form:
SELECT COUNT(*)
FROM Data
WHERE ;
An example of such a query is below:
SELECT COUNT(*)
FROM Data
WHERE A > 20 AND B < 40;
2. Store these 10 queries in a file ScanQueries.sql, as follows:
• each query is stored in a separate line, and
• there is a blank line at the end of the file.
These queries will be executed with sequential scans.
3. Write 10 queries of the form:
SELECT COUNT(*)
FROM Data
WHERE ;
An example of such a query is below:
SELECT COUNT(*)
FROM Data
WHERE ID > 7 AND ID < 20;
4. Store these 10 queries in a file IndexScanQueries.sql, as follows:
• each query is stored in a separate line, and
• there is a blank line at the end of the file.
These queries should probably be executed with index scans.
5. Before proceeding further,
• try executing these queries in PostgreSQL , and
• check, using the EXPLAIN command in psql, that they are indeed executed using Sequential Scans
or Index Scans, as specified.
2
CSCD43 DATABASE SYSTEM TECHNOLOGY
Assignment 1
2.3 Evaluation of the queries
By now, you should have the data and the queries to run on it.
To run the queries on a backend, and extract the buffer hit rate, you should run PostgreSQL in a
standalone backend mode, using the command postgres as follows. Note that this is the easiest way to run
a set of queries and extract “interesting” information from the backend.
cat | postgres -B -D -d -s
The output of the postgres command contains lots of information. Of interest to you is the buffer hit rate
for each query. In order to make sure you
• understand its output, and
• can extract appropriate information,
we recommend you to run different queries.
The flags on the postgres command are explained below:
• The -B flag specifies the size of the buffer cache in blocks.
• The -D flag refers to the data directory.
• The -d flag sets the debug level. This flag will force the backend to print out useful statistics.
– For this assignment, setting the debug-level to 1 or 2 should be enough.
• The -s flag in conjunction with the debug flag results in buffer hit rates being printed in the output.
For more information on postgres, you can use man postgres.
Note: in the evaluation section, you will have to vary the number of buffers, and to printe the hit rates for
different configurations.
An example of the command above is as follows:
cat ScanQueries.sql | postgres -B 20 -D ~/data/ -d 1 -s mydatabase
Now, you may hack!
3
CSCD43 DATABASE SYSTEM TECHNOLOGY
Assignment 1
3 Implementation
The version of PostgreSQL you are using for this assignment uses the LRU buffer replacement policy. For this
assignment you are required to implement the LFU (Least Frequently Used) and MRU (Most Recently Used)
replacement policies. Consult your favourite textbook to find out the details of these policies.
You can find the buffer manager code in the directories
src/backend/storage/buffer
src/include/storage/
The files which will most likely need the most are:
• freelist.c
– it manages pages which are not pinned in memory and are eligible for replacement.
• bufmgr.c
– it defines the interface used by the rest of PostgreSQL to access the memory buffer.
• buf_init.c
– it handles initializations of the buffer manager data structures.
• buf_internals.h
– it defines the data structures used by the rest of the buffer manager.
You should be able to complete the entire assignment by modifying just these files.
We recommend that, before you start modifying the files to implement the new replacement policies,
you save a copy of these files elsewhere. Note that you will need to keep separate copies of the 4 files for
implementing the LFU and MRU policies.
Each time you make changes to the files, you have to compile and install PostgreSQL again. This can be
done using the following commands:
$gmake clean
$gmake uninstall
$gmake
$gmake install
If you haven’t modified any header files since you last compiled the code, you may avoid the gmake clean
command. Also, you do not need to create the database again each time you recompile and reinstall
PostgreSQL .
4
CSCD43 DATABASE SYSTEM TECHNOLOGY
Assignment 1
3.1 Tips on how to deal with such code
• Do not delete any old LRU code in the files. It is much easier to just comment it out and add a marker
(for instance, BEGIN OLDCODE) at the beginning of the commented section.
Similarly, you may want to clearly delimit the new code you write in the file, to keep track of your
changes. Such marking should help even if you are using a CVS.
• You may have to declare global variables to make your code work. Although this isn not the best
programming practice, it makes life much simpler with such legacy code. Be sure to use the C modifier
static to limit the scope of your global variables to a single C file.
• To debug your code, you could either use
* fprint(stderr,...), or
* gdb.
• You have to comment your code. In the event that your assignment is not completely correct,
commented code is the only way we can understand your code, and give you partial credit. Also, your
own code should be clearly demaracted with BEGIN NEWCODE and END NEWCODE comments.
3.1.1 Tips on using gdb
To use gdb, you have to configure and compile PostgreSQL with debugging enabled, as below:
./configure --prefix=PREFIX --enable-debug --enable-depend
This creates much bigger compiled binaries, though. For this assignment, you will probably not need to
resort to gdb.
If you do decide to use gdb, you should run it as below:
$gdb postgres
(gdb) run -B 20 -D ~/data/ -d 1 -s mydatabase < ScanQueries.sql
5
CSCD43 DATABASE SYSTEM TECHNOLOGY
Assignment 1
4 Evaluation of the performance
Finally, you will now compare the performance of the LRU, LFU, and MRU replacement policies. To accomplish
this, you will have to run the queries (from your query files) with varying buffer cache sizes (as discussed in
Section 2.3). The PostgreSQL binary should report buffer hit rates for each query in the query files. For
each run, you should take the average over all queries in a file.
1. You should produce 2 graphs, as described below:
• The first graph contains the buffer hit rates for all three algorithms, applied to the queries on
ScanQueries.sql, using varying buffer sizes.
• The second graph contains the buffer hit rates for all three algorithms, applied to the queries on
IndexScanQueries.sql, using varying buffer sizes.
Remember to clearly mark the axes on the graphs and state clearly which parameters are being kept
constant and what their values are. Submissions with graphs which are not clear and precise will be
penalized
2. Analyze/Interpret any “interesting” trends that you notice in the behaviour of the LRU, LFU, and
MRU replacement policies. You have to explain when and why one policy is better than the other. Note
that any trend you claim should be clearly visible in the graphs. If you notice anything else interesting
in your results (say the behaviour over some type of queries), then add this to your report. Please be
concise!
3. Try to estimate the size of your table Data in number of blocks, based on the buffer cache hit rates,
with increasing size of the table. (This should be easy!)
6
CSCD43 DATABASE SYSTEM TECHNOLOGY
Assignment 1
5 Submission instructions
1. You have to submit electronically the following files:
• Your report(pdf ONLY):
– it should contain the graphs, your interpretation of the results, and any other interesting
trends that you observed. No additional documentation is necessary.
• A README file:
– it should contain your name, student number, what works and what doesn’t work in your
assignment.
• ScanQueries.sql
• IndexScanQueries.sql
• The 4 C code files for LFU. Rename the files
freelist_lfu.c, bufmgr_lfu.c, buf_init_lfu.c, buf_internals_lfu.h.
You will have to submit all 4 files even if you didn’t have to modify all of them.
• The 4 C code files for MRU. Rename the files
freelist_mru.c, bufmgr_mru.c, buf_init_mru.c, buf_internals_mru.h.
As with LFU, you will have to submit all 4 files even if you didn’t have to modify all of them.
• If you had to modify any other files, please include them as well. Note that the assignment can
and should be solved by modifying just the 4 files mentioned.
Good luck!
7