Добро пожаловать в форум, Guest  >>   Войти | Регистрация | Поиск | Правила | В избранное | Подписаться
Все форумы / Microsoft SQL Server Новый топик    Ответить
 BETWEEN - Join: как оптимизировать запрос  [new]
KPEMEHb
Member

Откуда:
Сообщений: 18
Всем привет.

Вполне тривиальная задача. Есть 2 таблицы:
Таблица 1 - лог интернет-запросов. В таблице имеется поле с IP адресом (в формате bigint)
Tаблица 2 - географическое распределение IP-областей с полями IP_FROM, IP_TO и ID страны.

Требуется создать запрос, в котором каждому IP из первой таблицы в соответствие будет поставлен ID страны. Важно: Таблица 2 может быть неполной, т.е. необходимо использовать OUTER JOIN.

У меня никак не получается создать оптимальный запрос. Может быть у кого-то есть идеи, как это сделать?

Ниже - пример.
Таблица T1 c 1 млн. записей - это аналог лога запросов
Таблица T2 с 100 тыс. записей - это географическое распределение IP адресов.

IF OBJECT_ID('T1', 'U') IS NOT NULL 
	DROP TABLE T1
GO
IF OBJECT_ID('T2', 'U') IS NOT NULL 
	DROP TABLE T2
GO

CREATE TABLE T1 (ID bigint, IP bigint, PRIMARY KEY CLUSTERED(ID));
GO
CREATE TABLE T2 (ID bigint, IP_FROM bigint, IP_TO bigint, PRIMARY KEY CLUSTERED(ID));
GO

WITH S1 (N) AS (SELECT 1 UNION ALL SELECT 2),
S2 (N) AS (SELECT 1 FROM S1, S1 B),
S3 (N) AS (SELECT 1 FROM S2, S2 B),
S4 (N) AS (SELECT 1 FROM S3, S3 B),
S5 (N) AS (SELECT 1 FROM S4, S4 B),
S6 (N) AS (SELECT 1 FROM S5, S5 B),
Nums (N) AS (SELECT Row_Number() OVER (ORDER BY (SELECT 1)) FROM S6)
INSERT INTO T1(ID, IP)
SELECT N, N
FROM Nums
WHERE N <= 1000000;
GO

WITH S1 (N) AS (SELECT 1 UNION ALL SELECT 2),
S2 (N) AS (SELECT 1 FROM S1, S1 B),
S3 (N) AS (SELECT 1 FROM S2, S2 B),
S4 (N) AS (SELECT 1 FROM S3, S3 B),
S5 (N) AS (SELECT 1 FROM S4, S4 B),
S6 (N) AS (SELECT 1 FROM S5, S5 B),
Nums (N) AS (SELECT Row_Number() OVER (ORDER BY (SELECT 1)) FROM S6)
INSERT INTO T2(ID, IP_FROM, IP_TO)
SELECT N, (N-1)*10 + 1, N*10
FROM Nums
WHERE N <= 100000;
GO

UPDATE STATISTICS T1
UPDATE STATISTICS T2
GO

-- работает ужасно медленно
SELECT
	T1.ID, T2.ID
FROM 
	T1
	LEFT JOIN T2 ON
		T1.IP BETWEEN T2.IP_FROM AND T2.IP_TO

