On 30/04/2013 12:59 PM, Richard Hipp wrote:
On Thu, Mar 14, 2013 at 2:07 PM, Ryan Johnson
<ryan.john...@cs.utoronto.ca>wrote:
Hi all,
I'm running sqlite-3.7.13 on cygwin. Playing around with various TPC-H
queries with my class recently, I hit a strangely slow query and don't
understand why it's so slow.
http://www.sqlite.org/draft/queryplanner-ng.html
Nice. If you're willing to do quadratic work anyway, would it make sense
to try and establish upper/lower bounds on the optimal solution to
decide how much harder to work? I believe it's possible to find lower
bounds for TSP using minimum spanning trees, and that computing the MST
should be log-linear in the number of joins for most queries; if the
"easy" NN=1 solution isn't too much higher than the lowest of a random
selection of upper bounds, it's probably safe to stop looking; if the
best upper bound is a *lot* lower (like the NN=1 result for Q8 being
14,000 times slower than the optimal), it probably justifies investing
more time with an NNN search for that particular query, in hopes of
bringing down the predicted runtime; the expected time difference could
even be used to set the NNN factor...
Thoughts?
Ryan
_______________________________________________
sqlite-users mailing list
sqlite-users@sqlite.org
http://sqlite.org:8080/cgi-bin/mailman/listinfo/sqlite-users