Database processing method and database processing system

Provided is a database processing system including: a computer for outputting data in response to a received query request; and a storage system including a storage device for storing the data, in which: the storage device stores a plurality of partial indices indicating a storage location of the data; the data stored in the storage device is grouped; and the computer is configured to: receive the query request for the data; acquire one of the plurality of partial indices; specify, based on the query request for the data and the acquired one of the plurality of partial indices, a location at which the requested data is stored; and send a request to acquire the data stored at the specified location to the storage system. Accordingly, in the database processing system, a time period necessary to input and output the data is shortened.

CLAIM OF PRIORITY

The present application claims priority from Japanese patent application JP 2009-116517 filed on May 13, 2009, the content of which is hereby incorporated by reference into this application.

BACKGROUND OF THE INVENTION

This invention relates to a technology of processing data managed by a database using an index.

In recent years, introduction of the radio frequency identification (RFID) has rapidly increased the scale of a database for storing data such as transaction data and traceability data. Further, there has increasingly arisen a need to use such a large-scale database for business analysis and sales analysis and to apply results thereof to business. The data size is expected to exceed 100 terabytes, and be on the scale of petabytes.

Business analysis and sales analysis are conducted from various perspectives, and therefore a database processing system is required to process ad hoc queries for large-size data at high speed. JP 2007-34414 A discloses, to meet the need as described above, a database processing system capable of processing ad hoc queries for large-size data with high efficiency.

In the database processing system disclosed in JP 2007-34414 A, tasks are dynamically generated at the time of execution of a query, and the plurality of generated tasks are executed in parallel to one another. Then, in order to read data stored in a secondary storage system constituted by a plurality of disk devices such as hard disk drives (HDDs) at high speed, the plurality of tasks issue input/output requests (hereinafter, referred to as “I/O requests”) respectively.

The I/O requests issued by the tasks are executed in parallel to one another in the plurality of disk devices that constitute the secondary storage system, and hence may be processed in a short time period. Further, the multiply-issued I/O requests are scheduled so that a seek time and a rotational latency can be shortened, in consideration of the location of the head of the HDD and the location of the read request target data in the HDD as well as an issuance order of the I/O requests. Accordingly, the I/O request processing time period can further be shortened.

In addition, “Understanding the LINUX KERNEL, THIRD EDITION” authored by Daniel P. Bovet et al., published by O'Reilly Media, Inc., pp. 560-598 discloses a technology in which a database processing system or an operating system queues a plurality of I/O requests and schedules the queued I/O requests, to shorten an I/O request processing time period. Specifically, the database processing system or the operating system specifies an access destination logical block address (LBA) for each of the plurality of queued I/O requests, and changes an output order so that the seek time and the rotational latency of the HDD can be shortened.

SUMMARY OF THE INVENTION

In the database processing system, in a case of search for specific data from among data stored in a table, an index is created in order to reduce the number of I/O requests issued along with the search processing and to shorten a search time period. However, in a case where a large amount of data is handled, even if an index is used for search, a considerable number of I/O requests are issued.

In order to shorten the I/O request processing time period in a case where I/O requests are queued and scheduled, it is effective to queue all I/O requests necessary for the search processing and to schedule all the queued I/O requests. However, it takes a long time period to queue all the I/O requests, and further takes a considerably long time period to schedule the considerable number of I/O requests.

Meanwhile, instead of scheduling all the I/O requests necessary for the search processing, there is disclosed a technology of scheduling only a part of I/O requests repeatedly. For example, there is a method such that a part of I/O requests are issued from a database processing system and are accumulated in a queue provided by a disk device, then all the accumulated I/O requests are scheduled. However, in this method, only a part of I/O requests are focused as a target of the scheduling processing, and hence the entire I/O request processing time period cannot necessarily be shortened.

This invention has been made in view of the problems described above, and it is therefore an object of this invention to shorten a time period necessary to process I/O requests in a manner in which a database processing system controls an issuance order of the I/O requests.

The representative aspects of this invention are as follows. That is, there is provided a database processing method used in a database processing system having: a computer for outputting data in response to a received query request; and a storage system for storing the data to be output by the computer, the computer having: a first interface coupled to the storage system; a processor coupled to the first interface; and a memory coupled to the processor, the storage system having: a second interface coupled to the computer; a controller coupled to the second interface; and a storage device for storing the data, the storage device storing an index indicating a storage location of the data, the data stored in the storage device being grouped, based on the storage location of the data, into a plurality of data groups, the index comprising including a plurality of partial indices, the plurality of partial indices each indicating the storage location of the data included in one of the plurality of the data groups, the database processing method including the steps of: receiving, by the processor, the query request for the data stored in the storage device; acquiring, by the processor, one of the plurality of partial indices from the index; specifying, by the processor, based on the query request for the data and the acquired one of the plurality of partial indices, a location at which the requested data is stored; and sending, by the processor, a request to acquire the data stored at the specified location to the storage system.

According to the aspect of this invention, the request to acquire the data is sent to the storage system for each of the plurality of partial indices created based on the storage location of the data, and accordingly, a scheduling function provided by the storage system is utilized, to thereby allow a time period necessary to input and output the data to be shortened.

DETAILED DESCRIPTION OF THE PREFERRED EMBODIMENTS

Hereinbelow, referring to the accompanying drawings, embodiments of this invention are described.

First Embodiment

FIG. 1is a block diagram illustrating a configuration of a computer system according to a first embodiment of this invention.

The computer system according to the embodiments of this invention includes a database server100, an external storage system for storage150, and an external storage system for task160. A database management system operates in the database server100. The external storage system for storage150stores data managed by the database management system. The external storage system for task160temporarily stores data generated in the course of processings performed by the database management system.

The database server100, the external storage system for storage150, and the external storage system for task160are coupled to one another via a network170. For example, the network170is a storage area network (SAN) to which the fibre channel (FC) protocol is applied, but the network170may be any other type of network than the above. For example, the network170may be an internet protocol (IP) network, via which the database server100, the external storage system for storage150, and the external storage system for task160communicate with one another in conformity to the internet small computer system interface (iSCSI) protocol.

The external storage system for storage150includes an interface151, a controller152, and a storage device155. The external storage system for storage150reads and writes data stored in the storage device155in response to an input/output (I/O) request received from the database server100.

The interface151is coupled to the network170. The controller152processes the I/O request sent from the database server100.

The storage device155stores data which is to be read and written by the database server100. Specifically, the storage device155is a hard disk drive (HDD), an optical disk drive, a semiconductor storage device, or other such storage device. Further, the storage device155stores a table154and an index153serving as data to be processed by the database server100.

It should be noted thatFIG. 1illustrates three storage devices155, but an arbitrary number of storage devices155may be provided in the external storage system for storage150. Alternatively, a plurality of storage devices155may be provided to form a disk array.

In consideration of a location of a read head of the HDD and a storage location of data which is the target of the read request, the external storage system for storage150has a function of scheduling I/O requests for data so that a seek time and a rotational latency can be shortened.

Similarly to the external storage system for storage150, the external storage system for task160includes an interface161, a controller162, and a storage device163. Functions of the interface161and the controller162are the same as those of the interface151and the controller152of the external storage system for storage150. The storage device163temporarily stores data necessary for processings performed by the database server100.

The database server100includes a memory101, a processor102, and an interface103.

The memory101stores programs executed by the processor102and data necessary to execute the programs. The programs and data stored in the memory101are described later.

