Jialiang Liang created CALCITE-7953:
---------------------------------------
Summary: RelBuilder.field(String) searches every field on each
call, so resolving many fields by name is quadratic
Key: CALCITE-7953
URL: https://issues.apache.org/jira/browse/CALCITE-7953
Project: Calcite
Issue Type: Improvement
Components: core
Reporter: Jialiang Liang
{{RelBuilder.field(String)}} finds the field with a linear search of the
input's fields:
{code:java}
final List<String> fieldNames = Pair.left(frame.fields());
int i = fieldNames.indexOf(fieldName);
{code}
So resolving many fields by name is O(n²) in the number of fields.
{{RelBuilder.fields(Iterable<String>)}} does this, as does any caller that
projects all of an input's fields by name.
It matters on wide inputs. In OpenSearch SQL (PPL on Calcite), indices with
tens of thousands of fields are common, and several commands that project every
column by name spent most of their planning time in this search, for example
about 0.9 s for one command on a 14,000-field index. We have been fixing each
call site with a name-to-ordinal map and {{field(int)}}
([#5913|https://github.com/opensearch-project/sql/pull/5913],
[#5956|https://github.com/opensearch-project/sql/pull/5956],
[#5960|https://github.com/opensearch-project/sql/pull/5960],
[#5961|https://github.com/opensearch-project/sql/pull/5961]), but any new call
site can bring it back.
Time for {{RelBuilder.fields(names)}} with every field name, over a scan of an
n-field table (best of 3, JDK 21):
||n||before||after||
|1,000|2.0 ms|0.3 ms|
|10,000|185 ms|2.0 ms|
|25,000|1,129 ms|2.5 ms|
|50,000|4,977 ms|3.5 ms|
{{RelRecordType}} already handles this for {{RelDataType.getField}}: above 20
fields it keeps a map from field name to field, keeping the first field when a
name repeats.
Proposed fix: on the first lookup, and only above the same 20-field threshold,
{{RelBuilder.Frame}} builds a map from field name to the ordinal of the first
field with that name, and {{field(int, int, String)}} uses it. The result
(first match, case-sensitive) and the error for an unknown name are unchanged,
and frames with 20 or fewer fields keep the linear search.
--
This message was sent by Atlassian Jira
(v10.3.26#10030026)