4 ms·
It seems a little surprising that GIN indexes have never been improved to allow for efficient sorting. Is this just not in enough demand to receive any attentio
by ollysb 4y ago
It seems a little surprising that GIN indexes have never been improved to allow for efficient sorting. Is this just not in enough demand to receive any attention or is there a technical aspect that makes it particularly difficult?
- mattashii 4y agoI'm not familiar with the full details, but GIN indeed has some issues that make it difficult to make presorting expensive: It has a guarantee of only one item in the tree for each key. All table rows that share that key are stored under that one item, as one large value. This value can thus become really large (and is stored as a subtree in such cases). To sort these tuples, you can either implement that as 'merge key/value pairs when keys are equal during the sort phase' or 'merge key/value pairs when keys are equal during the index load phase'. The first requires handling of arbitrarily large KV pairs (potentially larger than the normal page size, which indexes generally don't handle well) and losing sort elements during the sort (due to merges of values, I'm not sure sort algorithms can work with that). The second requires a significantly larger temporary space to store the temporary data (potentially several times the size of the original data). Additionally, someone must first find this enough of an issue to try to fix this, and apparently nobody has yet thought it to be enough of an issue to take a stab at it.