Xaprb

In an earlier article I discussed how to find missing members in a sequence with SQL. In this article I’ll do the reverse: demonstrate how to find the start and end point of each contiguous range.

Motivation

Someone posted a comment on the article linked above, asking how to do this. At least, that’s what I think the question was; I might be misinterpreting it. I considered replying in the comments on that article, but decided it should go in its own article instead.

I’ll use the same sample data as in the earlier article: a sequence of integers from 1 to 20, with the numbers 5, 11, 12, 13, and 14 missing. I’ll also delete the value 7, so 6 is a range of length 1. The desired answer is

The solution

This isn’t as easy as I thought it would be at first. I stared at it for a while, then it came to me: I want to find the start and end of each contiguous range, so I need to define “start” and “end.” The start of a range is defined by the absence of the preceding number. I initially thought “has a next but no previous,” but that’s incorrect because a single number is a valid range; if I require the start to have a “next,” that eliminates 6 (I initially wrote the whole thing wrong, then thought about single-number ranges and re-wrote everything). So the definition of “start” is a number that has no “previous.”

The end of a range is almost the reverse: it has no “next” but might have a “previous.” Additionally, it should be the smallest such number that’s greater than or equal to the start. The “or equal to” is again necessary to include ranges that are just one number.

Each of these queries is fairly simple by itself, using exclusion joins. Here’s one that will find the start of every range:

select l.id
from sequence as l
    left outer join sequence as r on r.id = l.id - 1
where r.id is null;

I’m referring to the left-hand table as “l” and the right-hand table as “r.” Here’s a query that will find the end of every range. It’s almost the same:

select l.id
from sequence as l
    left outer join sequence as r on r.id = l.id + 1
where r.id is null;

Bringing the two together, and meeting the “smallest value greater than or equal to” requirement, is a more complex query. Here I solve it with a correlated subquery:

select l.id as start,
    (
        select min(a.id) as id
        from sequence as a
            left outer join sequence as b on a.id = b.id - 1
        where b.id is null
            and a.id >= l.id
    ) as end
from sequence as l
    left outer join sequence as r on r.id = l.id - 1
where r.id is null;

I’ve re-aliased the subquery’s tables as “a” and “b” to avoid confusion with “r” and “l.”

You might also like:

1. How to find missing values in a sequence with SQL
2. How to find data distributions with SQL
3. How to subtract in SQL over samples that wrap
4. How to write a SQL exclusion join
5. How to simulate FULL OUTER JOIN in MySQL

It’s been a while since I’ve posted an abstract, theoretical article on a fine point of SQL. Today I want to bring your attention to two ways in which an RDBMS can allow you to do something that has no well-defined result. These involve queries where several values are eligible, but only one is chosen — and chosen in an undefined manner. I’ll show you the two blunders, tell you when they might occur, and explain how to avoid them.

Selecting an un-grouped column in a grouped query

As far as I know, this bad behavior only applies to MySQL. As the manual explains, MySQL “extends the use of GROUP BY” to allow selecting columns that do not appear in the GROUP BY clause. What does this mean? Well, suppose I have the following data:^[1]

MySQL lets me write the following query against the data:

select Fruit, Price, count(*) as c
from Fruits
group by Fruit;

The results will look like this:

Here’s the problem: the query groups the tuples (rows) into two groups, one group containing two Apples and one with two Oranges. I can’t logically get “the price” from two tuples in a group, because there is no one “the” price. In the formal mathematics upon which SQL is based, this query is nonsense. MySQL’s documentation admits as much, and tells me not to do this unless all the tuples in the group have the same value in that column — or I’ll risk getting unpredictable behavior. In my example, it’s pretty easy to see MySQL chooses the value from the “first” tuple in the group (a funny notion, given that there is no first tuple because sets are theoretically unordered).

This is a bad behavior introduced solely for the sake of optimization, and the documentation admits that. Grouping requires sorting, which requires comparing values, so grouping literally by as few columns as possible — even when the logical grouping may be by more columns — is an (ill-gotten) efficiency gain.

As with any other non-standard technique, the benefit is offset by lack of portability. Plus, it might cause evil glares from colleagues ;-).

To avoid this problem on MySQL, use standard SQL (sorry for stating the obvious). To make my query standard SQL, I’d either have to use an aggregate function on that column, such as SUM, MIN, AVG, MAX or similar — or, I could add the column to the GROUP BY clause, which would separate the results into more groups and change the output. In other words, every column must either be in the grouping clause or an aggregate function.

Some platforms, such as SQL Server 2000, will not allow the query. MySQL can be made to throw an error too, if ONLY_FULL_GROUP_BY mode is enabled.

It’s important to group the query by the data, not by the expressions used to transform the data. Programmers who don’t really understand what’s going on sometimes just change the code to make the errors stop, often making an even worse mess out of the query. Watch out for this. Here’s a good article on how to group queries properly.

Updates from a join

Unlike the first gotcha above, this one can happen systems other than MySQL. The issue is an UPDATE in a join with a FROM, where tuples from the base table being updated appear multiple times. Here is a query:

