Segmentation Fault in JoinIndex when joining large tables (GCC only)

[SvenLehmann]

There is a bug in the JoinIndex operator that occurs with GCC, but not with Clang.

Consider the following playground:

#include <iostream>

#include "operators/get_table.hpp"
#include "operators/join_index.hpp"

#include "storage/chunk.hpp"
#include "storage/index/b_tree/b_tree_index.hpp"
#include "storage/storage_manager.hpp"
#include "storage/table.hpp"

using namespace opossum;  // NOLINT

int main() {
  const auto table = std::make_shared<Table>(TableColumnDefinitions{{"column", DataType::Int}}, TableType::Data,
                                             100'000, UseMvcc::Yes);

  // Create table with 600'000 rows
  for (int i = 0; i < 600'000; i++) {
    table->append({i});
  }

  // Create indices
  const auto chunks = table->chunks();
  for (const auto& chunk : chunks) {
    chunk->template create_index<BTreeIndex>({ColumnID{0}});
  }
  StorageManager::get().add_table("table", table);

  // Run IndexJoin
  auto gt = std::make_shared<GetTable>("table");
  gt->execute();
  auto join = std::make_shared<JoinIndex>(
      gt, gt, JoinMode::Inner, std::pair<ColumnID, ColumnID>{ColumnID{0}, ColumnID{0}}, PredicateCondition::Equals);
  // Will crash with GCC, but not with Clang
  join->execute();

  return 0;
}

The same test runs fine with smaller tables, e.g., 500'000, but will fail for larger tables, e.g., 700'000 rows, as well. It seems like the relevant criteria is the number of join matches, which is here 600'000.

The stacktrace looks as follows:

Program received signal SIGSEGV, Segmentation fault.
0x0000000000b5186e in boost::container::allocator_traits<boost::container::new_allocator<opossum::RowID> >::priv_construct<opossum::RowID, opossum::RowID const&> (p=0x0, args=...)
    at /usr/include/boost/container/allocator_traits.hpp:415
415       {  ::new((void*)p, boost_container_new_t()) T(::boost::forward<Args>(args)...); }
(gdb) bt
#0  0x0000000000b5186e in boost::container::allocator_traits<boost::container::new_allocator<opossum::RowID> >::priv_construct<opossum::RowID, opossum::RowID const&> (p=0x0, args=...)
    at /usr/include/boost/container/allocator_traits.hpp:415
#1  0x0000000000b51820 in boost::container::allocator_traits<boost::container::new_allocator<opossum::RowID> >::construct<opossum::RowID, opossum::RowID const&> (a=..., p=0x0, args=...)
    at /usr/include/boost/container/allocator_traits.hpp:360
#2  0x0000000000b517c4 in boost::container::container_detail::dispatch_uses_allocator<boost::container::new_allocator<opossum::RowID>, boost::container::pmr::memory_resource*, opossum::RowID, opossum::RowID const&> (
    construct_alloc=..., arg_alloc=@0x7fffffffc098: 0x12aa1d0, p=0x0, args=...) at /usr/include/boost/container/detail/dispatch_uses_allocator.hpp:121
#3  0x0000000000b5177a in boost::container::pmr::polymorphic_allocator<opossum::RowID>::construct<opossum::RowID, opossum::RowID const&> (this=0x3190d10, p=0x0, args=...)
    at /usr/include/boost/container/pmr/polymorphic_allocator.hpp:107
#4  0x0000000000b51710 in std::allocator_traits<boost::container::pmr::polymorphic_allocator<opossum::RowID> >::_S_construct<opossum::RowID, opossum::RowID const&> (__a=..., __p=0x0, __args=...)
    at /usr/bin/../lib/gcc/x86_64-linux-gnu/8/../../../../include/c++/8/bits/alloc_traits.h:243
#5  0x0000000000b51380 in std::allocator_traits<boost::container::pmr::polymorphic_allocator<opossum::RowID> >::construct<opossum::RowID, opossum::RowID const&> (__a=..., __p=0x0, __args=...)
    at /usr/bin/../lib/gcc/x86_64-linux-gnu/8/../../../../include/c++/8/bits/alloc_traits.h:344
#6  0x0000000000b4059e in std::vector<opossum::RowID, boost::container::pmr::polymorphic_allocator<opossum::RowID> >::push_back (this=0x3190d10, __x=...)
    at /usr/bin/../lib/gcc/x86_64-linux-gnu/8/../../../../include/c++/8/bits/stl_vector.h:1079
