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)

Reply via email to