Foreign and multi-directional functions
A foreign function allows subroutines defined in Java, C/C++, or Lisp to be called from sa.amos queries. This allows access to external databases, storage managers, or computational libraries.
There are different kinds of foreign functions, including:
A filter predicate is defined as a foreign function whose result is of type
Boolean
. It returns true when certain conditions over its arguments are satisfied, e.g.like(Charstring str, Charstring pat) -> Boolean
.A computation produces a result given that the arguments are known. Such a function has neither argument nor result of type
Bag
, e.g.sqrt(Number x) -> Number r
.An aggregate function has one argument of type
Bag
while the result is not of typeBag
. It iterates over the bag argument to compute some aggregate value over the bag, e.g.max(Bag b) -> Object
.A generator has the result of type
Bag
while no argument is a bag. It produces the result by generating a stream of result tuples for a given argument tuple, e.g.iota(Number l, Number u) -> Bag of Number
.A combiner has one or several arguments of type
Bag
and also the result of typeBag
. It combines one or several bags to form a new bag. For example, basic join operators can be defined as combiners.
A foreign function is defined by a foreign function implementation with syntax:
foreign-function-definition ::=
simple-foreign-definition |
multidirectional-definition
simple-foreign-definition ::=
'foreign' [string-constant]
multidirectional-definition ::=
'multidirectional' capability-list
capability ::= '(' binding-pattern ['key'] capability-implementation ')'
capability-implementation ::=
foreign-capability |
query-capability
foreign-capability ::=
'foreign' string-constant ['cost' cost-spec]
query-capability ::= select-statement
binding-pattern ::= A string constant containing 'b':s and 'f':s
cost-spec ::= function-name |
'{' number ',' number '}'
For example, the system function iota()
is implemented in C as a
simple-foreign-definition
:
create function iota(Number l, Number u) -> Bag of Integer
as foreign 'iota--+';
The string iota--+
is a symbolic name associated in the C code with
the address of the C function implementing iota()
.
The syntax using multidirectional-definition
defines a
multi-directional foreign function. A multi-directional foreign
function has one or several different capability implementations
depending on what variables are known for its arguments or results in a
query execution plan. For a given query using a multi-directional foreign
function, the query optimizer chooses the best capability
implementation to minimize the total execution cost.
For example, the following multi-directional foreign function computes
0, 1, or 2 square roots r
of a number x
:
create function sqroots(Number x) -> Bag of Number r
as multidirectional
("bf" foreign 'sqrt-+') /* capability 1 as foreign function */
("fb" select r*r); /* capability 2 as query */
sqroots()
has two capability definitions, one when x
is known but
not r
indicated by binding pattern bf
, and one for the inverse
when r
is known but not x
with binding pattern fb
.
In general a binding pattern is a string of b:s and f:s, indicating which arguments or results are known or unknown, respectively.
In the example, capability 1 will be used in the query:
select sqroots(4);
while capability 2 will be used in the query:
select n from Number n where sqroots(n)=2;
In the following query the system chooses the cheapest of the two capability implementations:
select sqroots(4)=2;
In general sqroots()
may have the following possible binding patterns:
If we know
x
but notr
, the binding pattern isbf
and the capability implementation should returnr
as the square root ofx
. This capability is implemented as C and associated with the symbolsqrt-+
.If we know
r
but notx
, the binding pattern infb
and the implementation should returnx
asr*r
. This capability is implemented as a query (select expression).If we know both
r
andx
then the binding pattern isbb
and the implementation should check thatx = r*r
. We need not implement this capability since the system can use either of the two other capabilities to infer this test.
With simple foreign functions only the forward (non-inverse) function call is possible. Multi-directional foreign functions permit also the inverse to be called in queries. The benefit of multi-directional foreign functions is that a larger class of queries calling the function is executable, and that the system can make better query optimization.
A capability can be defined as a key to improve query optimization, e.g:
create function sqroots(Number x)-> Bag of Number r
as multidirectional
("bf" foreign 'sqrt-+') /* not unique square root r per x */
("fb" key select r*r); /* unique square x per r */
Be very careful not to declare a binding pattern as key unless it
really is a key for the arguments and results of the function. In the
case of sqroots()
the declaration says that if you know r
you can
uniquely determine x
. However, there is no key for binding pattern
bf
since if you know x
there may be several (i.e. two) square
roots, the positive and the negative. The key declarations are used by
the system to optimize queries. Wrong key declarations may result in
wrong query results because the optimizer has assumed incorrect key
uniqueness.
An example of an advanced multidirectional function is the bult-in
function plus()
(operator +
):
create function plus(Number x, Number y) -> Number r
as multidirectional
('bbf' key foreign 'plus--+') /* addition*/
('bfb' key foreign 'plus-+-') /* subtraction */
('fbb' key select x where y+x=r); /* Addition is commutative */
The following steps are required to define a foreign function:
Implement each foreign function capability using the interface of the implementation language. For Java this is explained in ER00 and for C in Ris12.
If the foreign function is implemented in Java, its foreign function definition must be a string "JAVA:class/method" (e.g. "JAVA:Foreign/helloWorld") that identifies the Java implementation method. There are examples in the Java subfolder of sa.amos.
In case the foreign code is implemented in C/C++ the compiled code must be included in a DLL (Windows) or a shared library (Unix) and dynamically linked to the kernel by calling the function
load_extension("name-of-extension");
. The C function nameda_initialize_extension()
exported from the DLL/shared library extension must assign a symbolic name to the foreign C functions which is referenced in the foreign function definition (sqrt-+
in the example).A multidirectional foreign function needs to be defined through a foreign function definition in AmosQL as
multidirectional-definition
. Here the implementor must associate a binding pattern and an optional cost estimate with each capability. Normally the foreign function definition is specified in an AmosQL script.
Cost estimates
To help the query optimizer the user can associate different costs with each foreign capability.
For example:
create function sqroots(Number x)-> Bag of Number r
as multidirectional
("bf" foreign 'sqrts' cost {2,2}) /* capability 1 by foreign function */
("fb" select r*r); /* capability 2 by query */
Different capabilities of multi-directional foreign functions often
have different execution costs. In the sqroots()
example the cost of
computing the square root is higher than the cost of computing the
square. When there are several alternative implementations of a
multi-directional foreign function the cost-based query optimizer
needs cost estimates to help it choose the most efficient
implementation. In the example we might want to indicate that the cost
of executing a square root is double as large as the cost of executing
a multiplication.
Furthermore, the cost of executing a query depends on the expected
size of the result from a function call. This is called the
fanout (or selectivity for predicates) of the call for a given
binding pattern. In the multi-directional foreign function sqroots()
example the implementation sqrts usually has a fanout of 2.
For good query optimization each foreign function capability should have associated costs and fanouts:
The cost is an estimate of how expensive it is to completely execute (emit all tuples of) a foreign function for given arguments.
The fanout estimates the expected number of elements in the result stream (emitted tuples), given the arguments.
The cost and fanout for a multi-directional foreign function
implementation can be either specified as a constant vector of two
numbers (as in sqroots()
) or as an sa.amos cost function returning
the vector of cost and fanout for a given function call. The numbers
normally need only be rough numbers, as they are used by the query
optimizer to compare the costs of different possible execution plans
to produce the optimal one. The number 1 for the cost of a foreign
function should roughly be the cost to perform a cheap function call,
such as +
or *
. Notice that these estimates are run a query
optimization time, not when the query is executed, so the estimates
must be based on meta-data about the multi-directional foreign
function.
If the simple-foreign-definition
syntax is used or no cost is
specified the system tries to put reasonable default costs and fanouts
on foreign functions, called the default cost model. The default
cost model estimates the cost based on the signature of the function,
index definitions, and some other heuristics. For example, the default
cost model assumes aggregate functions are expensive to execute and
combiners even more expensive. If you have expensive foreign functions
you are strongly advised to specify cost and fanout estimates.
A cost function cfn
is an sa.amos function with signature
create function <cfn>(Function f, Vector bpat, Vector args)
-> (Integer cost, Integer fanout) as ...;
/* e.g. */
create function typesofcost(Function f, Vector bpat, Vector args)
-> (Integer cost, Integer fanout) as foreign ...;
The cost function is normally called at compile time when the optimizer needs the cost and fanout of a function call in some query. The arguments and results of the cost function are:
f
is the full name the called sa.amos function.
bpat
is the binding pattern of the call as a vector of
strings b
and f
, e.g. {"f","b"}
indicating which arguments in
the call are bound or free, respectively.
args
is a vector of actual variable names and constants used in the
call.
cost
is the computed estimated cost to execute a call to f
with
the given binding pattern and argument list. The cost to access a
tuple of a stored function (by hashing) is 2; other costs are
calibrated accordingly.
fanout
is the estimated fanout of the execution, i.e. how many
results are emitted from the execution.
If the cost hint function does not return anything it indicates that the function is not executable in the given context and the optimizer will try some other capability or execution strategy.
The costs and fanouts are normally specified as part of the capability specifications for a multi-directional foreign function definition, as in the example. The costs can also be specified after the definition of a foreign function by using the following sa.amos system function:
costhint(Charstring fn,Charstring bpat,Vector ch)->Boolean
Example:
costhint("number.sqroots->number","bf",{4,2});
costhint("number.sqroots->number","fb",{2,1});
fn
is the full name of the resolvent. bpat
is the binding pattern
string. ch
is a vector with two numbers where the first
number is the estimated cost and the second is the estimated fanout. A
cost function cfn
can be assigned to a capability with:
costhint(Charstring fn, Charstring bpat, Function cfn) -> Boolean
To find out what cost estimates are associated with a function use:
costhints(Function r)-> Bag of (Charstring bpat, Object q)
It returns the cost estimates for resolvent r
and their associated
binding patterns.
To obtain the estimated cost of executing an
sa.amos function f
for a given binding pattern bp
, use:
plan_cost(Function r, Charstring bp)-> (Number cost, Number fanout)