I would concur in that SQLite is asking "which subset of the given constraints yields the most efficient access".
The possible query plans are 1) A() -> B(ID) -> C(LINKID) 2) C() -> B(LINKID) -> A(ID) 3) B() -> A(ID) + C(LINKID) or B() -> C(LINKID) + A(ID) 4) A() -> C() -> B(ID,LINKID) or C() -> A() -> B(ID,LINKID) Assuming unique keys in A and C and cardinalities of a, b and c we have estimated costs (in # of records retrieved): 1) a + a*b/a + a*b/a*1 = a + 2b 2) c + c*b/c + c*b/c*1 = c + 2b 3) b + b*1 + b*1 = 3b 4) a + a*c + a*c*b/a/c = a + a*c + b (resp. c + a*c + b) So which is the smallest cost? We know that b <= a*c, which makes query plan 4 at least as expensive as plans 1 or 2 respectively. Choosing between plans 1 and 2 means starting with the smaller of the two tables (assume a < c). So how do plans 1 and 3 compare? Plan 3 is better only for very sparse link tables where b < a < c is true. -----Ursprüngliche Nachricht----- Von: Dan Kennedy [mailto:danielk1...@gmail.com] Gesendet: Montag, 15. Dezember 2014 12:24 An: General Discussion of SQLite Database Betreff: Re: [sqlite] Query Planner for Virtual Tables: link table evaluation & transitive property of constraints not used On 12/12/2014 09:22 PM, Josef Kučera wrote: > Hello, > I am trying to use SQLite's marvellous Virtual Table mechanism as a > SQL layer for querying an in memory storage. This works good, but I > have a problem with more complex queries. When querying a real SQLite > database it correctly moves the constant conditions across joined > tables to optimize the execution plan (I think this was implemented in the > 3.7.17 release). > Unfortunately for virtual tables this does not seem to be supported. I > can overcome this limitation by manually tuning the SQL, but it will > help if the query planner can do this automatically. > > The major problem I have is with link table evaluation. Imagine a SQL > like "select * from A join B on A.ID=B.ID join C on C.ID=B.LINKID". > The current implementation evaluates cost of B only as B (ID, LINKID) > causing the execution to perform a full scan on either A or C. This > seems to be caused by the implementation of whereLoopAddVirtual() > function. I think it should evaluate cost for terms separated by tables in > the right term as well, e.g. > for the mentioned SQL, table B, it should try B(), B(ID), B(LINKID), > B(ID, > LINKID) instead of only B() and B(ID, LINKID). > > What should I do? You want this (or the same thing with the roles of "A" and "C" reversed): * a full-scan on A, * a lookup on B by (b.id=?) * a lookup on C by (c.id=?) correct? It's tricky. As you say, xBestIndex() will currently be invoked twice - once with no constraints usable and once with both "b.id=?" and "b.linkid=?" usable. I guess the reason it is not invoked in the other ways you suggest is that that strategy might conceivably require a huge number of xBestIndex() calls if there were more than a few other tables in the join. You could change the query so that only one of the constraints is visible to the virtual table implementation. Say: select * from A join B on A.ID=B.ID join C on C.ID=+B.LINKID Or rework the virtual table code so that it knows only to use one of "b.id=?" or "b.linkid=?" at a time. If the xBestIndex only uses one of the constraints, the planner should do the right thing. Dan. _______________________________________________ sqlite-users mailing list sqlite-users@sqlite.org http://sqlite.org:8080/cgi-bin/mailman/listinfo/sqlite-users ___________________________________________ Gunter Hick Software Engineer Scientific Games International GmbH FN 157284 a, HG Wien Klitschgasse 2-4, A-1130 Vienna, Austria Tel: +43 1 80100 0 E-Mail: h...@scigames.at This communication (including any attachments) is intended for the use of the intended recipient(s) only and may contain information that is confidential, privileged or legally protected. Any unauthorized use or dissemination of this communication is strictly prohibited. If you have received this communication in error, please immediately notify the sender by return e-mail message and delete all copies of the original communication. Thank you for your cooperation. _______________________________________________ sqlite-users mailing list sqlite-users@sqlite.org http://sqlite.org:8080/cgi-bin/mailman/listinfo/sqlite-users
