On Fri, Jul 8, 2022 at 9:10 AM Masahiko Sawada <sawada.m...@gmail.com> wrote:
> I guess that the tree height is affected by where garbages are, right? > For example, even if all garbage in the table is concentrated in > 0.5GB, if they exist between 2^17 and 2^18 block, we use the first > byte of blockhi. If the table is larger than 128GB, the second byte of > the blockhi could be used depending on where the garbage exists. Right. > Another variation of how to store TID would be that we use the block > number as a key and store a bitmap of the offset as a value. We can > use Bitmapset for example, I like the idea of using existing code to set/check a bitmap if it's convenient. But (in case that was implied here) I'd really like to stay away from variable-length values, which would require "Single-value leaves" (slow). I also think it's fine to treat the key/value as just bits, and not care where exactly they came from, as we've been talking about. > or an approach like Roaring bitmap. This would require two new data structures instead of one. That doesn't seem like a path to success. > I think that at this stage it's better to define the design first. For > example, key size and value size, and these sizes are fixed or can be > set the arbitary size? I don't think we need to start over. Andres' prototype had certain design decisions built in for the intended use case (although maybe not clearly documented as such). Subsequent patches in this thread substantially changed many design aspects. If there were any changes that made things wonderful for vacuum, it wasn't explained, but Andres did explain how some of these changes were not good for other uses. Going to fixed 64-bit keys and values should still allow many future applications, so let's do that if there's no reason not to. > For value size, if we support > different value sizes specified by the user, we can either embed > multiple values in the leaf node (called Multi-value leaves in ART > paper) I don't think "Multi-value leaves" allow for variable-length values, FWIW. And now I see I also used this term wrong in my earlier review comment -- v3/4 don't actually use "multi-value leaves", but Andres' does (going by the multiple leaf types). From the paper: "Multi-value leaves: The values are stored in one of four different leaf node types, which mirror the structure of inner nodes, but contain values instead of pointers." (It seems v3/v4 could be called a variation of "Combined pointer/value slots: If values fit into pointers, no separate node types are necessary. Instead, each pointer storage location in an inner node can either store a pointer or a value." But without the advantage of variable length keys). -- John Naylor EDB: http://www.enterprisedb.com
