Automated query optimization method using both global and parallel local optimizations for materialization access planning for distributed databases

A machine implemented method for automatically determining an optimal execution strategy for a request comprising query, update or transaction operations on a distributed database system having a plurality of data site, with each site having a computer and data storage facility, and said sites are interconnected by communication lines, said machine implemented method comprising the steps of:

• A. inputting an ad hoc relational query or update request from a first computer process that formulates the relational query or update request as a compacted tree having lead nodes that are select, project or join operators and non-leaf nodes that are union, intersection, difference, delete, modify or insert operators to a second computer process which thereafter performs step B;
• B. for each node in the compacted tree perform the following starting at the root node:
• 1. if the current node is a leaf node perform the following:
• a. materialization planning to choose the data sites from which data is to be accessed;
• b. local process planning to determine which operations can be processed locally at each site determined by materialization planning and estimate parameters of resultant data from the local operations;
• c. non-local process planning to determine strategy for remaining operations which can not be performed locally without transmission of data between sites;
• d. execution strategy building to build an execution strategy for each data site in the distributed database system at which data is processed by access or manipulation;
• 2.