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

Откуда:
Сообщений: 479
Добрый день!
Для сопоставления имеющейся номенклатуры товаров и поступающих прайс листов, для выбора оптимальной цены (или хотя бы подсказки оператору) использую алгоритм N-Gram.

Для не очень больших данных (прайс на 45432 записей) попытка найти оптимальную цену для 1055 записей занимает 9-10 минут....
Видимо я что-то не так делаю.
Пожалуйста, помогите оптимизировать запрос.

Больной:
select s.TMCCod, b.* 
from dbo.PriceSeek s
cross apply dbo.fnGetBestPrice2(s.TMCCod, s.Quantity, 0.55) b
where s.Query='1126D775-B6C8-40BA-BC02-D2A15F2A7FBA'


P.S.
На основании плана выполнения запроса ясно, что 71% тратится на

Clustered Index Seek(OBJECT:([Forecast].[dbo].[PriceNGrams].[PK_PriceNGrams] AS [S1]), SEEK:([S1].[NGram] > [Expr1093] AND [S1].[NGram] < [Expr1094]), WHERE:([Forecast].[dbo].[PriceNGrams].[NGram] as [S1].[NGram] like [Forecast].[dbo].[TMCNGrams].[NGram] as [S2].[NGram]) ORDERED FORWARD)

Таблицы:
CREATE TABLE [dbo].[TMC](
	[Cod]			[int] IDENTITY(1,1) NOT NULL,
	[Name]			[varchar](80) NOT NULL,
	.....
	CONSTRAINT [PK_TMC] PRIMARY KEY CLUSTERED ([Cod])
) -- 27992 rows

CREATE TABLE [dbo].[ORD_PRICES](
	[ID]			[int] IDENTITY(1,1) NOT NULL,
	[SUPPID]		[int] NOT NULL,
	[SUPPTMCID]		[varchar](20) NOT NULL,
	[SUPPTMCNAME]	[varchar](200) NOT NULL,
	[PRICERUB]		[decimal](15, 2) NULL,
	[PRICE]			[decimal](15, 2) NULL,
	[QUANTITY]		[decimal](15, 2) NULL,
	[MINORDERQTY]	[int] NULL,
	.....
	CONSTRAINT [PK_TMC] PRIMARY KEY CLUSTERED ([Cod])	
) -- 45432 rows
CREATE INDEX [IX_SUPPID] ON [dbo].[ORD_PRICES] ([SUPPID]) INCLUDE ( [ID], [SUPPTMCID], [SUPPTMCNAME], [PRICERUB])

CREATE TABLE [dbo].[TMCNGrams](
	[TMCCod] [int] NOT NULL,
	[NGram] [char](3) NOT NULL,
	[NGramCount] [smallint] NOT NULL,
	CONSTRAINT [PK_TMCNGrams] PRIMARY KEY CLUSTERED ([NGram], [TMCCod])
)  -- 902403
CREATE INDEX IX_TMCNGrams_TMCCod ON [dbo].[TMCNGrams] ([TMCCod])

CREATE TABLE [dbo].[TMCCount](
	[TMCCod] [int] NOT NULL,
	[NGramCount] [int] NOT NULL,
 CONSTRAINT [PK_TMCCount] PRIMARY KEY CLUSTERED ([TMCCod])
) -- 27992 rows

CREATE TABLE [dbo].[PriceNGrams](
	[PriceID] [int] NOT NULL,
	[NGram] [char](3) NOT NULL,
	[NGramCount] [smallint] NOT NULL,
	CONSTRAINT [PK_PriceNGrams] PRIMARY KEY CLUSTERED ([NGram], [PriceID])
)  -- 902403 rows
CREATE INDEX IX_PriceNGrams_TMCCod ON [dbo].[PriceNGrams] ([PriceID])

CREATE TABLE [dbo].[PriceCount](
	[PriceID] [int] NOT NULL,
	[NGramCount] [int] NOT NULL,
 CONSTRAINT [PK_PriceCount] PRIMARY KEY CLUSTERED ([PriceID])
) -- 45432 rows