The processor102executes the programs stored in the memory101. The interface103is an interface for coupling the database server100to the network170. For example, in a case where the network170is a storage area network (SAN), a host bus adapter (HBA) is employed as the interface103.

The memory101stores an application program104, a database management system105, and an operating system106. The application program104issues a query for data to the database management system105, and receives a query result therefrom.

The database management system105processes a query request for data issued from the application program104, and sends a query result as a response. Specifically, based on the received query request, the database management system105reads and writes the data stored in the external storage system for storage150or the external storage system for task160via the operating system106if necessary.

The operating system106receives a request from the database management system105, and sends, to the external storage system for storage150or the external storage system for task160, a read/write request for the data stored therein. Further, the operating system106manages the processor102and the memory101of the database server100.

In the first embodiment of this invention, the same computer executes the application program104as well as the database management system105. Alternatively, the application program104may be executed by another computer coupled to the database server100via the network170.

The database management system105extracts and processes the data stored in the external storage system for storage150in response to a given query request, and sends a query result as a response. In a relational database management system (RDBMS), which is based on a relational model, data called “record” is stored in the table154, and the index153, which has a data structure for accessing the record with a small number of I/O requests, is provided thereto. A B-tree, a hash, or other data structure is employed as the data structure of the index153. The query for data is written in the structured query language (SQL).

In the first embodiment of this invention, the database management system105stores the table154and the index153in the external storage system for storage150coupled to the database management system105via the network170. Alternatively, the database management system105may store the table154and the index153in a storage device provided in the database server100.

The database management system105includes a query execution control module110and a partial index creation module120. The query execution control module110receives a query request issued from the application program104, and processes the query to send a result thereof as a response. The partial index creation module120creates a partial index associated with a group of data pieces having locality, based on storage locations of data pieces. As described later, the locality means that data pieces are stored within a predetermined range of the storage device. The predetermined range may be set based on physical addresses or alternatively on a track or sector basis.

The partial index creation module120includes an index data acquisition module121, an index information file storage area122, an index creation module123, and a partial index creation management module130.

The index data acquisition module121acquires data pieces necessary to create an index from a group of records stored in the table. The index information file storage area122is an area for storing the acquired data pieces as a file.

The index creation module123creates an index based on the data pieces acquired by the index data acquisition module121or the like. The index creation module123includes a work area for index creation124for temporarily holding data generated in the course of index creation.

The partial index creation management module130includes an external storage system structural information acquisition module131and a locality determination criterion designation reception module132. The external storage system structural information acquisition module131acquires structural information of the external storage system for storage150that stores the table154and the index153, and holds the acquired structural information. The locality determination criterion designation reception module132receives an input of a locality determination criterion designated by a user.

It should be noted that the locality determination criterion is input by the user in the first embodiment of this invention, but alternatively, may be set automatically based on a system environment such as a capacity of the memory101. A method of automatically setting the locality determination criterion is described in a fourth embodiment.

It should also be noted that, in a case where the amount of data stored in the index information file storage area122and the work area for index creation124has exceeded the capacity of the memory101, the data is temporarily stored in the external storage system for task160, and is read again to the memory101if necessary.

The query execution control module110includes a query reception module111, a query execution plan generation module112, a query execution module113, a DB buffer114, and an executed task management module115.

The query reception module111receives a query request issued from the application program104.

The query execution plan generation module112generates procedures of processing the received query (query execution plan). The query execution plan refers to processing procedures obtained by combining database operations necessary to generate a query result.

The query execution module113dynamically generates tasks according to the generated query execution plan, and executes the plurality of tasks thus generated in parallel to one another. The query execution module113is provided with basic database operations for generating a query result.

The DB buffer114temporarily stores, in order to process queries at high speed, data used in the course of the processing.

The executed task management module115manages tasks that have been executed by the query execution module113. The executed task management module115includes a partial index search control module116. The partial index search control module116controls a search processing performed by using partial indices.

As described above, according to the first embodiment of this invention, a plurality of tasks are generated and the generated tasks are executed in parallel to one another, to thereby process query requests at high speed. Further, an I/O request for data is issued independently among the tasks. At this time, storage locations of data pieces which are targets of input and output are controlled so that I/O requests for those data pieces can be issued locally, to thereby utilize the scheduling function provided to the external storage system for storage150with more efficiency.

Hereinbelow, description is given of processing procedures performed by the database management system105according to the first embodiment of this invention.FIGS. 2A and 2Billustrate procedures of creating partial indices, andFIG. 3illustrates search procedures performed by using the partial indices.FIG. 4illustrates an example of the structural information of the external storage system for storage150, the structural information being used for determining locality necessary to create partial indices.FIG. 5illustrates a sales history table500as an example of data for describing the procedures of creating partial indices.FIG. 6illustrates an example of a created index information file600. First, description is given of the sales history table500serving as a source of partial index creation according to the first embodiment of this invention.

FIG. 5is a diagram illustrating an example of the sales history table500used for creating partial indices according to the first embodiment of this invention.

The sales history table500is an example of a history of sold items in a shop, and is also an example of the table154stored in the external storage system for storage150. The sales history table500contains a sales ID501, a customer ID502, an item ID503, and a quantity504.

The sales ID501is an identifier for identifying a history of a sold item. The customer ID502is an identifier of a customer who has purchased the item. The item ID503is an identifier of the purchased item. The quantity504is a quantity of the purchased item identified by the item ID503.

Hereinbelow, description is given of the procedures of creating partial indices based on the item ID503of the sales history table500illustrated inFIG. 5.

FIG. 2Ais a flow chart illustrating procedures of creating an index according to the first embodiment of this invention.

This processing is executed by the processor102of the database server100executing the partial index creation module120.

First, the processor102executes the external storage system structural information acquisition module131to acquire the structural information of the external storage system for storage150(Step201).FIG. 4illustrates an example of the structural information acquired in the processing of Step201.

FIG. 4is a diagram illustrating a mapping table400showing a mapping between logical addresses and physical addresses, which is an example of the structural information of the external storage system for storage150according to the first embodiment of this invention.

In the first embodiment of this invention, the external storage system for storage150includes three HDDs each providing a storage area in 1-kilobyte stripes from the head. It should be noted that this invention is not limited to the structure of the storage area described herein, and the storage area only needs to be structured by one or more storage devices.

The mapping table400contains a logical address401recognized by the database server100, and a physical address402associated with the logical address401. The physical address402contains an HDD number, which is identification information of an HDD, and a cylinder/head/sector (CHS) of the HDD.

The structural information may be acquired from the external storage system for storage150by executing the external storage system structural information acquisition module131, but alternatively, if the external storage system for storage150has a management command for outputting the structural information, such a management command as described above may be used for acquiring the structural information. Still alternatively, a database designer who has made settings to the external storage system for storage150may create a file containing the mapping table400in advance, which may be read by the external storage system structural information acquisition module131. Further, an administrator may input the structural information to the external storage system structural information acquisition module131via a user interface such as a graphical user interface (GUI). Still further, the structural information may be acquired again at an arbitrary timing, to thereby create a mapping table400again.

The procedures of creating partial indices illustrated inFIG. 2Aare described again.

Subsequently, the processor102reads one page of records of the sales history table500. Then, the processor102executes the index data acquisition module121to extract index information pieces each formed by a pair of an item ID of the record and a pointer thereto, which are necessary to create an index (Step203).

