SQL Precedence Matching - PullRequest
       13

SQL Precedence Matching

1 голос
/ 22 декабря 2008

Я пытаюсь выполнить сопоставление приоритета для таблицы в хранимой процедуре. Требования немного сложно объяснить, но, надеюсь, это будет иметь смысл. Допустим, у нас есть таблица с названием books, с полями id, author, title, date и pages.

У нас также есть хранимая процедура, которая сопоставит запрос с ОДНОЙ строкой в ​​таблице.

Вот подпись протокола:

create procedure match
  @pAuthor varchar(100)
  ,@pTitle varchar(100)
  ,@pDate varchar(100)
  ,@pPages varchar(100)

 as

 ...

Правила приоритета следующие:

  • Сначала попробуйте сопоставить все 4 параметра. Если мы найдем совпадение, вернемся.
  • Далее попробуйте сопоставить, используя любые 3 параметра. 1-й параметр имеет здесь самый высокий приоритет, а 4-й - самый низкий. Если мы найдем совпадения, вернем совпадение.
  • Затем мы проверяем, совпадают ли какие-либо два параметра и, наконец, совпадает ли какой-либо из них (все еще следуя правилам приоритета порядка параметров).

Я реализовал это в каждом конкретном случае. Например:

 select @lvId = id 
 from books
 where
  author = @pAuthor 
 ,title = @pTitle 
 ,date = @pDate 
 ,pages = @pPages

if @@rowCount = 1 begin
  select @lvId
  return
end

 select @lvId = id 
  from books
 where
  author = @pAuthor 
 ,title = @pTitle 
 ,date = @pDate 

 if @@rowCount = 1 begin
  select @lvId
  return
end

....

Однако для каждого нового столбца в таблице количество отдельных проверок увеличивается на порядок 2. Я действительно хотел бы обобщить это на X количество столбцов; однако у меня возникли проблемы при разработке схемы.

Спасибо за прочтение, и я могу предоставить любую необходимую дополнительную информацию.


Добавлено:

Дейв и другие, я пытался реализовать ваш код, и он задыхается от первого заказа по предложению, где мы добавляем все значения. Это дает мне неверную ошибку имени столбца. Когда я закомментирую общее количество и порядок по отдельным псевдонимам, proc скомпилируется нормально.

У кого-нибудь есть идеи?

Это в Microsoft Sql Server 2005

Ответы [ 7 ]

2 голосов
/ 24 декабря 2008

Я считаю, что ответы, над которыми вы работаете, самые простые на сегодняшний день. Но я также считаю, что на SQL-сервере они всегда будут выполнять полное сканирование таблицы. (В Oracle вы можете использовать битовые индексы, если таблица не подвергается множеству одновременных DML)

Более сложным, но гораздо более эффективным решением было бы создание собственного индекса. Не индекс SQL Server, а ваш собственный.

Создать таблицу (Hash-index) с 3 столбцами (lookup-hash, rank, Rowid)

Скажем, у вас есть 3 столбца для поиска. А, В, С

Для каждой строки, добавленной в Книги, вы вставляете 7 строк в hash_index с помощью триггера или процедуры CRUD.

Сначала вы будете

insert into hash_index 
SELECT HASH(A & B & C), 7 , ROWID
FROM Books

Где & - оператор конкатенации, а HASH - функция

тогда вы вставите хэши для A & B, A & C и B & C. Теперь у вас есть некоторая гибкость, вы можете присвоить им одинаковый ранг или, если A & B превосходят B & C, вы можете присвоить им более высокий ранг.

А затем вставьте хэши для A и B и C с одинаковым выбором ранга ... все одинаковые числа или все разные ... вы даже можете сказать, что совпадение на A является лучшим выбором, чем совпадение на B & C. Это решение дает вам большую гибкость.

Конечно, это добавит много накладных расходов на INSERT, но если DML on Books низок или производительность не важна, у вас все в порядке.

