• Feeds

  • Archive for January, 2010




    select * from msgs where thread_id = ? limit page * count, count

    不过在看Twitter API的时候,我们却发现不少接口使用cursor的方法,而不用page, count这样直观的形式,如 followers ids 接口



    Returns an array of numeric IDs for every user following the specified user.

    * cursor. Required. Breaks the results into pages. Provide a value of -1 to begin paging. Provide values as returned to in the response body’s next_cursor and previous_cursor attributes to page back and forth in the list.
    o Example: http://twitter.com/followers/ids/barackobama.xml?cursor=-1
    o Example: http://twitter.com/followers/ids/barackobama.xml?cursor=-1300794057949944903


    从上面描述可以看到,http://twitter.com/followers/ids.xml 这个调用需要传cursor参数来进行分页,而不是传统的 url?page=n&count=n的形式。这样做有什么优点呢?是否让每个cursor保持一个当时数据集的镜像?防止由于结果集实时改变而产生查询结果有重复内容?
    在Google Groups这篇Cursor Expiration讨论中Twitter的架构师John Kalucki提到

    A cursor is an opaque deletion-tolerant index into a Btree keyed by source
    userid and modification time. It brings you to a point in time in the
    reverse chron sorted list. So, since you can’t change the past, other than
    erasing it, it’s effectively stable. (Modifications bubble to the top.) But
    you have to deal with additions at the list head and also block shrinkage
    due to deletions, so your blocks begin to overlap quite a bit as the data
    ages. (If you cache cursors and read much later, you’ll see the first few
    rows of cursor[n+1]’s block as duplicates of the last rows of cursor[n]’s
    block. The intersection cardinality is equal to the number of deletions in
    cursor[n]’s block). Still, there may be value in caching these cursors and
    then heuristically rebalancing them when the overlap proportion crosses some

    在另外一篇new cursor-based pagination not multithread-friendly中John又提到

    The page based approach does not scale with large sets. We can no
    longer support this kind of API without throwing a painful number of

    Working with row-counts forces the data store to recount rows in an O
    (n^2) manner. Cursors avoid this issue by allowing practically
    constant time access to the next block. The cost becomes O(n/
    block_size) which, yes, is O(n), but a graceful one given n < 10^7 and
    a block_size of 5000. The cursor approach provides a more complete and
    consistent result set.

    Proportionally, very few users require multiple page fetches with a
    page size of 5,000.

    Also, scraping the social graph repeatedly at high speed is could
    often be considered a low-value, borderline abusive use of the social
    graph API.


    select * from msgs limit 100000, 100

    假定我们使用表的主键的值作为cursor_id, 使用cursor分页方式对应的SQL可以优化为

    select * from msgs where id > cursor_id limit 100;

    同样的表中,通常只需要100ms以下, 效率会提高几十倍。MySQL limit性能差别也可参看我3年前写的一篇不成熟的文章 MySQL LIMIT 的性能问题