{"id":13052,"date":"2021-12-05T20:28:36","date_gmt":"2021-12-06T01:28:36","guid":{"rendered":"https:\/\/carleton.ca\/scs\/?page_id=13052"},"modified":"2026-06-02T14:59:24","modified_gmt":"2026-06-02T18:59:24","slug":"tr-01-06-the-efficiency-of-modern-day-histogram-like-techniques-for-query-optimization","status":"publish","type":"page","link":"https:\/\/carleton.ca\/scs\/research\/scs-technical-reports\/technical-reports-2001\/tr-01-06-the-efficiency-of-modern-day-histogram-like-techniques-for-query-optimization\/","title":{"rendered":"TR-01-06: The Efficiency of Modern-Day Histogram-Like Techniques for Query Optimization"},"content":{"rendered":"\n
\n
\n\n
\n
\n
\n

\n TR-01-06: The Efficiency of Modern-Day Histogram-Like Techniques for Query Optimization\n <\/h1>\n \n \n <\/header>\n\n <\/div>\n\n <\/div>\n\n <\/div>\n<\/section>\n\n

Carleton University
\nTechnical Report<\/a> TR-01-06
\nJuly 2001<\/p>\n\n\n\n

The Efficiency of Modern-Day Histogram-Like Techniques for Query Optimization<\/h2>\n\n\n\n
\n
\n
\n
\n
\n
\n
\n
\n
B. John Oommen & Luis G. Rueda<\/div>\n<\/div>\n<\/div>\n<\/div>\n<\/div>\n
\n

Abstract<\/h3>\n<\/div>\n<\/div>\n<\/div>\n<\/div>\n<\/div>\n\n\n\n

One of the most di\u001ecult tasks in modern day Database Management Systems (DBMS) is information retrieval. Basically, this task involves a user query, written in a high-level language such as the Structured Query Language (SQL), and some internal operations, which are transparent to the user. The internal operations are carried out through very complex modules that decompose, optimize and execute the dif- ferent operations. We consider the problem of Query Optimization which consists of the system choosing, among many di\u001berent Query Evaluation Plans (QEP), the most economical one. Since the number of QEPs increases exponentially as the number of relations involving the query is larger, query optimization is a very complex problem.Many estimation techniques have been developed in order to approximate the cost of a QEP. Histogram- based techniques are the most used methods in this context. In this paper, we discuss the e\u001eciency of some of these methods: Equi-width, Equi-depth, the Rectangular Attribute Cardinality Map (R-ACM), and the Trapezoidal Attribute Cardinality Map (T-ACM). These methods are used to estimate the cost of the di\u001berent QEPs and choose the best one. It has been shown that the errors of the estimates from the R-ACM and T-ACM are signi\u001ccantly less than the corresponding errors obtained from the Equi-width and Equi-depth. This fact has been formally demonstrated using reasonable statistical distributions for the cost of a QEP, the doubly exponential distribution and the normal distribution. For the empirical analysis, we have developed a formal, rigorous prototype model used to analyze these methods on random databases. Our empirical results demonstrate that the R-ACM chooses a superior QEP more than three times as often as the Equi-width and Equi-depth. In the case of the T-ACM the ratio is even greater than four. Indeed, in the most general scenario, we analytically prove that under certain models, the better the accuracy of an estimation technique, the greater the probability of choosing the most e\u001ecient QEP.<\/p>\n\n\n\n

TR-01-06.pdf<\/a><\/p>\n","protected":false},"excerpt":{"rendered":"

Carleton University Technical Report TR-01-06 July 2001 The Efficiency of Modern-Day Histogram-Like Techniques for Query Optimization B. John Oommen & Luis G. Rueda Abstract One of the most di\u001ecult tasks in modern day Database Management Systems (DBMS) is information retrieval. Basically, this task involves a user query, written in a high-level language such as the […]<\/p>\n","protected":false},"author":2,"featured_media":0,"parent":12272,"menu_order":0,"comment_status":"closed","ping_status":"closed","template":"","meta":{"_acf_changed":false,"_cu_dining_location_slug":"","footnotes":"","_links_to":"","_links_to_target":""},"cu_page_type":[],"class_list":["post-13052","page","type-page","status-publish","hentry"],"acf":{"cu_post_thumbnail":false},"_links":{"self":[{"href":"https:\/\/carleton.ca\/scs\/wp-json\/wp\/v2\/pages\/13052","targetHints":{"allow":["GET"]}}],"collection":[{"href":"https:\/\/carleton.ca\/scs\/wp-json\/wp\/v2\/pages"}],"about":[{"href":"https:\/\/carleton.ca\/scs\/wp-json\/wp\/v2\/types\/page"}],"author":[{"embeddable":true,"href":"https:\/\/carleton.ca\/scs\/wp-json\/wp\/v2\/users\/2"}],"replies":[{"embeddable":true,"href":"https:\/\/carleton.ca\/scs\/wp-json\/wp\/v2\/comments?post=13052"}],"version-history":[{"count":1,"href":"https:\/\/carleton.ca\/scs\/wp-json\/wp\/v2\/pages\/13052\/revisions"}],"predecessor-version":[{"id":13053,"href":"https:\/\/carleton.ca\/scs\/wp-json\/wp\/v2\/pages\/13052\/revisions\/13053"}],"up":[{"embeddable":true,"href":"https:\/\/carleton.ca\/scs\/wp-json\/wp\/v2\/pages\/12272"}],"wp:attachment":[{"href":"https:\/\/carleton.ca\/scs\/wp-json\/wp\/v2\/media?parent=13052"}],"wp:term":[{"taxonomy":"cu_page_type","embeddable":true,"href":"https:\/\/carleton.ca\/scs\/wp-json\/wp\/v2\/cu_page_type?post=13052"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}