You are viewing a plain text version of this content. The canonical link for it is here.
Posted to issues@arrow.apache.org by "mosalx (via GitHub)" <gi...@apache.org> on 2023/04/27 23:23:24 UTC
[GitHub] [arrow] mosalx opened a new issue, #35360: Equal scalars may have different hash values
mosalx opened a new issue, #35360:
URL: https://github.com/apache/arrow/issues/35360
### Describe the bug, including details regarding any error messages, version, and platform.
# Summary
When a pyarrow `ListArray` or `FixedSizeListArray` has a struct type, it is possible to run into a condition when two equal scalars have different hash values. It violates the contract for python hash function stating "The only required property is that objects which compare equal have the same hash value"
https://docs.python.org/3/reference/datamodel.html#object.__hash__
Below is the smallest reproducible example that demonstrates this issue. This example is for `FixedSizeListArray` but it affects `ListSizeArray` too.
# Environment
Windows 10
python=3.11.2
pyarrow=11.0.0
# Details
```python
import pyarrow as pa
# initial array
_type = pa.list_(pa.struct([('a', pa.int32())]), list_size=1)
array = pa.array([[{'a': 1}], [{'a': 1}], [{'a': 1}], None], type=_type)
# make a deep copy of the last two elements. This involves copying all array buffers
# and truncating unused bytes due to array offset. For simplicity, I am not copying all buffers
# (`field` array is not copied). This step was omitted to keep the example small
chunk = array[2:]
child = chunk.values[chunk.offset:] # StructArray
field = child.field('a') # Int32Array
# create a copy of `child`. Validity buffer could be set to None, it would not change the outcome
validity_buffer_child = pa.array([True, False, False, False, False, False, False, False]).buffers()[1]
child_copy = type(child).from_buffers(child.type, length=len(child),
buffers=[validity_buffer_child],
children=[field])
assert child_copy.equals(child)
# create a copy of `chunk` using `child_copy` made above
validity_buffer_chunk = pa.array([True, False, False, False, False, False, False, False]).buffers()[1]
chunk_copy = pa.FixedSizeListArray.from_buffers(type=chunk.type, length=len(chunk),
buffers=[validity_buffer_chunk],
children=[child_copy])
assert chunk_copy.equals(chunk)
```
Now we have two equal arrays, where the first element is valid (not-null).
Equality check for the first element passes
```python
assert chunk_copy[0] == chunk[0] # Ok
```
But their hash values are different
```python
assert hash(chunk_copy[0]) == hash(chunk[0]) # AssertionError
```
### Component(s)
Python
--
This is an automated message from the Apache Git Service.
To respond to the message, please log on to GitHub and use the
URL above to go to the specific comment.
To unsubscribe, e-mail: issues-unsubscribe@arrow.apache.org.apache.org
For queries about this service, please contact Infrastructure at:
users@infra.apache.org
[GitHub] [arrow] felipecrv commented on issue #35360: [C++] Incorrect hash value for Scalars with sliced child data (ignores offset)
Posted by "felipecrv (via GitHub)" <gi...@apache.org>.
felipecrv commented on issue #35360:
URL: https://github.com/apache/arrow/issues/35360#issuecomment-1563390727
Currently investigating this. Fix won't be trivial.
For instance, hashing the validity bitmap while considering the array offset requires some ingenuity to be made efficient as the offset doesn't always point to a byte-aligned bit.
--
This is an automated message from the Apache Git Service.
To respond to the message, please log on to GitHub and use the
URL above to go to the specific comment.
To unsubscribe, e-mail: github-unsubscribe@arrow.apache.org
For queries about this service, please contact Infrastructure at:
users@infra.apache.org
[GitHub] [arrow] felipecrv commented on issue #35360: [C++] Incorrect hash value for Scalars with sliced child data (ignores offset)
Posted by "felipecrv (via GitHub)" <gi...@apache.org>.
felipecrv commented on issue #35360:
URL: https://github.com/apache/arrow/issues/35360#issuecomment-1563397418
Is it fair to say this can only be made efficient by having some kind of Rolling Hash on the stream of bits?
https://en.wikipedia.org/wiki/Rolling_hash
--
This is an automated message from the Apache Git Service.
To respond to the message, please log on to GitHub and use the
URL above to go to the specific comment.
To unsubscribe, e-mail: github-unsubscribe@arrow.apache.org
For queries about this service, please contact Infrastructure at:
users@infra.apache.org
[GitHub] [arrow] pitrou closed issue #35360: [C++] Incorrect hash value for Scalars with sliced child data (ignores offset)
Posted by "pitrou (via GitHub)" <gi...@apache.org>.
pitrou closed issue #35360: [C++] Incorrect hash value for Scalars with sliced child data (ignores offset)
URL: https://github.com/apache/arrow/issues/35360
--
This is an automated message from the Apache Git Service.
To respond to the message, please log on to GitHub and use the
URL above to go to the specific comment.
To unsubscribe, e-mail: issues-unsubscribe@arrow.apache.org
For queries about this service, please contact Infrastructure at:
users@infra.apache.org
[GitHub] [arrow] pitrou commented on issue #35360: [C++] Incorrect hash value for Scalars with sliced child data (ignores offset)
Posted by "pitrou (via GitHub)" <gi...@apache.org>.
pitrou commented on issue #35360:
URL: https://github.com/apache/arrow/issues/35360#issuecomment-1563415123
@felipecrv Let's not overdo this. We don't need to hash everything, and the null bitmap can be ignored if it makes things simpler.
--
This is an automated message from the Apache Git Service.
To respond to the message, please log on to GitHub and use the
URL above to go to the specific comment.
To unsubscribe, e-mail: github-unsubscribe@arrow.apache.org
For queries about this service, please contact Infrastructure at:
users@infra.apache.org
[GitHub] [arrow] jorisvandenbossche commented on issue #35360: [C++] Incorrect hash value for Scalars with sliced child data (ignores offset)
Posted by "jorisvandenbossche (via GitHub)" <gi...@apache.org>.
jorisvandenbossche commented on issue #35360:
URL: https://github.com/apache/arrow/issues/35360#issuecomment-1527112161
Thanks for the report!
I can confirm this on the last development version as well, and looking into our `Scalar::Hash` implementation, it seems that when the scalar is backed by an array (as is the case for a ListArray), our hashing implementation is a bit too simple:
https://github.com/apache/arrow/blob/05a61d6fd4fee0c998ae650fa0e67881681e4a5a/cpp/src/arrow/scalar.cc#L154-L165
First, this will just loop through the child data and hash those. But I _think_ that this then doesn't take into account the correct length / offset in case your array is sliced (in which case the child data correspond to the full un-sliced data. For example, for a StructArray, getting a field does not just access the child_data, but slices the child data:
https://github.com/apache/arrow/blob/05a61d6fd4fee0c998ae650fa0e67881681e4a5a/cpp/src/arrow/array/array_nested.cc#L584-L598
Now, in addition you can also see from the first snippet we actually _only_ check the length and null count of an array, and not the values inside it ... So that means we actually ignore the content and give the same hash for different scalars:
```
In [69]: hash(pa.scalar([{'a': 1}]))
Out[69]: -285312971393311483
In [70]: hash(pa.scalar([{'a': 2}]))
Out[70]: -285312971393311483
```
--
This is an automated message from the Apache Git Service.
To respond to the message, please log on to GitHub and use the
URL above to go to the specific comment.
To unsubscribe, e-mail: github-unsubscribe@arrow.apache.org
For queries about this service, please contact Infrastructure at:
users@infra.apache.org
[GitHub] [arrow] pitrou commented on issue #35360: [C++] Incorrect hash value for Scalars with sliced child data (ignores offset)
Posted by "pitrou (via GitHub)" <gi...@apache.org>.
pitrou commented on issue #35360:
URL: https://github.com/apache/arrow/issues/35360#issuecomment-1563414383
The bug description is convoluted so here is a simpler reproducer:
```pycon
>>> a = pa.array([[{'a': 5}, {'a': 6}], [{'a': 7}, None]])
>>> b = pa.array([[{'a': 7}, None]])
>>> a[1]
<pyarrow.ListScalar: [{'a': 7}, None]>
>>> b[0]
<pyarrow.ListScalar: [{'a': 7}, None]>
>>> a[1] == b[0]
True
>>> hash(a[1]) == hash(b[0])
False
```
--
This is an automated message from the Apache Git Service.
To respond to the message, please log on to GitHub and use the
URL above to go to the specific comment.
To unsubscribe, e-mail: github-unsubscribe@arrow.apache.org
For queries about this service, please contact Infrastructure at:
users@infra.apache.org
[GitHub] [arrow] felipecrv commented on issue #35360: [C++] Incorrect hash value for Scalars with sliced child data (ignores offset)
Posted by "felipecrv (via GitHub)" <gi...@apache.org>.
felipecrv commented on issue #35360:
URL: https://github.com/apache/arrow/issues/35360#issuecomment-1567693454
Hashing anything other than the validity bitmap buffer can be super tricky as the null values can be anything within the value buffers. It would also require inference of bit widths for each type, so I maintained the hashing simple by hashing only validity buffers as it is now.
The part where I might have overdone things a bit is that I figured a way to make a hash function for bitmaps that can consider offsets. It didn't have to be a rolling hash, only involved shifts and rotations before data is fed into the hash mixing and careful handling of leading/trailing bits.
--
This is an automated message from the Apache Git Service.
To respond to the message, please log on to GitHub and use the
URL above to go to the specific comment.
To unsubscribe, e-mail: github-unsubscribe@arrow.apache.org
For queries about this service, please contact Infrastructure at:
users@infra.apache.org
[GitHub] [arrow] pitrou commented on issue #35360: [C++] Incorrect hash value for Scalars with sliced child data (ignores offset)
Posted by "pitrou (via GitHub)" <gi...@apache.org>.
pitrou commented on issue #35360:
URL: https://github.com/apache/arrow/issues/35360#issuecomment-1561556924
@felipecrv @benibus Does one of you want to take a look here?
--
This is an automated message from the Apache Git Service.
To respond to the message, please log on to GitHub and use the
URL above to go to the specific comment.
To unsubscribe, e-mail: github-unsubscribe@arrow.apache.org
For queries about this service, please contact Infrastructure at:
users@infra.apache.org