4 ms·

Does anyone know why something like binary search isn't a first simple choice for skipping to the next unique item, if the index is ordered? Is it because of t

Does anyone know why something like binary search isn't a first simple choice for skipping to the next unique item, if the index is ordered? Is it because of the tree structure of the index?

fny 5y ago
Very rough sketch. Say you have a table with two rows. One is time, the other is temperature. Your table is sorted by time, but you want all the unique temperatures. Given the temperatures are unordered, you can't perform a binary search. If you also create a proper index against the times, your temperatures will also live in leaves of a tree that you'll need to access to get the values. So trick 1 is to just index that column, like you said, a precomputed binary search if you will But since we're interested in distinct queries, we can optimize further by pointing to the next greatest value with the index tree too (hence skip scan.)
- zmmmmm 5y ago
  > Say you have a table with two rows You mean two columns, right?
djk447 5y ago
(Disclaimer: I'm an engineer at Timescale, I didn't work directly on this feature but have some knowledge of what it does). I'm not 100% sure I understand exactly what you're asking, but, perhaps some more info will be useful. First off, the goal with this isn't just to find the next unique item, it's to find the set of all the unique items, so you'd need to iterate the search, which is basically what the skipscan is doing internally. Internally, the index is using something like a binary search (it's a btree, so slightly different, IIRC) to skip to the next unique item. A lot of the work here was in teaching the planner / executor to actually do that rather than the simpler, less efficient way that PG usually does it (brute force unique over a full scan). There's some more complexity on top of that in terms of teaching it to do that over all the chunks and then combine the results (because each has a separate index) and some more complexity in terms of knowing when you can use multi-column indexes and the like, but at its most basic level, it basically is using some sort of binary search to find the next item. But perhaps I'm missing what you're asking, feel free to clarify if I can better help here...
- knuthsat 5y ago
  If index is ordered, I imagined it as a flat array. I would go to the next bigger item using binary search. I guess SkipScan does a similar thing but the index is a btree. Of course, things get more complicated when more tuples need to be distinct but I was a bit confused as to why the ordered property was not exploited by PG before (and still is not).
efficax 5y ago
Walking a btree just is binary search (effectively, although btrees have more than two branches and leaves)

Does anyone know why something like binary search isn't a first simple choice for skipping to the next unique item, if the index is ordered? Is it because of the tree structure of the index?

fny 5y ago

Very rough sketch. Say you have a table with two rows. One is time, the other is temperature. Your table is sorted by time, but you want all the unique temperatures. Given the temperatures are unordered, you can't perform a binary search. If you also create a proper index against the times, your temperatures will also live in leaves of a tree that you'll need to access to get the values. So trick 1 is to just index that column, like you said, a precomputed binary search if you will But since we're interested in distinct queries, we can optimize further by pointing to the next greatest value with the index tree too (hence skip scan.)

zmmmmm 5y ago
> Say you have a table with two rows You mean two columns, right?

djk447 5y ago

(Disclaimer: I'm an engineer at Timescale, I didn't work directly on this feature but have some knowledge of what it does). I'm not 100% sure I understand exactly what you're asking, but, perhaps some more info will be useful. First off, the goal with this isn't just to find the next unique item, it's to find the set of all the unique items, so you'd need to iterate the search, which is basically what the skipscan is doing internally. Internally, the index is using something like a binary search (it's a btree, so slightly different, IIRC) to skip to the next unique item. A lot of the work here was in teaching the planner / executor to actually do that rather than the simpler, less efficient way that PG usually does it (brute force unique over a full scan). There's some more complexity on top of that in terms of teaching it to do that over all the chunks and then combine the results (because each has a separate index) and some more complexity in terms of knowing when you can use multi-column indexes and the like, but at its most basic level, it basically is using some sort of binary search to find the next item. But perhaps I'm missing what you're asking, feel free to clarify if I can better help here...

knuthsat 5y ago
If index is ordered, I imagined it as a flat array. I would go to the next bigger item using binary search. I guess SkipScan does a similar thing but the index is a btree. Of course, things get more complicated when more tuples need to be distinct but I was a bit confused as to why the ordered property was not exploited by PG before (and still is not).

efficax 5y ago

Walking a btree just is binary search (effectively, although btrees have more than two branches and leaves)