It should be noted that the first embodiment of this invention describes the method of creating the index153with respect to data that has already been stored in the table154of the storage device155, but the index153may be created in parallel to a processing of inserting data to the table154. In this case, the index information is extracted in parallel to the processing of inserting data to the table154.

The processor102determines whether or not the page thus read is the last page of the sales history table500(Step204). In a case where the page thus read is not the last page of the sales history table500(the result of Step204is “No”), the processor102then determines whether or not the records from which the index information pieces have been extracted have locality in the external storage system for storage150with respect to a group of records contained in the index information file600(Step205).

The criterion for determining whether or not the group of records contained in the index information file600and the records from which the index information pieces have been extracted have locality is set based on an instruction received from the user through the locality determination criterion designation reception module132. In the first embodiment of this invention, the records having locality are those stored within a designated range of the area of the storage device155. In the processing of Step205, the processor102determines whether or not the storage locations of the records from which the index information pieces have been extracted are included in a storage area corresponding to that of the group of records contained in the index information file600. The processor102may determine whether or not the storage area after addition of the records from which the index information pieces have been extracted to the group of records contained in the index information file600under creation falls within the designated range.

Specifically, the processor102determines the locality by associating, according to the mapping table400stored in the external storage system structural information acquisition module131, logical addresses of the records recognized by the database management system105with physical addresses of the storage device155, respectively. In other words, the processor102determines whether or not the records are stored physically close to one another. It should be noted that, as described above, any other criterion than the address may be designated as the locality determination criterion. There is provided, as another example of the locality determination criterion, a movement distance of the head of each HDD falling within a range of a predetermined threshold value or less. Further, the processor102may determine the locality based on logical block addressing (LBA) of the storage locations of the records. In this case, the LBA scheme may be employed for the physical address402of the mapping table400.

FIG. 2Bis a flow chart illustrating procedures of determining locality according to the first embodiment of this invention.

This processing is executed in the processing of Step205of the flow chart illustrated inFIG. 2A.

The processor102specifies the storage locations of the records from which the index information pieces have been extracted. Then, based on the mapping table400illustrated inFIG. 4, the processor102determines whether or not the group of records to which the records from which the index information pieces have been extracted are added are stored in a storage area of a designated size (Step251).

In a case where the group of records are stored in the storage area of the designated size (the result of Step251is “Yes”), the processor102determines that the group of records after addition of the index information pieces have locality (Step252).

On the other hand, in a case where the group of records are not stored in the storage area of the designated size (the result of Step251is “No”), the processor102determines that the group of records after addition of the index information pieces do not have locality (Step253).

The procedures of creating partial indices illustrated inFIG. 2Aare described again.

In a case where the records from which the index information pieces have been extracted have locality with respect to the group of records contained in the index information file600(the result of Step205is “Yes”), the processor102adds the extracted index information pieces to the index information file600(Step211).

In a case where the group of records contained in the index information file600and the records from which the index information pieces have been extracted do not have locality (the result of Step205is “No”), the processor102newly sets another index information file600as an output destination of the index information pieces, and outputs the extracted index information pieces to the another index information file600(Step206).

Further, the processor102newly generates a thread for executing index creation, and creates a partial index based on the switched index information file600(Step207). In the first embodiment of this invention, in order to shorten an index creation time period, the processor102newly generates a thread for creating a partial index, and executes the processing of creating the index information file600and the processing of creating a partial index in parallel to each other. It should be noted that all the processings may be executed in one thread in turn.

When the processor102has finished the processing of Step207, the processor102executes the processings of Step203and subsequent steps with respect to the subsequent records.

In a case where the page thus read is the last page of the sales history table500(the result of Step204is “Yes”), the processor102adds the extracted index information pieces to the index information file600(Step208). Further, the processor102executes the processing of creating a partial index in another thread than that for the processing of extracting the index information (Step209).

Through the processings described above, the index information file having locality and the partial index associated therewith are created.FIG. 6illustrates an example of the index information file in which index information pieces of records having locality are stored.

FIG. 6is a diagram illustrating an example of the index information file600according to the first embodiment of this invention.

As the index information file600,FIG. 6illustrates three files created for each group of records having locality. In the first embodiment of this invention, as described above, the index information file600is created in association with the group of records, in which records stored within a predetermined range of the storage area have locality. Further, each of the index information files600is created so that index information to be stored therein is not the same as index information stored in another index information file600.

Further description is given of a relation between the created partial indices and the sales history table500, which is a source of the partial index creation.

FIG. 7is an explanatory diagram illustrating a relation between an index700and the sales history table500according to the first embodiment of this invention.

In the first embodiment of this invention, the three index information files600illustrated inFIG. 6are created through the procedures illustrated inFIGS. 2A and 2B, and the index700containing partial indices001to003(702to704) associated with the three index information files600, respectively, is created. As described above, the partial indices001to003(702to704) are created so as not to contain the same record thereamong. Further, in each partial index, records to be stored are sorted by items, which base the index (item IDs).

Lastly, description is given of procedures for the search processing performed by using the index700containing a plurality of partial indices.

As described above, the search processing is executed by the processor102executing the query execution control module110.

As described above, the processor102dynamically generates a plurality of tasks upon the execution of the search processing. The generated tasks are managed by the executed task management module115. I/O requests are issued multiply in the generated tasks, respectively, from the database server100to the external storage system for storage150. On the above-mentioned premise, referring toFIG. 3, description is given below of procedures for search performed by using the index700.

FIG. 3is a flow chart illustrating procedures for index search according to the first embodiment of this invention.

First, the processor102initializes a value N of a counter that indicates a partial index to be used for search. Specifically, the processor102sets the value N of the counter to “1” (Step301).

Subsequently, the processor102uses the partial index search control module116to execute search using an N-th partial index contained in the index700(Step302). At this time, a plurality of tasks of acquiring data associated with the N-th partial index are generated and executed for the search intensively in parallel to one another.

When the processor102has finished the search using the N-th partial index, the processor102determines whether or not the N-th partial index is the last partial index (Step303). In a case where the N-th partial index is the last partial index (the result of Step303is “Yes”), the processor102ends the search processing.

On the other hand, in a case where the N-th partial index is not the last partial index (the result of Step303is “No”), the processor102updates the value N of the counter to “N+1” (Step304), and executes the search using an (N+1)th partial index in a similar manner to the above.

As described above, according to the first embodiment of this invention, upon the execution of the search using each partial index associated with the group of records having locality, I/O requests for data pieces stored at local locations of the storage device are issued intensively. Accordingly, an I/O request processing time period can be shortened owing to the function of scheduling I/O requests, which is provided to the external storage system for storage150.

Further, according to the first embodiment of this invention, the index can be created on a partial index basis in a parallel manner, and accordingly the index creation time period can also be shortened.

Second Embodiment

In the first embodiment of this invention, data pieces of the table154are stored in a contiguous storage area. In a second embodiment, in contrast, description is given of a case where data pieces of the table154are not stored in the contiguous storage area.

It should be noted that differences from the first embodiment are mainly described in the second embodiment and subsequent embodiments, and components and processings common to those of the first embodiment are denoted by the same reference symbols, to thereby omit description thereof.

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

The second embodiment of this invention is different from the first embodiment in the partial index creation module120. Specifically, the partial index creation module120according to the second embodiment includes a disk-based last address storage module833in addition to the components of the first embodiment.