Теперь, когда вы перейдете к поиску, вы создадите функцию, которая возвращает таблицу HASH для ваших @A, @B и @C. у вас будет небольшая таблица из 7 значений, которую вы присоедините к lookup-hash в таблице хэш-индекса. Это даст вам все возможные совпадения и, возможно, некоторые ложные совпадения (это просто природа хэшей). Вы возьмете этот результат, закажите порядок в столбце рейтинга. Затем верните первый идентификатор строки в таблицу book и убедитесь, что все значения @A @B @C действительно находятся в этой строке. На случай, если это не так, и вы получите ложный положительный результат, вам нужно проверить следующий rowid.

Каждая из этих операций в этом «брось себе» выполняется очень быстро.

  • Хеширование 3-х значений в небольшую 7-строчную табличную переменную = очень быстро.
  • объединение их по индексу в вашей таблице Hash_index = очень быстрый поиск по индексу
  • Цикл с набором результатов приведет к доступу к 1 или 2 или 3 таблицам по rowid = очень быстро

Конечно, все это вместе может быть медленнее, чем FTS ... Но FTS будет продолжать работать медленнее и медленнее. Будет размер, который FTS медленнее, чем этот. Вам придется играть с этим.

1 голос
/ 22 декабря 2008

У меня нет времени выписать запрос, но я думаю, что эта идея сработает.

В качестве предиката используйте «author = @pAuthor OR title = @ptitle ...», чтобы получить все строки-кандидаты.

Используйте выражения CASE или все, что вам нравится, для создания виртуальных столбцов в наборе результатов, например:

SELECT CASE WHEN author = @pAuthor THEN 1 ELSE 0 END author_match,
       ...

Затем добавьте этот порядок и верните первую строку:

ORDER BY (author_match+title_match+date_match+page_match) DESC,
         author_match DESC,
         title_match DESC,
         date_match DESC
         page_match DESC

Вам все еще нужно расширить его для каждого нового столбца, но только немного.

1 голос
/ 22 декабря 2008

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

В вашей СУБД может быть другой способ обработки "TOP", поэтому вам, возможно, придется также подстроиться под него.

SELECT TOP 1
     author,
     title,
     date,
     pages
FROM
     Books
WHERE
     author = @author OR
     title = @title OR
     date = @date OR
     pages = @pages OR
ORDER BY
     CASE WHEN author = @author THEN 1 ELSE 0 END +
     CASE WHEN title = @title THEN 1 ELSE 0 END +
     CASE WHEN date = @date THEN 1 ELSE 0 END +
     CASE WHEN pages = @pages THEN 1 ELSE 0 END DESC,

     CASE WHEN author = @author THEN 8 ELSE 0 END +
     CASE WHEN title = @title THEN 4 ELSE 0 END +
     CASE WHEN date = @date THEN 2 ELSE 0 END +
     CASE WHEN pages = @pages THEN 1 ELSE 0 END DESC
0 голосов
/ 23 декабря 2008

В связи с невозможностью компиляции в предложении Order By:

Как рекурсивно сказано (в комментарии), псевдоним 'не может быть в выражениях, которые используются в предложениях Order By. чтобы обойти это, я использовал подзапрос, который возвращал строки, затем упорядочивал их во внешнем запросе. Таким образом, я могу использовать псевдоним 'в порядке по предложению. Немного медленнее, но намного чище.

0 голосов
/ 23 декабря 2008

Попробуйте это:

ALTER PROCEDURE match  
  @pAuthor varchar(100)  
 ,@pTitle varchar(100)  
 ,@pDate varchar(100)  
 ,@pPages varchar(100)  
-- exec match 'a title', 'b author', '1/1/2007', 15  
AS

SELECT  id,

        CASE WHEN author = @pAuthor THEN 1 ELSE 0 END
        + CASE WHEN title = @pTitle THEN 1 ELSE 0 END
        + CASE WHEN bookdate = @pDate THEN 1 ELSE 0 END
        + CASE WHEN pages = @pPages THEN 1 ELSE 0 END AS matches,

        CASE WHEN author = @pAuthor THEN 4 ELSE 0 END
        + CASE WHEN title = @pTitle THEN 3 ELSE 0 END
        + CASE WHEN bookdate = @pDate THEN 2 ELSE 0 END
        + CASE WHEN pages = @pPages THEN 1 ELSE 0 END AS score
FROM books
WHERE author = #pAuthor 
    OR title = @pTitle 
    OR bookdate = @PDate 
    OR pages = @pPages
ORDER BY matches DESC, score DESC