#7  0x0000000000b525c7 in std::back_insert_iterator<opossum::PosList>::operator= (this=0x7fffffffc1e0, __value=...) at /usr/bin/../lib/gcc/x86_64-linux-gnu/8/../../../../include/c++/8/bits/stl_iterator.h:489
#8  0x0000000000b52534 in std::__fill_n_a<std::back_insert_iterator<opossum::PosList>, long, opossum::RowID> (__first=..., __n=1, __value=...)
    at /usr/bin/../lib/gcc/x86_64-linux-gnu/8/../../../../include/c++/8/bits/stl_algobase.h:742
#9  0x0000000000b4039a in std::fill_n<std::back_insert_iterator<opossum::PosList>, long, opossum::RowID> (__first=..., __n=1, __value=...)
    at /usr/bin/../lib/gcc/x86_64-linux-gnu/8/../../../../include/c++/8/bits/stl_algobase.h:789
#10 0x0000000000b3d104 in opossum::JoinIndex::_append_matches (this=0x3190950, range_begin=0, range_end=1, chunk_offset_left=0, chunk_id_left=..., chunk_id_right=...)
    at /home/Sven.Lehmann/hyrise/src/lib/operators/join_index.cpp:271

I did not spend time on narrowing down the problem any further yet.

[mrks]

Can't reproduce the crash with 800k rows on nemea with gcc 8.2, neither in debug, nor in release. Asan is unhappy though:

==25203==WARNING: AddressSanitizer failed to allocate 0x4a817c80000 bytes
[...]
    #6 0x7fce02b60b2a in __interceptor_malloc (/usr/lib/x86_64-linux-gnu/libasan.so.5+0xedb2a)
    #7 0x55a1da1310d8 in std::vector<opossum::RowID, boost::container::pmr::polymorphic_allocator<opossum::RowID> >::reserve(unsigned long) (/home/Markus.Dreseler/hyrise/build-release-asan/hyrisePlayground+0xe7c80d8)
    #8 0x55a1dbbdc39e in opossum::JoinIndex::_perform_join() (/home/Markus.Dreseler/hyrise/build-release-asan/hyrisePlayground+0x1027339e)
    #9 0x55a1dbbe9150 in opossum::JoinIndex::_on_execute() (/home/Markus.Dreseler/hyrise/build-release-asan/hyrisePlayground+0x10280150)
    #10 0x55a1da0d3a3a in opossum::AbstractReadOnlyOperator::_on_execute(std::shared_ptr<opossum::TransactionContext>) (/home/Markus.Dreseler/hyrise/build-release-asan/hyrisePlayground+0xe76aa3a)
    #11 0x55a1da0bdbf9 in opossum::AbstractOperator::execute() (/home/Markus.Dreseler/hyrise/build-release-asan/hyrisePlayground+0xe754bf9)
    #12 0x55a1d6b17bff in main (/home/Markus.Dreseler/hyrise/build-release-asan/hyrisePlayground+0xb1aebff)
    #13 0x7fcdffc51b96 in __libc_start_main (/lib/x86_64-linux-gnu/libc.so.6+0x21b96)
    #14 0x55a1d7ca1c19 in _start (/home/Markus.Dreseler/hyrise/build-release-asan/hyrisePlayground+0xc338c19)

[Bouncner]

Why is asan so unreliable? Your ASAN issue with the sort-merge join was only found on a Mac.

[mrks]

I would expect this to be a libstdc++ / libc++ issue.

[Bouncner]

Sven: is it reproducible and have you seen this issue with other indices as well?

[mrks]

Here is asan on a debug build:

    #14 0x561553d0a0a6 in opossum::JoinIndex::_perform_join() ../src/lib/operators/join_index.cpp:73

Mmmmmh...

71  size_t worst_case = input_table_left()->row_count() * input_table_right()->row_count();
72
73  _pos_list_left->reserve(worst_case);

[mrks]

@Bouncner: You have some experience with estimating join results. Could you come up with something that is more sane?

[Bouncner]

800,000 tuples on both sides means we reserve a worst case of 5 TB (800,000 800,000 8/1000/1000/1000) if I am not mistaken.

I'd rather vote for something like max(N, min(left_table_size, right_table_size)), assuming that each tuple of the smaller table has one single matching tuple. Just to avoid too many early reallocations, N could be something like 100.

Shall I create a PR with something like that?

[mrks]

Sounds good.

[SvenLehmann]

Sven: is it reproducible and have you seen this issue with other indices as well?

I don't think I've checked this with other indices.