JP5458330B2 - Database processing method and database processing system - Google Patents

Description

  The present invention relates to a technique for extracting data from a database, and more particularly to a technique for extracting sorted data.

  In recent years, a large amount of data collection tools related to corporate activities have been established, and business data analysis in which on-site personnel analyze using a large amount of sales data is becoming widespread. In business data analysis, analysis proceeds at each stage, such as hypothesis planning, trend analysis, and factor analysis.

  In business data analysis, it is necessary to extract a large amount of data because the person in charge in the field performs trial and error and repeats several hypothesis planning and trend analysis. Therefore, in order to efficiently process such a large amount of data, it is managed by a database.

  In a database system that processes a large amount of data, data to be analyzed is stored in a plurality of tables. When data is extracted, data stored in a plurality of tables are concatenated to extract data that satisfies the conditions specified by the analyst.

  Therefore, in order to speed up the process of extracting such data, it is possible to speed up the data extraction by issuing multiple data read requests to the secondary storage device (storage device) in which the data is stored. An unordered database (DB) has been developed (see Patent Document 1).

  On the other hand, in trend analysis, it is often required to extract data from a large amount of accumulated data in an important order and show it to an analyst. If the size of the extracted data is large, it takes time to arrange the data in the specified sort order. Patent Document 2 describes a technique for converting a sorting result for a column in which an index is created in an unordered DB at high speed.

JP 2007-34414 A US Patent Publication 2010/0211577

  In business data analysis, it is necessary to extract necessary data from a large amount of accumulated data in trend analysis and rearrange the extracted data in a specified order so that analysis is easy. At this time, if the extracted data amount is large, a large amount of processing time is required to rearrange the data in the designated order.

  With the unordered DB disclosed in Patent Document 1, it is possible to speed up the data extraction, but the rearrangement of the extracted data (sorting) does not take advantage of the characteristics of the unordered DB. There wasn't. Therefore, even if data extraction is accelerated, sorting of the extracted data may become a bottleneck.

  It is an object of the present invention to speed up the process of extracting sorted data in a database processing system that acquires data stored in a secondary storage device.

  According to a representative aspect of the present invention, in a computer that executes a database management system that manages a database in which data is stored, a database processing method that outputs requested data, the computer including: A processor for executing a database management system; and a memory for storing the database management system, wherein a record is constituted by one or more columns corresponding to the data, and the columns constituting the record have the specified order Including a sort specification column corresponding to a value to be determined, the method wherein the processor accepts a query request designated to output query results for the requested data in a designated order; Based on the received inquiry request, the processor assigns to a table storing the data. A second step of generating a query execution plan including an access order; and a third step in which the processor obtains data requested based on the query request from the database based on the generated query execution plan. A fourth step in which the processor generates an intermediate result including the acquired data for each record in the record unit; and the processor specifies the generated intermediate result in the query request. A fifth step of rearranging in the ordered order, and a sixth step in which the processor determines, for each of the intermediate results, whether or not the order of the sorted intermediate results has been determined based on the progress of processing. A seventh step in which the processor outputs the intermediate results of the determined order in order from the top as the query results; The processor, the intermediate result generated in the fourth step, a first list constituted by intermediate results for which the value of the sort designation column is not obtained, the value of the sort designation column is obtained, and The second list constituted by intermediate results from which all the data corresponding to the columns constituting the record are not obtained, or the second list constituted by the intermediate results from which all the data corresponding to the columns constituting the record are obtained. An eighth step of classifying the list into any one of the three lists, wherein the fifth step includes the step of rearranging the order of the intermediate results classified into the third list in the specified order. In the sixth step, if all the data corresponding to the columns constituting the record have not been acquired, the processor And the sixth step includes a ninth step in which the processor determines whether there is an intermediate result classified in the first list, and the processor includes the second step. A tenth step of obtaining the value of the sort specification column of the intermediate result with the first order as the order determination determination value when the intermediate results classified in the list are rearranged in the specified order; In the sixth step, when there is no intermediate result classified in the first list, the processor is classified in the third list, and the order comes before the intermediate result having the order determination determination value. It is determined that the intermediate result having the value of the sort specification column is determined, and in the seventh step, the processor is classified into the third list, and the intermediate result whose order is fixed Is output as the query results in order from the head.

  According to one aspect of the present invention, the data extracted and the data sorted and returned are executed in parallel, thereby reducing the time from the start of extraction to the start of transmission of the query result, thereby sorting the sorted data. Can be speeded up.

It is a block diagram which shows the structure of the computer system of the 1st Embodiment of this invention. It is a flowchart which shows the procedure which classifies an execution context by the execution context management part of the 1st Embodiment of this invention. It is a flowchart which shows the procedure which determines whether the sort order of a query result was decided by the result order decision part judgment part of the 1st Embodiment of this invention. It is a figure which shows an example of SQL corresponding to the inquiry request | requirement of the 1st Embodiment of this invention. It is a figure which shows an example of the table which stores the data extracted by the inquiry request of the 1st Embodiment of this invention. It is a figure which shows an example of the query execution plan corresponding to SQL corresponding to the query request of the 1st Embodiment of this invention. It is a figure explaining the specific example of the process in which the sorted data in the 1st Embodiment of this invention are extracted from a database, and it outputs as a query result. It is a block diagram which shows the structure of the computer system of the 2nd Embodiment of this invention.