Однако это, конечно, вызывает сканирование таблицы. Вы можете избежать этого, сделав это объединением предложений CTE и 4 WHERE, по одному для каждого свойства - будут дубликаты, но вы все равно можете просто взять TOP 1.

EDIT: добавлено предложение WHERE ... OR. Я бы чувствовал себя более комфортно, если бы это было

SELECT ... FROM books WHERE author = @pAuthor
UNION
SELECT ... FROM books WHERE title = @pTitle
UNION
...
0 голосов
/ 23 декабря 2008

Хорошо, позвольте мне повторить мое понимание вашего вопроса: вам нужна хранимая процедура, которая может принимать переменное число параметров и возвращать верхнюю строку, которая соответствует параметрам в весовом порядке предпочтения, передаваемому в SQL Server 2005.

В идеале он будет использовать предложения WHERE для предотвращения полных сканирований таблиц, а также использовать преимущества индексов и будет «замыкать» поиск - вы не хотите искать все возможные комбинации, если они могут быть найдены раньше. Возможно, мы также можем использовать другие компараторы, кроме =, например> = для дат, LIKE для строк и т. Д.

Один из возможных способов - передать параметры в виде XML, как в этой статье , и использовать хранимые процедуры .Net, но давайте пока оставим это простым T-SQL.

Это выглядит для меня как бинарный поиск по параметрам: поиск по всем параметрам, затем удаление последнего, затем второй, но последний, и т. Д.

Давайте передадим параметры в виде строки с разделителями, поскольку хранимые процедуры не позволяют передавать массивы в качестве параметров. Это позволит нам получить переменное число параметров в нашей хранимой процедуре, не требуя хранимой процедуры для каждого варианта параметров.

Чтобы разрешить какое-либо сравнение, мы пропустим весь список предложений WHERE, например, так: title вроде '%thing%'

Передача нескольких параметров означает их разделение в строке. Мы будем использовать символ тильды ~ для разграничения параметров, например: author = 'Chris Latta' ~ title наподобие '%thing%' ~ pages> = 100

Тогда это просто вопрос выполнения бинарного взвешенного поиска для первой строки, которая соответствует нашему упорядоченному списку параметров (надеюсь, хранимая процедура с комментариями не требует пояснений, но если нет, дайте мне знать). Обратите внимание, что вам всегда гарантирован результат (при условии, что в вашей таблице есть хотя бы одна строка), поскольку последний поиск не имеет параметров.

Вот код хранимой процедуры:

