• We are using an

ItemsSketch

with K = 32768 • We are adding byte arrays to the sketch which are strings -> bytes. • Theoretically, we donot have any upper bound on N • Number of splits is generally N/3_000_000 We are downsampling the sketch. based on average element sizes. We store the the avg element size * sktech.getN() . If this crosses 300MB we downsample to the k/2.

so like if you have 90M rows in your dataset then 30 splits

What are you doing exactly?

Now I understand, I misread your bullet above. but I still don’t understand the above sentence. What are you doing when you “downsample the sketch” ?

Or are you using the downSample(newK) method with a smaller K?

If you start with a smaller K, it will speed up your processing 🙂

Since we donot know how many records will come into the system we went with the Biggest K value, and then downsampled stuff as we hit the memory limits.

Do you have large numbers of duplicate rows?

And how successful is this strategy? How much variance across the partition sizes are you getting?

Regarding duplicate rows, we cannot control that. There may or may not be duplicates

This is very very interesting.

Hmm, That is not very good. Let me think about this. Could you send me a sample of what a single row might look like that is fed to the sketch? Just one or two.

(sorry for the break, my wife called me for dinner 🙂 )

Your little distribution implies 62M rows and 4.68K partitions (like you said).

Hmmmm. How did you generate the 1B longs?

How many splits did you request?

It was similar

A few more questions, if you don’t mind. I’d like to reproduce your experiment.

Did you, by chance try feeding the longs into the DoublesSketch?

Did you configure the ItemSketch with a generic <Long>?

Also, the little distribution you show above must be a sampling of the output, because the total rows is only 36M.

I mean sampling of the resulting partitions.

1M*1+4M*261+7M*3+8M*4091+11M*1

IIRC we did not use the doubleSketch

OK, now I get 35B

Or was this real data?

This was most likely the real data.

It is getting late for me, I probably won’t get much time to spend on this until Monday.

Cheers for now,

@Gian Merlino @Vadim @Karan Kumar @Adarsh Sanjeev Here is my initial analysis of what is causing the high variance in your partition sizes. The short answer is that you are inadvertently requesting too many split points given the size of the maximum input stream and the size of the quantile sketch. In other words, the implied resolution you are requesting is very close to or smaller than the error limit of the sketch, thus causing a lot of noise and variation in the resulting partition sizes. To illustrate this I have run some simulations of what you have described to me about your use case and it comes down to these key parameters: • Input N can be as large as 37B. • Classic Quantile Sketch => ItemSketch<String> with K=2^15 • tgtPartSize: target partition size of 3M items. • Number of SplitPoints calculated by N/tgtPartSize. I first decided to model this using the Classic Quantiles DoubleSketch, as handling strings is much much slower. I felt that if I can reproduce the problem with the DoublesSketch then all I have to do is some spot measurements with the ItemSketch to eliminate anything peculiar with the ItemSketch. ( I haven’t done this last step, because what I have so far is quite convincing, I think, but I will.) My model has these parameters: • lgK ranges from 10 to 15 • inputN ranges from 1B to 39B • tgtPartSize = 2.5M items (which is a little worse than (3M). Varying these parameters produces these metrics: • NumPart: number of partitions = SplitPoints+1 • ImpRes; implied resolution = 1/numPart • hMean: average resulting partition size • hMax: maximum resulting partition size • hMin: minimum resulting partition size • hRange: hMax - hMin • hRange% = hRange/hMean *100 • Variance; the computed variance of all the partition sizes • StdDev: the computed standard deviation of all the partition sizes • StdDev/Mean%: • SkErr: the error of the sketch determined by K • Retained items: This gives a sense of the size of the sketch (in items, not bytes) (to be continued)

is that matching what you are finding as well?

This first chart confirms that as we configure the sketch with larger K, Not only does the native error of the sketch go down (green), so does the range of the variation in sizes (hRange%) of the partition reduce as well as the standard deviation of that variation (StdDev/Mean%). These two last metrics are normalized by the mean size of the partitions so we can get a sense of the impact. As you can see from the title of the chart, N=1B, and with a target partition size of 2.5M, this results in only 400 partitions. Thus, 1/400 => 2.5e-3 implied resolution (black line). The dashed curves are plotted on the right vertical axis. The key metrics of hRange% and StdDev/Mean% certainly improve with larger K.

(Continuing) Now let’s look at the next couple of plots:

The chart on the left is much more revealing. Now I’m plotting against N keeping the other parameters constant. Here N varies from 1e9 items to 39e9 items in steps of 2e9. LgK is constant at 15, the TgtPartSize is constant at 2.5e6, and since the sketch is a constant size the SkErr is constant at 8e-5. The black curve now decreases dramatically with each increase in N, where at the largest N, it actually crosses the green line and becomes less than the sketch error. This is bad news. And you can see the results in the erratic plots of the hRange% and the StdDev/Mean%. And as you can see at N=35B the variation in partition size is about 52% of the average size of the partitions! This explains the wild variations you are seeing. The StdDev/Mean% is smaller, because if you examine the Gaussian, +1 StdDev is only about 34% of the area under the curve. The second chart just confirms the underlying cause: If you always keep the target size of the resulting partitions the same size (here 2.5M items), as N increases, it demands more and more splits from the sketch, to the point where it demands more resolution from the sketch than it is designed to handle and you get very noisy results.

(Continuing) We have had quite a bit of internal discussion in our team about this and here are some of our thoughts. • Frankly, this use case has come as a bit of a surprise. When we designed these sketches, we anticipated large N, and that’s not the problem. What we didn’t anticipate was large N and large number of split-points. And this specific use-case requires values of K much larger than what we originally anticipated anyone ever needing. • We feel this needs a new sketch design specifically targeted for very large N, and very large # of split points, where K can scale much larger than 2^15. This is why we would like to huddle with you folks to understand more about your environment and your constraints. I hope you find this analysis interesting. Cheers,

@Gian Merlino I think this analysis answers your question 🙂

And then what do you do to create the partitions?

This will produce a quasi-sorted partition array, where the overall array is sorted but the values in each partition will not be sorted, but somewhat “close” together. So now my question is. Why is this quasi-sorted property important?

This is the first I have heard of this issue. Has this been reported to us as an issue on our website?

No, since we figured it was out of scope for any of the sketches you have