2b:null 2c:["$","title",null,{"children":"Inside VertiPaq: Bucket Splitting Animation | hugoberry | Observable"}] 31:T55f,sampleData = [ { id: 0, Category: "Electronics", Region: "West", Year: 2026 }, { id: 1, Category: "Books", Region: "East", Year: 2025 }, { id: 2, Category: "Electronics", Region: "East", Year: 2026 }, { id: 3, Category: "Clothing", Region: "West", Year: 2026 }, { id: 4, Category: "Electronics", Region: "West", Year: 2025 }, { id: 5, Category: "Books", Region: "West", Year: 2026 }, { id: 6, Category: "Electronics", Region: "East", Year: 2026 }, { id: 7, Category: "Clothing", Region: "East", Year: 2025 }, { id: 8, Category: "Electronics", Region: "West", Year: 2026 }, { id: 9, Category: "Books", Region: "East", Year: 2026 }, { id: 10, Category: "Electronics", Region: "West", Year: 2026 }, { id: 11, Category: "Clothing", Region: "West", Year: 2025 }, { id: 12, Category: "Electronics", Region: "East", Year: 2026 }, { id: 13, Category: "Books", Region: "West", Year: 2026 }, { id: 14, Category: "Electronics", Region: "West", Year: 2026 }, { id: 15, Category: "Clothing", Region: "East", Year: 2026 }, { id: 16, Category: "Electronics", Region: "West", Year: 2026 }, { id: 17, Category: "Books", Region: "East", Year: 2025 }, { id: 18, Category: "Electronics", Region: "East", Year: 2026 }, { id: 19, Category: "Clothing", Region: "West", Year: 2026 } ]32:T796,utils = ({ calcBits(n) { return n <= 1 ? 0 : Math.ceil(Math.log2(n)); }, buildHistogram(data, rowOrder, bucket, colName) { const counts = new Map(); for (let i = bucket.start; i <= bucket.end; i++) { const row = data.find(d => d.id === rowOrder[i]); const val = row[colName]; counts.set(val, (counts.get(val) || 0) + 1); } return Array.from(counts.entries()) .map(([value, count]) => ({ value, count })) .sort((a, b) => b.count - a.count); }, analyzeColumns(data, rowOrder, bucket, cols) { const analysis = cols.map(col => { if (bucket.done.includes(col.name)) { return { column: col.name, color: col.color, skipped: true }; } const hist = this.buildHistogram(data, rowOrder, bucket, col.name); const bits = this.calcBits(hist.length); const best = hist[0] || { value: null, count: 0 }; return { column: col.name, color: col.color, histogram: hist, value: best.value, frequency: best.count, bitsPerValue: bits, savings: best.count * bits, skipped: false }; }); const candidates = analysis.filter(a => !a.skipped && a.savings > 0); const winner = candidates.length > 0 ? candidates.reduce((a, b) => a.savings > b.savings ? a : b) : null; return { analysis, winner }; }, partitionRows(data, rowOrder, bucket, column, targetValue) { const slice = rowOrder.slice(bucket.start, bucket.end + 1); const match = [], nonMatch = []; slice.forEach(id => { const row = data.find(d => d.id === id); (row[column] === targetValue ? match : nonMatch).push(id); }); const newOrder = [...rowOrder]; [...match, ...nonMatch].forEach((id, i) => { newOrder[bucket.start + i] = id; }); return { newOrder, matchCount: match.length, nonMatchCount: nonMatch.length }; } })33:Tabf,function stepAnimation(s, data, cols) { // Stop if already complete if (s.phase === "complete") return s; // Save snapshot without history to avoid exponential growth const snapshot = { frame: s.frame, rowOrder: [...s.rowOrder], buckets: JSON.parse(JSON.stringify(s.buckets)), currentBucket: s.currentBucket, winner: s.winner ? {...s.winner} : null, phase: s.phase, matchCount: s.matchCount, nonMatchCount: s.nonMatchCount }; const next = { ...snapshot, history: [...s.history, snapshot].slice(-50) // Limit history }; next.frame++; // Safety limit if (next.frame > 200) { next.phase = "complete"; return next; } const activeIdx = next.buckets.findIndex(b => b.done.length < cols.length && (b.end - b.start + 1) >= config.minBucketSize ); if (activeIdx === -1) { next.phase = "complete"; return next; } next.currentBucket = activeIdx; const bucket = next.buckets[activeIdx]; switch (next.phase) { case "initial": next.phase = "histogram"; break; case "histogram": next.phase = "calculate"; break; case "calculate": { const { winner } = utils.analyzeColumns(data, next.rowOrder, bucket, cols); next.winner = winner; if (winner) { next.phase = "reorder"; } else { bucket.done = cols.map(c => c.name); const hasWork = next.buckets.some(b => b.done.length < cols.length && (b.end - b.start + 1) >= config.minBucketSize ); next.phase = hasWork ? "histogram" : "complete"; } break; } case "reorder": { const { newOrder, matchCount, nonMatchCount } = utils.partitionRows( data, next.rowOrder, bucket, next.winner.column, next.winner.value ); next.rowOrder = newOrder; next.matchCount = matchCount; next.nonMatchCount = nonMatchCount; next.phase = "split"; break; } case "split": { const { matchCount, nonMatchCount, winner } = next; if (nonMatchCount > 0 && matchCount >= config.minBucketSize) { const pure = { start: bucket.start, end: bucket.start + matchCount - 1, done: [...bucket.done, winner.column] }; const impure = { start: bucket.start + matchCount, end: bucket.end, done: [...bucket.done] }; next.buckets.splice(activeIdx, 1, pure, impure); } else { bucket.done.push(winner.column); } const hasWork = next.buckets.some(b => b.done.length < cols.length && (b.end - b.start + 1) >= config.minBucketSize); next.phase = hasWork ? "histogram" : "complete"; next.winner = hasWork ? null : next.winner; break; } } return next; }34:T9ec,function renderTable(data, rowOrder, buckets, winner, phase) { const { tableWidth: w, rowHeight: h } = config; const height = h * (rowOrder.length + 1) + 10; const colX = { id: 0, Category: 35, Region: 125, Year: 195 }; const svg = d3.create("svg").attr("width", w).attr("height", height) .attr("font-family", "system-ui").attr("font-size", "11px"); // Header const hdr = svg.append("g").attr("transform", "translate(8,0)"); Object.keys(colX).forEach(col => { hdr.append("text").attr("x", colX[col]).attr("y", 14) .attr("font-weight", "bold") .attr("fill", columns.find(c => c.name === col)?.color || "#374151") .text(col === "id" ? "Row" : col); }); // Rows const rows = svg.append("g").attr("transform", `translate(8,${h})`); rowOrder.forEach((rowId, idx) => { const row = data.find(d => d.id === rowId); const y = idx * h; const bucket = buckets.find(b => idx >= b.start && idx <= b.end); const isActive = buckets.indexOf(bucket) === state.currentBucket; // Background let bg = "#fff"; if (bucket?.done.length > 0 && bucket.end - bucket.start < 6) bg = config.pureColor + "18"; else if (isActive) bg = config.activeColor + "12"; if (winner && phase === "reorder" && row[winner.column] === winner.value) { bg = config.highlightColor + "35"; } rows.append("rect").attr("x", -4).attr("y", y).attr("width", w - 8).attr("height", h - 2) .attr("fill", bg).attr("rx", 3); // Values rows.append("text").attr("x", colX.id).attr("y", y + 14).attr("fill", "#6b7280").text(rowId); ["Category", "Region", "Year"].forEach(col => { const isWin = winner?.column === col && row[col] === winner.value; rows.append("text").attr("x", colX[col]).attr("y", y + 14) .attr("fill", isWin ? config.highlightColor : "#1f2937") .attr("font-weight", isWin ? "bold" : "normal") .text(row[col]); }); }); // Bucket borders buckets.forEach((b, i) => { const y = b.start * h; const bh = (b.end - b.start + 1) * h; const isActive = i === state.currentBucket && state.phase !== "complete"; rows.append("rect").attr("x", -6).attr("y", y - 1).attr("width", w - 4).attr("height", bh) .attr("fill", "none") .attr("stroke", isActive ? config.activeColor : config.impureColor) .attr("stroke-width", isActive ? 2 : 1) .attr("rx", 4) .attr("stroke-dasharray", b.done.length > 0 ? "3,2" : "none"); }); return svg.node(); }35:T909,function renderHistograms(analysis, winner) { const div = d3.create("div").style("display", "flex").style("gap", "12px").style("flex-wrap", "wrap"); analysis.filter(a => !a.skipped).forEach(col => { const isWin = winner?.column === col.column; const { histogramWidth: w, histogramHeight: h } = config; const m = { t: 22, r: 8, b: 24, l: 32 }; const svg = div.append("svg").attr("width", w).attr("height", h) .style("border", `${isWin ? 2 : 1}px solid ${isWin ? config.highlightColor : "#e5e7eb"}`) .style("border-radius", "6px") .style("background", isWin ? config.highlightColor + "10" : "#fff"); svg.append("text").attr("x", w/2).attr("y", 14).attr("text-anchor", "middle") .attr("font-size", "11px").attr("font-weight", "bold").attr("fill", col.color) .text(col.column); if (!col.histogram?.length) return; const g = svg.append("g").attr("transform", `translate(${m.l},${m.t})`); const iw = w - m.l - m.r, ih = h - m.t - m.b; const x = d3.scaleBand().domain(col.histogram.map(d => d.value)).range([0, iw]).padding(0.25); const y = d3.scaleLinear().domain([0, d3.max(col.histogram, d => d.count)]).range([ih, 0]); g.selectAll("rect").data(col.histogram).join("rect") .attr("x", d => x(d.value)).attr("y", d => y(d.count)) .attr("width", x.bandwidth()).attr("height", d => ih - y(d.count)) .attr("fill", d => d.value === col.value ? config.highlightColor : col.color) .attr("opacity", d => d.value === col.value ? 1 : 0.6) .attr("rx", 2); g.selectAll(".lbl").data(col.histogram).join("text").attr("class", "lbl") .attr("x", d => x(d.value) + x.bandwidth()/2).attr("y", d => y(d.count) - 3) .attr("text-anchor", "middle").attr("font-size", "9px") .attr("font-weight", d => d.value === col.value ? "bold" : "normal") .attr("fill", d => d.value === col.value ? config.highlightColor : "#374151") .text(d => d.count); g.selectAll(".val").data(col.histogram).join("text").attr("class", "val") .attr("x", d => x(d.value) + x.bandwidth()/2).attr("y", ih + 12) .attr("text-anchor", "middle").attr("font-size", "8px").attr("fill", "#6b7280") .text(d => String(d.value).slice(0, 5)); }); return div.node(); }36:T771,function renderSavings(analysis, winner) { const cands = analysis.filter(a => !a.skipped && a.savings > 0).sort((a,b) => b.savings - a.savings); if (!cands.length) return html`

No candidates for this bucket

`; const w = 300, barH = 36, h = cands.length * barH + 45; const maxS = d3.max(cands, d => d.savings); const svg = d3.create("svg").attr("width", w).attr("height", h).attr("font-family", "system-ui"); svg.append("text").attr("x", 0).attr("y", 14).attr("font-size", "12px").attr("font-weight", "bold") .text("Bit Savings Competition"); const g = svg.append("g").attr("transform", "translate(0,28)"); cands.forEach((col, i) => { const y = i * barH; const isWin = winner?.column === col.column; const bw = (col.savings / maxS) * (w - 80); g.append("rect").attr("x", 0).attr("y", y + 2).attr("width", bw).attr("height", barH - 12) .attr("fill", isWin ? config.highlightColor : col.color) .attr("opacity", isWin ? 1 : 0.7).attr("rx", 4); g.append("text").attr("x", 6).attr("y", y + 17).attr("font-size", "10px").attr("fill", "#fff").attr("font-weight", "500") .text(col.column); g.append("text").attr("x", bw + 6).attr("y", y + 17).attr("font-size", "11px") .attr("font-weight", isWin ? "bold" : "normal") .attr("fill", isWin ? config.highlightColor : "#374151") .text(`${col.savings} bits`); g.append("text").attr("x", 0).attr("y", y + 29).attr("font-size", "9px").attr("fill", "#6b7280") .text(`${col.frequency} × ${col.bitsPerValue} bits`); }); if (winner) { g.append("text").attr("x", 0).attr("y", cands.length * barH + 8) .attr("font-size", "11px").attr("fill", config.highlightColor).attr("font-weight", "bold") .text(`🏆 Winner: ${winner.column} = "${winner.value}"`); } return svg.node(); }37:T5ce,function renderRLE(data, rowOrder, cols) { const div = d3.create("div").style("font-family", "system-ui").style("font-size", "11px"); div.append("div").style("font-weight", "bold").style("margin-bottom", "6px").style("font-size", "12px") .text("RLE Runs (Current Order)"); cols.forEach(col => { let runs = [], cur = null, cnt = 0; rowOrder.forEach(id => { const v = data.find(d => d.id === id)[col.name]; if (v === cur) cnt++; else { if (cur !== null) runs.push({ v: cur, c: cnt }); cur = v; cnt = 1; } }); if (cur !== null) runs.push({ v: cur, c: cnt }); const row = div.append("div").style("display", "flex").style("align-items", "center") .style("gap", "6px").style("margin-bottom", "3px"); row.append("span").style("width", "65px").style("font-weight", "500").style("color", col.color) .text(col.name + ":"); const badges = row.append("div").style("display", "flex").style("gap", "2px").style("flex-wrap", "wrap"); runs.forEach(r => { badges.append("span") .style("padding", "1px 5px") .style("background", col.color + "20") .style("border", `1px solid ${col.color}50`) .style("border-radius", "3px") .style("font-size", "9px") .text(`${String(r.v).slice(0,4)}×${r.c}`); }); row.append("span").style("color", "#6b7280").style("font-size", "10px") .text(`(${runs.length} runs)`); }); return div.node(); }38:T5d4,viewof controls = { const div = html`

`; let interval = null; div.querySelector("#reset").onclick = () => { if (interval) { clearInterval(interval); interval = null; div.querySelector("#auto").textContent = "▶▶ Auto"; } mutable state = resetState(); }; div.querySelector("#back").onclick = () => { if (interval) { clearInterval(interval); interval = null; div.querySelector("#auto").textContent = "▶▶ Auto"; } if (state.history.length > 0) { const prevState = state.history[state.history.length - 1]; mutable state = { ...prevState, history: state.history.slice(0, -1) }; } }; div.querySelector("#step").onclick = () => { if (interval) { clearInterval(interval); interval = null; div.querySelector("#auto").textContent = "▶▶ Auto"; } if (state.phase !== "complete") mutable state = stepAnimation(state, sampleData, columns); }; return div; }39:[] 2f:{"id":"a1afbbb244db581a","slug":null,"title":"Inside VertiPaq: Bucket Splitting Animation","thumbnail":"b2ae384b0d6b7b33c71c391a0049347a4d6cd63c5d0640c6e91bb60e9c713868","access_level":"public","create_time":"$D2026-01-05T10:42:55.811Z","update_time":"$D2026-01-05T11:24:12.888Z","view_time":null,"first_public_time":"$D2026-01-05T10:42:55.811Z","has_unpublished_edits":null,"fork":false,"stars":0,"starred":false,"owner":{"type":"team","id":"f1ed078e8b647276","login":"hugoberry","name":"","avatar_url":"https://avatars-next.observableusercontent.com/edbb6a6165ce69ef17c1863f7024b08435153541390d8227eb12cfb63d17d1fc","tier":"starter_2024"},"version":79,"publish_version":null,"role":null,"authored":false,"authors":[{"type":"individual","id":"4463ef404bd99b16","login":"hugoberry","name":"","avatar_url":"https://avatars-next.observableusercontent.com/edbb6a6165ce69ef17c1863f7024b08435153541390d8227eb12cfb63d17d1fc","tier":null}],"members":[{"type":"individual","id":"4463ef404bd99b16","login":"hugoberry","name":"","avatar_url":"https://avatars-next.observableusercontent.com/edbb6a6165ce69ef17c1863f7024b08435153541390d8227eb12cfb63d17d1fc","tier":null,"role":"editor"},{"type":"team","id":"f1ed078e8b647276","login":"hugoberry","name":"","avatar_url":"https://avatars-next.observableusercontent.com/edbb6a6165ce69ef17c1863f7024b08435153541390d8227eb12cfb63d17d1fc","tier":"starter_2024","role":"editor"}],"comments":[],"custom_thumbnail":false,"trashed":false,"lapsed":null,"subscribed":null,"forks":0,"collection":null,"type":"notebook","body":{"titling":"auto","title":"Inside VertiPaq: Bucket Splitting Animation","cells":[{"id":0,"value":"# Inside VertiPaq: Bucket Splitting Animation\n\nWatch how Power BI's compression engine decides row order through greedy bucket splitting.\nEach step reveals why low-cardinality columns dominate and how the algorithm balances competing columns.","pinned":false,"hidden":false,"mode":"md","author":"$undefined","summary":"$undefined","providerMetadata":"$undefined","attachments":"$undefined","output":"","database":"$undefined"},{"id":5,"value":"$31","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","providerMetadata":"$undefined","attachments":"$undefined","output":"$undefined","database":"$undefined"},{"id":8,"value":"columns = [\n { name: \"Category\", color: \"#3b82f6\" },\n { name: \"Region\", color: \"#22c55e\" },\n { name: \"Year\", color: \"#f59e0b\" }\n]","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","providerMetadata":"$undefined","attachments":"$undefined","output":"$undefined","database":"$undefined"},{"id":10,"value":"config = ({\n tableWidth: 280,\n rowHeight: 22,\n histogramWidth: 180,\n histogramHeight: 110,\n pureColor: \"#22c55e\",\n impureColor: \"#94a3b8\",\n activeColor: \"#3b82f6\",\n highlightColor: \"#f59e0b\",\n minBucketSize: 3\n})","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","providerMetadata":"$undefined","attachments":"$undefined","output":"$undefined","database":"$undefined"},{"id":14,"value":"mutable state = ({\n frame: 0,\n rowOrder: sampleData.map(d => d.id),\n buckets: [{ start: 0, end: 19, done: [] }],\n currentBucket: 0,\n winner: null,\n phase: \"initial\",\n matchCount: 0,\n nonMatchCount: 0,\n history: []\n})","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","providerMetadata":"$undefined","attachments":"$undefined","output":"$undefined","database":"$undefined"},{"id":17,"value":"$32","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","providerMetadata":"$undefined","attachments":"$undefined","output":"$undefined","database":"$undefined"},{"id":20,"value":"$33","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","providerMetadata":"$undefined","attachments":"$undefined","output":"$undefined","database":"$undefined"},{"id":23,"value":"function resetState() {\n return {\n frame: 0,\n rowOrder: sampleData.map(d => d.id),\n buckets: [{ start: 0, end: 19, done: [] }],\n currentBucket: 0,\n winner: null,\n phase: \"initial\",\n matchCount: 0,\n nonMatchCount: 0,\n history: []\n };\n}","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","providerMetadata":"$undefined","attachments":"$undefined","output":"$undefined","database":"$undefined"},{"id":26,"value":"$34","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","providerMetadata":"$undefined","attachments":"$undefined","output":"$undefined","database":"$undefined"},{"id":29,"value":"$35","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","providerMetadata":"$undefined","attachments":"$undefined","output":"$undefined","database":"$undefined"},{"id":32,"value":"$36","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","providerMetadata":"$undefined","attachments":"$undefined","output":"$undefined","database":"$undefined"},{"id":35,"value":"$37","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","providerMetadata":"$undefined","attachments":"$undefined","output":"$undefined","database":"$undefined"},{"id":38,"value":"statusMsg = ({\n initial: \"All rows start in one bucket. Analyzing which (column, value) pair gives best compression...\",\n histogram: \"Building histograms: counting value frequencies for each column in the active bucket.\",\n calculate: \"Calculating bit savings = frequency × bits_per_value. Highest savings wins!\",\n reorder: `Reordering rows: grouping all \"${state.winner?.value || '...'}\" values together.`,\n split: \"Splitting into PURE bucket (matching values, column done) and IMPURE bucket (remaining rows).\",\n complete: \"✅ Done! Compare the RLE runs now vs the original random order.\"\n})","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","providerMetadata":"$undefined","attachments":"$undefined","output":"$undefined","database":"$undefined"},{"id":70,"value":"currentAnalysis = {\n const idx = state.buckets.findIndex(b => \n b.done.length < columns.length && \n (b.end - b.start + 1) >= config.minBucketSize\n );\n if (idx === -1) return { analysis: [], winner: null };\n return utils.analyzeColumns(sampleData, state.rowOrder, state.buckets[idx], columns);\n}","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","providerMetadata":"$undefined","attachments":"$undefined","output":"$undefined","database":"$undefined"},{"id":41,"value":"$38","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","providerMetadata":"$undefined","attachments":"$undefined","output":"$undefined","database":"$undefined"},{"id":64,"value":"state.phase.charAt(0).toUpperCase() + state.phase.slice(1)","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","providerMetadata":"$undefined","attachments":"$undefined","output":"$undefined","database":"$undefined"},{"id":47,"value":"renderTable(sampleData, state.rowOrder, state.buckets, state.winner, state.phase)","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","providerMetadata":"$undefined","attachments":"$undefined","output":"$undefined","database":"$undefined"},{"id":52,"value":"renderHistograms(currentAnalysis.analysis, state.winner || currentAnalysis.winner)","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","providerMetadata":"$undefined","attachments":"$undefined","output":"$undefined","database":"$undefined"},{"id":61,"value":"renderSavings(currentAnalysis.analysis, state.winner || currentAnalysis.winner)","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","providerMetadata":"$undefined","attachments":"$undefined","output":"$undefined","database":"$undefined"},{"id":58,"value":"renderRLE(sampleData, state.rowOrder, columns)","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","providerMetadata":"$undefined","attachments":"$undefined","output":"$undefined","database":"$undefined"}],"files":"$W39","stdlib":"1"}} 30:"$2f:body"