Database management system and method

• US 9,177,027 B2
• Filed: 06/20/2012
• Issued: 11/03/2015
• Est. Priority Date: 07/22/2005
• Status: Active Grant

• Current Assignee: Kazuo Goda, Masaru Kitsuregawa
• Original Assignee: Masaru Kitsuregawa
• Inventors: Kitsuregawa, Masaru, Goda, Kazuo
• Primary Examiner(s): Badawi, Sherief
• Assistant Examiner(s): Raab, Christopher J
• Application Number:
  US13/527,951
• Publication Number:
  US 20120259838A1
• Time in Patent Office: 1,231 Days
• Field of Search: 707/713, 707/718, 707/764
• US Class Current: 1/1
• CPC Class Codes: G06F 16/24524 Access plan code generation and invalidation; Reuse of access plans
• CPC Class Codes: G06F 16/24542 Plan optimisation
• CPC Class Codes: G06F 16/24549 Run-time optimisation
• CPC Class Codes: G06F 16/24566 Recursive queries

Abstract

A database management system has a query interface for receiving a query and a query executor for executing the received query. The query executor dynamically generates a task, and executes a plurality of tasks in parallel. In execution of each task, each time data is required to be read from a database, the query executor generates a task for acquiring the data, and in execution of the generated task, issues a data read request for reading the data from the database, to thereby shorten a time taken to execute each task.

Claims

1. A database management system for managing a database, comprising:

a query interface for receiving a query to said database;

a query plan generator connected with said query interface for generating a query plan from said received query, said generated query plan comprising a plurality of database operations necessary for execution of said received query; and

at least one hardware processor connected with said database and said query plan generator for executing said received query in accordance with said generated query plan,

wherein said at least one hardware processor;

executes the following steps for executing said received query;

(A) a step of generating a task for executing a database operation associated to said task and starting to execute said generated task, (B) a step of issuing a data read request to a storage device storing said database to read data necessary for executing said database operation in executing said generated task, (C) when a plurality of tasks can be generated, in accordance with a result of execution of said database operation, for a next database operation which is necessary for executing said received query, a step of generating said plurality of tasks in accordance with said result of execution of said database operation, and (D) a step of recursively executing steps (B) and (C) for each of said plurality of tasks generated in step (C);

whereby parallel processing of at least two tasks of said plurality of tasks generated in recursive execution of steps (B) and (C) is performed; and

after issuing said data read requests for said generated tasks in step (B), suspends execution of said generated tasks and thereafter, upon completion of data read of said data read requests, resumes execution of said generated tasks for starting to execute said database operations associated to said generated tasks with said read data for said generated tasks in the same order that the at least one hardware processor issues said data read requests.

2. A database management system for managing a database according to claim 1,

wherein, in resuming execution of a respective task of said generated tasks, resumes execution of said respective task of said generated tasks if the at least one hardware processor has not suspended execution of any task for which the at least one hardware processor issues a data read request before the at least one hardware processor issues said data read request for said respective task of said generated tasks.

3. A database management method for managing a database in a database management system connected to said database via a network, comprising:

a step of receiving a query to said database;

a step of generating a query plan from said received query, said generated query plan comprising a plurality of database operations necessary for execution of said received query;

a step of executing said received query in accordance with said generated query plan;

a step of executing the following steps for executing said received query;

(A) a step of generating a task for executing a database operation associated to said task and starting to execute said generated task, (B) a step of issuing a data read request to a storage device storing said database to read data necessary for executing said database operation in executing said generated task, (C) when a plurality of tasks can be generated, in accordance with a result of execution of said database operation, for a next database operation which is necessary for executing said received query, a step of generating said plurality of tasks in accordance with said result of execution of said database operation, and (D) a step of recursively executing steps (B) and (C) for each of said plurality of tasks generated in step (C);

a step of performing parallel processing of at least two tasks of said plurality of tasks generated in recursive execution of steps (B) and (C); and

