Pricing policies and query processing in the Mariposa agoric distributed database management syste

This thesis describes query processing in the Mariposa distributed database management system. Mariposa takes an approach to distributed query processing that is very different than traditional distributed database management systems. Traditional DDBMSs have included a distributed query optimizer, which determines all aspects of how a query will be processed, including the sites involved at each step. Because of the exponential growth in the solution space of distributed plans, the scalability of this approach is limited; the number of sites that can be included in such a system must remain relatively small, and factors which may drastically affect query processing performance have been ignored. These factors include uneven processor load, changing availability of computational resources such as memory and disk space, heterogeneous processor architecture, heterogeneous single-site DBMSs, and heterogeneous network capacity. Traditional distributed database management systems have also ignored practical considerations, such as user quality of service and administrative constraints on access to certain database servers. A new approach to distributed systems has arisen within the past fifteen years called agoric systems. An agoric system departs from the traditional centralized approach to distributed decision-making and distributed resource allocation by describing distributed systems in terms of economics. Each computing server is a seller of its services and sets its prices just as a vendor in any real-life marketplace would. Buyers in search of these services contact brokers, which match buyers and sellers. Agoric systems scale because the decision-making process, and therefore resource management, are themselves distributed.;Mariposa is an example of an agoric system. Servers in a Mariposa distributed database management system price their services and offer them for sale. Users, acting as consumers, express their preferences in terms of price and service to a broker, who is in charge of scheduling the distributed execution of the query by matching the consumer with the appropriate servers. This approach to distributed optimization and scheduling allows Mariposa to account for all of the factors listed above. A Mariposa site's behavior will adapt to changes in resource usage and user demands by raising or lowering its prices.;This thesis addresses the issues of load balancing, resource availability, heterogeneous systems, quality of service and administrative constraints by describing appropriate pricing policies for each one. The Mariposa system has been implemented and the pricing policies are validated experimentally. The performance studies are based on the TPC-D decision-support query benchmark. A Mariposa system which uses a very simplistic pricing mechanism to obtain load balancing is compared against a traditional distributed optimizer in a variety of situations. Mariposa is also compared to an algorithm which was designed to maximize pipelining parallelism and achieve load balancing in parallel shared-nothing environments. Pricing mechanisms that allow Mariposa to address heterogeneous environments and a population of users demanding different quality of service characteristics are described and validated experimentally.