Эффективный способ поиска последовательных значений - PullRequest
Новая
       9

Эффективный способ поиска последовательных значений

2 голосов
/ 04 ноября 2011

Каждый «Продукт» может иметь до 10000 строк «Сегмент».Сегменты имеют столбец сортировки, который начинается с 1 для каждого продукта (1, 2, 3, 4, 5, ...) и столбец значений, который может содержать любые значения, такие как (323.113, 5423.231, 873.42, 422.64, 763.1,...).

Я хотел бы определить потенциальные совпадения для продуктов с заданным подмножеством сегментов.Например, если у меня есть 5 значений сегмента в правильном порядке, как я могу эффективно найти все продукты, которые имеют все 5 сегментов в одном и том же порядке где-то в таблице сегментов?

Обновить

Я разместил следующий вопрос по этому вопросу здесь: Найдите ряд данных, используя неточные измерения (нечеткая логика)

Ответы [ 3 ]

4 голосов
/ 04 ноября 2011

Допустим, таблицы так: 

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

1 голос
/ 04 ноября 2011

Вероятно, наилучший способ сделать это - сохранить денормализованную версию данных. 

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('')) + '%'
1 голос
/ 04 ноября 2011

Возможно, то, что я пытаюсь предложить, занимает слишком много места: как только вы добавляете новый продукт, поскольку сегменты статичны, вы можете проиндексировать их, взяв все «суффиксы» списка сегментов.

Например, список сегментов: 

34 57 67 34

выдаст: 

34 57 67 34
57 67 34
67 34
34

Вам может потребоваться сохранить их в файлах на жестком диске, поскольку для 10000 сегментов дляза каждый продукт вы получите множество «суффиксов» (до 10000 на каждый продукт).Хорошей новостью является то, что вы можете хранить их непрерывно, чтобы у вас не было слишком много обращений к жесткому диску.Затем вы можете просто линейно сканировать список суффиксов и сопоставлять первые k значений для запроса, который содержит k значений сегмента.Таким образом, если в приведенном выше списке вы ищете 57 67, он вернет этот продукт, поскольку он соответствует второму суффиксу.

Вы также можете выполнить индексацию дерева для более быстрого сопоставления, но это может оказаться слишком сложным.

Редактировать: Как я уже говорил в комментарии, это адаптация соответствия подстроки.Вы также должны отсортировать суффиксы по номеру, а затем выполнить бинарный поиск по списку суффиксов, что в теории должно указывать совпадение / несоответствие в шагах журнала (10000).

...