(First embodiment)
FIG. 1 is a block diagram showing a configuration of a computer system according to the first embodiment of this invention.

  The computer system according to the first embodiment of this invention includes a database server 101, one or a plurality of external storage devices 103. The database server 101 and the external storage device 103 are connected to each other via the network 102.

  The database server 101 executes a database management system 132 that is a program for managing data stored in the external storage device 103. Then, the query requested by the application program 131 executed by the database server 101 or a client computer (not shown) is processed, and the query result is returned.

  The database server 101 includes a memory 111, a processor 112, and an interface 113. The memory 111 stores a program such as the database management system 132 and data necessary for executing the program. The processor 112 executes various processes by executing a program stored in the memory 111.

  The interface 113 is connected to the external storage device 103 via the network 102. When the network 102 is a storage area network (SAN), the interface 113 may be a so-called host bus adapter (HBA). When the program stored in the memory 111 is executed, an input / output request is issued to the external storage device 103 via the interface 113 as necessary.

  The network 102 is, for example, a storage area network (SAN) to which a fiber channel (FC) protocol is applied, but may be any other form of network. Specifically, if the network 102 is an Internet protocol (IP) network, the database server 101 and the external storage device 103 may communicate with each other using the iSCSI protocol.

  The external storage device 103 stores data managed by the database server 101 and reads / writes the requested data based on an input / output request transmitted from the database server 101.

  The external storage device 103 includes an interface 123, a control device 122, and a storage device 121. The interface 123 is connected to the network 102. The control device 122 processes the input / output request transmitted from the database server 101.

  The storage device 121 stores a database that manages data that is read and written by input / output requests. The storage device 121 may be a hard disk drive (HDD), an optical disk drive, a semiconductor storage device, or another storage device. In FIG. 1, one storage device 121 is provided in the external storage device 103, but the number of storage devices 121 is arbitrary. Further, when a plurality of storage devices 121 are provided, a disk array may be configured.

  Next, a program executed on the database server 101 will be described. Programs stored in the memory 111 include an application program (AP) 131, a database management system 132, and an operating system (OS) 133.

  The processor 112 executes various business processes by executing the AP 131. At this time, the AP 131 issues a query request to the database management system 132 and receives the query result. In the first embodiment of the present invention, the AP 131 is executed by the same computer (database server 101) as the database management system 132, but the application program is executed by another computer connected through the network. It is good.

  The database management system 132 searches the database stored in the external storage device 103 for data that matches the condition specified by the requested query. Then, data that becomes a search result (inquiry result) is acquired, and a response is made to the request source.

  The database management system 132 includes a relational database management system (RDBMS) based on a relational model or an object-oriented database management system based on an object model. In the first embodiment of the present invention, RDBMS is particularly targeted.

  In the RDBMS, data is stored in the table 161 in units of records composed of a plurality of types of data, and an index 162 is provided for accessing records with a small number of I / O requests. The data structure of the index 162 may be a B-tree or a hash. A query for data is described by SQL (Structured Query Language). In SQL, the output order specification of query results is expressed by an Order by clause, and the aggregation operation is expressed by a Group by clause.

  In the first embodiment of the present invention, the database management system 132 stores the table 161 and the index 162 in the external storage device 103 connected via the network 102, but the database server 101 has a storage device. If provided, it may be stored in a storage device in the database server 101.

  The OS 133 is a program that manages the resources (the processor 112 and the memory 111) of the database server 101. Further, it receives an input / output request from the database management system 132 and issues an input / output request to the external storage device 103.

  Here, the detailed configuration of the database management system 132 will be described. The database management system 132 includes a query reception unit 141, a query execution unit 143, a query execution plan generation unit 142, an execution task management unit 144, and a DB buffer 145. And a query result storage unit 146 are provided.

  The inquiry reception unit 141 receives an inquiry request requested from the AP 131. Furthermore, the inquiry reception unit 141 analyzes the received inquiry request, and executes the query execution plan generation unit 142 or the query execution unit 143 according to the analysis result.

  The query execution plan generating unit 142 generates a query execution plan that is a processing procedure of the query request received by the query receiving unit 141. The query execution plan will be described later.

  The query execution unit 143 executes processing necessary for processing the requested query based on the query execution plan generated by the query execution plan generation unit 142.

  The query execution unit 143 can execute a basic database operation for generating a query result. The query execution plan is a combination of database operations necessary to generate a result corresponding to the query.

  The query execution unit 143 includes an execution context management unit 150, a result order fixed part determination unit 160, and a query result return unit 170.

  As described above, the query execution unit 143 generates a plurality of tasks and processes the query request. An execution context that can be logically executed in parallel in the query execution plan is assigned to the plurality of tasks. The execution context includes processing corresponding to the operations constituting the query execution plan. When the execution context is executed, a task is generated for each operation, and the query processing is executed by executing the generated task.

  The execution context management unit 150 classifies and manages a plurality of execution contexts for each process progress. The execution context management unit 150 includes a result candidate list 151 (first list and second list) and a result confirmation list 152 (third list), and classifies the execution context into one of the lists according to the progress of processing. To do. At this time, intermediate results including acquired data in the execution context being processed may be classified. The procedure for classifying the execution context will be described later with reference to FIG.

  The result candidate list 151 stores (classifies) execution contexts for which the sorting result is undetermined among the results of executing a part of the task for processing the query. The result candidate list 151 includes a determination column non-acquisition list 153 (first list) and a determination column acquisition completed list 154 (second list). The determination column non-acquisition list 153 stores execution contexts in which data corresponding to the sort specification column is not acquired. On the other hand, the determination column acquired list 154 stores execution contexts for which data corresponding to the sort specification column has been acquired. The result confirmation list 152 stores an execution context in which the result of the query request is confirmed.

  The result order determination part determination unit 160 determines the sort order determination part of the query results for the execution context classified and managed, and notifies the query result return unit 170 of the record in which the sort order is determined.

  Specifically, when there is no execution context classified in the determination column non-acquisition list 153 of the result candidate list 151, the value of the sort designation column of the execution context with the first sort order in the determination column acquisition list 154 Refer to Then, in the result confirmation list 152, the query result generated by the execution context whose order is earlier than the value in which the value of the sort designation column is referred to is determined to have the confirmed sort order. The procedure for determining the sorting order determination part of the inquiry result will be described later with reference to FIG.

  The query execution unit 143 issues an I / O request to the operating system 133 in the course of processing the query request, and holds the I / O result in the DB buffer 145. Then, the result of the query request is stored in the query result storage unit 146.

  The query result return unit 170 returns the result of the query request stored in the query result storage unit 146 to the application program 131.

  The execution task management unit 144 manages a task generated for executing the query execution plan.

  The DB buffer 145 stores cached data in order to speed up data access.

  The query result storage unit 146 stores the result of the query executed by the query execution unit 143.

  FIG. 2 is a flowchart illustrating a procedure for classifying execution contexts by the execution context management unit 150 according to the first embodiment of this invention. This process is executed by executing a program included in the execution context management unit 150.

  As described above, this processing is processing for classifying execution contexts that are being processed or have been processed. The execution context classification is to store (assign) execution contexts that are being processed or have been processed in the result candidate list 151 (the determination column non-acquisition list 153, the determination column acquisition completed list 154) or the result determination list 152. .

  In addition, when managing execution contexts in the result candidate list 151 and the result confirmation list 152, data (intermediate results) corresponding to the execution context itself may be managed, or references to data (pointers) may be managed. . In the result confirmation list 152, reference to the result data generated by the execution context classified in the result confirmation list 152 and stored in the query result storage unit 146 may be managed.

  First, the processor 112 selects an execution context, and determines whether or not the value of the sort specification column, that is, the column (determination column) for which the sort order is determined has been acquired from the table 161 of the database (S201). ).

  If the determination column value has not been acquired (the result of S201 is “N”), the processor 112 classifies the execution context selected in the determination column non-acquisition list 153 of the result candidate list 151 (S202).

  On the other hand, when the value of the determination column has been acquired (the result of S201 is “Y”), the processor 112 determines whether or not the execution of the selected execution context has been completed (S203).

  When the execution of the selected execution context is not completed (the result of S203 is “N”), the processor 112 classifies the selected execution context in the determination column acquired list 154 of the result candidate list 151 ( S204). On the other hand, when the execution of the selected execution context is completed (the result of S203 is “Y”), the selected execution context is classified in the result confirmation list 152 (S205).

  As described above, in the first embodiment of the present invention, the execution context is classified based on whether or not the value of the sort designation column has been acquired, and whether or not all the data acquired in the execution context has been acquired. To do. When the values of the sort specification columns are acquired for all execution contexts, that is, when all execution contexts are classified into the determination column acquired list 154 or the result determination list 152 of the result candidate list 151, the result determination is performed. It is determined whether or not the sorting order of the query results corresponding to the execution context included in the list 152 has been determined. A procedure for determining whether or not the sorting order of the inquiry results has been determined will be described with reference to FIG.

  FIG. 3 is a flowchart illustrating a procedure for determining whether or not the result order determination part determination unit 160 according to the first embodiment of this invention determines the sort order of the query results.

  First, the processor 112 determines whether or not the determination column non-acquisition list 153 of the result candidate list 151 is empty (S301). That is, it is determined whether or not all values of the sort specification column have been acquired. When the determination column non-acquisition list 153 of the result candidate list 151 is not empty (the result of S301 is “N”), all the values to be sorted are not acquired, and the data order cannot be determined. This process ends.

  When the determination column non-acquisition list 153 of the result candidate list 151 is empty (the result of S301 is “Y”), the processor 112 has acquired all the values of the target sort specification column, and therefore at least confirms the result. Sort processing can be executed on the execution contexts classified in the list 152. At this time, the values of the sort designation columns corresponding to the execution contexts classified in the determination column acquired list 154 and the result confirmation list 152 of the result candidate list 151 are already sorted.

  Then, the processor 112 sets the value of the sort designation column (order determination determination value) of the execution context in the topmost order in the determination column acquired list 154 of the result candidate list 151 to N (S302). Then, it is determined whether or not the value of the sort designation column (determination column value) of the first execution context in the result determination list 152 precedes N (S303). When it does not precede N (the result of S303 is “N”), the execution context in which the sort order is determined is not included in the result determination list 152, and thus this processing is terminated.

  If the determination column value of the first execution context in the result determination list 152 precedes N when the result is sorted (the result of S303 is “Y”), the processor 112 starts the execution context in the result determination list 152. Is sent to the inquiry result return unit 170 and deleted from the result confirmation list 152 (S304). Then, it is determined whether or not the determination column value of the execution context that has newly headed precedes N (S303), and until the determination column value of the leading execution context does not precede N (or the result is confirmed) Steps S303 and S304 are executed until the list 152 becomes empty.

  Hereinafter, a method for extracting sorted data according to the first embodiment of the present invention will be specifically described with reference to the drawings.

  In the specific example described below, data is extracted in the specified order from the three tables of the product schedule (T1), the sales history data table (T2), and the customer table (T3). A query request for extracting data is expressed by general SQL.

  FIG. 4 is a diagram illustrating an example of SQL corresponding to the inquiry request according to the first embodiment of this invention.

  The query request SQL shown in FIG. 4 extracts the data stored in the product specification table (T1), the sales history data table (T2), and the customer table (T3) that satisfy the specified conditions in the specified order. .

  First, before explaining the details of SQL, the configuration of the product specification table (T1), the sales history data table (T2), and the customer table (T3) will be described with reference to FIG.

  FIG. 5 is a diagram illustrating an example of a table storing data extracted by the inquiry request according to the first embodiment of this invention.

  The three tables of the product specification table (T1), the sales history data table (T2), and the customer table (T3) are included in the table 161 stored in the storage device 123 of the external storage device 103.

  The commodity specification table (T1) includes an “itemID” column, a “category” column, and a “price” column.

  The value of the “itemID” column is an identifier for identifying a product. The value of the “category” column indicates the category of the product identified by itemID. Specifically, values such as “coffee” and “tea” are set. The value in the “price” column indicates the price of the product identified by the itemID.

  The sales history data table (T2) includes an “orderID” column, an “itemID” column, a “cusID” column, and a “num” column.

  The value of the “orderID” column is an identifier for identifying an order. The value of the “itemID” column is an identifier for identifying the ordered product. The value in the “customID” column is an identifier for identifying the customer who has placed the order. The value in the “num” column is the number of items ordered.

  The customer table (T3) includes a “custID” column, a “gender” column, and an “age” column.

  The value in the “customID” column is an identifier for identifying a customer. The value in the “gender” column is information indicating the gender of the customer identified by the custom ID. The value of the “age” column is information indicating the age of the customer identified by the custom ID.

  Here, it returns to description of SQL shown in FIG. The SQL shown in FIG. 4 corresponds to the product specification table (T1), the sales history data table (T2), and the customer table (T3) that satisfy the condition that a woman aged 20 to 29 has ordered coffee. Indicates that a record (data) is to be extracted.

  More specifically, the value of the “category” column of the product schedule (T1) is “offee”, and the “itemID” column of the product schedule (T1) and the “itemID” column of the sales history data table (T2) Are the same, and the “customID” column of the sales history data table (T2) and the “customID” column of the customer table (T3) are the same, that is, the item description table (T1) and the sales history data table with itemID (T2) is joined, and the sales history data table (T2) and the customer table (T3) are joined by customID. Then, data (records) satisfying the condition that the value of the “gender” column of the customer table (T3) is “F” and the value of the “age” column of the customer table (T3) is 20 to 29 are combined. Extract from the three tables (T1, T2, T3), and output the values in the “price” column of the product specification table (T1) in descending order.

  The arrows connecting the records in each table shown in FIG. 5 illustrate the combined state of the records. More specifically, the record with the value “0001” in the “itemID” column of the product description table (T1) whose value in the “category” column is “offee” is the “itemID” in the sales history data table (T2). It is linked to two records whose column value is “0001”. Furthermore, the values in the “custID” column of these two records are “0001” and “0003”, respectively, and are linked to the corresponding records in the customer table (T3). At this time, in the SQL shown in FIG. 4, the condition “female” and “20 to 29 years old” is specified, so the record whose value in the “custID” column is “0003” is not extracted.

  Next, a query execution plan (processing order) indicating the order of accessing the table and the index generated based on the SQL shown in FIG. 4 will be described.

  FIG. 6 is a diagram illustrating an example of a query execution plan corresponding to the SQL corresponding to the query request according to the first embodiment of this invention.

  In the first embodiment of the present invention, an index is assigned to the “category” column of the product schedule (T1), the “itemID” column of the sales history data table (T2), and the “customID” column of the customer table (T3). Has been created. These indexes are included in the index 162 stored in the storage device 123 of the external storage device 103.

  The query execution plan shown in FIG. 6 is composed of six operations (OP1 to OP6), and query results sorted by OP6 are output. The execution context includes processing from OP1 to OP6, and when a plurality of data is extracted in the middle of the operation, the execution context is divided into execution contexts corresponding to the number of extracted data. The divided execution contexts can be processed in parallel.

  In addition, as described above, the query execution unit 143 generates a task for each operation in order to execute each operation constituting the query execution plan generated by the query execution plan generation unit 142. Tasks generated in the same execution context are sequentially executed according to the execution order of operations, but tasks generated in different execution contexts can be executed in parallel.

  In the query execution plan shown in FIG. 6, first, a record in which the value of the “category” column is “offset” is searched using the index of the “category” column of the product schedule (T1), and the corresponding record is displayed. Obtain from T1.

  Subsequently, using the index of the “itemID” column in the sales history data table (T2), search for a record in which the value of the “itemID” column is the same as the value of the “itemID” column of the record acquired from the product description table (T1) To do. Then, the corresponding record is acquired from the sales history data table (T2) and combined with the record acquired from the product description table (T1).

  Subsequently, using the index of the “customID” column of the customer table (T3), search for a row in which the value of the “customID” column is the same as the value of the “customID” column of the record acquired from the history data table (T2) The corresponding record is acquired from the customer table (T3). Further, it is determined whether or not the value of the “gender” column of the acquired record is “F (female)” and the value of the “age (age)” column is 20 to 29. When the condition is satisfied, the record generated by combining the acquired records of T1 and T2 and the record acquired from the customer table (T3) are combined and stored in the query result storage unit 146.

  When returning a query result, a record stored in the query result storage unit 146 and combined so that the value of the “price” column of the product schedule (T1) is in descending order is queried. Return to the sender of the request.

  Next, a process of acquiring data and outputting a query result according to the query execution plan shown in FIG. 6 will be described.

  FIG. 7 is a diagram illustrating a specific example of a process of extracting sorted data from the database and outputting it as a query result according to the first embodiment of this invention.

  In the query execution plan shown in FIG. 6, a query combining records of the corresponding sales history data table (T2) and customer table (T3) from the data for one record of the product description table (T1) shown in FIG. A series of processes for retrieving and extracting the result is one execution context. Therefore, at the stage before the execution context is divided, an execution context is generated for each row in which the value of the “category” column is “offee”. These execution contexts can be processed in parallel.

  Phase 1 in FIG. 7 indicates a state immediately after the start of execution of the inquiry process. Specifically, in the execution context that is executed first, the index search processing part of the “category” column of the product schedule (T1) is being executed by one task. That is, OP1 in the query execution plan of FIG. 6 has been completed. The execution context in phase 1 is classified into the determination column non-obtained list 153 of the result candidate list 151 because the value of “price” in the product specification table (T1), which is the sort designation column, is not acquired (S202 in FIG. 2). ).

  Phase 2 in FIG. 7 indicates a state in which the processing has progressed more than the above-described phase 1. Specifically, the execution context may acquire the first record whose “category” column value is “offset” from the product schedule (T1), and the corresponding “price” column value may be 500. Prove. At this stage, OP2 in the query execution plan of FIG. 6 has been completed.

  Subsequently, based on the value (specifically, “0001”) in the “itemID” column of the product description table (T1), an index search of the “itemID” column in the sales history data table (T2) is executed (OP3). The corresponding record is acquired from the sales history data table (T2) (OP4). At this time, since two records are acquired from the sales history data table (T2), the execution context is divided into two.

  In phase 2, since the value of the sort designation column is acquired, it is classified into the determination column acquired list 154 of the result candidate list 151 (S204 in FIG. 2). In addition, another execution context in which the index search processing of the “category” column of the product specification table (T1) is started in parallel is classified in the determination column non-acquisition list 153 of the result candidate list 151. At the stage where phase2 is completed, OP4 in the query execution plan of FIG. 6 is in a completed state.

  Phase 3 shows a state in which the processing has progressed further than phase 2. Specifically, the execution context having the value of the “price” column of 500 is further processed, and is completed until the acquisition of the record of the customer table (T3) and the condition determination. At this time, OP6 in the query execution plan of FIG. 6 has been completed. Therefore, the execution context is classified into a “result confirmation list” (S205 in FIG. 2).

  Note that the other execution context divided by phase 2 does not satisfy the search condition, and therefore is not classified into the result determination list 152. An execution context that does not satisfy the search condition is discarded when it is determined that the search condition is not satisfied, and is not classified into any list.

  In phase 4, since there is no execution context classified in the determination column non-acquisition list 153 of the result candidate list 151, the result of determining the sort order from the result determination list 152 is determined. That is, all values are acquired in the sort specification column of records that may at least satisfy the search condition. Therefore, the execution context having the largest value in the “price” column, which is the sort specification column, is acquired from the execution contexts classified in the determination column acquired list 154 of the result candidate list 151, and the value of the “price” column is set as the value. The order determination determination value is used (S302 in FIG. 3). Then, if execution contexts whose values in the “price” column are larger than the order decision determination value are classified in the result decision list 152, it is possible to return the result as a query result to the request source.

  More specifically, in phase 4 of FIG. 7, the value of the “price” column of the execution context classified in the determination column acquired list 154 of the result candidate list 151 is 200, and the order determination determination value is 200. Then, an execution context (1000, 500) having a value of “price” column of 200 or more is selected from the execution contexts of the result confirmation list 152. Since the records (intermediate results) generated by the selected execution context can determine the order, the records generated by the selected execution context are sorted in the order of the values in the “price” column. Then, the record is notified to the query result return unit 170, and the return of the query result is started before all the search processes for the query request are completed.

  When the execution contexts are classified into the judgment column acquired list 154 or the result confirmation list 152 of the result candidate list 151, the execution contexts are sorted in advance so as to be in the order specified by the received query request. It is good to leave.

  When sorting by the value of the sort specification column in the result confirmation list 152, the value of the sort specification column and the order determination determination value are compared in order from the first execution context, and the value of the sort specification column is earlier than the order determination determination value. The comparison may be stopped when the order is not reached, and the record (intermediate result) of the compared execution context in the result confirmation list 152 may be notified to the query result return unit 170. In addition, the inquiry result return unit 170 may be notified at the time of comparison.

  In addition, when sorting is performed by the value of the sort specification column in the determination column acquisition list 154 of the result candidate list 151, the value of the sort specification column of the first execution context can be set as the order determination determination value. It is possible to improve the efficiency of the process of obtaining the.

  Furthermore, when the context classification destination is changed from the determination column acquired list 154 of the result candidate list 151 to the result confirmation list 152, the storage position of the result confirmation list 152 can be determined by comparing in order from the top of the list. It becomes possible.

  At this time, the data structure for managing the execution contexts classified in the determination column acquired list 154 of the result confirmation list 152 and the result candidate list 151 in the order of the values of the sort specification column may be a unidirectional list. An interactive list may be used. Moreover, a tree structure may be sufficient.

  Also, when managing execution contexts in the list in the order of the values of the sort specification column, the sort process may be executed each time execution contexts are inserted into the list, and the timing when a predetermined number of execution contexts are classified It may be executed at any other timing.

  In addition, the timing at which the result order determination part determination unit 160 executes the order determination determination is immediately after the execution context classified in the determination column non-acquisition list 153 of the result candidate list 151 disappears. Thereafter, the result return may be executed at a timing requested by the user, or may be a timing when a certain number of records (query results) are inserted into the query result storage unit 146.

  Further, in the first embodiment of the present invention, if the acquisition of the value of the sort designation column is completed in all execution contexts as soon as possible, the return start time of the query result can be advanced. Therefore, when the query execution plan is generated, the return start time of the query result can be advanced by setting the access order of the table including the sort specification column to be earlier.

  The execution task management unit 144 can manage the execution order of a plurality of execution contexts, but executes the execution contexts classified in the determination column unacquired list 153 of the result candidate list 151 most preferentially, and subsequently By preferentially executing the execution context classified in the determination column acquired list 154 of the result candidate list 151, the time from the start of the query process to the start of the query result return process can be further shortened. It becomes.

  According to the first embodiment of the present invention, it is possible to sequentially return query results sorted before obtaining all query results. Therefore, it is possible to shorten the time from the start of the query process to the start of the query result return process. Further, since the query results classified in the result confirmation list 152 are sorted and stored in advance based on the value of the sort designation column, it is not necessary to execute a process of sorting the data after extracting all the results.

  In addition, according to the first embodiment of the present invention, the values of the sort specification column can be sorted without using the index, and therefore, the sort specification column for which no index is created is used. It becomes possible to extract the sorted data quickly.