The disk-based last address storage module833stores, on an HDD basis, the last address of a record which is written to the index information file600and is associated with the index thereof. The disk-based last address storage module833includes a disk-based last address storage table1100that holds an address of data that has been read last on an HDD basis. The disk-based last address storage table1100is described later in detail referring toFIG. 11.

Other components of the second embodiment are similar to those of the first embodiment, and the second embodiment is different from the first embodiment in procedures of creating an index and procedures of determining locality. Referring toFIGS. 9A and 9B, the respective procedures are described.

FIG. 9Ais a flow chart illustrating procedures of creating an index according to the second embodiment of this invention.

This processing is executed by the processor102of the database server100executing the partial index creation module120.

Similarly to the first embodiment, the processor102first executes the external storage system structural information acquisition module131to acquire the structural information of the external storage system for storage150(Step201).FIG. 10illustrates the structural information acquired in the processing of Step201.

FIG. 10is a diagram illustrating a mapping table1000showing a mapping between logical addresses and physical addresses, which is an example of the structural information of the external storage system for storage150according to the second embodiment of this invention. The mapping table1000has the same structure as the mapping table400of the first embodiment.

In the second embodiment of this invention, similarly to the first embodiment, the external storage system for storage150includes three HDDs. However, unlike the first embodiment, records are not always stored in a contiguous storage area. Referring toFIG. 10, in an HDD having an HDD number “01”, records are stored in an area including addresses “000000 to 0000ff”, and subsequently, stored in an area including addresses “005000 to 0050ff”.

The procedures of creating partial indices illustrated inFIG. 9Aare described again.

Subsequently, similarly to the first embodiment, the processor102reads one page of records of the sales history table500. Then, the processor102executes the index data acquisition module121to extract index information pieces each formed by a pair of an item ID of each of the records and an address thereof, which are necessary to create an index (Step203).

The processor102determines whether or not the page thus read is the last page of the sales history table500(Step204). In a case where the page thus read is not the last page of the sales history table500(the result of Step204is “No”), the processor102then determines whether or not the records from which the index information pieces have been extracted have locality in the external storage system for storage150with respect to the group of records contained in the index information file600(Step205).

In the second embodiment of this invention, in addition to the criterion that the group of records are stored in an area of the storage device155within the designated range, there is further provided a criterion that storage locations of adjacent records are not separate from each other by a designated value or more to determine that the group of records have locality.

FIG. 9Bis a flow chart illustrating procedures of determining locality according to the second embodiment of this invention.

The processor102specifies the storage locations of the records from which the index information pieces have been extracted. Then, the processor102determines whether or not the group of records to which the records from which the index information pieces have been extracted are added are stored in a storage area of a designated size (Step251).

In a case where the group of records are stored in the storage area of the designated size (the result of Step251is “Yes”), the processor102further determines whether the physical address of each table data and the last address managed on a disk basis are separate from each other by a designated value or more (Step953).FIG. 11illustrates an example of the disk-based last address storage table1100that stores the last address managed on a disk basis.

FIG. 11is a diagram illustrating an example of the disk-based last address storage table1100according to the second embodiment of this invention.

In the disk-based last address storage table1100, an address of a record that has been read last is stored on an HDD basis. The disk-based last address storage table1100contains an HDD number1101for identifying an HDD, and a last address1102in which an address associated with a record that has been read last is stored.

In a case where the physical address of each table data and the last address managed on a disk basis are not separate from each other by the designated value or more (the result of Step953is “No”), the processor102determines that the group of records after addition of the index information pieces have locality (Step252).

On the other hand, in a case where the group of records are not stored in the storage area of the designated size (the result of Step251is “No”), or in a case where the physical address of each table data and the last address managed on a disk basis are separate from each other by the designated value or more (the result of Step953is “Yes”), the processor102determines that the group of records after addition of the index information pieces do not have locality (Step253).

The procedures of creating partial indices illustrated inFIG. 9Aare described again.

In a case where the records from which the index information pieces have been extracted have locality with respect to the group of records contained in the index information file600(the result of Step205is “Yes”), the processor102adds the extracted index information pieces to the index information file600. Further, the processor102acquires, based on a logical address of a record associated with an index of the index information file600to which the record is to be added, a physical address on the HDD according to the mapping table1000illustrated inFIG. 10, and updates the disk-based last address storage table1100(Step912).

In a case where the group of records contained in the index information file600and the records from which the index information pieces have been extracted do not have locality (the result of Step205is “No”), the processor102newly sets another index information file600as an output destination of the index information pieces, and outputs the extracted index information pieces to the another index information file600(Step206).

The processor102acquires, based on a logical address of a record associated with an index of the index information file600to which the record is to be added, a physical address on the HDD according to the mapping table1000illustrated inFIG. 10, and updates the disk-based last address storage table1100(Step907). Subsequently, the processor102newly generates a thread for executing index creation, and creates a partial index based on the switched index information file600(Step207).

When the processor102has finished the processing of Step207, the processor102executes the processings of Step203and subsequent steps with respect to the subsequent records.

In a case where the page thus read is the last page of the sales history table500(the result of Step204is “Yes”), the processor102adds the extracted index information pieces to the index information file600(Step208). Further, the processor102executes the processing of creating a partial index in another thread than that for the processing of extracting the index information (Step209).

According to the second embodiment of this invention, in the case where the storage area of the HDD that stores the table is not contiguous as in the case of the addresses “000000 to 0000ff” and “005000 to 0050ff” illustrated inFIG. 10, the boundary therebetween may trigger creation of another partial index. Accordingly, even in the case where table data pieces are not stored in the contiguous storage area, the effect similar to that of the first embodiment can be obtained, and the I/O request processing time period can be shortened owing to the function of scheduling I/O requests, which is provided to the external storage system for storage150.

Third Embodiment

In a third embodiment of this invention, in addition to the criterion regarding the structural information of the external storage system for storage150, there is further provided a criterion that the processing of creating a partial index can be executed on the memory of the computer to determine locality. With this configuration, the external storage system for task160does not need to be accessed at the time of index creation, and accordingly, the index creation time period can be shortened.

A computer system according to the third embodiment of this invention has a configuration obtained by excluding the external storage system for task160from the configuration of the computer system according to the first embodiment. It should be noted that it is at the time of index creation that the external storage system for task160is unnecessary. Hence, in a case where the external storage system for task160is assumed to be necessary at the time of search execution or other such processing, the same configuration as that of the computer system according to the first embodiment may be employed as the configuration of the computer system according to the third embodiment.

The third embodiment is basically the same as the first embodiment in procedures of creating an index, and is different from the first embodiment in procedures of determining locality. Description is given below of the processing of determining locality while simply describing the procedures of creating an index.

The procedures of creating an index according to the third embodiment of this invention are similar to those of the first embodiment. Therefore, referring to the flow chart illustrated inFIG. 2A, which shows the procedures of creating an index according to the first embodiment, the procedures of creating an index according to the third embodiment are described.

First, the processor102uses the external storage system structural information acquisition module131to acquire the structural information of the external storage system for storage150(Step201). Then, the processor102reads one page of records of the sales history table500, and extracts index information pieces (Step203).

The processor102determines whether or not the page thus read is the last page of the sales history table500(Step204). In a case where the page thus read is not the last page of the sales history table500(the result of Step204is “No”), the processor102then determines whether or not the records from which the index information pieces have been extracted have locality (Step205). Referring toFIG. 12, the procedures of determining locality are described below.

