Method and apparatus for processing data base

• US 4,967,341 A
• Filed: 10/06/1989
• Issued: 10/30/1990
• Est. Priority Date: 02/14/1986
• Status: Expired due to Term

• Current Assignee: Hitachi, Ltd.
• Original Assignee: Hitachi, Ltd.
• Inventors: Fukushima, Shinichi, Yamamoto, Akira, Yamashita, Yoshiaki, Tsuchida, Masashi, Kitajima, Hiroyuki, Satoh, Kazuhiro, Taniguchi, Nobuhiro, Ohmachi, Kazuhiko, Ohsone, Tadashi
• Primary Examiner(s): Lall, Parshotam S.
• Assistant Examiner(s): DIXON, JOSEPH L
• Application Number:
  US07/418,343
• Time in Patent Office: 389 Days
• Field of Search: 364/200, 364/300, 364/900
• US Class Current: 1/1
• CPC Class Codes: G06F 16/2456 Join operations
• CPC Class Codes: G06F 16/24561 Intermediate data storage techniques for performance improvement
• CPC Class Codes: Y10S 707/99932 Access augmentation or optimizing

Abstract

A set of sorted columns of one table stored in a DB machine are binary-searched by a hardware in synchronism with data transfer when another table is read from a disk unit, to select a row to be joined. Where a key word sequence to be searched is stored in ascending or descending order, determination of a maximum address in an area in which key words smaller than a search key are stored and determination of a maximum address in an area in which the key words smaller than or equal to the search key are stored are parallelly executed to determine the store range in one searching.

Claims

1. A method for processing a data base in an information processing system having a memory unit for storing tables each having columns and rows of data and at least one data base processing unit, comprising the steps of:

transferring a table from said data base to said memory unit and storing contents of columns of said table specified in an operation to be performed by said information processing system into an internal memory in said data base processing unit;

reading another table to be joined with said table from said data base; and

storing contents of columns of said another table to be joined with said table into said internal memory in said data base processing unit in synchronism with said reading step.

2. A method for processing a data base in an information processing system having a memory unit for storing tables each having columns and rows of data and at least one data base processing unit, comprising the steps of:

transferring a table from said data base to said memory unit and storing contents of columns of said table specified in an operation to be performed by said information processing system into an internal memory in said data base processing unit;

reading another table to be joined with said table from said data base;

storing contents of columns of said another table to be joined with said table into said internal memory in said data base processing unit in synchronism with said reading step; and

adding addresses of rows which cross said columns of said table transferred to said memory unit to said contents of said columns of said tables in said internal memory in said data base processing unit, said addresses being one of said memory unit storing said rows.

3. An apparatus for processing a data base having tables, each having columns and rows of data, in a computer system comprising:

(a) a CPU;

(b) a main memory unit for storing tables;

(c) an auxiliary memory unit for storing tables as said data base; and

(d) a data base processing unit connected to said CPU, said main memory unit and said auxiliary memory unit, including

(d-1) first means for transferring a table from said auxiliary memory unit to said main memory unit,

(d-2) second means for storing columns of said table specified in an operation to be performed by said apparatus into an internal memory in said data base processing unit,

(d-3) third means for reading another table to be joined with said table from said auxiliary memory unit, and

(d-4) fourth means for storing columns of said another table into said internal memory in said data base processing unit during the reading of said table by said third means.

4. An apparatus for processing a data base, in a computer system comprising:

(a) a CPU;

(b) a main memory unit for storing tables;

(c) an auxiliary memory unit for storing tables, each having columns and rows of data, as said data base; and

(d) a data base processing unit connected to said CPU, said main memory unit and said auxiliary memory unit, including

(d-1) first means for transferring a table from said auxiliary memory unit to said main memory unit, and

(d-2) second means for storing columns of said table specified in an operation to be performed by said apparatus into an internal memory in said data base processing unit,

(d-3) third means for reading another table to be joined with said table from said auxiliary memory unit, and

(d-4) fourth means for storing columns of said another table into said internal memory in said data base processing unit during the reading of said table by said third means; and

wherein said fourth means comprises

means for storing contents of columns of said table, which cross rows satisfying a specified condition and which are specified in an operation to be performed by said apparatus with columns in said another table to be joined with said table, into said internal memory in said data base processing unit during the reading of said another table by said third means.

5. An apparatus for processing a data base, having tables each including columns and rows of data, in a computer system comprising:

(a) a CPU;

(b) a main memory unit for storing tables;

(c) an auxiliary memory unit for storing tables as said data base;

(d) a data base processing unit connected to said CPU, said main memory unit and said auxiliary memory unit, including

(d-1) first means for transferring a table from said auxiliary memory unit to said main memory unit,

(d-2) second means for storing columns of said table specified in an operation to be performed by said apparatus into an internal memory in said data base processing unit,

(d-3) third means for reading another table to be joined with said table from said auxiliary memory unit, and

(d-4) fourth means for storing columns of said another table into said internal memory in said data base processing unit during the reading of said table by said third means; and

fifth means for adding addresses of rows which cross said columns of said table transferred to said main memory unit to said contents of said columns of said table in said internal memory in said data base processing unit, said addresses being ones of said main memory unit storing said rows.

6. An apparatus for processing a data base, having tables each including columns and rows of data, in a computer system comprising:

(a) a CPU;

(b) a main memory unit for storing tables;

(c) an auxiliary memory unit for storing tables as said data base;

(d) a data base processing unit connected to said CPU, said main memory unit and said auxiliary memory unit, including

