[ Top page ]

« Timer by JavaScript | Main | A test program for sending/receiving packets with a VLAN tag »

Database

Simulation of RDB queries using Perl

Relational databases are widely used. However, it is not very clear how queries written by SQL are executed by the DBMS. Queries are usually interpreted by DBMS but not compiled into native code. The reason why not compiled into machine code is that it is very important to optimize queries by looking at the properties of tables at run time for the query to be applied. However, in this article, to look at the execution mechanism of queries, I try to simulate them using Perl programs (i.e., “compiled code”).

Contents

Introduction

In a Web site called “SQL Join” (which is described in Japanese), there are tens of examples that contain SQL statements and execution results. I modify these examples and translate them into Perl code. Although the whole program is included in this article, concatenated and immediately executable souce code is available.

Data to Be Used

I use a slightly modified version of the data used in “SQL Join”. Databases are usually stored in disks, but I assume they are in main memory here. It is unlikely to put databases on volatile memory. However, it is possible to put them on main memory if it is non-volatile.

my @Store_Information =
    ({store_name => 'Los Angeles', Sales => 1500, Date => 'Jan-05-1999'},
     {store_name => 'San Diego', Sales => 250, Date => 'Jan-07-1999'},
     {store_name => 'San Francisco', Sales => 300, Date => 'Jan-08-1999'},
     {store_name => 'Los Angeles', Sales => 300, Date => 'Jan-08-1999'},
     {store_name => 'Boston', Sales => 700, Date => 'Jan-08-1999'});

my @Geography =
    ({region_name => 'East', store_name => 'Boston'},
     {region_name => 'East', store_name => 'New York'},
     {region_name => 'West', store_name => 'Los Angeles'},
     {region_name => 'West', store_name => 'San Diego'});

my @Internet_Sales =
    ({Date => 'Jan-07-1999', Sales => 250},
     {Date => 'Jan-10-1999', Sales => 535},
     {Date => 'Jan-11-1999', Sales => 320},
     {Date => 'Jan-12-1999', Sales => 750});

Here, Store_Information table is the record of shop-wise sales. Geography table indicates the relationship between the stores (shops) and the areas that the stores exist. Internet_Sales table is the record of amount of one-day sales on the Internet. Tables are represented by arrays, and each array element, i.e., the database record (tuple) is represented by a hash in Perl.

Simple Query

First, I show a simplest SELECT statement for example. The original SQL query is as follows.

SELECT store_name FROM Store_Information

This query extracts shop names (store_name) from Store_Information table (which is an array of hashes). This query can be translated into the following Perl code.

sub select_store_name() {
    print_result(@Store_Information, ['store_name']);
}

Subroutine select_store_name only gets elements that has 'store_name' as its key from each record in Store_Information table, and prints them. print_result is a general-purpose subroutine that is used in the following examples too, and it extracts and prints the elements that has the specified (one or more) keys.

sub print_result(\@$) {
    my ($result, $keys) = @_;
    foreach my $key (@$keys) {
	print "\t$key";
    }
    print "\n\t----------------\n";

    foreach my $record (@$result) {
	foreach my $key (@$keys) {
	    print "\t$record->{$key}";
	}
	print "\n";
    }
}

By calling subroutine select_store_name(), the following result is obtained.

	store_name
	----------------
	Los Angeles
	San Diego
	San Francisco
	Los Angeles
	Boston

In Store_Information table, there are two (different) stores named “Los Angeles”. So it was displayed twice.

To compare this subroutine with the examples below (for example, “A Query with WHERE clause”), the following form of select_store_name (whose function is the same as above) may be better.

sub select_store_name() {
    my @result = ();
    foreach my $record (@Store_Information) { # FROM Store_Information
	push(@result, $record);
    }

    print_result(@result, ['store_name']); # SELECT store_name
}

However, the newly added loop in this program does not perform any net work (i.e., it only copies the array). So, if the loop is removed, the program becomes the one shown first.

Query with a DISTINCT Operator

