View refactoring and addition of raw collationoption. Significant performance improvements in view indexer.

git-svn-id: https://svn.apache.org/repos/asf/couchdb/trunk@814893 13f79535-47bb-0310-9956-ffa450edef68

14 files changed, 258 insertions, 145 deletions

diff --git a/share/www/script/couch_tests.js b/share/www/script/couch_tests.js
index e5426ade..5c1e2bc3 100644
--- a/share/www/script/couch_tests.js
+++ b/share/www/script/couch_tests.js
@@ -74,6 +74,7 @@ loadTest("update_documents.js");
 loadTest("utf8.js");
 loadTest("uuids.js");
 loadTest("view_collation.js");
+loadTest("view_collation_raw.js");
 loadTest("view_conflicts.js");
 loadTest("view_errors.js");
 loadTest("view_include_docs.js");
diff --git a/share/www/script/test/design_docs.js b/share/www/script/test/design_docs.js
index 25c36424..82c186f8 100644
--- a/share/www/script/test/design_docs.js
+++ b/share/www/script/test/design_docs.js
@@ -55,7 +55,7 @@ function() {
   var vinfo = dinfo.view_index;
   TEquals(51, vinfo.disk_size);
   TEquals(false, vinfo.compact_running);
-  TEquals("64625dce94960fd5ca116e42aa9d011a", vinfo.signature);
+  TEquals("3f88e53b303e2342e49a66c538c30679", vinfo.signature);
 
   db.bulkSave(makeDocs(1, numDocs + 1));
 
diff --git a/share/www/script/test/list_views.js b/share/www/script/test/list_views.js
index d845f926..55d34acc 100644
--- a/share/www/script/test/list_views.js
+++ b/share/www/script/test/list_views.js
@@ -317,7 +317,7 @@ couchTests.list_views = function(debug) {
   T(!(/Key: 1 /.test(xhr.responseText)));
   T(/Key: 2/.test(xhr.responseText));
   T(/FirstKey: 2/.test(xhr.responseText));
-  T(/LastKey: 11/.test(xhr.responseText));
+  T(/LastKey: 7/.test(xhr.responseText));
 
   // no multi-key fetch allowed when group=false
   xhr = CouchDB.request("POST", "/test_suite_db/_design/lists/_list/simpleForm/withReduce?group=false", {
diff --git a/share/www/script/test/view_collation_raw.js b/share/www/script/test/view_collation_raw.js
new file mode 100644
index 00000000..08f37fae
--- /dev/null
+++ b/share/www/script/test/view_collation_raw.js
@@ -0,0 +1,123 @@
+// Licensed under the Apache License, Version 2.0 (the "License"); you may not
+// use this file except in compliance with the License. You may obtain a copy of
+// the License at
+//
+//   http://www.apache.org/licenses/LICENSE-2.0
+//
+// Unless required by applicable law or agreed to in writing, software
+// distributed under the License is distributed on an "AS IS" BASIS, WITHOUT
+// WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied. See the
+// License for the specific language governing permissions and limitations under
+// the License.
+
+couchTests.view_collation_raw = function(debug) {
+  var db = new CouchDB("test_suite_db", {"X-Couch-Full-Commit":"false"});
+  db.deleteDb();
+  db.createDb();
+  if (debug) debugger;
+
+  // NOTE, the values are already in their correct sort order. Consider this
+  // a specification of collation of json types.
+
+  var values = [];
+
+  //  numbers
+  values.push(1);
+  values.push(2);
+  values.push(3);
+  values.push(4);
+  
+  values.push(false);
+  values.push(null);
+  values.push(true);
+  
+  // then object, compares each key value in the list until different.
+  // larger objects sort after their subset objects.
+  values.push({a:1});
+  values.push({a:2});
+  values.push({b:1});
+  values.push({b:2});
+  values.push({b:2, a:1}); // Member order does matter for collation.
+                           // CouchDB preserves member order
+                           // but doesn't require that clients will.
+                           // (this test might fail if used with a js engine
+                           // that doesn't preserve order)
+  values.push({b:2, c:2});
+
+  // then arrays. compared element by element until different.
+  // Longer arrays sort after their prefixes
+  values.push(["a"]);
+  values.push(["b"]);
+  values.push(["b","c"]);
+  values.push(["b","c", "a"]);
+  values.push(["b","d"]);
+  values.push(["b","d", "e"]);
+
+
+  // then text, case sensitive
+  values.push("A");
+  values.push("B");
+  values.push("a");
+  values.push("aa");
+  values.push("b");
+  values.push("ba");
+  values.push("bb");
+
+  for (var i=0; i<values.length; i++) {
+    db.save({_id:(i).toString(), foo:values[i]});
+  }
+
+  var designDoc = {
+    _id:"_design/test", // turn off couch.js id escaping?
+    language: "javascript",
+    views: {
+      test: {map: "function(doc) { emit(doc.foo, null); }",
+            options: {collation:"raw"}}
+    }
+  }
+  T(db.save(designDoc).ok);
+  var rows = db.view("test/test").rows;
+  for (i=0; i<values.length; i++) {
+    T(equals(rows[i].key, values[i]));
+  }
+
+  // everything has collated correctly. Now to check the descending output
+  rows = db.view("test/test", {descending: true}).rows;
+  for (i=0; i<values.length; i++) {
+    T(equals(rows[i].key, values[values.length - 1 -i]));
+  }
+
+  // now check the key query args
+  for (i=1; i<values.length; i++) {
+    rows = db.view("test/test", {key:values[i]}).rows;
+    T(rows.length == 1 && equals(rows[0].key, values[i]));
+  }
+
+  // test inclusive_end=true (the default)
+  // the inclusive_end=true functionality is limited to endkey currently
+  // if you need inclusive_start=false for startkey, please do implement. ;)
+  var rows = db.view("test/test", {endkey : "b", inclusive_end:true}).rows;
+  T(rows[rows.length-1].key == "b")
+  // descending=true
+  var rows = db.view("test/test", {endkey : "b",
+    descending:true, inclusive_end:true}).rows;
+  T(rows[rows.length-1].key == "b")
+
+  // test inclusive_end=false
+  var rows = db.view("test/test", {endkey : "b", inclusive_end:false}).rows;
+  T(rows[rows.length-1].key == "aa")
+  // descending=true
+  var rows = db.view("test/test", {endkey : "b",
+    descending:true, inclusive_end:false}).rows;
+  T(rows[rows.length-1].key == "ba")
+  
+  var rows = db.view("test/test", {
+    endkey : "b", endkey_docid: "10",
+    inclusive_end:false}).rows;
+  T(rows[rows.length-1].key == "aa")
+  
+  var rows = db.view("test/test", {
+    endkey : "b", endkey_docid: "11",
+    inclusive_end:false}).rows;
+  T(rows[rows.length-1].key == "aa")
+};
diff --git a/src/couchdb/couch_btree.erl b/src/couchdb/couch_btree.erl
index 6176603c..0dad13f8 100644
--- a/src/couchdb/couch_btree.erl
+++ b/src/couchdb/couch_btree.erl
@@ -14,7 +14,7 @@
 
 -export([open/2, open/3, query_modify/4, add/2, add_remove/3]).
 -export([fold/4, full_reduce/1, final_reduce/2,foldl/3,foldl/4]).
--export([fold_reduce/6, fold_reduce/7, lookup/2, get_state/1, set_options/2]).
+-export([fold_reduce/4, lookup/2, get_state/1, set_options/2]).
 
 -define(CHUNK_THRESHOLD, 16#4ff).
 
@@ -69,10 +69,11 @@ final_reduce(Reduce, {KVs, Reductions}) ->
     Red = Reduce(reduce, KVs),
     final_reduce(Reduce, {[], [Red | Reductions]}).
 
-fold_reduce(Bt, StartKey, EndKey, KeyGroupFun, Fun, Acc) ->
-    fold_reduce(Bt, fwd, StartKey, EndKey, KeyGroupFun, Fun, Acc).
-
-fold_reduce(#btree{root=Root}=Bt, Dir, StartKey, EndKey, KeyGroupFun, Fun, Acc) ->
+fold_reduce(#btree{root=Root}=Bt, Fun, Acc, Options) ->
+    Dir = proplists:get_value(dir, Options, fwd),
+    StartKey = proplists:get_value(start_key, Options),
+    EndKey = proplists:get_value(end_key, Options),
+    KeyGroupFun = proplists:get_value(key_group_fun, Options, fun(_,_) -> true end),
     {StartKey2, EndKey2} =
     case Dir of
         rev -> {EndKey, StartKey};
@@ -80,9 +81,9 @@ fold_reduce(#btree{root=Root}=Bt, Dir, StartKey, EndKey, KeyGroupFun, Fun, Acc)
     end,
     try
         {ok, Acc2, GroupedRedsAcc2, GroupedKVsAcc2, GroupedKey2} =
-            reduce_stream_node(Bt, Dir, Root, StartKey2, EndKey2, nil, [], [],
+            reduce_stream_node(Bt, Dir, Root, StartKey2, EndKey2, undefined, [], [],
             KeyGroupFun, Fun, Acc),
-        if GroupedKey2 == nil ->
+        if GroupedKey2 == undefined ->
             {ok, Acc2};
         true ->
             case Fun(GroupedKey2, {GroupedKVsAcc2, GroupedRedsAcc2}, Acc2) of
@@ -105,11 +106,10 @@ convert_fun_arity(Fun) when is_function(Fun, 2) ->
 convert_fun_arity(Fun) when is_function(Fun, 3) ->
     Fun.    % Already arity 3
 
-
 make_key_in_end_range_function(#btree{less=Less}, fwd, Options) ->
-    case proplists:get_value(end_key, Options) of
+    case proplists:get_value(end_key_gt, Options) of
     undefined ->
-        case proplists:get_value(end_key_inclusive, Options) of
+        case proplists:get_value(end_key, Options) of
         undefined ->
             fun(_Key) -> true end;
         LastKey ->
@@ -119,9 +119,9 @@ make_key_in_end_range_function(#btree{less=Less}, fwd, Options) ->
         fun(Key) -> Less(Key, EndKey) end
     end;
 make_key_in_end_range_function(#btree{less=Less}, rev, Options) ->
-    case proplists:get_value(end_key, Options) of
+    case proplists:get_value(end_key_gt, Options) of
     undefined ->
-        case proplists:get_value(end_key_inclusive, Options) of
+        case proplists:get_value(end_key, Options) of
         undefined ->
             fun(_Key) -> true end;
         LastKey ->
@@ -179,15 +179,11 @@ query_modify(Bt, LookupKeys, InsertValues, RemoveKeys) ->
     FetchActions = [{fetch, Key, nil} || Key <- LookupKeys],
     SortFun =
         fun({OpA, A, _}, {OpB, B, _}) ->
-            case less(Bt, A, B) of
-            true -> true;
+            case A == B of
+            % A and B are equal, sort by op.
+            true -> op_order(OpA) < op_order(OpB);
             false ->
-                case less(Bt, B, A) of
-                true -> false;
-                false ->
-                    % A and B are equal, sort by op.
-                    op_order(OpA) < op_order(OpB)
-                end
+                less(Bt, A, B)
             end
         end,
     Actions = lists:sort(SortFun, lists:append([InsertActions, RemoveActions, FetchActions])),
@@ -482,14 +478,14 @@ reduce_stream_kv_node(Bt, Dir, KVs, KeyStart, KeyEnd,
 
     GTEKeyStartKVs =
     case KeyStart of
-    nil ->
+    undefined ->
         KVs;
     _ ->
         lists:dropwhile(fun({Key,_}) -> less(Bt, Key, KeyStart) end, KVs)
     end,
     KVs2 =
     case KeyEnd of
-    nil ->
+    undefined ->
         GTEKeyStartKVs;
     _ ->
         lists:takewhile(
@@ -507,7 +503,7 @@ reduce_stream_kv_node2(_Bt, [], GroupedKey, GroupedKVsAcc, GroupedRedsAcc,
 reduce_stream_kv_node2(Bt, [{Key, Value}| RestKVs], GroupedKey, GroupedKVsAcc,
         GroupedRedsAcc, KeyGroupFun, Fun, Acc) ->
     case GroupedKey of
-    nil ->
+    undefined ->
         reduce_stream_kv_node2(Bt, RestKVs, Key,
                 [assemble(Bt,Key,Value)], [], KeyGroupFun, Fun, Acc);
     _ ->
@@ -533,7 +529,7 @@ reduce_stream_kp_node(Bt, Dir, NodeList, KeyStart, KeyEnd,
                         KeyGroupFun, Fun, Acc) ->
     Nodes =
     case KeyStart of
-    nil ->
+    undefined ->
         NodeList;
     _ ->
         lists:dropwhile(
@@ -543,7 +539,7 @@ reduce_stream_kp_node(Bt, Dir, NodeList, KeyStart, KeyEnd,
     end,
     NodesInRange =
     case KeyEnd of
-    nil ->
+    undefined ->
         Nodes;
     _ ->
         {InRange, MaybeInRange} = lists:splitwith(
@@ -557,9 +553,9 @@ reduce_stream_kp_node(Bt, Dir, NodeList, KeyStart, KeyEnd,
 
 
 reduce_stream_kp_node2(Bt, Dir, [{_Key, NodeInfo} | RestNodeList], KeyStart, KeyEnd,
-                        nil, [], [], KeyGroupFun, Fun, Acc) ->
+                        undefined, [], [], KeyGroupFun, Fun, Acc) ->
     {ok, Acc2, GroupedRedsAcc2, GroupedKVsAcc2, GroupedKey2} =
-            reduce_stream_node(Bt, Dir, NodeInfo, KeyStart, KeyEnd, nil,
+            reduce_stream_node(Bt, Dir, NodeInfo, KeyStart, KeyEnd, undefined,
                 [], [], KeyGroupFun, Fun, Acc),
     reduce_stream_kp_node2(Bt, Dir, RestNodeList, KeyStart, KeyEnd, GroupedKey2,
             GroupedKVsAcc2, GroupedRedsAcc2, KeyGroupFun, Fun, Acc2);
diff --git a/src/couchdb/couch_db.erl b/src/couchdb/couch_db.erl
index 9cace709..736b80aa 100644
--- a/src/couchdb/couch_db.erl
+++ b/src/couchdb/couch_db.erl
@@ -200,7 +200,7 @@ get_design_docs(#db{fulldocinfo_by_id_btree=Btree}=Db) ->
         (_, _Reds, AccDocs) ->
             {stop, AccDocs}
         end,
-        [], [{start_key, <<"_design/">>}, {end_key, <<"_design0">>}]),
+        [], [{start_key, <<"_design/">>}, {end_key_gt, <<"_design0">>}]),
     {ok, Docs}.
 
 check_is_admin(#db{admins=Admins, user_ctx=#user_ctx{name=Name,roles=Roles}}) ->
@@ -716,13 +716,10 @@ changes_since(Db, Style, StartSeq, Fun, Options, Acc) ->
 count_changes_since(Db, SinceSeq) ->
     {ok, Changes} =
     couch_btree:fold_reduce(Db#db.docinfo_by_seq_btree,
-        SinceSeq + 1, % startkey
-        ok, % endkey
-        fun(_,_) -> true end, % groupkeys
         fun(_SeqStart, PartialReds, 0) ->
             {ok, couch_btree:final_reduce(Db#db.docinfo_by_seq_btree, PartialReds)}
         end,
-        0),
+        0, [{start_key, SinceSeq + 1}]),
     Changes.
 
 enum_docs_since(Db, SinceSeq, InFun, Acc, Options) ->
diff --git a/src/couchdb/couch_db.hrl b/src/couchdb/couch_db.hrl
index ead78418..a52bc983 100644
--- a/src/couchdb/couch_db.hrl
+++ b/src/couchdb/couch_db.hrl
@@ -14,6 +14,9 @@
 -define(DESIGN_DOC_PREFIX0, "_design").
 -define(DESIGN_DOC_PREFIX, "_design/").
 
+-define(MIN_STR, <<"">>).
+-define(MAX_STR, <<255>>). % illegal utf string
+
 -define(JSON_ENCODE(V), mochijson2:encode(V)).
 -define(JSON_DECODE(V), mochijson2:decode(V)).
 
@@ -157,10 +160,10 @@
 
 
 -record(view_query_args, {
-    start_key = nil,
-    end_key = {},
-    start_docid = nil,
-    end_docid = {},
+    start_key,
+    end_key,
+    start_docid = ?MIN_STR,
+    end_docid = ?MAX_STR,
 
     direction = fwd,
     inclusive_end=true, % aka a closed-interval
@@ -218,7 +221,8 @@
     map_names=[],
     def,
     btree=nil,
-    reduce_funs=[]
+    reduce_funs=[],
+    options=[]
     }).
 
 -record(index_header,
diff --git a/src/couchdb/couch_db_updater.erl b/src/couchdb/couch_db_updater.erl
index 42a85894..a13f9955 100644
--- a/src/couchdb/couch_db_updater.erl
+++ b/src/couchdb/couch_db_updater.erl
@@ -14,7 +14,6 @@
 -behaviour(gen_server).
 
 -export([btree_by_id_reduce/2,btree_by_seq_reduce/2]).
--export([less_docid/2]).
 -export([init/1,terminate/2,handle_call/3,handle_cast/2,code_change/3,handle_info/2]).
 
 -include("couch_db.hrl").
@@ -279,13 +278,6 @@ simple_upgrade_record(Old, New) ->
         lists:sublist(tuple_to_list(New), size(Old) + 1, size(New)-size(Old)),
     list_to_tuple(tuple_to_list(Old) ++ NewValuesTail).
 
-less_docid(A, B) when A == B -> false;
-less_docid(nil, _) -> true; % nil - special key sorts before all
-less_docid({}, _) -> false; % {} -> special key sorts after all
-less_docid(_, nil) -> false;
-less_docid(_, {}) -> true; 
-less_docid(A, B) -> A < B.
-
 
 init_db(DbName, Filepath, Fd, Header0) ->
     Header1 = simple_upgrade_record(Header0, #db_header{}),
@@ -297,7 +289,6 @@ init_db(DbName, Filepath, Fd, Header0) ->
     ?LATEST_DISK_VERSION -> Header1;
     _ -> throw({database_disk_version_error, "Incorrect disk header version"})
     end,
-    Less = fun less_docid/2,
 
     {ok, FsyncOptions} = couch_util:parse_term(
             couch_config:get("couchdb", "fsync_options",
@@ -311,8 +302,7 @@ init_db(DbName, Filepath, Fd, Header0) ->
     {ok, IdBtree} = couch_btree:open(Header#db_header.fulldocinfo_by_id_btree_state, Fd,
         [{split, fun(X) -> btree_by_id_split(X) end},
         {join, fun(X,Y) -> btree_by_id_join(X,Y) end},
-        {reduce, fun(X,Y) -> btree_by_id_reduce(X,Y) end},
-        {less, Less}]),
+        {reduce, fun(X,Y) -> btree_by_id_reduce(X,Y) end}]),
     {ok, SeqBtree} = couch_btree:open(Header#db_header.docinfo_by_seq_btree_state, Fd,
             [{split, fun(X) -> btree_by_seq_split(X) end},
             {join, fun(X,Y) -> btree_by_seq_join(X,Y) end},
diff --git a/src/couchdb/couch_httpd_auth.erl b/src/couchdb/couch_httpd_auth.erl
index 6df1a393..00952942 100644
--- a/src/couchdb/couch_httpd_auth.erl
+++ b/src/couchdb/couch_httpd_auth.erl
@@ -128,7 +128,7 @@ get_user(Db, UserName) ->
         {ok, View, _Group} ->
             FoldFun = fun({_, Value}, _, {_}) -> {stop, Value} end,
             {ok, _, {Result}} = couch_view:fold(View, FoldFun, {nil},
-                    [{start_key, {UserName, nil}},{end_key, {UserName, {}}}]),
+                    [{start_key, {UserName, ?MIN_STR}},{end_key, {UserName, ?MAX_STR}}]),
             Result;
         {not_found, _Reason} ->
             nil
diff --git a/src/couchdb/couch_httpd_db.erl b/src/couchdb/couch_httpd_db.erl
index 2e0a2fdb..dab583e3 100644
--- a/src/couchdb/couch_httpd_db.erl
+++ b/src/couchdb/couch_httpd_db.erl
@@ -597,7 +597,7 @@ all_docs_view(Req, Db, Keys) ->
             end,
             {ok, LastOffset, FoldResult} = couch_db:enum_docs(Db,
                 AdapterFun, FoldAccInit, [{start_key, StartId}, {dir, Dir},
-                    {if Inclusive -> end_key_inclusive; true -> end_key end, EndId}]),
+                    {if Inclusive -> end_key; true -> end_key_gt end, EndId}]),
             couch_httpd_view:finish_view_fold(Req, TotalRowCount, LastOffset, FoldResult);
         _ ->
             FoldlFun = couch_httpd_view:make_view_fold_fun(Req, QueryArgs, CurrentEtag, Db,
diff --git a/src/couchdb/couch_httpd_show.erl b/src/couchdb/couch_httpd_show.erl
index 176a9b15..3aa6b566 100644
--- a/src/couchdb/couch_httpd_show.erl
+++ b/src/couchdb/couch_httpd_show.erl
@@ -168,13 +168,9 @@ send_view_list_response(Lang, ListSrc, ViewName, DesignId, Req, Db, Keys) ->
 output_map_list(#httpd{mochi_req=MReq, user_ctx=UserCtx}=Req, Lang, ListSrc, View, Group, Db, QueryArgs, nil) ->
     #view_query_args{
         limit = Limit,
-        direction = Dir,
-        skip = SkipCount,
-        start_key = StartKey,
-        start_docid = StartDocId
+        skip = SkipCount
     } = QueryArgs,
     {ok, RowCount} = couch_view:get_row_count(View),
-    Start = {StartKey, StartDocId},
     Headers = MReq:get(headers),
     Hlist = mochiweb_headers:to_list(Headers),
     Accept = proplists:get_value('Accept', Hlist),
@@ -194,16 +190,15 @@ output_map_list(#httpd{mochi_req=MReq, user_ctx=UserCtx}=Req, Lang, ListSrc, Vie
                 send_row = SendListRowFun
             }),
         FoldAccInit = {Limit, SkipCount, undefined, []},
-        {ok, _, FoldResult} = couch_view:fold(View, FoldlFun, FoldAccInit, [{start_key, Start},{dir, Dir}]),
+        {ok, _, FoldResult} = couch_view:fold(View, FoldlFun, FoldAccInit,
+                couch_httpd_view:make_key_options(QueryArgs)),
         finish_list(Req, QueryServer, CurrentEtag, FoldResult, StartListRespFun, RowCount)
     end);
 
 output_map_list(#httpd{mochi_req=MReq, user_ctx=UserCtx}=Req, Lang, ListSrc, View, Group, Db, QueryArgs, Keys) ->
     #view_query_args{
         limit = Limit,
-        direction = Dir,
-        skip = SkipCount,
-        start_docid = StartDocId
+        skip = SkipCount
     } = QueryArgs,
     {ok, RowCount} = couch_view:get_row_count(View),
     Headers = MReq:get(headers),
@@ -221,16 +216,18 @@ output_map_list(#httpd{mochi_req=MReq, user_ctx=UserCtx}=Req, Lang, ListSrc, Vie
         FoldAccInit = {Limit, SkipCount, undefined, []},
         {ok, _, FoldResult} = lists:foldl(
             fun(Key, {ok, _, FoldAcc}) ->
-                FoldlFun = couch_httpd_view:make_view_fold_fun(Req, QueryArgs#view_query_args{
+                QueryArgs2 = QueryArgs#view_query_args{
                         start_key = Key,
                         end_key = Key
-                    }, CurrentEtag, Db, RowCount,
+                    },
+                FoldlFun = couch_httpd_view:make_view_fold_fun(Req, QueryArgs2, CurrentEtag, Db, RowCount,
                     #view_fold_helper_funs{
                         reduce_count = fun couch_view:reduce_to_count/1,
                         start_response = StartListRespFun,
                         send_row = SendListRowFun
                     }),
-                couch_view:fold(View, FoldlFun, FoldAcc, [{start_key, {Key, StartDocId}}, {dir, Dir}])
+                couch_view:fold(View, FoldlFun, FoldAcc,
+                    couch_httpd_view:make_key_options(QueryArgs2))
             end, {ok, nil, FoldAccInit}, Keys),
         finish_list(Req, QueryServer, CurrentEtag, FoldResult, StartListRespFun, RowCount)
     end).
@@ -295,12 +292,7 @@ send_non_empty_chunk(Resp, Chunk) ->
 output_reduce_list(#httpd{mochi_req=MReq, user_ctx=UserCtx}=Req, Lang, ListSrc, View, Group, Db, QueryArgs, nil) ->
     #view_query_args{
         limit = Limit,
-        direction = Dir,
         skip = SkipCount,
-        start_key = StartKey,
-        start_docid = StartDocId,
-        end_key = EndKey,
-        end_docid = EndDocId,
         group_level = GroupLevel
     } = QueryArgs,
     % get the os process here
@@ -321,19 +313,16 @@ output_reduce_list(#httpd{mochi_req=MReq, user_ctx=UserCtx}=Req, Lang, ListSrc,
                 send_row = SendListRowFun
             }),
         FoldAccInit = {Limit, SkipCount, undefined, []},
-        {ok, FoldResult} = couch_view:fold_reduce(View, Dir, {StartKey, StartDocId},
-            {EndKey, EndDocId}, GroupRowsFun, RespFun,
-            FoldAccInit),
+        {ok, FoldResult} = couch_view:fold_reduce(View, RespFun, FoldAccInit, 
+            [{key_group_fun, GroupRowsFun} | 
+                couch_httpd_view:make_key_options(QueryArgs)]),
         finish_list(Req, QueryServer, CurrentEtag, FoldResult, StartListRespFun, null)
     end);
 
 output_reduce_list(#httpd{mochi_req=MReq, user_ctx=UserCtx}=Req, Lang, ListSrc, View, Group, Db, QueryArgs, Keys) ->
     #view_query_args{
         limit = Limit,
-        direction = Dir,
         skip = SkipCount,
-        start_docid = StartDocId,
-        end_docid = EndDocId,
         group_level = GroupLevel
     } = QueryArgs,
     % get the os process here
@@ -343,7 +332,6 @@ output_reduce_list(#httpd{mochi_req=MReq, user_ctx=UserCtx}=Req, Lang, ListSrc,
     Hlist = mochiweb_headers:to_list(Headers),
     Accept = proplists:get_value('Accept', Hlist),
     CurrentEtag = couch_httpd_view:view_group_etag(Group, Db, {Lang, ListSrc, Accept, UserCtx, Keys}),
-
     couch_httpd:etag_respond(Req, CurrentEtag, fun() ->
         StartListRespFun = make_reduce_start_resp_fun(QueryServer, Req, Db, CurrentEtag),
         SendListRowFun = make_reduce_send_row_fun(QueryServer, Db),
@@ -357,8 +345,11 @@ output_reduce_list(#httpd{mochi_req=MReq, user_ctx=UserCtx}=Req, Lang, ListSrc,
         FoldAccInit = {Limit, SkipCount, undefined, []},
         {ok, FoldResult} = lists:foldl(
             fun(Key, {ok, FoldAcc}) ->
-                couch_view:fold_reduce(View, Dir, {Key, StartDocId},
-                    {Key, EndDocId}, GroupRowsFun, RespFun, FoldAcc)
+                couch_view:fold_reduce(View, RespFun, FoldAcc,
+                    [{key_group_fun, GroupRowsFun} | 
+                        couch_httpd_view:make_key_options(
+                        QueryArgs#view_query_args{start_key=Key, end_key=Key})]
+                    )    
             end, {ok, FoldAccInit}, Keys),
         finish_list(Req, QueryServer, CurrentEtag, FoldResult, StartListRespFun, null)
     end).
diff --git a/src/couchdb/couch_httpd_view.erl b/src/couchdb/couch_httpd_view.erl
index ba2a004a..4af1dc82 100644
--- a/src/couchdb/couch_httpd_view.erl
+++ b/src/couchdb/couch_httpd_view.erl
@@ -19,6 +19,7 @@
 -export([make_view_fold_fun/6, finish_view_fold/4, view_row_obj/3]).
 -export([view_group_etag/2, view_group_etag/3, make_reduce_fold_funs/5]).
 -export([design_doc_view/5, parse_bool_param/1, doc_member/3]).
+-export([make_key_options/1]).
 
 -import(couch_httpd,
     [send_json/2,send_json/3,send_json/4,send_method_not_allowed/2,send_chunk/2,
@@ -142,27 +143,23 @@ handle_temp_view_req(Req, _Db) ->
 output_map_view(Req, View, Group, Db, QueryArgs, nil) ->
     #view_query_args{
         limit = Limit,
-        direction = Dir,
-        skip = SkipCount,
-        start_key = StartKey,
-        start_docid = StartDocId
+        skip = SkipCount
     } = QueryArgs,
     CurrentEtag = view_group_etag(Group, Db),
     couch_httpd:etag_respond(Req, CurrentEtag, fun() ->
         {ok, RowCount} = couch_view:get_row_count(View),
         FoldlFun = make_view_fold_fun(Req, QueryArgs, CurrentEtag, Db, RowCount, #view_fold_helper_funs{reduce_count=fun couch_view:reduce_to_count/1}),
         FoldAccInit = {Limit, SkipCount, undefined, []},
-        {ok, LastReduce, FoldResult} = couch_view:fold(View, FoldlFun, FoldAccInit,
-                [{dir, Dir}, {start_key, {StartKey, StartDocId}} |  make_end_key_option(QueryArgs)]),
-        finish_view_fold(Req, RowCount, couch_view:reduce_to_count(LastReduce), FoldResult)
+        {ok, LastReduce, FoldResult} = couch_view:fold(View, 
+                FoldlFun, FoldAccInit, make_key_options(QueryArgs)),
+        finish_view_fold(Req, RowCount, 
+                couch_view:reduce_to_count(LastReduce), FoldResult)
     end);
 
 output_map_view(Req, View, Group, Db, QueryArgs, Keys) ->
     #view_query_args{
         limit = Limit,
-        direction = Dir,
-        skip = SkipCount,
-        start_docid = StartDocId
+        skip = SkipCount
     } = QueryArgs,
     CurrentEtag = view_group_etag(Group, Db, Keys),
     couch_httpd:etag_respond(Req, CurrentEtag, fun() ->
@@ -177,8 +174,7 @@ output_map_view(Req, View, Group, Db, QueryArgs, Keys) ->
                         reduce_count = fun couch_view:reduce_to_count/1
                     }),
                 {ok, LastReduce, FoldResult} = couch_view:fold(View, FoldlFun, FoldAcc, 
-                    [{dir, Dir},{start_key, {Key, StartDocId}} |  make_end_key_option(
-                            QueryArgs#view_query_args{end_key=Key})]),
+                    make_key_options(QueryArgs#view_query_args{start_key=Key, end_key=Key})),
                 {LastReduce, FoldResult}
             end, {{[],[]}, FoldAccInit}, Keys),
         finish_view_fold(Req, RowCount, couch_view:reduce_to_count(LastReduce), FoldResult)
@@ -186,21 +182,17 @@ output_map_view(Req, View, Group, Db, QueryArgs, Keys) ->
 
 output_reduce_view(Req, Db, View, Group, QueryArgs, nil) ->
     #view_query_args{
-        start_key = StartKey,
-        end_key = EndKey,
         limit = Limit,
         skip = Skip,
-        direction = Dir,
-        start_docid = StartDocId,
-        end_docid = EndDocId,
         group_level = GroupLevel
     } = QueryArgs,
     CurrentEtag = view_group_etag(Group, Db),
     couch_httpd:etag_respond(Req, CurrentEtag, fun() ->
         {ok, GroupRowsFun, RespFun} = make_reduce_fold_funs(Req, GroupLevel, QueryArgs, CurrentEtag, #reduce_fold_helper_funs{}),
         FoldAccInit = {Limit, Skip, undefined, []},
-        {ok, {_, _, Resp, _}} = couch_view:fold_reduce(View, Dir, {StartKey, StartDocId},
-            {EndKey, EndDocId}, GroupRowsFun, RespFun, FoldAccInit),
+        {ok, {_, _, Resp, _}} = couch_view:fold_reduce(View,
+                RespFun, FoldAccInit, [{key_group_fun, GroupRowsFun} |
+                make_key_options(QueryArgs)]),
         finish_reduce_fold(Req, Resp)
     end);
 
@@ -208,9 +200,6 @@ output_reduce_view(Req, Db, View, Group, QueryArgs, Keys) ->
     #view_query_args{
         limit = Limit,
         skip = Skip,
-        direction = Dir,
-        start_docid = StartDocId,
-        end_docid = EndDocId,
         group_level = GroupLevel
     } = QueryArgs,
     CurrentEtag = view_group_etag(Group, Db),
@@ -220,8 +209,10 @@ output_reduce_view(Req, Db, View, Group, QueryArgs, Keys) ->
             fun(Key, {Resp, RedAcc}) ->
                 % run the reduce once for each key in keys, with limit etc reapplied for each key
                 FoldAccInit = {Limit, Skip, Resp, RedAcc},
-                {_, {_, _, Resp2, RedAcc2}} = couch_view:fold_reduce(View, Dir, {Key, StartDocId},
-                    {Key, EndDocId}, GroupRowsFun, RespFun, FoldAccInit),
+                {_, {_, _, Resp2, RedAcc2}} = couch_view:fold_reduce(View,
+                        RespFun, FoldAccInit, [{key_group_fun, GroupRowsFun} |
+                        make_key_options(QueryArgs#view_query_args{
+                            start_key=Key, end_key=Key})]),
                 % Switch to comma
                 {Resp2, RedAcc2}
             end,
@@ -229,8 +220,8 @@ output_reduce_view(Req, Db, View, Group, QueryArgs, Keys) ->
         finish_reduce_fold(Req, Resp)
     end).
 
-reverse_key_default(nil) -> {};
-reverse_key_default({}) -> nil;
+reverse_key_default(?MIN_STR) -> ?MAX_STR;
+reverse_key_default(?MAX_STR) -> ?MIN_STR;
 reverse_key_default(Key) -> Key.
 
 get_stale_type(Req) ->
@@ -353,12 +344,8 @@ validate_view_query(descending, true, Args) ->
         fwd ->
             Args#view_query_args{
                 direction = rev,
-                start_key =
-                    reverse_key_default(Args#view_query_args.start_key),
                 start_docid =
                     reverse_key_default(Args#view_query_args.start_docid),
-                end_key =
-                    reverse_key_default(Args#view_query_args.end_key),
                 end_docid =
                     reverse_key_default(Args#view_query_args.end_docid)
             }
@@ -533,17 +520,33 @@ apply_default_helper_funs(#reduce_fold_helper_funs{
         send_row = SendRow2
     }.
 
+make_key_options(#view_query_args{direction = Dir}=QueryArgs) ->
+     [{dir,Dir} | make_start_key_option(QueryArgs) ++ 
+            make_end_key_option(QueryArgs)].
+
+make_start_key_option(
+        #view_query_args{
+            start_key = StartKey,
+            start_docid = StartDocId}) ->
+    if StartKey == undefined ->
+        [];
+    true ->
+        [{start_key, {StartKey, StartDocId}}]
+    end.
+
+make_end_key_option(#view_query_args{end_key = undefined}) ->
+    [];
 make_end_key_option(
         #view_query_args{end_key = EndKey,
             end_docid = EndDocId,
             inclusive_end = true}) ->
-    [{end_key_inclusive, {EndKey, EndDocId}}];
+    [{end_key, {EndKey, EndDocId}}];
 make_end_key_option(
         #view_query_args{
             end_key = EndKey,
             end_docid = EndDocId,
             inclusive_end = false}) ->
-    [{end_key, {EndKey,reverse_key_default(EndDocId)}}].
+    [{end_key_gt, {EndKey,reverse_key_default(EndDocId)}}].
 
 json_view_start_resp(Req, Etag, TotalViewCount, Offset, _Acc) ->
     {ok, Resp} = start_json_response(Req, 200, [{"Etag", Etag}]),
diff --git a/src/couchdb/couch_view.erl b/src/couchdb/couch_view.erl
index 41d34e89..778756ef 100644
--- a/src/couchdb/couch_view.erl
+++ b/src/couchdb/couch_view.erl
@@ -13,10 +13,10 @@
 -module(couch_view).
 -behaviour(gen_server).
 
--export([start_link/0,fold/4,less_json/2,less_json_keys/2,expand_dups/2,
+-export([start_link/0,fold/4,less_json/2,less_json_ids/2,expand_dups/2,
     detuple_kvs/2,init/1,terminate/2,handle_call/3,handle_cast/2,handle_info/2,
     code_change/3,get_reduce_view/4,get_temp_reduce_view/5,get_temp_map_view/4,
-    get_map_view/4,get_row_count/1,reduce_to_count/1,fold_reduce/7,
+    get_map_view/4,get_row_count/1,reduce_to_count/1,fold_reduce/4,
     extract_map_view/1,get_group_server/2,get_group_info/2,cleanup_index_files/1]).
 
 -include("couch_db.hrl").
@@ -152,16 +152,14 @@ expand_dups([{Key, {dups, Vals}} | Rest], Acc) ->
 expand_dups([KV | Rest], Acc) ->
     expand_dups(Rest, [KV | Acc]).
 
-fold_reduce({temp_reduce, #view{btree=Bt}}, Dir, StartKey, EndKey, GroupFun, Fun, Acc) ->
-
+fold_reduce({temp_reduce, #view{btree=Bt}}, Fun, Acc, Options) ->
     WrapperFun = fun({GroupedKey, _}, PartialReds, Acc0) ->
             {_, [Red]} = couch_btree:final_reduce(Bt, PartialReds),
             Fun(GroupedKey, Red, Acc0)
         end,
-    couch_btree:fold_reduce(Bt, Dir, StartKey, EndKey, GroupFun,
-            WrapperFun, Acc);
+    couch_btree:fold_reduce(Bt, WrapperFun, Acc, Options);
 
-fold_reduce({reduce, NthRed, Lang, #view{btree=Bt, reduce_funs=RedFuns}}, Dir, StartKey, EndKey, GroupFun, Fun, Acc) ->
+fold_reduce({reduce, NthRed, Lang, #view{btree=Bt, reduce_funs=RedFuns}}, Fun, Acc, Options) ->
     PreResultPadding = lists:duplicate(NthRed - 1, []),
     PostResultPadding = lists:duplicate(length(RedFuns) - NthRed, []),
     {_Name, FunSrc} = lists:nth(NthRed,RedFuns),
@@ -178,8 +176,7 @@ fold_reduce({reduce, NthRed, Lang, #view{btree=Bt, reduce_funs=RedFuns}}, Dir, S
             {_, Reds} = couch_btree:final_reduce(ReduceFun, PartialReds),
             Fun(GroupedKey, lists:nth(NthRed, Reds), Acc0)
         end,
-    couch_btree:fold_reduce(Bt, Dir, StartKey, EndKey, GroupFun,
-            WrapperFun, Acc).
+    couch_btree:fold_reduce(Bt, WrapperFun, Acc, Options).
 
 get_key_pos(_Key, [], _N) ->
     0;
@@ -358,9 +355,16 @@ nuke_dir(Dir) ->
         ok = file:del_dir(Dir)
     end.
 
+
 % keys come back in the language of btree - tuples.
-less_json_keys(A, B) ->
-    less_json(tuple_to_list(A), tuple_to_list(B)).
+less_json_ids({JsonA, IdA}, {JsonB, IdB}) ->
+    case JsonA == JsonB of
+    false ->
+        less_json(JsonA, JsonB);
+    true ->
+        IdA < IdB
+    end.
+        
 
 less_json(A, B) ->
     TypeA = type_sort(A),
@@ -382,7 +386,6 @@ type_sort({V}) when is_list(V) -> 4;
 type_sort(V) when is_tuple(V) -> 5.
 
 
-atom_sort(nil) -> 0;
 atom_sort(null) -> 1;
 atom_sort(false) -> 2;
 atom_sort(true) -> 3.
diff --git a/src/couchdb/couch_view_group.erl b/src/couchdb/couch_view_group.erl
index 8cae3e72..2a757c55 100644
--- a/src/couchdb/couch_view_group.erl
+++ b/src/couchdb/couch_view_group.erl
@@ -438,20 +438,21 @@ open_temp_group(DbName, Language, DesignOptions, MapSrc, RedSrc) ->
             id_num=0,
             btree=nil,
             def=MapSrc,
-            reduce_funs= if RedSrc==[] -> []; true -> [{<<"_temp">>, RedSrc}] end},
+            reduce_funs= if RedSrc==[] -> []; true -> [{<<"_temp">>, RedSrc}] end,
+            options=DesignOptions},
 
-        {ok, Db, #group{
-            name = <<"_temp">>,
-            db=Db,
-            views=[View],
-            def_lang=Language,
-            design_options=DesignOptions,
-            sig = erlang:md5(term_to_binary({[View], Language, DesignOptions}))
-        }};
+        {ok, Db, set_view_sig(#group{name = <<"_temp">>, db=Db, views=[View],
+            def_lang=Language, design_options=DesignOptions})};
     Error ->
         Error
     end.
 
+set_view_sig(#group{
+            views=Views,
+            def_lang=Language,
+            design_options=DesignOptions}=G) ->
+    G#group{sig=erlang:md5(term_to_binary({Views, Language, DesignOptions}))}.
+
 open_db_group(DbName, GroupId) ->
     case couch_db:open(DbName, []) of
     {ok, Db} ->
@@ -484,20 +485,17 @@ design_doc_to_view_group(#doc{id=Id,body={Fields}}) ->
     Language = proplists:get_value(<<"language">>, Fields, <<"javascript">>),
     {DesignOptions} = proplists:get_value(<<"options">>, Fields, {[]}),
     {RawViews} = proplists:get_value(<<"views">>, Fields, {[]}),
-    % sort the views by name to avoid spurious signature changes
-    SortedRawViews = lists:sort(fun({Name1, _}, {Name2, _}) ->
-            Name1 >= Name2
-        end, RawViews),
     % add the views to a dictionary object, with the map source as the key
     DictBySrc =
     lists:foldl(
         fun({Name, {MRFuns}}, DictBySrcAcc) ->
             MapSrc = proplists:get_value(<<"map">>, MRFuns),
             RedSrc = proplists:get_value(<<"reduce">>, MRFuns, null),
+            {ViewOptions} = proplists:get_value(<<"options">>, MRFuns, {[]}),
             View =
-            case dict:find(MapSrc, DictBySrcAcc) of
+            case dict:find({MapSrc, ViewOptions}, DictBySrcAcc) of
                 {ok, View0} -> View0;
-                error -> #view{def=MapSrc} % create new view object
+                error -> #view{def=MapSrc, options=ViewOptions} % create new view object
             end,
             View2 =
             if RedSrc == null ->
@@ -505,16 +503,15 @@ design_doc_to_view_group(#doc{id=Id,body={Fields}}) ->
             true ->
                 View#view{reduce_funs=[{Name,RedSrc}|View#view.reduce_funs]}
             end,
-            dict:store(MapSrc, View2, DictBySrcAcc)
-        end, dict:new(), SortedRawViews),
+            dict:store({MapSrc, ViewOptions}, View2, DictBySrcAcc)
+        end, dict:new(), RawViews),
     % number the views
     {Views, _N} = lists:mapfoldl(
         fun({_Src, View}, N) ->
             {View#view{id_num=N},N+1}
-        end, 0, dict:to_list(DictBySrc)),
+        end, 0, lists:sort(dict:to_list(DictBySrc))),
 
-    Group = #group{name=Id, views=Views, def_lang=Language, design_options=DesignOptions},
-    Group#group{sig=erlang:md5(term_to_binary({Views, Language, DesignOptions}))}.
+    set_view_sig(#group{name=Id, views=Views, def_lang=Language, design_options=DesignOptions}).
 
 reset_group(#group{views=Views}=Group) ->
     Views2 = [View#view{btree=nil} || View <- Views],
@@ -534,12 +531,13 @@ init_group(Db, Fd, #group{views=Views}=Group, nil) ->
     init_group(Db, Fd, Group,
         #index_header{seq=0, purge_seq=couch_db:get_purge_seq(Db),
             id_btree_state=nil, view_states=[nil || _ <- Views]});
-init_group(Db, Fd, #group{def_lang=Lang,views=Views}=Group, IndexHeader) ->
+init_group(Db, Fd, #group{def_lang=Lang,views=Views}=
+            Group, IndexHeader) ->
      #index_header{seq=Seq, purge_seq=PurgeSeq,
             id_btree_state=IdBtreeState, view_states=ViewStates} = IndexHeader,
     {ok, IdBtree} = couch_btree:open(IdBtreeState, Fd),
     Views2 = lists:zipwith(
-        fun(BtreeState, #view{reduce_funs=RedFuns}=View) ->
+        fun(BtreeState, #view{reduce_funs=RedFuns,options=Options}=View) ->
             FunSrcs = [FunSrc || {_Name, FunSrc} <- RedFuns],
             ReduceFun =
                 fun(reduce, KVs) ->
@@ -555,8 +553,15 @@ init_group(Db, Fd, #group{def_lang=Lang,views=Views}=Group, IndexHeader) ->
                         UserReds),
                     {Count, Reduced}
                 end,
+            
+            case proplists:get_value(<<"collation">>, Options, <<"default">>) of
+            <<"default">> ->
+                Less = fun couch_view:less_json_ids/2;
+            <<"raw">> ->
+                Less = fun(A,B) -> A < B end
+            end,
             {ok, Btree} = couch_btree:open(BtreeState, Fd,
-                        [{less, fun couch_view:less_json_keys/2},
+                        [{less, Less},
                             {reduce, ReduceFun}]),
             View#view{btree=Btree}
         end,