一道Facebook DS SQL题

Write an SQL query that makes recommendations using the pages that your friends liked. Assume you have two tables: a two-column table of users and their friends, and a two-column table of users and the pages they liked. It should not recommend pages you already like.

不知这个Query Work不？
Select b.users, b.pages from pages_table b
Where b.users in (
Select a.friends from friends_table a
Where a.users = my_id
) and b.pages not in (
select c.pages from pages_table c
where c.users = my_id
)

我觉得题主用的子查询没有问题，self join的效率应该是比这个使用in/not in的要低的。

对于多数商用数据库系统来说，其优化器（query optimizer）一般可以将单层嵌套子查询优化到最佳的query plan -- 除非是那些需要用window query（也就是使用了OVER (PARTITION BY ... ORDER BY ...)）来表达以达到最佳效率的查询。

-- 那么题主的query一般会被怎么执行呢？
-- 这要看表上建了哪些索引。

单服务器规模的数据，可以假定pages_table和friends_table各建有对users的B-tree（或者hash）索引
那么query plan基本上是：
t1 = Index scan on friends_table
t2 = Hash aggregate (distinctify) on t1
t3 = Index nested loops join between t2 and pages_table
t4 = Index scan on pages_table
结果 = Hash anti-join between t3 and t4

时间复杂度是O(# of my friends + # of my friends' liked pages)

不使用子查询而用self join，可能会没有t2的步骤并需要在最后做distinctify（用于去掉重复的tuple），效率反而会低。

----
如果没有索引，那么需要全表scan + Hash semi/anti join，时间复杂度是O(# of rows in friends_table + # of rows in pages_table)，对于这个问题来说是非常低效的 -- 而且没有任何一种query写法可以做到高效。

----
对于分布式数据库+海量数据，一般没有全局的索引，不过就这道题而言可以将两个表根据users进行sharding，然后使用局部索引，本质上和单机执行方案是差不多的。

为啥大家都写得这么复杂？我怎么觉得一个EXCEPT就可以了啊。。。

SELECT T1.UID, T2.LIKED_PID
FROM friends as T1 JOIN likes as T2 ON T1.FID = T2.UID
EXCEPT
SELECT UID, LIKED_PID
FROM likes

难道是我想错了？

I would try to use left outer join.
Suppose you have two tables:
a
user_id     friend_id
b
user_id     pages

SELECT t.user_id, t.pages
FROM
           (SELECT distinct a.user_id, b.pages
            FROM a INNER JOIN b
            ON a.friend_id = b.users ) t
LEFT OUTER JOIN b
ON t.user_id = b.user_id
AND t.pages=b.pages
WHERE b.pages is null

应该是OK的吧。不过实际应用一般应该不推荐使用子查询吧，也可以自join USER_TABLE筛选

我是个新手，我的想法可能比较机械，想讨论一下：
user： user1，user2
like：user，page

1.left join两个table where u.user2=l.user，得到user1，user2，page   (page 可能是none)
2. group by user1，page （page肯定是好友点赞的），count（*）得到user1的好友对各个page点赞的count， order by count（*）desc，得到user1，page，like_count
3. 之后也可以操作得到每个user最推荐的page，利用最大like_count的row
————————————————————————————————————

呀，没考虑到不能是自己点赞过的。那么就是要再筛选一下page了～新手写得好烂，啊哈哈。。。

这个是work的，但是有个问题是这样用b.users in () and b.pages not in()可能会非常非常慢一旦数据量非常大的时候。

iamchrisa 发表于 2017-6-19 01:57
这个是work的，但是有个问题是这样用b.users in () and b.pages not in()可能会非常非常慢一旦数据量非常大 ...

同意。谢谢。

1 select page in (subquery) where page not in (second subquery) . this is the naive solution
2 if need frequency, just count(distinct page) order by 1 desc
3 The follow up must be "do not use subquery", (you can refer to glassdoor, this will be the follow up and we should not use subquery in production as it perform bad.)
4 So how to solve if no subquery? Always, and only, self join existing table.
(I am not sure whether below works or not? Hey, anyone solve this problem without subquery?)
select p1.page
from user table u1
join page table p1 on u1.friends = p1.uid
left join user table u2 on u1.uid = u2.uid
left join page table p2 on u2.friends = p2.uid
where u1.uid = @myuid and p2.uid != @myuid and p1.page != p2.page
5 Another way to avoid subquery is to use temp table, its performance is better than subquery.

I find a similar question:
https://stackoverflow.com/questions/7819654/sql-to-get-all-the-friends-of-friends-whos-not-my-friend

alpha8421 发表于 2017-6-13 15:27
应该是OK的吧。不过实际应用一般应该不推荐使用子查询吧，也可以自join USER_TABLE筛选

could you provide the sql for 自join USER_TABLE筛选 solution? thanks.

I would try to use left outer join.
Suppose you have two tables:
a
user_id     friend_id
b
user_id     pages

SELECT t.user_id, t.pages
FROM
           (SELECT distinct a.user_id, b.pages
            FROM a INNER JOIN b
            ON a.friend_id = b.users ) t
LEFT OUTER JOIN b
ON t.user_id = b.user_id
WHERE b.pages is null

Does this work?

Select f.user_id, p.pg
        from friends f
        inner join pages p on f.friend_id = p.user_id
        inner join pages p2 on f.user_id = p2.user_id
        where p.page <> p2.page