Details

    • Type: Sub-task Sub-task
    • Status: Closed
    • Priority: Major Major
    • Resolution: Fixed
    • Affects Version/s: None
    • Fix Version/s: 1.1.1, 1.2
    • Component/s: None
    • Labels:
      None

      Description

      The time required to query _all_docs?limit=1 can be proportional to the doc_del_count of the database depending on where the deleted docs are in the sort order. As kocolosk explained on IRC:

      The tree that serves as the source for _all_docs contains a small record for each document, deleted or not ... if you have a large number of deleted docs and their IDs are interspersed with the non-deleted ones i can imagine that it would cause additional seeks when streaming the _all_docs response

      In my use case (https://github.com/natevw/RQMS) and in other cases (e.g. a rolling log or any long-lived database), the deleted docs may all be at the beginning of the _all_docs view, making query performance end up like using "?limit=N&skip=doc_del_count".

      To improve the performance in cases where large blocks of documents have been deleted, kocolosk notes:

      [10:30am] kocolosk: the inner nodes in the btree currently report the doc_count and doc_del_count
      [10:31am] kocolosk: we might be able to rewrite the function that walks the btree so that it checks if the doc_count underneath an inner node is zero
      [10:31am] kocolosk: and then it can skip that part of the tree entirely
      [10:31am] kocolosk: instead of descending all the way to the leaf nodes and skipping deleted documents one by one
      [10:31am] n[ate]vw: yeah, that'd have the benefit of being a code-only change
      [10:31am] kocolosk: right
      [10:32am] kocolosk: i think it should work rather nicely, though it probably requires some interesting spelunking into the depths of couch_btree
      [10:33am] kocolosk: davisp: whaddya think? would what i'm proposing be possible? (checking for doc_count=0 in the inner node reduction and then skipping ahead when serving _all_docs)
      ...
      [10:39am] davisp: n[ate]vw: Its definitely doable, its just a question of how to do it so that I don't bleed from the eyes when trying to read through the implementation
      ...
      [10:40am] rnewson: davisp: right. we definitely want to preserve the high readability of the current btree code. /s
      [10:40am] davisp: kocolosk: The only thing I can think of is passing a function to the view iteration that gets called to evaluate whether it should decend to a child node based on the key/reduction pair
      [10:41am] kocolosk: davisp: what you're proposing would also allow for (more) efficient implementation of skip

        Issue Links

          Activity

          Hide
          ASF subversion and git services added a comment -

          Commit 8d37ee36f23e5aea09f1fd17fd783b74a45d2e7e in couchdb's branch refs/heads/2189-ddoc-info-on-demand from Randall Leeds
          [ https://git-wip-us.apache.org/repos/asf?p=couchdb.git;h=8d37ee3 ]

          Update pagination docs - COUCHDB-1076 is old now

          As far as I'm aware, skip is equivalently fast to a startkey search
          because whole subtrees are skipped when their document count does
          not exceed the remaining skip.

          Show
          ASF subversion and git services added a comment - Commit 8d37ee36f23e5aea09f1fd17fd783b74a45d2e7e in couchdb's branch refs/heads/2189-ddoc-info-on-demand from Randall Leeds [ https://git-wip-us.apache.org/repos/asf?p=couchdb.git;h=8d37ee3 ] Update pagination docs - COUCHDB-1076 is old now As far as I'm aware, skip is equivalently fast to a startkey search because whole subtrees are skipped when their document count does not exceed the remaining skip.
          Hide
          ASF subversion and git services added a comment -

          Commit 8d37ee36f23e5aea09f1fd17fd783b74a45d2e7e in couchdb's branch refs/heads/master from Randall Leeds
          [ https://git-wip-us.apache.org/repos/asf?p=couchdb.git;h=8d37ee3 ]

          Update pagination docs - COUCHDB-1076 is old now

          As far as I'm aware, skip is equivalently fast to a startkey search
          because whole subtrees are skipped when their document count does
          not exceed the remaining skip.

          Show
          ASF subversion and git services added a comment - Commit 8d37ee36f23e5aea09f1fd17fd783b74a45d2e7e in couchdb's branch refs/heads/master from Randall Leeds [ https://git-wip-us.apache.org/repos/asf?p=couchdb.git;h=8d37ee3 ] Update pagination docs - COUCHDB-1076 is old now As far as I'm aware, skip is equivalently fast to a startkey search because whole subtrees are skipped when their document count does not exceed the remaining skip.
          Randall Leeds made changes -
          Status Resolved [ 5 ] Closed [ 6 ]
          Randall Leeds made changes -
          Status In Progress [ 3 ] Resolved [ 5 ]
          Resolution Fixed [ 1 ]
          Hide
          Randall Leeds added a comment -

          Fixed on trunk (r1152398) and 1.1.x (r1152406)

          Show
          Randall Leeds added a comment - Fixed on trunk (r1152398) and 1.1.x (r1152406)
          Randall Leeds made changes -
          Status Open [ 1 ] In Progress [ 3 ]
          Randall Leeds made changes -
          Link This issue relates to COUCHDB-977 [ COUCHDB-977 ]
          Randall Leeds made changes -
          Parent COUCHDB-977 [ 12492546 ]
          Issue Type Bug [ 1 ] Sub-task [ 7 ]
          Randall Leeds made changes -
          Field Original Value New Value
          Assignee Randall Leeds [ tilgovi ]
          Fix Version/s 1.1.1 [ 12316395 ]
          Fix Version/s 1.2 [ 12315198 ]
          Hide
          Randall Leeds added a comment -

          Thanks, Filipe and Damien.

          Filipe:
          1) I'd rather keep it in couch_db_updater. The other functions depending on (or generating) the reduction values for the by_id tree are in that module. It makes most sense to me to keep all the code that relies on that format in one place.

          2) Cool. Easy fix. Good catch.

          3) I'll see if I can add some trivial tests.

          Show
          Randall Leeds added a comment - Thanks, Filipe and Damien. Filipe: 1) I'd rather keep it in couch_db_updater. The other functions depending on (or generating) the reduction values for the by_id tree are in that module. It makes most sense to me to keep all the code that relies on that format in one place. 2) Cool. Easy fix. Good catch. 3) I'll see if I can add some trivial tests.
          Hide
          Filipe Manana added a comment -

          Looks good Randall, only 2 minor comments:

          1) Do you have to add the skip function to couch_db_updater and export it if it's only used in couch_httpd_db.erl?

          2) The skip function doesn't account for db reduction values created by 1.1.x and older releases, which are 2 tuple terms

          {NotDeleted, Deleted}

          ; So either another clause should be added or simply do a "Skip >= element(1, Reduction)"

          Do you think there's a sane way do add some etap tests (to 020-btree-basics.t)? At least for the trivial cases it's easy to test (all branches skipped, or none of the branches is skipped)

          Show
          Filipe Manana added a comment - Looks good Randall, only 2 minor comments: 1) Do you have to add the skip function to couch_db_updater and export it if it's only used in couch_httpd_db.erl? 2) The skip function doesn't account for db reduction values created by 1.1.x and older releases, which are 2 tuple terms {NotDeleted, Deleted} ; So either another clause should be added or simply do a "Skip >= element(1, Reduction)" Do you think there's a sane way do add some etap tests (to 020-btree-basics.t)? At least for the trivial cases it's easy to test (all branches skipped, or none of the branches is skipped)
          Hide
          Damien Katz added a comment -

          I haven't looked very closely at this patch line for line, so I can't say if there are bugs, etc. But I definitely agree with this approach and structure. Nice work.

          Show
          Damien Katz added a comment - I haven't looked very closely at this patch line for line, so I can't say if there are bugs, etc. But I definitely agree with this approach and structure. Nice work.
          Hide
          Randall Leeds added a comment -

          Got it. Came out very clean. If there are no complaints I'll commit this in a couple of days.
          I haven't done the work to apply this to ddoc views yet, but it should be pretty easy.

          Differences here: https://github.com/tilgovi/couchdb/compare/trunk...skiptree

          Show
          Randall Leeds added a comment - Got it. Came out very clean. If there are no complaints I'll commit this in a couple of days. I haven't done the work to apply this to ddoc views yet, but it should be pretty easy. Differences here: https://github.com/tilgovi/couchdb/compare/trunk...skiptree
          Hide
          Randall Leeds added a comment -

          I did the digging and I think I've got an elegant fix. A little more work to be done before I post a patch but I wanted to let you all know so we avoid duplicate work. If you've thought about, or are curious about, this or have partial work of your own, ping me on IRC (tilgovi).

          Show
          Randall Leeds added a comment - I did the digging and I think I've got an elegant fix. A little more work to be done before I post a patch but I wanted to let you all know so we avoid duplicate work. If you've thought about, or are curious about, this or have partial work of your own, ping me on IRC (tilgovi).
          Nathan Vander Wilt created issue -

            People

            • Assignee:
              Randall Leeds
              Reporter:
              Nathan Vander Wilt
            • Votes:
              0 Vote for this issue
              Watchers:
              1 Start watching this issue

              Dates

              • Created:
                Updated:
                Resolved:

                Development