DST Lezione 22 - Streaming Data and Columnar Databases
Sources:
- Lecture
Streaming data
Stream data is by definition infinite. An infinte stream of data cannot be stored and conseguently you can’t use algorithms that need multiple passes over the same data.
The first challenge is how to store this data? How to query this data?
Problem: If you do the query at
Simplest case: If you have only 1 query, then you can simply do costantly queries and check any new data.
In general: If you have hundreds of queries with different conditions, it gets unmanageable to check every new piece of data because the system would constantly run queries, consuming lots of memory and resources.
Window Intervals
To manage this problem, you need a mechanism of windowing or batching.
CQL There are variations of SQL for stream data, like CQL (Continuous Query Language) from Stanford. It’s an old but still usable project from a reliable source. Think of CQL as SQL with a windowing clause at the end of the query.
A window is like a partition by time.
Different kind of partitions
What types of windows can you have?
- Regular time intervals
- Irregular time intervals
- Overlapping intervals
- Weighted intervals
(4) and (3) can be combined with each other and with regular or irregular time intervals.
Regular interval
----|-------|--------|-------|----
t1 t2 t3 t4
This means that:
Irregular interval
----|----|-------------|-------|--------->
t1 t2 t3 t4
In this case
Overlapping windows
t3 t4
|#| |###|
---#|----|###-------->
t1 t2
There is an overlap (# significa overlap, magari fai un disegno mo che sistemi gli appunti)
Weighted windows
A weighted interval assigns different weights or importance to data points within the window.
You could have any combination of these four. It depends on the use case and you cannot know in advantage.
Example - alert system
Example: suppose you want an alert system. It’s a stream of data that comes from a sensor like a camera. The stream is endless. If it’s an alert you don’t need to store the data, it’s enough to see if the data is coherent or if it overcomes a threshold - in general if trigger the data. In this case regular interval and they must be quite short because as long as there is anomaly you want to send an alert. You would then send a query like select * from my data streams where values > threshold and for each batch you send the query and eventually you trigger an alarm with this threshold. In this case it doesn’t make sense to store data. Everything is real time
Imagine an alert system using a sensor, like a camera, streaming endless data. For alerts, you don’t need to store the data. You just check if the data is coherent or surpasses a threshold to trigger an alert. You’d set regular, short intervals because you want to catch anomalies quickly. Your query would be like:
select * from my data streams where values > thresholdand for each window, you’d check and trigger an alarm if needed.
In this case, it’s all-real time, so no need to store the data.
Example - weather forecasting
For weather forecasting, you need data from multiple sensors, like humidity, wind speed and so on. There are multiple source of data, a complex algorithm with time-related dependencies. Like, if it’s raining now, it likely was raining ten minutes ago and might rain in ten minutes (time correlation).
But yesterday’s rain doesn’t matter much, in fact recent values are more important. So the best kind of window would be a weighted regular 24-hour time window. Assigning low weight to older data and higher weight to recent data.
Pub-Sub model
In the Pub-Sub model, publishers (pubs) send data to a database, and subscribers (subs) get data from the pubs. You can have one or more topics (Apache Kafka uses the term “Topics”). Publishers send their messages to specific topics, which are collections of data.
There are two main schemas: push-based and pull-based.
Push based schema
In a push-based system, subs are notified of new topics. The downside of the push schema is the coordinator has to keep track of each subscriber and send notifications, which creates overhead.
Also, push-based systems send data immediately, but there’s no guarantee the sub received it.
The coordinator know if it has sent data and data is sent as soon as it arrives, so there is no way a subscriber could lose a message.
Pull based schema
In a pull-based system, subscribers have the responsability to check each topic for new data.
Pull-based systems ensure subs get all messages, even if not in real time, by sending all missed messages later.
Apache Kafka
Apache Kafka is pull based, not push based, so the coordinator has to keep track of the list of each messages. That’s a very convenient schema, you have multiple sensors and writers and you have a cache of the most recent data and forward data to the subscribers.
Concept drift
Concept drift is when the pattern you’re observing changes significantly. For example, if a room suddenly gets loud, that’s concept drift—not an error, but a real change in the phenomenon.
Concept drift happens when the probability distribution changes, either in parameters, shape, or both. It differs from accidental errors, which are just regular variations with respect to the base shape or parameter.
Detecting drift early is tough because you need to see if these changes are systematic. There are methods to analyze and estimate this drift.
Concept Drif Example
Imagine you have a room with temperature sensors that usually fluctuate between 20°C and 15°C. Let’s say your alert system triggers at 40°C. Now, if you install a big server that runs all day, it might heat up the room, pushing the temperature to around 30°C. You’re faced with a drift—you might need to adjust your threshold, but first, you need to detect that change.
Detecting drift is tricky. You have to sample data, estimate distributions before, during, and after the change. In this scenario, you’d still use windowing, but with a twist—you’d need to roll in new data and roll out the old stuff as it becomes outdated.
You can do this in relational systems, like CQL. In other cases if you need a pub-sub system you can use Apache Kafka.
Streaming data doesn’t apply to movies because streaming require just massive hardware, multiple copies, huge amount of ram and there is nothing to optimize.
CQL
Souce:
Example from Page 19 of the pdf:
SELECT A.Seller, MAX(P.cost):
FROM Auctions [PARTITION BY A.seller ROWS 10] AS A,
Purchases ad P
WHERE A.auction_id=P.auction_id
GROUP BY A.seller;It is also implemented in Oracle.
Columnar Databases
Columnar databases can be SQL-based or not. The key difference is how they store data—instead of by rows, they organize data by columns. (We talked about Column wise organization of pages).
What happens instead if we store the data column wise? Well, instead of having one big table, you break it down into smaller ones. For instance, let’s say you’ve got a table with student IDs and surnames in one, then student IDs and regions in another, and so forth. Each table focuses on specific attributes, making it easier to manage.
The primary key is required otherwise we can’t get the full record again. For each of these attributes i have to compute the record size, BFR and number of pages of pages.
The total number of pages required to store the entire table will be obtained by summing the number of pages of each smaller table.
Generally speaking, the, record size and number of pages of the individual tables will be smaller (and BFR higher).
Advantage
When you need to fetch just one column, it’s very fast. Think analytics—calculating stuff like averages and counts will require less computational power when you’re working with just a single column.
Indexing
If you would do indexing, what kind of indexing would you use? Bitmap Indexing.
Disadvantage
The problem with columnar database is that if you want the whole record tricky. You have to do join multiple tables to piece it together, which can slow things down.
Avoiding storing the primary key
There are some smart workarounds to avoid using the primary key, like using inverted indexes or sorting data. Sorting data works because you know by the position of data which value corresponds to which primary key.
Where are columnar databases most used?
Columnar databases shine brightest in data warehousing and business analytics.
You can have the best of both worlds (columnar and non-columnar) by mirroring data—though it’ll gobble up more memory. Also, you can pick which database to query based on the specific query you’re running.
SADAS
SADAS is a company in Naples that developed one of the first columnar databases. (Tirocinioooo?)