Nội dung được dịch bởi AI, chỉ mang tính chất tham khảo
Ước lượng tính chọn lọc nhất quán thông qua entropy tối đa
Tóm tắt
Các bộ tối ưu truy vấn dựa trên chi phí cần ước lượng tính chọn lọc của các phép toán liên hợp khi so sánh các kế hoạch thực thi truy vấn thay thế. Để đạt được điều này, các bộ tối ưu nâng cao sử dụng thống kê đa biến để cải thiện thông tin về phân phối đồng thời của các giá trị thuộc tính trong một bảng. Phân phối đồng thời cho tất cả các cột gần như luôn quá lớn để lưu trữ hoàn toàn, và việc sử dụng thông tin phân phối một phần dẫn đến khả năng có thể có nhiều ước lượng tính chọn lọc không tương đương cho một phép toán nhất định. Các bộ tối ưu hiện tại sử dụng các phương pháp ad hoc khó sử dụng để đảm bảo rằng các ước lượng được thực hiện một cách nhất quán. Những phương pháp này bỏ qua thông tin quý giá và có xu hướng thiên lệch bộ tối ưu về các kế hoạch truy vấn mà trong đó thông tin ít nhất có sẵn, thường dẫn đến kết quả kém. Trong bài báo này, chúng tôi trình bày một phương pháp mới cho việc ước lượng tính chọn lọc nhất quán dựa trên nguyên lý entropy tối đa (ME). Phương pháp của chúng tôi khai thác tất cả thông tin có sẵn và tránh vấn đề thiên lệch. Trong trường hợp thiếu thông tin chi tiết, phương pháp ME giảm về các giả định đồng nhất và độc lập tiêu chuẩn. Các thí nghiệm với việc triển khai thử nghiệm của chúng tôi trên DB2 UDB cho thấy việc sử dụng phương pháp ME có thể cải thiện ước lượng số lượng của bộ tối ưu lên nhiều bậc, dẫn đến chất lượng kế hoạch tốt hơn và thời gian thực thi truy vấn giảm đáng kể. Đối với hầu hết các truy vấn, những cải tiến này đạt được trong khi chỉ thêm vài chục mili giây vào tổng thời gian cần thiết cho việc tối ưu truy vấn.
Từ khóa
Tài liệu tham khảo
Aboulnaga, A., Chaudhuri, S.: Self-tuning histograms: Building histograms without looking at data. SIGMOD 181–192 (1999)
Aboulnaga, A., Haas, P., Lightstone, S., et al.: Automated statistics collection in DB2 UDB. VLDB 1146–1157 (2004)
Ault, M., Tumma, M., Liu, D., et al.: Oracle Database 10 g new features: Oracle10 g reference for advanced tuning and administration. Rampant TechPress (2003)
Bruno, N., Chaudhuri, S., Gravano, L.: STHoles: a multidimensional workload-aware histogram. SIGMOD 211–222 (2001)
Bruno, N., Chaudhuri, S.: Exploiting statistics on query expressions for optimization. SIGMOD 263–274 (2002)
Bruno, N., Chaudhuri, S.: Efficient creation of statistics over query expressions. ICDE 201–212 (2003)
Bruno, N., Chaudhuri, S.: Conditional selectivity for statistics on query expressions. SIGMOD 311–322 (2004)
Chaudhuri, S., Narasayya, V.: Automating statistics management for query optimizers. ICDE 339–348 (2000)
Chiu D., Wong A., Cheung B. (1991): Information discovery through hierarchical maximum-entropy discretization and synthesis. In: Piatesky-Shapiro G., Fracley W.J., (eds). Knowledge Discovery in Databases. MIT Press, Cambridge, pp. 125–140
Christodoulakis S. (1983): Estimating record selectivities. Inf. Syst. 8(2):105–115
Darroch J.N., Ratcliff D. (1972): Generalized iterative scaling for log-linear models. Ann. Math. Statist. 43:1470–1480
Deshpande, A., Garofalakis, M., Rastogi, R.: Independence is good: dependency-based histogram synopses for high-dimensional data. SIGMOD 199–210 (2001)
Galindo-Legaria, C., Joshi, M., Waas, F., et al.: Statistics on views. VLDB 952–962 (2003)
García-Varea, I., Och, F., Ney, H., et al.: Refined Lexikon models for statistical machine translation using a maximum-entropy approach. ACL 204–211 (2001)
Getoor, L., Taskar, B., Koller, D.: Selectivity estimation using probabilistic models. SIGMOD 461–472 (2001)
Greiff W., Ponte J. (2000): The maximum-entropy approach and probabilistic IR models. ACM Trans. Inform. Sys. 18(3):246–287
Guiasu S., Shenitzer A. (1985): The principle of maximum-entropy. Math. Intell. 7(1):42–48
Haas, P., Swami, A.: Sampling-based selectivity estimation for joins using augmented frequent-value statistics. ICDE 522–531 (1995)
IBM Corp.: DB2 Universal Database for iSeries: Database Performance and Query Optimization (2002)
IBM Corp.: DB2 v8.2 Performance Guide (2004)
Ilyas, I.F., Markl, V., Haas, P.J., Brown, P.G., Aboulnaga, A.: CORDS: automatic discovery of correlations and soft functional dependencies. SIGMOD 647–658 (2004)
Ioannidis, Y.E., Christodoulakis, S.: Propagation of errors in the size of join results. SIGMOD 268–277 (1991)
Kutsch, M., Haas, P.J., Markl, V., Megiddo, N., Tran, T.M.: Integrating a maximum-entropy cardinality estimator into DB2 UDB. EDBT 1092–1096 (2006)
Lynch, C.A.: Selectivity estimation and query optimization in large databases with highly skewed distribution of column values. VLDB 240–251 (1988)
Markl, V., Megiddo, N., Kutsch, M., Tran, T.M., Haas, P.J., Srivastava, U.: Consistently estimating the selectivity of conjuncts of predicates. VLDB 378–384 (2005)
Microsoft Corp.: SQL Server 2000 Books Online v8.00.02 (2004)
Piatetsky-Shapiro, G., Connell, C.: Accurate estimation of the number of tuples satisfying a condition. SIGMOD 256–276 (1984)
Poosala, V., et al.: Improved histograms for selectivity estimation of range predicates. SIGMOD 294–305 (1996)
Poosala, V., Ioannidis, Y.: Selectivity estimation without the attribute value independence assumption. VLDB 486–495 (1997)
Selinger, P.G., et al.: Access path selection in a relational DBMS. SIGMOD 23–34 (1979)
Shannon, C.E.: A mathematical theory of communication. Bell Sys. Tech. J. 27, 379–423 623–656 (1948)
Srivastava, U., Haas, P.J., Markl, V., Megiddo, N.: ISOMER: consistent histogram construction using query feedback. ICDE 6 (2006)
Stillger, M., Lohman, G., Markl, V., Kandil, M.: LEO – DB2’s learning optimizer. VLDB 19–28 (2001)
Swami, A.N., Schiefer, K.B.: On the estimation of join result sizes. EDBT 287–300 (1994)
Van Gelder, A.: Multiple join size estimation by virtual domains. PODS 180–189 (1993)