a step of, after issuing said data read requests for said generated tasks in step (B), suspending execution of said generated tasks and thereafter, upon completion of data read of said data read requests, resuming execution of said generated tasks for starting to execute said database operations associated to said generated tasks with said read data for said generated tasks in the same order that said data read requests are issued.

4. A database management method according to claim 3, further comprising:

a step of, in resuming execution of a respective task of said generated tasks, resuming execution of said respective task of said generated tasks if execution of any task for which a data read request is issued before said data read request is issued for said respective task of said generated tasks has not been suspended.

5. A database management system for managing a database, comprising:

a query interface for receiving a query to said database;

a query plan generator connected with said query interface for generating a query plan from said received query, said generated query plan comprising at least first, second and third database operations and a sequence thereof necessary for execution of said received query; and

at least one hardware processor connected with said database and said query plan generator for executing said received query in accordance with said generated query plan,

wherein said at least one hardware processor;

generates a first task for executing a first database operation of said sequence of said database operations, starts to execute said first task, and issues a data read request to a storage device storing said database to read data necessary for said first database operation to be executed for said first task;

after executing said first database operation for said first task, when a plurality of second tasks can be generated, in accordance with a result of execution of said first database operation executed for said first task, for a second database operation of said sequence of said database operations, generates said plurality of second tasks, each second task for executing said second database operation in accordance with said result of execution of said first database operation, starts to execute each of said plurality of second tasks, and issues a data read request to said storage device storing said database to read data necessary for said second database operation to be executed for each of said plurality of second tasks in accordance with said result of execution of said first database operation executed for said first task;

after executing said second database operation for said one of said plurality of second tasks, when a plurality of third tasks can be generated, in accordance with a result of execution of said second database operation executed for said one of said plurality of second tasks, for a third database operation of said sequence of said database operations, generates said plurality of third tasks, each third task for executing said third database operation in accordance with said result of execution of said second database operation, starts to execute each of said plurality of third tasks, and issues a data read request to said storage device storing said database to read data necessary for said third database operation to be executed for each of said plurality of third tasks in accordance with said result of execution of said second database operation executed for said one of said plurality of second tasks;

executes in parallel at least two tasks of said plurality of generated first, second and third tasks; and

after issuing said data read requests for said generated tasks, suspends execution of said generated tasks and thereafter, upon completion of data read of said data read requests, resumes execution of said generated tasks for starting to execute said database operations associated to said generated tasks with said read data for said generated tasks in the same order that the at least one hardware processor issues said data read requests.

6. A database management system for managing a database, comprising:

a query interface for receiving a query to said database;

a query plan generator connected with said query interface for generating a query plan from said received query, said generated query plan comprising at least first, second and third database operations and a sequence thereof necessary for execution of said received query; and

at least one hardware processor connected with said database and said query plan generator for executing said received query in accordance with said generated query plan,

wherein said at least one hardware processor;

generates a first task for executing a first database operation of said sequence of said database operations, starts to execute said first task, and issues a data read request to a storage device storing said database to read data necessary for said first database operation to be executed for said first task;

after executing said first database operation for said first task, when a plurality of second tasks can be generated, in accordance with a result of execution of said first database operation executed for said first task, for a second database operation of said sequence of said database operations, generates said plurality of second tasks, each second task for executing said second database operation in accordance with said result of execution of said first database operation, starts to execute each of said plurality of second tasks, and issues a data read request to said storage device storing said database to read data necessary for said second database operation to be executed for each of said plurality of second tasks in accordance with said result of execution of said first database operation executed for said first task;

after executing said second database operation for said one of said plurality of second tasks, when a plurality of third tasks can be generated, in accordance with a result of execution of said second database operation executed for said one of said plurality of second tasks, for a third database operation of said sequence of said database operations, generates said plurality of third tasks, each third task for executing said third database operation in accordance with said result of execution of said second database operation, starts to execute each of said plurality of third tasks, and issues a data read request to said storage device storing said database to read data necessary for said third database operation to be executed for each of said plurality of third tasks in accordance with said result of execution of said second database operation executed for said one of said plurality of second tasks;

