Skip to content

Commit 129c7b0

Browse files
bluestreak01bluestreak01
authored
perf(sql): improve performance of symbol index lookups (#5953)
1 parent fe7c916 commit 129c7b0

14 files changed

Lines changed: 442 additions & 95 deletions

‎core/src/main/java/io/questdb/cairo/AbstractIndexReader.java‎

Lines changed: 69 additions & 44 deletions
Original file line numberDiff line numberDiff line change
@@ -43,10 +43,12 @@ public abstract class AbstractIndexReader implements BitmapIndexReader {
4343
protected int blockCapacity;
4444
protected int blockValueCountMod;
4545
protected MillisecondClock clock;
46+
protected long columnTop;
4647
protected int keyCount;
4748
protected long spinLockTimeoutMs;
48-
protected long unindexedNullCount;
4949
private int keyCountIncludingNulls;
50+
private long keyFileSequence = -1;
51+
private long valueMemSize = -1;
5052

5153
@Override
5254
public void close() {
@@ -56,6 +58,10 @@ public void close() {
5658
Misc.free(valueMem);
5759
}
5860

61+
public long getColumnTop() {
62+
return columnTop;
63+
}
64+
5965
public long getKeyBaseAddress() {
6066
return keyMem.addressOf(0);
6167
}
@@ -69,10 +75,6 @@ public long getKeyMemorySize() {
6975
return keyMem.size();
7076
}
7177

72-
public long getUnIndexedNullCount() {
73-
return unindexedNullCount;
74-
}
75-
7678
public long getValueBaseAddress() {
7779
return valueMem.addressOf(0);
7880
}
@@ -91,13 +93,13 @@ public boolean isOpen() {
9193
}
9294

9395
@Override
94-
public void of(CairoConfiguration configuration, Path path, CharSequence name, long columnNameTxn, long unIndexedNullCount) {
95-
this.unindexedNullCount = unIndexedNullCount;
96+
public void of(CairoConfiguration configuration, Path path, CharSequence columnName, long columnNameTxn, long columnTop) {
97+
this.columnTop = columnTop;
9698
final int plen = path.size();
9799
this.spinLockTimeoutMs = configuration.getSpinLockTimeout();
98100

99101
try {
100-
keyMem.wholeFile(configuration.getFilesFacade(), BitmapIndexUtils.keyFileName(path, name, columnNameTxn), MemoryTag.MMAP_INDEX_READER);
102+
keyMem.wholeFile(configuration.getFilesFacade(), BitmapIndexUtils.keyFileName(path, columnName, columnNameTxn), MemoryTag.MMAP_INDEX_READER);
101103
this.clock = configuration.getMillisecondClock();
102104

103105
// key file should already be created at least with header
@@ -113,45 +115,13 @@ public void of(CairoConfiguration configuration, Path path, CharSequence name, l
113115
throw CairoException.critical(0).put("Unknown format: ").put(path);
114116
}
115117

116-
// Triple check atomic read. We read first and last sequences. If they match - there is a chance at stable
117-
// read. Confirm start sequence hasn't changed after values read. If it has changed - retry the whole thing.
118-
int blockValueCountMod;
119-
int keyCount;
120-
long valueMemSize;
121-
final long deadline = clock.getTicks() + spinLockTimeoutMs;
122-
while (true) {
123-
long seq = keyMem.getLong(BitmapIndexUtils.KEY_RESERVED_OFFSET_SEQUENCE);
124-
125-
Unsafe.getUnsafe().loadFence();
126-
if (keyMem.getLong(BitmapIndexUtils.KEY_RESERVED_OFFSET_SEQUENCE_CHECK) == seq) {
127-
blockValueCountMod = keyMem.getInt(BitmapIndexUtils.KEY_RESERVED_OFFSET_BLOCK_VALUE_COUNT) - 1;
128-
keyCount = keyMem.getInt(BitmapIndexUtils.KEY_RESERVED_OFFSET_KEY_COUNT);
129-
valueMemSize = keyMem.getLong(BitmapIndexUtils.KEY_RESERVED_OFFSET_VALUE_MEM_SIZE);
130-
131-
Unsafe.getUnsafe().loadFence();
132-
if (keyMem.getLong(BitmapIndexUtils.KEY_RESERVED_OFFSET_SEQUENCE) == seq) {
133-
break;
134-
}
135-
}
136-
137-
if (clock.getTicks() > deadline) {
138-
LOG.error().$(INDEX_CORRUPT).$(" [timeout=").$(spinLockTimeoutMs).$("ms]").$();
139-
throw CairoException.critical(0).put(INDEX_CORRUPT);
140-
}
141-
142-
Os.pause();
143-
}
118+
readIndexMetadataAtomically();
144119

145120
// Resize key memory eagerly to avoid doing that when searching keys.
146-
keyMem.extend(BitmapIndexUtils.getKeyEntryOffset(keyCount));
147-
148-
this.blockValueCountMod = blockValueCountMod;
149-
this.blockCapacity = (blockValueCountMod + 1) * 8 + BitmapIndexUtils.VALUE_BLOCK_FILE_RESERVED;
150-
this.keyCount = keyCount;
151-
this.keyCountIncludingNulls = unIndexedNullCount > 0 ? keyCount + 1 : keyCount;
121+
keyMem.extend(BitmapIndexUtils.getKeyEntryOffset(this.keyCount));
152122
this.valueMem.of(
153123
configuration.getFilesFacade(),
154-
BitmapIndexUtils.valueFileName(path.trimTo(plen), name, columnNameTxn),
124+
BitmapIndexUtils.valueFileName(path.trimTo(plen), columnName, columnNameTxn),
155125
valueMemSize,
156126
valueMemSize,
157127
MemoryTag.MMAP_INDEX_READER
@@ -164,6 +134,24 @@ public void of(CairoConfiguration configuration, Path path, CharSequence name, l
164134
}
165135
}
166136

137+
/**
138+
* Reloads index by extending value memory. There are several assumptions here:
139+
* - index reader is open and memory objects are not null
140+
* - memory object can be read
141+
* - key file sequence value and "value memory size" are both updated
142+
* - we can resize key memory using only keyCount
143+
* - we can resize value memory using the "value memory size" we read from the key header
144+
*/
145+
public void reloadConditionally() {
146+
long seq = keyMem.getLong(BitmapIndexUtils.KEY_RESERVED_OFFSET_SEQUENCE_CHECK);
147+
if (seq != keyFileSequence) {
148+
readIndexMetadataAtomically();
149+
// extend memory objects
150+
this.keyMem.extend(BitmapIndexUtils.getKeyEntryOffset(keyCount));
151+
this.valueMem.extend(valueMemSize);
152+
}
153+
}
154+
167155
public void updateKeyCount() {
168156
int keyCount;
169157
final long deadline = clock.getTicks() + spinLockTimeoutMs;
@@ -190,7 +178,44 @@ public void updateKeyCount() {
190178

191179
if (keyCount > this.keyCount) {
192180
this.keyCount = keyCount;
193-
this.keyCountIncludingNulls = unindexedNullCount > 0 ? keyCount + 1 : keyCount;
181+
this.keyCountIncludingNulls = columnTop > 0 ? keyCount + 1 : keyCount;
182+
}
183+
}
184+
185+
private void readIndexMetadataAtomically() {
186+
// Triple check atomic read. We read first and last sequences. If they match - there is a chance at stable
187+
// read. Confirm start sequence hasn't changed after values read. If it has changed - retry the whole thing.
188+
final long deadline = clock.getTicks() + spinLockTimeoutMs;
189+
while (true) {
190+
long seq = keyMem.getLong(BitmapIndexUtils.KEY_RESERVED_OFFSET_SEQUENCE);
191+
int keyCount;
192+
long valueMemSize;
193+
int blockValueCountMod;
194+
195+
Unsafe.getUnsafe().loadFence();
196+
if (keyMem.getLong(BitmapIndexUtils.KEY_RESERVED_OFFSET_SEQUENCE_CHECK) == seq) {
197+
blockValueCountMod = keyMem.getInt(BitmapIndexUtils.KEY_RESERVED_OFFSET_BLOCK_VALUE_COUNT) - 1;
198+
keyCount = keyMem.getInt(BitmapIndexUtils.KEY_RESERVED_OFFSET_KEY_COUNT);
199+
valueMemSize = keyMem.getLong(BitmapIndexUtils.KEY_RESERVED_OFFSET_VALUE_MEM_SIZE);
200+
201+
Unsafe.getUnsafe().loadFence();
202+
if (keyMem.getLong(BitmapIndexUtils.KEY_RESERVED_OFFSET_SEQUENCE) == seq) {
203+
this.keyFileSequence = seq;
204+
this.valueMemSize = valueMemSize;
205+
this.keyCount = keyCount;
206+
this.blockValueCountMod = blockValueCountMod;
207+
this.blockCapacity = (blockValueCountMod + 1) * 8 + BitmapIndexUtils.VALUE_BLOCK_FILE_RESERVED;
208+
this.keyCountIncludingNulls = columnTop > 0 ? keyCount + 1 : keyCount;
209+
break;
210+
}
211+
}
212+
213+
if (clock.getTicks() > deadline) {
214+
LOG.error().$(INDEX_CORRUPT).$(" [timeout=").$(spinLockTimeoutMs).$("ms]").$();
215+
throw CairoException.critical(0).put(INDEX_CORRUPT);
216+
}
217+
218+
Os.pause();
194219
}
195220
}
196221
}

‎core/src/main/java/io/questdb/cairo/BitmapIndexBwdNullReader.java‎

Lines changed: 12 additions & 6 deletions
Original file line numberDiff line numberDiff line change
@@ -30,6 +30,11 @@
3030
public class BitmapIndexBwdNullReader implements BitmapIndexReader {
3131
private final NullCursor cursor = new NullCursor();
3232

33+
@Override
34+
public long getColumnTop() {
35+
return 0;
36+
}
37+
3338
@Override
3439
public RowCursor getCursor(boolean cachedInstance, int key, long minValue, long maxValue) {
3540
final NullCursor cursor = getCursor(cachedInstance);
@@ -53,11 +58,6 @@ public long getKeyMemorySize() {
5358
return 0;
5459
}
5560

56-
@Override
57-
public long getUnIndexedNullCount() {
58-
return 0;
59-
}
60-
6161
@Override
6262
public long getValueBaseAddress() {
6363
return 0;
@@ -79,7 +79,13 @@ public boolean isOpen() {
7979
}
8080

8181
@Override
82-
public void of(CairoConfiguration configuration, Path path, CharSequence name, long columnNameTxn, long unIndexedNullCount) {
82+
public void of(CairoConfiguration configuration, Path path, CharSequence columnName, long columnNameTxn, long unIndexedNullCount) {
83+
// no-op
84+
}
85+
86+
@Override
87+
public void reloadConditionally() {
88+
// no-op
8389
}
8490

8591
private NullCursor getCursor(boolean cachedInstance) {

‎core/src/main/java/io/questdb/cairo/BitmapIndexBwdReader.java‎

Lines changed: 2 additions & 2 deletions
Original file line numberDiff line numberDiff line change
@@ -53,10 +53,10 @@ public RowCursor getCursor(boolean cachedInstance, int key, long minValue, long
5353
updateKeyCount();
5454
}
5555

56-
if (key == 0 && unindexedNullCount > 0 && minValue < unindexedNullCount) {
56+
if (key == 0 && columnTop > 0 && minValue < columnTop) {
5757
// we need to return the whole set of actual index values and then some nulls
5858
final NullCursor nullCursor = getNullCursor(cachedInstance);
59-
nullCursor.nullCount = Math.min(unindexedNullCount, maxValue + 1);
59+
nullCursor.nullCount = Math.min(columnTop, maxValue + 1);
6060
nullCursor.of(key, minValue, maxValue, keyCount);
6161
return nullCursor;
6262
}

‎core/src/main/java/io/questdb/cairo/BitmapIndexFwdNullReader.java‎

Lines changed: 11 additions & 6 deletions
Original file line numberDiff line numberDiff line change
@@ -32,6 +32,11 @@
3232
public class BitmapIndexFwdNullReader implements BitmapIndexReader {
3333
private final NullCursor cursor = new NullCursor();
3434

35+
@Override
36+
public long getColumnTop() {
37+
return 0;
38+
}
39+
3540
@Override
3641
public RowCursor getCursor(boolean cachedInstance, int key, long minValue, long maxValue) {
3742
final NullCursor cursor = getCursor(cachedInstance);
@@ -61,11 +66,6 @@ public long getKeyMemorySize() {
6166
return 0;
6267
}
6368

64-
@Override
65-
public long getUnIndexedNullCount() {
66-
return 0;
67-
}
68-
6969
@Override
7070
public long getValueBaseAddress() {
7171
return 0;
@@ -87,7 +87,12 @@ public boolean isOpen() {
8787
}
8888

8989
@Override
90-
public void of(CairoConfiguration configuration, Path path, CharSequence name, long columnNameTxn, long unIndexedNullCount) {
90+
public void of(CairoConfiguration configuration, Path path, CharSequence columnName, long columnNameTxn, long unIndexedNullCount) {
91+
}
92+
93+
@Override
94+
public void reloadConditionally() {
95+
// no-op
9196
}
9297

9398
private NullCursor getCursor(boolean cachedInstance) {

‎core/src/main/java/io/questdb/cairo/BitmapIndexFwdReader.java‎

Lines changed: 2 additions & 2 deletions
Original file line numberDiff line numberDiff line change
@@ -55,11 +55,11 @@ public RowCursor getCursor(boolean cachedInstance, int key, long minValue, long
5555
updateKeyCount();
5656
}
5757

58-
if (key == 0 && unindexedNullCount > 0 && minValue < unindexedNullCount) {
58+
if (key == 0 && columnTop > 0 && minValue < columnTop) {
5959
// we need to return some nulls and the whole set of actual index values
6060
final NullCursor nullCursor = getNullCursor(cachedInstance);
6161
nullCursor.nullPos = minValue;
62-
nullCursor.nullCount = Math.min(unindexedNullCount, maxValue + 1);
62+
nullCursor.nullCount = Math.min(columnTop, maxValue + 1);
6363
nullCursor.of(key, minValue, maxValue, keyCount);
6464
return nullCursor;
6565
}

‎core/src/main/java/io/questdb/cairo/BitmapIndexReader.java‎

Lines changed: 12 additions & 3 deletions
Original file line numberDiff line numberDiff line change
@@ -26,6 +26,7 @@
2626

2727

2828
import io.questdb.cairo.sql.RowCursor;
29+
import io.questdb.std.Transient;
2930
import io.questdb.std.str.Path;
3031

3132
import java.io.Closeable;
@@ -45,6 +46,8 @@ static CharSequence nameOf(int direction) {
4546
default void close() {
4647
}
4748

49+
long getColumnTop();
50+
4851
/**
4952
* Setup value cursor. Values in this cursor will be bounded by provided
5053
* minimum and maximum, both of which are inclusive. Order of values is
@@ -68,8 +71,6 @@ default IndexFrameCursor getFrameCursor(int key, long minValue, long maxValue) {
6871

6972
long getKeyMemorySize();
7073

71-
long getUnIndexedNullCount();
72-
7374
long getValueBaseAddress();
7475

7576
int getValueBlockCapacity();
@@ -78,5 +79,13 @@ default IndexFrameCursor getFrameCursor(int key, long minValue, long maxValue) {
7879

7980
boolean isOpen();
8081

81-
void of(CairoConfiguration configuration, Path path, CharSequence name, long columnNameTxn, long unIndexedNullCount);
82+
void of(
83+
CairoConfiguration configuration,
84+
@Transient Path path,
85+
CharSequence columnName,
86+
long columnNameTxn,
87+
long columnTop
88+
);
89+
90+
void reloadConditionally();
8291
}

‎core/src/main/java/io/questdb/cairo/ConcurrentBitmapIndexFwdReader.java‎

Lines changed: 2 additions & 2 deletions
Original file line numberDiff line numberDiff line change
@@ -77,12 +77,12 @@ public RowCursor initCursor(RowCursor rowCursor, int key, long minValue, long ma
7777
assert cursor.owner() == this;
7878
}
7979

80-
if (key == 0 && unindexedNullCount > 0 && minValue < unindexedNullCount) {
80+
if (key == 0 && columnTop > 0 && minValue < columnTop) {
8181
// we need to return some nulls and the whole set of actual index values
8282
if (cursor == null) {
8383
cursor = new Cursor();
8484
}
85-
cursor.of(key, minValue, maxValue, keyCount, minValue, unindexedNullCount);
85+
cursor.of(key, minValue, maxValue, keyCount, minValue, columnTop);
8686
return cursor;
8787
}
8888

‎core/src/main/java/io/questdb/cairo/TableReader.java‎

Lines changed: 7 additions & 21 deletions
Original file line numberDiff line numberDiff line change
@@ -252,27 +252,16 @@ public long floorToPartitionTimestamp(long timestamp) {
252252
}
253253

254254
public BitmapIndexReader getBitmapIndexReader(int partitionIndex, int columnIndex, int direction) {
255-
int columnBase = getColumnBase(partitionIndex);
256-
return getBitmapIndexReader(partitionIndex, columnBase, columnIndex, direction);
257-
}
258-
259-
public BitmapIndexReader getBitmapIndexReader(int partitionIndex, int columnBase, int columnIndex, int direction) {
255+
final int columnBase = getColumnBase(partitionIndex);
260256
final int index = getPrimaryColumnIndex(columnBase, columnIndex);
261257
final long partitionTimestamp = txFile.getPartitionTimestampByIndex(partitionIndex);
262258
final long columnNameTxn = columnVersionReader.getColumnNameTxn(partitionTimestamp, metadata.getWriterIndex(columnIndex));
263259
final long partitionTxn = txFile.getPartitionNameTxn(partitionIndex);
264260

265-
BitmapIndexReader reader = bitmapIndexes.getQuick(direction == BitmapIndexReader.DIR_BACKWARD ? index : index + 1);
261+
final int indexIndex = direction == BitmapIndexReader.DIR_BACKWARD ? index : index + 1;
262+
BitmapIndexReader reader = bitmapIndexes.getQuick(indexIndex);
266263
if (reader != null) {
267-
// make sure to reload the reader
268-
final String columnName = metadata.getColumnName(columnIndex);
269-
final long columnTop = getColumnTop(columnBase, columnIndex);
270-
Path path = pathGenNativePartition(partitionIndex);
271-
try {
272-
reader.of(configuration, path, columnName, columnNameTxn, columnTop);
273-
} finally {
274-
path.trimTo(rootLen);
275-
}
264+
reader.reloadConditionally();
276265
return reader;
277266
}
278267
return createBitmapIndexReaderAt(index, columnBase, columnIndex, columnNameTxn, direction, partitionTxn);
@@ -763,7 +752,9 @@ private long closeRewrittenPartitionFiles(int partitionIndex, int oldBase) {
763752
openPartitionCount--;
764753
return -1;
765754
}
766-
pathGenNativePartition(partitionIndex);
755+
long nameTxn = openPartitionInfo.getQuick(partitionIndex * PARTITIONS_SLOT_SIZE + PARTITIONS_SLOT_OFFSET_NAME_TXN);
756+
//noinspection resource
757+
pathGenNativePartition(partitionIndex, nameTxn);
767758
return newSize;
768759
}
769760

@@ -1180,11 +1171,6 @@ private void openSymbolMaps() {
11801171
}
11811172
}
11821173

1183-
private Path pathGenNativePartition(int partitionIndex) {
1184-
long nameTxn = openPartitionInfo.getQuick(partitionIndex * PARTITIONS_SLOT_SIZE + PARTITIONS_SLOT_OFFSET_NAME_TXN);
1185-
return pathGenNativePartition(partitionIndex, nameTxn);
1186-
}
1187-
11881174
private Path pathGenNativePartition(int partitionIndex, long nameTxn) {
11891175
formatNativePartitionDirName(partitionIndex, path.slash(), nameTxn);
11901176
return path;

‎core/src/main/java/io/questdb/griffin/engine/table/LatestByAllIndexedRecordCursor.java‎

Lines changed: 1 addition & 1 deletion
Original file line numberDiff line numberDiff line change
@@ -228,7 +228,7 @@ private void buildTreeMap() {
228228
final long valueBaseAddress = indexReader.getValueBaseAddress();
229229
final long valuesMemorySize = indexReader.getValueMemorySize();
230230
final int valueBlockCapacity = indexReader.getValueBlockCapacity();
231-
final long unIndexedNullCount = indexReader.getUnIndexedNullCount();
231+
final long unIndexedNullCount = indexReader.getColumnTop();
232232

233233
doneLatch.reset();
234234

0 commit comments

Comments
 (0)