\documentclass[a4paper,11pt]{article}
\usepackage[ansinew]{inputenc}
\usepackage[T1]{fontenc}
%\usepackage{ae}
\usepackage[english]{babel}
\usepackage{thumbpdf}
\usepackage{amstext}
\usepackage{amssymb}
\usepackage{amsmath}
\usepackage{enumerate}
\usepackage{graphicx}
\usepackage{multirow}
\usepackage[cm,empty]{fullpage}
\usepackage{color}
\usepackage[pdftex,
            pdfpagelabels,
            colorlinks=true,           % Links nicht farbig umrahmen, sondern als farbigen Text
%            urlcolor=colorBlue,        % Farbe für externe Verweise, \href{...}{...}
%            filecolor=colorGreen,      % Farbe für lokale Verweise, \href{...}{...}
%            linkcolor=colorRed,        % Farbe für interne Verweise, \ref{...} und \pageref{...}
%            pdftitle={(Titel)},
%            pdfauthor={(Autor)},
%            pdfsubject={(Thema)},
%            pdfkeywords={(Schlagwörter)},
            pdfpagemode=None,          % Navigationsleiste beim Start ausblenden
            % pdfpagemode=UseThumbs,     % Thumbnails beim Start anzeigen
            % pdfpagemode=UseOutlines,   % Lesezeichen beim Start anzeigen
            % pdfpagemode=FullScreen,    % im Vollbildmodus starten
            % pdfstartpage=2,            % spezielle Startseite festlegen
            bookmarks,
            % bookmarksopen,             % alle Lesezeichen aufklappen
            % bookmarksopenlevel=2,      % Tiefe, bis zu welcher die Lesezeichen aufgeklappt werden sollen
            bookmarksnumbered,         % Lesezeichen nummerieren
            pdfstartview=FitH,         % Seite auf voller Breite anzeigen
            pagebackref
           ]{hyperref}
%\definecolor{colorRed}{rgb}{0.00,0.00,0.00}
%\definecolor{colorGreen}{rgb}{0.00,0.00,0.00}
%\definecolor{colorBlue}{rgb}{0.00,0.00,0.00}

\title{Database Systems: Semester project}
\author{
	Group "We Don't Like Mondays" (pB+ tree in C/C++) \\
	Daniel Fischer, Jan Hendrik Dithmar, Eric Falk
}
\date{}

\begin{document}
\maketitle