In the next example, as same as the above example, the store names are extracted from Store_Information talbe, but duplicated store names are deleted.

SELECT DISTINCT store_name FROM Store_Information

This query can be translated into the following Perl code.

sub select_distinct_store_name() {
    my %Distinct_Store_Information = ();
    foreach my $record (@Store_Information) { # FROM Store_Information
	$Distinct_Store_Information{$record->{store_name}} = $record; # DISTINCT
    }
    my @result = ();
    foreach my $store_name (keys %Distinct_Store_Information) { # DISTINCT
	my $record = $Distinct_Store_Information{$store_name};  # DISTINCT
	push(@result, $record);
    }

    print_result(@result, ['store_name']); # SELECT store_name
}

To remove duplicated store names, a hash table called %Distinct_Store_Information is used. It is easy to implement a hash table in Perl because Perl has so-called hashes. In @result, there are only one “Los Angeles” which was duplicated in array @Store_Information.

By calling subroutine select_store_name(), the following result is obtained.

	store_name
	----------------
	San Francisco
	San Diego
	Los Angeles
	Boston

“Los Angeles” is not duplicated here.

Query with a WHERE Clause

In the next example, store names are extracted from Store_Information table too. However, only the stores whose sales is over 1000 (dollars) are selected.

SELECT store_name
FROM Store_Information
WHERE Sales > 1000

This statement can be translated into the following Perl code.

sub select_store_name_where() {
    my @result = ();
    foreach my $record (@Store_Information) { # FROM Store_Information
	if ($record->{Sales} > 1000) { # WHERE Sales > 1000
	    push(@result, $record);
	}
    }

    print_result(@result, ['store_name']); # SELECT store_name
}

By comparing this subroutine with the select_store_name subroutine with an added loop, we can see the only difference is a conditional statement that corresponds to the WHERE clause.

By calling subroutine select_store_name_where(), the following result is obtained.

	store_name
	----------------
	Los Angeles

Query with a WHERE Clause with AND and OR Operators

An example with a WHERE clause with AND and OR operators is shown here.

SELECT store_name
FROM Store_Information
WHERE Sales > 1000 OR (Sales < 500 AND Sales > 275)

This statement can be translated into the following Perl code.

sub select_store_name_and_or() {
    my @result = ();
    foreach my $record (@Store_Information) { # FROM Store_Information
	if ($record->{Sales} > 1000 ||
	    $record->{Sales} < 500 && $record->{Sales} > 275) {
		# WHERE Sales > 1000 OR (Sales < 500 AND Sales > 275)
	    push(@result, $record);
	}
    }

    print_result(@result, ['store_name']); # SELECT store_name
}

By calling subroutine select_store_name_and_or(), the following result is obtained.

	store_name
	----------------
	Los Angeles
	San Francisco
	Los Angeles

Query with a WHERE Clause with an IN Operator

An example with a WHERE clause with an IN operator is shown here.

SELECT *
FROM Store_Information
WHERE store_name IN ('Los Angeles', 'San Diego')

This statement can be translated into the following Perl code.

sub select_store_name_in() {
    my @result = ();
    foreach my $record (@Store_Information) { # FROM Store_Information
	if (grep ($_ eq $record->{store_name},
		  'Los Angeles', 'San Diego')) {
		# WHERE store_name IN ('Los Angeles', 'San Diego')
	    push(@result, $record);
	}
    }

    print_result(@result, ['store_name', 'Sales', 'Date']); # SELECT *
}

Except that grep function is used for the list search and that program is very similar to the previous one, i.e., select_store_name_and_or().

By calling subroutine select_store_name_in(), the following result is obtained.

	store_name	Sales	Date
	----------------
	Los Angeles	1500	Jan-05-1999
	San Diego	250	Jan-07-1999
	Los Angeles	300	Jan-08-1999

Query with a WHERE Clause with a LIKE Operator

An example with a WHERE clause with a LIKE operator is shown here.

SELECT *
FROM Store_Information
WHERE store_name LIKE '%AN%'