FIG. 12is a flow chart illustrating procedures of determining locality according to the third embodiment of this invention.

The processor102specifies the storage locations of the records from which the index information pieces have been extracted. Then, the processor102determines whether or not the group of records to which the records from which the index information pieces have been extracted are added are stored in a storage area of a designated size (Step251).

In a large-scale database system, when an extremely large number of records are stored in the table154, there is a risk that the size of the index information file600that holds index information becomes larger than the size of the index information file storage area122.

In this case, in the first embodiment, data that has overflowed is appropriately stored in the external storage system for task160. However, as compared with the case where access is made only to data stored in the memory to execute processings, a longer processing time period is required in the case where access is made to data stored in the external storage system to execute processings. Therefore, in the third embodiment, it is determined that the group of records do not have locality at the time when the index information file600can no longer be stored in the index information file storage area122.

In a case where the group of records are stored in the storage area of the designated size (the result of Step251is “Yes”), the processor102further determines whether or not the index information file600can be stored in the memory101(Step1453). In other words, the processor102determines whether or not the size of the index information file600is smaller than the size of the index information file storage area122. In a case where the index information file600can be stored in the memory101(the result of Step1453is “Yes”), the processor102determines that the group of records after addition of the records from which the index information pieces have been extracted have locality (Step252).

On the other hand, in a case where the group of records are not stored in the storage area of the designated size (the result of Step251is “No”), or in a case where an index information piece is newly added to the index information file600and hence the size of the index information file600so increases that the index information file600cannot be held in the memory101(the result of Step1453is “No”), the processor102determines that the group of records after addition of the index information pieces do not have locality (Step253).

The procedures of creating partial indices illustrated inFIG. 2Aare described again.

In a case where the records from which the index information pieces have been extracted have locality (the result of Step205is “Yes”), the processor102adds the extracted index information pieces to the index information file600(Step211).

On the other hand, in a case where the records from which the index information pieces have been extracted do not have locality (the result of Step205is “No”), the processor102newly sets another index information file600as an output destination of the index information pieces, and outputs the extracted index information pieces to the another index information file600(Step206). After that, the processor102newly generates a thread for creating a partial index, and creates a partial index based on the switched index information file600(Step207).

When the processor102has finished the processing of Step207, the processor102executes the processings of Step203and subsequent steps with respect to the subsequent records.

In a case where the page thus read is the last page of the sales history table500(the result of Step204is “Yes”), the processor102adds the extracted index information pieces to the index information file600(Step208). Further, the processor102creates a partial index in another thread than that for the processing of extracting the index information (Step209).

By creating partial indices through the procedures described above, there is no need to store, in the external storage system for task160, data that has exceeded the capacity of the memory101. In this manner, access to the external storage system is no longer necessary, and accordingly, the time period necessary to create partial indices can be shortened.

The processing of creating an index includes a processing of sorting data pieces contained in the index information file600in an order of key values. In executing the sorting processing, the data pieces need to be stored in the memory101temporarily. In this case, if the memory101is short in capacity thereof, there arises a need to input and output data to and from the external storage system for task160in order to execute the sorting processing. Therefore, the size of the index information file600used for determining locality is set in consideration of the size of the temporary data to be output.

According to the third embodiment of this invention, the index information file600can be stored in the memory101, and hence partial indices can be created without inputting and outputting data to and from the external storage system for task160. In other words, the size of the index information file600is set so that partial indices can be created on memory, to thereby reduce overhead due to the input and output of data to and from the external storage system for task160, and to shorten the time period necessary to create an index.

Fourth Embodiment

In the first to third embodiments of this invention, the locality determination criterion of the group of records is set by the user's designation. In a fourth embodiment, the locality determination criterion of the group of records is automatically decided by the database management system105based on a system environment and the like.

In the fourth embodiment of this invention, the partial index creation management module130of the first embodiment includes a locality determination criterion creation module instead of the locality determination criterion designation reception module132.

The locality determination criterion creation module references the structural information of the external storage system for storage150, load information of the network170and the interface103, information that may be acquired by the operating system106, and the like, to thereby generate a locality determination criterion. Based on the created criterion, partial indices are created in a similar manner to the procedures described in the first embodiment.

Examples of the method of generating a locality determination criterion includes deciding a locality determination criterion based on a size of the striped storage area.

Alternatively, the size of the storage area, with which access to the external storage system for task160is unnecessary when creating the index information file600, is acquired, and the size may be set as a locality determination criterion. In this case, the acquired size may be calculated based on an available memory capacity that is acquired from the operating system106or the like, and may be set as a size of the index information file storage area122. By setting the acquired size as a size of the storage area in which the group of records are stored, the effect similar to that of the third embodiment of this invention can be obtained.

Further, based on the mapping table showing the mapping between the logical addresses and the physical addresses, it is determined whether or not the storage areas having the same HDD number are contiguous. In a case where the storage areas are not contiguous, the interval between the storage areas in terms of the physical addresses is acquired. Based on the acquired interval between the storage areas, by, for example, setting the value designated in the processing of Step953of the second embodiment, which is illustrated inFIG. 9B, the effect similar to that of the second embodiment can be obtained.

According to the fourth embodiment of this invention, the locality determination criterion can automatically be set without the user's designation. Accordingly, the load on the user is reduced, and moreover, when the system environment is changed as in the case of extension of the external storage system over a long-term operation, a locality determination criterion adapted to such a change in system environment can be applied.

Fifth Embodiment

In a fifth embodiment of this invention, description is given of a method of executing the index search in a case where data pieces of the table154are divided to be stored in a plurality of storage devices.

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

In the fifth embodiment of this invention, the executed task management module115according to the first embodiment includes a partial index storage location management module1517. Other components of the fifth embodiment are similar to those of the first embodiment.

The partial index storage location management module1517includes a partial index storage location management table1900that holds numbers of the storage devices155that store the group of records contained in each partial index. The partial index storage location management module1517creates and updates the partial index storage location management table1900, for example. The partial index storage location management table1900is described later in detail referring toFIG. 17.

A mapping table according to the fifth embodiment of this invention has the same structure as the mapping table400according to the first embodiment. As illustrated inFIG. 4, data pieces of the table154are stored across the three HDDs.

FIG. 14is an explanatory diagram illustrating a relation between an index1700and the sales history table500according to the fifth embodiment of this invention.

Referring toFIG. 4, a storage area including logical addresses “0x00000000” to “0x00000fff” is provided by a storage device155having an HDD number “01”, and a storage area including logical addresses “0x00001000” to “0x00001fff” is provided by a storage device155having an HDD number “02”. Hence, data pieces corresponding to records associated with a partial index003are stored in the storage devices155having the HDD numbers “01” and “02”.

FIG. 17is a diagram illustrating an example of the partial index storage location management table1900held by the partial index storage location management module1517according to the fifth embodiment of this invention.

The partial index storage location management table1900shows a mapping between the partial index and the HDD, and holds an identifier of the HDD that stores the partial index. The partial index storage location management table1900contains a partial index number1901and an HDD number1902. The partial index number1901is a number for identifying a partial index. The HDD number1902is a number for identifying an HDD.

In the fifth embodiment of this invention, upon execution of a query, the query execution control module110is used to dynamically generate a plurality of tasks. The generated tasks are managed by the executed task management module115. Then, I/O requests are issued multiply in the tasks, respectively, from the database server100to the external storage system for storage150.