\subsection*{Preface}
We started with the idea of implementing a CSB+ tree in Java. Despite some helpful hints from
Mr. Dittrich we unfortunately failed in doing this. A potential reason was Java not being
perfectly suited for implementing a highly memory/cache optimized data structure. But in the
end we simply failed to track down one (or even more, we don't know) nasty bugs. Therefore
we decided to switch to C/C++. Due to the near deadline we decided not to implement a CSB+
tree but a pB+ tree instead (which appeared to be an easier to implement approach).

\subsection*{Results}
In order to improve the cache effectiveness we used much larger nodes than typical. We
experimented with linear search vs. binary search within the keys of a node. We originally
planned to try code expansion for the binary search as well, but we did not manage to
finish that before the deadline. Furthermore we experimented with different ways to prefetch
data into the processor cache in order to improve the binary search performance. All our
prefetching efforts performed equally well - unfortunately no performance improvement.

\noindent We tried numerous combinations of node size, search method (linear search vs. binary search)
and prefetching on/off with our implementation. The following table shows our findings:

\begin{center}
	\begin{tabular}{l|c|c|c|c|c|c|c}
		\multirow{3}{*}{search method} &
		\multirow{3}{*}{prefetch?} &
		\multicolumn{6}{c}{node size, keys per node} \\
		            &     & 128b  & 256b & 512b  & 1kb   & 2kb   & 4kb \\
		            &     & 14    & 30   & 62    & 126   & 254   & 510 \\ \hline \hline
		linear      & no  & 15,7s & 13,3 & 11,6s & 12,0s & 13,3s & 17,3s \\ \hline
		linear      & yes & 15,6s & 13,3 & 11,7s & 12,0s & 13,4s & 17,3s \\ \hline
		bin. search & no  & 20,6s & 15,0 & 12,6s & 12,1s & 11,9s & 12,8s \\ \hline
		bin. search & yes & 20,6s & 16,0 & 12,5s & 12,3s & 12,0s & 13,0s
	\end{tabular}
\end{center}

\noindent We can clearly see that the combination with the best performance is the one with a node
size of 512 bytes and linear search (at least for the given workload). This is pretty
surprising, we assumed binary search within the keys to perform much better. Furthermore
we can see that prefetching does not help at all. Again, this was quite surprising to us
since we expected a performance gain of about factor 2. There are two possible reasons: either
our prefetching implementation is simply "crap" or the processor itself already does quite
good prefetching s.t. our prefetching is rendered useless.

\subsection*{Build/usage instructions}
The program is built using "\texttt{make FINAL=1}". The argument "\texttt{FINAL=1}" enables
optimized compiling without asserts and debug symbols. There are two binaries: "\texttt{test}"
and "\texttt{work}". The first one is some kind of a simple unit test in order to assure the
correctness of the implementation. The second one is the actual workload generator. Both
binaries do not take any command line arguments, they are run by typing "\texttt{./test}"
or "\texttt{./work}" respectively. Customization of the data structure is done in the
header file "\texttt{settings.hpp}" using preprocessor symbols (see the file for more info).


%Core ideas
%----------
%As a core idea, the program uses a prefetching B+-tree (pB+-tree) written in C++. This is done, because
%prefetching is pretty difficult to realize in Java.
%
%We created the code as follows:
%* The core data structure of the B+-tree was simply ported to C++.
%* The intermediate nodes are realized in "dir.hpp".
%* dir.hpp contains an array of possible child nodes (children[]) and an array containing all the keys that are stored
%  in the current node (keys[]).
%* The leaf nodes are realized in "leaf.hpp".
%* The leaf nodes are connected via the pointer "nextLeaf" which points to the next leaf node in the tree.
%  This makes it possible to do the prefetching step on the leaf level, since all the nodes are connected
%  which allows to jump easily to the next node.
%* insert
%  Start with the root node. If this is a leaf node, the algorithm checks whether there's space in this node. This is the
%  case for n < LEAF_KEYS, where LEAF_KEYS is a preprocessor directive which provides the number of slots in a leaf. If
%  n >= LEAF_KEYS, the root node is split according the splitting in a B+-tree. A recursive split can also occur which means
%  that also the parent node (and maybe its parent node) has to be split. This is where DIR_KEYS comes into play which is a
%  preprocessor directive telling the program how much slots an intermediate node can carry.
%  Otherwise, it selects the next child node by comparing the pivot elements of the current node with the key
%  that is requested. This is done until a leaf node is reached. Again, the algorithm checks whether there's space in this node.
%  If there's space left, do the insert by storing the key in the keys[]-array and the value in the values[]-array.
%  If n >= LEAF_KEYS, do a split and insert afterwards.
%  In all cases above, n denotes the number of keys contained in the keys[]-array of the current node.
%* remove
%  Start with the root node. If this is a leaf node, the algorithm looks up the key in this node, removes it with its
%  corresponding value and is done.
%  Otherwise, it selects the next child node by comparing the pivot elements of the current node with the key
%  that is requested. This is done until a leaf node is reached. The key is looked up and is deleted together with its
%  corresponding value.
%  This remove is realized by using "lazy deletion" as proposed by J. Rao and K. A. Ross in "Making B+-Trees Cache
%  Conscious in Main Memory".
%* pointQuery
%  Start with the root node. If this is a leaf node, the algorithm looks up the key in this node and is done.
%  Otherwise, it selects the next child node by comparing the pivot elements of the current node with the key
%  that is requested. This is done until a leaf node is reached. The key is looked up and the corresponding
%  value is passed to the IntPushOperator.
%* rangeQuery
%  Instead of using one single key, here one has to handle a key range (lowKey to highKey).
%  The tree is traversed exactly as it would have been travesed in pointQuery using lowKey. After having reached
%  the leaf node, highKey comes into play. Now the leaves are scanned sequentially until highKey is reached or
%  no other leaf node is there (nextLeaf == NULL). All the values of the searched key are passed to the IntPushOperator.
%* size
%  Access each node by traversing the tree until a leaf is reached. For each node on this path, count the number of keys
%  in the keys[]-array. This number is stored in the variable n. Next, go up again until the node that has child nodes that
%  are not visited yet and go down the tree again until a leaf is reached. Repeat, until all nodes of the tree are processed.
%
%pbptree.hpp:
%All the methods (insert, remove, ...) delegate the function call to the root-node (either a leaf or an intermediate node).
%The corresponding class handles these request as described above.
%
%
%
%Major Modifications to the B+ tree
%----------------------------------
%Due to the prefetching, the code was ported to C++ which can be seen as one "modification".
%
%Further modifications:
%* The code uses the B+-tree as a basis and does prefetching by using the code specified in "utils.hpp".
%
\end{document}



