On Thu, Jun 13, 2019 at 03:17:07PM +0200, Rafia Sabih wrote:
On Thu, 13 Jun 2019 at 06:07, Kuntal Ghosh <kuntalghosh.2...@gmail.com> wrote:
On Thu, Jun 13, 2019 at 5:49 AM Tomas Vondra
<tomas.von...@2ndquadrant.com> wrote:
>
> >> ...
> >>
> >That'll be an interesting work. For the above query, we can definitely
> >calculate the correction coefficient of t1-t2 join given (t1.a = ? AND
> >t1.b = ? AND t1.c < ?) and
> >(t2.x = ? AND t2.y = ?) are true. But, I'm not sure how we can
> >extrapolate that value for t1-t2 join.
>
> I'm not sure I see the problem? Essentially, we need to know the sizes
> of the join inputs, i.e.
>
> t1 WHERE (t1.a = ? AND t1.b = ? AND t1.c < ?)
>
> t2 WHERE (t2.x = ? AND t2.y = ?)
>
> (which we know, and we know how to correct the estimate), and then the
> selectivity of the join condition. Which we also know.
>
> Obviously, there's a chance those parts (clauses at the scan / join
> level) are correlated, which could make this less accurate.
This is exactly what my concern is. The base predicate selectivities
of t1 and t2 should have an impact on the calculation of the
correction coefficient. If those selectivities are low, the
misestimation (which is actual/estimate) should not affect the t1-t2
join correction coefficient much.
Interesting discussion. Talking of query optimization techniques and
challenges, isn't the biggest challenge there is of selectivity
estimation?
Yes, selectivity estimation is the major challenge. It's not the only one,
but we rely on the estimates quite a bit - it's probably the main factor
affecting cost estimates.
Then instead of working on optimizing the process which
has been talked of since long, how about skipping the process
altogether. This reminds of the work I came across sometime back[1].
Basically, the idea is to not spend any energy on estimation the
selectivities rather get on with the execution. Precisely, a set of
plans is kept apriori for different selectivities and at the execution
time it starts with the plans one by one, starting from the lower
selectivity one till the query execution completes. It might sound
like too much work but it isn't, there are some theoretical guarantees
to bound the worst case execution time. The trick is in choosing the
plan-set and switching at the time of execution. Another good point
about this is that it works smoothly for join predicates as well.
Since, we are talking about this problem here, I though it might be a
good idea to shed some light on such an approach and see if there is
some interesting trick we might use.
[1] https://dsl.cds.iisc.ac.in/publications/conference/bouquet.pdf
AFAIK adaptive execution (switching from one plan to another
mid-execution) is actually quite difficult to implement in practice,
especially when some of the rows might have been already sent to the
user, etc. Which is why databases (outside of academia) use this only
in very limited/specific situations.
regards
--
Tomas Vondra http://www.2ndQuadrant.com
PostgreSQL Development, 24x7 Support, Remote DBA, Training & Services