(d-1) first means for transferring a table from said auxiliary memory unit to said main memory unit,

(d-2) second means for storing columns of said table specified in an operation to be performed by said apparatus into an internal memory in said data base processing unit,

(d-3) third means for reading another table to be joined with said table from said auxiliary memory unit, and

(d-4) fourth means for storing columns of said another table into said internal memory in said data base processing unit during the reading of said table by said third means; and

sixth means for transferring contents of said columns of said table and said another table from said internal memory in said data base processing unit to said main memory unit.

7. An apparatus for processing a data base, having tables each including columns and rows of data, in a computer system comprising:

(a) a CPU;

(b) a main memory unit for storing tables;

(c) an auxiliary memory unit for storing tables as said data base;

(d) a data base processing unit connected to said CPU, said main memory unit and said auxiliary memory unit, including

(d-1) first means for transferring a table from said auxiliary memory unit to said main memory unit,

(d-2) second means for storing columns of said table specified in an operation to be performed by said apparatus into an internal memory in said data base processing unit,

(d-3) third means for reading another table to be joined with said table from said auxiliary memory unit, and

(d-4) fourth means for storing columns of said another table into said internal memory in said data base processing unit during the reading of said table by said third means;

seventh means for executing an operation, specified by said apparatus, between specified columns of said another table and said columns stored in said internal memory in said data base processing unit in synchronism with reading said another table from said auxiliary memory unit, said operation being executed row by row; and

eighth means for storing specified columns crossing rows for which the execution result of said operation satisfies a condition specified by said apparatus into said internal memory in said data base processing unit.

8. An apparatus for processing a data base according to claim 7, wherein said eighth means comprises:

means for transferring contents of said specified columns stored in said internal memory to said main memory unit.

9. An apparatus for processing a data base according to claim 8, further comprising:

means for storing columns of said another table, which are specified in an operation with columns of said table to be joined with said another table, and cross-rows for which the execution result of said operation satisfies a condition specified by said apparatus into said internal memory in said data base processing unit.

10. An apparatus for processing a data base, having tables each including columns and rows of data, in a computer system comprising:

(a) a CPU;

(b) a main memory unit for storing tables;

(c) an auxiliary memory unit for storing tables as said data base;

(d) a data base processing unit connected to said CPU, said main memory unit and said auxiliary memory unit, including

(d-1) first means for transferring a table from said auxiliary memory unit to said main memory unit,

(d-2) second means for storing columns of said table specified in an operation to be performed by said apparatus into an internal memory in said data base processing unit,

(d-3) third means for reading another table to be joined with said table from said auxiliary memory unit, and

(d-4) fourth means for storing columns of said another table into said internal memory in said data base processing unit during the reading of said table by said third means; and

ninth means for sorting data of said columns of said table stored in said internal memory of said data base processing unit.

11. An apparatus for processing a data base according to claim 10, further comprising:

tenth means for adding addresses of said specified columns crossing rows for which the execution result of said operation satisfies a condition specified by said apparatus in said main memory unit to said contents of said columns in said internal memory in said data base processing unit, said address being ones of said main memory unit.

12. A search method of a key word from a key word sequence stored in ascending order in a memory, comprising the steps of:

inputting a search key;

determining a first maximum address of said memory in which a key word which is smaller than said search key is stored;

determining a second maximum address of said memory in which a key word which is not larger than said search key is stored; and

outputting said first and second maximum addresses of said memory as an address range in which a key word in said key word sequence matching said search key is stored.

13. A search method of a key word from a key word sequence stored in descending order in a memory, comprising the steps of:

inputting a search key;

determining a first maximum address of said memory having stored therein a key word that is larger than said search key;

determining a second maximum address of said memory n which a key word which is not smaller than said search key is stored; and

outputting said first and second maximum addresses of said memory as an address range in which a key word in said key word sequence matching said search key is stored.

14. A search system comprising:

a search key buffer for inputting a search key;

a first relative address register, designating said search key buffer, in which all m bits are initialized with zero and in which bits designated by said system are setable bit by bit from the most significant bit to the least significant bit;

first means for comparing said search key in said search key buffer with a key word which is stored in a search buffer in ascending order designated by said first relative address register, for outputting "1", when said search key is smaller than said key word stored in said search buffer, to a designated bit of said first relative address register;

a second relative address register, designating said search key buffer, in which all m bits are initialized with zero and in which bits designated by said system are setable bit by bit from the most significant to the least significant bit;

second means for comparing said search key in said search key buffer with a key word which is stored in a search buffer designated by said second relative address register and for outputting "1", when said search key is not larger than said key word stored in said search buffer, to a designated bit of said second relative address register; and

means for outputting contents of said first and second relative address registers.

15. A search system comprising:

a search key buffer for inputting a search key;

a first relative address register, designating said search key buffer, in which all m bits are initialized with zero and in which bits designated by said system are setable bit by bit from the most significant bit to the least significant bit;

first means for comparing said search key in said search key buffer with a key word which is stored in a search buffer in descending order designated by said first relative address register and for outputting "1", when said search key is smaller than said key word stored in said search buffer, to a designated bit of said first relative address register;

a second relative address register, designating said search key buffer, in which all m bits are initialized with zero and in which bits designated by said system are setable bit by bit from the most significant bit to the least significant bit;

second means for comparing said search key in said search key buffer with a key word which is stored in a search buffer designated by said second relative address register and for outputting "1", when said search key is not larger than said key word stored in said search buffer, to a designated bit of said second relative address register; and

means for outputting contents of said first and second relative address registers.