16.1 UNION and UNION ALL

UNIONs have been supported since SQL-86, with this infixed syntax:

< table expression > UNION [ALL] < table expression >

The two versions of the UNION statement take two tables and build a result table from them. The two tables must be union compatible, which means that they have exactly the same number of columns, and that each column in the first table has the same data type (or automatically cast to it) as the column in the same position in the second table. That is, their rows have the same structure, so they can be put in the same final result table. Most implementations will do some data type conversions to create the result table, but this can be implementation-dependent and you should check it out for yourself.

There are two forms of the UNION statement: the UNION and the UNION ALL. The simple UNION is the same operator you had in high school set theory; it returns the rows that appear in either or both tables and removes redundant duplicates from the result table.

The phrase "redundant duplicates" sounds funny; but it means that you leave one copy of the row in the table. The problem is that string equality in SQL works by padding the shorter string with trailing blanks, then comparing them position by position. Which string is retained is implementation defined.

The sample tables will yield:

(SELECT a1 FROM S1
UNION
SELECT a2 FROM S2)

In many early SQL implementations, merge-sorting the two tables discarding duplicates during the sorting did this removal. This had the side effect that the result table is sorted, but you cannot depend on that. Later implementations use hashing, indexing and parallel processing to find the duplicates.

The UNION ALL preserves the duplicates from both tables in the result table. Most early implementations simply appended one table to the other in physical storage. They used file systems based on physically contiguous storage, so this was easy and used the file system code. But, again, you cannot depend on any ordering in the results of either version of the UNION statement. Again, the sample tables will yield:

(SELECT a1 FROM S1
UNION ALL
SELECT a2 FROM S2)

You can assign names to the columns by using the AS operator to make the result set into a derived table, thus:

SELECT rent, utilities, phone
FROM (SELECT a, b, c 
FROM Old_Locations 
WHERE city_name = 'Boston'
UNION
SELECT x, y, z 
FROM New_Locations
WHERE city_name = 'New York')
 AS Cities (rent, utilities, phone);

A few SQL products will attempt to optimize UNIONs if they are made on the same table. Those UNIONs can often be replaced with OR-ed predicates. For example:

SELECT city_name 'Western'
FROM Cities
WHERE market_code = 't'
UNION ALL
SELECT city_name 'Eastern'
FROM Cities
WHERE market_code = 'v'; 

could be rewritten (probably more efficiently) as follows:

SELECT city_name
CASE market_code
WHEN 't' THEN 'Western'
WHEN 'v' THEN 'Eastern' END
FROM Cities
WHERE market_code IN ('v', 't'),

It takes system architecture based on domains rather than tables to optimize UNIONs if they are made on different tables.

Doing a UNION to the same table is the same as a SELECT DISTINCT, but the SELECT DISTINCT will probably run faster and preserve the column names too.

(SELECT * FROM Small_Table1)
UNION
(SELECT * FROM Big_Table)
UNION
(SELECT * FROM Small_Table2);

(SELECT * FROM Small_Table1)
UNION
(SELECT * FROM Small_Table2)
UNION
(SELECT * FROM Big_Table);

((SELECT * FROM Small_Table1)
UNION
(SELECT * FROM Small_Table2)) -– intermediate set
UNION ALL
(SELECT * FROM Big_Table);

SELECT CASE WHEN S1.seq = 1 THEN F1.col1
WHEN S1.seq = 2 THEN F1.col2
ELSE NULL END
FROM Foobar AS F1
CROSS JOIN
Series AS S1(seq)
 WHERE S1.seq IN (1, 2)

16.2 INTERSECT and EXCEPT

The INTERSECT and EXCEPT set operators take two tables and build a new table from them. The two tables must be union compatible, just like with the UNION [ALL] operator. Like the UNION [ALL], the result of an INTERSECT [ALL] or EXCEPT [ALL] should use an AS operator if you want to have names for the result table and its columns.

Oracle was the first major vendor to have the EXCEPT operator with the keyword MINUS. The set difference is the rows in the first table, except for those that also appear in the second table. It answers questions like "Give me all the employees except the salesmen" in a natural manner.

Let's take our two multisets and use them to explain the basic model, by making a mapping between them:

S1 =  {a, a, b, b, c }
↕ ↕ ↕ ↕
S2 =  {a, b, b, b, c, d}

The INTERSECT and EXCEPT operators remove all duplicates from both sets, so we would have:

S1 = {a, b, c }
↕ ↕ ↕
S2 = {a, b, c, d}

and therefore,

S1 INTERSECT S2 = {a, b, c}

and

S2 EXCEPT S1 = {d}
S1 EXCEPT S2 = {}

When you add the ALL option, things are trickier. The mapped pairs become the unit of work. The INTERSECT ALL keeps each pairing, so that

S1 INTERSECT ALL S2 = {a, b, b, c}

and the EXCEPT ALL throws them away, retain what is left in the first set, thus.

S2 EXCEPT ALL S1 = {b, d}

Trying to write the INTERSECT and EXCEPT with other operators is trickier than it looks. It has to be general enough to handle situations where there is no key available and the number of columns is not known.

Standard SQL defines the actions for duplicates in terms of the count of duplicates of matching rows. Let (m) be the number of rows of one kind in S1 and (n) be the number in S2. The UNION ALL will have (m + n) copies of the row. The INTERSECT ALL will have LEAST(m, n) copies. EXCEPT ALL will have the greater of either the first table's count minus the second table's count or zero copies.

The immediate impulse of a programmer is to write the code with EXISTS() predicates. The bad news is that it does not work because of NULLs. This is easier to show with code. Let's redo our two sample tables.

CREATE TABLE S1 (a1 CHAR(1));
INSERT INTO S1 
VALUES ('a'), ('a'), ('b'), ('b'), ('c'), (NULL), (NULL);
CREATE TABLE S2 (a2 CHAR(1));
INSERT INTO S2 
VALUES ('a'), ('b'), ('b'), ('b'), ('c'), ('d'), (NULL);

Now build a view to hold the duplication_cnt of each value in each table.

CREATE VIEW DupCounts (a, s1_dup, s2_dup)
AS
SELECT S.a, SUM(s1_dup), SUM(s2_dup)
FROM (SELECT S1.a1, 1, 0
FROM S1
UNION ALL
 SELECT S2.a2, 0, 1
FROM S2) AS S(a, s1_dup, s2_dup)
GROUP BY S.a, s1_dup, s2_dup;

The GROUP BY will put the NULLs into a separate group giving them the right tallies. Now code is a straightforward implementation of the definitions in Standard SQL.

-- S1 EXCEPT ALL S2
SELECT DISTINCT D1.a, (s1_dup - s2_dup) AS dups
FROM DupCounts AS D1, 
Series AS S1
 WHERE S1.seq <= (s1_dup - s2_dup);
-- S1 INTERSECT ALL S2
SELECT DISTINCT D1.a, 
CASE WHEN s1_dup <= s2_dup
THEN s1_dup ELSE s2_dup END
AS duplication_cnt
FROM DupCounts AS D1, 
Series AS S1
WHERE S1.seq <= CASE WHEN s1_dup <= s2_dup
 THEN s1_dup ELSE s2_dup END;

Notice that we had to use SELECT DISTINCT. Without it, the sample data will produce this table.

a	duplication_cnt
NULL	1
a	1
b	2
b	2 redundant row
c	1

The nonduplicated versions are easy to write from the definitions in the Standards. In effect their duplication tallies are set to one.

-- S1 INTERSECT S2
SELECT D1.a
FROM DupCounts AS D1
 WHERE s1_dup > 0
AND s2_dup > 0;
-- S1 EXCEPT S2
SELECT D1.a
FROM DupCounts AS D1
 WHERE s1_dup > 0
AND s2_dup = 0;
-- S2 EXCEPT S1
SELECT D1.a
 FROM DupCounts AS D1
WHERE s2_dup > 0
AND s1_dup = 0;

SELECT *
FROM S1
WHERE EXISTS
(SELECT *
FROM S2
WHERE S1.a1 = S2.a2);

SELECT *
FROM S2
WHERE EXISTS
(SELECT *
FROM S1
 WHERE S1.a1 = S2.a2);

SELECT DISTINCT S2.*
FROM (S2 INNER JOIN S1 ON S1.a1 = S2.a2);