CREATE TABLE [dbo].[PriceSeek](
	[ID] [int] IDENTITY(1,1) NOT NULL,
	[Query] [uniqueidentifier] NOT NULL,
	[TMCCod] [int] NOT NULL,
	[Quantity] [int] NOT NULL,
 CONSTRAINT [PK_PriceSeek] PRIMARY KEY CLUSTERED ([ID])
) – 1055 rows

Данные в dbo.TMCNGrams и dbo.PriceNGrams попадают на основании запросов:

insert into dbo.TMCNGrams (TMCCod, NGram, NGramCount)
select t.Cod TMCCod, p.NGram, p.NGramCount
from Store.dbo.TMC t
cross apply dbo.cStrToGrams(t.Name, 3) p

insert into dbo.TMCCount (TMCCod, NGramCount)
select TMCCod, sum(NGramCount) NGramCount 
FROM dbo.TMCNGrams 
GROUP BY TMCCod

и

insert into dbo.PriceNGrams (PriceID, NGram, NGramCount)
select o.ID PriceID, p.NGram, p.NGramCount
from uniorder.dbo.ORD_PRICES o
cross apply dbo.cStrToGrams(o.SUPPTMCNAME, 3) p

insert into dbo.PriceCount (PriceID, NGramCount)
select PriceID, sum(NGramCount) NGramCount 
FROM dbo.PriceNGrams 
GROUP BY PriceID

Где cStrToGrams – процедура разбивающая строки на граммы.

-- процедура поиска оптимальной цены по прайсу 
create function dbo.fnGetBestPrice2(@TMCCod int, @Quantity int, @MinRelevance float = 0.55)
RETURNS TABLE AS
RETURN (
select top 1
  p.*, s.*, sp.NAME SUPP_NAME
from (
SELECT
    Relevance = (convert(float, count(*)) / 
      (SELECT NGramCount FROM dbo.PriceCount WHERE PriceID = S1.PriceID) +                 
       convert(float, count(*)) /
      (SELECT NGramCount FROM dbo.TMCCount WHERE TMCCod=@TMCCod)) / 2,
    DuplicateCod = S1.PriceID
  FROM dbo.PriceNGrams S1 
  JOIN dbo.TMCNGrams S2 ON S2.TMCCod=@TMCCod AND S1.NGram like S2.NGram
  GROUP BY S1.PriceID
  HAVING
    (convert(float, count(*)) /
    (SELECT NGramCount FROM dbo.PriceCount WHERE PriceID = S1.PriceID) +
     convert(float, count(*)) /
    (SELECT NGramCount FROM dbo.TMCCount WHERE TMCCod=@TMCCod)) / 2 >= @MinRelevance
) s
inner join uniorder.dbo.ORD_PRICES p on s.DuplicateCod=p.ID
inner join uniorder.dbo.ORD_SUPPLIERS sp on p.SUPPID=sp.ID
where
	  IsNull(p.QUANTITY,0)-@Quantity>2
  and case when IsNull(p.MINORDERQTY,0)=0 then @Quantity else MINORDERQTY end >=@Quantity
order by 
  s.Relevance desc,
  p.PRICERUB
)


С Уважением,
Александр.
4 апр 14, 16:09    [15833970]     Ответить | Цитировать Сообщить модератору
 Re: N-Gram и как его готовить?  [new]
Владислав Колосов
Member

Откуда:
Сообщений: 8570
Попробуйте отобрать предварительно во временную таблицу PriceSeek , а затем применяйте функцию.
4 апр 14, 16:25    [15834078]     Ответить | Цитировать Сообщить модератору
 Re: N-Gram и как его готовить?  [new]
Lisichkin
Member

Откуда:
Сообщений: 479
PriceSeek - и есть временная таблица в которой хранится список товаров (из справочника ТМЦ) для которых нужно подобрать товар из прайса.

P.S. Прошу прощения - описался в таблице dbo.PriceNGrams - 1639725 записей.
P.S.S. MS SQL Server 2008 R2
4 апр 14, 16:28    [15834094]     Ответить | Цитировать Сообщить модератору
 Re: N-Gram и как его готовить?  [new]
Владислав Колосов
Member

