I've thought about different algorithms little more. General problem I see is online update. We need it while it is typically not covered by researches at all. We already have to invent small index in the end of page. Different encoding methods adds more challenges. In general, methods can be classified in two groups: 1) Values aren't aligned by bytes (gamma-codes, PFOR etc.) 2) Multiple values are packed together in small group (simple-9, simple-18)
Ok.
For the first group of methods when inserting in the middle of the page we would have to do not byte-aligned shift of right part of values. I don't know how expensive is this shift but I expect that it would be much slower than memmove.
Agreed.
When values are packed into small groups, we have to either insert inefficiently encoded value or re-encode whole right part of values.
It would probably be simplest to store newly inserted items uncompressed, in a separate area in the page. For example, grow the list of uncompressed items downwards from pg_upper, and the compressed items upwards from pg_lower. When the page fills up, re-encode the whole page.
Good idea. But:
1) We'll still need item indexes in the end of page for fast scan.
2) Storage would be easily extendable to hold additional information as well.
Better compression shouldn't block more serious improvements.
