JP4081236B2 - Database processing method - Google Patents

Description

[0001]
[Industrial application fields]
The present invention relates to high-speed database processing, and more particularly to a data processing technique applicable to a search engine and a cross tabulation data management system having a large number of key items.
[0002]
[Technical background]
The creation and management of databases using general-purpose computers has become difficult to handle with the conventionally known basic processing methods due to the increase in the number of data in recent years, and a technology that enables higher-speed arithmetic processing is desired. Yes.
[0003]
The technical difficulties in handling huge amounts of data are, for example, (1) the algorithm to be processed differs depending on the type of data to be handled, and (2) the basic principle of the processing method depending on whether or not to perform multidimensional processing. The difference is that (3) the algorithm (principle) to be used depends on the performance of the computer.
[0004]
Regarding (1), the processing technique differs depending on whether the data handled is mainly a character string or a number. For example, record data is created mainly with characters (Hiragana, Kanji, Katakana) such as department data, department name, name, gender, hobby, family structure, details of internal evaluation contents, etc. In the case of handling numerical data such as the number of units sold for each product name and the sales amount at each chain store, it is natural that the processing algorithm inside the computer is different. This is the basis of a database. For example, the construction method differs depending on the storage method of the basic record of data such as hierarchical type, relational type, and network type.
[0005]
The point {circle around (2)} is how to handle a huge data file record. For example, after performing arithmetic processing such as addition, subtraction, multiplication and division at the time of data creation and storing it in a memory as a simple record file, if you only need to perform processing such as calling and checking the record file at any time, The problem in this case is limited to speeding up the processing at the time of data creation. On the other hand, since it is not premised on what kind of processing is performed, only fact (facts; mainly numbers) data is recorded for the time being, and various processing (projection / selection / combination, etc.) is performed at a later date based on this fact file. If there is, the principle for data processing is naturally different, and it can be narrowed down to achieve faster key item retrieval and numerical aggregation, and to obtain free aggregation results at any item dimension at high speed. In that case, the creation of the basic record file is desired to be simpler.
[0006]
The point (3) is important in the correlation with the conventionally proposed patent technology and the database processing expected in the future. Regardless of the type of data, the data processing speed can be solved almost without any problem by using a large computer equipped with a large number of high-speed parallel CPUs or a huge memory. However, so-called supercomputers are extremely expensive, and an environment where they are always used cannot be expected at a general practical level. Rather, it is desired to use a current general-purpose computer to process a huge amount of record files (original data) at a highly responsive level and obtain a free multidimensional processing result that responds to any request.
[0007]
[Prior art]
An object of the present invention is to obtain a cross tabulation result in an arbitrary dimension in a short time by freely processing, for example, an enormous amount of original data files exceeding 1 million cases. In this case, the data file to be processed includes key items mainly including characters (in this specification, key values; store names, etc.) and key items mainly including numbers (in this specification, items; Will be handled.
[0008]
In other words, key items composed of character strings such as store names and product names, and key items composed of numbers such as the number of units sold and the amount of money are stored as recording files in a free format. The purpose is to obtain the total results immediately after processing.
[0009]
There are, of course, several proposals for database processing methods with such technical trends. First, as a processing method focused on the cross tabulation process, there is a technique for speeding up the process using a weight code (Japanese Patent Laid-Open No. 8-77266). This is because a weight code of a relatively low level is assigned to another table including the meaning of data of a certain table, and a necessary fact is extracted using the weight code when a search condition is given. . Specifically, when collecting data such as who, what, what was eaten, what the ingredients were, and how much the price was in the group, the name, date, menu, amount, material The meaning of the data is hierarchized and stored as fact data, and data in an appropriate hierarchical area is extracted using a weight code as necessary.
[0010]
However, since this technology associates the meaning of data up and down, as a general-purpose system, such as a self-reliable vertical relationship caused by the system designer's subjectivity, or the processing of items that cannot be associated originally becomes impossible It remains difficult to use.
[0011]
Secondly, although there is no direct purpose of cross tabulation processing, there are many techniques for high-speed keyword search from a large amount of character data. For example,
(1) Japanese Patent Laid-Open No. 11-031096 A technique for retrieving data without creating an index (2) A technique for creating a subordinate relationship of items of Japanese Patent Laid-Open No. 11-003354 and performing a search from the subordinate relationship (3) Japanese Patent Laid-Open No. 10- No. 143538 Index key value associating with data identifier (4) Japanese Patent Laid-Open No. 10-003414 A method for predefining and storing key values that are frequently used (5) Japanese Patent Laid-Open No. 9-167111 A technique for clustering key values. However, these techniques are suitable for obtaining an efficient result using a search key from a large amount of character data existing on the Internet, for example, but the depth of searching all hierarchical data files. There is no search capability, and if data is stored by the subjective operation of the operator, the system tends to be very inconvenient.
[0012]
Considering these data processing techniques, a conventional publicly known technique capable of freely processing original data can be cited as disclosed in JP-A-5-257774. This holds the search key value and the compressed IRN (index record number) in the memory, extracts the IRN from the search key value based on the search condition (key item specification), and uses the compressed IRN It is something to restore.
[0013]
[Problems to be solved by the invention]
The problem is the processing time when searching for items and performing cross tabulation processing.
Certainly, according to the technique disclosed in Japanese Patent Laid-Open No. 5-257774, when handling a relatively small number of original data of about several thousand to 10,000, any item can be searched at a relatively high speed using a compressed IRN. In addition, addition / subtraction / multiplication / division calculation of numbers corresponding to items can be processed at a relatively high speed. However, when there is a huge amount of original data, for example, when considering the case of continuously managing sales data for a large number of products reported in real time from each chain store over a long period of time, simply compress the IRN. Simply doing this will limit your processing power. This is because compression of IRN is mainly compression of facts (numbers), and compression processing is not performed on portions of character data (items) that may spread enormously, such as names of new products.
[0014]
Of course, the compression of the character data is easy, and the character data can also be compressed in the invention of JP-A-5-257774. However, the problem in that case is that there is no means for searching and restoring compressed character data at high speed. Therefore, in the invention of Japanese Patent Laid-Open No. 5-257774, only a few thousand records can be managed. For example, the power to process a huge number of original data exceeding 1 million at high speed from a free viewpoint. There is no waste.
[0015]
Therefore, the object of the present invention is to firstly store an enormous amount of original data consisting of a large number of key values and items efficiently, and secondly to be able to restore the original data at high speed based on the stored data. It is in.
[0016]
[Means for Solving the Problems]
In order to achieve the above object, a database processing method according to the present invention includes firstly a step of compressing a key value for each item based on original data, creating a compressed decompression index, and storing the compressed decompression index. And generating and storing a compression result set cache in which a compression key is written for each item.
Second, when a search condition is given, a step of searching (searching) a compression key based on the compression result set cache, and reading an original key value from the compression / decompression index based on the searched compression key. Stages. Note that, when a compression key is searched based on the compression result set cache, a multi-dimensional cross tabulation can be processed at a very high speed by creating a hierarchical structure of the compression keys.
[0017]
[Action]
The present invention performs the following processing in order to efficiently store a large amount of original data that is constantly added / updated and enable high-speed search (or aggregation) as needed.
[0018]
(1) A step of creating and storing a compression / decompression index by compressing a key value for each item based on original data. This is a process for processing and compressing original key values that are absolutely necessary at the time of actual multidimensional tabulation in a state where they can be searched and stored in a state where they can be quickly searched and restored. The compression / decompression index may be any conventionally known hierarchical means such as a P-tree hierarchical structure, a B-tree hierarchical structure, a T-tree hierarchical structure, or a hash hierarchical structure as a search hierarchical structure. A P-tree structure is preferable in terms of high-speed subsequent processing and retrieval.
[0019]
(2) A step of creating and storing a compression result set cache in which a compression key is written for each item based on a compression / decompression index. This is a processing stage for writing the compression key value obtained with the compression / decompression index of (1) for each item to realize the freedom of computation and the high speed of retrieval after the operation. By storing a large number of items (store name, product name, date, amount, etc.) using the compression key (node ID) obtained in the processing stage (1), the data capacity is significantly reduced and the storage efficiency is reduced. To optimize. In addition, the search efficiency is greatly improved by these processes.
[0020]
(3) When a search condition is given, the following processing is performed in addition to the processing of (1) and (2). That is, a step of retrieving a compression key based on the compression result set cache of (2). Since the search for the compression key can be performed at high speed, searching for a single item or a plurality of items is very easy, and a search engine can be created with a simple configuration. Further, in this processing stage, when the compressed key to be searched is processed with a hierarchical structure (claim 2), it becomes possible to perform summarization in an arbitrary dimension at a high speed in combination with the subsequent stage processing. Since the data of the compression result set cache is a compression key (node ID), the time required for creating the search hierarchy means is at most 1 second even in the current general-purpose computer. Although it is theoretically possible to restore the original data directly from the compression / decompression index (1) or the compression result set cache (2), the number of calls between the compressed data and the original data increases. For example, high-speed processing becomes difficult.
[0021]
(4) A step of reading the original key value from the compression / decompression index based on the searched compression key. The original key value included in the compression / decompression index (1) can be processed as data that can be restored at any time by searching the compression key (3). This is because the compression / decompression index is created for each item, and if the item is specified, the original key value is immediately restored.
[0022]
As described above, the present invention is provided with a compression / decompression index in which the key value is compressed for each item in the preceding stage, with the compression result set cache storing the compression key for each item as an essential condition. At the time of retrieval, the original key value is restored from the compression / decompression index after retrieving the compression key. Such a processing method increases the number of processing steps as compared with a conventional processing method such as multidimensional cross tabulation, but can efficiently store a large amount of data and reliably increase the processing speed at the time of execution. This is because the relationship between the two-stage compression processing and the generated file at each stage can be realized within the processing capability range of the general-purpose computer, and the amount of data handled at the time of search is dramatically reduced.
[0023]
DETAILED DESCRIPTION OF THE INVENTION
FIG. 1 shows the overall principle of a high-speed database processing method according to the present invention.
[0024]
1 is original data including many items, 10 is a compression / decompression index created based on the original data, 20 is a compression result set cache created based on the compression / decompression index 10, and 30 is a search condition C. This is a search hierarchical structure created based on the compression result set cache 20 when given.
[0025]
FIG. 2 illustrates the relationship between the original data 1 and the compression / decompression index 10. In this embodiment, the original data 1 has five items (columns) of store, date, product, quantity, and amount, and each item has a unique value (key value; column value). Further, in this embodiment, for example, the item is distinguished by setting the store as item 1, the date as item 2, and the merchandise as item 3. Taking the store A of item 1 as an example, this key value is the letter “A”. More specifically, when the store name is “Kasumigaseki Shoten”, the key value of this item is the character “Kasumigaseki Shoten”. Similarly, the key value of the date of the store “A” (item 2) is the numeric string “00, 04, 01”, and the key value of the product (item 3) is the character “1”. In this example, the product 1 is used, but in actuality, letters / numbers or the like constituting a specific trade name are key values. The original data 1 is received in various recording media or online transfer data formats, for example. Perform normal preprocessing to arrange the data format as needed.
[0026]
The compression / decompression index 10 created based on the original data 1 is created for each item. That is, the original key value is compressed and stored for the store in the case of item 1 and the date in the case of item 2. The compression / decompression index 10 created here is preferably provided with at least an original key value and a compression key, and has an appropriate hierarchical structure in order to ensure high speed at the time of decompression. For example, there are a P tree structure, a B tree structure, a T tree structure, a hash structure, and the like. Although these creation principles are known, a P-tree structure is desirable in terms of high speed. The created compression / decompression index is stored in an appropriate storage location (memory) of the server device. It is desirable to make it rewritable.
[0027]
By the way, various tree structures for search are conventionally known, but means for arranging an original key having an arbitrary data length in a search hierarchical structure has not been known. However, for example, the original key value is compressed and stored in each node based on the bit index evaluation method, and at the same time, the process of infinite bit length is achieved by processing the bit index evaluation order in ascending order from the LSB to the MSB of the bit stream. It becomes possible. Of course, when the bit length of each item to be handled is sufficiently short, it is not necessary to perform such processing.
[0028]
FIG. 3 is a diagram illustrating the relationship between the compression / decompression index 10 and the compression result set cache 20. The compression result set cache 20 is means for storing, for each item, a compression key value that can be acquired at the stage of creating the compression / decompression index 10. The compression key value of item 1 is written in the file of item 1 of the compression result set cache 20 shown in the figure. For example, the compression key value “0” corresponds to “Store A”, and the compression key value “1” corresponds to “Store B”. The file data of item 1 stores only item 1, but items 2, item 3,... Are written in the same manner in other files. The compression result set cache 20 is permanently stored in an appropriate storage field such as a server device. Note that it is desirable to be able to rewrite.
[0029]
FIG. 4 illustrates a search hierarchical structure 30 created based on the compression result set cache 20 when a certain search condition is given. This search hierarchical structure 30 is an indispensable processing step in the present invention that employs a runtime calculation method.
[0030]
The search hierarchical structure 30 creates a search hierarchical structure in an arbitrary dimension based on the compression key of each item constituting the compression result set cache 20. Since the compression key used here is an original key value that has been remarkably compressed in the preceding process, the hierarchical structure (30) can be created in a normal instant (1 second or less).
[0031]
Similar to the compression / decompression index 10, the search hierarchical structure 30 may be of any structure principle as long as the search reliability and high-speed conditions are satisfied. For example, a P tree structure, a B tree structure, a T tree structure, a hash structure, or the like can be used. However, considering the creation process and search efficiency, the P-tree structure is excellent at present.
[0032]
The search hierarchical structure 30 preferably has a function of simultaneously calling the compression keys of other items (for example, date and product) included in the designated condition based on the compression key of the item (for example, store). Of course, the essential function of the search hierarchical structure 30 is to access the compression / decompression index 10 from the created hierarchical structure (30) and restore the original key value. However, the simultaneous processing is not an absolute condition.
[0033]
However, since the amount of data handled at the time of creating the search hierarchical structure 30 is extremely small, other dimension items included in the specified condition are simultaneously called and placed in the hierarchical structure (total compressed item value), and required from the compression / decompression index 10 It is very easy to obtain a unique original key value.
[0034]
Therefore, according to such a high-speed processing method for a multi-dimensional database, a large number of items and key values that increase every time are accumulated through the creation stage of the compression result set cache 20, and can be tallied at any speed at any time. A feature of the present invention is that a compression / decompression index 10 is created from original data, and a compression result set cache for each item is created based on the index, and a compression result set cache is appropriately used when a search condition is given. Is created, and the compression / decompression index 10 having the original key value is accessed through this search hierarchy, and the original key value is reproduced at high speed.
[0035]
The flow of these processes constitutes the gist of the present invention, but the specific technique in other processing stages is not particularly limited except for the process of the compression result set cache 20 that files the compression key value for each item. For example, the compression / decompression index 10 only needs to be able to compress the original unique key value in an appropriate format, and the search hierarchical structure 30 also has an appropriate search structure depending on the nature of the compression key value included in the compression result set cache 20. Can be taken.
[0036]
If the form (data format) of the original data 1 to be subjected to compression processing is not unified in the present invention, the data format is set in the processing system according to the present invention prior to the creation of the compression / decompression index 10. It is desirable to convert to a format that can be handled.
[0037]
【The invention's effect】
As described above, according to the present invention, a huge number of record files can be efficiently stored, and high-speed search and cross tabulation in an arbitrary dimension can be realized at high speed.
[Brief description of the drawings]
FIG. 1 is a diagram showing the overall principle of a processing method according to the present invention.
FIG. 2 is a diagram illustrating creation of a compression / decompression index according to the present invention.
FIG. 3 is a diagram illustrating creation of a compressed result set cache according to the present invention.
FIG. 4 is a diagram illustrating creation of a search hierarchical structure according to the present invention.
[Explanation of symbols]
1 Original data 10 Compression / decompression index 20 Compression result set cache 30 Search hierarchical structure

Claims (2)

In a database processing method executed by a computer,
The computer acquires original data including a plurality of records having at least one item having a plurality of key values from a recording medium or as online transfer data, and the original data includes the plurality of items in the item. An ID is uniquely assigned to a key value, the key value and the ID are set as one node, a hierarchical structure composed of the nodes is created, and a node ID list having pointers to the nodes is created. Storing and storing a compressed / decompressed index comprising the node ID list and the hierarchical structure in a storage medium of the computer;
The computer replaces the key value in the item with the corresponding ID for each item of the original data based on the compression / decompression index, creates a compression result set cache, and stores the compression result set cache in a storage medium And storing and storing a compressed result set cache,
When the computer is given a search condition with an arbitrary ID, the computer searches for a matching ID in the compressed result set cache; and
The database processing method comprising: the computer searching the compression / decompression index based on the matched ID and reading the corresponding original key value. When a search condition is given to the computer to call a plurality of key values at the same time, the computer uniquely assigns an ID to the plurality of keys, and all IDs corresponding to the plurality of key values to be called at the same time are all assigned. Searching for the records we have,
The database processing method according to claim 1, further comprising: searching the compressed decompression index based on the retrieved record and reading the corresponding original key value.

Images