On Friday 22 February 2002 00:03, Colin Dewey wrote: This is an example of a class of problem that crops up in a lot of applications, like GIS systems all the time.
Unfortunately B-Tree type indexes, like RDBMS systems generally use are just not well adapted to this type of query. I know Informix had a "Data Blade" for Universal Server that provided some indexing strategies for this type of thing, but that is a pretty expensive solution... There are several ways to build indexes for this sort of stuff, but in MySQL you would essentially have to design a new table handler. Given MySQL's flexibility in that respect it is conceivable that someone will provide products like that in the future. For now I think you have the best solution you can get. The next best in theory I guess would be a table that was a cross join on t1 and t2 holding every possible t1.start - t2.end and t1.end - t2.start value. I suspect it would be HUGE! You might however construct such a table and then reduce it to only a few records of interest, but if your record set is being updated often that won't do you a lot of good either. Another possibility would be to try to use other criteria to reduce the work the slow query needs to do. Maybe there are entire sets of t1's such that they cannot possibly overlap a t2 (for instance any t1 who's start is greater than max(t2.end)). Those need not be considered at all. Depending on your data, that may eliminate a lot of work. > Given two tables (t1 and t2) with fields "start" and "end", what is the > most efficient method of finding the all the intervals in the first table > that overlap any interval in the second table? > > Right now, I use a query like: > > SELECT t1.name, t2.name FROM t1, t2 > WHERE t1.start <= t2.end AND t1.end >= t2.start; > > I use a key (start, end) in each table. > > Is there anything else that I can do to optimize this type of query (i.e. > add keys, change the select statement)? The tables typically have > thousands of records, so optimizing this query is very important. > > Thanks in advance for any help you can give me, > > Colin > > _________________________________________________________________ > Get your FREE download of MSN Explorer at http://explorer.msn.com/intl.asp. > > > --------------------------------------------------------------------- > Before posting, please check: > http://www.mysql.com/manual.php (the manual) > http://lists.mysql.com/ (the list archive) > > To request this thread, e-mail <[EMAIL PROTECTED]> > To unsubscribe, e-mail > <[EMAIL PROTECTED]> Trouble > unsubscribing? Try: http://lists.mysql.com/php/unsubscribe.php --------------------------------------------------------------------- Before posting, please check: http://www.mysql.com/manual.php (the manual) http://lists.mysql.com/ (the list archive) To request this thread, e-mail <[EMAIL PROTECTED]> To unsubscribe, e-mail <[EMAIL PROTECTED]> Trouble unsubscribing? Try: http://lists.mysql.com/php/unsubscribe.php
