I added the rationale in the commit message (not yet to the PR description), but my thinking is that 16 bytes is the minimum acceptable (so that UUIDs are inlined), and we have at least 3 bytes of padding which gives us 19 bytes. We could add more padding in order to increase inlinable space at the cost of larger allocations, but at the moment a single element is 32 bytes which seems just right to me. It's a bit unfortunate that we cannot use 8 bytes from the slice header, but reusing SliceHeader.Data field leads to issues with the GC.

Reviewable status: complete! 0 of 0 LGTMs obtained

Spicy! 🌶️ 🙂

I buy your argument about the ArrowBatchConverter regressions. Being able to Bytes.Set() seems like a big win.

Reviewable status: complete! 0 of 0 LGTMs obtained (waiting on @jordanlewis and @yuzefovich)

pkg/col/coldata/bytes.go, line 61 at r2 (raw file):

	// element was valid (namely, it'll contain a non-inlined value with an
	// empty []byte).
	nonInlined     bool

You might be able to inline this, too. (Isn't data.Data always nil when the value is inlined and non-nil when the value is pointed to?)

pkg/col/coldata/bytes.go, line 62 at r2 (raw file):

	// empty []byte).
	nonInlined     bool
	lengthOrOffset int32

If this were only used by inlined data, you could also inline it. (E.g. you could use the first inline byte for the length of inlined data.)

pkg/col/coldata/bytes.go, line 164 at r2 (raw file):

					e.data = b.buffer[e.lengthOrOffset : e.lengthOrOffset+int32(len(e.data)) : e.lengthOrOffset+int32(cap(e.data))]
				}
			}

If element.data were something like {Offset, Len, Cap} rather than {Ptr, Len, Cap} then you wouldn't need to do this update. And bonus, you might be able to use more of element for inlining. (This takes go GC out of the loop, of course, which could cause problems if we're relying on go GC to know when to free Bytes.buffer based on some element outliving its parent Bytes. But if an element never outlives its parent Bytes then it could be fine.)

pkg/col/coldata/bytes.go, line 175 at r2 (raw file):

