Попарные пересечения
https://dba.stackexchange.com/questions/103961
-
26-09-2020 - |
italiano
english
français
española
中国
日本の
العربية
Deutsch
한국어
Português
RussianВопрос
У меня есть таблица с двумя столбцами, скажем, FirstName и LastName.Мне нужно получить другую таблицу, которая для каждой пары имен из первой содержит количество общих фамилий.
Возможно ли это вообще сделать в SQL?
Существует гораздо больше уникальных фамилий, чем имен, если это влияет на эффективность запроса.
Игрушечный пример, ввод:
FirstName, LastName
John, Smith
John, Doe
Jane, Doe
Выход:
FirstName1, FirstName2, CommonLastNames
John, John, 2
John, Jane, 1
Jane, Jane, 1
Jane, John, 1
Поскольку это отношение рефлексивно и симметрично, ничего страшного, если результатом будет только один из треугольников (например, тот, что выше диагонали).
Решение
Я собираюсь использовать MS SQL Server для этого, так как у меня есть копия под рукой.Я думаю, что большинство крупных компаний поступили бы точно так же.
Сначала приведем пример таблицы с данными.Я использую табличную переменную, но она одинакова для любого типа таблицы.
declare @t table (FirstName char(10), LastName char(10));
insert @t(FirstName,LastName)
values ('John','Smith'),('John','Doe'),('Jane','Doe');
Вы можете получить все пары, выполнив самостоятельное соединение:
select
a.FirstName, a.LastName, b.FirstName, b.LastName
from @t as a
cross apply @t as b;
С помощью CROSS APPLY позволяет избежать необходимости перепрыгивать через обручи, чтобы найти условие соединения для ON пункт.
Далее вам нужно что-то подсчитать.Это то место, где CASE поступает заявление.Регистр возвращает целочисленное значение для каждой пары имен, которое и засчитывается.(Если я правильно понимаю ваш вопрос, вы хотите, чтобы фамилии совпадали, так что это сравнение у меня есть.Надеюсь, очевидно, как это изменить, если я ошибаюсь.)
select
...
case
when a.LastName = b.LastName then 1
else 0
end
...etc.
Добавьте в SUM() и GROUP BY и вы получите свой ответ:
select
a.FirstName,
b.FirstName,
sum(
case
when a.LastName = b.LastName then 1
else 0
end
) as CommonLastNames
from @t as a
cross apply @t as b
group by a.FirstName, b.FirstName;
Другие советы
Я должен признать, что мой вопрос был немного ошибочным. То, что мне действительно нужно, не было «для каждой пары первого имени от первого содержит счет общей фаната».На самом деле, мне не волнует пары с нулевым количеством.
Когда вопрос исправлен, решение становится намного быстрее.
Учитывая вход:
create local temp table t (FirstName char(10), LastName char(10)) ON COMMIT PRESERVE ROWS;
insert into t(FirstName,LastName) values ('John','Smith');
insert into t(FirstName,LastName) values ('John','Doe');
insert into t(FirstName,LastName) values ('Jane','Doe');
Для оригинального вопроса решения o (n ^ 2) (потому что вопрос настаивает на «каждую пару»):
select a.FirstName, b.FirstName,
sum(case when a.LastName = b.LastName then 1 else 0 end) CommonNames
from t a, t b group by 1, 2;
Если это нормально, чтобы пропустить отсчет нуля, то самостоятельно присоединяется к фамилию, работает намного быстрее (при условии, что данные достаточно редки):
select a.FirstName, b.FirstName,
count(*) CommonNames from t a
join t b using (LastName) group by 1, 2;
Мне все еще интересно, как я пропустил этот тривиальный раствор.
дой!Вот лучший способ:
SELECT city_a, city_b, COUNT(*)
FROM (
SELECT a.city city_a,
a.state,
b.city city_b
FROM us a
CROSS JOIN us b
WHERE a.state = b.state
AND a.city < b.city
) x
GROUP BY city_a, city_b
ORDER BY 3 DESC;
Выход:
+-----------+-------------+----------+
| city_a | city_b | COUNT(*) |
+-----------+-------------+----------+
| Lebanon | Springfield | 5 |
| Bedford | Franklin | 4 | -- as shown in previous 'answer'
| Franklin | Lebanon | 4 |
| Franklin | Hudson | 4 |
| Franklin | Salem | 4 |
| Hudson | Salem | 4 |
| Salem | Springfield | 4 |
| Clinton | Columbia | 4 |
| Auburn | Fairfield | 3 |
| Auburn | Madison | 3 |
...
(2.63 sec) -- for all 4175 cities in `us`.
Проверка здравоохранения на первом элементе:
mysql> SELECT city, state FROM us WHERE city IN ('Lebanon', 'Springfield');
+-------------+-------+
| city | state |
+-------------+-------+
| Springfield | FL |
| Springfield | IL |
| Lebanon | IN |
| Springfield | MA |
| Lebanon | ME |
| Lebanon | MO |
| Springfield | MO |
| Lebanon | NH |
| Springfield | NJ |
| Lebanon | OH |
| Springfield | OH |
| Lebanon | OR |
| Springfield | OR |
| Lebanon | PA |
| Springfield | PA |
| Lebanon | TN |
| Springfield | TN |
| Springfield | VA |
| Springfield | VT |
+-------------+-------+
19 rows in set (0.00 sec)
Основным обработчиком% Значения состояния показывают, что он сделал много работы, но не совсем O (n * n) (вероятно, потому что поперечное соединение - это только одно состояние за раз):
| Handler_read_key | 4176 |
| Handler_read_next | 667294 |
| Handler_read_rnd | 1742 |
| Handler_read_rnd_next | 701964 |
| Handler_update | 1731 |
| Handler_write | 703693 |
экстраполяция до миллионов строк - это, вероятно, займет дни.
Это была интересная задача.Используя список городов США, я придумал это решение (в MySQL):
SELECT city_a, city_b,
COUNT(DISTINCT state)
FROM (
( SELECT a.city city_a,
b.city city_b,
a.state -- This line differs
FROM us a
CROSS JOIN us b
WHERE a.state = b.state
AND a.city != b.city -- Added (to avoid noise)
AND a.city < 'M' -- to speed up test
AND b.city < 'M'
)
UNION ALL
( SELECT a.city city_a,
b.city city_b,
b.state -- This line differs
FROM us a
CROSS JOIN us b
WHERE a.state = b.state
AND a.city != b.city -- Added (to avoid noise)
AND a.city < 'M' -- to speed up test
AND b.city < 'M'
)
) ab
GROUP BY 1, 2
HAVING COUNT(DISTINCT state) > 1
ORDER BY COUNT(DISTINCT state) desc
INDEX(state, city) помогает с производительностью.
Результаты:
+----------+------------+-----------------------+
| city_a | city_b | COUNT(DISTINCT state) |
+----------+------------+-----------------------+
| Franklin | Bedford | 4 |
| Lebanon | Franklin | 4 |
| Franklin | Lebanon | 4 |
| Hudson | Franklin | 4 |
| Columbia | Clinton | 4 |
| Clinton | Columbia | 4 |
| Franklin | Hudson | 4 |
| Bedford | Franklin | 4 |
| Lebanon | Farmington | 3 |
| Hanover | Kingston | 3 |
...
(25.17 sec)
Это могло быть в 4 раза больше, чтобы включить весь алфавит.В таблице были только 4К строки, так что это не быстрая задача.
"Доказательство" результатов: MySQL> Выберите город, штат у нас, где город в («Франклин», «Бедфорд»);
+----------+-------+
| city | state |
+----------+-------+
| Bedford | IN |
| Franklin | IN |
| Bedford | MA |
| Franklin | MA |
| Bedford | NH |
| Franklin | NH |
| Bedford | OH |
| Franklin | OH |
| Franklin | TN |
| Bedford | TX |
| Franklin | WI |
+----------+-------+
11 rows in set (0.00 sec)
