Skip to content

A free and open source instant messaging and VoIP chat app built for friends, groups, and communities.

TypeScript fluxerfluxerapp
16.4 KB
Raw Blame
// SPDX-License-Identifier: AGPL-3.0-or-later

import {LocalDate} from '@app/api/database/LocalDate';
import {describe, expect, it} from 'vitest';
import '@app/api/Tables';
import {getTableMetadata} from '@app/api/database/CassandraMetaRegistry';
import {defineTable} from '@app/api/database/CassandraTableDsl';
import type {CassandraParams, PreparedQuery} from '@app/api/database/CassandraTypes';
import {
	buildCandidatePlan,
	type CandidatePlan,
	keyFromColumns,
	matchesWhere,
	POSTGRES_KV_MIGRATION_TABLE,
} from '@app/api/database/PostgresKvQueryExecutor';

type Row = Record<string, unknown>;

const SEPARATOR = '\u001f';

const TRICKY_STRINGS = [
	'',
	'a',
	'a"b',
	'a\\b',
	'a\u0001b',
	'a\u001fb',
	'a b',
	'a\u007fb',
	'\u{1f600}',
	'\ufffd',
	'a\u0000b',
	'b',
];

function byteCompare(left: string, right: string): number {
	return Buffer.compare(Buffer.from(left, 'utf8'), Buffer.from(right, 'utf8'));
}

function withinRange(rowKey: string, lowerBound: string, upperBound: string): boolean {
	return byteCompare(rowKey, lowerBound) >= 0 && byteCompare(rowKey, upperBound) < 0;
}

function rangeBounds(plan: CandidatePlan): Array<[string, string]> {
	if (plan.kind === 'ranges') return plan.lowerBounds.map((lower, index) => [lower, plan.upperBounds[index]!]);
	if (plan.kind === 'rangeGroups') {
		return plan.groups.flatMap((group) =>
			group.lowerBounds.map((lower, index): [string, string] => [lower, group.upperBounds[index]!]),
		);
	}
	return [];
}

function planAccepts(plan: CandidatePlan, rowKey: string): boolean {
	switch (plan.kind) {
		case 'none':
			return false;
		case 'rowKeys':
			return plan.rowKeys.includes(rowKey);
		case 'range':
			return withinRange(rowKey, plan.lowerBound, plan.upperBound);
		case 'ranges':
		case 'rangeGroups':
			return rangeBounds(plan).some(([lower, upper]) => withinRange(rowKey, lower, upper));
		case 'scan':
			return true;
	}
}

function matchingRangeCount(plan: CandidatePlan, rowKey: string): number {
	return rangeBounds(plan).filter(([lower, upper]) => withinRange(rowKey, lower, upper)).length;
}

function expectKeyShape(key: string, separators: number): void {
	let seen = 0;
	for (const byte of Buffer.from(key, 'utf8')) {
		if (byte === 0x1f) {
			seen += 1;
			continue;
		}
		expect(byte).toBeGreaterThanOrEqual(0x20);
	}
	expect(seen).toBe(separators);
}

function planOf(query: PreparedQuery) {
	const meta = query.kvMeta;
	if (!meta) {
		throw new Error('Query is missing kv metadata');
	}
	return {meta, plan: buildCandidatePlan(meta, query.params)};
}

function checkQuery(query: PreparedQuery, rows: Array<Row>): CandidatePlan {
	const {meta, plan} = planOf(query);
	const primaryKey = meta.table.primaryKey as ReadonlyArray<string>;
	const accepted: Array<Row> = [];
	const matched: Array<Row> = [];
	for (const row of rows) {
		const rowKey = keyFromColumns(primaryKey, row);
		expectKeyShape(rowKey, primaryKey.length - 1);
		expect(matchingRangeCount(plan.candidates, rowKey)).toBeLessThanOrEqual(1);
		if (planAccepts(plan.candidates, rowKey)) accepted.push(row);
		if (matchesWhere(row, meta.where, query.params)) matched.push(row);
	}
	for (const row of matched) {
		expect(accepted).toContain(row);
	}
	if (plan.exact) {
		expect(accepted).toEqual(matched);
	}
	return plan.candidates;
}

