Increasing IndexTupleData.t_info from uint16 to uint32
The overall trend in machine learning embedding sizes has been growing
rapidly over the last few years from 128 up to 4K dimensions yielding
additional value and quality improvements. It's not clear when this trend
in growth will ease. The leading text embedding models
<https://d2Vt1P04.na1.hs-sales-engage.com/Ctc/I9+23284/d2Vt1P04/Jl22-6qcW7lCdLW6lZ3mZW2xQSTk7n4W72W13GRJl8P4L5lW65mzGl6rb-LDW3fZkLK7wL6F7W7bLKRl3_KR8gW2H6rqc3sKVWHW4D9qCR2clFY9W7HsFTL26WFWlW5Hfcrf2QPpJMW3LsmXC7QBywcW6f_40K6rHypwN72RsbhFLs2vW6jlt_y6pFdc9V91HDm4pT7BnVccdx84tkPBQW6PJxqG2F_FLmV6W6fc5JT11jW8vC6FB5DCKGjW1854vH3kDmt-W9lxPZm4_rYkDW4L32gg19WxLrW6-_S_-5MBHNYW2MsMBv25m7NkW5tPMCP5x2DzRf7CCRKR04>
generate
now exceeds the index storage available in IndexTupleData.t_info.
The current index tuple size is stored in 13 bits of IndexTupleData.t_info,
which limits the max size of an index tuple to 2^13 = 8129 bytes. Vectors
implemented by pgvector
<https://d2Vt1P04.na1.hs-sales-engage.com/Ctc/I9+23284/d2Vt1P04/JkM2-6qcW6N1vHY6lZ3nBW1KW3_33qLHXZW5SdJZV6V1sGTW4c2GQ_3MLxkdW2lzQbs2W87JKW772TLX7BpFlQW8-WNlD7GgH2tW3yzJG98NPhgFW3QMP2h5CKxzKN4DD1QlzH6WrW1ByHLF3QYtPQW1W8HLB2Jl6vZW8C8pKB9fvQMtW7wJpwd3-8fwWW60mRbF435_NkW253WL721Q95QW20Z-xk3_22C0W1Thshf6-_qGbW6rz9tX72gbKyW5L9ktk1Vtn-dW8601Jv3ZfHxhW7ZW-6L86RX2ZW293jnQ921NT6f2Kg23K04>
currently use
a 32 bit float for elements, which limits vector size to 2K
dimensions, which is no longer state of the art.
I've attached a patch that increases IndexTupleData.t_info from 16bits to
32bits allowing for significantly larger index tuple sizes. I would guess
this patch is not a complete implementation that allows for migration from
previous versions, but it does compile and initdb succeeds. I'd be happy to
continue work if the core team is receptive to an update in this area, and
I'd appreciate any feedback the community has on the approach.
I imagine it might be worth hiding this change behind a compile time
configuration parameter similar to blocksize. I'm sure there are
implications I'm unaware of with this change, but I wanted to start the
discussion around a bit of code to see how much would actually need to
change.
Also, I believe this is my first mailing list post in a decade or 2, so let
me know if I've missed something important. BTW, thanks for all your work
over the decades!
Attachments:
32bit_index_info.patchapplication/octet-stream; name=32bit_index_info.patchDownload
diff --git a/src/backend/access/common/indextuple.c b/src/backend/access/common/indextuple.c
index bb2c6a2bcc..e896c98db9 100644
--- a/src/backend/access/common/indextuple.c
+++ b/src/backend/access/common/indextuple.c
@@ -73,7 +73,7 @@ index_form_tuple_context(TupleDesc tupleDescriptor,
data_size,
hoff;
int i;
- unsigned short infomask = 0;
+ index_info infomask = 0;
bool hasnull = false;
uint16 tupmask = 0;
int numberOfAttributes = tupleDescriptor->natts;
diff --git a/src/backend/access/spgist/spgutils.c b/src/backend/access/spgist/spgutils.c
index 5b5e6e82d3..40c4f168a5 100644
--- a/src/backend/access/spgist/spgutils.c
+++ b/src/backend/access/spgist/spgutils.c
@@ -942,7 +942,7 @@ spgFormNodeTuple(SpGistState *state, Datum label, bool isnull)
{
SpGistNodeTuple tup;
unsigned int size;
- unsigned short infomask = 0;
+ index_info infomask = 0;
/* compute space needed (note result is already maxaligned) */
size = SGNTHDRSZ;
diff --git a/src/include/access/itup.h b/src/include/access/itup.h
index 94885751e5..84498790d3 100644
--- a/src/include/access/itup.h
+++ b/src/include/access/itup.h
@@ -19,6 +19,8 @@
#include "storage/bufpage.h"
#include "storage/itemptr.h"
+typedef uint32 index_info;
+
/*
* Index tuple header structure
*
@@ -39,14 +41,14 @@ typedef struct IndexTupleData
/* ---------------
* t_info is laid out in the following fashion:
*
- * 15th (high) bit: has nulls
- * 14th bit: has var-width attributes
- * 13th bit: AM-defined meaning
- * 12-0 bit: size of tuple
+ * 31st (high) bit: has nulls
+ * 30th bit: has var-width attributes
+ * 29th bit: AM-defined meaning
+ * 28-0 bit: size of tuple
* ---------------
*/
- unsigned short t_info; /* various info about tuple */
+ index_info t_info; /* various info about tuple */
} IndexTupleData; /* MORE DATA FOLLOWS AT END OF STRUCT */
@@ -62,11 +64,11 @@ typedef IndexAttributeBitMapData * IndexAttributeBitMap;
/*
* t_info manipulation macros
*/
-#define INDEX_SIZE_MASK 0x1FFF
-#define INDEX_AM_RESERVED_BIT 0x2000 /* reserved for index-AM specific
- * usage */
-#define INDEX_VAR_MASK 0x4000
-#define INDEX_NULL_MASK 0x8000
+#define INDEX_SIZE_MASK 0x1FFFFFFF
+#define INDEX_AM_RESERVED_BIT 0x20000000 /* reserved for index-AM specific
+ * usage */
+#define INDEX_VAR_MASK 0x40000000
+#define INDEX_NULL_MASK 0x80000000
#define IndexTupleSize(itup) ((Size) ((itup)->t_info & INDEX_SIZE_MASK))
#define IndexTupleHasNulls(itup) ((((IndexTuple) (itup))->t_info & INDEX_NULL_MASK))
@@ -96,7 +98,7 @@ extern IndexTuple index_truncate_tuple(TupleDesc sourceDescriptor,
* at index_form_tuple time so enough space is allocated).
*/
static inline Size
-IndexInfoFindDataOffset(unsigned short t_info)
+IndexInfoFindDataOffset(index_info t_info)
{
if (!(t_info & INDEX_NULL_MASK))
return MAXALIGN(sizeof(IndexTupleData));
Montana Low <montana@postgresml.org> writes:
I've attached a patch that increases IndexTupleData.t_info from 16bits to
32bits allowing for significantly larger index tuple sizes.
I fear this idea is a non-starter because it'd break on-disk
compatibility. Certainly, if we were to try to pursue it, there'd
need to be an enormous amount of effort spent on dealing with existing
indexes and transition mechanisms. I don't think you've made the case
why that would be time well spent.
On a micro level, this makes sizeof(IndexTupleData) be not maxaligned,
which is likely to cause problems on alignment-picky hardware, or else
result in space wastage if we were careful to MAXALIGN() everywhere.
(Which we should have been, but I don't care to bet on it.) A lot of
people would be sad if their indexes got noticeably bigger when they
weren't getting anything out of that.
regards, tom lane
I wrote:
On a micro level, this makes sizeof(IndexTupleData) be not maxaligned,
which is likely to cause problems on alignment-picky hardware, or else
result in space wastage if we were careful to MAXALIGN() everywhere.
(Which we should have been, but I don't care to bet on it.) A lot of
people would be sad if their indexes got noticeably bigger when they
weren't getting anything out of that.
After thinking about that a bit more, there might be a way out that
both avoids bloating index tuples that don't need it, and avoids
the compatibility problem. How about defining that if the
INDEX_SIZE_MASK bits aren't zero, they are the tuple size as now;
but if they are zero, then the size appears in a separate uint16
field following the existing IndexTupleData fields. We could perhaps
also rethink how the nulls bitmap storage works in this "v2"
index tuple header layout? In any case, I'd expect to end up in
a place where (on 64-bit hardware) you pay an extra MAXALIGN quantum
for either an oversize tuple or a nulls bitmap, but only one quantum
when you have both, and nothing above today when the tuple is not
oversize.
This'd complicate tuple construction and inspection a bit, but
it would avoid building an enormous lot of infrastructure to deal
with transitioning to a not-upward-compatible definition.
regards, tom lane
On Thu, 18 Jan 2024 at 13:41, Montana Low <montana@postgresml.org> wrote:
The overall trend in machine learning embedding sizes has been growing rapidly over the last few years from 128 up to 4K dimensions yielding additional value and quality improvements. It's not clear when this trend in growth will ease. The leading text embedding models generate now exceeds the index storage available in IndexTupleData.t_info.
The current index tuple size is stored in 13 bits of IndexTupleData.t_info, which limits the max size of an index tuple to 2^13 = 8129 bytes. Vectors implemented by pgvector currently use a 32 bit float for elements, which limits vector size to 2K dimensions, which is no longer state of the art.
I've attached a patch that increases IndexTupleData.t_info from 16bits to 32bits allowing for significantly larger index tuple sizes. I would guess this patch is not a complete implementation that allows for migration from previous versions, but it does compile and initdb succeeds. I'd be happy to continue work if the core team is receptive to an update in this area, and I'd appreciate any feedback the community has on the approach.
I'm not sure why this is needed.
Vector data indexing generally requires bespoke index methods, which
are not currently available in the core PostgreSQL repository, and
indexes are not at all required to utilize the IndexTupleData format
for their data tuples (one example of this being BRIN).
The only hard requirement in AMs which use Postgres' relfile format is
that they follow the Page layout and optionally the pd_linp/ItemId
array, which limit the size of Page tuples to 2^15-1 (see
ItemIdData.lp_len) and ~2^16-bytes
(PageHeaderData.pd_pagesize_version).
Next, the only non-internal use of IndexTuple is in IndexOnlyScans.
However, here the index may fill the scandesc->xs_hitup with a heap
tuple instead, which has a length stored in uint32, too. So, I don't
quite see why this would be required for all indexes.
Kind regards,
Matthias van de Meent
Neon (https://neon.tech)
Hi,
The overall trend in machine learning embedding sizes has been growing rapidly over the last few years from 128 up to 4K dimensions yielding additional value and quality improvements. It's not clear when this trend in growth will ease. The leading text embedding models generate now exceeds the index storage available in IndexTupleData.t_info.
The current index tuple size is stored in 13 bits of IndexTupleData.t_info, which limits the max size of an index tuple to 2^13 = 8129 bytes. Vectors implemented by pgvector currently use a 32 bit float for elements, which limits vector size to 2K dimensions, which is no longer state of the art.
I've attached a patch that increases IndexTupleData.t_info from 16bits to 32bits allowing for significantly larger index tuple sizes. I would guess this patch is not a complete implementation that allows for migration from previous versions, but it does compile and initdb succeeds. I'd be happy to continue work if the core team is receptive to an update in this area, and I'd appreciate any feedback the community has on the approach.
If I read this correctly, basically the patch adds 16 useless bits for
all applications except for ML ones...
Perhaps implementing an alternative storage specifically for ML using
TAM interface would be a better approach?
--
Best regards,
Aleksander Alekseev