Select only neighbour rows who pass a where-test

Question

I want to apply a selection process to my data, that will not include rows which should be accepted by my WHERE clause but who follow after a row which fails the WHERE.

Example. I have a list of gps locations and want to put them in a tour entity, if they surpass a speed limit.

SELECT _id, speed FROM location;

results in (sqlite3 syntax):

1|0
2|0
3|3
4|3
5|3
6|0
7|0
8|0
9|3
10|3
11|3
12|0

So, if I SELECT for WHERE speed > 2 now, I will get 3,4,5 and also 9,10,11. These both clearly should be separated tours. Can I formulate my SQL in a way that it only results in 3,4,5 because the following entity will result in a failed WHERE speed > 2 test?

First I thought, that I can simply return all these entities, but now I think there will be 2 problems with that. First there might be a lot of these, when this SELECT is called. And second there might be deleted rows. So instead of the 11 row there might be a lot higher number as _id which still should belong to the same tour, because there are no rows between 10 and this row and both pass the WHERE speed > 2. That there are no rows failing the WHERE between 10 and the next row is totally unknown the Application waiting for the result of this SELECT.

It is on purpose that I don't ask for a database specific answer. If you know an easy solution for database X or Y there is no problem adding it as a solution. The real question is, how to solve it with standard SQL, though. I think every well known database should have some way of solving any task out of the standard solvable task set.

Answer 1

I don't know if this will work in sqlite3, but you didn't tag the question with that, so here is an Oracle solution.

SELECT ID, Speed FROM
(
    SELECT ID, Speed, MIN(Speed) OVER (ORDER BY ID) InSequence  
    FROM
    (
        SELECT ID, Speed, SUM(Speed) OVER (ORDER BY ID) SpeedSum
        FROM location 
    )
    WHERE SpeedSum > 0 
) 
WHERE InSequence > 0
ORDER BY ID;

The SUM(Speed) analytic removed the leading zero speed rows and the MIN(Speed) analytic allows us to eliminate rows starting with the first zero speed row remaining. The sample data can be created as follows:

drop table location;

create table location as (select level id, 
   case when level between 3 and 5 then 3 
        when level between 9 and 11 then 3
        else 0 end speed from dual connect by level <=12);

select * from location;

It seems to behave correctly through all the following variations, but there could be a pattern I've missed:

UPDATE location SET Speed=1 WHERE ID=2;
UPDATE location SET Speed=2 WHERE ID=3;
UPDATE location SET Speed=1 WHERE ID=6;
DELETE FROM location WHERE ID IN (7,9);


UPDATE location SET Speed=0 WHERE ID=2;
UPDATE location SET Speed=5 WHERE ID=1;

This solution only requires one full table scan rather than the two Noam's solution requires, but it only finds the first set of values whereas Noam's finds all the sets. It also assumes a threshold of zero, but could be modified for any threshold.

Answer 2

This solution sucks, because it is too complex. If you have an easier solution to the problem, go ahead and show it!!!

Okay, I found something like a solution. What helped me a lot was the realisation that I can't identify afterwards which id really was the followup to the one before, but I can identify the first one which FAILS the WHERE quite easily by knowing the start_id of a tour (the first returned by the SELECT in the question). From there it is easy to backtrack.

I go in 5 steps that I put into temporary views just for better readability (it got way too complicated). What I called tour before is called track now, because this is the term used in KML.

the steps involved:

1. Find the last foreign_id that was already tracked (in the track table, not important for this discussion)
2. Find the first _id in location that passes the WHERE (start_id)
3. Find the first _id after start_id that fails the WHERE (first_fail)
4. Find the last _id before first_fail that passes the WHERE (end_id)
5. Put start_id and end_id together for simpler querying of the result

Here is the code (remember each step one view in the same order as described above):

DROP VIEW IF EXISTS last_tracked;
DROP VIEW IF EXISTS start_id;
DROP VIEW IF EXISTS first_fail;
DROP VIEW IF EXISTS end_id;
DROP VIEW IF EXISTS next_track;
CREATE VIEW last_tracked AS SELECT end_location FROM track order by end_location DESC LIMIT 1;
CREATE VIEW start_id AS SELECT _id FROM location WHERE sped >= 2 AND _id > (SELECT * FROM last_tracked) ORDER BY _id LIMIT 1;
CREATE VIEW first_fail AS SELECT _id FROM location WHERE sped < 2 AND _id >= (SELECT * FROM start_id) ORDER BY _id LIMIT 1;
CREATE VIEW end_id AS SELECT _id FROM location WHERE _id >= (SELECT * FROM start_id) AND _id < (SELECT * FROM first_fail) ORDER BY _id DESC LIMIT 1;
CREATE VIEW next_track AS SELECT (SELECT * FROM start_id), (SELECT * FROM end_id);
SELECT * FROM next_track;

Answer 3

(taking 3 as the speed threshold)

SELECT id,speed, 

  (SELECT COUNT(*) 

   FROM  location location2 

   WHERE (IF(location.speed < 3,1,0) <> IF(location2.speed < 3,1,0)) 

   AND location2.id <= location.id) as TourNumber 

FROM location

where speed >= 3

Since this is essentially a self-join, I need some way to distinguish between the two copies of the table. Location2 is an alias assigned to the table location (putting a , will result in a join operation which will naturally fail because there's no location2 table).

For brevity, let's say that id with speed above the threshold are "good" and the others are bad. So, if your current id is good/bad, this will give you the total number of bad/good ids that precede it. This number will be the same for all the good/bad ids in that specific good/bad tour. Afterwards, select only the good tours.fin.