interface SingleRow {
	a: string;
	payload: string;
}

const SingleKey = defineTable<SingleRow, 'a'>({
	name: 'kv_plan_single',
	columns: ['a', 'payload'],
	primaryKey: ['a'],
});

const singleRows: Array<Row> = TRICKY_STRINGS.map((a) => ({a, payload: 'p'}));

interface PairRow {
	a: string;
	b: bigint;
	payload: string;
}

const PairKey = defineTable<PairRow, 'a' | 'b'>({
	name: 'kv_plan_pair',
	columns: ['a', 'b', 'payload'],
	primaryKey: ['a', 'b'],
});

const pairRows: Array<Row> = TRICKY_STRINGS.flatMap((a) =>
	[-1n, 0n, 9n, 10n, 1000n].map((b) => ({a, b, payload: 'p'})),
);

interface TripleRow {
	a: string;
	b: bigint;
	c: boolean;
	payload: string;
}

const TripleKey = defineTable<TripleRow, 'a' | 'b' | 'c'>({
	name: 'kv_plan_triple',
	columns: ['a', 'b', 'c', 'payload'],
	primaryKey: ['a', 'b', 'c'],
});

const tripleRows: Array<Row> = TRICKY_STRINGS.flatMap((a) =>
	[9n, 10n].flatMap((b) => [true, false].map((c) => ({a, b, c, payload: 'p'}))),
);

interface WideRow {
	a: string;
	b: bigint;
	c: boolean;
	d: Date | null;
	e: Buffer;
	f: number;
	payload: string;
}

const WideKey = defineTable<WideRow, 'a' | 'b' | 'c' | 'd' | 'e' | 'f'>({
	name: 'kv_plan_wide',
	columns: ['a', 'b', 'c', 'd', 'e', 'f', 'payload'],
	primaryKey: ['a', 'b', 'c', 'd', 'e', 'f'],
});

const wideRows: Array<Row> = ['a', 'a"b', '\u{1f600}'].flatMap((a) =>
	[9n, 10n].flatMap((b) =>
		[true, false].flatMap((c) =>
			[null, new Date('2020-01-01T00:00:00.000Z')].flatMap((d) =>
				[Buffer.from('one'), Buffer.from([0x00, 0x1f, 0xff])].flatMap((e) =>
					[1, 2].map((f) => ({a, b, c, d, e, f, payload: 'p'})),
				),
			),
		),
	),
);

