0

I might need to work with relatively large (non-clustered) index keys (between 1KB to 4KB). I found that Spanner and DB2 support 8KB index-key size, MSSQL allows 1.7KB and Postgress around 2.6KB (1/3 of the Postgress' block size). While reading other posts, I found that mostly one can avoid using such large keys, and I will try to think whether I can do so, but I have a few questions in case I do not succeed to avoid it in all cases.

I do not know what data structures are used to implement indexes in the mentioned systems (except of Postgress of course). I am well familiar with B+Trees, and it seems hard to efficiently save such large keys as the B+Tree's inner nodes pivots, since the branching factor will be too small and thus any read/write will cost too many IOs. I believe that compression methods might work, but many compression methods (like using hash function which does not preserve order) might defect the key's order which eliminates the possibility to use the index for range queries. So, I would be glad for any documentation or information about the DBMS's index implementations, especially anything that relates to relatively large keys. (I have already read the manuals, but they do not talk about how they actually work with large keys).

In addition, I would like to know whether those DBMS are indeed efficient when working with keys which are close to stated index-key size limits? I have no previous experience working with large index-keys, and any information and past experience (dos and dont's) would be really appreciated.

6
  • I guess range queries on such large keys is strange enough already. What exactly is your use case? Sep 26 '21 at 18:16
  • 1
    Loosely speaking, I think the lack of information you're finding on standards for working with large key sizes is evident to the fact that such key sizes just don't perform well as indexes, and resultantly just don't make sense to index on since the performance tradeoff isn't worth it. I believe if you truly can't architect your schema to reduce the overall size of your index keys, then your only options are to either reduce the amount of data, increase the hardware provisioned for your database server, or unfortunately live by the mathematical limitations of data structures for your data.
    – J.D.
    Sep 26 '21 at 20:29
  • Without the range queries a hash would be way to go, with it I would suggest truncating - index only some reasonable prefix of the data. If the keys have long common prefixes then then thats not very useful unless you can devise some shortening method that would keep the ordering (for example if the keys were entire xml documents, you can skip the common header and then index prefix of the remaining document data).
    – jkavalik
    Sep 27 '21 at 7:21
  • Please edit the question to limit it to a specific problem with enough detail to identify an adequate answer.
    – Community Bot
    Sep 27 '21 at 13:44
  • @Charlieface I will need to use composite index with medium size keys (for example, indexing 5 columns, when each attribute is around 256B). Sep 29 '21 at 7:19

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.