after issuing said data read request for said generated task, suspends execution of said generated task, and thereafter, upon completion of data read of said data read request issued for said generated task, resumes execution of said generated task for starting to execute said database operation associated to said generated task with said read data for said generated task if the at least one hardware processor has not suspended execution of any task for which the at least one hardware processor issues a data read request before the at least one hardware processor issues said data read request for said generated task; and

executes in parallel at least two tasks of said plurality of generated first, second and third tasks.

7. A database management method for a database management system connected to a database via a network, comprising:

a step of receiving a query to said database;

a step of generating a query plan from said received query, said generated query plan comprising at least first, second and third database operations and a sequence thereof necessary for execution of said received query;

a step of executing said received query in accordance with said generated query plan;

a step of generating a first task for executing a first database operation of said sequence of said database operations, starting to execute said first task, and issuing a data read request to a storage device storing said database to read data necessary for said first database operation to be executed for said first task;

a step of, after executing said first database operation for said first task, when a plurality of second tasks can be generated, in accordance with a result of execution of said first database operation executed for said first task, for a second database operation of said sequence of said database operations, generating said plurality of second tasks, each second task for executing a second database operation in accordance with said result of execution of said first database operation, starting to execute each of said plurality of second tasks, and issuing a data read request to said storage device storing said database to read data necessary for said second database operation to be executed for each of said plurality of second tasks in accordance with said result of execution of said first database operation executed for said first task;

a step of, after executing said second database operation for said one of said plurality of second tasks, when a plurality of third tasks can be generated, in accordance with a result of execution of said second database operation executed for said one of said plurality of second tasks, for a third database operation of said sequence of said database operations, generating said plurality of third tasks, each third task for executing said third database operation in accordance with said result of execution of said second database operation, starting to execute each of said plurality of third tasks, and issuing a data read request to said storage device storing said database to read data necessary for said third database operation to be executed for each of said plurality of third tasks in accordance with said result of execution of said second database operation executed for said one of said plurality of second tasks;

a step of executing in parallel at least two tasks of said plurality of generated first, second and third tasks; and

a step of, after issuing said data read requests for said generated tasks in step (B), suspending execution of said generated tasks and thereafter, upon completion of data read of said data read requests, resuming execution of said generated tasks for starting to execute said database operations associated to said generated tasks with said read data for said generated tasks in the same order that said data read requests are issued.

8. A database management method for a database management system connected to a database via a network, comprising:

a step of receiving a query to said database;

a step of generating a query plan from said received query, said generated query plan comprising at least first, second and third database operations and a sequence thereof necessary for execution of said received query;

a step of executing said received query in accordance with said generated query plan;

a step of generating a first task for executing a first database operation of said sequence of said database operations, starting to execute said first task, and issuing a data read request to a storage device storing said database to read data necessary for said first database operation to be executed for said first task;

a step of, after executing said first database operation for said first task, when a plurality of second tasks can be generated, in accordance with a result of execution of said first database operation executed for said first task, for a second database operation of said sequence of said database operations, generating said plurality of second tasks, each second task for executing a second database operation in accordance with said result of execution of said first database operation, starting to execute each of said plurality of second tasks, and issuing a data read request to said storage device storing said database to read data necessary for said second database operation to be executed for each of said plurality of second tasks in accordance with said result of execution of said first database operation executed for said first task;

a step of, after executing said second database operation for said one of said plurality of second tasks, when a plurality of third tasks can be generated, in accordance with a result of execution of said second database operation executed for said one of said plurality of second tasks, for a third database operation of said sequence of said database operations, generating said plurality of third tasks, each third task for executing said third database operation in accordance with said result of execution of said second database operation, starting to execute each of said plurality of third tasks, and issuing a data read request to said storage device storing said database to read data necessary for said third database operation to be executed for each of said plurality of third tasks in accordance with said result of execution of said second database operation executed for said one of said plurality of second tasks;