describe('PostgresKvQueryExecutor candidate planner', () => {
	it('pins a single-column primary key by equality', () => {
		for (const a of TRICKY_STRINGS) {
			expect(checkQuery(SingleKey.select({where: SingleKey.where.eq('a')}).bind({a}), singleRows).kind).toBe('rowKeys');
		}
	});

	it('pins a single-column primary key by IN', () => {
		const query = SingleKey.select({where: SingleKey.where.in('a', 'ids')}).bind({
			ids: ['a', 'a\u0001b', 'a"b', 'a'],
		});
		expect(checkQuery(query, singleRows).kind).toBe('rowKeys');
	});

	it('returns nothing for an empty IN list', () => {
		for (const params of [{ids: []}, {ids: new Set<string>()}, {}]) {
			const query = SingleKey.select({where: SingleKey.where.in('a', 'ids')}).bind(params as CassandraParams);
			expect(checkQuery(query, singleRows).kind).toBe('none');
		}
	});

	it('ranges over the leading column of a composite primary key', () => {
		for (const a of TRICKY_STRINGS) {
			expect(checkQuery(PairKey.select({where: PairKey.where.eq('a')}).bind({a}), pairRows).kind).toBe('range');
		}
	});

	it('ranges over the leading column when a comparison follows', () => {
		const query = PairKey.select({where: [PairKey.where.eq('a'), PairKey.where.lt('b')]}).bind({
			a: 'a\u0001b',
			b: 10n,
		});
		expect(checkQuery(query, pairRows).kind).toBe('range');
	});

	it('emits one range per value when the leading column uses IN', () => {
		const query = PairKey.select({where: PairKey.where.in('a', 'ids')}).bind({
			ids: ['a', 'a\u0001b', 'a\u001fb', 'a'],
		});
		expect(checkQuery(query, pairRows).kind).toBe('ranges');
	});

	it('pins the full primary key across a cartesian product of IN lists', () => {
		const query = PairKey.select({where: [PairKey.where.in('a', 'ids'), PairKey.where.in('b', 'bs')]}).bind({
			ids: ['a', 'a\u007fb'],
			bs: [9n, 10n],
		});
		expect(checkQuery(query, pairRows).kind).toBe('rowKeys');
	});

	it('ranges over a two-column prefix of a three-column primary key', () => {
		for (const a of TRICKY_STRINGS) {
			const query = TripleKey.select({where: [TripleKey.where.eq('a'), TripleKey.where.eq('b')]}).bind({a, b: 9n});
			expect(checkQuery(query, tripleRows).kind).toBe('range');
		}
	});

	it('falls back to a scan when the leading column is unpinned', () => {
		const query = TripleKey.select({where: [TripleKey.where.eq('b'), TripleKey.where.eq('c')]}).bind({b: 9n, c: true});
		expect(checkQuery(query, tripleRows).kind).toBe('scan');
	});

	it('pins every column of a six-column primary key', () => {
		const query = WideKey.select({
			where: [
				WideKey.where.eq('a'),
				WideKey.where.eq('b'),
				WideKey.where.eq('c'),
				WideKey.where.eq('d'),
				WideKey.where.eq('e'),
				WideKey.where.eq('f'),
			],
		}).bind({a: '\u{1f600}', b: 10n, c: false, d: null, e: Buffer.from([0x00, 0x1f, 0xff]), f: 2});
		expect(checkQuery(query, wideRows).kind).toBe('rowKeys');
	});

	it('stops at the first gap in the primary key', () => {
		const query = WideKey.select({
			where: [WideKey.where.eq('a'), WideKey.where.eq('b'), WideKey.where.eq('f')],
		}).bind({a: 'a', b: 9n, f: 1});
		expect(checkQuery(query, wideRows).kind).toBe('range');
	});

	it('scans a table with no predicate', () => {
		expect(checkQuery(SingleKey.select().bind({}), singleRows).kind).toBe('scan');
	});
});

describe('PostgresKvQueryExecutor plan exactness', () => {
	it('is exact when the key predicate consumes every clause', () => {
		expect(planOf(PairKey.select({where: PairKey.where.eq('a')}).bind({a: 'a'})).plan.exact).toBe(true);
		expect(planOf(SingleKey.select().bind({})).plan.exact).toBe(true);
	});

	it('is inexact when a clause is left for the JavaScript filter', () => {
		const bounded = PairKey.select({where: [PairKey.where.eq('a'), PairKey.where.lt('b')]}).bind({a: 'a', b: 9n});
		expect(planOf(bounded).plan.exact).toBe(false);
		expect(planOf(TripleKey.select({where: TripleKey.where.eq('b')}).bind({b: 9n})).plan.exact).toBe(false);
	});

	it('is inexact when a limit or an order is present', () => {
		expect(planOf(PairKey.select({where: PairKey.where.eq('a'), limit: 5}).bind({a: 'a'})).plan.exact).toBe(false);
		const ordered = PairKey.select({where: PairKey.where.eq('a'), orderBy: {col: 'b'}}).bind({a: 'a'});
		expect(planOf(ordered).plan.exact).toBe(false);
	});

	it('is inexact when a pinned value has no stable key encoding', () => {
		expect(planOf(SingleKey.select({where: SingleKey.where.eq('a')}).bind({a: {}})).plan.exact).toBe(false);
		expect(planOf(SingleKey.select({where: SingleKey.where.eq('a')}).bind({a: Number.NaN})).plan.exact).toBe(false);
	});

	it('is exact for an empty IN list regardless of the other clauses', () => {
		const query = PairKey.select({where: [PairKey.where.in('a', 'ids'), PairKey.where.lt('b')], limit: 3}).bind({
			ids: [],
			b: 9n,
		});
		expect(planOf(query).plan.exact).toBe(true);
	});
});

