JP6680871B2 - Computer and database management method - Google Patents

Description

  The present invention relates generally to database management technology.

  Generally, in business activities, it is required to utilize a large amount of business data. Therefore, the construction of a column store DB (database) that stores data in a column format (typically compresses data in the column direction and stores it) is increasing for the collection, storage, and analysis of vast amounts of data. There is.

  If the added data is stored in the column format each time data is added (collected), the processing time increases. This is because in order to store the added data, it is necessary to temporarily read out the data group stored in the column format, decompress it, and add the additional data to compress it. This problem increases as the frequency of adding data increases.

  Therefore, in the case of storing the collected data in the column format, the conversion method is generally adopted. According to the conversion method, the added data is temporarily stored in a row format, a plurality of data is accumulated in the row format, and then the plurality of data are stored in a column format. The process of converting the data storage format from the row format (row-oriented) to the column format (column-oriented) can be called “conversion processing”. In the conversion process, the data storage position is changed. That is, the data is moved from the row storage location to the column storage location.

  Search using an index is known. The index generally holds a search key and a pointer. The pointer indicates the storage location of data. When the conversion process is performed, the data is moved (the data storage position is changed), so that the index needs to be updated. There are the following two methods for updating the index.

  (First Index Update Method) Index management is known in which pointers of the same search key are sorted in pointer order. In the index, one or more leaf nodes hold the same search key pointer set. According to the first index update method, the exclusive lock of all leaf nodes including the target search key (search key corresponding to the pointer corresponding to the moved data) is acquired, the pointer corresponding to the moved data is updated, A pointer set including the updated pointers is sorted in pointer order, and then the acquired exclusive lock is released.

  (Second Index Update Method) A mapping index is known (for example, Non-Patent Document 1). According to the second index updating method, a pointer set, which is a set of a pointer indicating a position before movement and a pointer indicating a position after movement, is registered in the mapping index for the moved data.

Per- Å ke Larson, Adrian Birka, Eric N. Hanson, Weiyun Huang, Michal Nowakiewicz, Vassilis Papadimos, “Real-Time Analytical Processing with SQL Server”, VLDB2015

  According to the first index updating method, while the exclusive lock state (exclusive) is set for the target search key, other processing such as a search processing of data corresponding to the target search key is suspended. Therefore, the processing performance as a whole is lowered.

  According to the second index update method, the pointer set is registered in the mapping index for each moved data, and as a result, the capacity of the mapping index increases. The index is additional information created to improve search performance, and the mapping index is also additional information. However, as the capacity of such additional information, the index capacity (normal index capacity and It is not preferable that the total of the mapping index and the capacity) increases. Further, since the mapping index can be referred to in the search, the search performance may decrease as the capacity of the mapping index increases.

  For the above reasons, it is not preferable for the column store DB, particularly for the environment where the collected data is stored in the column format. Such a problem is not limited to the data movement for changing the storage format from the row format to the column format, and may occur in the case where the data movement occurs for other reasons.

  A computer executes a record move process to move at least one record in the table of the database including the index and the table. Further, the computer executes an index update process for updating the index along with the record moving process. The index update process includes overwriting the before-movement pointer in the index with the after-movement pointer for the record moved in the record movement process. The pre-movement pointer is a pointer to the record at the storage position before the movement. The post-movement pointer is a pointer to the record at the storage position after the movement. The “computer” may be one or more physical computers and may include at least one virtual computer.

  The index capacity does not increase in the index update processing that accompanies the record movement processing, and other processing such as search processing is possible in parallel with the index word update processing.

