postgresql中拼字遊戲的最佳查詢

Question

我有一個500萬行的表。 想要編寫能夠幫助拼字遊戲玩家的查詢。 有8個字母，其中2個可以是通配符。

可能的組合數是itertools.permutations(letters)，在最壞的情況下是8!。 假設詞是ex*ampl* 然後我寫的查詢SELECT * from words where word like 'exampl_' or name like 'ex_ample'...

但也有8! or子句和查詢速度太慢。 有更快的方法嗎？

Answer 1

您正在查詢單詞但不在手中的字符數小於可用通配符數 的字數。

要找到一個候選詞集多餘的字符：

-- characters in the word 
SELECT unnest(regexp_split_to_array(word, '')) 
-- except those in the hand 
EXCEPT ALL 
SELECT unnest('{E, X, A, M, P, L}' :: CHAR []) 

您可以用它來選擇的話，其中的一套多餘的字符少於可用通配符的數量。在 你的榜樣手包含字符{E, X, A, M, P, L}和兩個通配符，所以查詢將是：

SELECT word 
FROM words 
WHERE 
    (
    SELECT count(*) 
    FROM 
     (
     SELECT unnest(regexp_split_to_array(word, '')) 
     EXCEPT ALL 
     SELECT unnest('{E, X, A, M, P, L}' :: CHAR []) 
    ) extra 
) <= 2 
; 

這需要一個表掃描，所以它不會那麼快。加速它的一種方法是去標準化一點;將 字作爲字符數組存儲，您將能夠利用GIN索引並使用postgres數組運算符 來縮小要搜索的單詞集。

隨着索引chars柱：

-- Add a chars column to the words table 
ALTER TABLE words ADD COLUMN chars CHAR []; 

-- Populate it 
UPDATE words SET chars = regexp_split_to_array(word, ''); 
ALTER TABLE words ALTER COLUMN chars SET NOT NULL; 

-- A GIN index on the chars column 
CREATE INDEX ix_word_chars ON words USING GIN (chars); 

-- An index on word length 
CREATE INDEX ix_word_length ON words (char_length(word)); 

可以使用Postgres的@>陣列操作迅速找到一個詞的字謎：

SELECT word 
FROM words 
WHERE 
    chars @> '{E, X, A, M, P, L, E}' :: CHAR [] 
    AND 
    char_length(word) = 7 
    AND 
    (
    SELECT count(*) 
    FROM 
     (
     SELECT unnest(chars) 
     EXCEPT ALL 
     SELECT unnest('{E, X, A, M, P, L, E}' :: CHAR []) 
    ) extra 
) = 0 
; 

注：即使雖然沒有在上面的例子中，我們仍然需要過濾掉帶有額外 個字符的單詞。 @>運算符只檢查左邊的數組是否包含右側的數組 上的所有元素;它不檢查基數，所以重複字母的單詞將匹配。

將其擴展到查找具有不同輸入字符組合的單詞需要更多工作。他指出，一個字長七 必須從手（加上兩個通配符）的五個字符一些組合搭配，我們可以過濾 對這些組合的候選集（由Python的itertools.combinations('EXAMPL', 5)有益提供）：

WITH combinations (combination) AS (
    VALUES 
    ('{E, X, A, M, P}' :: CHAR []), 
    ('{E, X, A, M, L}' :: CHAR []), 
    ('{E, X, A, P, L}' :: CHAR []), 
    ('{E, X, M, P, L}' :: CHAR []), 
    ('{E, A, M, P, L}' :: CHAR []), 
    ('{X, A, M, P, L}' :: CHAR []) 
) 
SELECT DISTINCT word 
FROM words w 
    JOIN combinations c ON w.chars @> c.combination 
WHERE 
    char_length(word) = 7 
    AND 
    (
    SELECT count(*) 
    FROM 
     (
     SELECT unnest(chars) 
     EXCEPT ALL 
     SELECT unnest('{E, X, A, M, P, L}' :: CHAR []) 
    ) extra 
) <= 2; 

可根據需要擴展以容納更短的單詞或更少的通配符。