Hi - I have an int column with several million rows of data. What is the fastest way to write a query to get the median value of the column? Apparently there is no median() function in SQL. A web search revealed lots of various talk about using stored procedures and fancy functions. None of this looked like it would be very efficient. I searched these archives but didn't see a single mention of median. Thank you! I'm not an expert on MonetDB/SQL, but finding a median (on any quantile) is a well researched problem, e.g. http://en.wikipedia.org/wiki/Selection_algorithm Still, MEDIAN is a significantly different function than e.g. SUM or AVG, that's why it's usually not supported in SQL.
You have some choices: 1. sort and select, e.g. : SELECT value FROM table ORDER BY value LIMIT half_table_size, 1. This probably has an O(NlogN) complexity, might be acceptable for your data sizes. I hope MonetDB/SQL supports LIMIT ;) 2. use binary search, also O(NlogN), a bit more complicated 3. use Hoere's algorithm (quickselect), which can generate the answer in O(N) (average case), but it requires some explicit data manipulation. Only worth it if you really focus on speed. I'd go for #1, if it's too slow, I'd try #3 Good luck, m.
------------------------------------------------------------------------- Check out the new SourceForge.net Marketplace. It's the best place to buy or sell services for just about anything Open Source. http://sourceforge.net/services/buy/index.php _______________________________________________ Monetdb-developers mailing list Monetdb-developers@lists.sourceforge.net https://lists.sourceforge.net/lists/listinfo/monetdb-developers
-- : Marcin Zukowski < marcin@cwi.nl | http://www.cwi.nl/~marcin >