1 shows the configuration of a computer system related to Example 1. FIG. 3 is a schematic diagram of an example of an index according to the first embodiment and a table corresponding to the index (before moving records). FIG. 3 is a schematic diagram of an example of an index according to the first embodiment and a table corresponding to the index (after moving records). 6 is a flowchart of index conversion processing according to the first embodiment. 6 is a flowchart of index search processing according to the first embodiment. 6 is a flowchart of index insert processing according to the first embodiment. 7 shows an index deletion processing flow according to the first embodiment. It is a sequence diagram which shows an example of parallel execution of an index update process and an index search process. An example of the 1st report showing DB capacity transition is shown. An example of the 2nd report showing DB performance behavior is shown. FIG. 9 is a schematic diagram of an example of an index according to the second embodiment and a table corresponding to the index (after moving records). 9 is a flowchart of index insert processing according to the second embodiment. 9 is a flowchart of index deletion processing according to the second embodiment.

  The issuer of the query to the DBMS (database management system) may be a computer program inside the DBMS or an external computer program. For example, the query issuer may be a computer program (for example, an application program) executed in a database server having a DBMS (hereinafter referred to as a DB server), or a device such as a client computer connected to the DB server. It may be a computer program (for example, an application program) to be executed.

  In the following description, the “interface unit” includes one or more interfaces. The one or more interfaces may be one or more same type interface devices (for example, one or more NICs (Network Interface Cards)) or two or more different type interface devices (for example, NICs and HBAs (Host Bus Adapters)). It may be.

  Further, in the following description, “storage resource” includes one or more memories. The at least one memory may be a volatile memory or a non-volatile memory. Storage resources may include one or more PDEVs in addition to one or more memories. “PDEV” means a physical storage device, which may typically be a non-volatile storage device (eg, auxiliary storage device). The PDEV may be, for example, an HDD (Hard Disk Drive) or SSD (Solid State Drive).

  Further, in the following description, the “processor unit” includes one or more processors. At least one processor is typically a CPU (Central Processing Unit). The processor may include a hardware circuit (eg, FPGA (Field-Programmable Gate Array) or ASIC (Application Specific Integrated Circuit)) that performs a part or all of the processing.

  Further, in the following description, the processing unit (function) may be described by the expression “kkk unit”, but the processing unit may be realized by executing a computer program by the processor unit, It may be realized by a hardware circuit (for example, FPGA or ASIC). When the processing unit is realized by the processor unit, the processing unit executes the predetermined processing while appropriately using the storage resource (for example, memory) and / or the communication interface device (for example, communication port). It may be at least a part of the part. The processing described with the processing unit as the subject may be processing performed by the processor unit or an apparatus including the processor unit. The processor unit may also include a hardware circuit that performs a part or all of the processing. The program may be installed on the processor from a program source. The program source may be, for example, a program distribution computer or a computer-readable recording medium (for example, a non-transitory recording medium). The description of each processing unit is an example, and a plurality of processing units may be integrated into one processing unit or one processing unit may be divided into a plurality of processing units.

  Hereinafter, some embodiments will be described with reference to the drawings. In the following embodiments, the record movement occurs in the conversion process, but the present invention can also be applied to an environment in which records move for reasons other than the conversion process.

  FIG. 1 shows the configuration of a computer system according to the first embodiment.

  The DB server 101 is connected to the external storage device 118 via the communication network 403. As a protocol for communication via the communication network 403, for example, FC (Fibre Channel), SCSI (Small Computer System Interface), or TCP / IP (Transmission Control Protocol / Internet Protocol) may be adopted.

  The DB server 101 is a computer, for example, a personal computer, a workstation, a mainframe, or a virtual computer (virtual machine) configured by any of these. The DB server 101 has a network adapter 119, a memory 102, a local storage device 117, and a processor (typically a microprocessor) 116 connected to them. The processor 116 executes a computer program, for example, an OS (Operating System) 114, the DBMS 104, and an AP (Application Program) 103 that issues a query to the DBMS 104. The memory 102 temporarily stores a program executed by the processor 116 and data used by the program. The local storage device 117 stores programs and data used by the programs. The network adapter 119 connects the communication network 403 and the DB server 101. The AP 103 may operate not on the DB server 101 but on another computer (not shown) connected to the communication network 403.

  The DB server 101 may include a plurality of at least one element of the processor 116, the memory 102, the local storage device 117, and the network adapter 119 from the viewpoint of performance and redundancy. Further, the DB server 101 may include an input device (for example, a keyboard and a pointing device) (not shown) and a display device (for example, a liquid crystal display). The input device and the display device may be integrated.

  In the DB server 101, the DBMS 104 executes the query issued by the AP 103. When executing the query, the DBMS 104 issues an I / O request for the DB 122 stored in the external storage device 118 to the OS 114. The OS 114 sends the I / O request issued from the DBMS 104 to the external storage device 118.

  The external storage device 118 is a device having a storage device group 121. Alternatively, the external storage device 118 may be a single storage device. The external storage device 118 stores data and programs used by the DB server 101. The external storage device 118 receives the I / O request from the DB server 101, executes the process corresponding to the I / O request, and sends the process result to the DB server 101.

  The external storage device 118 has a network adapter 119, a storage device group 121, and a controller 120 connected to them.

  The network adapter 119 connects the external storage device 118 to the communication network 403.

  The storage device group 121 includes one or more storage devices. The storage device is a PDEV and is, for example, a magnetic disk, a flash memory, or another semiconductor memory. The storage device group 121 may be a group that stores data at a predetermined RAID level according to RAID. A logical storage device (logical volume) may be provided to the DB server 101 based on the storage space of the storage device group 121. The storage device group 121 stores the DB 122.

  The controller 120 includes, for example, a memory and a processor. The controller 120 inputs / outputs data to / from the storage device group 121 storing the DB 122 according to the I / O request from the DB server 101. For example, the controller 120 stores the write-targeted data in the storage device group 121 according to the write request from the DB server 101. Further, the data to be read according to the read request from the DB server 101 is read from the storage device group 121 and the data is transmitted to the DB server 101.

  The external storage device 118 may include a plurality of elements such as the controller 120 from the viewpoint of performance and ensuring redundancy.

  The DBMS 104 manages the DB 122 including business data. The DB 122 includes one or more tables 124 and indexes 123. The table 124 is a set of one or more records, and each record is composed of one or more columns. The table 124 includes a plurality of records stored in a column format. That is, although the DB 122 is a column store DB, specifically, it is a DB in which one or more records in the table 124 are stored in a column format. The index 123 is a data structure created for one or more columns in the table, and speeds up access to the table according to a selection condition including the column targeted by the index 123. For example, the index 123 is a data structure that holds, for each value of the target column, a pointer that indicates the position of a record in the table that includes that value, and a B-tree structure or the like is used.

  The DBMS 104 includes a query reception unit 105, a query execution plan generation unit 106, a query execution unit 107, a column store management unit 109, and an area control unit 427.

  The query reception unit 105 receives a query issued by the AP 105. The query is described in SQL, for example.

  The query execution plan generation unit 106 generates a query execution plan having, for the query received by the query reception unit 105, information indicating one or more DB operations required to execute the query. The query execution plan is, for example, information that defines the execution order of a DB operation to be performed when executing a query in a tree structure, and is stored in the memory 102. The query execution plan may also include, for each DB operation, information indicating the amount of memory resources required for execution by a task. For example, in the case of a query execution plan that includes information indicating a DB operation that reads a record of a table, the query execution plan may include information regarding the amount of memory resources for storing the record of the table in the memory 102. .

  The area control unit 427 manages a storage area (DB buffer) for temporarily storing data in the DB 122, and manages a plurality of logical areas (DB pages) storing the DB 122. The DB buffer may be built on the memory 102 or the local storage device 117. The DB page may be a part of the logical space based on the storage device group 121.

  The query execution unit 107 executes a query according to the query execution plan generated by the query execution plan generation unit 106. The query execution unit 107 includes a search unit 110 that executes a record search process, an insert unit 111 that executes a record insert process, a deletion unit 112 that executes a record deletion process, and a conversion unit 113 that executes a conversion process. . The query execution unit 107 also includes an index management unit 131 that manages the index 123. The index management unit 131 includes an index search unit 132 that executes an index search process, an index insert unit 133 that executes an index insert process (insertion of an entry into an index), and an index delete process (delete an entry from an index). It has an index deleting unit 134 to be executed and an index converting unit 135 to execute an index updating process (a process accompanying record movement in the converting process).

  The above is the outline of the computer system. Note that, for example, the configuration of the DBMS 104 is an example. For example, a certain processing unit may be divided into a plurality of processing units, or one processing unit that integrates the functions of the plurality of processing units may be constructed.

  FIG. 2 is a schematic diagram (before record movement) of an example of the index 123 and the table 124 corresponding to the index 123.

  The table 124 stores seven records 220 to 226. Of these, the records 220 and 221 are records stored in raw format. The record stored in the row format is an example of a record whose storage position may be changed in the future. The remaining records 222 to 226 are records stored in a column format. The record stored in the column format is an example of a record whose storage position cannot be changed. In this embodiment, both the storage destination of records stored in the row format and the storage destination of records stored in the column format are DB pages based on the storage device group 121. The destination may be a temporary area based on the memory 102. The record stored in the raw format is an example of a record that can be moved (a record whose storage position can be changed). That is, in the present embodiment, for example, each time data is collected from a data source (for example, one or more sensors), a record based on one or more collected data (for example, a record including a value included in the collected data). ) Is stored in the row format by the DBMS 104, and when N or more records (N is an integer of 2 or more) stored in the row format are accumulated, the conversion unit 113 performs the conversion process. In the conversion process, the storage format of at least N records is converted from the row format to the column format.

  The index 123 has a plurality of B-tree structured nodes. The plurality of nodes include a root node 251, a leaf node 253, and an intermediate node 252. A "root node" is a node that has no parent node. A "leaf node" is a node that has no child nodes. The "intermediate node" is a node other than the root node and the leaf node.

  At least a search key of the search key and the pointer set is stored in each node. The child node to be referred to is specified based on the search key in the parent node.

  The leaf node 253 holds one or more search keys. The leaf node 253 stores one or more pointer sets for each search key. The "pointer set" is a set of the number of pointers and pointers of 0 or more. The number of pointers in the pointer set represents the number of pointers in the pointer set. In FIG. 2, the number of pointers is a one-digit integer, and the pointer is a set of alphabetic capital letters “P” and an integer of one or more digits. Hereinafter, the area (intra-node area) where significant information elements such as the number of pointers and pointers are present is referred to as “slot” for convenience. According to the example of FIG. 2, the number of pointers is stored in each of the slots 204 and 207, and the pointer (for example, the address of the storage position of the record) is stored in each of the slots 205 to 206 and 208 to 210. There is. Specifically, one pointer set is stored in consecutive slots such as the slots 204 to 206 and the slots 207 to 210. That is, the number of pointers "2" in the slot 204 represents the number of pointers ("P1" and "P2") in the pointer set including the number of pointers. Similarly, the number of pointers “3” in the slot 207 represents the number of pointers (“P10”, “P11”, and “P13”) in the pointer set including the number of pointers. In the present embodiment, the pointer set includes the number of pointers, but the pointer set does not necessarily include the number of pointers.

  The leaf node 253 includes an entry for each search key. The “entry” is a term for convenience indicating an area (a part or all of a leaf node) in which a search key and one or more pointer sets corresponding to the search key are stored. According to the example of FIG. 2, the leaf node 253 includes an entry 261 corresponding to the search key “100” and an entry 262 corresponding to the search key “101”.

  Further, in this embodiment, the leaf node 253 has a non-sorted entry part and a sorted entry part for each search key. One or more pointer sets are stored in each of the non-sorted entry portion and the sorted entry portion. According to the example of FIG. 2, an entry 261 corresponding to the search key “100” includes a non-sorted entry portion 271 including slots 204 to 206 in which pointer sets are stored, and slots 207 to 210 in which pointer sets are stored. And a sort entry portion 272 including Similarly, the entry 262 corresponding to the search key “101” includes a non-sorted entry portion 273 and a sorted entry portion 274. Whether the entry part is a non-sorted entry part or a sorted entry part can be determined by, for example, referring to the value of a flag set at a predetermined position of the entry part. In the following description, of the search keys “100” and “101”, the search key “100” is mainly taken as an example. As will be described later, when the lock is acquired in DB page units, it is preferable that the non-sorted entry portion 271 and the sorted entry portion 272 be stored in different DB pages. For example, when the sort entry part 272 is stored in the DB page # 2, the non-sort entry part 271 is preferably stored in a different DB page # 1. Non-sorted entry parts corresponding to one or more search keys may be aggregated in one or more first DB pages, and sort entry parts corresponding to one or more search keys may be aggregated in one or more second DB pages. .

  The pointers stored in the sort entry portion 272 are sorted in pointer order (for example, the integer value of the pointer is small), but the pointers stored in the non-sort entry portion 271 are not sorted in pointer order. In the non-sorted entry portion 271, pointers "P1" and "P2" of records (records corresponding to the search key "100") stored in raw format, in other words, record storage positions can be updated in the future. A unique pointer is stored. In the sort entry portion 272, pointers “P10”, “P11”, and “P13” of records (records corresponding to the search key “100”) stored in the column format, in other words, record storage positions will be updated in the future. Not stored pointer.

  In the example of FIG. 2, as described above, the records 220 and 221 are stored in raw format. In other words, the example of FIG. 2 shows an example of the state before the record movement.

  FIG. 3 is a schematic diagram (after moving records) of an example of the index 123 and the table 124 corresponding to the index 123.

  The records 220 and 221 stored in the row format become the records 303 and 304 stored in the column format by the conversion processing performed by the conversion unit 113. That is, the records 220 and 221 stored in the row format are moved to become the records 304 and 303 stored in the column format. Even if the storage format is changed in this way, the records 220 and 221 are not immediately deleted.

  The converting unit 113 attaches (associates) the post-movement pointer 301 (“P16”) to the record 220 and the post-movement pointer 302 (“P15”) to the record 221. Such additional pointer writing may be performed immediately by the converting unit 113 after the record is moved. The post-movement pointers 301 to 302 may be explicitly described for each record, for example, only the first record may be explicitly described and the subsequent records may be calculated by adding the record offsets. The “post-movement pointer” is a pointer indicating the storage position of the record after the movement. On the other hand, the “pre-movement pointer” described later is a pointer that indicates the storage position before movement of the record. Both the after-movement pointer and the before-movement pointer may be expressed by an explicit pointer or may be expressed by an offset from a reference storage position (for example, the storage position of the first record).

  After the conversion process (record move process) is completed, the index conversion unit 135 executes the update process of the index 123. Specifically, the index conversion unit 135 overwrites the post-movement pointer "P16" on the slot 205 in which the pre-movement pointer "P1" of the record 220 was stored. Similarly, the index conversion unit 135 overwrites the post-movement pointer "P15" on the slot 206 in which the pre-movement pointer "P2" of the record 221 was stored.

  These pointer overwrite processes may be executed in parallel with other search processes. For example, when the search unit 110 refers to the pointer “P1” before pointer overwriting from the index 123 in the search process, the post-movement pointer “P16” added to the record 220 specified by the pointer “P1” is acquired. After that, the record 304 can be referred to by using the pointer “P16”. On the other hand, when the search unit 110 refers to the pointer “P16” after pointer overwriting from the index 123 in the search process, the record 304 can be referred to using the pointer “P16”.

  The DBMS 104 (for example, the deletion unit 112) deletes the records 220 and 221 after the conversion processing (record movement processing). The deletion is performed, for example, when the process of referring to the records 220 and 221 before the movement disappears.

  FIG. 4 is a flowchart of the index update process. The index update process is executed by the index conversion unit 135.

  In step S4001, the index conversion unit 135 searches the index 123 for a slot in which the pre-movement pointer (for example, “P1”) of the movement target record (for example, 220) is stored.

  In S4002, the index conversion unit 135 overwrites the found pointer (for example, the slot in which the pre-movement pointer “P1” is stored) with the post-movement pointer (for example, “P16”).

  FIG. 5 is a flowchart of the index search process. The index search process is executed by the index search unit 132.

  In step S5001, the index search unit 132 searches the index 123 for an entry (for example, 261) in which a search target key (for example, “100”) is stored.

  In step S5002, the index search unit 132 acquires all pointers from the found entry.

  FIG. 6 is a flowchart of the index insert process. The index insert processing is executed by the index insert unit 133.

  In step S6001, the index insert unit 133 searches the index 123 for an entry in which the search key of the inserted record is stored.

  In step S6002, the index insert unit 133 determines whether the inserted record may be moved (whether the inserted record is stored in the raw format). Specifically, for example, there are row format DB pages (DB pages for storing row format) and column format DB pages (DB page for storing column format) as DB pages, and the index insert unit 133 is inserted. It is determined whether the record that exists in the raw format DB page exists.

  When the determination result of S6002 is true (S6002: Y), the index insertion unit 133 specifies the tail pointer of the non-sorted entry portion of the entries found in S6001 in S6003. Then, in step S6005, the index insert unit 133 adds a pointer indicating the storage position of the inserted record after the identified last pointer. As a result, the pointer of the non-sorted entry portion can always be identified by the pointer offset. For example, even if the pointer is overwritten by the conversion process during the index search, the pointer is uniquely specified by the pointer offset in the search process, and the search is performed while incrementing the pointer offset, so that the search can be performed without omission or duplication. It becomes possible to execute processing.

  On the other hand, when the determination result of S6002 is false (S6002: N), the index insert unit 133 specifies the sort entry part of the entries found in S6001 and inserts from the specified sort entry part in S6004. Specify the insert position of the pointer of the record that was saved. Then, in S6005, the index insert unit 133 additionally writes the pointer of the inserted record at the specified position.

  In the above index insert processing, for example, the following processing may be performed.

  That is, in S6004, the index insert unit 133 acquires a lock (for example, an exclusive lock) of the identified sort entry portion (for example, a DB page including the non-sort entry portion). If already locked, the index insert unit 133 waits for unlocking. While the sort entry part is in the locked state, in S6005, the index insert part 133 additionally writes pointers, sorts the pointer set in the sort entry part in pointer order, and releases the lock after sorting. Since it is in the locked state until pointer addition and sorting are completed, the locked state takes a long time. In addition, when the sort entry part is stored in two or more DB pages, the index insert unit 133 acquires the lock of those two or more DB pages. This is because all pointers in the sort entry part are targets of sorting.

  On the other hand, in step S6003, the index insert unit 133 acquires the lock of the non-sorted entry portion (for example, the DB page including the non-sorted entry portion). The index insert unit 133 additionally writes the pointer during the locked state, and releases the lock after the additional writing of the pointer. Since the lock is released after the pointer is additionally written, the lock time can be shortened. Further, even if the non-sorted entry part is stored in two or more DB pages, the lock is only for the DB page including the pointer added part (last part) in the non-sorted entry part among the two or more DB pages. It should be acquired. This is because all the pointers in the non-sorted entry part are not sorted.

  As described above, the lock may be acquired (excluded) in the sort entry part and the lock may not be acquired in the non-sort entry part. The lock acquisition may be performed in DB page units as described above. In this case, it is preferable that the sorted entry portion and the unsorted entry portion are stored in different DB pages.

  FIG. 7 is a flowchart of the index deletion process. The index deleting process is executed by the index deleting unit 134.

  In step S7001, the index deletion unit 134 searches the index 123 for an entry in which the search key of the record to be deleted is stored.

  In step S7002, the index deletion unit 134 determines whether the deletion target record may be moved (whether it is stored in raw format). The determination of S7002 is the same determination as S6002 of FIG.

  If the determination result of S7002 is false (S7002: N), the index deleting unit 134 searches the sort entry part of the entries found in S7001 by dichotomy in S7003, and finds the slot containing the pointer of the record to be deleted. Search for. When the search target slot is found by the binary search in S7003 (S7004: Y), the index deleting unit 134 deletes the pointer in the found slot in S7006. If the search target slot is not found in the binary search of S7003 (S7004: N), the index deleting unit 134 searches the unsorted entry portion of the entries found in S7001 in S7005, and deletes the record to be deleted. Search for the slot containing the pointer. Then, in S7006, the index deleting unit 134 deletes the pointer contained in the slot found in the full search in S7005.

  If the determination result of S7002 is true (S7002: Y), the index deleting unit 134 searches the unsorted entry part of the entries found in S7001 in S7005, and the slot containing the pointer of the record to be deleted is included. To search. Then, in S7006, the index deleting unit 134 deletes the pointer contained in the slot found in the full search in S7005.

  S7002: In the case of N, the slot is searched from the sort entry part before the non-sort entry part. This is because the search from the sort entry part has a lower search cost (faster search speed).

  FIG. 8 is a sequence diagram showing an example of parallel execution of the index update process and the index search process.

  It is assumed that the index search unit 132 acquires the shared lock of the DB page A by requesting the shared lock of the DB page A including the search target from the area control unit 108 (S804) (S805). While the DB page A is in the shared lock state, when the index conversion unit 135 requests the area control unit 108 for the exclusive lock of the same DB page A, the acquisition of the exclusive lock is awaited. After the shared lock is released (S806), the index conversion unit 135 can acquire the exclusive lock (S811).

  After that, it is assumed that the index search unit 132 acquires the shared lock of the DB page B by requesting the shared lock of the DB page B from the area control unit 108 (S807) (S808). During the index search process for the DB page B, the index conversion unit 135 can execute the index update process for the DB page A for which the exclusive lock has been acquired in parallel. The index conversion unit 135 releases the exclusive lock on the DB page A (S812), and the index search unit 132 releases the shared lock on the DB page B (S809).

  FIG. 9 is an example of the first report 901.

  The first report 901 is an example of information for the DB administrator, for example, and represents the transition of the DB capacity. The first report 901 is displayed by the column store management unit 109. The column store management unit 109 may display the first report 901 on a display device included in the DB server 101, or may display the first report 901 on a remote computer connected to the DB server 101 (the first report 901). 1 Display information of the report 901 may be transmitted to the remote computer).

  The first report 901 includes a capacity 902 of the table 124, a capacity 903 of the index 123, a capacity transition (for example, a graph) 905, and a predicted period 904 until the DB maximum capacity is reached. The first report 901 shows an example of the report description format, and does not limit the report description format. In the first report 901, information may be described in a different format, or different information may be additionally described.

  The transition of the capacity of the table 124 is predicted by the column store management unit 109 based on information such as the record collection speed (total record capacity added per unit time). The transition of the capacity of the index 123 is predicted by the column store management unit 109 based on the transition of the capacity of the table 124. The reason that the capacity of the index 123 can be predicted based on the capacity of the table 124 is that the capacity of the index 123 is not increased by the conversion process according to this embodiment.

  FIG. 10 is an example of the second report 1001.

  The second report 1001 is an example of information for the DB administrator, for example, and represents the DB performance behavior based on the DB statistical information. The second report 1001 is displayed by the column store management unit 109. The column store management unit 109 may display the second report 1001 on the display device of the DB server 101, or may display the second report 1001 on a remote computer connected to the DB server 101 (the first report 1001). 2 The display information of the report 1001 may be transmitted to the remote computer). Also, the format of the second report 1001 may be an example, like the first report 901.

  The DB statistical information includes, for example, the number of insert executions 1002, the number of deletion executions 1003, the number of conversion executions 1004, the number of waits 1005 caused by the insert processing during the search processing, the number 1006 of waits caused by the deletion processing during the search processing, In addition, the number of times 1007 the wait occurs due to the conversion process during the search process is described.

  According to the example of FIG. 10, the case where waiting occurs due to the conversion process is when the pointer is overwritten in the slot, and as described above, another process such as the search process can be executed in parallel with the conversion process. . For this reason, the number 1007 of waits generated by the conversion process is considerably lower than the number 1004 of conversion executions. It should be noted that if the number 1007 of waits generated by the conversion process is large, reducing the size of the DB page is an example of coping measures.

  As described above, according to the first embodiment, the index capacity is not increased by the conversion process, and the search process can be performed for the same search key in parallel with the conversion process. That is, both an increase in index capacity and a decrease in processing performance can be avoided.

  Example 2 will be described. At that time, differences from the first embodiment will be mainly described, and description of common points with the first embodiment will be omitted or simplified.

  FIG. 11 is a schematic diagram (after moving records) of an example of the index 123 and the table 124 corresponding to the index 123 according to the second embodiment.

  The leaf entry 1253 of the index 1123 has an entry for each search key, but the entry has a non-sorted entry portion and does not have a sorted entry portion. That is, the entry does not have an area in which the points are sorted in pointer order. For example, the entry 1261 corresponding to the search key “100” has a slot 1107 in which the number of pointers “5” is stored, and five pointers “P16”, “P15”, “P10”, “P11” and “P13”. There are five pointers 1101 to 1105 in which are respectively stored. The pre-movement pointers "P1" and "P2" are overwritten by the post-movement pointers "P16" and "P15", respectively, but the above-mentioned five pointers including the post-movement pointers "P16" and "P15" are sorted in pointer order. Not done.

  FIG. 12 is a flowchart of the index insert process according to the second embodiment.

  In step S12001, the index insert unit 1133 searches the index 1123 for an entry in which the search key of the inserted record is stored.

  In S12002, the index insert unit 1133 identifies the tail pointer of the found entry.

  In step S12003, the index insert unit 1133 additionally writes the pointer of the inserted record after the identified last pointer.

  FIG. 13 is a flowchart of the index deletion process according to the second embodiment.

  In step S13001, the index deletion unit 1134 searches the index 1123 for an entry in which the key of the record to be deleted is stored.

  In S13002, the index insert unit 1133 searches all the entries (pointer group) found in S13001 and searches for the slot containing the pointer of the record to be deleted.

  In S13003, the index insert unit 1133 deletes the pointer contained in the slot found by the full search in S13002.

  As described above, also in the second embodiment, the index capacity is not increased by the conversion process, and the search process can be performed on the same search key in parallel with the conversion process. Further, according to the second embodiment, since the total search is always required, the deletion processing amount is larger than that of the first embodiment, but the index structure can be simplified as compared with the first embodiment. In addition, in cases like analysis, it is likely that multiple records will be deleted together, and it is unlikely that individual records will be deleted.Therefore, in such cases, the increase in the amount of deletion processing is exceptional. It is not considered to be a disadvantage.

  Although some embodiments have been described above, it is needless to say that the present invention is not limited to these embodiments and can be variously modified without departing from the scope of the invention.

  For example, both of the first and second embodiments can be expected to be applied to the case where the on-demand analysis is performed during the conference to shorten the decision-making time, such as a dynamic meeting.

