"For example, if the minimum delta is about -1 million, and the other deltas are usually between -10 and +10, then all of those deltas will be shifted up by 1 million"

- This is true. Zigzag would be able to encode better if the range of deltas within a single page was very large. This doesn't seem like a good fit for delta encoding though and I don't think it's worth the tax on the read path.

"I re-run your benchmark, and calculated the time it takes to encode the input data. Also you should note that the whole page must be read and stored in memory to find the minimum, and while doing this, the ValuesWriter won't be able to correctly give the size of the currently encoded data."

- This is also correct. But again, buffering the page is not a problem. Pages are ~64K and there are other reasons we need to buffer it (compression, computing exact sizes etc). In general, I think we should prefer 
good on disk size and good read performance over good write performance. We're expecting this data to be written once and read repeatedly so I'd happily take 3x slower on write for a 50% improvement on read. We certainly don't want the writes to be unreasonably slow.