Apparatus and method for processing a data stream

An apparatus and method for processing data stream are provided. A query execution plan for processing data stream is shared between the server and the terminal. The server builds a query execution plan and determines a part of the built query execution plan to be executed in the terminal. The terminal executes the part of the built query execution plan and transfers a result of the execution. The server executes the remaining part of the built query execution plan based on the execution result transferred by the terminal. The part of the query execution plan to be executed in the terminal is determined depending on the performance of the terminal.

CROSS-REFERENCE TO RELATED APPLICATION(S)

This application claims the benefit under 35 U.S.C. §119(a) of Korean Patent Application No. 10-2009-0123326, filed on Dec. 11, 2009, the disclosure of which is incorporated herein by reference in its entirety for all purposes.

BACKGROUND

The following description relates to a Data Stream Management System (DSMS).

2. Description of the Related Art

A DataBase Management System (DBMS) is generally used to extract specific information from structured data. However, a new scheme of processing data has been newly developed with the emergence of new technologies such as a Sensor Network, Mobile Sensing and a Real Time Web. The new processing scheme dynamically corresponds to the data of the Sensor Network, the Mobile Sensing and Real Time Web that is continuously being streamed across a network.

The technology of handling dynamic data is referred to as Data Stream Processing, and also referred to as a Data Stream Management System (DSMS) which is in opposition to DBMS which handles static data.

Data Stream Processing has been used in particular industrial fields such as network monitoring and logistic monitoring using a radio frequency identification (RFID) or other particular specialized fields. However, recently, as personal terminals having a sensor attached thereto have become available on the open market, users now have a data stream based service. An example of such a data stream based service includes a service of reporting a traffic flow or population density using a mobile position sensor and a health care service using a biosensor attached to a personal terminal.

As described above, as the user easily receives a data stream based service, a system of processing a significant amount of continuously changing mass data stream suffers from a load of handling a large number of queries requested by users. In particular, a mobile position sensor based service needs to process all queries requested by users while monitoring a data stream on position information sent from a large number of mobiles devices.

SUMMARY

In one general aspect, there is provided an apparatus for processing a data stream, the apparatus comprising: a determination unit configured to determine a first part and a second part of a query execution plan on queries, the first part comprising a part to be executed in a terminal, the second part comprising a part to be executed in a server; a providing unit configured to provide the terminal with the first part; and a combining unit configured to combine a query execution result with the second part, the query execution result corresponding to the first part and being received from the terminal.

The apparatus may include that the determination unit is further configured to: estimate an operation cost, the operation cost being used to execute a query operator included in the query execution plan in the terminal; and determine the first part based on the estimated operation cost.

The apparatus may further include a terminal information storage unit configured to store terminal-related information comprising at least one of: identification information of the terminal, a Central Processing Unit (CPU) performance information of the terminal, a memory size of the terminal, and an access speed of the terminal to a network.

The apparatus may include that the operation cost is estimated based on the terminal-related information.

The apparatus may include that the combining unit is further configured to combine the query execution result corresponding to the first part with the second part based on the terminal-related information.

The apparatus may include that the query execution plan comprises: at least one query operator; and an execution order of the query operator.

In another general aspect, there is provided an apparatus for processing a data stream, the apparatus comprising: a receiving unit configured to receive a first part of a query execution plan on queries, the first part being determined as a part to be executed in a terminal; and a partial query execution part configured to: execute the first part of the query execution plan; and transmit a result of the execution to a server.

The apparatus may include that the partial query execution unit is further configured to transmit identification information of the terminal, together with the execution result, to the server.

The apparatus may include that the query execution plan comprises: at least one query operator; and an execution order of the query operator.

In another general aspect, there is provided an apparatus for processing a data stream based on a query execution plan for queries, the apparatus comprising: a data sensing terminal configured to execute a part of the query execution plan; and a data stream management server configured to: receive a result of the part of query execution plan from the data sensing terminal; and execute another part of the query execution plan based on the received result.