a step of, after issuing said data read request for said generated task, suspending execution of said generated task, and thereafter, upon completion of data read of said data read request issued for said generated task, resuming execution of said generated task for starting to execute said database operation associated to said generated task with said read data for said generated task if execution of any task for which a data read request is issued before said data read request is issued for said generated task has not been suspended; and

a step of executing in parallel at least two tasks of said plurality of generated first, second and third tasks.

9. A database management system for managing a database, comprising:

a query interface for receiving a query to said database;

a query plan generator connected with said query interface for generating a query plan from said received query, said generated query plan comprising a plurality of database operations necessary for execution of said received query; and

at least one hardware processor connected with said database and said query plan generator for executing said received query in accordance with said generated query plan,

wherein said at least one hardware processor;

executes the following steps for executing said received query;

(A) a step of generating a task for executing a database operation associated to said task and starting to execute said generated task, (B) a step of issuing a data read request to a storage device storing said database to read data necessary for executing said database operation in executing said generated task, (C) when a plurality of tasks can be generated, in accordance with a result of execution of said database operation, for a next database operation which is necessary for executing said received query, a step of generating said plurality of tasks in accordance with said result of execution of said database operation, and (D) a step of recursively executing steps (B) and (C) for each of said plurality of tasks generated in step (C); and

upon completion of data read of said data read request issued by said generated task in step (B), executes said database operation associated to said generated task with said read data for said generated task and thereafter eliminates said generated task,

whereby parallel processing of at least two tasks of said plurality of tasks generated in recursive execution of steps (B) and (C) for said received query is performed.

10. A database management system for managing a database, comprising:

a query interface for receiving a query to said database;

a query plan generator for generating a query plan from said received query, said generated query plan comprising a plurality of database operations necessary for execution of said received query; and

at least one hardware processor for executing said received query in accordance with said generated query plan,

wherein said at least one hardware processor;

executes the following steps for executing said received query;

(A) a step of generating a task for executing a database operation and starting to execute said generated task, (B) a step of issuing a data read request to a storage device storing said database to read data necessary for executing said database operation in executing said generated task, (C) when a plurality of tasks can be generated in accordance with a result of execution of said database operation, for a next database operation which is necessary for executing said received query, a step of generating said plurality of tasks in accordance with said result of execution of said database operation, and (D) a step of recursively executing steps (B) and (C) for each of said plurality of tasks generated in step (C),

whereby parallel processing of at least two tasks of said plurality of tasks generated in recursive execution of steps (B) and (C) is performed.

11. A database management method for managing a database in a database management system connected to said database via a network, comprising:

a step of receiving a query to said database;

a step of generating a query plan from said received query, said generated query plan comprising a plurality of database operations necessary for execution of said received query;

a step of executing said received query in accordance with said generated query plan;

a step of executing the following steps for executing said received query;

(A) a step of generating a task for executing a database operation associated to said task and starting to execute said generated task, (B) a step of issuing a data read request to a storage device storing said database to read data necessary for executing said database operation in executing said generated task, (C) when a plurality of tasks can be generated, in accordance with a result of execution of said database operation, for a next database operation which is necessary for executing said received query, a step of generating said plurality of tasks in accordance with said result of execution of said database operation, and (D) a step of recursively executing steps (B) and (C) for each of said plurality of tasks generated in step (C);

a step of, upon completion of data read of said data read request issued by said generated task in step (B), executing said database operation associated to said generated task with said read data for said generated task and thereafter eliminating said generated task; and

a step of performing parallel processing of at least two tasks of said plurality of tasks generated in recursive execution of steps (B) and (C).

12. A database management method for managing a database in a database management system connected to said database via a network, comprising:

a step of receiving a query to said database;

a step of generating a query plan from said received query, said generated query plan comprising a plurality of database operations necessary for execution of said received query;

a step of executing said received query in accordance with said generated query plan;

a step of executing the following steps for executing said received query;

