Эффективный способ поиска последовательных значений
Каждый "продукт" может иметь до 10000 "сегментированных" строк. Сегменты имеют столбец сортировки, который начинается с 1 для каждого продукта (1, 2, 3, 4, 5, ...) и столбец значений, который может содержать любые значения, такие как (323.113, 5423.231, 873.42, 422.64, 763.1, ...).
Я хотел бы определить потенциальные совпадения для продуктов с учетом подмножества сегментов. Например, если у меня есть 5 значений сегмента в правильном порядке, как я могу эффективно найти все продукты, которые имеют все 5 сегментов в одном и том же порядке где-то в таблице сегментов?
Обновить
Я разместил дополнительный вопрос к этому здесь: найдите ряд данных, используя неточные измерения (нечеткая логика)
3 ответа
Предположим, что таблицы выглядят так:
CREATE TABLE Products
(
ProductId int not null
constraint PK_Products
primary key
,Name varchar(100) not null
)
CREATE TABLE Segments
(
ProductId int not null
constraint FK_Segments__Products
foreign key references Products (ProductId)
,OrderBy int not null
,Value float not null
,constraint PK_Segments
primary key (ProductId, OrderBy)
)
Затем настройте данные поиска во временной таблице:
CREATE TABLE #MatchThis
(
Position int not null
,Value float not null
)
Для N поисковых объектов это должно быть заполнено так
First item 0 <value 1>
Second item 1 <value 2>
Third item 2 <value 3>
...
Nth item N-1 <value N>
Теперь настройте некоторые важные значения. (Это может быть включено в окончательный запрос, но этот способ облегчает чтение и может немного повысить производительность.)
DECLARE
@ItemCount int
,@FirstValue float
-- How many items to be matched ("N", above)
SELECT @ItemCount = count(*)
from #MatchThis
-- The value of the first item in the search set
SELECT @FirstValue = Value
from #MatchThis
where Position = 0
И тогда это просто запрос:
SELECT
pr.Name
,fv.OrderBy -- Required by the Group By, but otherwise can be ignored
from #MatchThis mt
cross join (-- All Segments that match the first value in the set
select ProductId, OrderBy
from Segment
where Value = @FirstValue) fv
inner join Product pr -- Just to get the Product name
on pr.ProductId = fv.ProductId
inner join Segment se
on se.ProductId = fv.ProductId
and se.OrderBy = fv.OrderBy + mt.Position -- Lines them up based on the first value
and se.Value = mt.Value -- No join if the values don't match
group by
pr.Name
,fv.OrderBy
having count(*) = @ItemCount -- Only include if as many segments pulled for this product/segment.OrderBy as are required
Я уверен, что это сработает, но у меня нет времени, чтобы проверить это подробно сейчас. Для оптимизации производительности помимо указанных первичных ключей можно добавить обычный индекс для Segment.Value
Вероятно, наилучший способ сделать это - сохранить денормализованную версию данных.
ProductId, DelimitedList
1 ,323.113,5423.231,873.42,422.64,763.1,
Тогда ваш поиск прост
WHERE DelimitedList LIKE '%,323.113,5423.231,873.42,%'
Вы могли бы сначала сделать стандартный запрос реляционного деления, чтобы вернуть те ProductId значения, которые соответствуют всем значениям (не обязательно в правильном порядке или смежных), чтобы уменьшить количество строк, которые ищутся.
Полный демонстрационный скрипт
/*Set up test tables*/
CREATE TABLE Products(
ProductId int primary key)
CREATE TABLE ProductSegments(
ProductId int REFERENCES Products,
Sort int,
Value decimal(10,3)
Primary key (ProductId,Sort))
CREATE NONCLUSTERED INDEX ix ON ProductSegments(ProductId,Value)
CREATE TABLE ProductSegmentsDenormalized
(
ProductId int REFERENCES Products,
DelimitedList varchar(max)
)
/*Insert some initial data to Products...*/
INSERT INTO Products VALUES (1),(2),(3)
/*... and for ProductSegments*/
;WITH numbers(N)
AS (SELECT TOP 10000 ROW_NUMBER() OVER (ORDER BY (SELECT 0))
FROM master..spt_values v1,
master..spt_values v2)
INSERT INTO ProductSegments
(ProductId,
Sort,
Value)
SELECT ProductId AS Product,
n1.N Sort,
( ABS(CHECKSUM(NEWID()))% 1000000000 ) / 1000.00
FROM numbers n1,
Products
/*Set up table for search data*/
DECLARE @SearchValues TABLE
(
Sequence int primary key,
Value decimal(10,3)
)
INSERT INTO @SearchValues
VALUES (1,323.113),(2,5423.231),(3,873.420),(4,422.640),(5,763.100)
/*Fiddle the test data so we have some guaranteed matches*/
UPDATE ps
SET ps.Value = sv.Value
FROM ProductSegments ps
JOIN @SearchValues sv ON ProductId = 1 AND Sort = 100 + Sequence
UPDATE ps
SET ps.Value = sv.Value
FROM ProductSegments ps
JOIN @SearchValues sv ON ProductId = 3 AND Sort = 987 + Sequence
/*Create the denormalised data*/
INSERT INTO ProductSegmentsDenormalized
SELECT ProductId, '|' + DelimitedList
FROM Products p
CROSS APPLY ( SELECT CAST(Value as varchar) + '|'
FROM ProductSegments ps
WHERE ps.ProductId = p.ProductId
ORDER BY Sort
FOR XML PATH('') ) D ( DelimitedList )
/*Do the search*/
SELECT ProductId
FROM ProductSegmentsDenormalized psd
WHERE psd.ProductId IN (SELECT p.ProductId
FROM Products p
WHERE NOT EXISTS (SELECT *
FROM @SearchValues sv
WHERE NOT EXISTS
(SELECT *
FROM ProductSegments ps
WHERE ps.ProductId = p.ProductId
AND sv.Value = ps.Value)))
AND DelimitedList LIKE '%|' + (SELECT CAST(Value AS VARCHAR) + '|'
FROM @SearchValues sv
ORDER BY Sequence
FOR XML PATH('')) + '%'
Возможно, то, что я пытаюсь предложить, занимает слишком много места: как только вы добавляете новый продукт, поскольку сегменты статичны, вы можете проиндексировать их, взяв все "суффиксы" из списка сегментов.
Например, список сегментов:
34 57 67 34
будет производить:
34 57 67 34
57 67 34
67 34
34
Возможно, вам придется хранить их в файлах на жестком диске, потому что для 10000 сегментов для каждого продукта вы получите множество "суффиксов" (фактически до 10000 для каждого продукта). Хорошей новостью является то, что вы можете хранить их непрерывно, чтобы у вас не было слишком много обращений к жесткому диску. Затем вы можете просто линейно сканировать список суффиксов и сопоставлять первые k значений для запроса, который содержит k значений сегмента. Таким образом, если в приведенном выше списке вы ищете 57 67, он вернет этот продукт, потому что он соответствует второму суффиксу.
Вы также можете выполнить индексацию дерева для более быстрого соответствия, но это может оказаться слишком сложным.
Изменить: Как я уже говорил в комментарии, это адаптация соответствия подстроки. Вы также должны отсортировать суффиксы по номеру, а затем выполнить бинарный поиск по списку суффиксов, что в теории должно указывать совпадение / несоответствие в шагах журнала (10000).