LIKE operator matches a character string to a regular expression. Because pattern matching is a strong part of Perl, it can easily be expressed by Perl.

sub select_store_name_like() {
    my @result = ();
    foreach my $record (@Store_Information) { # FROM Store_Information
	if ($record->{store_name} =~ /.*AN.*/i) { # WHERE store_name LIKE '%AN%'
	    push(@result, $record);
	}
    }

    print_result(@result, ['store_name', 'Sales', 'Date']); # SELECT *
}

By calling subroutine select_store_name_like(), the following result is obtained.

	store_name	Sales	Date
	----------------
	Los Angeles	1500	Jan-05-1999
	San Diego	250	Jan-07-1999
	San Francisco	300	Jan-08-1999
	Los Angeles	300	Jan-08-1999

Query with an ORDER-BY Clause

To sort the result by the decreasing order of sales, an ORDER-BY clause can be used as follows.

SELECT store_name, Sales, Date
FROM Store_Information
ORDER BY Sales

This statement can be translated into the following Perl code.

sub select_store_name_order_by() {
    my @result = ();
    @result = sort {$b->{Sales} <=> $a->{Sales}} @Store_Information; # ORDER BY Sales

    print_result(@result, ['store_name', 'Sales', 'Date']);
    # SELECT store_name, Sales, Date
}

That means, sort function can be used before displaying the result.

By calling subroutine select_store_name_order_by(), the following result is obtained.

	store_name	Sales	Date
	----------------
	Los Angeles	1500	Jan-05-1999
	Boston	700	Jan-08-1999
	San Francisco	300	Jan-08-1999
	Los Angeles	300	Jan-08-1999
	San Diego	250	Jan-07-1999

Query with an Aggregation Using SUM Function

The examples above do not contain computation using multiple records. The next example use SUM function to compute the sum of sales.

SELECT SUM(Sales) FROM Store_Information

This statement can be translated into the following Perl code.

sub select_sales_sum() {

    my $SUM_Sales = 0;
    foreach my $record (@Store_Information) { # FROM Store_Information
	$SUM_Sales += $record->{Sales};
    }

    print "\tSUM(Sales)\n";
    print "\t$SUM_Sales\n";
}

By calling subroutine select_sales_sum(), the following result is obtained.

	SUM(Sales)
	3050

Query with an Aggregation Using COUNT and AVG Functions

The following example is similar to the previous example using SUM function. This statement counts the number of records using COUNT function, and calculates the average (using AVG function).

SELECT COUNT(store_name), AVG(Sales)
FROM Store_Information
WHERE store_name is not NULL

This statement can be translated into the following Perl code.

sub select_store_name_count() {
    my $COUNT = 0;
    my $SUM_Sales = 0;
    foreach my $record (@Store_Information) { # FROM Store_Information
	if ($record->{store_name}) { # WHERE store_name is not NULL
	    $COUNT++; # COUNT(store_name)
	    $SUM_Sales += $record->{Sales};
	}
    }

    print "\tCOUNT(store_name)\tAVG(Sales)\n";
    print "\t$COUNT\t", $SUM_Sales / $COUNT, "\n";
}

This subroutine calculates the same intermediate value as SUM function, and it finally gets the average by dividing the intermediate value by the number of records.

By calling subroutine select_store_name_count(), the following result is obtained.

	COUNT(store_name)	AVG(Sales)
	5	610

Query with a Combination of COUNT Function and DISTINCT Operator

The next example combines use of a COUNT function and a DISTINCT operator.

SELECT COUNT(DISTINCT store_name)
FROM Store_Information

This statement can be translated into the following Perl code.

sub select_store_name_count_distinct() {
    my %Distinct_Store_Information = (); # DISTINCT
    foreach my $record (@Store_Information) { # FROM Store_Information
	$Distinct_Store_Information{$record->{store_name}} = $record; # DISTINCT
    }
    my $COUNT_store_name = 0;
    foreach my $store_name (keys %Distinct_Store_Information) { # DISTINCT
	$COUNT_store_name++; # COUNT(DISTINCT store_name)
    }

    print "COUNT(DISTINCT store_name)\n";
    print $COUNT_store_name, "\n";
}

