使用JOIN而不是HAVING（COUNT> n）來提高性能

我有一張用戶表，以及一張「Facebook朋友」關係表。考慮到（已知）用戶列表，我想快速找到所有在該組中具有2個或更多用戶的Facebook朋友的用戶。使用JOIN而不是HAVING（COUNT> n）來提高性能

（這基本上可以歸結爲一個問題：我能否重寫GROUP BY/HAVING使用的JOIN？）

這裏是我的工作架構的簡化版本。我在這裏使用VARCHAR使我的示例數據（下面）中的用戶名更易於理解; IRL的相關列爲INT：

-- Simplified Schema 
CREATE TABLE _users (
    user_name VARCHAR NOT NULL PRIMARY KEY, 
    fb_id  VARCHAR NULL UNIQUE 
); 
CREATE TABLE _fb_friends (
    id   SERIAL PRIMARY KEY, 
    user_name VARCHAR NULL REFERENCES _users(user_name), 
    friend_fb_id VARCHAR NULL REFERENCES _users(fb_id), 
    UNIQUE (user_name, friend_fb_id) 
);

請注意，friend_fb_id上沒有（可訪問的）索引。

還要注意_fb_friends表是巨大的 - 比_users表大幾個數量級 - 使得明顯的GROUP BY/HAVING解決方案不可能很慢。 I.E.這是不可行的：

-- Using GROUP BY/HAVING: Obvious solution, but way too slow. 
-- Does a SEQ SCAN on the gigantic table 
SELECT me.* 
FROM 
    _users me 
    LEFT OUTER JOIN _fb_friends ff ON (
     ff.user_name = me.user_name 
    ) 
    LEFT OUTER JOIN _users friend ON (
     friend.fb_id = ff.friend_fb_id 
    ) 
GROUP BY me.user_name 
HAVING COUNT(friend.user_name) >= 2;

我改寫了這用連接，但我不知道我想出了一個解決方案是有效的或最佳：

-- Using JOINs: Way faster, but is it correct? Better way? 
SELECT DISTINCT me.* 
FROM (
    _users me 
    LEFT OUTER JOIN _fb_friends ff1 ON (
     ff1.user_name = me.user_name 
    ) 
    LEFT OUTER JOIN _fb_friends ff2 ON (
     ff2.user_name = me.user_name 
     AND ff2.friend_fb_id <> ff1.friend_fb_id 
    ) 
    LEFT OUTER JOIN _users friend ON (
     friend.fb_id = ff1.friend_fb_id 
    ) 
    LEFT OUTER JOIN _users friend_2 ON (
     friend_2.fb_id = ff2.friend_fb_id 
    ) 
) 
WHERE (
    friend.user_name IS NOT NULL 
    AND friend_2.user_name IS NOT NULL 
);

對於它的價值，我寫的一個簡單的測試例子，似乎正常工作。但我真的不確定這是否正確，或者我正在以這種最好的方式進行討論。這兩種策略返回相同的用戶：

BEGIN; 

CREATE TABLE _users (
    user_name VARCHAR NOT NULL PRIMARY KEY, 
    fb_id  VARCHAR NULL UNIQUE 
); 
CREATE TABLE _fb_friends (
    id   SERIAL PRIMARY KEY, 
    user_name VARCHAR NULL REFERENCES _users(user_name), 
    friend_fb_id VARCHAR NULL REFERENCES _users(fb_id) 
); 
INSERT INTO _users (user_name, fb_id) VALUES 
    ('Bob', 'bob'), 
    ('Joe', 'joe'), 
    ('Will', 'will'), 
    ('Marcus', 'marcus'), 
    ('Mitch', 'mitch'), 
    ('Rick', 'rick'); 
INSERT INTO _fb_friends (user_name, friend_fb_id) VALUES 
    ('Bob', 'joe'), 
    ('Will', 'marcus'), 
    ('Joe', 'bob'), 
    ('Joe', 'marcus'), 
    ('Joe', 'mitch'), 
    ('Marcus', 'will'), 
    ('Marcus', 'joe'), 
    ('Mitch', 'joe'); 

SELECT 'GROUP BY/HAVING' AS Strategy, me.* 
FROM 
    _users me 
    LEFT OUTER JOIN _fb_friends ff ON (
     ff.user_name = me.user_name 
    ) 
    LEFT OUTER JOIN _users friend ON (
     friend.fb_id = ff.friend_fb_id 
    ) 
GROUP BY me.user_name 
HAVING COUNT(friend.user_name) >= 2; 

SELECT DISTINCT 'JOIN' AS Strategy, me.* 
FROM (
    _users me 
    LEFT OUTER JOIN _fb_friends ff1 ON (
     ff1.user_name = me.user_name 
    ) 
    LEFT OUTER JOIN _fb_friends ff2 ON (
     ff2.user_name = me.user_name 
     AND ff2.friend_fb_id <> ff1.friend_fb_id 
    ) 
    LEFT OUTER JOIN _users friend ON (
     friend.fb_id = ff1.friend_fb_id 
    ) 
    LEFT OUTER JOIN _users friend_2 ON (
     friend_2.fb_id = ff2.friend_fb_id 
    ) 
) 
WHERE (
    friend.user_name IS NOT NULL 
    AND friend_2.user_name IS NOT NULL 
); 

DROP TABLE _fb_friends; 
DROP TABLE _users; 

COMMIT;

所以基本上，我的問題是：

是我加盟的解決方案是否正確？
有沒有比這更好的/規範的方法？

索引friend_fb_id以及更改模式被視爲禁止訪問。我需要用我目前擁有的最好的東西做到最好。

來源

2014-10-29 danonanimal

我並沒有強加這些限制，這只是我必須處理的情況。所以這裏沒有什麼「魔力」，問題是查詢是否可以以更有效的方式進行修改。我一直無法找到此JOIN策略的任何示例，並希望從其他開發者處獲得反饋。 – danonanimal 2014-10-29 21:16:30

如果沒有索引 - 它將是一個完整的掃描。 Fullscans慢。如果你想提高你的表現 - 第一步是正確的索引。你不能改變模式？直到第一步完成纔有第二步。我堅持：你想要的是「魔術」。你無法從魔術般的地方獲得性能（除非你購買更昂貴的硬件） – zerkms 2014-10-29 22:13:06

爲了記錄，JOIN解決方案不執行SEQ掃描;如果確實如此，那麼它與GROUP BY一樣具有性能，我不會問這個問題。在帶有1億行的產品數據庫中，GROUP BY策略需要1-30分鐘，而JOIN需要約3秒。 – danonanimal 2014-10-29 23:15:59

你可以使用臨時表嗎？如果是的話，試試這個...

drop table if exists friend_count; 

create temporary table friend_count ( 
    user_name varchar not null primary key, 
    friend_count int not null 
); 

create index on friend_count (friend_count); 

insert into friend_count select 
    user_name, 
    count(*) 
from _fb_friends 
/* place more code here necessary to count only the firends within a smaller 
    group of users */ 
group by user_name; 

select 
    me.user_name, 
    me.fb_id 
from _users me 
join friend_count fc on fc.user_name = me.user_name 
where fc.friend_count >= 2;

來源

2014-10-31 18:42:27

我沒有足夠大的數據集來檢查，但看看這個執行得更快。

select me.* 
from _users me 
where 2=(select count(1) from 
      (select 1 from _fb_friends ff 
      join _users friend on friend.fb_id=ff.friend_fb_id 
      where ff.user_name=me.user_name 
      limit 2) x 
     )

來源

2014-12-04 16:30:20

使用JOIN而不是HAVING（COUNT> n）來提高性能

回答

相關問題