kwillets

Snowflake perplexes me. From what I can see of my own org it's a data tool with a database behind it that you can't swap out for another or run on your own cloud account.

A Bloom filter with 1% FPR would fit in 285 MB and need 7 accesses per key.

That's hilarious -- I worked on Zynga's analytics system in the early days, and we made it (hopefully) very easy to instrument code and get up and running. We created patient zero I guess.

This question is becoming critical right now, as nonrecoverable deletes are required within 30 days for both GDPR and CCPA.

Most products do the asynchronous rewrite, especially if they're based on immutable storage. That's fine, but it should be tested to verify that it's not triggering on every delete, for example, and that it's resource-efficient.

I did the work that Lemire links there.

It started with realizing that Lemire's rejection method becomes more likely to need a division/modulo as the range maxes out (the gate on division is fraction < range, so as range -> maxint the division case approaches 100%, if the fraction and range have the same precision). If the range is 32 bit but the fraction is 64, the division case is 2^32 times less likely, so I worked out Lemire's method for 32.64 fixed point.

That turned out to be similar to the infinite-precision case described here, as we only need 32 bits of fraction if it's far enough from the edges, ie nothing can carry into the integer part if we extend to 64.

Once I worked out when to extend to 64 bits in the rejection method, I realized that the infinite-precision case is similar, using a loop instead of a conditional. It's simpler since there's no rejection, just a decision to continue as long as it's possible to carry.

This may save random bits, which are generally more costly than the range reduction.

I see, this is one of several posts on this topic. There is a link near the end to the unbiased method, which is more original, but as you note fixed-point multiplication is not new.

What is new here is the method to remove bias.

It's easier when there are more bits available than in the original operand.

For 64, a variable shift may work. Powers of 10 have a lot of trailing 0 bits.

Originally I used a macro:

// this increments the upper 32 bits (log10 T - 1) when >= T is added

#define K(T) (((sizeof(#T)-1)<<32) - T)

(T is 10,100, etc.)

Snowflake tries to auto-sort its containers to fit the query pattern; most of these platforms use at least one data ordering. Vertica allows multiple projections on a table with different orderings and distribution keys.

On top of that BRIN (block range) indexes are usually used to capture the value of sorting by pruning I/O. I don't see these mentioned here -- they seem like a good open-source version of this idea.

Generate a temp table with a sufficient number of random values and join. Add an ORDER BY RANDOM() to those results to subsample.

Another approach would be to create a table with a small sample of the main one and refresh it periodically -- each query just needs to do a random reordering on the small sample, and the results will be truly random over time.

You're not from here, are you?

That confused me as well -- where I work we have a legal dept. approval for IP issues, and that's it. Academic review doesn't make sense in that context or time frame.

SF has had generations of this type of politician. I can't count the number of times I've seen the phrase "fighting for real change". Finally on Preston's flyer I tore the "for" out.

The city requires housing producers to sell a percentage of their output to low-income buyers at a government-set price. So middle-class housing buyers pay significantly more to cover that cost.

The government has an exclusive right to run mass transit?

Me three. HP just gave me a bad feeling.

There have apparently been some injection attacks where an overlength ";" or something has been missed by a string sanitizer. Overlength means eg a 7-bit ASCII character is encoded in two or more bytes, neither of which would be noticed by an 8-bit delimiter checker. The only flag in this case is that bitfields in the two bytes have 0's in the high bits beyond 7.

Drug overdoses are far ahead of CoVid.

Just learning the words sounds great until you find out that Korean is agglutinative, and Koreans don't even agree on where the word boundaries are.

What features are you looking for? Wifi range/bandwidth? Security? Advanced routing?

I upgraded my range by adding a couple of Unifi AP's to my existing ISP router. It was less of a commitment than a UDM, and I originally just set them up in standalone mode with no account or cloud presence.

It might be worth it. There are already programs to collect biomass, but not much is done with it.

They should do what my employer does: give everybody 16 hours per day to discuss politics, religion, or any other topic.

One thought on timing is that, when generating a whole batch of numbers, it makes sense to calculate the modulo exactly once in advance rather than on-demand.

You are correct; it's a transformation from an RNG to a range. I have a version (actually 3 versions) that works with std::random here: https://github.com/KWillets/range_generator . That framework is a bit more explicit about the distinction between RNG's and distributions (eg uniform within a range).

see also: Malthus.

That's an interesting look at their internals; I wasn't aware of their dynamic sorting feature.

At read time, though, Snowflake's zone map is the same as Redshift's and Vertica's; you'll see similar pruning for many queries.

Redshift however doesn't prune during joins, which is a huge deficiency.

Snowflake looks more flexible about getting the data into its final ordering.

SQL Server had too much political pull within the org for such a deal to succeed.

Oops, I started on an entry for this, and then went off with some new variants on the algo and forgot my original goal.

But I did make it fairly readable:

    FixedPoint<uint32_t> x;
    do {
      x.setFraction(src());
      x *= range;
    } while(isRejectedValue(x.fraction()));

    return x.floor();

Basically all the weird casts and things in Lemire are parts of 32.32 fixed point arithmetic; we stuff a random value into the .32 part to make a number in [0,1) and multiply. The rejection condition is a bit of modular arithmetic but not super hard.

https://github.com/KWillets/range_generator/blob/59ffea502c4...

I added another method where it doesn't reject but extends right (variable-precision) until it's certain of the exact answer (ie that the floor() cannot change). I believe the Ryu printf algorithm does something similar to get the requested number of digits. It's unbiased but uses more random bits, which are expensive.