By calling subroutine select_store_name_count_distinct(), the following result is obtained.

COUNT(DISTINCT store_name)
4

Because there are two stores named “Los Angeles”, this subroutine counts them only once.

Query with a GROUP-BY Clause

The following statement groups stores by their names, and shows the sales of each group.

SELECT store_name, SUM(Sales)
FROM Store_Information
GROUP BY store_name

This statement can be translated into the following Perl code.

sub select_store_name_group_by() {
    my %Grouped_Store_Information = ();
    foreach my $record (@Store_Information) { # FROM Store_Information
	if (!$Grouped_Store_Information{$record->{store_name}}) { # GROUP BY store_name
	    $Grouped_Store_Information{$record->{store_name}} =
	    {store_name => $record->{store_name},
	     SUM_Sales => $record->{Sales}};
	} else {
	    $Grouped_Store_Information{$record->{store_name}}->{SUM_Sales} +=
		$record->{Sales};
	}
    }
    my @result = ();
    foreach my $store_name (keys %Grouped_Store_Information) {
	push(@result, $Grouped_Store_Information{$store_name});
    }

    print "store_name SUM(Sales)\n";
    print_result(@result, ['store_name', 'SUM_Sales']); # SELECT store_name, SUM(Sales)
}

The first loop contains a condition statement. A new record is created in the then-part of the condition statement. This is the record for holding the intermediate and final values for the calculation of SUM. In the previous examples, there was no need to hold such an intermediate value. So only pointers to preexisting records are used and there was no need to generate new records (hashes). The else-part of the conditional statement in the present example only updates the intermediate value of SUM.

By calling subroutine select_store_name_group_by(), the following result is obtained.

	store_name	SUM_Sales
	----------------
	San Francisco	300
	San Diego	250
	Los Angeles	1800
	Boston	700

The sales of two stores named “Los Angeles” are added, but the other values are the same as those in Store_Information table.

Query with GROUP-BY and HAVING Clauses

To express a condition on the result of “GROUP BY”, “HAVING” is used in this example.

SELECT store_name, SUM(sales)
FROM Store_Information
GROUP BY store_name
HAVING SUM(sales) > 1500

This statement shows the groups whose sum of sales is greater than 1500.

This statement can be translated into the following Perl code.

sub select_store_name_having() {
    my %Grouped_Store_Information = ();
    foreach my $record (@Store_Information) { # FROM Store_Information
	if (!$Grouped_Store_Information{$record->{store_name}}) { # GROUP BY store_name
	    $Grouped_Store_Information{$record->{store_name}} =
	    {store_name => $record->{store_name},
	     SUM_Sales => $record->{Sales}};
	} else {
	    $Grouped_Store_Information{$record->{store_name}}->{SUM_Sales} +=
		$record->{Sales};
	}
    }
    my @result = ();
    foreach my $store_name (keys %Grouped_Store_Information) {
	my $record = $Grouped_Store_Information{$store_name};
	if ($record->{SUM_Sales} > 1500) { # HAVING SUM(sales) > 1500
	    push(@result, $record);
	}
    }

    print "store_name SUM(Sales)\n";
    print_result(@result, ['store_name', 'SUM_Sales']); # SELECT store_name, SUM(sales)
}

The condition in the WHERE clause in handled in the first loop, but the condition in the HAVING clause is handled in the second loop.

By calling subroutine select_store_name_having(), the following result is obtained.

	store_name	SUM_Sales
	----------------
	Los Angeles	1800

Query with a JOIN Operator

JOIN operation is one of the most important operations for relational databases.

SELECT Geography.region_name, SUM(Store_Information.Sales)
FROM Geography, Store_Information
WHERE Geography.store_name = Store_Information.store_name
GROUP BY Geography.region_name