(A) a step of generating a task for executing a database operation and starting to execute said generated task, (B) a step of issuing a data read request to a storage device storing said database to read data necessary for executing said database operation in executing said generated task, (C) when a plurality of tasks can be generated, in accordance with a result of execution of said database operation, for a next database operation which is necessary for executing said received query, a step of generating said plurality of tasks in accordance with said result of execution of said database operation, and (D) a step of recursively executing steps (B) and (C) for each of said plurality of tasks generated in step (C); and

a step of performing parallel processing of at least two tasks of said plurality of tasks generated in recursive execution of steps (B) and (C).

13. One or more non-transitory computer-readable media maintaining instructions that, when executed by one or more processors, program the one or more processors to:

receive a query to said database;

generate a query plan from said received query, said generated query plan comprising a plurality of database operations necessary for execution of said received query;

execute said received query in accordance with said generated query plan;

execute the following steps for executing said received query;

(A) a step of generating a task for executing a database operation associated to said task and starting to execute said generated task, (B) a step of issuing a data read request to a storage device storing said database to read data necessary for executing said database operation in executing said generated task, (C) when a plurality of tasks can be generated, in accordance with a result of execution of said database operation, for a next database operation which is necessary for executing said received query, a step of generating said plurality of tasks in accordance with said result of execution of said database operation, and (D) a step of recursively executing steps (B) and (C) for each of said plurality of tasks generated in step (C);

perform parallel processing of at least two tasks of said plurality of tasks generated in recursive execution of steps (B) and (C); and

after issuing said data read requests for said generated tasks in step (B), suspend execution of said generated tasks and thereafter, upon completion of data read of said data read requests, resume execution of said generated tasks for starting to execute said database operations associated to said generated tasks with said read data for said generated tasks in the same order that said data read requests are issued.

14. One or more non-transitory computer-readable media according to 13, further maintaining instructions that, when executed by one or more processors, program the one or more processors to:

in resuming execution of a respective task of said generated tasks, resume execution of said respective task of said generated tasks if execution of any task for which a data read request is issued before said data read request is issued for said respective task of said generated tasks has not been suspended.

15. One or more non-transitory computer-readable media maintaining instructions that, when executed by one or more processors, program the one or more processors to:

receive a query to said database;

generate a query plan from said received query, said generated query plan comprising at least first, second and third database operations and a sequence thereof necessary for execution of said received query;

execute said received query in accordance with said generated query plan;

generate a first task for executing a first database operation of said sequence of said database operations, starting to execute said first task, and issuing a data read request to a storage device storing said database to read data necessary for said first database operation to be executed for said first task;

after executing said first database operation for said first task, when a plurality of second tasks can be generated, in accordance with a result of execution of said first database operation executed for said first task, for a second database operation of said sequence of said database operations, generate said plurality of second tasks, each second task for executing a second database operation in accordance with said result of execution of said first database operation, start to execute each of said plurality of second tasks, and issue a data read request to said storage device storing said database to read data necessary for said second database operation to be executed for each of said plurality of second tasks in accordance with said result of execution of said first database operation executed for said first task;

after executing said second database operation for said one of said plurality of second tasks, when a plurality of third tasks can be generated, in accordance with a result of execution of said second database operation executed for said one of said plurality of second tasks, for a third database operation of said sequence of said database operations, generate said plurality of third tasks, each third task for executing said third database operation in accordance with said result of execution of said second database operation, start to execute each of said plurality of third tasks, and issue a data read request to said storage device storing said database to read data necessary for said third database operation to be executed for each of said plurality of third tasks in accordance with said result of execution of said second database operation executed for said one of said plurality of second tasks;

execute in parallel at least two tasks of said plurality of generated first, second and third tasks; and

after issuing said data read requests for said generated tasks in step (B), suspend execution of said generated tasks and thereafter, upon completion of data read of said data read requests, resume execution of said generated tasks for starting to execute said database operations associated to said generated tasks with said read data for said generated tasks in the same order that said data read requests are issued.