type Bytes struct {
	// elements contains all values stored in this Bytes vector.
	elements []element

I see, you already implemented the "second layer" @msirek was talking about today with this elements slice. I wonder how much of the performance changes are due to being able to Bytes.Set() using this second layer, rather than due to inlining? The inlining seems like a small optimization on top of this more fundamental change... but maybe I'm misjudging it?

Just curious, did you happen to run any benchmarks with only the second layer, no inlining? If not, would you be willing to try some benchmarks with BytesMaxInlineLength = -1?

Thanks for the feedback! I like your suggestions, currently have a WIP to implement them, but will need to polish the code more. I'll put this PR aside for a couple of days and will likely pick it back up on Friday.

Reviewable status: complete! 0 of 0 LGTMs obtained (waiting on @jordanlewis and @yuzefovich)

I think it is RFAL. I added a separate commit to add some optimizations (kept separately for ease of reviewing). The performance regressions for Append/Copy have been reduced to an acceptable level (and there are some speedups too), here are the overall change of this PR on SortUUID and unordered distinct.

Reviewable status: complete! 0 of 0 LGTMs obtained (waiting on @jordanlewis, @michae2, and @msirek)

pkg/col/coldata/bytes.go, line 61 at r2 (raw file):

Refactored.

pkg/col/coldata/bytes.go, line 62 at r2 (raw file):

I decided to keep a single byte for inlinedLength separately to reduce the complexity.

pkg/col/coldata/bytes.go, line 164 at r2 (raw file):

Nice! This is a very good point, and I implemented your suggestion. Now we have 30 bytes of inlinable space and don't have to update pointers for non-inlined elements when Bytes.buffer is reallocated.

We could have squeezed one more byte of inlinable space by merging inlinedLength and nonInlined boolean into a single byte, but I feel like that extra complexity is not worth it. Thoughts?

pkg/col/coldata/bytes.go, line 175 at r2 (raw file):

My guess is that inlining is quite important. I'll run some benchmarks with inlining disabled next week.

Reviewable status: complete! 0 of 0 LGTMs obtained (waiting on @jordanlewis, @michae2, and @msirek)

pkg/col/coldata/bytes.go, line 175 at r2 (raw file):

Hm, the benchmarks here show that there are some improvements and some regressions without any inlining when comparing against the current tip of this PR.

I think maybe the best approach will be with no inlining, but with preallocating buffer with some fixed width (say 16 bytes for each element) right away. I'll prototype that at some point, so hold off on reviewing for now.

@michae2 PTAL.

Reviewable status: complete! 0 of 0 LGTMs obtained (waiting on @jordanlewis, @michae2, and @msirek)

pkg/col/coldata/bytes.go, line 175 at r2 (raw file):

My initial WIP had a bug where in the AppendSlice method which inflated the benchmark numbers. The updated numbers are here, and they are aligned with my expectation - the inlining is important, so I think the PR in its current form is the way to go.

Alright, done pushing, RFAL. The current benchmark numbers are here.

Reviewable status: complete! 0 of 0 LGTMs obtained (waiting on @jordanlewis, @michae2, and @msirek)

This is looking good. I'm still reading but have to pause for a bit.

Reviewed 6 of 15 files at r1, 1 of 17 files at r5, 5 of 8 files at r8.
Reviewable status: complete! 0 of 0 LGTMs obtained (waiting on @jordanlewis, @michae2, and @yuzefovich)

pkg/col/coldata/bytes.go, line 164 at r2 (raw file):

This is fine. No need to squeeze any more byte juice.

nit: But it might be nice to reverse the meaning of the inlined boolean so that the zero element was a zero-length inlined []byte rather than a zero-length []byte at offset 0 of the buffer. (Maybe you meant to do that, since you wrote nonInlined instead of inlined in your comment above?)

pkg/col/coldata/bytes.go, line 175 at r2 (raw file):

Sounds good!

pkg/col/coldata/bytes.go, line 86 at r9 (raw file):

// BytesMaxInlineLength is the maximum length of a []byte that can be inlined
// within element.
const BytesMaxInlineLength = int(ElementSize - 2)

nit: Might be a little "safer" to use unsafe.Offsetof(element.inlinedLength) instead of ElementSize - 2 in case go ever puts padding after or between the last two fields.

pkg/col/coldata/bytes.go, line 186 at r9 (raw file):

// TODO(yuzefovich): consider renaming it to Slice and allowing modification of
// "sliced" Bytes since we can now support semantics similar to Golang's slices.
func (b *Bytes) Window(start, end int) *Bytes {

Even with this PR I still don't think it is safe to modify a window, because calls to Set could cause a reallocation of Bytes.buffer. Go slices don't have this problem (assignments to index expressions will never cause a reallocation of the underlying array).

Random thought: it might be more effective for "Window" to be a separate type that is simply missing the modification methods. Then these checks would happen at compile time instead of at (test) runtime. (But that's not a suggestion for this PR; just a random thought.)

Code quote:

// TODO(yuzefovich): consider renaming it to Slice and allowing modification of
// "sliced" Bytes since we can now support semantics similar to Golang's slices.

pkg/col/coldata/bytes.go, line 304 at r9 (raw file):

		// we can set the new length accordingly (the elements will be set
		// below).
		b.zero(newLen)

Why do we zero these? If we zero them then we won't be able to reuse spots in buffer for non-inlined elements.

pkg/col/coldata/bytes.go, line 307 at r9 (raw file):

		b.elements = b.elements[:newLen]
	}
	for i := 0; i < len(srcElementsToCopy); i++ {

We might also need the reverse loop case from CopySlice when b == src && destIdx > srcStartIdx. Come to think of it, seems like AppendSlice could simply call CopySlice after ensuring the capacity of b but maybe I'm overthinking it.

pkg/sql/colexec/colexecspan/span_encoder_tmpl.go, line 127 at r9 (raw file):

func (op *_OP_STRING) next(batch coldata.Batch, startIdx, endIdx int) *coldata.Bytes {
	oldBytesSize := op.outputBytes.Size()
	if op.outputBytes == nil || op.outputBytes.Len() < endIdx-startIdx {

nit: Couldn't this check capacity instead of length? (But then I guess we would need a Cap method and a way to set the length?)

I added another cleanup commit into this PR. I could see the last two commits not passing the bar for being merged during the stability period, still personally I'd like to get them in. Curious to hear your thoughts.

Reviewable status: complete! 0 of 0 LGTMs obtained (waiting on @jordanlewis and @michae2)

pkg/col/coldata/bytes.go, line 164 at r2 (raw file):

I did reverse the meaning from nonInlined to inlined in the latest set of changes (like a couple of days ago).

pkg/col/coldata/bytes.go, line 186 at r9 (raw file):

calls to Set could cause a reallocation of Bytes.buffer

I think everything would still work, no?

Let's think through an example (imagine we have zero inlinable space):

b := NewBytes(2)
b.Set(0, []byte("zero"))
b.Set(1, []byte("one"))

At this point we have:

buffer = []byte("zeroone")
elements = []element{{offset: 0, len: 4}, {offset: 4, len: 3}}

Now we do b.Window(0, 1).Set(0, "long_string") which will cause reallocation of the buffer:

buffer = []byte("zeroonelong_string")
elements = []element{{offset: 7, len: 11}, {offset: 4, len: 3}}

We have successfully overwritten the zeroth element in the window as well as in the original vector. The only thing is that buffer[:4] is now garbage and will never be used again, unless the vector is reset.

Am I missing something?

Random thought: it might be more effective for "Window" to be a separate type that is simply missing the modification methods. Then these checks would happen at compile time instead of at (test) runtime. (But that's not a suggestion for this PR; just a random thought.)

I've thought a bit about this too previously. We could imagine having something ImmutableVec interface that doesn't include any mutation methods and making Vec interface embed ImmutableVec and add those mutation methods. This will - probably - require quite a bit of changes in the plumbing, and I thought it wasn't worth it. Additionally, it will likely come with some cost since we're performing all operations on the well-typed structs, so if we were to pull methods like Get and Set into the interface, we'd have to pay the interface dispatch cost. Alternatively, we would need to have separate well-typed structs - something like ImmutableBytes and Bytes.

OTOH we only have a handful of use cases where we're using these "windows" (like when we're spilling to disk from an in-memory operator in order to "export the buffered data"), and I believe if in those cases we actually did modify the window, then fakedist-disk logic test config would have crashed or returned incorrect results.

pkg/col/coldata/bytes.go, line 304 at r9 (raw file):

Hm. I think I wanted to maintain an invariant that all elements in b.elements[len:cap] range are uninitialized which makes Reset faster when len < cap.

Consider the following scenario with zero inlinable space:

b := NewBytes(2)
b.Set(0, "foo")
b.Set(1, "bar")
b.Set(0, "fooo")
// buffer = "foobarfooo"
// elements = {{offset: 6, len: 4}, {offset: 3, len: 3}}

// Truncate b to length 1.
b.AppendSlice(b, 1, 0, 0)
// buffer = "foobarfooo"
// elements = {{offset: 6, len: 4}, {offset: 3, len: 3}}, len(elements) = 1

// Reset with zeroing out elements only up to len(b.elements)
b.Reset()
// buffer: len = 0, cap = 10
// elements = {{}, {offset: 3, len: 3}}, len(elements) = 1

b.Set(0, "zero")
// buffer = "zero", cap = 10
// elements = {{offset: 0, len: 4}, {offset: 3, len: 3}}, len(elements) = 1

b2 := NewBytes(1)
b2.Set(0, "one")
// Here we will get corruption because b.elements[1] thinks it can reuse
// buffer[3:6], but the zeroth element uses buffer[0:4].
b.AppendSlice(b2, 1 /* destIdx */, 0 /* startIdx */, 1 /* endIdx */)

If this is right, then we either have to zero out all elements after newLen in AppendSlice or to zero out all elements up to cap(b.elements) in Reset.

Update: this is, indeed, a problem, and I converted this snippet into a unit test. I also decided to switch to zeroing out elements up to the capacity in Reset.

pkg/col/coldata/bytes.go, line 307 at r9 (raw file):
AppendSlice from the vector into itself is only allowed when srcStartIdx == srcEndIdx in which case there is no overlap, so we don't have to be too smart about it. This is why I opened #76529 some time ago.

Come to think of it, seems like AppendSlice could simply call CopySlice after ensuring the capacity of b

That's a nice observation - I factored out a common helper method using the same optimization as we had in the append case. I also added some BCEs, and the benchmarks have improved for CopySlice.

pkg/sql/colexec/colexecspan/span_encoder_tmpl.go, line 127 at r9 (raw file):

Given that we're now using Sets in this file, checking the length is the right thing to do - Sets are only allowed in [0, len] range.

Nice work!

I think it would be fine to merge the last two commits.

Reviewed 1 of 15 files at r1, 2 of 8 files at r8, 8 of 8 files at r13, 5 of 5 files at r14, 2 of 2 files at r15, 3 of 3 files at r16, 17 of 17 files at r17, all commit messages.
Reviewable status: complete! 1 of 0 LGTMs obtained (waiting on @jordanlewis and @yuzefovich)

pkg/col/coldata/bytes.go, line 186 at r9 (raw file):

Splitting this b.Window(0, 1).Set(0, "long_string") out into:

c := b.Window(0, 1)
c.Set(0, "long_string")

Won't the call to c.Set assign the reallocated buffer to c.buffer but not b.buffer?

Anyway, I'm not requesting any changes to the code 😆 just agreeing with the current immutableness of Window.

pkg/col/coldata/bytes.go, line 304 at r9 (raw file):

Interesting! Thank you for the example, I wasn't thinking about Reset at all (or using AppendSlice for truncation, ha). Zeroing up to capacity in Reset makes sense to me.

pkg/col/coldata/bytes.go, line 137 at r14 (raw file):

	// Check if we there was an old non-inlined value we can overwrite.
	if !e.inlined && e.header.cap >= len(v) {
		copy(e.getNonInlined(b)[:len(v)], v)

nit: If element.getNonInlined took a length argument then we wouldn't need the [:len(v)] expression here. But maybe that's too finicky.

Thanks for the reviews and the feedback!

bors r+

Reviewable status: complete! 0 of 0 LGTMs obtained (and 1 stale) (waiting on @jordanlewis and @michae2)

pkg/col/coldata/bytes.go, line 186 at r9 (raw file):

Oh, indeed. Removed the TODO.

pkg/col/coldata/bytes.go, line 137 at r14 (raw file):

I refactored the code a bit to remove this.

Reviewable status: complete! 0 of 0 LGTMs obtained (and 1 stale)

pkg/col/coldata/bytes.go, line 77 at r18 (raw file):

I thought about it and chose to keep using int.

Everything will still work correctly on 32-bit systems, we'll just have less inlinable space (18 bytes instead of 30) and we won't be using the whole size of the object in the Golang's size class (element will take up 20 bytes, and it'll be in 24 byte object class, so we could have used 4 bytes for more padding; alternatively, we could have used less padding to get into 16 byte class).

I think that 32-bit systems are quite rare nowadays, and we usually just assume that we're running on a 64-bit system.