update t1
   inner join t2 on t1.id = t2.id
set t1.col1 = t2.col1;

/* Equivalent syntax for SQL Server 2000
update t1
   set t1.col1 = t2.col1
   from t1 inner join t2 on t1.id = t2.id
*/

If you’re used to seeing it, it may look like there’s nothing wrong with that query^[2]. Suppose, though, that my data looks like this:

(Ignore for a moment that this table has pretty much the same data as the Fruits table…)

I’ll re-write the query to show how I might unwittingly update a FruitPrices tuple from multiple Fruits tuples:

update FruitPrices as fp
   inner join Fruits as f on f.Fruit = fp.Fruit
set fp.Price = f.Price;

What does this statement actually do? Well, logically it first joins the base tables together:

Next it updates each Price value in the left-hand side from the column on the right-hand side. But wait, the value appears twice — that means logically, Apples are being assigned $5.00 twice, and Oranges are being assigned both $4.00 and $6.00 prices. Danger, Will Robinson! Which one wins? As it turns out, in MySQL again the “first” value wins. Not in SQL Server 2000, though — the “last” one wins on that platform, if memory serves. It doesn’t really matter the particulars of which value wins; it would be more legitimate if the database server threw an error, in my opinion.

I can think of a few ways to avoid this situation.

Method 1: Avoid non-standard syntax

Neither syntax above is standard, and neither makes any sense from a true relational standpoint, which is why they have undefined, vendor-specific behavior. A standard UPDATE statement does not have a FROM clause. Joe Celko has written extensively about this:

The correct syntax for a searched update statement is

<update statement> ::=
  UPDATE <table name>
     SET <set clause list>
  [WHERE <search condition>]

<set clause list> ::=
  <set clause> [{ , <set clause> }...]

<set clause> ::= <object column> = <update source>

<update source> ::= <value expression> | NULL | DEFAULT

<object column> ::= <column name>

The UPDATE clause simply gives the name of the base table or updatable view to be changed.

That’s not terribly enlightening to most people, especially those not used to reading BNF! Let me try to correct the query:

update FruitPrices as fp
   set fp.Price =  (
      select f.Price from Fruits as f
      where f.Fruit = fp.Fruit);
ERROR 1242 (21000): Subquery returns more than 1 row

Oops! It looks like MySQL is now complaining about me trying to update a single value from a whole set of values! Very good. This shows me that my query is wrong, instead of silently doing something bad. Here’s a query that works:

update FruitPrices as fp
   set fp.Price =  (
      select max(f.Price) from Fruits as f
      where f.Fruit = fp.Fruit);

Method 2: Join one-to-one

The second way, if you must use non-standard, mathematically invalid syntaxes, is to make sure the join is based on indexes and primary keys in such a way that the many-to-one problem doesn’t happen. For example, if the columns used in the join criterion are the primary key in the right-hand base table, it’s safe.

Method 3: Group the right-hand side

The last is to follow the advice of the article linked above and group the right-hand table appropriately. This is effectively the same thing as my second suggestion.

^[1] You can create the tables I’m using with the following scripts:

create table Fruits(
   Fruit varchar(50),
   Price decimal(3,2));

create table FruitPrices(
   Fruit varchar(50) not null primary key,
   Price decimal(3,2));

insert into Fruits values 
   ("Apples", 5.00),
   ("Apples", 5.00),
   ("Oranges", 6),
   ("Oranges", 4);

insert into FruitPrices(Fruit)
   values("Apples"), ("Oranges");

What’s really wrong with these queries?

The relational model, which SQL doesn’t follow exactly, is all about functions in the mathematical sense. Recall a function is just a mapping from the domain to the range, and one input value from the domain must produce exactly one output in the range. A given input value may not map to two output values. This is why a lot of functions can’t be turned around backwards and still be functions. For example, sin(0) is 0, but so is sin(2*pi), and sin is a function; but the inverse isn’t a function. If you turn sin around and try to put 0 into the back end, what do you get out? You get 0, and 2*pi, and … infinitely many other values.

The incorrect statements I’ve shown above make no sense because they’re trying to shove data into a function backwards, and there can be more than one result on the output. I’ve shown how RDBMSs often just pick one of the outputs, and it’s fine to know that’s going to happen, but it’s also important to know what is really going on.

This really does matter. Two days ago at work, my boss brought up a situation where a production query on our main database server had created a bad situation because of updates in a join. Bogus!

^[2] If you’re not familiar with either of these syntaxes, I feel your pain. I wasn’t either until I got out of database-theory classes. These syntaxes are confusing because they are meaningless, not because you are inexperienced. And every DB vendor implements them differently, yet another reason to avoid them.

You might also like:

1. How to write a SQL exclusion join
2. What is a SQL blind insert?
3. How to select from an update target in MySQL
4. How to write multi-table, cross-database deletes with aliases in MySQL
5. How to delete duplicate rows with SQL, Part 2