On Fri, 6 Sep 2013 17:29:25 +0000
Harmen de Jong - CoachR Group B.V. <[email protected]> wrote:
> > If I recall correctly, query planner's behavior is worst-case
> > quadratic in the number of tables participating in the query. This
> > includes tables mentioned directly, and also those pulled in
> > indirectly via views, triggers or foreign keys.
Factorial, actually. After three tables, each addtional table
increases potential join sequences by roughly an order of
magnitude.
Given tables A, B, and C, 1 * 2 * 3 = 6:
sqlite> select a.T, b.T, c.T from F a join F b on a.T <> b.T
sqlite> join F c on b.T <> c.T where a.T <> c.T order by a.T, b.T, c.T;
A B C
A C B
B A C
B C A
C A B
C B A
That's six plans for the order in which the system could choose to
access the tables to execute the query.
Factorial grows quickly, as is demonstrated by adding table D:
sqlite> select a.T, b.T, c.T, d.T from F a join F b on a.T <> b.T
> cross join F c on b.T <> c.T join F as d on c.T <> d.T where
> a.T <> c.T and a.T <> d.T and b.T <> d.T order by a.T, b.T,
> c.T, d.T;
A B C D
A B D C
A C B D
A C D B
A D B C
A D C B
B A C D
B A D C
B C A D
B C D A
B D A C
B D C A
C A B D
C A D B
C B A D
C B D A
C D A B
C D B A
D A B C
D A C B
D B A C
D B C A
D C A B
D C B A
Pity the query optimizer facing an 8-way join. Or, say, a 20-table
join:
$ FACT=1; seq 20 | while read F; do FACT=$(( ${FACT} * $F )); printf '%
3d! = %d\n' $F ${FACT}; done
1! = 1
2! = 2
3! = 6
4! = 24
5! = 120
6! = 720
7! = 5040
8! = 40320
9! = 362880
10! = 3628800
11! = 39916800
12! = 479001600
13! = 6227020800
14! = 87178291200
15! = 1307674368000
16! = 20922789888000
17! = 355687428096000
18! = 6402373705728000
19! = 121645100408832000
20! = 2432902008176640000
There is such a thing as too many choices!
--jkl
_______________________________________________
sqlite-users mailing list
[email protected]
http://sqlite.org:8080/cgi-bin/mailman/listinfo/sqlite-users
