apache / apache/arrow

[C++] Substrait serialised expression size increases exponentially due to extension URIs being repeated

Open
#48,761 3 comments 0 reactions 1 assignee Claimed by @mohit7705 View on GitHub
Component: C++ Type: bug
Dominant language
C++
Stars
17.1k
Forks
4.3k
Avg merge
3d 13h
Merged PRs (30d)
88

Description

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

When serialising pyarrow expressions using substrait, the size of the serialised buffer increases exponentially with the number of binary operation clauses in the expression due to extension URIs being repeated again for each nested expression.

Testing with pyarrow 21.0.0:
```
================================================================================
Testing with 1 OR condition(s)
================================================================================
Expression: (int_col == 1)
Substrait size: 201 bytes
Total extension URIs: 1

================================================================================
Testing with 2 OR condition(s)
================================================================================
Expression: ((int_col == 1) or (int_col == 2))
Substrait size: 634 bytes
Total extension URIs: 5

================================================================================
Testing with 4 OR condition(s)
================================================================================
Expression: ((((int_col == 1) or (int_col == 2)) or (int_col == 3)) or (int_col == 4))
Substrait size: 2967 bytes
Total extension URIs: 29

================================================================================
Testing with 6 OR condition(s)
================================================================================
Expression: ((((((int_col == 1) or (int_col == 2)) or (int_col == 3)) or (int_col == 4)) or (int_col == 5)) or (int_col == 6))
Substrait size: 12017 bytes
Total extension URIs: 125

================================================================================
Testing with 8 OR condition(s)
================================================================================
Expression: ((((((((int_col == 1) or (int_col == 2)) or (int_col == 3)) or (int_col == 4)) or (int_col == 5)) or (int_col == 6)) or (int_col == 7)) or (int_col == 8))
Substrait size: 48306 bytes
Total extension URIs: 509

================================================================================
Testing with 10 OR condition(s)
================================================================================
Expression: ((((((((((int_col == 1) or (int_col == 2)) or (int_col == 3)) or (int_col == 4)) or (int_col == 5)) or (int_col == 6)) or (int_col == 7)) or (int_col == 8)) or (int_col == 9)) or (int_col == 10))
Substrait size: 193172 bytes
Total extension URIs: 2045

================================================================================
Testing with 12 OR condition(s)
================================================================================
Expression: ((((((((((((int_col == 1) or (int_col == 2)) or (int_col == 3)) or (int_col == 4)) or (int_col == 5)) or (int_col == 6)) or (int_col == 7)) or (int_col == 8)) or (int_col == 9)) or (int_col == 10)) or (int_col == 11)) or (int_col == 12))
Substrait size: 772342 bytes
Total extension URIs: 8189

================================================================================
Testing with 14 OR condition(s)
================================================================================
Expression: ((((((((((((((int_col == 1) or (int_col == 2)) or (int_col == 3)) or (int_col == 4)) or (int_col == 5)) or (int_col == 6)) or (int_col == 7)) or (int_col == 8)) or (int_col == 9)) or (int_col == 10)) or (int_col == 11)) or (int_col == 12)) or (int_col == 13)) or (int_col == 14))
Substrait size: 3105111 bytes
Total extension URIs: 32765

================================================================================
Summary:
================================================================================
OR Conditions | Size (bytes) | Size (KB) | Extension URIs
----------------------------------------------------------------------
1 | 201 | 0.20 | 1
2 | 634 | 0.62 | 5
4 | 2,967 | 2.90 | 29
6 | 12,017 | 11.74 | 125
8 | 48,306 | 47.17 | 509
10 | 193,172 | 188.64 | 2045
12 | 772,342 | 754.24 | 8189
14 | 3,105,111 | 3032.33 | 32765
```

Serialization was done by simply: `buf = pyarrow.substrait.serialize_expressions([expr], ["result"], schema)`

Unfortunately, it might not be possible to just use `is_in` in the expression for my use-case so that might not be a possible workaround.

Would be nice to know if I am somehow misusing the API which is causing this. Thanks!

cc: @westonpace

### Component(s)

C++

Contributor guide

Open the contributing guide

Assessment

This issue has not been assessed yet.

Get new issues in your inbox

A short digest of beginner-friendly GitHub issues.