Claims (12)

An interface section including one or more interfaces including an interface to a database including an index and a table,
A processor unit including one or more processors connected to the interface unit,
The processor unit executes an index update process of updating the index, along with a record move process of moving at least one record in the table,
In the index update process, the processor unit overwrites the post-movement pointer on the pre-movement pointer in the index for the record moved in the record movement process,
The pre-movement pointer is a pointer to a record at the storage position before the movement,
The after-movement pointer is a pointer to the record at the storage position after movement,
The index includes a plurality of nodes in a tree structure,
A pointer for each key is stored in one or more leaf nodes of the plurality of nodes,
The one or more leaf nodes are
A first area which is an area in which a pointer to a movable record corresponding to the key is stored and the pointer is not sorted in pointer order;
A second area which is an area in which a pointer to an immovable record corresponding to the key is stored and the pointer is sorted in pointer order,
calculator. The processor unit executes an index deletion process that is a process of searching for a pointer to be deleted from the index and deleting the found pointer,
The search for the first region is a full search,
Search for the second region, Ri binary search der,
In the index deletion processing, when the pointer to be deleted is a pointer to a record that cannot be moved, a search is performed on the second area, and when the pointer is not found by the search, the first area is searched. The computer according to claim 1. The processor unit deletes the moved record from the storage position before the move, after executing the index update process accompanying the record move process,
The computer according to claim 2. When a record stored in a raw format is added, the processor unit stores a pointer to the record next to the last pointer of the first area,
The computer according to claim 1. When searching for a pointer from the first area, the processor unit searches while incrementing the pointer offset,
The computer according to claim 1. The logical space in which the database is stored is composed of multiple pages,
The processor unit acquires a lock in page units,
The first area is stored in one or more pages different from the one or more pages in which the second area is stored,
The computer according to claim 1. The processor unit is
When a pointer is stored in the second area, locks of all pages including the second area are acquired,
When a pointer is stored in the first area, a lock is acquired only on a page including a place where the pointer is stored among one or more pages including the first area,
The computer according to claim 6. The record that can be moved is each of two or more records stored in raw format,
The record that cannot be moved is each of a plurality of records stored in a column format,
The processor unit executes a conversion process for converting the storage format of the two or more records from a row format to a column format,
The conversion processing includes the record movement processing and the index update processing,
The computer according to claim 1. The processor unit stores records based on one or more collected data in raw format each time data is collected from a data source,
The processor unit executes the conversion process for converting the storage format of at least N records from a row format to a column format each time N or more records are accumulated.
The computer according to claim 8. The logical space in which the database is stored is composed of multiple pages,
For each key, the first area is stored on one or more pages other than the one or more pages on which the second area is stored,
The processor unit is
When a pointer is stored in the second area, locks of all pages including the second area are acquired,
When a pointer is stored in the first area, a lock is acquired only on a page including a place where the pointer is stored among one or more pages including the first area,
The computer according to claim 8. Performing a record move operation to move at least one record in said table of a database containing an index and a table,
With the record moving process, an index updating process for updating the index is executed,
The index update process includes overwriting the before-movement pointer in the index with the after-movement pointer for the record moved in the record movement process,
The pre-movement pointer is a pointer to a record at the storage position before the movement,
The after-movement pointer is a pointer to the record at the storage position after movement,
The index includes a plurality of nodes in a tree structure,
A pointer for each key is stored in one or more leaf nodes of the plurality of nodes,
The one or more leaf nodes are
A first area which is an area in which a pointer to a movable record corresponding to the key is stored and the pointer is not sorted in pointer order;
A second area which is an area in which a pointer to an immovable record corresponding to the key is stored and the pointer is sorted in pointer order,
Database management method. A computer program that causes a computer to execute the following (a) and (b):
(A) performing a record move process of moving at least one record in the table of the database including the index and the table,
(B) executing an index update process for updating the index along with the record movement process,
The index update process includes overwriting the before-movement pointer in the index with the after-movement pointer for the record moved in the record movement process,
The pre-movement pointer is a pointer to a record at the storage position before the movement,
The after-movement pointer is a pointer to the record at the storage position after movement,
The index includes a plurality of nodes in a tree structure,
A pointer for each key is stored in one or more leaf nodes of the plurality of nodes,
The one or more leaf nodes are
A first area which is an area in which a pointer to a movable record corresponding to the key is stored and the pointer is not sorted in pointer order;
A second area which is an area in which a pointer to an immovable record corresponding to the key is stored and the pointer is sorted in pointer order,
A computer-readable non-transitory recording medium on which is recorded.