Откуда:
Сообщений: 8570
Я к тому, что сначала надо применить фильтр s.Query='1126D775-B6C8-40BA-BC02-D2A15F2A7FBA' , а потом использовать функцию. Сервер может поступить иначе.
4 апр 14, 16:37    [15834141]     Ответить | Цитировать Сообщить модератору
 Re: N-Gram и как его готовить?  [new]
Lisichkin
Member

Откуда:
Сообщений: 479
А, Вы об этом - можете не беспокоится в таблице PriceSeek существуют записи только с одним Query = '1126D775-B6C8-40BA-BC02-D2A15F2A7FBA'
4 апр 14, 16:41    [15834162]     Ответить | Цитировать Сообщить модератору
 Re: N-Gram и как его готовить?  [new]
invm
Member

Откуда: Москва
Сообщений: 9719
1.
S1.NGram like S2.NGram
Почему тут like?

2.
SELECT
    Relevance = (convert(float, count(*)) / 
      (SELECT NGramCount FROM dbo.PriceCount WHERE PriceID = S1.PriceID) +                 
       convert(float, count(*)) /
      (SELECT NGramCount FROM dbo.TMCCount WHERE TMCCod=@TMCCod)) / 2,
    DuplicateCod = S1.PriceID
  FROM dbo.PriceNGrams S1 
  JOIN dbo.TMCNGrams S2 ON S2.TMCCod=@TMCCod AND S1.NGram like S2.NGram
  GROUP BY S1.PriceID
Из этого куска можно соорудить индексированное представление.

3. Переписать запрос без cross apply.
4 апр 14, 17:13    [15834299]     Ответить | Цитировать Сообщить модератору
 Re: N-Gram и как его готовить?  [new]
Lisichkin
Member

Откуда:
Сообщений: 479
1. Реализацию алгоритма N-Gram я взял от сюда [url=]http://www.arbinada.com/main/node/20[/url] - Там стоит Like.
Если докажете что нужно иное - исправлю. :)

2. В указанном куске есть параметр @TMCCod, как создать индексированное представление?
4 апр 14, 17:20    [15834333]     Ответить | Цитировать Сообщить модератору
 Re: N-Gram и как его готовить?  [new]
invm
Member

Откуда: Москва
Сообщений: 9719
Lisichkin
Если докажете что нужно иное - исправлю. :)
Я не собираюсь ничего вам доказывать. Можете прочитать документацию по like, проанализировать ваши данные и самостоятельно принять решение. Либо спросите автора статьи зачем там like, если нет сравнения с шаблоном.
Lisichkin
В указанном куске есть параметр @TMCCod, как создать индексированное представление?
Абстрагируйтесь от наличия переменной.
4 апр 14, 18:17    [15834615]     Ответить | Цитировать Сообщить модератору
 Re: N-Gram и как его готовить?  [new]
Lisichkin
Member

Откуда:
Сообщений: 479
invm

Развив Ваше предложение №2:
Создать таблицу-индекс:
CREATE TABLE [dbo].[TMC2Price](
	[TMCCod] [int] NOT NULL,
	[PriceID] [int] NOT NULL,
	[Relevance] [float] NOT NULL,
 CONSTRAINT [PK_TMC2Price] PRIMARY KEY CLUSTERED ([TMCCod],[PriceID] )
)

Заполнить ее:
insert dbo.TMC2Price (TMCCod, PriceID, Relevance)
select t.Cod TMCCod, s.DuplicateCod PriceID, s.DuplicateCod 
from Store.dbo.TMC t
cross apply 
(
  SELECT
    Relevance = (convert(float, count(*)) / 
      (SELECT NGramCount FROM dbo.PriceCount WHERE PriceID = S1.PriceID) +                 
       convert(float, count(*)) /
      (SELECT NGramCount FROM dbo.TMCCount WHERE TMCCod=t.Cod)) / 2,
    DuplicateCod = S1.PriceID
  FROM dbo.PriceNGrams S1 
  JOIN dbo.TMCNGrams S2 ON S2.TMCCod=t.Cod AND S1.NGram like S2.NGram
  GROUP BY S1.PriceID
  HAVING
    (convert(float, count(*)) /
    (SELECT NGramCount FROM dbo.PriceCount WHERE PriceID = S1.PriceID) +
     convert(float, count(*)) /
    (SELECT NGramCount FROM dbo.TMCCount WHERE TMCCod=t.Cod)) / 2 >= 0.55) s

