多個關鍵字反向索引搜索

Question

我要尋找一個建築解決以下問題：

的問題

一般說明我有很多不同的數據實體（約1500萬元）的。每個實體都與某些關鍵字（或標籤）相關聯（在最壞的情況下，從幾個關鍵字到每個實體的hunderds）。

鑑於N不同的關鍵詞，我的任務就是中檢索以下順序如下結果：

• 它們與所有N給出的關鍵字相關聯的所有實體;
• 實體，其中包含給定關鍵字N-1的任意組合的實體;
• 實體，其中包含給定關鍵字的N-2的任意組合;
• 等等（可能正好限制到某個N-K-限制，但在一般情況下，可降至1個關鍵字匹配）。

樸素方法

我來的幼稚的解決方案是爲使用MySQL/PostgreSQL的RDBMS每個關鍵字創建簡單的反向索引。一般來說，將包含兩個表：

Table Keywords    Table Entities 
---------------------  --------------------- 
    id  keyword   id  keyword_id 
---------------------  --------------------- 
    1   tag1    1    1 
    2   tag2    1    2    
    3   tag3    2    3 

• 表Keywords存儲關鍵詞;
• 表Entities存儲實體間的關係id-s和keyword_id-s。

對於每個keyword1 & keyword2 & ... & keywordN查詢我準備中檢索所有實體的id集的每個查詢的關鍵字，然後執行手動搜索N -keywords，N-1 -keywords等符合項目上的應用水平。

問題

顯然，這種做法會遇到兩個問題：

1. 從數十億項Entities表（即使指數的使用）接收數據集的時間長;
2. 長時間執行應用程序級別搜索N -keywords在應用程序級匹配。

對於這兩個問題，認爲一個標籤可與幾百萬在一般情況下，項目的關聯。

如何有效處理這些問題？

Answer 1

您提出的模式沒有多大意義。您在調用實體的東西之間存在N：M關係（相當困惑，因爲這通常用於關係數據庫中的單個表示的任何數據結構）。我認爲事端已經在重新講述迷路了，你居然說你有三個表：

keywords {id, keyword} 
entities {id, ....} 
entity_words {keyword_id, entity_id} 

這個架構顯著改善的唯一途徑是進行非規範化的比賽算入「實體」記載：

UPDATE entities e 
SET e.matches = (SELECT COUNT(DISTINCT ew.keyword_id) 
    FROM entity_words ew 
    WHERE ew.entity_id=e.id); 

....而你也可以在關鍵字表添加觸發器時在關鍵字的數據改變爲更新相關的實體唱片，這似乎矯枉過正時，你必須有一個機制creaing映射首先。

Answer 2

我會使用the intarray extension併爲此梗概指數。

Store的實體標籤陣列，例如：

SELECT 
    *, 
    ARRAY[1,3] & tags AS matched_tags 
FROM entity 
WHERE ARRAY[1,3] && tags 
ORDER BY array_length(ARRAY[1,3] & tags,1) DESC; 

該指數將用於排除不具有任何匹配的標籤行：

CREATE EXTENSION intarray; 

CREATE TABLE entity(
    entity_id BIGSERIAL PRIMARY KEY, 
    tags integer[] not null 
); 

INSERT INTO entity(tags) values (ARRAY[1,2,3]); 
INSERT INTO entity(tags) values (ARRAY[1,3,5]); 
INSERT INTO entity(tags) values (ARRAY[1]); 
INSERT INTO entity(tags) values (ARRAY[]::integer[]); 

CREATE INDEX entity_tags_idx ON entity USING GIST(tags); 

和查詢的東西隱約像。然後結果集將按照降序排列匹配標籤的數量。在具有相同數量的匹配標籤的組內不會強加任何訂單，但您可以爲其添加第二個排序鍵。

這應該只要每個實體沒有一個真正巨大的標籤列表工作。如果你不需要，不要計算「matched_tags」。如果您確實需要它，請考慮將其計算包裝到子查詢中，然後使用ORDER BY中的計算值而不是在那裏重新計算。

您可能需要有足夠的內存的機器，以適應要點指數在裏面。如果UPDATE/INSERT率很低，則可以使用GIN索引代替; GIN的性能對於變化非常小的數據更好，對於變化很大的數據非常不利。

Answer 3

，你就能把所有合併到1臺，如果我理解正確的模式。 我爲冗長的模式創建事先道歉，但我想向自己證明它實際上會使用索引。這個例子使用了postgres，如果你安裝了intarray擴展，你可以在關係上創建gist或者gin索引。我對Postgres的測試9.3

create table keyword (id serial primary key, tag varchar, relation integer[]); 

