****************************** BASIC APPROACH ******************************* ============================================================================= * To make fast graphs we are reducing actual number of points for processing. Basicaly, if we need to display picture 600x600 we need not more than 600 points. To get this points from the (possibly) huge amount of real data we are using two step algorithm. First Step ---------- * At first step we dividing the actual time window (whole interval we are interested in) in the N intervals and aggregating the data over it. For each interval we know - Interval start - Interval width - Number of data points within interval - Aggregated values for all channels (MIN, MAX, MEAN) - In the future versions over aggregated types like (MEDIAN) could be added - Optionaly we could have information about maximal data gap on the interval (please consider "DATA GAPS" section for information about precision) * Of course the database requests obtaining this information over big intervals would take a lot of time. Therefore, we have CACHE tables containing aggregated information for few standard interval sizes (configurable depending on the expected data rate). When data request is comming, we are: 1) Checking if the required intervals are quite close to one of CACHE tables and returning information from appropriate CACHE table if so. 2) Otherwise, we are aggregating the data from the biggest possible CACHE which still would provide enough data points (when aggregated) 3) For small intervals, the aggregation over raw data table is executed. However, it do not take much time on the small interval size. * The only problem is cases when we have few small periods with very high update rate, while the rest of data is sampled with much lower frequences. In that case it makes no sense (and will take a lot of disk space) to make CACHE table for aggregation. But amount of data in specific places is to much for in-place aggregation and, therefore, this places would be displayed with big delay. To handle such situation, we are using so called subcaches. [ WILL BE INTRODUCED in the next version ] Second Step ----------- * On second step we are converting intervals to the data points. Actually we using several approaches to get different view of the data. Just smoth averaged graph to get impression on the global processes. The MIN-MAX approach representing all extrim values of data channels, etc. MINMAX APPROACH =============== N + 1 points are used for representing N intervals. * Points are set in the begining, end and between all intervals. * For placing Y the following MIN-MAX-MIN algorithm is used. Consider two intervals: (min1,max1), (min2,max2). The following free points (a,b,c) will be used. 1. starting from minimum: a = min1 2. looking if second interval completely above as a) if so, puting b = min2 - location: begining of second interval - next iteration we will continue rise (at least to max2) b) otherwise, b is MAX(max1, max2) - location: end of ivl1 or begining of ivl2 - next iteration will umenshatsya. 3. c = max2 or min2 depending on previous step * All points are proccessed in the chunk and, therefore, we would have only one extra point compared to number of intervals. Handling Gaps ------------- * The described procedure should be interupted if we got a gap in the data. Otherwise we would get high precision problems. However, for each brake we would have extra point which would break specified limit of points. In order to handle that problem, we ignoring small gaps and restarting algorithm only if there are enough space in the gap for another point I.E. we normally do not put points in the gap area. Therefore, if we expect a point to be put there (if it would not be a gap), we consider that we have an extra (saved) point and are allowed to restart algorithm. * To find a mimimal size of gap, for which we are restarting algorithm, we are estimating the 'expected' gap between sequent points. When we dealing with non-raw (CACHE) data this value is exact (the 'resolution', window / interval width and maximal allowed number of points '$limit' - is used for calculation). Things a little bit more complicated while dialing with raw data. We do not actually know how much data points will be found. However, this value should be below limit. It would cause very often restarts in the cases if were are in reality much less points than allowed. To handle that case, we are differntly treating the intervals with a single data point inside. If we are out of our algorithm (just starting or after restart) we just puting the points in appropriate place without starting algorithm. Of course, if we are already processing the data using MINMAX algorithm, we would continue while the points within allowed range from each other. So, summarizing: a) if we have high density of points, the distance between points will fit in the approximated range. They would be aggregated and there will be no intervals with single point. Therefore, standard processing using MIN-MAX algorithm is used. b) if we have low density of points we will have single-point intervals and will process them directly. c) In the mixed cases, when we have variable density over interval. The MINMAX algorithm would exit on first single-alone (single point, and located away from others) point and enter MINMAX mode again then the dense area begins. * This all was not about reporting missing data to the user, this gap could be completely OK from data collecting point of view. Reporting Gaps -------------- If "CACHE::REPORT_EMPTY" mode is switched on and there is intervals without data present, this intervals will be reported. Normally, missing data just silently ignored. - Missing points on the edges are not reported. - Gaps bellow doubled 'expected' gap (see section Handling Gaps above) are not reported . - By default only the gaps above interval size in minimal used CACHE table are reported. However, the minimal size could be adjusted in configuration on per group basis. Expected Position Error ----------------------- Maximal error for this approximation is 2 intervals. Consider folowing case: ---.-|-.--- (3 intervals, with short drop within one of them). This case could be handled a) \\\.///.--- b) ---.\\\./// I.e. in any case the some lines are actually two intervals away from the real value ***************************** DATA AGGREGATION ****************************** ============================================================================= DATA GAPS ========= There are two parts in the data gap calculation code: creating caching tables, aggregating the data from caching tables. 1. The 'missing' attribute in non-raw caching tables are used to store maximal gap in the data. The current code have limited precision, the real gap is in the following range: "missing <= real_gap < 3 x missing". This is because of edge cases. For example we have two cache levels: 60 and 10, and if we have following sequence of 10th: |. |,| |,| .| single point in the begining, no points, single point in the end. The current algorithm will produce only 'missing=10' for encompassing cache60. [ We don't check edges, if there would be no points in the first and third intervals, the result would be correct - 30. ] 2. For speed reasons we perform aggregation on the database side, not in PHP. Unfortunatelly, there is no flexible way to process sequential rows and found the distance between them (or when the amount of points drops to 0 and rises again) [ actually there is a non standard way for doing that, but it doesn't work in php, only from mysql client, and it considers undocumented behaviour wich could change in the future versions of mysql. The way is based on variables and sequence of their evaluation. The example is looking, like: SELECT UNIX_TIMESTAMP(MIN(time)) AS timestamp, COUNT(*) AS items, (UNIX_TIMESTAMP(MAX(time)) - UNIX_TIMESTAMP(MIN(time))) AS width, MAX(IF(@tmpvar_pos=FLOOR((UNIX_TIMESTAMP(`time`) - 1185781200 )/171.428571429), (UNIX_TIMESTAMP(time)-@tmpvar_width), 0)) AS maxgap, @tmpvar_pos:=FLOOR((UNIX_TIMESTAMP(`time`) - 1185781200 )/171.428571429) AS tmpcol1, @tmpvar_width:=UNIX_TIMESTAMP(time) AS tmpcol2, MIN(v1) AS min0, MAX(v1) AS max0, AVG(v1) AS mean0 FROM `cache0__katrin__hauptspektrometer__0` WHERE ((`time`>= 20070730074000) AND (`time` < 20070730080000)) GROUP BY FLOOR((UNIX_TIMESTAMP(`time`) - 1185781200 )/171.428571429) ORDER BY `time` ASC; At the moment we just expect what the data is unifromly distributed over aggregated intervals. This could lead to ever bigger gaps inaccuracy. However, approximated gap values still do not exceed real value. In the future versions we should implement the precise way of gap calculation using stored functions for processing sequential rows. ******************************* OPTIONS ************************************* ============================================================================= Global options ============== Various per-group options ========================= * fill_raw_first Fill RAW cache table completely prior to processing agregating cache tables This is mainly intended for sources without correct indexes. In such situations selecting the data for a specified time interval make take a while (database engines iterates over whole dataset finding matching rows, instead looking in index). Therefore, we are doing only a single request to the datasource to make it only once. The tests, however, shown that this method is slightly faster than default one (31s agains 39s) and, therefore, could be used to optimize speed even if indexes are okey. [ Actually this is really dependent on relative performance of data source server and the caching server and, therefore, it's better recheck if it's really optimizion not slowdown. ]