CREATE PROCEDURE FirstMatch
@SearchParams VARCHAR(2000)
AS
BEGIN
    DECLARE @SQLstmt NVARCHAR(2000)
    DECLARE @WhereClause NVARCHAR(2000)
    DECLARE @OrderByClause NVARCHAR(500)
    DECLARE @NumParams INT
    DECLARE @Pos INT
    DECLARE @BinarySearch INT
    DECLARE @Rows INT

    -- Create a temporary table to store our parameters
    CREATE TABLE #params 
    (
        BitMask int,             -- Uniquely identifying bit mask
        FieldName VARCHAR(100),  -- The field name for use in the ORDER BY clause
        WhereClause VARCHAR(100) -- The bit to use in the WHERE clause
    )

    -- Temporary table identical to our result set (the books table) so intermediate results arent output
    CREATE TABLE #junk
    (
        id INT,
        author VARCHAR(50),
        title VARCHAR(50),
        printed DATETIME,
        pages INT
    )

    -- Ill use tilde ~ as the delimiter that separates parameters
    SET @SearchParams = LTRIM(RTRIM(@SearchParams))+ '~'
    SET @Pos = CHARINDEX('~', @SearchParams, 1)
    SET @NumParams = 0

    -- Populate the #params table with the delimited parameters passed
    IF REPLACE(@SearchParams, '~', '') <> ''
    BEGIN
        WHILE @Pos > 0
        BEGIN
            SET @NumParams = @NumParams + 1
            SET @WhereClause = LTRIM(RTRIM(LEFT(@SearchParams, @Pos - 1)))
            IF @WhereClause <> ''
            BEGIN
                -- This assumes your field names dont have spaces and that you leave a space between the field name and the comparator
                INSERT INTO #params (BitMask, FieldName, WhereClause) VALUES (POWER(2, @NumParams - 1), LTRIM(RTRIM(LEFT(@WhereClause, CHARINDEX(' ', @WhereClause, 1) - 1))), @WhereClause) 
            END
            SET @SearchParams = RIGHT(@SearchParams, LEN(@SearchParams) - @Pos)
            SET @Pos = CHARINDEX('~', @SearchParams, 1)
        END
    END 

    -- Set the binary search to search from all parameters down to one in order of preference
    SET @BinarySearch = POWER(2, @NumParams) 
    SET @Rows = 0
    WHILE (@BinarySearch > 0) AND (@Rows = 0)
    BEGIN
        SET @BinarySearch = @BinarySearch - 1
        SET @WhereClause = ' WHERE '
        SET @OrderByClause = ' ORDER BY '
        SELECT @OrderByClause = @OrderByClause + FieldName + ', ' FROM #params WHERE (@BinarySearch & BitMask) = BitMask ORDER BY BitMask
        SET @OrderByClause = LEFT(@OrderByClause, LEN(@OrderByClause) - 1) -- Remove the trailing comma
        SELECT @WhereClause = @WhereClause + WhereClause + ' AND ' FROM #params WHERE (@BinarySearch & BitMask) = BitMask ORDER BY BitMask
        SET @WhereClause = LEFT(@WhereClause, LEN(@WhereClause) - 4) -- Remove the trailing AND

        IF @BinarySearch = 0
        BEGIN
            -- If nothing found so far, return the top row in the order of the parameters fields
            SET @WhereClause = ''
            -- Use the full order sequence of fields to return the results
            SET @OrderByClause = ' ORDER BY '
            SELECT @OrderByClause = @OrderByClause + FieldName + ', ' FROM #params ORDER BY BitMask
            SET @OrderByClause = LEFT(@OrderByClause, LEN(@OrderByClause) - 1) -- Remove the trailing comma
        END

        -- Find out if there are any results for this search
        SET @SQLstmt = 'SELECT TOP 1 id, author, title, printed, pages INTO #junk FROM books' + @WhereClause + @OrderByClause
        Exec (@SQLstmt)

        SET @Rows = @@RowCount
    END

    -- Stop the result set being eaten by the junk table
    SET @SQLstmt = REPLACE(@SQLstmt, 'INTO #junk ', '')

    -- Uncomment the next line to see the SQL you are producing
    --PRINT @SQLstmt

    -- This gives the result set
    Exec (@SQLstmt)
END

Эта хранимая процедура называется так:

FirstMatch 'author = ''Chris Latta''~pages > 100~title like ''%something%'''

Вот и все - полностью расширяемый оптимизированный поиск для лучшего результата в взвешенном порядке предпочтений. Это была интересная проблема, и она показывает, что вы можете сделать с помощью собственного T-SQL.

Пара небольших проблем с этим:

  • для вызывающего абонента необходимо знать, что они должны оставить пробел после имени поля для правильной работы параметра
  • вы не можете иметь имена полей с пробелами в них - это можно исправить с некоторыми усилиями
  • предполагается, что соответствующий порядок сортировки всегда возрастает
  • следующий программист, который должен взглянуть на эту процедуру, подумает, что вы сошли с ума:)
0 голосов
/ 22 декабря 2008
      select id, 
               CASE WHEN @pPages = pages 
                    THEN 1 ELSE 0 
               END
             +  Case WHEN @pAuthor=author 
                    THEN 1 ELSE 0 
                END AS 
             /* +  Do this for each attribute. If each of your 
attributes are just as important as the other 
for example matching author is jsut as a good as matching title then 
leave the values alone, if different matches are more 
important then change the values */ as MatchRank  
        from books 

        where  author = @pAuthor OR
               title = @pTitle OR
               date = @pDate

     ORDER BY  MatchRank DESC

Отредактировано

Когда я запускаю этот запрос (измененный только для одной из моих собственных таблиц), он отлично работает в SQL2005.

Я бы порекомендовал пункт where, но вы можете поэкспериментировать с ним, чтобы увидеть влияние на производительность. Вам нужно будет использовать предложение ИЛИ, иначе вы потеряете потенциальные совпадения

...