Hi Mike,
> Having debugged the optimizer slightly, it does seem apparent that the
> inner group by is optimised for cost before looking at the join that needs
> to take place. The costs for the various orderings are similar ~ only 1%
> between the good and the bad ordering, which explains why it is unstable as
> to which ordering is chosen.
>
Yes, I came a similar conclusion. I tried to solve this in past during my
PhD with a different cost model. But the changes I made would imply in a
lot of changes in the code. Besides, according to a talk that I had with
Thomas, the actual optimizer and the cost model meet most cases presented
and/or evaluated here and he was without time to evaluate my work.
I think that one of reasons is the lack of a estimate of the number of rows
returned by a join operation. Such number could be used to a better
estimation the cost of rescan the inner nodes in more internal levels. In
some situations the optimizer is not capable to see difference in the
ordering, because the tables can be accessed by indexes with same cost, and
the number of rows become the main factor to define the order (tables with
less rows tend to be used firstly, I think).The following example
translates my thoughts:
create table a (a1 int primary key, a2 int);
create table b (b1 int primary key, b2 int);
create table c (c1 int primary key, c2 int);
insert into a values (1,1),(2,1),(3,1),(4,1),(5,1),(6,1),(7,2),(8,3),(9,4);
insert into b values (1,1),(2,1),(3,1),(4,1),(5,2),(6,3),(7,4),(8,5),(9,5);
insert into c values (1,1),(2,2),(3,3),(4,4),(5,5),(6,6),(7,7),(8,8),(9,9);
create index on a(a2);
create index on b(b2);
create index on c(c2);
analyze;
select column_name,selectivity from INFORMATION_SCHEMA.COLUMNS where
table_name in ('A','B','C')
Column Selectivity a2=44; Distinct rows= 1-((100-44)/100) --> 0,44 * 10 = 4;
Column Selectivity b2=55; Distinct rows= 1-((100-55)/100) --> 0,55 * 10 = 5;
Column Selectivity c2=100; Distinct rows= 1-((100-100)/100) --> 1 * 10 = 10;
Predicted rows = (1 / max(4,5)) * 10 * 10 = 20 rows; Real size = 27 rows
select count(*) from a inner join b on a2=b2
Predicted rows = (1 / max(4,10)) * 10 * 10 = 10 rows; Real size = 9 rows
select count(*) from a inner join c on a2=c2
Predicted rows = (1 / max(5,10)) * 10 * 10 = 10 rows; Real size = 9 rows
select count(*) from b inner join c on b2=c2
Pick the option 'a join c' or 'b join c' firstly is better, but as the
tables have the same number of rows and equivalent indexes (same costs),
the optimizer chooses the first order evaluated a join b join c. Well, I'm
not sure if a change in the optimizer could be interesting to the community
now, or even accepted. A feature that I thought is the possibility to skip
a number of tables during join ordering phase. In cases (I think yours)
where you know the distribution and is capable to generate queries already
optimized (more restrictive joins firstly) or the optimizer is not doing a
good job and you know better plan, you can skip the ordering of a fixed
number of tables, and tables will be read according to the order of parsing
phase. The Postgres has a similar feature to this, the join_collapse_limit
<http://www.postgresql.org/docs/9.0/static/runtime-config-query.html>.
Hey Thomas, Noel, Mike and others, what do you think if we include a new
property that allows to skip the ordering of a fixed number of tables in
join ordering phase?
Regards,
Fred
--
You received this message because you are subscribed to the Google Groups "H2
Database" group.
To unsubscribe from this group and stop receiving emails from it, send an email
to [email protected].
To post to this group, send email to [email protected].
Visit this group at http://groups.google.com/group/h2-database.
For more options, visit https://groups.google.com/d/optout.