In this example, both tables contain store names. They are used to join these tables. This means, the sales for each region are calculated in this example.

There are many methods to execute JOIN. Methods of optimization were the most important themes of database researches around 1980s. However, only one method called "hash join" is used here. This is a method of optimizing join operations using hashing.

sub select_store_geo_join() {
    my %Distinct_Geography = ();
    foreach my $record (@Geography) { # FROM Geography
	push(@{$Distinct_Geography{$record->{store_name}}}, $record); # hash chain
    }
    my %Grouped = ();
    foreach my $record_S (@Store_Information) { # FROM Store_Information
	foreach my $record_G (@{$Distinct_Geography{$record_S->{store_name}}}) {
	    if (!$Grouped{$record_G->{region_name}}) { # GROUP BY region_name
		$Grouped{$record_G->{region_name}} =
		{region_name => $record_G->{region_name},
		 Sales => $record_S->{Sales}};
	    } else {
		$Grouped{$record_G->{region_name}}->{Sales} +=
		    $record_S->{Sales};
	    }
	}
    }
    my @result = ();
    foreach my $region_name (keys %Grouped) {
	push(@result, $Grouped{$region_name});
    }

    print_result(@result, ['region_name', 'Sales']); # SELECT store_name
}

A hash table is created in the first loop. Hash tables are also used in the examples of “DISTINCT” and “GROUP BY”. However, in these examples, each hash-table entry contains only one result value (such as the value of SUM). In contrast, in this example, each entry may have multiple records (as an array), so the program is more complicated. However, the algorithm of "hash join" can be expressed by such a short program using Perl because of its power.

The second loop is nested, but the number of repetition of the inner loop is usually small. The inner loop contains a conditional statement. The then-part creates a new record that is a joined record of two tables. The else-part of the conditional statement only updates the records.

By calling subroutine select_store_geo_join(), the following result is obtained.

	region_name	Sales
	----------------
	West	2050
	East	700

Query with Nested SELECTs

The following query contains a subquery, i.e., SELECTs are nested in this example.

SELECT SUM(Sales) FROM Store_Information
WHERE Store_name IN
(SELECT store_name FROM Geography
 WHERE region_name = 'West')

This statement sums up the stores in the west region. This statement can be translated into the following Perl code.

sub select_store_subquery() {
    my @work = ();
    foreach my $record (@Geography) { # FROM Geography
	if ($record->{region_name} eq 'West') { # WHERE region_name = 'West')
	    push(@work, $record->{store_name}); # SELECT store_name
	}
    }
    my $SUM_Sales = 0;
    foreach my $record (@Store_Information) { # FROM Store_Information
	if (grep ($_ eq $record->{store_name}, @work)) { # WHERE store_name IN ...
	    $SUM_Sales += $record->{Sales};
	}
    }

    print "SUM_Sales\n";
    print $SUM_Sales, "\n";
}

The first loop corresponds to the inner SELECT, and the second loop corresponds to the outer SELECT.

By calling subroutine select_store_subquery(), the following result is obtained.

SUM_Sales
2050

Query with a UNION Operator

This query computes the union of two queries.

SELECT Date FROM Store_Information
UNION
SELECT Date FROM Internet_Sales

This statement can be translated into the following Perl code.

sub select_date_union() {
    my %work = ();
    foreach my $record (@Store_Information) { # FROM Store_Information
	$work{$record->{Date}} = 1; # SELECT DISTINCT Date
    }
    foreach my $record (@Internet_Sales) {    # FROM Internet_Sales
	$work{$record->{Date}} = 1; # UNION SELECT DISTINCT Date
    }
    my @result = ();
    foreach my $Date (keys %work) {
	push(@result, {Date => $Date});
    }

    print_result(@result, ['Date']);
}

A UNION operator must remove duplicated values, so a hash table is used for this purpose. The hash table contains null ('' or 0) or 1. Only the elements that contains 1 belongs to the result of UNION.

