4 ms·
if your doing a join on two size N tables, your O(n) cost for each record is N, thus you are doing N^2 lookups. basically reading the entire DB into memory eac
by autokad 9y ago
if your doing a join on two size N tables, your O(n) cost for each record is N, thus you are doing N^2 lookups. basically reading the entire DB into memory each record.
- parasubvert 9y agoNo. Worst case a nested join of two tables M and N would be O(MN). But most real databases would have a merge or hash join which could bring this down to O(M+N) if the tables are already stored in a sorted indexed order. It is also rare the cardinality of these databases will be similar in an analytical query - usually you have one time series “fact table” and a bunch of dimensions to enrich that data. If I’m doing analytics on a time series this gets even better with partition pruning and hash joins or bitmap indexes. And if I have a columnar database, that blows up this whole complexity argument. My point is that, layout and indexes should never be assumed to be one size fits all. Keep in mind if I’m doing analytics I want to bring my time series data into memory at least as a stream, as I need to calculate / filter / transform the records. Not everything is about rendering a page on a website.