[
https://issues.apache.org/jira/browse/TAJO-1091?page=com.atlassian.jira.plugin.system.issuetabpanels:comment-tabpanel&focusedCommentId=14174750#comment-14174750
]
Hyunsik Choi commented on TAJO-1091:
------------------------------------
In my opinion, we should consider a big picture of our statistic information
system prior to histogram implementation. At least, we have to briefly decide
how Tajo collects/manages/exploits statistics information. This is because
histogram is a part of statistic information that Tajo will have. This decision
will affect the interfaces and implementations of all statistics components
including histogram.
In addition, Tajo and its underlying environment are different from traditional
RDBMSs. As a result, we should rethink statistic information system with
considering our direction and ultimate goal.
In terms of this point, let's discuss the following:
* which stats we should collect
* how we collect stats
* how/when Tajo exploit the collected stats
Actually, this discussion may be out of scope of this issue. So, I'll create
another jira issue for it if necessary.
> (Umbrella) Improve selectivity estimation by histograms
> -------------------------------------------------------
>
> Key: TAJO-1091
> URL: https://issues.apache.org/jira/browse/TAJO-1091
> Project: Tajo
> Issue Type: Improvement
> Reporter: Mai Hai Thanh
>
> Accurate selectivity estimations are very useful for the query optimizer to
> choose the best query plan. However, Tajo currently assumes that the
> selectivity of all single predicates is 0.1 (in DEFAULT_SELECTION_FACTOR),
> which is far from correct in many cases. Therefore, I want to improve Tajo's
> ability in selectivity estimation.
> There are alternative methods for selectivity estimation, such as histogram,
> wavelet transformation, singular value decomposition, discrete cosine
> transform, kernel estimators, and sampling. Among these methods, histograms
> have been shown to be one of the most popular and effective ways to obtain
> accurate selectivity estimates. Thus, I propose to implement and use
> histograms in Tajo soon. Other methods can be added later if needed. (An
> ensemble method that combines the results of many methods among the above
> ones to get the best selectivity estimate is also attractive)
> For histograms, more technically, there are some tasks to do as follows.
> 1. Implement a selectivity estimation interface
> + For the adding of a new histogram
> + For the use of a histogram in the query optimizer
> + In doing this, should consider the use of different kinds of histograms
> as well as different kinds of selectivity estimation methods
> 2. Implement some popular kinds of histograms
> + First candidates are EquiWidth and EquiDepth (i.e., EquiHeight)
> + Including: histogram construction, maintenance, and selectivity
> estimation given a predicate (both simple and complex predicates)
> 3. Implement the registration of histogram information to Catalog Server
> + Histograms can be a sub-part of a TableStats
> + The content of a histogram is stored in the Catalog Server
> 4. Implement a histogram creation and maintenance mechanism
> + Constructing a histogram for a column requires at least a column scan
> (full or random partial scan), so it may take a substantial amount of time.
> By default, histogram creation and maintenance can be triggerred after a
> default amount of time that there is no query processing. On the other hand,
> the creation and maintenance process can also be forced to run by a command,
> such as "ANALYZE table_name"
> 5. Improve the query optimizer to use histograms
> + If a histogram is available, use histogram instead of the default value
> 6. Further future improvements
> 6.1. A table may have many columns. Creating and maintaining histograms
> for all columns of all tables is too costly. Hence, we should have a method
> to monitor the frequently accessed columns and we create histograms for only
> these special columns.
> 6.2. For simplicity, the construction and maintenance processes of a
> histogram are independent of those processes of other histograms. However,
> for efficiency, those processes of different histograms of the same table
> should be done at the same time to exploit cache locality.
> 6.3. So far, we have considered only one-dimensional histograms (in which
> EquiWidth and EquiDepth are representatives). These histograms are enough for
> us if the value distributions of all attributes are independent of each
> other. However, this is not always true in real-life data. So, additional
> techniques to detect and exploit dependency of the attributes will be useful.
> 6.4. The selectivity of past predicates (of past queries) should be use
> in some ways to improve the future selectivity estimation.
> 6.5. For each column, we should find the list of Most Common Values and
> compute their selectivities. This kind of information will be very useful
> when used together with histograms.
--
This message was sent by Atlassian JIRA
(v6.3.4#6332)