describe('PostgresKvQueryExecutor plan totality', () => {
	it('leaves a column unpinned when its value has no key encoding at all', () => {
		const invalid = PairKey.select({where: PairKey.where.eq('a')}).bind({a: new Date('nope')});
		const {plan} = planOf(invalid);
		expect(plan.candidates.kind).toBe('scan');
		expect(plan.exact).toBe(false);
	});

	it('leaves a trailing column unpinned without losing the leading prefix', () => {
		const query = PairKey.select({where: [PairKey.where.eq('a'), PairKey.where.eq('b')]}).bind({
			a: 'a',
			b: new Date('nope') as never,
		});
		const {plan} = planOf(query);
		expect(plan.candidates.kind).toBe('range');
		expect(plan.exact).toBe(false);
	});

	it('does not treat a scalar bound to an IN parameter as an iterable', () => {
		const query = SingleKey.select({where: SingleKey.where.in('a', 'ids')}).bind({ids: 'ab' as never});
		const {plan} = planOf(query);
		expect(plan.candidates.kind).toBe('scan');
		expect(plan.exact).toBe(false);
	});
});

describe('PostgresKvQueryExecutor plan size caps', () => {
	it('keeps a full primary key product as row keys rather than demoting it to ranges', () => {
		const ids = Array.from({length: 30}, (_, i) => `id${i}`);
		const seqs = Array.from({length: 30}, (_, i) => BigInt(i));
		const query = PairKey.select({where: [PairKey.where.in('a', 'ids'), PairKey.where.in('b', 'seqs')]}).bind({
			ids,
			seqs,
		});
		const {plan} = planOf(query);
		expect(plan.candidates.kind).toBe('rowKeys');
		expect(plan.exact).toBe(true);
		if (plan.candidates.kind !== 'rowKeys') return;
		expect(plan.candidates.rowKeys.length).toBe(900);
	});

	it('chunks the prefix ranges into groups instead of degrading to a scan', () => {
		const under = TripleKey.select({where: TripleKey.where.in('a', 'ids')}).bind({
			ids: Array.from({length: 256}, (_, i) => `id${i}`),
		});
		expect(planOf(under).plan.candidates.kind).toBe('ranges');
		const over = TripleKey.select({where: TripleKey.where.in('a', 'ids')}).bind({
			ids: Array.from({length: 700}, (_, i) => `id${i}`),
		});
		const {plan} = planOf(over);
		expect(plan.candidates.kind).toBe('rangeGroups');
		expect(plan.exact).toBe(true);
		if (plan.candidates.kind !== 'rangeGroups') return;
		expect(plan.candidates.groups.map((group) => group.lowerBounds.length)).toEqual([256, 256, 188]);
		expect(plan.candidates.groups.map((group) => group.upperBounds.length)).toEqual([256, 256, 188]);
	});

	it('brackets exactly the matching rows once the prefix ranges are chunked', () => {
		const ids = [...TRICKY_STRINGS, ...Array.from({length: 260}, (_, i) => `id${i}`)];
		const query = TripleKey.select({where: TripleKey.where.in('a', 'ids')}).bind({ids});
		expect(checkQuery(query, tripleRows).kind).toBe('rangeGroups');
	});

	it('falls back to a scan when even the leading column blows the combination bound', () => {
		const query = TripleKey.select({where: TripleKey.where.in('a', 'ids')}).bind({
			ids: Array.from({length: 32_769}, (_, i) => `id${i}`),
		});
		const {plan} = planOf(query);
		expect(plan.candidates.kind).toBe('scan');
		expect(plan.exact).toBe(false);
	});

	it('applies the cap to distinct IN values rather than to duplicates', () => {
		const query = TripleKey.select({where: TripleKey.where.in('a', 'ids')}).bind({
			ids: Array.from({length: 300}, (_, i) => `id${i % 50}`),
		});
		const {plan} = planOf(query);
		expect(plan.candidates.kind).toBe('ranges');
		if (plan.candidates.kind !== 'ranges') return;
		expect(plan.candidates.lowerBounds.length).toBe(50);
	});

	it('applies the row key combination bound to distinct products too', () => {
		const query = PairKey.select({where: [PairKey.where.in('a', 'ids'), PairKey.where.in('b', 'seqs')]}).bind({
			ids: Array.from({length: 200}, (_, i) => `id${i % 50}`),
			seqs: Array.from({length: 200}, (_, i) => BigInt(i % 50)),
		});
		const {plan} = planOf(query);
		expect(plan.candidates.kind).toBe('rowKeys');
		if (plan.candidates.kind !== 'rowKeys') return;
		expect(plan.candidates.rowKeys.length).toBe(2500);
	});

	it('enforces the cap even when the trailing pinned column is an equality', () => {
		const ids = Array.from({length: 40}, (_, i) => `id${i}`);
		const query = WideKey.select({
			where: [WideKey.where.in('a', 'ids'), WideKey.where.in('b', 'seqs'), WideKey.where.eq('c')],
		}).bind({ids, seqs: Array.from({length: 40}, (_, i) => BigInt(i)), c: true});
		const {plan} = planOf(query);
		expect(plan.candidates.kind).toBe('ranges');
		expect(plan.exact).toBe(false);
		if (plan.candidates.kind !== 'ranges') return;
		expect(plan.candidates.lowerBounds.length).toBe(40);
	});
});