SELECT DISTINCT S2.*
FROM (S2 LEFT OUTER JOIN S1
ON S1.a1 = S2.a2)
WHERE S1.a1 IS NULL;

-- S1 INTERSECT S2 
SELECT D.a
FROM (SELECT DISTINCT a1 FROM S1
UNION ALL
SELECT DISTINCT a2 FROM S2) AS D(a)
GROUP BY D.a
HAVING COUNT(*) > 1;
-- S1 INTERSECT ALL S2 
SELECT D2.a
FROM (SELECT D1.a, MIN(cnt) AS mincnt
FROM (SELECT a1, COUNT(*) 
FROM S1
 GROUP BY a1
 UNION ALL
 SELECT a2, COUNT(*)
 FROM S2
 GROUP BY a2) AS D1(a, cnt)
 GROUP BY D1.a
 HAVING COUNT(*) > 1) AS D2
INNER JOIN 
Series 
ON seq <= min_cnt;
-- S1 EXCEPT ALL S2 
SELECT D2.a
FROM (SELECT D1.a, SUM(cnt)
FROM (SELECT a1, COUNT(*) 
FROM S1
 GROUP BY a1
 UNION ALL
 SELECT a2, -COUNT(*)
FROM S2
 GROUP BY a2) 
 AS D1(a, cnt)
GROUP BY D1.a
 HAVING SUM(cnt) > 0) 
 AS D2(a, dups)
 INNER JOIN 
 Series ON seq <= D2.dups;

16.3 A Note on ALL and SELECT DISTINCT

Here is a series of observations about the relationship between the ALL option in set operations and the SELECT DISTINCT options in a query from Beught Gunne. The multiset model does not behave like the traditional set theory we know from school.

Given two tables with duplicate values:

CREATE TABLE A (i INTEGER NOT NULL);
INSERT INTO A VALUES (1), (1), (2), (2), (4), (4);
CREATE TABLE B (i INTEGER NOT NULL);
INSERT INTO B VALUES (2), (2), (3), (3);

The UNION and INTERSECT operations have regular behavior in that

(A UNION B) = SELECT DISTINCT (A UNION ALL B) = ((1), (2), (3))
and
(A INTERSECT B) = SELECT DISTINCT (A INTERSECT ALL B) = (2)

However,

(A EXCEPT B) <> SELECT DISTINCT (A EXCEPT ALL B)

Or more literally, (1) <> ((1), (2)) for the tables given in the example. And likewise, we have

  (B EXCEPT A) = SELECT DISTINCT (B EXCEPT ALL A) = (3)

by a coincidence of the particular values used in these tables.

16.4 Equality and Proper Subsets

At one point, when SQL was still in the laboratory at IBM, there was a CONTAINS operator that would tell you if one table was a subset of another. It disappeared in later versions of the language and no vendor picked it up. Set equality was never part of SQL as an operator, so you would have to have used the two expressions ((A CONTAINS B) AND (B CONTAINS A)) to find out.

Today, you can use the methods shown in the section on Relational Division to determine containment or equality. Or you can use set theory expressions, such as NOT EXISTS ((A EXCEPT B) UNION (B EXCEPT A)). Which method is fastest is going to depend on the SQL product and the access method used.

However, Itzak Ben-Gan came up with a novel approach for finding containment and equality that is worth a mention.

SELECT SUM(DISTINCT match_col)
FROM (SELECT CASE 
WHEN S1.col
IN (SELECT S2.col FROM S2)
THEN 1 ELSE -1 END
FROM S1) AS X(match_col)
HAVING SUM(DISTINCT match_col) = :n;

You can set (:n) to 1, 0, or − 1 for each particular test.

When I find a matching row in S1, I get a one; when I find a mismatched row in S1, get a − 1 and they sum together to give me a zero. Therefore, S1 is a proper subset of S2. If they sum to one, then they are equal. If they sum to − 1, they are disjoint.

Another trick for equality is based on the principle that if two sets are equal, then they have the same cardinality. This is necessary but not sufficient. They have the same elements. We can use a windowed count(*) to get the cardinality

EXISTS (SELECT a, COUNT(a) OVER() AS alpha_cardinality
FROM Alphas
EXCEPT
SELECT b, COUNT(b) OVER() AS beta_cardinality
FROM Betas)