wehub-resource-sync
498b235461
Build and test / Build and test AMD64 Ubuntu 22.04 (push) Failing after 0s
Publish Builder / amazonlinux2023 (push) Failing after 1s
Build and test / UT for Go (push) Has been skipped
Publish KRTE Images / KRTE (push) Failing after 1s
Build and test / Integration Test (push) Has been skipped
Build and test / Upload Code Coverage (push) Has been skipped
Publish Builder / rockylinux9 (push) Failing after 1s
Publish Builder / ubuntu22.04 (push) Failing after 0s
Publish Builder / ubuntu24.04 (push) Failing after 0s
Publish Gpu Builder / publish-gpu-builder (push) Failing after 1s
Publish Test Images / PyTest (push) Failing after 0s
Build and test / UT for Cpp (push) Has been cancelled
382 lines
12 KiB
Go
382 lines
12 KiB
Go
// Licensed to the LF AI & Data foundation 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 storage
|
|
|
|
import (
|
|
"fmt"
|
|
"io"
|
|
"math"
|
|
"testing"
|
|
|
|
"github.com/apache/arrow/go/v17/arrow"
|
|
"github.com/apache/arrow/go/v17/arrow/array"
|
|
"github.com/apache/arrow/go/v17/arrow/memory"
|
|
"github.com/bytedance/mockey"
|
|
"github.com/stretchr/testify/assert"
|
|
|
|
"github.com/milvus-io/milvus-proto/go-api/v3/schemapb"
|
|
"github.com/milvus-io/milvus/pkg/v3/common"
|
|
)
|
|
|
|
type oneShotRecordReader struct {
|
|
rec Record
|
|
done bool
|
|
}
|
|
|
|
func (r *oneShotRecordReader) Next() (Record, error) {
|
|
if r.done {
|
|
return nil, io.EOF
|
|
}
|
|
r.done = true
|
|
return r.rec, nil
|
|
}
|
|
|
|
func (r *oneShotRecordReader) Close() error {
|
|
return nil
|
|
}
|
|
|
|
func TestRadixSortByInt64(t *testing.T) {
|
|
t.Run("edge values across records", func(t *testing.T) {
|
|
// Keys laid out across 3 records, mixing negatives, zero, duplicates and
|
|
// the int64 bounds to exercise the sign-bit flip and every byte position.
|
|
keys := [][]int64{
|
|
{5, math.MaxInt64, -1},
|
|
{0, math.MinInt64, -1},
|
|
{42, 5},
|
|
}
|
|
var indices []rowIndex
|
|
for ri := range keys {
|
|
for i := range keys[ri] {
|
|
indices = append(indices, rowIndex{int32(ri), int32(i)})
|
|
}
|
|
}
|
|
|
|
radixSortByInt64(indices, keys)
|
|
|
|
got := make([]int64, len(indices))
|
|
for k, idx := range indices {
|
|
got[k] = keys[idx.ri][idx.i]
|
|
}
|
|
assert.Equal(t, []int64{math.MinInt64, -1, -1, 0, 5, 5, 42, math.MaxInt64}, got)
|
|
})
|
|
|
|
t.Run("stable for equal keys", func(t *testing.T) {
|
|
// Three rows share key 7 ({0,0},{1,0},{1,1} in input order); a stable sort
|
|
// must keep that relative order among the duplicates.
|
|
keys := [][]int64{
|
|
{7, 3},
|
|
{7, 7, 1},
|
|
}
|
|
indices := []rowIndex{{0, 0}, {0, 1}, {1, 0}, {1, 1}, {1, 2}}
|
|
|
|
radixSortByInt64(indices, keys)
|
|
|
|
assert.Equal(t, []rowIndex{{1, 2}, {0, 1}, {0, 0}, {1, 0}, {1, 1}}, indices)
|
|
})
|
|
|
|
t.Run("small inputs are no-ops", func(t *testing.T) {
|
|
single := []rowIndex{{0, 0}}
|
|
radixSortByInt64(single, [][]int64{{99}})
|
|
assert.Equal(t, []rowIndex{{0, 0}}, single)
|
|
|
|
assert.NotPanics(t, func() { radixSortByInt64(nil, nil) })
|
|
})
|
|
}
|
|
|
|
func TestSort(t *testing.T) {
|
|
const batchSize = 64 * 1024 * 1024
|
|
|
|
getReaders := func() []RecordReader {
|
|
blobs, err := generateTestDataWithSeed(10, 3)
|
|
assert.NoError(t, err)
|
|
reader10 := newIterativeCompositeBinlogRecordReader(generateTestSchema(), nil, MakeBlobsReader(blobs))
|
|
blobs, err = generateTestDataWithSeed(20, 3)
|
|
assert.NoError(t, err)
|
|
reader20 := newIterativeCompositeBinlogRecordReader(generateTestSchema(), nil, MakeBlobsReader(blobs))
|
|
rr := []RecordReader{reader20, reader10}
|
|
return rr
|
|
}
|
|
|
|
lastPK := int64(-1)
|
|
rw := &MockRecordWriter{
|
|
writefn: func(r Record) error {
|
|
pk := r.Column(common.RowIDField).(*array.Int64).Value(0)
|
|
assert.Greater(t, pk, lastPK)
|
|
lastPK = pk
|
|
return nil
|
|
},
|
|
|
|
closefn: func() error {
|
|
lastPK = int64(-1)
|
|
return nil
|
|
},
|
|
}
|
|
|
|
t.Run("sort", func(t *testing.T) {
|
|
gotNumRows, timings, err := Sort(batchSize, generateTestSchema(), getReaders(), rw, func(r Record, ri, i int) bool {
|
|
return true
|
|
}, []int64{common.RowIDField})
|
|
assert.NoError(t, err)
|
|
assert.Equal(t, 6, gotNumRows)
|
|
assert.NotNil(t, timings)
|
|
assert.Equal(t, 6, timings.NumRows)
|
|
assert.Greater(t, timings.NumBatches, 0)
|
|
assert.GreaterOrEqual(t, timings.ReadCost.Nanoseconds(), int64(0))
|
|
assert.GreaterOrEqual(t, timings.SortCost.Nanoseconds(), int64(0))
|
|
assert.GreaterOrEqual(t, timings.WriteCost.Nanoseconds(), int64(0))
|
|
err = rw.Close()
|
|
assert.NoError(t, err)
|
|
})
|
|
|
|
t.Run("sort with predicate", func(t *testing.T) {
|
|
gotNumRows, timings, err := Sort(batchSize, generateTestSchema(), getReaders(), rw, func(r Record, ri, i int) bool {
|
|
pk := r.Column(common.RowIDField).(*array.Int64).Value(i)
|
|
return pk >= 20
|
|
}, []int64{common.RowIDField})
|
|
assert.NoError(t, err)
|
|
assert.Equal(t, 3, gotNumRows)
|
|
assert.NotNil(t, timings)
|
|
assert.Equal(t, 3, timings.NumRows)
|
|
err = rw.Close()
|
|
assert.NoError(t, err)
|
|
})
|
|
|
|
t.Run("sort empty readers", func(t *testing.T) {
|
|
gotNumRows, timings, err := Sort(batchSize, generateTestSchema(), []RecordReader{}, rw, func(r Record, ri, i int) bool {
|
|
return true
|
|
}, []int64{common.RowIDField})
|
|
assert.NoError(t, err)
|
|
assert.Equal(t, 0, gotNumRows)
|
|
assert.NotNil(t, timings)
|
|
assert.GreaterOrEqual(t, timings.ReadCost.Nanoseconds(), int64(0))
|
|
})
|
|
|
|
t.Run("sort with reader error", func(t *testing.T) {
|
|
mockNext := mockey.Mock((*IterativeRecordReader).Next).Return(nil, fmt.Errorf("read error")).Build()
|
|
defer mockNext.UnPatch()
|
|
errReader := &IterativeRecordReader{}
|
|
gotNumRows, timings, err := Sort(batchSize, generateTestSchema(), []RecordReader{errReader}, rw, func(r Record, ri, i int) bool {
|
|
return true
|
|
}, []int64{common.RowIDField})
|
|
assert.Error(t, err)
|
|
assert.Equal(t, 0, gotNumRows)
|
|
assert.Nil(t, timings)
|
|
})
|
|
|
|
t.Run("sort with batch write error", func(t *testing.T) {
|
|
errWriter := &MockRecordWriter{
|
|
writefn: func(r Record) error {
|
|
return fmt.Errorf("write error")
|
|
},
|
|
closefn: func() error {
|
|
return nil
|
|
},
|
|
}
|
|
// Use small batchSize to trigger mid-loop batch write error (line 157)
|
|
gotNumRows, timings, err := Sort(1, generateTestSchema(), getReaders(), errWriter, func(r Record, ri, i int) bool {
|
|
return true
|
|
}, []int64{common.RowIDField})
|
|
assert.Error(t, err)
|
|
assert.Equal(t, 0, gotNumRows)
|
|
assert.Nil(t, timings)
|
|
})
|
|
|
|
t.Run("sort with final write error", func(t *testing.T) {
|
|
errWriter := &MockRecordWriter{
|
|
writefn: func(r Record) error {
|
|
// Fail on the first write (which is the final batch write when batchSize is large)
|
|
return fmt.Errorf("write error")
|
|
},
|
|
closefn: func() error {
|
|
return nil
|
|
},
|
|
}
|
|
// Use large batchSize so data doesn't trigger mid-loop write, only the final batch write (line 164)
|
|
gotNumRows, timings, err := Sort(batchSize, generateTestSchema(), getReaders(), errWriter, func(r Record, ri, i int) bool {
|
|
return true
|
|
}, []int64{common.RowIDField})
|
|
assert.Error(t, err)
|
|
assert.Equal(t, 0, gotNumRows)
|
|
assert.Nil(t, timings)
|
|
})
|
|
}
|
|
|
|
func TestMergeSort(t *testing.T) {
|
|
getReaders := func() []RecordReader {
|
|
blobs, err := generateTestDataWithSeed(1000, 5000)
|
|
assert.NoError(t, err)
|
|
reader10 := newIterativeCompositeBinlogRecordReader(generateTestSchema(), nil, MakeBlobsReader(blobs))
|
|
blobs, err = generateTestDataWithSeed(4000, 5000)
|
|
assert.NoError(t, err)
|
|
reader20 := newIterativeCompositeBinlogRecordReader(generateTestSchema(), nil, MakeBlobsReader(blobs))
|
|
rr := []RecordReader{reader20, reader10}
|
|
return rr
|
|
}
|
|
|
|
lastPK := int64(-1)
|
|
rw := &MockRecordWriter{
|
|
writefn: func(r Record) error {
|
|
pk := r.Column(common.RowIDField).(*array.Int64).Value(0)
|
|
assert.Greater(t, pk, lastPK)
|
|
lastPK = pk
|
|
return nil
|
|
},
|
|
|
|
closefn: func() error {
|
|
lastPK = int64(-1)
|
|
return nil
|
|
},
|
|
}
|
|
|
|
const batchSize = 64 * 1024 * 1024
|
|
|
|
t.Run("merge sort", func(t *testing.T) {
|
|
gotNumRows, err := MergeSort(batchSize, generateTestSchema(), getReaders(), rw, func(r Record, ri, i int) bool {
|
|
return true
|
|
}, []int64{common.RowIDField})
|
|
assert.NoError(t, err)
|
|
assert.Equal(t, 10000, gotNumRows)
|
|
err = rw.Close()
|
|
assert.NoError(t, err)
|
|
})
|
|
|
|
t.Run("merge sort with predicate", func(t *testing.T) {
|
|
gotNumRows, err := MergeSort(batchSize, generateTestSchema(), getReaders(), rw, func(r Record, ri, i int) bool {
|
|
pk := r.Column(common.RowIDField).(*array.Int64).Value(i)
|
|
// cover a single record (1024 rows) that is deleted, or the last data in the record is deleted
|
|
// index 1023 is deleted. records (1024-2048) and (5000-6023) are all deleted
|
|
return pk < 2000 || (pk >= 3050 && pk < 5000) || pk >= 7000
|
|
}, []int64{common.RowIDField})
|
|
assert.NoError(t, err)
|
|
assert.Equal(t, 5950, gotNumRows)
|
|
err = rw.Close()
|
|
assert.NoError(t, err)
|
|
})
|
|
}
|
|
|
|
func TestMergeSortReturnsRecordBuilderAppendError(t *testing.T) {
|
|
textBuilder := array.NewStringBuilder(memory.DefaultAllocator)
|
|
textBuilder.Append("not-a-lob-ref")
|
|
textColumn := textBuilder.NewArray()
|
|
defer textColumn.Release()
|
|
textBuilder.Release()
|
|
|
|
pkBuilder := array.NewInt64Builder(memory.DefaultAllocator)
|
|
pkBuilder.Append(1)
|
|
pkColumn := pkBuilder.NewArray()
|
|
defer pkColumn.Release()
|
|
pkBuilder.Release()
|
|
|
|
rec := NewSimpleArrowRecord(array.NewRecord(
|
|
arrow.NewSchema([]arrow.Field{
|
|
{Name: "pk", Type: arrow.PrimitiveTypes.Int64},
|
|
{Name: "text", Type: arrow.BinaryTypes.String},
|
|
}, nil),
|
|
[]arrow.Array{pkColumn, textColumn},
|
|
1,
|
|
), map[FieldID]int{100: 0, 101: 1})
|
|
defer rec.Release()
|
|
|
|
reader := &oneShotRecordReader{rec: rec}
|
|
writer := &MockRecordWriter{
|
|
writefn: func(r Record) error {
|
|
return nil
|
|
},
|
|
closefn: func() error {
|
|
return nil
|
|
},
|
|
}
|
|
schema := &schemapb.CollectionSchema{Fields: []*schemapb.FieldSchema{
|
|
{FieldID: 100, Name: "pk", DataType: schemapb.DataType_Int64, IsPrimaryKey: true},
|
|
{FieldID: 101, Name: "text", DataType: schemapb.DataType_Text},
|
|
}}
|
|
|
|
_, err := MergeSort(1024, schema, []RecordReader{reader}, writer, func(r Record, ri, i int) bool {
|
|
return true
|
|
}, []int64{100})
|
|
assert.ErrorContains(t, err, "failed to append value")
|
|
}
|
|
|
|
// Benchmark sort
|
|
func BenchmarkSort(b *testing.B) {
|
|
batch := 500000
|
|
blobs, err := generateTestDataWithSeed(batch, batch)
|
|
assert.NoError(b, err)
|
|
reader10 := newIterativeCompositeBinlogRecordReader(generateTestSchema(), nil, MakeBlobsReader(blobs))
|
|
blobs, err = generateTestDataWithSeed(batch*2+1, batch)
|
|
assert.NoError(b, err)
|
|
reader20 := newIterativeCompositeBinlogRecordReader(generateTestSchema(), nil, MakeBlobsReader(blobs))
|
|
rr := []RecordReader{reader20, reader10}
|
|
|
|
rw := &MockRecordWriter{
|
|
writefn: func(r Record) error {
|
|
return nil
|
|
},
|
|
|
|
closefn: func() error {
|
|
return nil
|
|
},
|
|
}
|
|
|
|
const batchSize = 64 * 1024 * 1024
|
|
b.ResetTimer()
|
|
|
|
b.Run("sort", func(b *testing.B) {
|
|
for i := 0; i < b.N; i++ {
|
|
Sort(batchSize, generateTestSchema(), rr, rw, func(r Record, ri, i int) bool {
|
|
return true
|
|
}, []int64{common.RowIDField})
|
|
}
|
|
})
|
|
}
|
|
|
|
func TestSortByMoreThanOneField(t *testing.T) {
|
|
const batchSize = 10000
|
|
sortByFieldIDs := []int64{common.RowIDField, common.TimeStampField}
|
|
|
|
blobs, err := generateTestDataWithSeed(10, batchSize)
|
|
assert.NoError(t, err)
|
|
reader10 := newIterativeCompositeBinlogRecordReader(generateTestSchema(), nil, MakeBlobsReader(blobs))
|
|
blobs, err = generateTestDataWithSeed(20, batchSize)
|
|
assert.NoError(t, err)
|
|
reader20 := newIterativeCompositeBinlogRecordReader(generateTestSchema(), nil, MakeBlobsReader(blobs))
|
|
rr := []RecordReader{reader20, reader10}
|
|
|
|
lastPK := int64(-1)
|
|
lastTS := int64(-1)
|
|
rw := &MockRecordWriter{
|
|
writefn: func(r Record) error {
|
|
pk := r.Column(common.RowIDField).(*array.Int64).Value(0)
|
|
ts := r.Column(common.TimeStampField).(*array.Int64).Value(0)
|
|
assert.True(t, pk > lastPK || (pk == lastPK && ts > lastTS))
|
|
lastPK = pk
|
|
return nil
|
|
},
|
|
|
|
closefn: func() error {
|
|
lastPK = int64(-1)
|
|
return nil
|
|
},
|
|
}
|
|
gotNumRows, _, err := Sort(batchSize, generateTestSchema(), rr, rw, func(r Record, ri, i int) bool {
|
|
return true
|
|
}, sortByFieldIDs)
|
|
assert.NoError(t, err)
|
|
assert.Equal(t, batchSize*2, gotNumRows)
|
|
assert.NoError(t, rw.Close())
|
|
}
|