order by random sometimes crashes rethinkdb

[eden]

When ordering rows by the result of r.random(), rethinkdb sometimes crashes. Below is a stack trace and sample script. This only repros on Linux and did not repro when I ran it locally on my Mac.

import rethinkdb as r

conn = r.connect()

tables = r.db('test').table_list().run(conn)
if 'random' not in tables:
    r.db('test').table_create('random').run(conn)
    r.db('test').table('random').insert(dict(a=1)).run(conn)
    r.db('test').table('random').insert(dict(b=2)).run(conn)
    r.db('test').table('random').insert(dict(c=3)).run(conn)
    print 'test.random created'

for _ in range(0, 4):
    row = r.db('test').table('random').order_by(lambda t: r.random()).limit(1).run(conn)
    print row

conn.close()

Version: rethinkdb 2.2.5~0jessie (GCC 4.9.2)
error: Error in src/rdb_protocol/datum.cc at line 256:
error: Unreachable code:
error: Backtrace:
addr2line: addr2line: 'rethinkdb': No such file
'rethinkdb': No such file
error: Mon Mar 21 15:55:25 2016

       1 [0xa8b7f0]: backtrace_t::backtrace_t() at 0xa8b7f0 (rethinkdb)
       2 [0xa8bb69]: format_backtrace(bool) at 0xa8bb69 (rethinkdb)
       3 [0xd0135d]: report_fatal_error(char const*, int, char const*, ...) at 0xd0135d (rethinkdb)
       4 [0x8d190a]: ql::datum_t::data_wrapper_t::assign_copy(ql::datum_t::data_wrapper_t const&) at 0x8d190a (rethinkdb)
       5 [0x865570]: void std::__insertion_sort<__gnu_cxx::__normal_iterator<ql::datum_t*, std::vector<ql::datum_t, std::allocator<ql::datum_t> > >, __gnu_cxx::__ops::_Iter_comp_iter<boost::_bi::bind_t<boost::_bi::unspecified, ql::orderby_term_t::lt_cmp_t, boost::_bi::list4<boost::_bi::value<ql::env_t*>, boost::_bi::value<profile::sampler_t*>, boost::arg<1>, boost::arg<2> > > > >(__gnu_cxx::__normal_iterator<ql::datum_t*, std::vector<ql::datum_t, std::allocator<ql::datum_t> > >, __gnu_cxx::__normal_iterator<ql::datum_t*, std::vector<ql::datum_t, std::allocator<ql::datum_t> > >, __gnu_cxx::__ops::_Iter_comp_iter<boost::_bi::bind_t<boost::_bi::unspecified, ql::orderby_term_t::lt_cmp_t, boost::_bi::list4<boost::_bi::value<ql::env_t*>, boost::_bi::value<profile::sampler_t*>, boost::arg<1>, boost::arg<2> > > >) at 0x865570 (rethinkdb)
       6 [0x867bfe]: void std::__merge_sort_with_buffer<__gnu_cxx::__normal_iterator<ql::datum_t*, std::vector<ql::datum_t, std::allocator<ql::datum_t> > >, ql::datum_t*, __gnu_cxx::__ops::_Iter_comp_iter<boost::_bi::bind_t<boost::_bi::unspecified, ql::orderby_term_t::lt_cmp_t, boost::_bi::list4<boost::_bi::value<ql::env_t*>, boost::_bi::value<profile::sampler_t*>, boost::arg<1>, boost::arg<2> > > > >(__gnu_cxx::__normal_iterator<ql::datum_t*, std::vector<ql::datum_t, std::allocator<ql::datum_t> > >, __gnu_cxx::__normal_iterator<ql::datum_t*, std::vector<ql::datum_t, std::allocator<ql::datum_t> > >, ql::datum_t*, __gnu_cxx::__ops::_Iter_comp_iter<boost::_bi::bind_t<boost::_bi::unspecified, ql::orderby_term_t::lt_cmp_t, boost::_bi::list4<boost::_bi::value<ql::env_t*>, boost::_bi::value<profile::sampler_t*>, boost::arg<1>, boost::arg<2> > > >) at 0x867bfe (rethinkdb)
       7 [0x868383]: void std::__stable_sort_adaptive<__gnu_cxx::__normal_iterator<ql::datum_t*, std::vector<ql::datum_t, std::allocator<ql::datum_t> > >, ql::datum_t*, long, __gnu_cxx::__ops::_Iter_comp_iter<boost::_bi::bind_t<boost::_bi::unspecified, ql::orderby_term_t::lt_cmp_t, boost::_bi::list4<boost::_bi::value<ql::env_t*>, boost::_bi::value<profile::sampler_t*>, boost::arg<1>, boost::arg<2> > > > >(__gnu_cxx::__normal_iterator<ql::datum_t*, std::vector<ql::datum_t, std::allocator<ql::datum_t> > >, __gnu_cxx::__normal_iterator<ql::datum_t*, std::vector<ql::datum_t, std::allocator<ql::datum_t> > >, ql::datum_t*, long, __gnu_cxx::__ops::_Iter_comp_iter<boost::_bi::bind_t<boost::_bi::unspecified, ql::orderby_term_t::lt_cmp_t, boost::_bi::list4<boost::_bi::value<ql::env_t*>, boost::_bi::value<profile::sampler_t*>, boost::arg<1>, boost::arg<2> > > >) at 0x868383 (rethinkdb)
       8 [0x86ab6b]: ql::orderby_term_t::eval_impl(ql::scope_env_t*, ql::args_t*, ql::eval_flags_t) const at 0x86ab6b (rethinkdb)
       9 [0x7d0952]: ql::op_term_t::term_eval(ql::scope_env_t*, ql::eval_flags_t) const at 0x7d0952 (rethinkdb)
       10 [0x8ea64a]: ql::runtime_term_t::eval_on_current_stack(ql::scope_env_t*, ql::eval_flags_t) const at 0x8ea64a (rethinkdb)
       11 [0x8ea94c]: ql::runtime_term_t::eval(ql::scope_env_t*, ql::eval_flags_t) const at 0x8ea94c (rethinkdb)
       12 [0x7cd19a]: ql::op_term_t::maybe_grouped_data(ql::scope_env_t*, ql::argvec_t*, ql::eval_flags_t, counted_t<ql::grouped_data_t>*, scoped_ptr_t<ql::val_t>*) const at 0x7cd19a (rethinkdb)
       13 [0x7d030b]: ql::op_term_t::term_eval(ql::scope_env_t*, ql::eval_flags_t) const at 0x7d030b (rethinkdb)
       14 [0x8ea64a]: ql::runtime_term_t::eval_on_current_stack(ql::scope_env_t*, ql::eval_flags_t) const at 0x8ea64a (rethinkdb)
       15 [0x8ea94c]: ql::runtime_term_t::eval(ql::scope_env_t*, ql::eval_flags_t) const at 0x8ea94c (rethinkdb)
       16 [0x6fbc46]: ql::query_cache_t::ref_t::run(ql::env_t*, ql::response_t*) at 0x6fbc46 (rethinkdb)
       17 [0x6fd6be]: ql::query_cache_t::ref_t::fill_response(ql::response_t*) at 0x6fd6be (rethinkdb)
       18 [0x7cb503]: rdb_query_server_t::run_query(ql::query_params_t*, ql::response_t*, signal_t*) at 0x7cb503 (rethinkdb)
       19 [0xa88457]: void save_exception<void query_server_t::connection_loop<json_protocol_t>(linux_tcp_conn_t*, unsigned long, ql::query_cache_t*, signal_t*)::{lambda()#1}::operator()() const::{lambda()#1}>(std::__exception_ptr::exception_ptr*, std::string*, cond_t*, void query_server_t::connection_loop<json_protocol_t>(linux_tcp_conn_t*, unsigned long, ql::query_cache_t*, signal_t*)::{lambda()#1}::operator()() const::{lambda()#1}&&) at 0xa88457 (rethinkdb)
       20 [0xa88a4a]: void query_server_t::connection_loop<json_protocol_t>(linux_tcp_conn_t*, unsigned long, ql::query_cache_t*, signal_t*)::{lambda()#1}::operator()() const at 0xa88a4a (rethinkdb)
       21 [0x99c958]: coro_t::run() at 0x99c958 (rethinkdb)
error: Exiting.

[danielmewes]

Thanks for the bug report @eden .

I think we didn't consider the scenario of having a non-deterministic function to sort on when implementing orderBy. We make use of the standard library's std::stable_sort, and I think that gets into trouble when the comparison isn't behaving consistently, depending on its implementation (which explains why it crashes on Linux and not on Mac).

As a work-around, you can do something like this:

r.db('test').table('random').map(r.row.merge({"rand_ind": r.random()})).order_by("rand_ind").limit(1).without("rand_ind").run(conn)

[danielmewes]

I think we should probably rewrite the in-memory order_by to pre-compute all sorting values. Alternatively we could disallow non-deterministic sorting functions.

[mlucy]

We should probably disallow non-deterministic sorting functions; that seems a little clearer.

[soplakanets]

Hi, I'm having an issue with sorting by random also. The stacktrace:

2016-04-21T08:01:10.678165622 43.918828s error: Error in src/rdb_protocol/datum.cc at line 1475:
2016-04-21T08:01:10.678263985 43.918923s error: Unreachable code:
2016-04-21T08:01:10.678282800 43.918941s error: Backtrace:
2016-04-21T08:01:10.894402209 44.135066s error: Thu Apr 21 08:01:10 2016\n\n1 [0xa5ce10]: backtrace_t::backtrace_t() at ??:?\n2 [0xa5d1a3]: format_backtrace(bool) at ??:?\n3 [0xc9f6b5]: report_fatal_error(char const*, int, char const*, ...) at ??:?\n4 [0x8db1d6]: void ql::datum_t::write_json_unchecked_stack<rapidjson::Writer<rapidjson::GenericStringBuffer<rapidjson::UTF8<char>, rapidjson::RAllocator>, rapidjson::UTF8<char>, rapidjson::UTF8<char>, rapidjson::RAllocator> >(rapidjson::Writer<rapidjson::GenericStringBuffer<rapidjson::UTF8<char>, rapidjson::RAllocator>, rapidjson::UTF8<char>, rapidjson::UTF8<char>, rapidjson::RAllocator>*) const at ??:?\n5 [0x8dc1fa]: void ql::datum_t::write_json<rapidjson::Writer<rapidjson::GenericStringBuffer<rapidjson::UTF8<char>, rapidjson::RAllocator>, rapidjson::UTF8<char>, rapidjson::UTF8<char>, rapidjson::RAllocator> >(rapidjson::Writer<rapidjson::GenericStringBuffer<rapidjson::UTF8<char>, rapidjson::RAllocator>, rapidjson::UTF8<char>, rapidjson::UTF8<char>, rapidjson::RAllocator>*) const at ??:?\n6 [0x8dae43]: void ql::datum_t::write_json_unchecked_stack<rapidjson::Writer<rapidjson::GenericStringBuffer<rapidjson::UTF8<char>, rapidjson::RAllocator>, rapidjson::UTF8<char>, rapidjson::UTF8<char>, rapidjson::RAllocator> >(rapidjson::Writer<rapidjson::GenericStringBuffer<rapidjson::UTF8<char>, rapidjson::RAllocator>, rapidjson::UTF8<char>, rapidjson::UTF8<char>, rapidjson::RAllocator>*) const at ??:?\n7 [0x8dc1fa]: void ql::datum_t::write_json<rapidjson::Writer<rapidjson::GenericStringBuffer<rapidjson::UTF8<char>, rapidjson::RAllocator>, rapidjson::UTF8<char>, rapidjson::UTF8<char>, rapidjson::RAllocator> >(rapidjson::Writer<rapidjson::GenericStringBuffer<rapidjson::UTF8<char>, rapidjson::RAllocator>, rapidjson::UTF8<char>, rapidjson::UTF8<char>, rapidjson::RAllocator>*) const at ??:?\n8 [0xa52750]: write_response_internal(ql::response_t*, rapidjson::GenericStringBuffer<rapidjson::UTF8<char>, rapidjson::RAllocator>*, bool) at ??:?\n9 [0xa574a8]: query_server_t::handle(http_req_t const&, http_res_t*, signal_t*) at ??:?\n10 [0x9c627d]: routing_http_app_t::handle(http_req_t const&, http_res_t*, signal_t*) at ??:?\n11 [0x9c627d]: routing_http_app_t::handle(http_req_t const&, http_res_t*, signal_t*) at ??:?\n12 [0x9cff34]: http_server_t::handle_conn(scoped_ptr_t<linux_tcp_conn_descriptor_t> const&, auto_drainer_t::lock_t) at ??:?\n13 [0x9d34e4]: std::_Function_handler<void (scoped_ptr_t<linux_tcp_conn_descriptor_t>&), boost::_bi::bind_t<void, boost::_mfi::mf2<void, http_server_t, scoped_ptr_t<linux_tcp_conn_descriptor_t> const&, auto_drainer_t::lock_t>, boost::_bi::list3<boost::_bi::value<http_server_t*>, boost::arg<1>, boost::_bi::value<auto_drainer_t::lock_t> > > >::_M_invoke(std::_Any_data const&, scoped_ptr_t<linux_tcp_conn_descriptor_t>&) at ??:?\n14 [0x969b6c]: linux_nonthrowing_tcp_listener_t::handle(int) at ??:?\n15 [0x9819f8]: coro_t::run() at ??:?
2016-04-21T08:01:10.894879411 44.135538s error: Exiting.

The query is quite complicated, used it while sifting through data, don't think any sane person should do this in production, but still...

var startDate = new Date(2016, 8, 1);
var endDate = new Date(2016,9,31);
var start = r.time(startDate.getUTCFullYear(), startDate.getUTCMonth() + 1, startDate.getUTCDate(), 0, 0, 0, 'Z');
var end = r.time(endDate.getUTCFullYear(), endDate.getUTCMonth() + 1, endDate.getUTCDate(), 23, 59, 59, 'Z');
r.db('dbName').table("tableName").concatMap(function(D) {
          return D('schedule').merge({
            id: D('id'),
            realWishlistedCount: D('realWishlistedCount').default(0),
            destinationId: D('destinationId')
          })
        })
        .filter(r.row('realWishlistedCount').gt(0)) // only show those at least 2 users have wishlisted
        .filter(function(D) {
           return r.or(
             // case 1: date range is smaller than reason's range
             r.expr(start).during(D('start'), D('end'), {leftBound: 'open', rightBound: 'open'})
                .or(r.expr(end).during(D('start'), D('end'), {leftBound: 'open', rightBound: 'open'}))
             // case 2: reason's range is smaller than date range
           , D('start').during(start, end, {leftBound: 'open', rightBound: 'open'})
                .or(D('end').during(start, end, {leftBound: 'open', rightBound: 'open'}))
            );
        })
        .group('id')
        .max('realWishlistedCount')
        .ungroup()
        .map(function(D) {
          return {
            reasonId: D('group'),
            destinationId: D('reduction')('destinationId'),
            score: D('reduction')('realWishlistedCount')
          }
        })
.orderBy(function () { return r.random(); })

[eden]

@soplakanets it seems like the recommendation would be to merge in the random value in your map then sort on its value in the orderBy making the result of the sort predicate deterministic.

I think the RethinkDB documentation should be updated to at least call out the degenerate behavior with non-deterministic functions.

[soplakanets]

@eden Thank you very much. That was easy, should have figure that out myself :) +1 for updating docs.

[nighelles]

This is fixed in next.