Integerset of PostgreSQL

One 、 brief introduction

1.1 integerset What is it?

As its name suggests ,integer set, Set of integers . Here refers to the data structure for storing integers . For the definition of set in Mathematics , There is no repetition of elements in the set .

integerset characteristic ：

• Energy storage 64bit Integers

• Memory data structure , Fast memory operation

• Use B-tree Structure organizes data , Insert 、 Search for Complexity O(log2)

• Use Simple-8b Algorithms compress data , Make storage space smaller , Can also be used SIMD Wait for instructions to accelerate

1.2 What can be used for

• Can store maximum 64bit Any positive integer of
• Quickly retrieve whether an integer is in the set

1.3 What are the limitations

• The inserted values must be ordered
• You cannot insert values when traversing a collection
• Deleting values... Is not supported
• Negative numbers are not supported

1.4 contrast redis Of intset

redis And intset

data structure	The maximum value can be stored	Organization form	Search method	storage	Support negative numbers	Insertion order
integerset	unsigned 64bit	B-tree	Traversing the tree + Half search	simple-8b code	No	It has to be orderly
intset	signed 64bit	Array	Half search	Direct deposit value	Yes	arbitrarily , Automatic sorting

1.5 contrast redis Of listpack Variable length coding

redis And listpack

data structure	Numerical coding	Coding form	Code length influencing factors
integerset	simple-8b code	Batch coding	The difference between multiple consecutive values
listpack	Variable length byte encoding	Single value coding	The size of a single value itself

Two 、 data structure

2.1 Data structure definition

typedef struct intset_node intset_node;
typedef struct intset_leaf_node intset_leaf_node;
typedef struct intset_internal_node intset_internal_node;

/* Common structure of both leaf and internal nodes. */
struct intset_node
{
    
	uint16		level;			/* tree level of this node */
	uint16		num_items;		/* number of items in this node */
};

/* Internal node */
struct intset_internal_node
{
    
	/* common header, must match intset_node */
	uint16		level;			/* >= 1 on internal nodes */
	uint16		num_items;

	/* * 'values' is an array of key values, and 'downlinks' are pointers to * lower-level nodes, corresponding to the key values. */
	uint64		values[MAX_INTERNAL_ITEMS];
	intset_node *downlinks[MAX_INTERNAL_ITEMS];
};

/* Leaf node */
typedef struct
{
    
	uint64		first;			/* first integer in this item */
	uint64		codeword;		/* simple8b encoded differences from 'first' */
} leaf_item;

#define MAX_VALUES_PER_LEAF_ITEM (1 + SIMPLE8B_MAX_VALUES_PER_CODEWORD)

struct intset_leaf_node
{
    
	/* common header, must match intset_node */
	uint16		level;			/* 0 on leafs */
	uint16		num_items;

	intset_leaf_node *next;		/* right sibling, if any */

	leaf_item	items[MAX_LEAF_ITEMS];
};

/* * We buffer insertions in a simple array, before packing and inserting them * into the B-tree. MAX_BUFFERED_VALUES sets the size of the buffer. The * encoder assumes that it is large enough that we can always fill a leaf * item with buffered new items. In other words, MAX_BUFFERED_VALUES must be * larger than MAX_VALUES_PER_LEAF_ITEM. For efficiency, make it much larger. */
#define MAX_BUFFERED_VALUES (MAX_VALUES_PER_LEAF_ITEM * 2)

/* * IntegerSet is the top-level object representing the set. * * The integers are stored in an in-memory B-tree structure, plus an array * for newly-added integers. IntegerSet also tracks information about memory * usage, as well as the current position when iterating the set with * intset_begin_iterate / intset_iterate_next. */
struct IntegerSet
{
    
	/* * 'context' is the memory context holding this integer set and all its * tree nodes. * * 'mem_used' tracks the amount of memory used. We don't do anything with * it in integerset.c itself, but the callers can ask for it with * intset_memory_usage(). */
	MemoryContext context;
	uint64		mem_used;

	uint64		num_entries;	/* total # of values in the set */
	uint64		highest_value;	/* highest value stored in this set */