FIG. 15is a flow chart illustrating procedures for index search according to the fifth embodiment of this invention.

First, the processor102determines whether or not the partial index storage location management table1900has already been created (Step1806). In a case where the partial index storage location management table1900has not been created yet (the result of Step1806is “No”), the processor102newly creates a partial index storage location management table1900(Step1807).

Subsequently, the processor102references the partial index storage location management table1900, and selects one partial index containing stored records for each storage device (Step1801). When referencing the partial index storage location management table1900illustrated inFIG. 17, the processor102selects a partial index001containing records stored in the HDD having the HDD number1902of “01”, and the partial index003containing records stored in the HDD having the HDD number1902of “02”.

The processor102generates a plurality of tasks for each of the selected partial indices, and starts search in the generated tasks (Step1802).

After that, the processor102determines whether or not the search has been started using all the partial indices (Step1803). In a case where the search has been started using all the partial indices (the result of Step1803is “Yes”), the processor102ends the index search.

In a case where there remains a partial index with which the search has not been started yet (the result of Step1803is “No”), the processor102selects a partial index which contains stored records for each storage device and with which the search has not been started yet (Step1804). Then, the processor102generates a plurality of tasks for the selected partial index, and starts the search in the generated tasks (Step1802). When referencing the partial index storage location management table1900illustrated inFIG. 17, the processor102selects a partial index002which contains records stored in the HDD having the HDD number1902of “01” and with which the search has not been started yet, and starts the search. The above-mentioned processing is repeated until the search is started using all the partial indices.

Next, description is given of a processing of creating the partial index storage location management table1900.

FIG. 16is a flow chart illustrating procedures of creating the partial index storage location management table1900according to the fifth embodiment of this invention.

This processing is executed by executing the partial index storage location management module1517.

First, the processor102initializes the counter that indicates a partial index to be processed. Specifically, the processor102sets the value N of the counter to “1” (Step1851).

The processor102acquires a number of a storage device155that stores records associated with an N-th partial index. Specifically, the processor102specifies logical addresses of storage locations based on record pointers associated with the partial index, and further, references the mapping table400acquired using the external storage system structural information acquisition module131, which is illustrated inFIG. 4, to thereby acquire the number for identifying the HDD that stores the group of records contained in the partial index. Then, the processor102stores the acquired number for identifying the HDD and the number for identifying the partial index in the partial index storage location management table1900(Step1852).

When the processor102has finished the processing with respect to the N-th partial index, the processor102determines whether or not the N-th partial index is the last partial index (Step1853). In a case where the N-th partial index is the last partial index (the result of Step1853is “Yes”), the processor102ends the processing of creating the partial index storage location management table1900.

On the other hand, in a case where the N-th partial index is not the last partial index (the result of Step1853is “No”), the processor102updates the value N of the counter to “N+1” (Step1854), and processes an (N+1)th partial index in a similar manner to the above.

It should be noted that the fifth embodiment of this invention describes the procedures of creating the partial index storage location management table1900with respect to the partial indices that have already been created, but the partial index storage location management table1900may be created in parallel to the processing of creating partial indices.

According to the fifth embodiment of this invention, after the search is executed using each partial index, I/O requests are issued intensively so that the storage locations have locality in each storage device, and further, in the case where data pieces of the table154are stored across a plurality of storage devices, I/O requests are issued in a parallel manner to the storage devices, respectively. Accordingly, the I/O requests are processed in parallel to one another in the storage devices, respectively, and hence the I/O request processing time period can further be shortened.

Sixth Embodiment

In a sixth embodiment of this invention, description is given of a processing of creating, when data is added to the table, an index associated with the added data. It should be noted that, in the following, description is given of a method of creating, after data is added to the table, an index associated with the added data, but the processing of creating an index associated with the added data may be executed in parallel to the processing of inserting additional data to the table.

A computer system according to the sixth embodiment of this invention has a configuration similar to that of the first embodiment, which is illustrated inFIG. 1. Further, the index structure of the sixth embodiment is also similar to that of the first embodiment. Hereinbelow, description is given of the processing of creating, when data is added to the table, an index associated with the added data.

First, the processor102determines whether or not the external storage system for storage150has any area for storing additional data. In a case where the external storage system for storage150runs short of the area for storing additional data, another storage device is added to extend the storage area, and the processor102uses the external storage system structural information acquisition module131to acquire and store the structural information of the external storage system for storage150which has the added storage area.

Subsequently, the processor102decides whether to create, when data is added to the table, an index associated with the added data as a new partial index, or to add an index associated with a part of the added data to the latest existing partial index, and then create an index associated with the remaining data as a new partial index. The partial index creation management module130may automatically make the above-mentioned decision based on information on the size of the latest partial index or the like, or the user may give an instruction of the decision to the partial index creation management module130.

In a case where an index associated with the added data is created as a new partial index, according to the procedures of creating partial indices illustrated inFIG. 2A, the processor102uses the index data acquisition module121to acquire index information of the added data, and creates a partial index.

In a case where an index associated with a part of the added data is added to the latest existing partial index, and then an index associated with the remaining data is created as a new partial index, the index is created according to the following procedures. The following procedures are executed based on the index information of the added data, the index information of the data contained in the existing partial index, the mapping table400stored in the external storage system structural information acquisition module131, and the locality determination criterion received by the locality determination criterion designation reception module132.

First, the processor102stores the index information pieces of the data pieces contained in the existing partial index in the index information file storage area122as the index information file600.

Subsequently, the processor102creates an index according to the procedures of creating partial indices illustrated inFIG. 2A.

The processor102reads one page of the added data pieces, and uses the index data acquisition module121to extract index information pieces necessary to create an index (Step203).

The processor102determines whether or not the page thus read is the last page of the added data pieces (Step204). In a case where the page thus read is not the last page of the added data pieces (the result of Step204is “No”), the processor102then determines whether or not the records from which the index information pieces have been extracted have locality in the external storage system for storage150with respect to the group of records contained in the index information file600(Step205).

In a case where the records from which the index information pieces have been extracted have locality with respect to the group of records contained in the index information file600(the result of Step205is “Yes”), the processor102adds the extracted index information pieces to the index information file600(Step211).

In a case where the group of records contained in the index information file600and the records from which the index information pieces have been extracted do not have locality (the result of Step205is “No”), the processor102newly sets another index information file600as an output destination of the index information pieces, and outputs the extracted index information pieces to the another index information file600(Step206).

Further, the processor102newly generates a thread for creating an index, and creates a partial index based on the switched index information file600(Step207).

When the processor102has finished the processing of Step207, the processor102executes the processings of Step203and subsequent steps with respect to the subsequent records.

In a case where the page thus read is the last page of the added data pieces (the result of Step204is “Yes”), the processor102adds the extracted index information pieces to the index information file600(Step208). Further, the processor102executes the processing of creating a partial index in another thread than that for the processing of extracting the index information (Step209).

According to the sixth embodiment of this invention, a partial index can be created for each group of records having locality in terms of their storage locations in the external storage system. Further, an index associated with added data can be created at high speed while modification of the existing partial index is minimized.

Seventh Embodiment

In a seventh embodiment of this invention, description is given of a case where a plurality of storage devices or external storage systems for storage provide storage areas in a distributed manner, which are then integrated, and data pieces of the table are stored in the areas thus integrated.

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