16. One or more non-transitory computer-readable media maintaining instructions that, when executed by one or more processors, program the one or more processors to:

receive a query to said database;

generate a query plan from said received query, said generated query plan comprising at least first, second and third database operations and a sequence thereof necessary for execution of said received query;

execute said received query in accordance with said generated query plan;

generate a first task for executing a first database operation of said sequence of said database operations, start to execute said first task, and issue a data read request to a storage device storing said database to read data necessary for said first database operation to be executed for said first task;

after executing said first database operation for said first task, when a plurality of second tasks can be generated, in accordance with a result of execution of said first database operation executed for said first task, for a second database operation of said sequence of said database operations, generate said plurality of second tasks, each second task for executing a second database operation in accordance with said result of execution of said first database operation, start to execute each of said plurality of second tasks, and issue a data read request to said storage device storing said database to read data necessary for said second database operation to be executed for each of said plurality of second tasks in accordance with said result of execution of said first database operation executed for said first task;

after executing said second database operation for said one of said plurality of second tasks, when a plurality of third tasks can be generated, in accordance with a result of execution of said second database operation executed for said one of said plurality of second tasks, for a third database operation of said sequence of said database operations, generate said plurality of third tasks, each third task for executing said third database operation in accordance with said result of execution of said second database operation, start to execute each of said plurality of third tasks, and issue a data read request to said storage device storing said database to read data necessary for said third database operation to be executed for each of said plurality of third tasks in accordance with said result of execution of said second database operation executed for said one of said plurality of second tasks;

after issuing said data read request for said generated task, suspend execution of said generated task, and thereafter, upon completion of data read of said data read request issued for said generated task, resume execution of said generated task for starting to execute said database operation associated to said generated task with said read data for said generated task if execution of any task for which a data read request is issued before said data read request is issued for said generated task has not been suspended; and

execute in parallel at least two tasks of said plurality of generated first, second and third tasks.

17. One or more non-transitory computer-readable media maintaining instructions that, when executed by one or more processors, program the one or more processors to:

receive a query to said database;

generate a query plan from said received query, said generated query plan comprising a plurality of database operations necessary for execution of said received query;

execute said received query in accordance with said generated query plan;

execute the following steps for executing said received query;

(A) a step of generating a task for executing a database operation associated to said task and starting to execute said generated task, (B) a step of issuing a data read request to a storage device storing said database to read data necessary for executing said database operation in executing said generated task, (C) when a plurality of tasks can be generated, in accordance with a result of execution of said database operation, for a next database operation which is necessary for executing said received query, a step of generating said plurality of tasks in accordance with said result of execution of said database operation, and (D) a step of recursively executing steps (B) and (C) for each of said plurality of tasks generated in step (C);

upon completion of data read of said data read request issued by said generated task in step (B), execute said database operation associated to said generated task with said read data for said generated task and thereafter eliminating said generated task; and

perform parallel processing of at least two tasks of said plurality of tasks generated in recursive execution of steps (B) and (C).

18. One or more non-transitory computer-readable media maintaining instructions that, when executed by one or more processors, program the one or more processors to:

receive a query to said database;

generate a query plan from said received query, said generated query plan;

comprising a plurality of database operations necessary for execution of said received query;

execute said received query in accordance with said generated query plan;

execute the following steps for executing said received query;

(A) a step of generating a task for executing a database operation and starting to execute said generated task, (B) a step of issuing a data read request to a storage device storing said database to read data necessary for executing said database operation in executing said generated task, (C) when a plurality of tasks can be generated, in accordance with a result of execution of said database operation, for a next database operation which is necessary for executing said received query, a step of generating said plurality of tasks in accordance with said result of execution of said database operation, and (D) a step of recursively executing steps (B) and (C) for each of said plurality of tasks generated in step (C); and

perform parallel processing of at least two tasks of said plurality of tasks generated in recursive execution of steps (B) and (C).