	/* * B-tree to hold the packed values. * * 'rightmost_nodes' hold pointers to the rightmost node on each level. * rightmost_parent[0] is rightmost leaf, rightmost_parent[1] is its * parent, and so forth, all the way up to the root. These are needed when * adding new values. (Currently, we require that new values are added at * the end.) */
	int			num_levels;		/* height of the tree */
	intset_node *root;			/* root node */
	intset_node *rightmost_nodes[MAX_TREE_LEVELS];
	intset_leaf_node *leftmost_leaf;	/* leftmost leaf node */

	/* * Holding area for new items that haven't been inserted to the tree yet. */
	uint64		buffered_values[MAX_BUFFERED_VALUES];
	int			num_buffered_values;

	/* * Iterator support. * * 'iter_values' is an array of integers ready to be returned to the * caller; 'iter_num_values' is the length of that array, and * 'iter_valueno' is the next index. 'iter_node' and 'iter_itemno' point * to the leaf node, and item within the leaf node, to get the next batch * of values from. * * Normally, 'iter_values' points to 'iter_values_buf', which holds items * decoded from a leaf item. But after we have scanned the whole B-tree, * we iterate through all the unbuffered values, too, by pointing * iter_values to 'buffered_values'. */
	bool		iter_active;	/* is iteration in progress? */

	const uint64 *iter_values;
	int			iter_num_values;	/* number of elements in 'iter_values' */
	int			iter_valueno;	/* next index into 'iter_values' */

	intset_leaf_node *iter_node;	/* current leaf node */
	int			iter_itemno;	/* next item in 'iter_node' to decode */

	uint64		iter_values_buf[MAX_VALUES_PER_LEAF_ITEM];
};

among intset_node It can be regarded as a base class , Others inherit it .

class intset_node {
    };
class intset_internal_node : intset_node {
    };
class intset_leaf_node : intset_node {
    };

2.2 chart

3、 ... and 、 relevant API

3.1 establish integerset

/* * Create a new, initially empty, integer set. * * The integer set is created in the current memory context. * We will do all subsequent allocations in the same context, too, regardless * of which memory context is current when new integers are added to the set. */
IntegerSet *
intset_create(void)
{
    
	IntegerSet *intset;

	intset = (IntegerSet *) palloc(sizeof(IntegerSet));
	intset->context = CurrentMemoryContext;
	intset->mem_used = GetMemoryChunkSpace(intset);

	intset->num_entries = 0;
	intset->highest_value = 0;

	intset->num_levels = 0;
	intset->root = NULL;
	memset(intset->rightmost_nodes, 0, sizeof(intset->rightmost_nodes));
	intset->leftmost_leaf = NULL;

	intset->num_buffered_values = 0;

	intset->iter_active = false;
	intset->iter_node = NULL;
	intset->iter_itemno = 0;
	intset->iter_valueno = 0;
	intset->iter_num_values = 0;
	intset->iter_values = NULL;

	return intset;
}

3.2 Insert elements

/* * Add a value to the set. * * Values must be added in order. */
void
intset_add_member(IntegerSet *intset, uint64 x)
{
    
	if (intset->iter_active)
		elog(ERROR, "cannot add new values to integer set while iteration is in progress");

	if (x <= intset->highest_value && intset->num_entries > 0)
		elog(ERROR, "cannot add value to integer set out of order");

	if (intset->num_buffered_values >= MAX_BUFFERED_VALUES)
	{
    
		/* Time to flush our buffer */
		intset_flush_buffered_values(intset);
		Assert(intset->num_buffered_values < MAX_BUFFERED_VALUES);
	}

	/* Add it to the buffer of newly-added values */
	intset->buffered_values[intset->num_buffered_values] = x;
	intset->num_buffered_values++;
	intset->num_entries++;
	intset->highest_value = x;
}

• First, it will be added to the cache
• Wait until the buffer is full , Insert again B In the tree

(1) Why insert the buffer first , Instead of directly inserting B-tree

• simple-8b It's the coding

• B-tree What is stored in the middle leaf node is through simple-8b Encoded value , Instead of the original value .

(2) What is? simple-8b code

simple-8b, among b yes byte, Use 8 Byte encoding , The result of each encoding is 8 byte .