The apparatus may include that the data stream management server is configured to: estimate an operation cost of the data sensing terminal for executing query operators included in the query execution plan; and determine a part of the query execution plan based on the estimated operation cost, the part of the query execution plan to be executed in the data sensing terminal.

In another general aspect, there is provided a method of processing a data stream, the method comprising: at a server, determining a first part and a second part of a query execution plan on queries, the first part comprising a part to be executed in a terminal, the second part comprising a part to be executed in the server; at the server, providing the terminal with the first part; at the terminal: executing the first part; and transmitting a result of the execution to the server; and at the server, combining the result of execution with the second part.

The method may include that the determining of the first part and the second part comprises: estimating an operation cost of the terminal for executing query operators included in the query execution plan; and determining the first part based on the estimated operation cost.

The method may include that the operation cost is estimated based on at least one of: identification information of the terminal, Central Processing Unit (CPU) performance information of the terminal, a memory size of the terminal, and an access speed of the terminal to a network.

The method may include that, in the combining, the execution result of the first part is combined with the second part based on an identification information of the terminal.

DETAILED DESCRIPTION

FIG. 1illustrates an example of a data stream processing system.

As shown inFIG. 1, a data stream processing system100may include a server101and at least one terminal102. The server101and the terminal102may exchange information with each other through a network103.

The terminal102may include a sensor for sensing various types of data. The sensor may be a position sensor, a Global Positioning System (GPS) sensor, a speed sensor, a temperature sensor, etc. For example, the terminal102may be a mobile phone, a Personal Digital Assistants (PDA), a MP3-player, a laptop computer, or a health care device that is equipped with a sensor described above. The above list is not intended to be limiting.

The terminal102may transmit sensed data to the server101. For example, if the terminal102is implemented as a mobile phone capable of GPS information, the terminal102may transmit GPS information to the server101at predetermined intervals.

The server101may be a data stream management server. The server101may analyze the data received from the terminal in real time and provides a user with information valuable to the user. For example, in response to a user's providing the server101with a question asking how many people are currently positioned in a predetermined area, the server101may notify the user of the number of people positioned in the predetermined area by analyzing GPS information received from the terminal102.

The server101and the terminal102may process a query in cooperation with each other. The process of a query represents searching for information requested by a user and providing of the information. For example, information requested by a user may be obtained by filtering data of a large number of terminals102through a continuous query registered by the user.

In the above example, a query may correspond to the process of asking how many people are currently being positioned in a predetermined area, and processing of a query may correspond to the process of notifying the number of people currently being positioned in the corresponding area. The processing of a query may include a process of executing query operators according to a predetermined order.

That is, individual pieces of data streamed from a plurality of terminals102may be input to the server101, and the server101may perform a stream mining and a continuous query process on a large amount of data stream input in real time.

According to the example of the data stream processing system, the cooperation between the server101and the terminal102may be implemented by sharing a query execution plan (QEP) between the server101and the terminal102. The query execution plan may include at least one query operator and an execution order of the query operator.

The method of building a query execution plan is generally known in art. For example, the server101receives a query from a user, inspects an error by parsing the input query, and generates an optimum query execution plan in consideration of an operation cost for each query operator.

According to the example of the data stream processing system, a part of the query execution plan may be executed in the terminal102and another part may be executed in the server101.

For example, the server101may determine a part of the entire query execution plan to be processed in the terminal102by analyzing the built query execution plan and may provide the determined part to the terminal102. The terminal102may execute the received part of the entire query execution plan and may transmit a result of the execution to the server101. The server101may execute the remaining part of the query execution plan using the result of execution received from the terminal102.

As described above, when the server101and the terminal102share the query execution plan and each executes a part of the query execution plan, the processing load applied to the server101in order to process queries may be reduced.

FIG. 2illustrates an example of a data stream processing apparatus that may also be an example of the server101shown inFIG. 1.

