lidavidm commented on code in PR #14111: URL: https://github.com/apache/arrow/pull/14111#discussion_r1073528175
########## go/arrow/encoded/ree_utils.go: ########## @@ -0,0 +1,202 @@ +// Licensed to the Apache Software Foundation (ASF) under one +// or more contributor license agreements. See the NOTICE file +// distributed with this work for additional information +// regarding copyright ownership. The ASF licenses this file +// to you under the Apache License, Version 2.0 (the +// "License"); you may not use this file except in compliance +// with the License. You may obtain a copy of the License at +// +// http://www.apache.org/licenses/LICENSE-2.0 +// +// Unless required by applicable law or agreed to in writing, software +// distributed under the License is distributed on an "AS IS" BASIS, +// WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied. +// See the License for the specific language governing permissions and +// limitations under the License. + +package encoded + +import ( + "math" + "sort" + + "github.com/apache/arrow/go/v11/arrow" +) + +// FindPhysicalOffset performs a binary search on the run-ends to return +// the appropriate physical offset into the values/run-ends that corresponds +// with the logical offset defined in the array. +// +// For example, an array with run-ends [10, 20, 30, 40, 50] and a logical +// offset of 25 will return the value 2. This returns the smallest offset +// whose run-end is greater than the logical offset, which would also be the +// offset index into the values that contains the correct value. +// +// This function assumes it receives Run End Encoded array data +func FindPhysicalOffset(arr arrow.ArrayData) int { + data := arr.Children()[0] + logicalOffset := arr.Offset() + + switch data.DataType().ID() { + case arrow.INT16: + runEnds := arrow.Int16Traits.CastFromBytes(data.Buffers()[1].Bytes()) + runEnds = runEnds[data.Offset() : data.Offset()+data.Len()] + return sort.Search(len(runEnds), func(i int) bool { return runEnds[i] > int16(logicalOffset) }) Review Comment: Hmm. Should we explicitly check for overflow? I suppose that's better left to a validation function (to ensure the array length isn't inconsistent). I suppose more interestingly, a REE array with 16-bit run ends can only store 32767 elements. -- 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: [email protected] For queries about this service, please contact Infrastructure at: [email protected]
