Aggregation operators Time Complexity

Working with Data
,
#1

Hello

Is there somewhere information of the Complexity of array/set/object operators? or how they work internally?

I am doing some benchmarks and i get some not expected results.

For example i have an array of integers and i reduce that array to itself
doing nothing just re-construct the array using reduce and $concatArrays
Everytime i do {$concatArrays $$newArray [anumber] }
Thought it would be similar with Java’s ArrayList that is O(1) with dynamic array but its not.
There is no $push(works only in $group the one we have) in aggregation framework so i used $concatArrays

Adding one member each time is so slow,unusable for large arrays
($concatArrays is super fast if arrays are big,but one by one adding is so slow)
For 200000 members it takes 240sec
For 100000 members it takes 23sec
For 50000 members it takes 6 sec
For 10000 members 168.411066 msec

How to add an element to an array to the end or in specific location?
Is it possible without $concatArrays which is slow for repeated calls?

Also mongoDB offers set operators without sets but on arrays,
Everytime i do one set operation i should think it as array->set->array
If i have a reduce that does set operations on an array at every step all array will become set
and then back to array? Or will remain set(internally)?
If its not kept internally as set it will be very slow to repeat many set operations on an array.

Thank you

#2

The one thing that I suspect is that by growing the array it has to be moved to other blocks on disk over and over again.

Order 1 is true when the array slots are allocated ahead of time. Otherwise the same issue about moving the array to other blocks occurs. But moving blocks in RAM is not as perceptible to us human, but disk is.

I think that allocating the array ahead of time should work for MongoDB too.

#3

Maybe for each call of $concatArrays there is new array allocation
I thought it would be like dynamic array,add with O(1) and when allocate ,allocate extra space.
But even if i preallocate i cant add at specific position of an array,what aggregation operator
to use?I only know $concatArrays ($push is only for groups)

In general its useful to know the complexity of array/set/object operators,and how they work internally if possible.

#4

I cannot test right now, but I am pretty and update with

{ $set : { "Path.To.Array.Index" : ValueOrObject } }

should work.

Agree. Hopefully someone with that knowledge can shed a light on the topic.

#5

I dont think this works on aggregation at aggregation $arrayElemAt only works i think and only to read not to set.Also the index will come from a variable if reducing.
If we find a way to add to array at end or at specific position without $concatArrays , would be helpful