As shown inFIG. 2, a data stream processing apparatus200may include a building unit201, a determination unit202, a providing unit203, a combining unit204, an execution unit205, a query storage unit206, and a terminal-related information storage unit207.

The building unit201may build a query execution plan for queries. The queries may be registered by a user and stored in the query storage unit206. The building unit201may perform a parsing or a validation test on the queries stored in the query storage unit206and may build an optimum query execution plan. The building of query execution plan represents a process of determining an execution order for query operators. Accordingly, the query execution plan may be represented as at least one query operator and an execution order of the query operator.

The determination unit202may determine a first part of the entire query execution plan to be executed in the terminal102and a second part of the entire query execution plan to be executed in the sever101by analyzing the built query execution plan. For example, the first part to be executed in the terminal102may be defined as a set of some query operators in the query execution plan and the second part to be executed in the server101may be defined as a set of remaining query operators in the query execution plan except for the first part.

The part of the entire query execution plan to be assigned to the terminal102may be determined in consideration of a computing power of the terminal102. For example, the determination may be performed taking into consideration information about the performance of a Central Processing Unit (CPU) of the terminal102, information about the memory size of the terminal102, and information about access speed of the terminal102to a network that are stored in the terminal-related information storage unit207. A detailed description thereof will be made later.

The providing unit203may provide the terminal102with the first part determined in the determination unit202. For example, the proving unit203may provide the terminal102with a set of query operators corresponding to the first part.

The combining part204may receive a result of query execution corresponding to the first part included in the entire query execution plan from the terminal102. The combining unit204may combine the received execution result with the second part. The combining unit204may combine the received execution result with the second part based on identification information of the terminal that is stored in the terminal-related information storage unit207.

The execution unit205may execute the second part of the entire query execution plan. When the first part is executed in the terminal102and then combined with the second part, if the execution unit205may execute the second part, the entire query execution plan may be executed.

FIG. 3illustrates an example of a query execution plan.

As shown inFIG. 3, {circle around (a)}, {circle around (b)}, {circle around (c)}, {circle around (d)}, and {circle around (e)} represent query operators, such as a “select,” “project,” “join,” and “union,” and an arrow represents an execution order of the query operators.

A query execution plan300may be built by the building unit201and the query execution plan300may be built differently depending on the type of query, the terminal102, and the type of data stream received from the terminal102. For example, if a query is processed in different terminals, a different query execution plan may be built by each terminal even though the same query is processed.

Referring toFIG. 3, a method of determining a first part301in the determination unit202is described. For convenience, it may be presumed in one example that the query execution plan300is built to process a data stream received from at least one terminal102.

The determination unit202may estimate an operation cost desired to execute a query operator in the terminal102. For example, the estimated operation cost may include a first operation cost310desired when the terminal102only executes the operator {circle around (a)}, a second operation cost320desired when the terminal102executes operators {circle around (a)} and {circle around (b)}, a third operation cost330desired when the terminal102executes operators {circle around (a)}, {circle around (b)}, and {circle around (c)}, a fourth operation cost340desired when the terminal102executes operators {circle around (a)}, {circle around (b)}, {circle around (c)}, and {circle around (d)} and a fifth operation cost350desired when the terminal102executes operators {circle around (a)}, {circle around (b)}, {circle around (c)}, {circle around (d)}, and {circle around (e)}.

The determination unit202may determine the first part301by comparing the estimated operation cost with a threshold value. The threshold value may correspond to a limit value of the computing power of the terminal102. For example, if the threshold value lies between the second operation cost320and the third operation cost330, the limit value of the computing power of the terminal102may be set for when operators {circle around (a)} and {circle around (b)} are executed. In one example, the determination unit202may determine the operators {circle around (a)} and {circle around (b)} as the first part301of the entire query execution plan300. In addition, the determination unit202may determine the remaining part of the entire query execution plan300except for the first part301as the second part302.

