Functional dependencies have been used in query optimisation for decades. Moreover, if two domains have a natural ordering of their elements, a functional dependency of them can potentially preserve these orderings, i.e. be a monotonic function. This monotonicity can be exploited by query optimizers. Recently, such monotonic functional dependencies have been termed order dependencies. In this paper we propose a query rewriting method based on order dependencies on primary keys. If an attribute used in the WHERE clause has an order dependency on the primary key, such a selection can be replaced by the corresponding condition on the primary key. We have implemented this optimisation method in the integration framework called the cuboid. It automates the integration of disparate databases according to the CQS model. Cuboids facilitate injecting dependencies and utilizing them in query optimization.
Optimisation methods that exploit functional dependencies have already been
know for decades. Most of these methods base on the injectivity of the
dependency function or its lack. Other properties of this functions are disused.
However, if the domain of such a function is ordered and the function itself can
preserve this order (i.e. be monotonic). This possibility have been discovered by
Jarek Gryz [
Optimisation methods invented by Jarek Gryz and his team are implemented
inside IBM DB2 in one of its experimental branches. It allows hoping that soon
these methods will be available to the user community. However, users of other
DBMSs cannot access them. Therefore, in this paper we struggle to implement
similar optimisation mechanisms outside of a specific database system. Our
experience [
The paper is organized as follows. Section section 2 presents a motivating example that shows optimisation potential values vested in order dependencies. Section section 3 describes the proposed query rewriting algorithm and justifies its semantic correctness. Section section 4 reminds the properties of the cuboid and portrays its potential usage to inject optimisations routines. Section section 5 shows experimental evaluation of the proposed optimisation method. Section section 6 concludes.
We would like to thank Jarek Gryz for his inspiring keynote talk on Order Dependencies at the conference BDAS 2014 in Ustroń.
The contribution of this paper consists of (1) a query rewriting algorithm that employs order dependencies and (2) an idea to use the cuboid as a layer to inject optimisation algorithms and (3) its positive verification. Assume a simple data warehouse of the schema presented on Figure fig. 1. Consider the query for the sales in a selected period show on Listing 1.1. If the column date has no index, this query will require a full scan of the fact table.
Listing 1.1. A query for sales in the indicated period SELECT cname , sum( a g g r v ) , SUM( a g g r q )
FROM f a c t s JOIN c u s t o m e r s USING ( c i d ) WHERE date between ’ 2008 12 13 ’ AND ’ 2008 12 15 ’ GROUP BY c i d , cname
The column f id of the table facts is its primary key. Therefore, all other columns of this tables are functionally dependent on it. The column date is this a function d : INT 7! DATES . The implementation of such an artificial key is usually based on a sequence generator. Moreover, it is easy to assure that facts on sales from a particular day are recorded after all sales from the previous day. Therefore, we can assume that that d : INT 7! DATES is non-decreasing. If we assume that: xmin = minfx; d(x) = ’2008-12-13’g xmax = max fx; d(x) = ’2008-12-15’g the query from Listing listing 1.1 is equivalent to the query shown on Listing listing 1.2. We have rewritten the condition of the WHERE clause.
Listing 1.2. A rewritten query for sales in the indicated period SELECT cname , sum( a g g r v ) , SUM( a g g r q )
FROM f a c t s JOIN c u s t o m e r s USING ( c i d )
GROUP BY c i d , cname
The query of Listing 1.2 will be executed using the range index on the primary key provided it is enough selective. Thus, its running time will be significantly shorter than that of the query from Listing listing 1.1. Moreover, the monotonicity of the function d allows efficient computing of xmin and xmax using the binary search. The experiments we have conducted prove that the overhead caused by this binary search is notably smaller that the time saved by executing the optimized version of the example query. This observations have led us to a rewrite algorithms that implements the idea presented above. 3 3.1
Assume a table T with its primary key P and remaining attributes fA1; : : : ; Ang. Since P is the primary key of T there exists functions f1; : : : ; fn such that each tuple (p; a1; :::; an) of the table T cane be expressed as (p; f1(p); : : : ; fn(p)). The existence of the functions f1; : : : ; fn validate the functional dependencies of the column A1; : : : ; An on the primary key P .
Assume that the domains of the columns P and Ai for a given i 2 f1; 2; : : : ; ng are linearly ordered sets. The functional dependency between P and Ai will be called an order Dependencies, if the function fi is monotonic. Moreover, an important property of fi is whether is increasing, non-decreasing, non-increasing or decreasing.
Such dependencies are initially called monotonic dependencies [
The goal of the algorithm is to replace range conditions on non-indexed columns to corresponding range search on usually indexed primary key. The algorithm is aware of the schema, functional and order dependencies. Its version presented is this paper is able to rewrite SPJ queries (select-project-joins) and grouping-andaggregate queries. The input of the algorithm is a query of the form portrayed on Listing1.3:
Listing 1.3. Initial form of the query to be possibly rewritten SELECT . . .
FROM T JOIN T1 ON (T . f 1 k = T1 . pk )
JOIN T2 ON (T . f 2 k = T2 . pk ) . . . .
We also allow WHERE clauses with equality and inequality. We than convert them to atomic formulae based on BETWEEN using the same value or the data type margin (“infinity”) values. The condition WHERE T.Ai = a is the converted to WHERE T.Ai a BETWEEN a.
In the first step we identify the fact table. We analyze the conditions in the JOIN ... ON clauses. The fact table connects other tables by foreign keys while its primary key is not connected by any other foreign key. In a query of the form shown on Listing 1.3 the fact table is denoted by T . If a query contains a string of dependencies foreign-primary key (e.g. in a snowflake schema), the algorithm will also do. However, if it encounters a cycle, it will stop processing and return the original query.
The second step of the algorithm consists in checking whether (1) the WHERE clause references a column of the identified fact table and (2) this column has an order dependency of the primary key.
In the third step, if the function fi is non-decreasing, we will search for values pmin and pmax such that: pmin = minfp; fi(p) = a1g; pmax = max fp; fi(p) = a2g (1)
Analogously, if this function in non-increasing, the algorithm will compute values pmin and pmax such that: pmin = minfp; fi(p) = a2g; pmax = max fp; fi(p) = a1g (2) Eventually, the algorithm concludes replacing the WHERE with:
WHERE T.P BETWEEN pmin AND pmax
Since the function fi is monotonic, the computation of pmin and pmax can be computed efficiently, e.g. using the binary search. 3.3
The algorithm is implemented in a middleware, i.e. outside of the database system. The computation of pmin and pmax that satisfy conditions (1) and (2) can be done in at least two ways. Both are based on the binary search.
Firstly, we can send a series of queries in the course of the binary search. Its advantage is its inherent simplicity and the lack of any additional database object required. However, it causes numerous communication round trips with the database systems.
Secondly, we can install appropriate stored procedures on the database side. We have decided to implement the binary search exactly this way. When the optimizer on the middleware side is informed on the order dependency between the primary key and the column date, it will generate and install two stored functions. One of them shown on Listing 1.4 finds minimal f id for a given date. An analogous function get max fid by date(DATE) that computes maximal f id is also needed.
Listing 1.4. A function that finds the minimal f id for a given date CREATE OR REPLACE FUNCTION g e t m i n f i n d b y d a t e (
) RETURNS integer AS $$ DECLARE
BEGIN
S=1; WHILE S<Z LOOP
S=S 2 ;
END LOOP; F=S ; WHILE S>1 LOOP
S=S / 2 ; SELECT date into D from f a c t s where f i d = F IF D>= DF THEN
F=F S ; END IF ;
END LOOP;
RETURN F ; END; $$ LANGUAGE p l p g s q l
For the sake of readability we removed error handling code from the function get min... These errors may be caused by gaps in the numbering stored in the column f id.
Using this function (and its twin get max...) the optimizer will first issue queries for corresponding margin values of f id. Then, it will put the collected parameters as values of bind variables in the modified query. 4
Cuboid is a form of central, master metadata repository. It is responsible for storing contributory meta information about constituent data sources. Each integrated data source must first be a subject of a registration procedure (see fig. 2). To register a data source at the Cuboid each data source needs a dedicated mediator to extract from the data source its most informative metadata about schemas, entities and their detailed description. Among those metadata mediator also places adequate queries. Those queries are native queries considering particular data source. Each query is responsible for storing information about particular part of the schema. The decision about which part of the data is going to be covered with the queries’ result sets is for the first time made at mediator configuration, prior to its registration in Cuboid. Thus, during mediator initialization (ie. metadata collecting from data source) mediator is aware of the data sets that needs to be covered with queries. The metadata collected from data source can further be modified during the mediator to Cuboid chatter. At the Cuboid, the metadata, in form of a contributory view provided during mediator registration, is stored and used for building of the global view. The global view is configured and build by designer at the Cubiod site. Prepared global view is then made available to the Adapter instance in form of interoperable Data Access Objects (iDAO). Those objects are designed to cover each data source contact details and its requested metadata with native queries. Each time client requests from Adapter one of global views1, Adapter reaches for requested global view from Cuboid and unmarshalls out of it native queries, together with contact details to the data source of their origin. Using the contact details Adapter sends native queries to original data sources and receives requested result sets. This is happening at the lowest level - ie. JDBC. Now the result sets are being composed together based on global view. When the global view is ready in materialized form, it shall be made available to the client in unified way - ie. in form of REST API.
The entire process involves complex metamodel for collecting and transforming
contributory and global metadata. This information has been discussed with
details and examples in [
The discussed optimization method in form of Order Dependencies (OD) can be easily applied with use of Cuboid architecture. Without need to interfere with database optimization engines we will be able to rewrite queries stored at the site of Cuboid. 4.1
As depict in fig. 2, client calls for the optimized resource are supposed to be commenced using REST API. The construct of the client REST API includes non optimized and optimized version of the query.
While requesting client will use the REST API to define whether the query response ie. result set, is going to be processed using non optimized version of the query or optimized. We have prepared four implementations for data access layers. Two of them - using JdbcTemplate and SimpleJdbcCall- are Spring Framework based and third is pure JDBC. The final method gets the pmin and pmax hard coded. This is to compare the time of pmin and pmax retrieval and overhead that is brought by each of the three remaining methods.
The REST API is designed as follows. To retrieve unoptimized query answer the request URL should look like this: http://localhost:8080/DIAS/rest/dbs/facts/2008-01-01:2008-01-02 1 The Cuboid can store many arbitrarily customized global views depending on designer requirements. Now, to request for an optimized query depending on query commuting mechanism the URL would change to: http://localhost:8080/DIAS/rest/dbs/facts/2008-01-01:2008-01-02/opti/X Where X stands for the query commit method number. The X values has been assigned as follows: 1. Spring simpleJdbcCall (stored functions) 2. Spring JDBCTemplate call statement (stored functions) 3. pure JDBC connection (stored functions) 4. Spring JdbcTemplate with (sub-queries rewrite) 5. hard coded pmin, pmax values
This way we can get the necessary optimization method in simple and straightforward manner. We will present the results in following section. 5
Let us first describe the testing environment. The tests has been performed using the following hardware:
CPU Intel Core i7-3612QM CPU @ 2.10 GHz x 8 RAM 15,6 GiB Disk SAMSUNG SSD PM830 2.5” 7mm 512GB OS Ubuntu 14.04 LTS Kernel 3.13.0-30-generic Arch. x86 64 GNU/Linux
The test cases assumed two optimization methods. One was to rewrite query with substitution of WHERE clause with two stored function results. For comparison reasons, the second case (fifth method) assumed replacing the stored functions with simple sub queries to achieve the same goal as in the firs case. Namely:
Listing 1.5. Simple rewrite with sub-queries SELECT f i d , sum( a g g r v ) , FROM f a c t s
where f d a t e >= x )
where f d a t e <= y )
All tested use cases were conducted against the same request parameters and source data. The queried data range was between 2008-01-01 and 2008-01-02. The result size was 31,546 MB. Each method has been tested 50 times.
Measuring database response times for pmin and pmax was based on Java’s currentTimeMilis() method from java.lang.System 2.
The test results has been placed in table 3.
The results has clearly shown that rewriting the WHERE clause boosts the target query almost 4 times. This is while only modifying the WHERE clause with subqueries enabling primary key in role of index. This gives us the idea of how order dependency based query can be effective. Both of the queries do operate on f date column that has not even been indexed. The result would be greatly better if only we would place an index on f date column. The hard coded column values for pmin and pmax are presented to compare the time performance of the query itself without rewriting process.
Three remaining JDBC-based use cases for (pmin,pmax) retrieval, are at worst
three times slower than the hard coded (pmin,pmax) pair.
2 The detailed discussion for choosing this method has been conducted in [
In this paper we have analyzed so called order dependencies and their optimisation potential when applied at the middleware level. An order dependency is a functional dependency such that its induced function is monotonic with respect to linear orderings of domains. We have proposed an optimisation method that exploits order dependencies on primary keys. We have prepared its proofof-concept implementation on the middleware level (the cuboid). Middleware has amounted to a feasible place for such optimisations and made such a solution vendor neutral. We have also performed experimental evaluation of this implementation and got promising results.