Repository files navigation

This project is the coprocessor part ofDingo Expression, written in C++. The project is made standalone to be easily integrated into other C++ projects.

#include"expr/runner.h"usingnamespacedingodb::expr;

Assumebytes is an array of typeexpr::Byte[size], which contains the encoded expression

Runner runner;runner.Decode(bytes, size);runner.Run();Operand result = runner.Get();

Operand is a class to hold any supported data types. AnOperand object can be created from any supported typeT by the constructorOperand<T>(T value), and the value contained in anOperand object can be retrieved by

TOperand::GetValue()const;

Operand can also hold aNULL value, and can be tested by the overloaded "equals/non-equals" operator, likeoperand == nullptr oroperand != nullptr.

Dingo Expression Coprocessor supports variables. Internally, variables are indexed by integers, start from 0. If the expression contains variables, aTuple must be bind to theRunner before run

Tuple tuple{1,"Alice",100.0};runner.BindTuple(&tuple);

whereTuple is a type alias ofstd::vector<Operand>. The variables indexed by 0, 1, 2 would be assigned the 1st, 2nd, 3rd values of thetuple, respectively.

Note:

• Therunner does not take ownership of thetuple, which should be released by the caller if necessary
• The number of elemnets in thetuple is not checked when retrieving the value and it is the caller's duty to ensure the index of variables are valid

Dingo Expression Coprocessor has also limited implementation for relational algebra. To use it, add the following to the source code

#include"rel/rel_runner.h"usingnamespacedingodb::expr;usingnamespacedingodb::rel;

Assumebytes is an array of typeexpr::Byte[size], which contains the encoded relational algebra

auto *rel =new RelRunner();rel->Decode(buf, size);

ThenTuples can be put into theRelRunner

for (int i =0; i < tuples.size(); ++i) {constauto *output = rel->Put(tuples[i]);}

Theoutput returned is anotherTuple ornullptr. The former is a valid result and the latter means no result can be retrieved immediately for the input may be fitered out or cached.

If there are datum cached in theRelRunner (which is typically when the relational algebra contains any aggregation), the cached results must be taken out after all tuples are put in

while ((constauto *output = rel->Get()) != nullptr) {do_some_thing(output);};

Note:

• TheRelRunner takes over the ownership of theTuple put in. The caller must not try to release it
• If theoutput returned either byPut orGet is notnullptr, it must be released by the caller
• The implementation ofRelRunner is not thread-safe

TheRunner class is for expression evaluating. The following figure illustrate the evaluating process, in which the expression is like2 + T[0] * 3

TheRunner contains an operand stack and an operator verctor. The operator vector is constructed byDecode method from the encoded bytes of an expression. Each operator can manipulate (push/pop) operands in the operand stack following pre-defined process. WhenRun method is called, operators in the vector are carried out one by one. By callingGet method, the top elemement in the stack is poped out as the returned result. Mostly, there is only one oprand left in the stack afterRun for a valid expression.

Data types are represented by 4 bit, as described in the following table

Note the C++ types are wrapped inOperand class.

Immediate numbers are const values embedded in the encoded expressions, to implement const, index of variables, length of arrays, etc. The encoding of immediate numbers is described in the following table

If the expressions are used in relational algebra, a special byte may be needed to indicate the end of expression. Byte0x00 is used for that purpose. But byte0x00 is not always means the termination of expression, because there may be any bytes in the presentation of an immediate number.

The expressions Dingo Expression Coprocessor processed are represented in suffix style, i.e. the operator is put after its operands. Consts and variables are also treated as operator in this representation. All the operators are encoded into unique bytes representation. Operators may have one or more immediate numbers followed. Generally

• For 1-byte representation, the HSB is set to0, and the lower 4 bits can be used to indicate a data type if needed
• For 2-bytes representation, the HSB is set to1, and the higher 4 bits and the lower 4 bits of the 2nd byte can be used to indicate two data types individually if needed
• No byte0x00 or0xFF is allowed in the representation except for immediate numbers

The encoding of operators is illustrated in the following figure

The encoding of one-byte operators is as follows (The template-likeT is any of theData Types)

The encoding of two-bytes operators is as follows (The template-likeT is any of theData Types)

The coding of functions is as follows

Aggregation functions are used only in relational algebra. Complicated aggregations such asAVG is not supported here. Actually,AVG can be converted toSUM andCOUNT with a projection before encoded.

Encoding of aggregations does not follow the way to encode normal function and has no leading0xF1 byte, but is more like that of one-byte operators, as in the following table

Note:

• The column indices are all started from0
• Some aggregation functions are requried to return0 if there are no input rows, such asCOUNT. For simplicity,NULL is returned for all aggregation functions here and it is in the final reducing stage to convertNULL to0

Only "simple" (the operators have only one single input and one output) relational algebra expressions are supported. These operators are chained with one's output connected to another's input to form a whole relational algebra expression. They are encoded one by one from the input end to the output end.

The encoding of each algebra operators contains an unique "leading byte", a "payload" for the parameters and expressions in the operator and a "trailing byte" which is alwaysEOE (End Of Expression). The details are in the following table

A "Project" operator may contains several expressions but they can be concatenated into one "huge" expression without any separator simplify the evaluating process. The "huge" expression is decoded by oneRunner, and after evaluating there will be several results left in the operand stack just as needed. These results can be taken out by multiple calls toGet method.

• Dingo-Store
• Dingo Expression