tamnd / tamnd/firepanda

Align two series on a duplicated row label, which pandas joins rather than unions

Open
#244 0 comments 0 reactions 0 assignees View on GitHub
Dominant language
Mojo
Stars
1
Forks
0
PR merge metrics
PR metrics pending

Description

`Series([1, 2, 3], index=list('aaa')) + Series([10, 20], index=list('aa'))` is six rows in pandas. Not three, not two, and not the five that any sensible reading of "union" would give. Every left `a` meets every right `a`, so a label that appears `n` times on one side and `m` times on the other produces `n * m` rows, and the whole thing is a join wearing the word align.

`firepanda/frame/align.mojo` refuses that case today rather than guessing at it, with a message that says what pandas does and why this is not it. This issue is to implement it.

### What is actually true

Measured against a running pandas 3.0.5 rather than read out of the documentation, because the documentation for this is thin and the behaviour is surprising enough that it is worth having the numbers.

| | |
|---|---|
| `aaa` plus `aa` | 6 rows, every pairing |
| `aab` plus `ab` | 3 rows, the two `a` labels each pairing with the single right `a`, then `b` |
| two indexes that are equal, duplicates and all | aligned by position, no product, so `['a', 'a']` plus `['a', 'a']` is two rows |
| a label duplicated on one side only | `n` rows for that label, which is the product with `m` equal to one |
| the row order within a duplicated label | left order outer, right order inner |

The third row is why the refusal is narrow rather than total. Two columns of one frame have the same index object, `Index.equals` says so, and the short circuit runs before any of this is reached. So a duplicated label costs nothing at all in the common case and this issue only concerns two indexes that genuinely differ.

### Why `union` cannot be made to do it

`Index.union` from #229 takes the larger of the two counts for a repeated label, which is the right answer for a set union and the wrong answer here. Six is not the larger of three and two. There is no argument to `union` that would make it produce a product, and adding one would give the type a second meaning that no other caller wants.

So this needs a join. The pieces are: hash the labels on both sides, and for each distinct label emit the cartesian product of its left positions and its right positions, in left outer and right inner order, with a label present on one side only emitting its rows against a single missing position. That is an outer hash join keyed on the label, and firepanda already has hash join machinery for the frame level that this should reuse rather than reimplement.

The output is two position vectors and one label array, which is exactly what `align_pair` already returns, so nothing above it changes. `_reindex` gathers on the positions the same way it does now.

### Where it goes

`align_pair` in `firepanda/frame/align.mojo` currently calls `_no_duplicates` on each side and then unions. That becomes: if either side has a duplicate, take the join path; otherwise take the union path, which stays as it is because it is faster and is what almost every real call does.

The refusal message and the paragraph in the module docstring that explains it both come out when this lands.

### Done when

- [ ] Two differing indexes with a duplicate on either side align by cartesian product per label, with the row order matching pandas
- [ ] The union path is still taken when neither side has a duplicate, and the `equals` short circuit still runs first
- [ ] `tests/test_series_arith.mojo` replaces its refusal test with the measured six row case and the `aab` plus `ab` case
- [ ] The refusal message and the docstring paragraph that describes it are deleted rather than reworded
- [ ] A frame level test, since `df1 + df2` aligns rows and columns and a duplicated column name has the same rule

### What is not in this issue

`MultiIndex` alignment, which is #155. A duplicated label under a `join` call on a frame, which is its own operation with its own `how` argument and is not reached from an operator.

Part of #8, milestone M6.

Contributor guide

Open the contributing guide

Research direction

Start with align_pair in firepanda/frame/align.mojo, then inspect the existing frame-level hash join machinery and the _reindex path. Run tests/test_series_arith.mojo, including the six-row and aab-plus-ab cases, and add the requested frame-level coverage. Done means differing duplicate indexes follow pandas' cartesian row order while the equals short circuit and unique-index union path remain unchanged.

Written by the indexing model from the issue text.

Assessment

Tech stack
pandas
Domain
data-engineering
Issue type
Feature
Difficulty
4/5
Estimated time
3-5 days
Activity status
Active
Clarity
Clearly specified
Newbie friendliness
68/100

Get new issues in your inbox

A short digest of beginner-friendly GitHub issues.