8byte, 64bit, Where start 4bit Used to select the encoding mode , Different coding modes , Decided the next 60bit How to allocate to store data .

static const struct simple8b_mode
{
    
	uint8		bits_per_int;
	uint8		num_ints;
}			simple8b_modes[17] =

{
    
	{
    0, 240},					/* mode 0: 240 zeroes */
	{
    0, 120},					/* mode 1: 120 zeroes */
	{
    1, 60},					/* mode 2: sixty 1-bit integers */
	{
    2, 30},					/* mode 3: thirty 2-bit integers */
	{
    3, 20},					/* mode 4: twenty 3-bit integers */
	{
    4, 15},					/* mode 5: fifteen 4-bit integers */
	{
    5, 12},					/* mode 6: twelve 5-bit integers */
	{
    6, 10},					/* mode 7: ten 6-bit integers */
	{
    7, 8},						/* mode 8: eight 7-bit integers (four bits * are wasted) */
	{
    8, 7},						/* mode 9: seven 8-bit integers (four bits * are wasted) */
	{
    10, 6},					/* mode 10: six 10-bit integers */
	{
    12, 5},					/* mode 11: five 12-bit integers */
	{
    15, 4},					/* mode 12: four 15-bit integers */
	{
    20, 3},					/* mode 13: three 20-bit integers */
	{
    30, 2},					/* mode 14: two 30-bit integers */
	{
    60, 1},					/* mode 15: one 60-bit integer */

	{
    0, 0}						/* sentinel value */
};

According to the coding mode, we can see , The smaller the numerical , The more you can code , The more space you save .

Then how to reduce the number that needs to be encoded

Code the difference between two adjacent numbers , Therefore, the more centralized the data set , The smaller the difference , The more you can code

Store only the difference , How to restore the original value ?

In order to restore the original value , Therefore, the coding is divided into two parts

• base base
• Subsequent data difference coding

typedef struct
{
    
	uint64		first;		// base
	uint64		codeword;	 // Coding results 
} leaf_item;

For example, use mode10, Then each value uses 10bit, In total, it can be encoded 6 A numerical

1010 xxxxxxxxxx xxxxxxxxxx xxxxxxxxxx xxxxxxxxxx xxxxxxxxxx xxxxxxxxxx

Only 60 bit Used to encode data , That's bigger than that 60bit How to encode the value of ？

For greater than 60bit The numerical , Store data base, code 8byte Just write UINT64CONST(0x0FFFFFFFFFFFFFFF), Encoding data length 0, It's equivalent to wasting 8byte.

a. simple-8b coded

/* * EMPTY_CODEWORD is a special value, used to indicate "no values". * It is used if the next value is too large to be encoded with Simple-8b. * * This value looks like a mode-0 codeword, but we can distinguish it * because a regular mode-0 codeword would have zeroes in the unused bits. */
#define EMPTY_CODEWORD UINT64CONST(0x0FFFFFFFFFFFFFFF)