(Modification of the first embodiment)
In the first embodiment described above, the present invention is applied to an unordered database that can execute data reading in parallel in a plurality of execution contexts. It may be applied to a typical database. Hereinafter, a description will be given as a modification of the first embodiment.

  A general database which is not an unordered database is different in that the execution task management unit 144 is not included in the database management system 132 in the system configuration shown in FIG. That is, since the execution context is sequentially executed by one task, one execution context is processed at a time.

  Therefore, execution contexts for which processing has not started are classified into the determination column non-obtained list 153 of the result candidate list 151, and execution contexts being processed are classified into the determination column acquired list 154 of the result candidate list 151. Then, execution contexts for which processing has been completed are classified into the result confirmation list 152.

  At this time, by managing the result confirmation list 152 in the order of the sort designation column, when the last execution context is classified into the determination column acquired list 154 of the result candidate list 151, the order confirmation portion of the result confirmation list 152 is returned. To do.

  As described above, according to the modification of the first embodiment of this invention, the query result cannot be returned in the middle of the query process, but the results of the execution context classified in the result confirmation list 152 are sorted. By sorting and managing based on the value of the designated column, the sorting process after the result extracting process becomes unnecessary, and the process of extracting the sorted data can be speeded up.

(Second Embodiment)
Next, a second embodiment of the present invention will be described. In the first embodiment, the present invention is applied to an unordered database. However, in the second embodiment, the present invention is applied to a parallel database system in which query requests are processed in parallel by a plurality of computers. In the following, the difference between the second embodiment and the first embodiment will be described.

  FIG. 8 is a block diagram illustrating a configuration of a computer system according to the second embodiment of this invention.

  The computer system according to the second embodiment of this invention includes a request reception server 104, a plurality of execution servers 106, and an external storage device 103.

  The request reception server 104 and the plurality of execution servers 106 are connected to each other via the network 105. A plurality of execution servers 106 and an external storage device 103 are included. The database server 101 and the external storage device 103 are connected to each other via the network 102.

  Similar to the database server 101, the request reception server 104 includes a memory 111, a processor 112, and an interface 113. The memory 111 stores a database management system 132. The interface 113 is connected to the network 105.

  The execution server 106 includes a memory 201, a processor 202, an interface 203, and an interface 204. The memory 201 stores a data processing unit 210 that acquires data from the external storage device 103. The interface 203 is connected to the request reception server 104 via the network 105. The interface 204 is connected to the external storage device 103 via the network 102.

  The request reception server 104 receives an inquiry request and assigns an execution context to the execution server 106. That is, the request reception server 104 generates a plurality of execution contexts as in the database server 101 in the first embodiment. At this time, information necessary for processing the execution context is transmitted to the execution server 106 without directly accessing the external storage device 103.

  The execution server 106 acquires the query result by processing the execution context instructed by the request reception server 104 by the data processing unit 210. Similar to a general database server, the execution server 106 can process only one execution context at a time.

  The request reception server 104 holds a result candidate list 151 and a result confirmation list 152 as in the database server of the first embodiment. The request reception server 104 selects the execution server 106 that processes the execution context after generating the query execution plan. Then, when the selected execution context is assigned to the selected execution server 106, the start of processing is instructed. At this time, the request reception server 104 classifies the assigned execution context into the determination column non-acquisition list 153 of the result candidate list 151.

  When the execution server 106 processes the assigned execution context and acquires the value of the sort specification column, the execution server 106 transmits an intermediate result to the request reception server 104. Upon receiving the intermediate result obtained from the value of the sort designation column, the request reception server 104 classifies the corresponding execution context into the determination column acquired list 154 of the result candidate list 151.

  Thereafter, the execution server 106 continues the processing of the execution context, and transmits the processing result to the request reception server 104 when the execution of all the operations is completed. The request reception server 104 classifies the execution context corresponding to the received processing result in the result confirmation list 152.

  When the execution context is divided into a plurality of parts while the execution server 106 is processing the execution context, the execution server 106 may process the execution context sequentially, or the request may be made except for one execution context. It may be transmitted to the reception server 104 and the request reception server 104 may be assigned to another execution server 106.

  As described above, according to the second embodiment of the present invention, the present invention can be applied to an existing parallel database system. Accordingly, by causing each execution server 106 to read out data and managing the result candidate list 151 and the result confirmation list 152 at the request receiving server, the query results sorted before obtaining all the query results are sequentially returned. It is possible to speed up the process of extracting the sorted data.

  The following are typical examples of aspects of the present invention other than those described in the claims.