Переписать процедуру поиска оптимальной цены по прайсу:
create function dbo.fnGetBestPrice2(@TMCCod int, @Quantity int)
RETURNS TABLE AS
RETURN (
select top 1
  p.*, s.*, sp.NAME SUPP_NAME
from dbo.TMC2Price s 
inner join uniorder.dbo.ORD_PRICES p on s.PriceID=p.ID
inner join uniorder.dbo.ORD_SUPPLIERS sp on p.SUPPID=sp.ID
where
	  IsNull(p.QUANTITY,0)-@Quantity>2
  and case when IsNull(p.MINORDERQTY,0)=0 then @Quantity else MINORDERQTY end >=@Quantity
order by 
  s.Relevance desc,
  p.PRICERUB
)

Тогда поиск оптимальной цены будет занимать 17 секунд…Ура!?
Но заполнение таблицы dbo.TMC2Price (для всех товаров из номенклатуры - 27992 записей) выполняется за ....5 часов 11 минут..

:(
5 апр 14, 18:25    [15837603]     Ответить | Цитировать Сообщить модератору
 Re: N-Gram и как его готовить?  [new]
Lisichkin
Member

Откуда:
Сообщений: 479
Так просто мысли в слух…:

FROM Store.dbo.TMC t
JOIN dbo.PriceNGrams S1 ON 1=1

Store.dbo.TMC (27992) * dbo.PriceNGrams (1639725) = 45899182200 (45,9 миллиардов)
5 апр 14, 19:09    [15837713]     Ответить | Цитировать Сообщить модератору
 Re: N-Gram и как его готовить?  [new]
invm
Member

Откуда: Москва
Сообщений: 9719
1.
create view dbo.vRelevance
with schemabinding
as
select
 s1.TMCCod,
 s2.PriceID as DuplicateCod,
 count_big(*) as cnt,
 (convert(float, count(*)) / pc.NGramCount + convert(float, count(*)) / tc.NGramCount) / 2 as Relevance
from
 dbo.TMCNGrams s1 join 
 dbo.PriceNGrams s2 on s2.NGram = s1.NGram join
 dbo.PriceCount pc on pc.PriceID = s1.PriceID join
 dbo.TMCCount tc on tc.TMCCod = s2.TMCCod
group by
 s1.TMCCod,
 s2.PriceID;
go

create unique clustered index IX_vRelevance__Relevance__TMCod__DuplicateCod on dbo.vRelevance (Relevance, TMCod, DuplicateCod);

/*А может быть вот так
create unique clustered index IX_vRelevance__TMCod__DuplicateCod on dbo.vRelevance (TMCod, DuplicateCod);
create unique index IX_vRelevance__Relevance__TMCod__DuplicateCod on dbo.vRelevance (Relevance, TMCod, DuplicateCod);
*/
go

2.
with x as
(
 select
  s.TMCod, p.*, r.*, sp.NAME as SUPP_NAME,
  row_number() over (partition by s.TMCCod order by r.Relevance, p.PRICERUB) as rn
 from
  dbo.PriceSeek s join
  dbo.vRelevance r with (noexpand) on r.TMCCod = s.TMCCod and r.Relevance <= 0.55 join
  uniorder.dbo.ORD_PRICES p on p.ID = r.DuplicateCod join
  uniorder.dbo.ORD_SUPPLIERS sp on sp.ID = p.SUPPID
 where
  s.Query='1126D775-B6C8-40BA-BC02-D2A15F2A7FBA' and
  p.QUANTITY - s.Quantity > 2 and
  isnull(p.MINORDERQTY, s.Quantity) >= s.Quantity
)
select
 *
from
 x
where
 rn = 1;
5 апр 14, 23:41    [15838346]     Ответить | Цитировать Сообщить модератору
Все форумы / Microsoft SQL Server Ответить