-- работает быстро, но только с INNER JOIN, а требуется OUTER JOIN :(
SELECT
	T1.ID, T2.ID
FROM 
	T2
	INNER JOIN T1 ON
		T1.IP BETWEEN T2.IP_FROM AND T2.IP_TO
OPTION (FORCE ORDER)
14 ноя 12, 14:42    [13472344]     Ответить | Цитировать Сообщить модератору
 Re: BETWEEN - Join: как оптимизировать запрос  [new]
iap
Member

Откуда: Москва
Сообщений: 47083
KPEMEHb,

индексы на IP, IP_FROM и IP_TO были бы намного полезнее PK в данном случае, а?
Хотя, конечно, и PK должен быть в каждой таблице.
14 ноя 12, 14:48    [13472390]     Ответить | Цитировать Сообщить модератору
 Re: BETWEEN - Join: как оптимизировать запрос  [new]
iap
Member

Откуда: Москва
Сообщений: 47083
iap
KPEMEHb,

индексы на IP, IP_FROM и IP_TO были бы намного полезнее PK в данном случае, а?
Хотя, конечно, и PK должен быть в каждой таблице.
Нет, не помогают.
14 ноя 12, 15:08    [13472586]     Ответить | Цитировать Сообщить модератору
 Re: BETWEEN - Join: как оптимизировать запрос  [new]
KPEMEHb
Member

Откуда:
Сообщений: 18
Ну, попробуйте предложить какие-нибудь индексы, увеличивающие производительность первого запроса.
По моим наблюдениям, любой индекс в данной ситуации лишь усугубляет ситуацию. Конечно можно сделать индекс на поле IP в первой таблице и составной индех на поля IP_FROM и IP_TO во второй таблице, но это лишь ускорит жутко неоптимальный (в данном конкретном случае) LOOP JOIN.
А вот как добиться того, чтобы производительность была как во втором запросе?
Кстати, если бы не BETWEEN, то можно было бы использовать HASH JOIN, но почему-то в том случае, когда таблицы объединяются с помощью BETWEEN - условия, SQL Server считает, что HASH JOIN не возможен :(
14 ноя 12, 15:17    [13472712]     Ответить | Цитировать Сообщить модератору
 Re: BETWEEN - Join: как оптимизировать запрос  [new]
Ivan Durak
Member

Откуда: Minsk!!!
Сообщений: 3684
Пробуй

CREATE NONCLUSTERED INDEX IX_T2_IP2 ON T2 (IP_TO, IP_FROM)
GO

SELECT
	T1.ID, T2.ID
FROM 
	T2
	INNER JOIN T1 ON
		T1.IP BETWEEN T2.IP_FROM AND T2.IP_TO
UNION ALL

SELECT
	T1.ID, NULL
FROM 
T1
WHERE NOT EXISTS (select ID FROM T2 WHERE T1.IP >= IP_FROM  and T1.IP <= IP_TO)
14 ноя 12, 15:24    [13472783]     Ответить | Цитировать Сообщить модератору
 Re: BETWEEN - Join: как оптимизировать запрос  [new]
KPEMEHb
Member

Откуда:
Сообщений: 18
Спасибо за ответ. Но штука с NOT EXISTS работает только до тех пор, пока количество не найденных IP-областей маленькое.

Я поменял исходные данные - теперь для трети IP-адресов в таблице с IP областями нет подходящей записи. И тогда вторая часть запроса с NOT EXISTS длится ужасно долго.

Что я не понимаю - это почему в случае BETWEEN-связки между таблицами обязательно используется LOOP JOIN.
Почему нельзя использовать HASH JOIN? Почему на попытку вручную использовать LEFT HASH JOIN, SQL Server выдает ошибку "Query processor could not produce a query plan because of the hints defined in this query."?

Вот пример с новыми даными:

IF OBJECT_ID('T1', 'U') IS NOT NULL 
	DROP TABLE T1
GO
IF OBJECT_ID('T2', 'U') IS NOT NULL 
	DROP TABLE T2
GO

CREATE TABLE T1 (ID bigint, IP bigint, PRIMARY KEY CLUSTERED(ID));
GO
CREATE TABLE T2 (ID bigint, IP_FROM bigint, IP_TO bigint, PRIMARY KEY CLUSTERED(ID));
GO

WITH S1 (N) AS (SELECT 1 UNION ALL SELECT 2),
S2 (N) AS (SELECT 1 FROM S1, S1 B),
S3 (N) AS (SELECT 1 FROM S2, S2 B),
S4 (N) AS (SELECT 1 FROM S3, S3 B),
S5 (N) AS (SELECT 1 FROM S4, S4 B),
S6 (N) AS (SELECT 1 FROM S5, S5 B),
Nums (N) AS (SELECT Row_Number() OVER (ORDER BY (SELECT 1)) FROM S6)
INSERT INTO T1(ID, IP)
SELECT N, N
FROM Nums
WHERE N <= 1000000;
GO

WITH S1 (N) AS (SELECT 1 UNION ALL SELECT 2),
S2 (N) AS (SELECT 1 FROM S1, S1 B),
S3 (N) AS (SELECT 1 FROM S2, S2 B),
S4 (N) AS (SELECT 1 FROM S3, S3 B),
S5 (N) AS (SELECT 1 FROM S4, S4 B),
S6 (N) AS (SELECT 1 FROM S5, S5 B),
Nums (N) AS (SELECT Row_Number() OVER (ORDER BY (SELECT 1)) FROM S6)
INSERT INTO T2(ID, IP_FROM, IP_TO)
SELECT N, (N-1)*10 + 1, N*10
FROM Nums
WHERE N <= 100000 AND N % 3 < 2;;
GO

-- работает ужасно медленно
SELECT
	T1.ID, T2.ID
FROM 
	T1
	LEFT JOIN T2 ON
		T1.IP BETWEEN T2.IP_FROM AND T2.IP_TO

-- работает быстро, но только с INNER JOIN, а требуется OUTER JOIN :(
SELECT
	T1.ID, T2.ID
FROM 
	T2
	INNER JOIN T1 ON
		T1.IP BETWEEN T2.IP_FROM AND T2.IP_TO
OPTION (FORCE ORDER)

--пример с NOT EXISTS

CREATE NONCLUSTERED INDEX IX_T2_IP2 ON T2 (IP_TO, IP_FROM)
GO

SELECT
	T1.ID, T2.ID
FROM 
	T2
	INNER JOIN T1 ON
		T1.IP BETWEEN T2.IP_FROM AND T2.IP_TO
UNION ALL 
SELECT
	T1.ID, NULL
FROM 
T1
WHERE NOT EXISTS (select ID FROM T2 WHERE T1.IP >= IP_FROM  and T1.IP <= IP_TO)
14 ноя 12, 21:50    [13475108]     Ответить | Цитировать Сообщить модератору
 Re: BETWEEN - Join: как оптимизировать запрос  [new]
Добрый Э - Эх
Guest
KPEMEHb
Что я не понимаю - это почему в случае BETWEEN-связки между таблицами обязательно используется LOOP JOIN.
Почему нельзя использовать HASH JOIN? Почему на попытку вручную использовать LEFT HASH JOIN, SQL Server выдает ошибку "Query processor could not produce a query plan because of the hints defined in this query."?
Все потому, что таков уж механизм соединения по HASH-у, что требует в условии соединения строгое равенство. Если же таблицы соединяются неравенством, коим BETWEEN и является, то HASH JOIN неприменим в принципе.
15 ноя 12, 04:46    [13475933]     Ответить | Цитировать Сообщить модератору
 Re: BETWEEN - Join: как оптимизировать запрос  [new]
нязнайка
Guest
            
            SELECT  
			   T1.IP, 
			   CAST(NULL AS BIGINT) AS [IP_FROM], 
			   CAST(NULL AS BIGINT) AS [IP_TO]
			   
		FROM dbo.T1 AS t1
		LEFT JOIN 
				  ( 

						SELECT
							   t1.IP							   
						FROM dbo.T1 AS t1 
						JOIN dbo.T2 AS t2 
						  ON t1.IP >= T2.IP_FROM AND  t1.IP <=  T2.IP_TO
				  ) AS q 
				ON   q.IP = t1.IP 
		          	
		WHERE q.IP IS NULL 

		UNION ALL

		SELECT
				 T1.IP,
				 t2.IP_FROM,
				 t2.IP_TO
							   
		FROM dbo.T1 AS t1
		
		JOIN dbo.T2 AS t2 
		   ON  t1.IP >= T2.IP_FROM AND  t1.IP <=  T2.IP_TO



Если сравнивать планы запросов (INNER vs LEFT OUTER), то видно в случае inner оптимизатор переворачивает запрос.
Т.е сканируется T2 и для каждой записи делается поиск в T1.
А т.к записей в T2 всего ~66 тыс, то нам нужно сделать всего 66 тыс циклов вместо 1 млн для inner.
Т.е время пропоционально числу строк, которые необходимо обработать.
Это хорошо видно для след. запросов :

SET STATISTICS TIME ON 

SELECT COUNT(*)
FROM(
SELECT
	  TOP(50000) t1.IP

FROM 
	T1 AS t1  
ORDER BY t1.IP		
) AS t1 
	
	LEFT JOIN T2 ON
		T1.IP BETWEEN T2.IP_FROM AND T2.IP_TO
		

SELECT COUNT(*)
FROM(
SELECT
	  TOP(100000) t1.IP

FROM 
	T1 AS t1  
ORDER BY t1.IP		
) AS t1 
	
	LEFT JOIN T2 ON
		T1.IP BETWEEN T2.IP_FROM AND T2.IP_TO	



И вот результаты :

 SQL Server Execution Times:
   CPU time = 4041 ms,  elapsed time = 4032 ms.

 SQL Server Execution Times:
   CPU time = 15381 ms,  elapsed time = 15420 ms.


А другие алгоритмы алгоритмы не могут быть применены. Чем больше строк - тем дольше будет работать запрос.
Я думаю вряд ли можно улучшить запрос.
15 ноя 12, 12:47    [13477527]     Ответить | Цитировать Сообщить модератору
 Re: BETWEEN - Join: как оптимизировать запрос  [new]
KPEMEHb
Member

Откуда:
Сообщений: 18
Добрый Э - Эх
Все потому, что таков уж механизм соединения по HASH-у, что требует в условии соединения строгое равенство. Если же таблицы соединяются неравенством, коим BETWEEN и является, то HASH JOIN неприменим в принципе.


Если быть совсем точным, HASH JOIN требует, чтобы ХОТЯ БЫ ОДНО из условий соединения было строгое равенство, но да, Вы правы :(

Но вот, что интересно. Почему-то такой запрос работает на порядок быстрее, чем обычный LEFT JOIN:

SELECT
	T1.ID, T2.ID
FROM 
	(SELECT ID, IP FROM T1) T1
	LEFT JOIN (SELECT ID, IP_FROM, IP_TO FROM T2) T2 ON
		T1.IP BETWEEN T2.IP_FROM AND T2.IP_TO


А если к этому добавить такой индекс, то производительность становится вполне приличной - конечно не как при INNER JOIN, но вполне терпимо.
CREATE INDEX IX_1 ON T2(IP_FROM, IP_TO) INCLUDE (ID)
15 ноя 12, 13:07    [13477739]     Ответить | Цитировать Сообщить модератору
 Re: BETWEEN - Join: как оптимизировать запрос  [new]
Гость333
Member

Откуда:
Сообщений: 3683
KPEMEHb
Что я не понимаю - это почему в случае BETWEEN-связки между таблицами обязательно используется LOOP JOIN.
Почему нельзя использовать HASH JOIN? Почему на попытку вручную использовать LEFT HASH JOIN, SQL Server выдает ошибку "Query processor could not produce a query plan because of the hints defined in this query."?

Потому, что применение хэш-функции к отсортированным данным выдаёт неотсортированную последовательность. Выполните такой запрос (%%lockres%% — это недокументированная функция, выдающая хэшированное значение индекса):
CREATE TABLE #TMP (ID DECIMAL(10,0) IDENTITY PRIMARY KEY CLUSTERED);
GO
INSERT #TMP DEFAULT VALUES;
GO 10
SELECT ID, %%lockres%% FROM #TMP;
DROP TABLE #TMP;
GO

Результат:
ID                                      
--------------------------------------- --------------------------------
1 (01008cff27c2)
2 (01006ff8a84c)
3 (0100f1f80280)
4 (0100e8f1c78a)
5 (010076f16d46)
6 (010095f6e2c8)
7 (01000bf64804)
8 (0100a7e468dd)
9 (010039e4c211)
10 (0100dae34d9f)

Теперь подумайте, можно ли каким-то образом узнать, что, например, значение хэш-функции для ID=5 (010076f16d46) должно быть между значениями хэш-функции для ID=4 и 6, то есть (0100e8f1c78a) и (010095f6e2c8)? ;-)
15 ноя 12, 13:16    [13477807]     Ответить | Цитировать Сообщить модератору
 Re: BETWEEN - Join: как оптимизировать запрос  [new]
KPEMEHb
Member

Откуда:
Сообщений: 18
Нашел!!!!

WITH T(ID1, ID2) AS
(
	SELECT
		T1.ID, T2.ID
	FROM 
		T1
		INNER JOIN T2 ON
			T1.IP BETWEEN T2.IP_FROM AND T2.IP_TO
)
SELECT T1.ID, T.ID2
FROM 
	T1
	LEFT JOIN T ON
		T.ID1 = T1.ID
15 ноя 12, 13:16    [13477810]     Ответить | Цитировать Сообщить модератору
Все форумы / Microsoft SQL Server Ответить