(1) A database processing method for outputting requested data in a computer in which a database management system for managing a database storing data is executed,
The computer includes a processor that executes the database management system, and a memory that stores the database management system,
The method
A first step of accepting a query request designated to output query results in a designated order for the requested data;
A second step of generating a query execution plan including an order of accessing a table storing the data based on the received query request;
A third step of obtaining data requested based on the query request from the database based on the generated query execution plan;
A fourth step of generating an intermediate result including the acquired data;
A fifth step of rearranging the generated intermediate results in the order specified in the query request;
A sixth step for determining for each intermediate result whether or not the order of the rearranged intermediate results is confirmed;
A database processing method comprising: a seventh step of outputting the intermediate results of which the order is determined in order from the top as the query results.

(2) The database processing method according to (1),
The query result is processed in units of records composed of one or more columns corresponding to data,
The third step acquires data for each column,
The fourth step generates the intermediate result for each record,
The sixth step is a database processing method in which it is determined that the order is not fixed when all the data corresponding to the columns constituting the record are not acquired.

(3) A database processing system including a storage device that stores data, and a computer that executes a database management system that manages the data stored in the storage device and outputs the requested data,
The calculator is
A query request receiving unit that receives a query request specified to output a query result in a specified order for the requested data;
A query execution plan generating unit that generates a query execution plan including an order of accessing the table storing the data based on the received query request;
Based on the generated query execution plan, the data requested by the query request is acquired from the storage device, and processed for each record configured by one or more columns storing the acquired data, A query execution unit that outputs a query result for the query request;
The inquiry execution unit
Get data for each column,
Generating an intermediate result including the acquired data for each record;
Reordering the generated intermediate results in the order specified in the query request;
Determine for each intermediate result whether or not the order of the sorted intermediate results is fixed;
A database processing system for outputting the intermediate results in which the order is determined in order from the top as the query results.
(4) A database management system for managing data stored in a storage device is executed, and there is a database server for outputting requested data,
A processor for executing the database management system; and a memory for storing the database management system;
The processor is
Accepting a query request specified to output query results in the specified order for the requested data;
Based on the received query request, generate a query execution plan including the order of accessing the table storing the data,
Based on the generated query execution plan, obtain the data requested by the query request from the storage device,
Generating an intermediate result including the acquired data;
Reordering the generated intermediate results in the order specified in the query request;
Determine for each intermediate result whether or not the order of the sorted intermediate results is fixed;
A database server for outputting the intermediate results whose order is determined in order from the top as the query results.