/* * Encode a number of integers into a Simple-8b codeword. * * (What we actually encode are deltas between successive integers. * "base" is the value before ints[0].) * * The input array must contain at least SIMPLE8B_MAX_VALUES_PER_CODEWORD * elements, ensuring that we can produce a full codeword. * * Returns the encoded codeword, and sets *num_encoded to the number of * input integers that were encoded. That can be zero, if the first delta * is too large to be encoded. */
static uint64
simple8b_encode(const uint64 *ints, int *num_encoded, uint64 base)
{
    
	int			selector;
	int			nints;
	int			bits;
	uint64		diff;
	uint64		last_val;
	uint64		codeword;
	int			i;

	Assert(ints[0] > base);

	/* * Select the "mode" to use for this codeword. * * In each iteration, check if the next value can be represented in the * current mode we're considering. If it's too large, then step up the * mode to a wider one, and repeat. If it fits, move on to the next * integer. Repeat until the codeword is full, given the current mode. * * Note that we don't have any way to represent unused slots in the * codeword, so we require each codeword to be "full". It is always * possible to produce a full codeword unless the very first delta is too * large to be encoded. For example, if the first delta is small but the * second is too large to be encoded, we'll end up using the last "mode", * which has nints == 1. */
	selector = 0;
	nints = simple8b_modes[0].num_ints;
	bits = simple8b_modes[0].bits_per_int;
	diff = ints[0] - base - 1;
	last_val = ints[0];
	i = 0;						/* number of deltas we have accepted */
	for (;;)
	{
    
		if (diff >= (UINT64CONST(1) << bits))
		{
    
			/* too large, step up to next mode */
			selector++;
			nints = simple8b_modes[selector].num_ints;
			bits = simple8b_modes[selector].bits_per_int;
			/* we might already have accepted enough deltas for this mode */
			if (i >= nints)
				break;
		}
		else
		{
    
			/* accept this delta; then done if codeword is full */
			i++;
			if (i >= nints)
				break;
			/* examine next delta */
			Assert(ints[i] > last_val);
			diff = ints[i] - last_val - 1;
			last_val = ints[i];
		}
	}

	if (nints == 0)
	{
    
		/* * The first delta is too large to be encoded with Simple-8b. * * If there is at least one not-too-large integer in the input, we * will encode it using mode 15 (or a more compact mode). Hence, we * can only get here if the *first* delta is >= 2^60. */
		Assert(i == 0);
		*num_encoded = 0;
		return EMPTY_CODEWORD;
	}

	/* * Encode the integers using the selected mode. Note that we shift them * into the codeword in reverse order, so that they will come out in the * correct order in the decoder. */
	codeword = 0;
	if (bits > 0)
	{
    
		for (i = nints - 1; i > 0; i--)
		{
    
			diff = ints[i] - ints[i - 1] - 1;
			codeword |= diff;
			codeword <<= bits;
		}
		diff = ints[0] - base - 1;
		codeword |= diff;
	}

	/* add selector to the codeword, and return */
	codeword |= (uint64) selector << 60;

	*num_encoded = nints;
	return codeword;
}

b. simple-8b Decoding implementation

take 8byte Code data for , Restore to an array .

/* * Decode a codeword into an array of integers. * Returns the number of integers decoded. */
static int
simple8b_decode(uint64 codeword, uint64 *decoded, uint64 base)
{
    
	int			selector = (codeword >> 60);
	int			nints = simple8b_modes[selector].num_ints;
	int			bits = simple8b_modes[selector].bits_per_int;
	uint64		mask = (UINT64CONST(1) << bits) - 1;
	uint64		curr_value;

	if (codeword == EMPTY_CODEWORD)
		return 0;

	curr_value = base;
	for (int i = 0; i < nints; i++)
	{
    
		uint64		diff = codeword & mask;

		curr_value += 1 + diff;
		decoded[i] = curr_value;
		codeword >>= bits;
	}
	return nints;
}

(3) For example, insert 1-600

• First, insert buffer

• When the buffer is full , Will be encoded and inserted B-tree

• The remaining data continues to be inserted into the buffer

After each coding , If there is still data left in the buffer , Will be copied to the beginning of the buffer

I try to transform this buffer into a circular queue , In this way, there is no need to copy the data . But for some use buffers All places need to add the remainder operation , It seems that the original code is not clearer and simpler , And with the use of queues , The array will be divided into two parts , The two parts are still in order , Or use half search , A try is still good , debugging , When it works properly , I'm still very happy

3.2 Determine whether a value is in integerset in

• First, determine whether it is in the buffer , The buffer is incremented orderly , So use half search
• Judge which node range the value is in , because B-tree characteristic , Also use half search
• Last in simple-8b Search in encoded data , simple8b_contains Functions and simple8b_decode similar

