Extraction device, data processing system, and extraction method

• US 10,089,370 B2
• Filed: 06/23/2015
• Issued: 10/02/2018
• Est. Priority Date: 12/13/2013
• Status: Active Grant

• Current Assignee: International Business Machines Corporation
• Original Assignee: International Business Machines Corporation
• Inventors: Imai, Haruki, Komatsu, Hideaki, Koseki, Akira, Takase, Toshiro
• Primary Examiner(s): Ly, Anh
• Application Number:
  US14/748,205
• Publication Number:
  US 20150293981A1
• Time in Patent Office: 1,197 Days
• CPC Class Codes: G06F 16/254 Extract, transform and load [ETL] procedures, e.g. ETL data flows in data warehouses
• CPC Class Codes: G06F 16/258 Data format conversion from or to a database

Abstract

An extraction method for extracting a sub query to be converted to a program for processing stream data continuously inputted to a database, from a query including instructions, as sub queries, to be issued to a database management system. The extraction method includes receiving input of the query and a lower limit value of efficiency as processing time per unit memory increase amount. A calculating operation calculates a one memory increase amount and the efficiency using the memory increase amount and the processing time to be reduced. The method selects a sub query whose calculated efficiency is equal to or higher than the lower limit value and extracts the selected sub query as a conversion object on condition that the integrated memory increase amount is equal to or smaller than the maximum memory increase amount.

Claims

1. An extraction method for extracting, as a conversion object, a sub query to be converted to a program for processing stream data continuously inputted to a database, from a query including one or more instructions as sub queries to be issued to a database management system for managing the database, the method comprising:

receiving,

an input query having one or more sub queries,

a maximum memory increase value to indicate an amount of memory by which memory usage may increase when processing the streamed data, and

a lower limit value of efficiency to indicate a ratio of reduced processing time to increased memory usage, the reduced processing time indicating a difference between a first time to process the stream data using the program and a second time to process the stream data using the database management system, the increased memory usage indicating an amount of memory by which memory usage increases due to processing the stream data using the program compared to processing the stream data using the database management system;

calculating, for each sub query in the input query,

at least one memory increase amount corresponding to a change in memory usage when the sub query is converted to the program and the program is used to process the stream data,

a processing time reduction corresponding to a difference in a time to process the stream data using the program and a time to process the stream data using the database management system, and

an efficiency by using the at least one calculated memory increase amount and the processing time reduction;

selecting at least one sub query having a calculated efficiency equal to or higher than the lower limit value;

integrating a memory increase amount calculated for the selected sub query;

extracting the selected sub query as a conversion object on condition that the integrated memory increase amount is equal to or smaller than the maximum memory increase amount, wherein the selected sub queries are extracted in descending order of the calculated efficiency;

parsing the input query and generating a graph expressed by a tree structure having a set of one or more nodes, wherein each sub query is a node in the set of one or more nodes;

determining whether each node in the set of one or more nodes is a first type of node which executes pipeline processing by processing input data and outputting a processing result or a second type of node which does not execute pipeline processing based on a result of parsing the input query;

classifying nodes in the set of one or more nodes into one or more first node groups and one or more second node groups, wherein nodes in the first node groups are hierarchically connected from a root node and include only nodes from the set of one or more nodes which are the first type of node and nodes in the one or more second node groups include remaining nodes from the set of one or more nodes; and

selecting first nodes corresponding to sub queries whose efficiencies are equal to or higher than the lower limit value from nodes classified into the first node groups and extracting the first nodes as conversion objects, wherein the first nodes are extracted in descending order of the calculated efficiency.

2. The extraction method according to claim 1, wherein selecting at least one sub query comprises selecting the at least one sub query in the descending order of calculated efficiency.

3. The extraction method according to claim 1, further comprising:

classifying the one or more second node groups into one or more third node groups and one or more fourth node groups, wherein nodes in the one or more third node groups are hierarchically connected from a leaf node and only which are the first type of node and nodes in the one or more fourth node groups include remaining nodes of the one or more second node groups;

determining, subsequent to selecting the first nodes and extracting the conversion objects, that the integrate memory increase amount has not reached the maximum memory increase amount; and

selecting, in response to determining that the integrated memory increase amount has not reached the maximum memory increase amount, second nodes whose efficiencies are equal to or higher than the lower limit value from nodes classified into the third node groups and extracts the second nodes as conversion objects.

4. The extraction method according to claim 1, further comprising

calculating the memory increase amount and the processing time reduction based on a data rate of the stream data, a time period of the processing of the stream data, statistical information obtained from the result of executing the query in the past, and information about an operation of the query.