The database server100of the seventh embodiment of this invention is coupled to one or more external storage systems for storage150via the network170. The external storage system structural information acquisition module131acquires structural information of the one or more external storage systems for storage150coupled thereto. Further, the external storage system structural information acquisition module131includes an inter-storage area structural information acquisition module2033for acquiring mutual structural information of storage areas provided by the one or more external storage systems for storage150coupled thereto.

FIG. 19is a diagram illustrating a mapping table2100showing a mapping between logical addresses and physical addresses, which is an example of the structural information of the external storage systems for storage150according to the seventh embodiment of this invention.

The mapping table2100contains a logical address2101recognized by the database server100, and a physical address2102associated with the logical address2101. The logical address2101is the same as the logical address401of the mapping table400of the first embodiment. The physical address2102has an external storage system number added in addition to the structure of the physical address402of the first embodiment. The external storage system number is identification information of the external storage system.

FIG. 20is an explanatory diagram illustrating a relation between an index2200and a sales history table2201according to the seventh embodiment of this invention.

Hereinbelow, description is given of procedures for an index creation processing according to the seventh embodiment.

First, the processor102uses the external storage system structural information acquisition module131to acquire the structural information of the one or more external storage systems for storage150coupled to the database server100. Further, the processor102uses the inter-storage area structural information acquisition module2033to acquire structural information of the storage areas provided by the one or more external storage systems for storage150coupled to the database server100, and creates the mapping table2100.

For example, in a case where the operating system106of the database server100uses a logical volume manager (LVM) to integrate a plurality of logical units (LUs) created in the one or more external storage systems for storage150coupled to the database server100so as to create one logical volume, the processor102creates the mapping table2100based on structural information of each LU, which is acquired from each external storage system for storage150, and LVM structural information acquired from the operating system106.

If a management command is provided by the operating system106, the management command is used to acquire the structural information of the storage areas provided by the one or more external storage systems for storage150coupled to the database server100. Alternatively, a database designer who has designed the one or more external storage systems for storage150coupled to the database server100may create a file into which the mapping table2100is written, and the inter-storage area structural information acquisition module2033may be notified of the file. Still alternatively, the inter-storage area structural information acquisition module2033may be notified of necessary information via an interface such as a GUI.

Subsequently, the processor102creates partial indices according to the procedures of creating an index of the first embodiment, which are illustrated inFIG. 2A. With regard to the locality determination, it is determined based on, for example, the mapping table2100, that records have locality if the records are stored in storage areas each having the same external storage system number and HDD number.

According to the seventh embodiment of this invention, a partial index is created for each group of records stored at local locations of each storage device, among data pieces stored in the plurality of external storage systems, and accordingly, even in the database processing system including the plurality of external storage systems, the I/O processing time period necessary for search can be shortened.

Eighth Embodiment

In an eighth embodiment of this invention, when the index search using partial indices is executed, a metaindex that holds information for narrowing partial indices to be used for search is created, to thereby achieve high-speed index search.

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

In the computer system according to the eighth embodiment of this invention, the executed task management module115includes a metaindex management module2417in addition to the configuration of the first embodiment. The metaindex management module2417creates and manages a metaindex for narrowing partial indices to be used for search when the index search using partial indices is executed. Specific procedures thereof are described later referring toFIGS. 23 and 24.

FIG. 22is an explanatory diagram illustrating a relation among a metaindex2506, an index2500, and a sales history table2501according to the eighth embodiment of this invention.

In the metaindex2506, an item ID, which bases the index, and identification information of a partial index serving as an index containing a record associated with the item ID are stored. Specifically, it is found based on the metaindex2506that partial indices “001” and “004” serve as indices containing the record associated with an item ID “Item001”.

In the eighth embodiment of this invention, when the index search is executed, the metaindex2506is first searched to specify a partial index associated with a record of a search target, and then the record is acquired. In this manner, not all the partial indices need to be used for search, and accordingly, high-speed index search can be achieved. Hereinbelow, description is given of procedures for an index search processing according to the eighth embodiment of this invention.

FIG. 23is a flow chart illustrating procedures for index search according to the eighth embodiment of this invention.

First, the processor102determines whether or not the metaindex has already been created (Step2606). In a case where the metaindex has not been created yet (the result of Step2606is “No”), the processor102uses the metaindex management module2417to newly create a metaindex (Step2607).FIG. 24illustrates a processing of creating a metaindex.

FIG. 24is a flow chart illustrating procedures of creating a metaindex according to the eighth embodiment of this invention.

First, the processor102initializes the counter that indicates a partial index to be processed. Specifically, the processor102sets the value N of the counter to “1” (Step2651).

The processor102creates a metaindex with respect to an N-th partial index (Step2652). In the processing of creating a metaindex, one partial index is referenced to specify a key column of records contained in the partial index, which is used for creating a metaindex, and values corresponding to the key column are acquired.

For example, in a case where the metaindex2506of the index2500for the sales history table2501illustrated inFIG. 22is created with the item ID serving as a key column, values of item IDs of records contained in the partial index001are acquired. As a result, “Item001” and “Item003” are acquired as the values of the item IDs of the records contained in the partial index001.

Based on the values acquired through the above-mentioned processing, the processor102registers (Item001,001), which is a pair of the value “Item001” of the key column and the partial index number “001”, and (Item003,001), which is a pair of the value “Item003” of the key column and the partial index number “001”, in the metaindex2506.

When the processor102has finished the processing with respect to the N-th partial index, the processor102determines whether or not the N-th partial index is the last partial index (Step2653). In a case where the N-th partial index is the last partial index (the result of Step2653is “Yes”), the processor102ends the processing of creating a metaindex.

On the other hand, in a case where the N-th partial index is not the last partial index (the result of Step2653is “No”), the processor102updates the value N of the counter to “N+1” (Step2654), and processes an (N+1)th partial index in a similar manner to the above.

The above-mentioned procedures are executed with respect to all the partial indices, to thereby create a metaindex. It should be noted that the eighth embodiment of this invention describes the procedures of creating the metaindex2506with respect to partial indices that have already been created, but the metaindex2506may be created in parallel to the execution of the processing of creating partial indices.

The flow chart of the index search processing illustrated inFIG. 23is described again.

The processor102references the metaindex to select a partial index which is to be used for search (Step2601). In the example ofFIG. 22, in a case of “search for a sales history of ‘item ID=Item001’”, the processor102first references the metaindex2506to specify the partial index001as a partial index containing the sales history of “Item001”, and selects the partial index001. Then, the processor102dynamically generates a plurality of tasks to execute the search processing using the selected partial index001(Step2602).

The processor102further references the metaindex to select a partial index which is to be used for search and with which the search processing has not been executed yet (Step2603). In the example ofFIG. 22, the processor102selects the partial index004which contains the sales history of “Item001” and with which the search processing has not been executed yet. Then, the processor102dynamically generates a plurality of tasks, and starts the search processing using the selected partial index004in a similar manner to the above (Step2602).

The processor102further references the metaindex to determine whether or not there remains a partial index which is to be used for search and with which the search processing has not been executed yet (Step2604).

In the example ofFIG. 22, it is the partial indices001and004that are associated with the record having “Item001” as the item ID, and there remains no other partial index to be selected (the result of Step2604is “No”). Hence, the processor102ends the index search.