insert into keyword(id, tag,relation) values(1,'tag1',array[1]); 
insert into keyword(id, tag,relation) values(2,'tag2',array[1,2]); 
insert into keyword(id, tag,relation) values(3,'tag3',array[1,2,3]); 
insert into keyword(id, tag,relation) values(4,'tag4',array[1,2,3,4]); 
insert into keyword(id, tag,relation) values(5,'tag5',array[1,2,3,4,5]); 
insert into keyword(id, tag,relation) values(6,'tag6',array[1,2,3,4,5,6]); 
insert into keyword(id, tag,relation) values(7,'tag7',array[1,2,3,4,5,6,7]); 
insert into keyword(id, tag,relation) values(8,'tag8',array[1,2,3,4,5,6,7,8]); 
insert into keyword(id, tag,relation) values(9,'tag9',array[1,2,3,4,5,6,7,8,9]); 
insert into keyword(id, tag,relation) values(10,'tag10',array[1,2,3,4,5,6,7,8,9,10]); 
insert into keyword(id, tag,relation) values(11,'tag11',array[11]); 
insert into keyword(id, tag,relation) values(12,'tag12',array[12]); 
insert into keyword(id, tag,relation) values(13,'tag13',array[13]); 
insert into keyword(id, tag,relation) values(14,'tag14',array[14]); 
insert into keyword(id, tag,relation) values(15,'tag15',array[15]); 
insert into keyword(id, tag,relation) values(16,'tag16',array[16,13,12]); 
insert into keyword(id, tag,relation) values(17,'tag17',array[17,10,9,5,2,1]); 
insert into keyword(id, tag,relation) values(18,'tag18',array[18,1,2,3]); 
insert into keyword(id, tag,relation) values(19,'tag19',array[19,1]); 
insert into keyword(id, tag,relation) values(20,'tag20',array[20,19,18,17,16,15,14,13,12,11,10,9,8,7,6,5,4,3,2,1]); 
insert into keyword(id, tag,relation) values(21,'tag21',array[21]); 
insert into keyword(id, tag,relation) values(22,'tag22',array[22]); 
insert into keyword(id, tag,relation) values(23,'tag23',array[23]); 
insert into keyword(id, tag,relation) values(24,'tag24',array[24]); 
insert into keyword(id, tag,relation) values(25,'tag25',array[25]); 
insert into keyword(id, tag,relation) values(26,'tag26',array[26]); 
insert into keyword(id, tag,relation) values(27,'tag27',array[27]); 
insert into keyword(id, tag,relation) values(28,'tag28',array[28]); 
insert into keyword(id, tag,relation) values(29,'tag29',array[29]); 
insert into keyword(id, tag,relation) values(30,'tag30',array[30]); 
insert into keyword(id, tag,relation) values(31,'tag31',array[30]); 
insert into keyword(id, tag,relation) values(32,'tag32',array[30]); 
insert into keyword(id, tag,relation) values(33,'tag33',array[30]); 
insert into keyword(id, tag,relation) values(34,'tag34',array[30]); 
insert into keyword(id, tag,relation) values(35,'tag35',array[30]); 
insert into keyword(id, tag,relation) values(36,'tag36',array[30]); 
insert into keyword(id, tag,relation) values(37,'tag37',array[30]); 
insert into keyword(id, tag,relation) values(38,'tag38',array[30]); 
insert into keyword(id, tag,relation) values(39,'tag39',array[30]); 
insert into keyword(id, tag,relation) values(40,'tag40',array[30]); 
insert into keyword(id, tag,relation) values(41,'tag41',array[30]); 
insert into keyword(id, tag,relation) values(42,'tag42',array[30]); 
insert into keyword(id, tag,relation) values(43,'tag43',array[30]); 
insert into keyword(id, tag,relation) values(44,'tag44',array[30]); 
insert into keyword(id, tag,relation) values(45,'tag45',array[30]); 
insert into keyword(id, tag,relation) values(46,'tag46',array[30]); 
insert into keyword(id, tag,relation) values(47,'tag47',array[30]); 
insert into keyword(id, tag,relation) values(48,'tag48',array[30]); 
insert into keyword(id, tag,relation) values(49,'tag49',array[30]); 
insert into keyword(id, tag,relation) values(50,'tag50',array[30]); 
insert into keyword (id, tag) (select generate_series, 'tag'||generate_series from generate_series(51,500)); 

create index on keyword(array_length(relation,1)); 
/*Uncomment the line below if you have intarray installed */ 
/*create index on keyword using gist(relation);*/ 
analyze keyword; 

因此，發現與其他標籤5間的關係的所有元素，只需運行以下命令：

select * from keyword where array_length(relation,1)=5 

要查找與標籤17相關的所有元素，運行以下內容：

select * from keyword where relation @> array[17] 

的關係陣列列可能持有這會搞砸重複的值，所以你可以寫一個函數和一個檢查約束，以防止這個，或者將這些代碼寫入應用程序 - 檢查約束可能會大大增加插入的成本。

隨意玩弄此架構上SQLFiddle，我已經在這裏創造的模式：SqlFiddle