The operation cost may be estimated based on CPU performance information of the terminal102, information about a memory size of the terminal102, and information about an access speed of the terminal102to a network. The information about the terminal102may be transmitted from the terminal102to the server101, or may be input by a user of the server101with reference to a device catalog of the terminal102.

As described above, as the query execution plan300may be built differently based on a data stream and the performance of a terminal which differs from terminal to terminal, the first part301of the query execution plan300may differ from terminal to terminal.

FIG. 4illustrates another example of a data stream processing apparatus that may be also an example of the terminal102shown inFIG. 1.

As shownFIG. 4, a data stream processing apparatus400may include a receiving unit401and a partial query execution unit402.

The receiving unit401may receive a first part that is included in the entire query execution plan and is determined as a part to be executed in the terminal. For example, the receiving part401may receive the operators {circle around (a)} and {circle around (b)} shown inFIG. 3or an execution instruction for executing the query operators {circle around (a)} and {circle around (b)}.

The partial query execution unit402may execute the first part of the entire query execution plan and may transmit a result of the execution to the server. For example, the receiving unit401may execute the operators {circle around (a)} and {circle around (b)} included in the entire query execution plan300and transmit a result of the execution to the server.

The partial query execution unit402may transmit the execution result to the server101together with identification information of the terminal102. The identification information of the terminal102transmitted together with the execution result may serve as a criterion that may be used when determining a terminal from which the data corresponding to the execution result of the partial query execution unit402is streamed.

According to one example, the data stream processing apparatus400may further include a front-end processor to remove errors from sensed data and maintain a raw data stream at a predetermined level.

FIG. 5illustrates an example of a data stream processing method.

As shown inFIG. 5, in operation501, the terminal102may transmit terminal-related information to the server101. The terminal-related information may include at least one of: identification information of the terminal102, performance information of a Central Processing Unit (CPU) of the terminal102, the memory size of the terminal102, and the access speed of the terminal102to a network. The transmitted terminal-related information may be stored in the server101.

Alternatively, the terminal102may not transmit terminal-related information and a server administrator of the server may directly input terminal-related information with reference to the specification of hardware stated in a catalog of the terminal102.

Meanwhile, in operation502, the server101may build a query execution plan for registered queries. The query execution plan may include at least one query operator and an execution order of the query operator. The query execution plan may be built differently depending on the type of query, the type of terminal, and the type of data stream received from a terminal.

In operation503, the server101may determine a part of the query execution plan to be executed in the terminal102and a part of the query execution plan to be executed in the server101. For example, the determination unit202may determine the first part301and the second part302of the query execution plan300. The first part301and the second part302may be determined by comparing a threshold value with an operation cost that is estimated based on performance information, such as a CPU performance of the terminal, a memory size of the terminal, and an access speed of the terminal to a network, among the stored terminal-related information.

In operation504, the server101may transmit to the terminal102the first part301to be executed by the terminal102. For example, the providing unit203may provide the terminal101with a query operator corresponding to the first part301, or provide the terminal101with an execution instruction allowing the terminal102to execute a query operator corresponding to the first part301.

In operation505, the terminal, having received the first part301, may execute a query operator corresponding to the first part301. For example, the partial query execution unit402may execute some part of the entire query execution plan.

In operation506, the terminal102may transmit an execution result on the first part301to the server101. For example, the terminal102may execute query operators {circle around (a)} and {circle around (b)} and transmit a result of execution to the server. In addition, the terminal102may transmit its own identification information together with the result of execution.

In operation505, the server101, having received the query execution result corresponding to the first part301, may combine the execution result with the second part302. In one example, the server101may determine a terminal, from which the execution result is generated, based on identification information of the terminal102of the stored terminal-related information.

In operation508, in response to the execution result transmitted from the terminal102, the server101may execute the second part302corresponding to the remaining part of the entire query execution plan300. In operation509, the server101may transmit a result of execution of the entire query execution plan300to the terminal102.