According to the eighth embodiment of this invention, the metaindex is used and partial indices to be used for search are narrowed, to thereby shorten the search processing time period. In particular, the eighth embodiment is effective in a case of a large-scale database that contains a large number of records, such as a case where the number of partial indices is large.

Ninth Embodiment

In a ninth embodiment of this invention, description is given of procedures for search using partial indices in a case where the application program104simultaneously issues a plurality of query requests to the database management system105.

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

The application program104is executed by the processor102, and processes various kinds of tasks. When processing the tasks, the application program104issues a query to the database management system105, and receives a query result therefrom. In the ninth embodiment of this invention, the application program104simultaneously issues, to the database management system105, a considerable number of queries which are different from one another only in argument of a search condition. Referring toFIGS. 26A to 26C, specific examples of such queries are described later.

The database management system105according to the ninth embodiment of this invention includes a multi-query execution control module2740.

The multi-query execution control module2740includes a multi-query reception module2741, a partial index search control module2742, and the query execution control module110.

The multi-query reception module2741simultaneously receives a plurality of query requests issued from the application program104. The partial index search control module2742controls the search processing using partial indices with respect to the plurality of query requests.

The query execution control module110processes one query request after another. Similarly to the first embodiment, the query execution control module110includes the query reception module111, the query execution plan generation module112, the query execution module113, and the DB buffer114. The components include in the query execution control module110are similar to those of the first embodiment. As described above, the query execution module113is provided with basic database operations for generating a query result. The query execution plan refers to processing procedures obtained by combining the database operations in order to generate a query result.

FIGS. 26A to 26Care diagrams illustrating examples of the queries that are simultaneously issued according to the ninth embodiment of this invention.

As illustrated inFIGS. 26A to 26C, in the ninth embodiment of this invention, queries are written in the SQL. The queries issued from the application program104to the database management system105are common to one another in terms of the index to be referenced, and as described above, are different from one another only in argument of a search condition.

Specifically, as illustrated inFIGS. 26A to 26C, the queries are different from one another only in argument of a search condition as indicated by “Item001”, “Item002”, and “Item003”, respectively. Other designation of the search condition is identical among the queries.

It should be noted that the index is similar to the index2200of the seventh embodiment of this invention, which is illustrated inFIG. 20. Hereinbelow, referring toFIG. 27, description is given of procedures of processing the plurality of queries as illustrated inFIGS. 26A to 26C.

FIG. 27is a flow chart illustrating procedures for index search according to the ninth embodiment of this invention.

When the application program104has simultaneously issued a plurality of query requests for which the same partial index may be used, the processor102uses the multi-query reception module2741of the database management system105to receive the query requests.

The processor102generates query execution plans for the plurality of queries thus received, respectively. Specifically, the processor102first sets the value N of the counter for the plurality of queries thus received to “1” as initialization (Step2901). Subsequently, the processor102uses the query execution plan generation module112to generate a query execution plan for an N-th query (Step2902).

The processor102determines whether or not query execution plans have been generated for all the received queries (Step2903). In a case where query execution plans have not been generated for all the received queries (the result of Step2903is “No”), the processor102adds “1” to the value N of the counter (Step2904), and generates query execution plans for the remaining queries (Step2902).

In a case where query execution plans have been generated for all the received queries (the result of Step2903is “Yes”), the processor102starts processing each of the queries. In the search processing of the ninth embodiment of this invention, each of the queries is executed using each partial index.

The processor102initializes the value N of the counter that corresponds to the query and a value M of a counter that corresponds to the partial index (Step2905). Then, the processor102starts the N-th query using the M-th partial index (Step2906).

Specific description is given referring to the index information ofFIG. 20and the queries ofFIGS. 26A to 26C. First, the processor102starts a processing of a first query request2800using the partial index001(2202) (Step2906). Subsequently, the processor102starts a processing of a second query request2801using the partial index001(2202) (Step2908and Step2906), and then starts a processing of a third query request2802using the partial index001(2202).

At this time, the processor102has started the processings up to the third (last) query request2802using the partial index001(2202) (the result of Step2907is “Yes”), and hence the processor102subsequently starts the processing starting from the first query request2800using the partial index002(2203) (Step2909, Step2910, and Step2911). Subsequently, the processor102starts the processing of the second query request2801using the partial index002. In the following steps, the processor102executes the three query requests using up to the partial index004through the similar procedures to the above.

As described above, according to the ninth embodiment of this invention, in the case where the plurality of query requests different from one another only in argument of a search condition are executed, it is possible that the processor102uses the multi-query execution control module2740to aggregate the input and output with respect to the partial indices, and to collectively issue I/O requests for data pieces stored at local locations of the storage device. Accordingly, the I/O request processing time period can be shortened owing to the function of scheduling I/O requests, which is provided to the external storage system for storage150.

Tenth Embodiment

In a tenth embodiment of this invention, description is given of a processing performed when data stored in the database is updated.

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

The executed task management module115of the query execution control module110includes an update writing control module3117for controlling a processing of reflecting a result of an update request on the external storage system for storage150.

FIG. 29is a diagram illustrating an example of an update request issued from the application program104to the database management system105according to the tenth embodiment of this invention.

The update request illustrated inFIG. 29corresponds to a processing of updating, in a case where items having the item ID “Item001” are all purchased, an inventory quantity of each warehouse to “0”.

FIG. 30is an explanatory diagram illustrating a relation between an index3300and an inventory management table3301according to the tenth embodiment of this invention.

When the update request ofFIG. 29is executed, records having the item ID “Item001” of the inventory management table3301are updated and the inventory quantity of each of the records is set to “0”. Specifically, in records respectively having “0x00000000”, “0x00003000”, and “0x00010000” as values of record pointers thereto, the inventory quantity thereof is set to “0”.

Hereinbelow, description is given of the data update processing according to the tenth embodiment of this invention.

When an update request3200is issued from the application program104to the database management system105, the processor102uses the query reception module111of the query execution control module110to receive the update request3200.

The processor102uses the query execution plan generation module112to generate a query execution plan for processing the received update request3200. Further, the processor102uses the query execution module113to dynamically generate tasks, and to execute the processing according to the generated query execution plan.

When executing the update request3200, the processor102first searches for records having the item ID “Item001”. In a case where the records of the search target are stored in the DB buffer114, the processor102acquires the records from the DB buffer114. In a case where the records are not stored in the DB buffer114, the processor102acquires the records from the external storage system for storage150. Procedures of searching the external storage system for storage150for records are similar to the procedures described in the first embodiment.

When the processor102has acquired the records, the processor102updates the inventory quantity thereof to “0”, and stores an update result in the DB buffer114. The processor102executes the processing of updating the inventory quantity with respect to all the records having the item ID “Item001”. The processor102searches the external storage system for storage150for records by following the procedures similar to the procedures described in the first embodiment, and hence records contained in partial indices are acquired in an order of the partial indices, with the result that the group of acquired records have locality in the storage device155in an order of the acquisition.

At a timing such as a time point at which the query execution control module110has received an instruction from the application program104, or a case where the number of updated records stored in the DB buffer114has exceeded a value set in advance by the database designer, the query execution control module110writes the group of updated records stored in the DB buffer114over the corresponding records stored in the external storage system for storage150.

According to the tenth embodiment of this invention, the group of acquired records have locality in the storage device155in the order of the acquisition, and accordingly, the data update processing (data writing processing) can be executed collectively at local locations of the storage device155. As a result, similarly to the search processing, the time period necessary for the data update processing can be shortened.