Consider the database definition below which stores student details as well as details of tests taken but the students.
CREATE TABLE STUDENTS(id INT NOT NULL, name CHAR(40) NOT NULL, email CHAR(80) NOT NULL);
CREATE TABLE SUBJECTS(id INT NOT NULL, name CHAR(40) NOT NULL, description TEXT NOT NULL);
CREATE TABLE TESTS(id INT NOT NULL, subject_id INT NOT NULL, name CHAR(40) NOT NULL, date TIMESTAMP NOT NULL, max_marks INT NOT NULL);
The table TEST_RESULTS below is the table that will contain the most number of rows (out of all tables in the database).
CREATE TABLE TEST_RESULTS(id INT NOT NULL, student_id INT NOT NULL, test_id INT NOT NULL, marks INT NOT NULL);
The query below computes the average marks obtained in tests and orders the results in non-increasing order of the average marks.
SELECT SUBJECTS.name AS subject_name, TESTS.name AS test_name, SUM(TEST_RESULTS.marks) / COUNT(*) AS average_marks FROM SUBJECTS, TESTS, TEST_RESULTS WHERE SUBJECTS.id = TESTS.subject_id AND TESTS.id = TEST_RESULTS.test_id GROUP BY SUBJECTS.name, TESTS.name ORDER BY average_marks DESC;
How does tddb distribute this query?
To distribute this query, each machine in the distributed system is setup so that the relation TEST_RESULTS is distributed across all the participating machines and the rest of the relations are replicated on all the participating machines.
Each of the individual nodes is fed the query and they all respond with a set of tuples which are only slightly different from the format of the final set of tuples that are to be projected.
We notice that the final result looks like this:
(subject name, test name, average marks)
where as what each individual node returns is this:
(subject name, test name, SUM(TEST_RESULTS.marks), COUNT(*))
What tddb does is that it figures out the individual basic columns from which the final projection list is computed. Individual nodes will return only these basic columns. In this example, they happen to be the columns that return the sum of all marks in a test and the number of rows for that test on that node. Combining these 2 results in the computation of the average marks for that test.
This trick works ONLY for associative operations such as MIN, MAX, SUM and COUNT. It will not work for SQLs AVG function. It is hence advisable to compute the average manually as shown above to aid the distributed execution of the query.
This enables the master node to collect output from each of the individual nodes and aggregate them into the final output. This is very similar to Hadoop's Combiners. The final reduction step occurs at the master node that combines results from all the nodes, generates the final set of tuples and performs ordering of the result set (if needed).