Skip to content

Left join doesn't preserve order of left for right missing values #37542

Closed as not planned

Description

@0x26res

Describe the bug, including details regarding any error messages, version, and platform.

I'm trying to do a left outer join (the default).

When all the keys in left can be found in right, the order of the left table is preserved:

import pyarrow as pa


left = pa.table(
    {
        "key": ["KEY_1", "KEY_3"],
        "left_value": ["1", "3"],
    }
)

right = pa.table(
    {
        "key": ["KEY_1", "KEY_3"],
        "right_value": ["1", "3"],
    }
)

But if any key from left is missing in right, the order is changed. The missing values are put at the end:

both = left.join(right, keys=["key"])
assert both["key"] == left["key"]


left = pa.table(
    {
        "key": ["KEY_1", "KEY_2", "KEY_3"],
        "left_value": ["1", "2", "3"],
    }
)

right = pa.table(
    {
        "key": ["KEY_1", "KEY_3"],
        "right_value": ["1", "3"],
    }
)


both = left.join(right, keys=["key"])
assert both["key"].to_pylist() == ["KEY_1", "KEY_3", "KEY_2"], "Should be 1,2,3"

I know there's no explicit guaranty on the order of the output data on the join, but it's weird that it preserve order when values are present, and changes it when they are missing.

Tested with pyarrow==13.0.0

Component(s)

Python

Activity

  1. zanmato1984 commented on Dec 29, 2023

    @zanmato1984
    Contributor

    This is an implementation specific behavior, i.e., depending on the underlying hash join algorithm. Currently there are two types of hash join implementation in acero, both having the similar logic. When doing left outer or full outer joins, the matched rows in the left side are first collected, by probing the hash table built from the right side. Then the unmatched rows in the left side are collected. This results in the order you observed. You can check the code below:

    For hash join (the normal algorithm), collecting the unmatched rows:

    if (join_type_ == JoinType::LEFT_OUTER || join_type_ == JoinType::FULL_OUTER) {
    for (size_t i = 0; i < no_match.size(); ++i) {
    match_left.push_back(no_match[i]);
    match_right.push_back(RowEncoder::kRowIdForNulls());
    }
    }

    For swiss join (a variation of hash join), first collecting the matched rows:

    bool no_duplicate_keys = (hash_table_->key_to_payload() == nullptr);
    bool no_payload_columns = (hash_table_->payloads() == nullptr);
    JoinMatchIterator match_iterator;
    match_iterator.SetLookupResult(
    minibatch_size_next, minibatch_start, match_bitvector_buf.mutable_data(),
    key_ids_buf.mutable_data(), no_duplicate_keys, hash_table_->key_to_payload());
    int num_matches_next;
    while (match_iterator.GetNextBatch(minibatch_size, &num_matches_next,
    materialize_batch_ids_buf.mutable_data(),
    materialize_key_ids_buf.mutable_data(),
    materialize_payload_ids_buf.mutable_data())) {
    const uint16_t* materialize_batch_ids = materialize_batch_ids_buf.mutable_data();
    const uint32_t* materialize_key_ids = materialize_key_ids_buf.mutable_data();
    const uint32_t* materialize_payload_ids =
    no_duplicate_keys || no_payload_columns
    ? materialize_key_ids_buf.mutable_data()
    : materialize_payload_ids_buf.mutable_data();
    // For right-outer, full-outer joins we need to update has-match flags
    // for the rows in hash table.
    //
    if (join_type_ == JoinType::RIGHT_OUTER || join_type_ == JoinType::FULL_OUTER) {
    hash_table_->UpdateHasMatchForKeys(thread_id, num_matches_next,
    materialize_key_ids);
    }
    // Call materialize for resulting id tuples pointing to matching pairs
    // of rows.
    //
    RETURN_NOT_OK(materialize_[thread_id]->Append(
    keypayload_batch, num_matches_next, materialize_batch_ids,
    materialize_key_ids, materialize_payload_ids, [&](ExecBatch batch) {
    return output_batch_fn_(thread_id, std::move(batch));
    }));
    }

    then collecting the unmatched rows:
    if (join_type_ == JoinType::LEFT_OUTER || join_type_ == JoinType::FULL_OUTER) {
    int num_passing_ids = 0;
    arrow::util::bit_util::bits_to_indexes(
    /*bit_to_search=*/0, hardware_flags, minibatch_size_next,
    match_bitvector_buf.mutable_data(), &num_passing_ids,
    materialize_batch_ids_buf.mutable_data());
    // Add base batch row index.
    //
    for (int i = 0; i < num_passing_ids; ++i) {
    materialize_batch_ids_buf.mutable_data()[i] +=
    static_cast<uint16_t>(minibatch_start);
    }
    RETURN_NOT_OK(materialize_[thread_id]->AppendProbeOnly(
    keypayload_batch, num_passing_ids, materialize_batch_ids_buf.mutable_data(),
    [&](ExecBatch batch) {
    return output_batch_fn_(thread_id, std::move(batch));
    }));
    }
    }

    I know there's no explicit guaranty on the order of the output data on the join, but it's weird that it preserve order when values are present, and changes it when they are missing.

    Yes, you shouldn't make any assumption of ordering in SQL except explicitly specified by order by clause. Hope the above information explains your concern.

  2. thisisnic commented on Sep 28, 2026

    @thisisnic
    Member

    Closing as appears to not be a bug

Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment

Metadata

Metadata

Assignees

No one assigned

    Type

    No type

    Projects

    No projects

      Milestone

      No milestone

      Relationships

      None yet

      Development

      No branches or pull requests

      Issue actions