Skip to content

Commit ee1b30f

Browse files
j-naylorj-naylor
committed
Add template for adaptive radix tree
This implements a radix tree data structure based on the design in "The Adaptive Radix Tree: ARTful Indexing for Main-Memory Databases" by Viktor Leis, Alfons Kemper, and ThomasNeumann, 2013. The main technique that makes it adaptive is using several different node types, each with a different capacity of elements, and a different algorithm for accessing them. The nodes start small and grow/shrink as needed. The main advantage over hash tables is efficient sorted iteration and better memory locality when successive keys are lexicographically close together. The implementation currently assumes 64-bit integer keys, and traversing the tree is in general slower than a linear probing hash table, so this is not a general-purpose associative array. The paper describes two other techniques not implemented here, namely "path compression" and "lazy expansion". These can further reduce memory usage and speed up traversal, but the former would add significant complexity and the latter requires storing the full key with the value. We do trivially compress the path when leading bytes of the key are zeros, however. For value storage, we use "combined pointer/value slots", as recommended in the paper. Values of size equal or smaller than the the platform's pointer type are stored in the array of child pointers in the last level node, while larger values are each stored in a separate allocation. This is for now fixed at compile time, but it would be fairly trivial to allow determining at runtime how variable-length values are stored. One innovation in our implementation compared to the ART paper is decoupling the notion of node "size class" from "kind". The size classes within a given node kind have the same underlying type, but a variable capacity for children, so we can introduce additional node sizes with little additional code. To enable different use cases to specialize for different value types and for shared/local memory, we use macro-templatized code generation in the same manner as simplehash.h and sort_template.h. Future commits will use this infrastructure for storing TIDs. Patch by Masahiko Sawada and John Naylor, but a substantial amount of credit is due to Andres Freund, whose proof-of-concept was a valuable source of coding idioms and awareness of performance pitfalls, and who reviewed earlier versions. Discussion: https://postgr.es/m/CAD21AoAfOZvmfR0j8VmZorZjL7RhTiQdVttNuC4W-Shdc2a-AA%40mail.gmail.com
1 parent 65db0cf commit ee1b30f

File tree

14 files changed

+3620
-0
lines changed

14 files changed

+3620
-0
lines changed

‎src/backend/utils/mmgr/dsa.c

+13
Original file line numberDiff line numberDiff line change
@@ -1035,6 +1035,19 @@ dsa_set_size_limit(dsa_area *area, size_t limit)
10351035
LWLockRelease(DSA_AREA_LOCK(area));
10361036
}
10371037

1038+
/* Return the total size of all active segments */
1039+
size_t
1040+
dsa_get_total_size(dsa_area *area)
1041+
{
1042+
size_t size;
1043+
1044+
LWLockAcquire(DSA_AREA_LOCK(area), LW_EXCLUSIVE);
1045+
size = area->control->total_segment_size;
1046+
LWLockRelease(DSA_AREA_LOCK(area));
1047+
1048+
return size;
1049+
}
1050+
10381051
/*
10391052
* Aggressively free all spare memory in the hope of returning DSM segments to
10401053
* the operating system.

0 commit comments

Comments
 (0)