StackOverflow2013

Note that there are some explanatory texts on larger screens.

plurals

POSearch next (bigger) key with SQL efficiently
text
Body
copied!<p>I have a table with tuples where timestamps (time) are not consecutive but (we can assume for simplicity) unique.</p> <pre><code>time | value ------------ 0 |4 3 |2 5 |6 8 |10 9 |5 13 |-1 15 |-3 ... |... </code></pre> <p>I am faced with the problem of finding the "next tuple given some time T" ( <- next(T);), e.g. next(4) -> <5,6>, or next(5) -> <8,10>. Further, since this data is hold in a MySQL database I would prefer to realize this with SQL. However, time constraints require to find the respective tuple in O (log n).</p> <p>At first glance, I tried the following SQL statement (I hope my Pseudo-code is understandable):</p> <pre><code><time, value> = next(T) { return (select * from table where time = (select min(time) from table where time > T)) } </code></pre> <p>However, this does not give the result in reasonable time. I guess that "select min(time) from table where time > find" takes O(n) time. Of course, I know performing a search in an ordered list takes only O(log n) time but I have no clue how to do that in SQL. Is this even possible? If so, how does it work?</p> <p>Thanks!</p> <hr> <p>For your information: </p> <p>(1) At the moment my solution caches the respective data in memory and orders it initially. This way I can then find the next tuple in O(log n) time. However, this consumes lots of memory and I would prefer to do it kind of "in-line" in the DBMS which is surely highly optimized regarding caching etc.</p> <p>(2) I could imagine a solution where data is hold ordered by time in the database, but I don't know how to ensure ordering or to implement a respective search algorithm in SQL. :-/</p> <p>(3) I am aware of indexing etc. and that it improves performance if I declare time as primary key but I don't know how it could help to find next in O(log n).</p>

Querying!

Guidance

An individual column

Larger individual text columns get their own page to allow for proper reading.

SQuiL has stopped working due to an internal error.

If you are curious you may find further information in the browser console, which is accessible through the devtools (F12).

Reload