101 Database Server 102 Network 103 External Storage Device 104 Request Accepting Server 105 Network 106 Execution Server 111 Memory 112 Processor 113 Interface 121 Interface 122 Control Device 123 Storage Device 131 Application Program (AP)
132 Database management system 133 Operating system (OS)
141 Query Accepting Unit 142 Query Execution Plan Generating Unit 143 Query Executing Unit 144 Execution Task Management Unit 145 DB Buffer 146 Query Result Saving Unit 150 Execution Context Management Unit 151 Result Candidate List 152 Result Confirmation List 153 Determination Column Unacquired List 154 Determination Sequence Acquisition Completed list 160 Result order fixed part determination unit 161 Table 162 Index 170 Query result return unit 201 Memory 202 Processor 203 Interface 204 Interface 210 Data processing unit

Claims (12)

In a computer on which a database management system for managing a database storing data is executed, a database processing method for outputting requested data,
The computer includes a processor that executes the database management system, and a memory that stores the database management system,
Composing a record by one or more columns corresponding to the data,
The columns constituting the record include a sort specification column corresponding to a value that determines the specified order,
The method
A first step in which the processor receives a query request designated to output query results for the requested data in a designated order;
A second step of generating a query execution plan including an order of accessing the table storing the data based on the received query request;
A third step in which the processor obtains data requested based on the query request from the database based on the generated query execution plan;
A fourth step in which the processor generates, for each record, an intermediate result including the acquired data for each record;
The processor, the intermediate result generated in the fourth step, a first list constituted by intermediate results for which the value of the sort designation column is not obtained, the value of the sort designation column is obtained, and The second list constituted by intermediate results from which all the data corresponding to the columns constituting the record are not obtained, or the second list constituted by the intermediate results from which all the data corresponding to the columns constituting the record are obtained. An eighth step for classifying into any of the three lists;
A fifth step in which the processor rearranges the intermediate results classified in the third list among the generated intermediate results in an order specified by the query request;
A sixth step in which the processor determines, for each intermediate result, whether or not the order of the rearranged intermediate results has been determined based on the progress of processing;
A seventh step in which the processor outputs the intermediate results in which the order is determined in order from the top as the query results;
In the sixth step, when all the data corresponding to the columns constituting the record have not been acquired, the processor determines that the order has not been determined,
The sixth step includes a ninth step in which the processor determines whether there is an intermediate result classified in the first list, and the processor determines the intermediate result classified in the second list as the second result. A tenth step of obtaining the value of the sort specification column of the intermediate result with the first order as the order determination determination value when rearranged in the specified order;
In the sixth step, when there is no intermediate result classified in the first list, the processor is classified in the third list, and the order comes before the intermediate result having the order determination determination value. It is determined that the intermediate result having the value of the sort specification column is confirmed in order,
In the seventh step, the processor outputs the intermediate results classified in the third list and determined in order as the query results in order from the top. The database processing method according to claim 1,
The third step includes
The processor includes processing for obtaining the query result based on the query execution plan, and generating an execution context that is a processing unit that can be executed in parallel.
The processor obtaining the data by processing the execution context;
In the ninth step, when all execution contexts for acquiring the value of the sort specification column have been completed, the processor determines that there is no intermediate result classified in the first list. . The database processing method according to claim 2, wherein
The eighth step includes
When the acquisition of the value of the sort specification column is completed in the process of processing the execution context, the processor classifies the generated intermediate result into the second list;
And a step of classifying the generated intermediate result into the third list when the process of obtaining the query result included in the execution context is completed. The database processing method according to claim 2, wherein
The database processing method, wherein the third step includes a step in which the processor preferentially processes an execution context in which a value of the sort designation column is not acquired. The database processing method according to claim 2, wherein
In the third step, for the execution context corresponding to the intermediate result classified in the second list, the processor gives priority to the execution context whose order is first based on the value of the sort specification column of the intermediate result. A database processing method including a step of processing. The database processing method according to claim 1,
The fifth step includes the step of the processor rearranging the order of the intermediate results classified in the second list in the designated order;
The tenth step is a database processing method in which the processor uses the value of the sort designation column of the first intermediate result classified in the second list as an order determination determination value. The database processing method according to claim 1,
In the second step, a database processing method in which the processor generates a query execution plan so that a table including the sort specification column is accessed with priority. The database processing method according to claim 1,
In the sixth step, when the processor receives an output request for a query result, the database processing method determines whether or not the order of the rearranged intermediate results is fixed. The database processing method according to claim 1,
In the sixth step, a database processing method in which the processor determines whether or not the order of the rearranged intermediate results is fixed when the number of the generated intermediate results exceeds a predetermined number. A database processing system comprising: a storage device for storing data; and a computer on which a database management system for managing data stored in the storage device and outputting requested data is executed,
A record is composed of one or more columns storing the data,
The columns constituting the record include a sort specification column corresponding to a value that determines the specified order,
The calculator is
A query request receiving unit that receives a query request specified to output a query result in a specified order for the requested data;
A query execution plan generating unit that generates a query execution plan including an order of accessing the table storing the data based on the received query request;
A query execution unit that obtains data requested by the query request from the storage device based on the generated query execution plan, processes the records for each record, and outputs a query result for the query request; ,
The inquiry execution unit
Generating an intermediate result including the acquired data for each record;
The generated intermediate result corresponds to a first list constituted by intermediate results for which the value of the sort specification column has not been acquired, the value of the sort specification column is acquired, and the column constituting the record Classify either the second list composed of intermediate results from which all data has not been acquired or the third list composed of intermediate results from which all data corresponding to the columns constituting the record have been acquired. ,
Rearranging the order of the intermediate results classified in the third list into the order specified in the query request;
Determining whether there are intermediate results classified in the first list;
When the intermediate results classified in the second list are rearranged in the specified order, an order determination determination value that is the value of the sort specification column of the intermediate result that is the first in the order is acquired;
If there is no intermediate result classified in the first list, the intermediate result is classified into the third list and has the value of the sort specification column that is in the order before the intermediate result having the order determination determination value. Is determined for each intermediate result that the order has been determined,
A database processing system for outputting intermediate results classified into the third list and in which the order is determined in order from the top as the query results. The database processing system according to claim 10, wherein
The inquiry execution unit
Based on the query execution plan, an execution context that is a processing unit that can be executed in parallel, including processing for obtaining the query result, is generated.
Obtaining the data by processing the execution context;
A database processing system that determines that there are no intermediate results classified in the first list when all execution contexts for acquiring values of the sort specification column have been completed. The database processing system according to claim 11, wherein
The inquiry execution unit
When the execution context for obtaining the value of the sort specification column is completed, the generated intermediate result is classified into the first list,
A database processing system that classifies the generated intermediate results into the third list when all execution contexts included in the query execution plan are completed.

Images