Re: Finding overlapping intervals efficiently
I did some playing around with various indices on the tables and found that the fastest configuration was without any indices! With two tables (t1 and t2) with fields start and end, using an index (start, end) or indices on the on the two fields separately, the speed of joining the two tables and finding all overlapping intervals was 10X SLOWER than the same query without using any indices. With the sizes of my tables, the speed of the queries is now very reasonable, so I probably won't pursue using a different table handler or index type. But it would be nice to eventually be able to use an index for this type of query that could make it more efficient, so that larger data sets could be compared. Thanks for all the help, Colin Hi, On Sat, 2002-02-23 at 01:14, Tod Harter 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. Hmm, maybe just a new index type, not a complete new table handler. Would R-tree indexes (and OpenGIS functions) make you happy? Regards, Arjen. -- MySQL Training in Brisbane: 18-22 March, http://www.mysql.com/training/ __ ___ ___ __ / |/ /_ __/ __/ __ \/ /Mr. Arjen G. Lentz [EMAIL PROTECTED] / /|_/ / // /\ \/ /_/ / /__ MySQL AB, Technical Writer, Trainer /_/ /_/\_, /___/\___\_\___/ Brisbane, QLD Australia ___/ www.mysql.com _ Join the worlds largest e-mail service with MSN Hotmail. http://www.hotmail.com - 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
Re: Finding overlapping intervals efficiently
Hi, On Sat, 2002-02-23 at 01:14, Tod Harter 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. Hmm, maybe just a new index type, not a complete new table handler. Would R-tree indexes (and OpenGIS functions) make you happy? Regards, Arjen. -- MySQL Training in Brisbane: 18-22 March, http://www.mysql.com/training/ __ ___ ___ __ / |/ /_ __/ __/ __ \/ /Mr. Arjen G. Lentz [EMAIL PROTECTED] / /|_/ / // /\ \/ /_/ / /__ MySQL AB, Technical Writer, Trainer /_/ /_/\_, /___/\___\_\___/ Brisbane, QLD Australia ___/ www.mysql.com - 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
Re: Finding overlapping intervals efficiently
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
Finding overlapping intervals efficiently
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