describe('PostgresKvQueryExecutor prefix bounds', () => {
	it('brackets exactly the rows sharing the pinned prefix', () => {
		const {plan} = planOf(PairKey.select({where: PairKey.where.eq('a')}).bind({a: 'a'}));
		expect(plan.candidates.kind).toBe('range');
		if (plan.candidates.kind !== 'range') return;
		expect(plan.candidates.lowerBound).toBe(`"a"${SEPARATOR}`);
		expect(plan.candidates.upperBound).toBe('"a" ');
		expect(byteCompare(plan.candidates.lowerBound, plan.candidates.upperBound)).toBeLessThan(0);
	});
});

describe('PostgresKvQueryExecutor key equality', () => {
	const eqWhere = [{kind: 'eq', col: 'a', param: 'a'}] as never;
	const corpus: Array<[string, unknown]> = [
		['null', null],
		['undefined', undefined],
		['empty-string', ''],
		['date-string', '2020-01-01'],
		['days-string', '18262'],
		['zero', 0],
		['neg-zero', -0],
		['number', 18262],
		['bigint', 18262n],
		['true', true],
		['false', false],
		['date', new Date('2020-01-01T00:00:00.000Z')],
		['buffer', Buffer.from('2020-01-01')],
		['local-date', LocalDate.fromString('2020-01-01')],
		['other-local-date', LocalDate.fromString('2021-06-05')],
	];

	it('accepts an equality exactly when both sides share a row key', () => {
		const deltas: Array<string> = [];
		for (const [storedName, stored] of corpus) {
			for (const [paramName, param] of corpus) {
				const accepted = matchesWhere({a: stored}, eqWhere, {a: param} as CassandraParams);
				const sameKey = keyFromColumns(['a'], {a: stored}) === keyFromColumns(['a'], {a: param});
				if (accepted !== sameKey)
					deltas.push(`stored=${storedName} param=${paramName} match=${accepted} key=${sameKey}`);
			}
		}
		expect(deltas).toEqual([]);
	});

	it('does not equate a LocalDate with its string rendering', () => {
		const localDate = LocalDate.fromString('2020-01-01');
		expect(matchesWhere({a: localDate}, eqWhere, {a: localDate} as CassandraParams)).toBe(true);
		expect(matchesWhere({a: localDate}, eqWhere, {a: '2020-01-01'} as CassandraParams)).toBe(false);
		expect(matchesWhere({a: '2020-01-01'}, eqWhere, {a: localDate} as CassandraParams)).toBe(false);
	});
});

describe('PostgresKvQueryExecutor migration bookkeeping', () => {
	it('reserves a table name that no logical table can claim', () => {
		expect(POSTGRES_KV_MIGRATION_TABLE.startsWith('__')).toBe(true);
		expect(getTableMetadata(POSTGRES_KV_MIGRATION_TABLE)).toBeUndefined();
	});
});