List:General Discussion« Previous MessageNext Message »
From:Sander de Bruijne Date:March 29 2011 8:53pm
Subject:Re: A common request
View as plain text  
Hi Gregory,

Are you sure you'd like to do this using MySQL? What would happen if you 
start using sharding?

Maybe you could consider using a stack (stored in a tool like Redis?). 
Whenever some user adds some item, you add primary key of the new item 
to the "network updates" stack of each friend of the user (and remove 
the last one). This way, your reads will be fast and you don't need 
complex joins over multiple shards. Just one of my first ideas which 
came up.

Any thoughts?

Best regards,
Sander

On 03/29/2011 07:50 PM, Gregory Magarshak wrote:
> Hey there. My company writes a lot of social applications, and there 
> is one operation that is very common, but I don't know if MySQL 
> supports it in a good way. I thought I'd write to this list for two 
> reasons:
>
>     1) Maybe MySQL has a good way to do this, and I just don't know 
> about it
>
>     2) Propose to MySQL developers a simple algorithm which would 
> greatly improve MySQL support for social networking apps.
>
>     Here is the situation. Let's say I have built a social networking 
> application where people create and edit some item (article, photo, 
> music mix, whatever). Now, a typical user logs in, and this user has 
> 3000 friends. How can I quickly find all the articles written by this 
> user's friends, and not just random articles?
>
>     Ideally, I would want to write something like this:
>
>     SELECT * FROM article WHERE user_id IN (345789, 324875, 398, ..., 
> 349580)
>
>     basically, execute a query with a huge IN ( ... ). Maybe if this 
> would exceed the buffer size for the MySQL wire protocol, I would 
> break up the list into several lists, and execute several queries, and 
> union the results together myself.
>
>     But my point is, this is very common for social networking apps. 
> Every app wants to show "the X created by your friends", or "friends 
> of yours (given some list from a social network) who have taken action 
> X".
>
>     Here is how I would do it if I had raw access to the MySQL index 
> in memory:
>
>     a) Sort the list of entries in the IN, in ascending order.
>
>     b) Do *ONE* binary search through the index (assuming it's a BTREE 
> index) and get them all in one pass. If it's a HASH index or 
> something, I would have to look up each one individually.
>
>     The benefits of this approach would be that this common operation 
> would be done extremely quickly. If the index fits entirely in memory, 
> and I just want to get the primary keys (i.e. get the list of friends 
> who did X), the disk isn't even touched. In addition, for BTREE 
> indexes, I would just need ONE binary search, because the entries have 
> been sorted in ascending order.
>
>     Does MySQL have something like this? And if not, perhaps you can 
> add it in the next version? It would really boost MySQL's support for 
> social networking apps tremendously. Alternative, how can I add this 
> to my MySQL? Any advice would be appreciated.
>
> Sincerely,
> Gregory Magarshak
> Qbix
>
Thread
A common requestGregory Magarshak29 Mar
  • Re: A common requestPeter Brawley29 Mar
    • Re: A common requestGregory Magarshak29 Mar
      • Re: A common requestPeter Brawley29 Mar
        • Re: A common requestGregory Magarshak31 Mar
          • Re: A common requestGregory Magarshak31 Mar
            • Re: A common requestJohan De Meersman31 Mar
          • Re: A common requestmos31 Mar
            • Re: A common requestJohan De Meersman31 Mar
            • Re: A common requestmos31 Mar
              • Re: A common requestWm Mussatto31 Mar
  • Re: A common requestSander de Bruijne29 Mar