/* * Does the set contain the given value? */
bool
intset_is_member(IntegerSet *intset, uint64 x)
{
    
	intset_node *node;
	intset_leaf_node *leaf;
	int			level;
	int			itemno;
	leaf_item  *item;

	/* * The value might be in the buffer of newly-added values. */
	if (intset->num_buffered_values > 0 && x >= intset->buffered_values[0])
	{
    
		int			itemno;

		itemno = intset_binsrch_uint64(x,
									   intset->buffered_values,
									   intset->num_buffered_values,
									   false);
		if (itemno >= intset->num_buffered_values)
			return false;
		else
			return (intset->buffered_values[itemno] == x);
	}

	/* * Start from the root, and walk down the B-tree to find the right leaf * node. */
	if (!intset->root)
		return false;
	node = intset->root;
	for (level = intset->num_levels - 1; level > 0; level--)
	{
    
		intset_internal_node *n = (intset_internal_node *) node;

		Assert(node->level == level);

		itemno = intset_binsrch_uint64(x, n->values, n->num_items, true);
		if (itemno == 0)
			return false;
		node = n->downlinks[itemno - 1];
	}
	Assert(node->level == 0);
	leaf = (intset_leaf_node *) node;

	/* * Binary search to find the right item on the leaf page */
	itemno = intset_binsrch_leaf(x, leaf->items, leaf->num_items, true);
	if (itemno == 0)
		return false;
	item = &leaf->items[itemno - 1];

	/* Is this a match to the first value on the item? */
	if (item->first == x)
		return true;
	Assert(x > item->first);

	/* Is it in the packed codeword? */
	if (simple8b_contains(item->codeword, x, item->first))
		return true;

	return false;
}

3.3 Traverse the whole integerset

/* * Begin in-order scan through all the values. * * While the iteration is in-progress, you cannot add new values to the set. */
void
intset_begin_iterate(IntegerSet *intset)
{
    
	/* Note that we allow an iteration to be abandoned midway */
	intset->iter_active = true;
	intset->iter_node = intset->leftmost_leaf;
	intset->iter_itemno = 0;
	intset->iter_valueno = 0;
	intset->iter_num_values = 0;
	intset->iter_values = intset->iter_values_buf;
}

/* * Returns the next integer, when iterating. * * intset_begin_iterate() must be called first. intset_iterate_next() returns * the next value in the set. Returns true, if there was another value, and * stores the value in *next. Otherwise, returns false. */
bool
intset_iterate_next(IntegerSet *intset, uint64 *next)
{
    
	Assert(intset->iter_active);
	for (;;)
	{
    
		/* Return next iter_values[] entry if any */
		if (intset->iter_valueno < intset->iter_num_values)
		{
    
			*next = intset->iter_values[intset->iter_valueno++];
			return true;
		}

		/* Decode next item in current leaf node, if any */
		if (intset->iter_node &&
			intset->iter_itemno < intset->iter_node->num_items)
		{
    
			leaf_item  *item;
			int			num_decoded;

			item = &intset->iter_node->items[intset->iter_itemno++];

			intset->iter_values_buf[0] = item->first;
			num_decoded = simple8b_decode(item->codeword,
										  &intset->iter_values_buf[1],
										  item->first);
			intset->iter_num_values = num_decoded + 1;
			intset->iter_valueno = 0;
			continue;
		}

		/* No more items on this leaf, step to next node */
		if (intset->iter_node)
		{
    
			intset->iter_node = intset->iter_node->next;
			intset->iter_itemno = 0;
			continue;
		}

		/* * We have reached the end of the B-tree. But we might still have * some integers in the buffer of newly-added values. */
		if (intset->iter_values == (const uint64 *) intset->iter_values_buf)
		{
    
			intset->iter_values = intset->buffered_values;
			intset->iter_num_values = intset->num_buffered_values;
			intset->iter_valueno = 0;
			continue;
		}

		break;
	}

	/* No more results. */
	intset->iter_active = false;
	*next = 0;					/* prevent uninitialized-variable warnings */
	return false;
}

• Start from the leftmost leaf node , Leaf nodes pass through next The pointer is connected into a linked list , Go through one by one

• There are multiple in each leaf node item, Go through one by one item

• Every item After simple-8b Encoded data , Through the decoding , Write data to the temporary buffer

• Each time, a data is returned from the temporary buffer

• After traversing all nodes , Traverse the buffer

Four 、 summary

• integerset Is a set of positive integers , The maximum value is 64bit

• Use B-tree Structure to manage data

• Use simple-8b Encoding data , Compress

• The insertion sequence must be orderly

• Deleting data is not supported

• Data compression rate depends on the gap between data

• Data cannot be inserted during iteration , Unrealized

• The search process uses half search

• Batch code data

Hold on B-tree After learning clearly , You can try to insert in an unordered way