By calling subroutine select_date_union(), the following result is obtained.

	Date
	----------------
	Jan-07-1999
	Jan-05-1999
	Jan-11-1999
	Jan-12-1999
	Jan-10-1999
	Jan-08-1999

The dates are not duplicated, but the order of them is nondeterministic because ordering is not specified.

Query with a UNION ALL Operator

This example is close to the previous one. It uses “UNION ALL”, instead of “UNION”. This means, this query does not remove duplicates.

SELECT Date FROM Store_Information
UNION ALL
SELECT Date FROM Internet_Sales

This statement can be translated into the following Perl code.

sub select_date_union_all() {
    my @work = ();
    foreach my $record (@Store_Information) { # FROM Store_Information
	push(@work, {Date => $record->{Date}}); # SELECT Date
    }
    foreach my $record (@Internet_Sales) {    # FROM Internet_Sales
	push(@work, {Date => $record->{Date}}); # UNION ALL SELECT Date
    }
    my @result = ();
    foreach my $record (@work) {
	push(@result, $record);
    }

    print_result(@result, ['Date']);
}

Because there is no need to remove duplicated values for UNION ALL operator, it is easier to implement than for UNION operator.

By calling subroutine select_date_union_all(), the following result is obtained.

	Date
	----------------
	Jan-05-1999
	Jan-07-1999
	Jan-08-1999
	Jan-08-1999
	Jan-08-1999
	Jan-07-1999
	Jan-10-1999
	Jan-11-1999
	Jan-12-1999

Query with an INTERSECT Operator

This example contains an INTERSECT (intersection) operator instead of a UNION operator.

SELECT Date FROM Store_Information
INTERSECT
SELECT Date FROM Internet_Sales

This statement can be translated into the following Perl code.

sub select_date_intersect() {
    my %work = ();
    foreach my $record (@Store_Information) { # FROM Store_Information
	$work{$record->{Date}} = 1;
    }
    foreach my $record (@Internet_Sales) {    # FROM Internet_Sales
	if ($work{$record->{Date}}) {
	    $work{$record->{Date}} = 2;	# INTERSECT
	}
    }
    my @result = ();
    foreach my $Date (keys %work) {
	if ($work{$Date} == 2) {
	    push(@result, {Date => $Date});
	}
    }

    print_result(@result, ['Date']); # SELECT Date
}

INTERSECT operator is slightly more difficult to implement than UNION operator. Only the elements that contain "2" are included in the result of the INTERSECT operator. However, this method cannot be applied to programs that contain more complicated expressions.

By calling subroutine select_date_intersect(), the following result is obtained.

	Date
	----------------
	Jan-07-1999

Query with a MINUS Operator

This query computes the difference of two subquery results.

SELECT Date FROM Store_Information
MINUS
SELECT Date FROM Internet_Sales

This statement can be translated into the following Perl code.

sub select_date_minus() {
    my %work = ();
    foreach my $record (@Store_Information) { # FROM Store_Information
	$work{$record->{Date}} = {Date => $record->{Date}};
    }
    foreach my $record (@Internet_Sales) {    # FROM Internet_Sales
	if ($work{$record->{Date}}) {
	    $work{$record->{Date}} = ''; # MINUS
	    # or, delete $work{$record->{Date}};
	}
    }
    my @result = ();
    foreach my $Date (keys %work) {
	if ($work{$Date}) {
	    push(@result, {Date => $Date});
	}
    }

    print_result(@result, ['Date']); # SELECT Date
}

By calling subroutine select_date_minus(), the following result is obtained.

	Date
	----------------
	Jan-05-1999
	Jan-08-1999
Keywords: Relational Database, SQL, Join

TrackBack

TrackBack URL for this entry:
http://www.kanadas.com/mt/mt-tb.cgi/3439

Post a comment

About

This page contains a single entry from the blog posted on December 29, 2008 6:45 PM.

Many more can be found on the main index page or by looking through the archives.

Creative Commons License
This weblog is licensed under a Creative Commons License.
Powered by
Movable Type 3.36