Techniques are described herein for probabilistic monitoring of high-frequency, low-latency database queries. In some embodiments, a probabilistic query monitoring system periodically samples active database sessions. For example, the system may generate sample data every one second or at some other sampling rate for each database session that is currently active. The sample data may include a mapping between query identifiers to sample counter values that are extracted at different sample intervals. The system may then estimate performance metrics for the set of active database based on the counter values sampled across consecutive sample intervals.